Po co wdrażać leksykon jako macierz 2D i gigantyczny przełącznik?

Powoli pracuję nad ukończeniem studiów, a ten semestr to Kompilatory 101. Korzystamy ze Smoczej Księgi . Wkrótce w trakcie kursu mówimy o analizie leksykalnej i o tym, jak można ją wdrożyć za pomocą deterministycznych automatów skończonych (dalej DFA). Skonfiguruj różne stany leksykalne, zdefiniuj przejścia między nimi itp.

Ale zarówno profesor, jak i książka proponują wdrożenie ich za pomocą tabel przejściowych, które stanowią gigantyczną tablicę 2d (różne stany nieterminalne jako jeden wymiar i możliwe symbole wejściowe jako drugi) oraz instrukcję przełączania do obsługi wszystkich terminali a także wysyłanie do tabel przejściowych, jeśli nie są w stanie terminalnym.

Teoria jest dobra i dobra, ale jako ktoś, kto pisał kod od dziesięcioleci, implementacja jest nikczemna. Nie można go przetestować, nie można go konserwować, nie można go odczytać, a debugowanie to półtorej bólu. Co gorsza, nie widzę, jak byłoby to praktyczne, gdyby język był zdolny do UTF. Posiadanie około miliona wpisów w tabeli przejścia na stan nieterminalny staje się niespieszne w pośpiechu.

Więc o co chodzi? Dlaczego definitywna książka na ten temat mówi, żeby zrobić to w ten sposób?

Czy narzut wywołań funkcji jest tak duży? Czy jest to coś, co działa dobrze, czy jest konieczne, gdy gramatyka nie jest znana z góry (wyrażenia regularne?)? A może coś, co obsługuje wszystkie przypadki, nawet jeśli bardziej szczegółowe rozwiązania będą działać lepiej dla bardziej szczegółowych gramatyk?

( uwaga: możliwe duplikowanie „ Dlaczego warto stosować podejście OO zamiast instrukcji gigantycznego przełącznika? ” jest bliskie, ale nie dbam o OO. Funkcjonalne podejście, a nawet rozsądne imperatywne podejście z samodzielnymi funkcjami byłoby dobrze.)

Dla przykładu rozważmy język, który ma tylko identyfikatory, a są to identyfikatory [a-zA-Z]+. W implementacji DFA otrzymasz coś takiego:

private enum State
{
    Error = -1,
    Start = 0,
    IdentifierInProgress = 1,
    IdentifierDone = 2
}

private static State[][] transition = new State[][]{
    ///* Start */                  new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
    ///* IdentifierInProgress */   new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
    ///* etc. */
};

public static string NextToken(string input, int startIndex)
{
    State currentState = State.Start;
    int currentIndex = startIndex;
    while (currentIndex < input.Length)
    {
        switch (currentState)
        {
            case State.Error:
                // Whatever, example
                throw new NotImplementedException();
            case State.IdentifierDone:
                return input.Substring(startIndex, currentIndex - startIndex);
            default:
                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;
        }
    }

    return String.Empty;
}

(chociaż coś, co poprawnie obsługiwałoby koniec pliku)

W porównaniu do tego, czego bym się spodziewał:

public static string NextToken(string input, int startIndex)
{
    int currentIndex = startIndex;
    while (currentIndex < startIndex && IsLetter(input[currentIndex]))
    {
        currentIndex++;
    }

    return input.Substring(startIndex, currentIndex - startIndex);
}

public static bool IsLetter(char c)
{
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

Po NextTokenponownym przekształceniu kodu w jego własną funkcję, gdy masz wiele miejsc docelowych od początku DFA.

W praktyce tabele te są generowane z wyrażeń regularnych, które definiują tokeny języka:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'
...

Mamy już narzędzia do generowania analizatorów leksykalnych od 1975 roku, kiedy Lex został napisany.

Zasadniczo sugerujesz zastąpienie wyrażeń regularnych kodem proceduralnym. Rozwija to kilka znaków wyrażenia regularnego na kilka wierszy kodu. Odręczny kod proceduralny do analizy leksykalnej każdego średnio interesującego języka jest zarówno nieefektywny, jak i trudny w utrzymaniu.

Motywacja dla konkretnego algorytmu polega w dużej mierze na tym, że jest to ćwiczenie edukacyjne, więc stara się pozostać blisko idei DFA i utrzymywać stany i przejścia bardzo wyraźnie w kodzie. Z reguły i tak nikt nie pisałby ręcznie tego kodu - używałbyś narzędzia do generowania kodu z gramatyki. I to narzędzie nie dbałoby o czytelność kodu, ponieważ nie jest to kod źródłowy, to wynik oparty na definicji gramatyki.

Twój kod jest czystszy dla kogoś, kto utrzymuje ręcznie pisany DFA, ale nieco dalej od nauczanych pojęć.

Wewnętrzna pętla:

                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;

ma wiele zalet wydajności. Nie ma w tym żadnych rozgałęzień, ponieważ robisz dokładnie to samo dla każdego znaku wejściowego. Wydajność kompilatora może być określana przez leksykon (który musi działać w skali każdego znaku wejściowego). Było to jeszcze bardziej prawdziwe, kiedy napisano Księgę Smoków.

W praktyce, oprócz studentów CS studiujących leksyki, nikt nie musi implementować (lub debugować) tej wewnętrznej pętli, ponieważ jest ona częścią płyty głównej dostarczanej z narzędziem, które tworzy transitiontabelę.

Z pamięci - od dawna nie czytałem książki i jestem pewien, że nie przeczytałem najnowszego wydania, na pewno nie pamiętam czegoś przypominającego Javę - ta część została napisana kod ma być szablonem, a tabela jest wypełniona lexerem jak generator lexerów. Jeszcze z pamięci znajdowała się sekcja poświęcona kompresji tabel (ponownie z pamięci, została napisana w taki sposób, że miała ona zastosowanie również do parserów sterowanych tabelą, a więc być może w dalszej części książki niż to, co widziałeś). Podobnie, książka, którą pamiętam, zakładała 8-bitowy zestaw znaków. Spodziewałbym się rozdziału o obsłudze większego zestawu znaków w późniejszych wydaniach, prawdopodobnie w ramach kompresji tabeli. Podałem alternatywny sposób, aby sobie z tym poradzić jako odpowiedź na pytanie SO.

Pewna przewaga wydajności wynika z posiadania ścisłej pętli danych sterowanej w nowoczesnej architekturze: jest ona dość przyjazna dla pamięci podręcznej (jeśli skompresowałeś tabele), a przewidywanie skoku jest tak doskonałe, jak to możliwe (jedna chybienie na końcu leksemu, może jedna tęsknię za przesłaniem przełącznika do kodu, który zależy od symbolu; przy założeniu, że dekompresja tabeli może być wykonana za pomocą przewidywalnych skoków). Przeniesienie tego automatu stanów do czystego kodu obniżyłoby wydajność przewidywania skoku i być może zwiększyło ciśnienie pamięci podręcznej.

Po wcześniejszym zapoznaniu się z Dragon Book, głównym powodem posiadania dźwigni i parserów sterowanych przez tabelę jest to, że możesz używać wyrażeń regularnych do generowania leksera i BNF do generowania parsera. Książka obejmuje także działanie narzędzi takich jak lex i yacc, a także po to, abyś wiedział, jak działają te narzędzia. Ponadto ważne jest, abyś przeszedł przez kilka praktycznych przykładów.

Pomimo wielu komentarzy, nie ma to nic wspólnego ze stylem kodu, który został napisany w latach 40., 50., 60. ..., chodzi o uzyskanie praktycznego zrozumienia tego, co narzędzia robią dla ciebie i co masz zrobić, aby działały. Ma to wszystko związek z podstawowym zrozumieniem działania kompilatorów zarówno z teoretycznego, jak i praktycznego punktu widzenia.

Mam nadzieję, że twój instruktor pozwoli ci również używać leksyk i yacc (chyba że jest to klasa dla absolwentów i możesz pisać leksykon i yacc).

Późno na imprezę :-) Tokeny są zestawiane z wyrażeniami regularnymi. Ponieważ jest ich wiele, masz silnik wielokrotnego wyrażenia regularnego, który z kolei jest gigantycznym DFA.

„Co gorsza, nie widzę, jak byłoby to praktyczne, gdyby język był zdolny do obsługi UTF”.

Jest to nieistotne (lub przejrzyste). Poza tym UTF ma niezłą własność, jego podmioty nie pokrywają się nawet częściowo. Np. Bajt reprezentujący znak „A” (z tabeli ASCII-7) nie jest ponownie używany dla żadnego innego znaku UTF.

Tak więc masz pojedynczy DFA (który jest wielokrotnym wyrażeniem regularnym) dla całego leksera. Jak lepiej zapisać to niż tablica 2D?