Jaką procedurę stosuje się podczas pisania leksykonu opartego na gramatyce?

Podczas czytania odpowiedzi na pytanie Wyjaśnienie dotyczące gramatyk, leksyk i parserów odpowiedź brzmiała:

[...] gramatyka BNF zawiera wszystkie reguły potrzebne do analizy leksykalnej i analizy.

Wydawało mi się to nieco dziwne, ponieważ do tej pory zawsze myślałem, że leksyk nie jest w ogóle oparty na gramatyce, podczas gdy parser był w dużej mierze oparty na jednym. Doszedłem do tego wniosku po przeczytaniu licznych postów na blogu o pisaniu leksykonów, i nigdy nie wykorzystałem ¹ EBNF / BNF jako podstawy do projektowania.

Jeśli zarówno leksery, jak i parsery, oparte są na gramatyce EBNF / BNF, to jak byś zajął się tworzeniem leksemu za pomocą tej metody? To znaczy, jak skonstruowałbym leksykon przy użyciu danej gramatyki EBNF / BNF?

Widziałem wiele, wiele stanowisko, które zajmują się napisanie parsera przy użyciu EBNF / BNF jako przewodnik lub planem, ale natrafiłem nikt do tej pory, które pokazują jego odpowiednik z projektu Lexer.

Weźmy na przykład następującą gramatykę:

input = digit| string ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
string = '"', { all characters - '"' }, '"' ;
all characters = ? all visible characters ? ;

Jak stworzyć leksykę opartą na gramatyce? Mogłem sobie wyobrazić, jak parser można napisać z takiej gramatyki, ale nie rozumiem koncepcji robienia tego samego z leksem.

Czy istnieją pewne reguły lub logika używane do wykonania takiego zadania, jak przy pisaniu parsera? Szczerze mówiąc, zaczynam się zastanawiać, czy projekty leksykalne w ogóle wykorzystują gramatykę EBNF / BNF, a tym bardziej bazują na jednym.

¹ _{Rozszerzony formularz Backus – Naur i Formularz Backus – Naur}

Lexery to tylko proste parsery, które są używane jako optymalizacja wydajności dla głównego parsera. Jeśli mamy leksykon, leksykon i parser pracują razem, aby opisać pełny język. Parsery, które nie mają osobnego etapu leksykalnego, są czasami nazywane „bez skanera”.

Bez leksemów analizator składni musiałby działać na zasadzie znak po znaku. Ponieważ analizator składni musi przechowywać metadane dotyczące każdego elementu wejściowego i może być konieczne wstępne obliczenie tabel dla każdego stanu elementu wejściowego, spowodowałoby to niedopuszczalne zużycie pamięci dla dużych rozmiarów wejściowych. W szczególności nie potrzebujemy osobnego węzła na znak w abstrakcyjnym drzewie składni.

Ponieważ tekst po znaku jest dość dwuznaczny, spowodowałoby to również o wiele więcej niejasności, które irytujące w obsłudze. Wyobraź sobie regułę R → identifier | "for " identifier. gdzie identyfikator składa się z liter ASCII. Jeśli chcę uniknąć dwuznaczności, potrzebuję teraz 4-znakowego spojrzenia w przód, aby ustalić, którą alternatywę wybrać. Za pomocą leksera analizator składni musi tylko sprawdzić, czy ma token IDENTYFIKATOR, czy FOR - z wyprzedzeniem 1-token.

Gramatyki dwupoziomowe.

Lexery pracują, tłumacząc wprowadzony alfabet na wygodniejszy.

Parser bez skanera opisuje gramatykę (N, Σ, P, S), w której nieterminale N są lewą stroną reguł gramatyki, alfabet Σ to np. Znaki ASCII, produkcje P to reguły w gramatyce , a symbol początkowy S jest regułą najwyższego poziomu parsera.

Lexer definiuje teraz alfabet tokenów a, b, c,…. Dzięki temu główny parser może używać tych tokenów jako alfabetu: Σ = {a, b, c,…}. Dla leksera te tokeny nie są terminalami, a reguła początkowa S _L to S _L → ε | S | b S | c S | … Czyli dowolna sekwencja tokenów. Reguły gramatyki leksykalnej to wszystkie reguły niezbędne do wytworzenia tych tokenów.

Przewaga wydajności wynika z wyrażania reguł leksykalnych jako zwykłego języka . Można je analizować znacznie wydajniej niż języki bezkontekstowe. W szczególności zwykłe języki można rozpoznać w przestrzeni O (n) i czasie O (n). W praktyce generator kodu może zamienić taki leksykon w wysoce wydajne tabele skoków.

Wydobywanie tokenów z gramatyki.

Na przykład: zasady digiti stringwyrażone są na poziomie znak po znaku. Możemy użyć ich jako tokenów. Reszta gramatyki pozostaje nienaruszona. Oto gramatyka leksykalna, napisana jako gramatyka prostoliniowa, aby wyjaśnić, że jest regularna:

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
string = '"' , string-rest ;
string-rest = '"' | STRING-CHAR, string-rest ;
STRING-CHAR = ? all visible characters ? - '"' ;

Ale ponieważ jest on regularny, zwykle używamy wyrażeń regularnych do wyrażenia składni tokena. Oto powyższe definicje tokenów jako wyrażeń regularnych, napisane przy użyciu składni wykluczania klas znaków .NET i znaków POSIX:

digit ~ [0-9]
string ~ "[[:print:]-["]]*"

Gramatyka dla głównego parsera zawiera następnie pozostałe reguły nieobsługiwane przez leksykon. W twoim przypadku jest to po prostu:

input = digit | string ;

Gdy leksykonów nie można łatwo użyć.

Projektując język, zwykle zwracamy uwagę na to, aby gramatykę można było w prosty sposób rozdzielić na poziom leksykalny i poziom analizatora składni, a poziom leksykalny opisuje zwykły język. Nie zawsze jest to możliwe.

• Podczas osadzania języków. Niektóre języki pozwalają interpolacji kod do strun: "name={expression}". Składnia wyrażenia jest częścią gramatyki bezkontekstowej i dlatego nie można jej wyrazić za pomocą wyrażenia regularnego. Aby rozwiązać ten problem, albo rekombinujemy parser z lekserem, albo wprowadzamy dodatkowe tokeny, takie jak STRING-CONTENT, INTERPOLATE-START, INTERPOLATE-END. Reguła gramatyka na sznurku może wtedy wyglądać następująco: String → STRING-START STRING-CONTENTS { INTERPOLATE-START Expression INTERPOLATE-END STRING-CONTENTS } STRING-END. Oczywiście wyrażenie może zawierać inne ciągi, co prowadzi nas do następnego problemu.

• Kiedy tokeny mogą się zawierać. W językach podobnych do C słowa kluczowe są nie do odróżnienia od identyfikatorów. Zostało to rozwiązane w leksykach poprzez nadanie priorytetu słowom kluczowym nad identyfikatorami. Taka strategia nie zawsze jest możliwa. Wyobraź sobie plik konfiguracyjny Line → IDENTIFIER " = " REST, w którym reszta to dowolny znak do końca linii, nawet jeśli reszta wygląda jak identyfikator. Przykładowa linia to a = b c. Lexer jest naprawdę głupi i nie wie, w jakiej kolejności mogą wystąpić tokeny. Więc jeśli nadamy priorytet IDENTYFIKATOROWI nad RESTEM, leksykon da nam IDENT(a), " = ", IDENT(b), REST( c). Jeśli nadamy priorytet REST przed IDENTYFIKATOREM, leksykon właśnie nam to zapewni REST(a = b c).

  Aby rozwiązać ten problem, musimy ponownie połączyć leksykon z parserem. Oddzielenie można nieco utrzymać, czyniąc lexera leniwym: za każdym razem, gdy parser potrzebuje następnego tokena, żąda go od lexera i podaje mu zestaw akceptowalnych tokenów. Skutecznie tworzymy nową regułę najwyższego poziomu dla gramatyki leksykalnej dla każdej pozycji. W rezultacie wywołałoby to połączenia nextToken(IDENT), nextToken(" = "), nextToken(REST)i wszystko działa dobrze. Wymaga to analizatora składni, który zna pełny zestaw akceptowalnych tokenów w każdej lokalizacji, co implikuje analizator składający się z dołu, taki jak LR.

• Kiedy leksykon musi utrzymać stan. Np. Język Python ogranicza bloki kodu nie przez nawiasy klamrowe, ale przez wcięcia. Istnieją sposoby radzenia sobie ze składnią wrażliwą na układ w obrębie gramatyki, ale dla Pythona te techniki są nadmierne. Zamiast tego leksykon sprawdza wcięcie każdej linii i emituje tokeny INDENT, jeśli zostanie znaleziony nowy blok wcięcia, i DEDENT, jeśli blok się skończył. Upraszcza to podstawową gramatykę, ponieważ może teraz udawać, że te tokeny są jak nawiasy klamrowe. Jednak leksykon musi teraz zachować stan: bieżące wcięcie. Oznacza to, że leksykon technicznie nie opisuje już zwykłego języka, ale język kontekstowy. Na szczęście ta różnica nie ma znaczenia w praktyce, a leksykon Pythona może nadal działać w czasie O (n).