Wymyślanie tokenów dla leksera

Piszę parser dla utworzonego przeze mnie języka znaczników (piszę w Pythonie, ale to nie jest tak naprawdę istotne w przypadku tego pytania - w rzeczywistości, jeśli wydaje się to złym pomysłem, chętnie zaproponuję lepszą ścieżkę) .

Czytam o parserach tutaj: http://www.ferg.org/parsing/index.html i pracuję nad napisaniem leksera, który, jeśli dobrze rozumiem, powinien podzielić zawartość na tokeny. Nie rozumiem, jakich typów tokenów powinienem używać i jak je tworzyć. Na przykład typy tokenów w przykładzie, z którym się połączyłem, to:

• STRUNOWY
• IDENTYFIKATOR
• NUMER
• BIAŁA PRZESTRZEŃ
• KOMENTARZ
• EOF
• Wiele symboli, takich jak {i (liczy się jako własny typ tokena)

Problemem jest to, że bardziej ogólne typy tokenów wydają mi się nieco arbitralne. Na przykład, dlaczego STRING ma swój własny osobny typ tokena kontra IDENTYFIKATOR. Ciąg może być reprezentowany jako STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Może to mieć również związek z trudnościami mojego języka. Na przykład deklaracje zmiennych są zapisywane {var-name var value}i wdrażane za pomocą {var-name}. Wygląda na to, że powinny '{'i '}'powinny być ich własnymi tokenami, ale czy VAR_NAME i VAR_VALUE są odpowiednimi typami tokenów, czy też oba byłyby objęte IDENTYFIKATOREM? Co więcej, VAR_VALUE może faktycznie zawierać białe znaki. Biały var-nameznak po służy do oznaczenia początku wartości w deklaracji. Wszelkie inne białe znaki są częścią wartości. Czy ta biała przestrzeń staje się własnym tokenem? Białe znaki mają tylko to znaczenie w tym kontekście. Co więcej, {może nie być początkiem deklaracji zmiennej. Zależy to od kontekstu (znowu to słowo!). {:rozpoczyna deklarację nazwy i{ może być nawet używany jako część pewnej wartości.

Mój język jest podobny do Pythona, ponieważ bloki są tworzone z wcięciem. Czytałem o tym, w jaki sposób Python używa leksykonu do tworzenia tokenów INDENT i DEDENT (które służą mniej więcej tak, jak {i }robią w wielu innych językach). Python twierdzi, że jest pozbawiony kontekstu, co oznacza dla mnie, że przynajmniej leksykon nie powinien dbać o to, gdzie jest w strumieniu podczas tworzenia tokenów. Skąd leksem Python wie, że buduje token INDENT o określonej długości, nie wiedząc o poprzednich znakach (np. Że poprzednia linia była nową linią, więc zacznij tworzyć spacje dla INDENT)? Pytam, bo ja też muszę to wiedzieć.

Moje ostatnie pytanie jest najgłupsze: dlaczego leksykon jest nawet potrzebny? Wydaje mi się, że analizator składni mógłby przejść znak po znaku i dowiedzieć się, gdzie jest i czego się spodziewa. Czy leksykon dodaje korzyści wynikające z prostoty?

Twoje pytanie (jak wskazano w ostatnim akapicie) tak naprawdę nie dotyczy lexera, ale dotyczy prawidłowego zaprojektowania interfejsu między lexerem a parserem. Jak można sobie wyobrazić, istnieje wiele książek o projektowaniu leksykonów i parserów. Zdarza mi się, że parser Dicka Grune'a może nie być dobrą książką wprowadzającą. Zdarza mi się bardzo nie lubić książki opartej na języku C autorstwa Appela , ponieważ kodu nie można łatwo rozszerzyć do własnego kompilatora (z powodu problemów z zarządzaniem pamięcią nieodłącznie związanych z decyzją udawania C jest jak ML). Moje własne wprowadzenie było książką PJ Browna , ale nie jest to dobre ogólne wprowadzenie (choć całkiem dobre dla tłumaczy). Ale wracając do twojego pytania.

Odpowiedź brzmi: zrób tyle, ile możesz w leksykach, bez konieczności używania ograniczeń skierowanych do przodu lub do tyłu.

Oznacza to, że (w zależności od szczegółów języka) powinieneś rozpoznać ciąg znaków jako „znak, po którym następuje ciąg nie-”, a następnie kolejny „znak. Zwróć to do parsera jako pojedynczą jednostkę. Istnieje kilka powody tego, ale ważne są

1. Zmniejsza to stan, jaki parser musi utrzymać, ograniczając zużycie pamięci.
2. Pozwala to implementacji leksykowej skoncentrować się na rozpoznawaniu podstawowych elementów składowych i uwalnia analizator składni do opisania, w jaki sposób poszczególne elementy składniowe są używane do budowy programu.

Bardzo często parsery mogą podjąć natychmiastowe działania po otrzymaniu tokena od leksera. Na przykład natychmiast po otrzymaniu IDENTYFIKATORA analizator składni może wykonać wyszukiwanie tablicy symboli, aby sprawdzić, czy symbol jest już znany. Jeśli twój analizator składni również analizuje stałe ciągów jako QUOTE (PRZESTRZEŃ IDENTYFIKATORA) * QUOTE, wykonasz wiele nieistotnych odnośników w tablicy symboli lub zakończysz podnoszenie odnośników tablicy symboli wyżej w drzewie elementów składniowych parsera, ponieważ możesz to zrobić w tym momencie jesteś pewien, że nie patrzysz na sznurek.

Aby powtórzyć to, co próbuję powiedzieć, ale inaczej, leksykon powinien zajmować się pisownią rzeczy, a parser strukturą rzeczy.

Możesz zauważyć, że mój opis tego, jak wygląda łańcuch, przypomina wyrażenie regularne. To nie przypadek. Analizatory leksykalne są często implementowane w małych językach (w sensie doskonałej książki Jona Bentleya o programowaniu pereł ), które używają wyrażeń regularnych. Przyzwyczajam się do myślenia w kategoriach wyrażeń regularnych podczas rozpoznawania tekstu.

Jeśli chodzi o pytanie dotyczące białych znaków, rozpoznaj je w leksyrze. Jeśli twój język ma być w dowolnym formacie, nie zwracaj tokenów WHITESPACE do parsera, ponieważ będzie musiał je tylko wyrzucić, więc reguły produkcji twojego parsera będą zasadniczo spamowane hałasem - rzeczy, które należy rozpoznać po prostu rzucać je z dala.

Co do tego, co to znaczy o tym, jak należy obchodzić się z białymi spacjami, gdy ma to znaczenie składniowe, nie jestem pewien, czy mogę dokonać oceny, która naprawdę będzie dobrze działać, nie wiedząc więcej o twoim języku. Uważam, że unikam przypadków, w których białe znaki są czasami ważne, a czasem nie, i używam pewnego rodzaju separatora (np. Cudzysłowu). Ale jeśli nie możesz zaprojektować języka w dowolny sposób, ta opcja może być niedostępna.

Istnieją inne sposoby projektowania parsowania języków. Z pewnością istnieją systemy konstrukcyjne kompilatora, które pozwalają na określenie połączonego systemu leksykalnego i parsera (myślę, że robi to wersja ANTLR w Javie ), ale nigdy go nie użyłem.

Ostatnia uwaga historyczna. Kilkadziesiąt lat temu ważne było, aby Lexer zrobił jak najwięcej przed przekazaniem do parsera, ponieważ oba programy nie zmieściłyby się w pamięci w tym samym czasie. Robiąc więcej w lekserze, pozostawia więcej dostępnej pamięci, aby parser był inteligentny. Ja używałem Whitesmiths kompilator C przez kilka lat, a jeśli dobrze rozumiem, że to działa tylko w 64KB pamięci RAM (to był program mały model MS-DOS), a mimo to tłumaczone wariant C, który był bardzo, bardzo blisko ANSI C.

Przyjmę twoje ostatnie pytanie, które w rzeczywistości nie jest głupie. Parsery mogą tworzyć złożone konstrukcje na zasadzie znak po znaku. O ile pamiętam, gramatyka w Harbison i Steele („C - Podręcznik referencyjny”) ma produkcje, które wykorzystują pojedyncze znaki jako terminale i tworzą identyfikatory, ciągi, liczby itp. Jako nieterminale z pojedynczych znaków.

Z punktu widzenia języków formalnych wszystko, co leksyks oparty na wyrażeniach regularnych może rozpoznać i sklasyfikować jako „literał łańcuchowy”, „identyfikator”, „liczba”, „słowo kluczowe” itd., Nawet parser LL (1) może rozpoznać. Nie ma więc teoretycznego problemu z użyciem generatora analizatora składni do rozpoznania wszystkiego.

Z algorytmicznego punktu widzenia rozpoznawanie wyrażeń regularnych może działać znacznie szybciej niż jakikolwiek parser. Z punktu widzenia kognitywnego programiście prawdopodobnie łatwiej jest przerwać pracę między lekserem wyrażeń regularnych a pisemnym analizatorem składni generatora analizatorów.

Powiedziałbym, że względy praktyczne powodują, że ludzie podejmują decyzję o oddzielnych leksykonach i analizatorach składni.

Wygląda na to, że próbujesz napisać leksykon / parser, ale tak naprawdę nie rozumiesz gramatyki. Zazwyczaj, gdy ludzie piszą leksykon i parser, piszą je, aby dostosować się do jakiejś gramatyki. Lexer powinien zwrócić tokeny w gramatyce, podczas gdy parser używa tych tokenów do dopasowania reguł / terminali . Jeśli możesz łatwo parsować dane wejściowe, przechodząc bajt po bajcie, to leksykon i parser mogą być przesadzone.

Lexers upraszczają sprawy.

Omówienie gramatyki : Gramatyka to zestaw zasad określających wygląd niektórych składni lub danych wejściowych. Na przykład, tutaj jest gramatyka zabawki (polecenie proste to symbol startowy):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Ta gramatyka oznacza, że ​​- Polecenie proste
składa się z
A) SŁOWA, a następnie DIGIT, a następnie AND_SYMBOL (są to „tokeny”, które definiuję)
B) „ Wyrażenie_dodatkowe ” (jest to reguła lub „nieterminalny”)

Wyrażenie dodatkowe składa się z:
NUM, po którym następuje „+”, po którym następuje NUM (NUM to „token”, który definiuję, „+” to dosłowny znak plus).

Dlatego, ponieważ simple_command jest „symbolem startowym” (miejscem, w którym zaczynam), kiedy otrzymuję token, sprawdzam, czy pasuje do simple_command. Jeśli pierwszym tokenem na wejściu jest WORD, a następnym tokenem jest DIGIT, a następnym tokenem jest AND_SYMBOL, to dopasowałem trochę polecenia simple_ i mogę podjąć pewne działania. W przeciwnym razie postaram się dopasować go do innej reguły polecenia simple_command, którą jest wyrażenie_wyrażenia. Tak więc, jeśli pierwszym tokenem był NUM, a następnie „+”, a następnie NUM, to dopasowałem polecenie simple_ i wykonuję pewne działania. Jeśli nie jest to żadna z tych rzeczy, mam błąd składniowy.

To bardzo, bardzo podstawowe wprowadzenie do gramatyki. Aby uzyskać dokładniejsze zrozumienie, zapoznaj się z tym artykułem wiki i wyszukaj w Internecie bezkontekstowe samouczki gramatyczne.

Korzystając z układu lexer / parser, oto przykład tego, jak może wyglądać twój parser:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, więc ten kod jest trochę brzydki i nigdy nie polecałbym potrójnego zagnieżdżenia instrukcji if. Ale chodzi o to, wyobraź sobie , że próbujesz zrobić to ponad znak po znaku, zamiast używać swoich miłych modułowych funkcji „get_next_token” i „peek_next_token” . Poważnie, spróbuj. Nie spodoba ci się wynik. Teraz pamiętaj, że powyższa gramatyka jest około 30 razy mniej złożona niż prawie jakakolwiek użyteczna gramatyka. Czy widzisz zalety korzystania z leksyk?

Szczerze mówiąc, lekserzy i parsery nie są najbardziej podstawowymi tematami na świecie. Poleciłbym najpierw przeczytać i zrozumieć gramatykę, potem trochę o leksykonach / parserach, a potem zanurzyć się.

Moje ostatnie pytanie jest najgłupsze: dlaczego leksykon jest nawet potrzebny? Wydaje mi się, że analizator składni mógłby przejść znak po znaku i dowiedzieć się, gdzie jest i czego się spodziewa.

To nie jest głupie, to po prostu prawda.

Ale wykonalność zależy w jakiś sposób od twoich narzędzi i celów. Na przykład, jeśli używasz yacc bez leksera, a chcesz dopuścić litery Unicode w identyfikatorach, będziesz musiał napisać dużą i brzydką regułę, która wyjaśnia wszystkie poprawne znaki. Podczas gdy w lekturze możesz zapytać procedurę biblioteczną, czy postać należy do kategorii liter.

Używanie lub nie używanie leksera jest kwestią posiadania poziomu abstrakcji między twoim językiem a poziomem postaci. Zauważ, że obecnie poziom postaci jest kolejną abstrakcją powyżej poziomu bajtów, która jest abstrakcją powyżej poziomu bitów.

W końcu możesz nawet parsować na poziomie bitów.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Nie, nie może. Co "("? Według ciebie to nie jest prawidłowy ciąg. I ucieka?

Zasadniczo najlepszym sposobem traktowania białych znaków jest zignorowanie ich poza ograniczanie tokenów. Wiele osób woli bardzo różne białe znaki, a egzekwowanie reguł białych znaków jest w najlepszym razie kontrowersyjne.