Czy oddzielne testy parsowania i leksykacji są dobrą praktyką w przypadku kombinacji parserów?

18

Kiedy zacząłem używać parseratorów, moją pierwszą reakcją było poczucie wyzwolenia z czegoś, co wydawało się sztuczną różnicą między analizą składniową a leksyką. Nagle wszystko zaczęło się przetwarzać!

Ostatnio jednak natknąłem się na ten post na codereview.stackexchange ilustrujący kogoś przywracającego to rozróżnienie. Na początku myślałem, że to z ich strony głupie, ale potem fakt, że w Parsec istnieją funkcje wspierające to zachowanie, każe mi się zastanawiać.

Jakie są zalety / wady analizy składniowej nad już zsynchronizowanym strumieniem w kombinatorach parsera?

Eli Frey
źródło
Czy ktoś mógłby dodać tag [parser-combinator]?
Eli Frey,

Odpowiedzi:

15

Podczas analizy rozumiemy najczęściej analizę języków bezkontekstowych. Język bezkontekstowy ma większą moc niż zwykły, dlatego parser może (najczęściej) natychmiast wykonać zadanie analizatora leksykalnego.

Ale jest to a) dość nienaturalne b) często nieefektywne.

Dla a), jeśli myślę o tym, jak na przykład ifwygląd ekspresyjnych, myślę, że jeśli wyrażenie TO wyrażenie ELSE wyrażenie a nie „i” „f”, być może niektóre przestrzenie, a następnie dowolny znak wyrazem może zacząć itp Państwo uzyskać pomysł.

Dla b) istnieją potężne narzędzia, które wykonują doskonałą pracę rozpoznając byty leksykalne, takie jak identyfikatory, literały, nawiasy wszelkiego rodzaju itp. Wykonają swoją pracę praktycznie w krótkim czasie i zapewnią ci ładny interfejs: listę tokenów. Nie musisz się już martwić o pomijanie spacji w parserze, twój parser będzie znacznie bardziej abstrakcyjny, gdy będzie zajmował się tokenami, a nie postaciami.

W końcu, jeśli uważasz, że parser powinien być zajęty niskopoziomowymi rzeczami, to po co w ogóle przetwarzać znaki? Można to również napisać na poziomie bitów! Widzisz, taki parser działający na poziomie bitów byłby prawie niezrozumiały. To samo dotyczy postaci i żetonów.

Tylko moje 2 centy.

Ingo
źródło
3
Tylko ze względu na precyzję: parser zawsze może wykonać zadanie analizatora leksykalnego.
Giorgio
Również w odniesieniu do wydajności: nie jestem pewien, czy parser byłby mniej wydajny (wolniej). Spodziewałbym się, że powstała gramatyka będzie zawierała podprogram gramatyki opisujący zwykły język, a kod tej podgrupy będzie tak szybki jak odpowiadający jej analizator leksykalny. IMO prawdziwą kwestią jest (a): jak naturalna, intuicyjna jest praca z prostszym, bardziej abstrakcyjnym parserem.
Giorgio
@Giorgio - Jeśli chodzi o twój pierwszy komentarz: masz rację. Miałem tu na myśli przypadki, w których leksykon pragmatycznie wykonuje pewne czynności, które ułatwiają gramatykę, dzięki czemu można użyć LALR (1) zamiast LALR (2).
Ingo
2
Usunąłem moją akceptację twojej odpowiedzi po dalszych eksperymentach i refleksjach. Wygląda na to, że wy dwaj pochodzicie ze świata Antlr i innych. Biorąc pod uwagę pierwszorzędną naturę kombinatorów parserów, często po prostu definiuję otoki parsera dla moich parserów tokenów, pozostawiając każdy token jako pojedynczą nazwę w warstwie parsującej parserów. na przykład wyglądałby twój przykład if if = string "if" >> expr >> string "then" >> expr >> string "else" >> expr.
Eli Frey
1
Wydajność to wciąż otwarte pytanie, zrobię kilka testów porównawczych.
Eli Frey,
8

Wszyscy sugerują, że oddzielanie leksyk i parsowania jest „dobrą praktyką” - muszę się nie zgodzić - w wielu przypadkach wykonywanie leksyk i parsowania w jednym przebiegu daje znacznie więcej mocy, a implikacje dotyczące wydajności nie są tak złe, jak przedstawiono w inne odpowiedzi (patrz Packrat ).

To podejście świeci, gdy trzeba wymieszać wiele różnych języków w jednym strumieniu wejściowym. Jest to potrzebne nie tylko przez dziwne języki zorientowane na metaprogramowanie, takie jak Katahdin i podobne , ale także w przypadku znacznie bardziej popularnych aplikacji, takich jak programowanie piśmiennicze (mieszanie lateksu i, powiedzmy, C ++), używanie HTML w komentarzach, wypychanie Javascript do HTML i wkrótce.

Logika SK
źródło
W mojej odpowiedzi zasugerowałem, że jest to „dobra praktyka w określonych kontekstach”, a nie że „lepsza praktyka we wszystkich kontekstach”.
Giorgio
5

Analizator leksykalny rozpoznaje zwykły język, a parser rozpoznaje język bezkontekstowy. Ponieważ każdy język regularny jest również pozbawiony kontekstu (może być zdefiniowany przez tak zwaną gramatykę liniowo-prawą ), analizator składni może również rozpoznać język regularny, a rozróżnienie między analizatorem składni i analizatorem leksykalnym wydaje się dodawać niepotrzebną złożoność: pojedynczy kontekst -wolna gramatyka (parser) mogłaby wykonać parser i analizator leksykalny.

Z drugiej strony przydatne może być przechwycenie niektórych elementów języka bezkontekstowego za pomocą zwykłego języka (a zatem analizatora leksykalnego), ponieważ

  1. Często elementy te pojawiają się tak często, że można je traktować w standardowy sposób: rozpoznawanie literałów liczbowych i łańcuchowych, słów kluczowych, identyfikatorów, pomijanie białych znaków i tak dalej.
  2. Zdefiniowanie zwykłego języka tokenów upraszcza wynikową gramatykę bez kontekstu, np. Można argumentować w kategoriach identyfikatorów, a nie pojedynczych znaków, lub całkowicie ignorować białe znaki, jeśli nie jest to istotne dla tego konkretnego języka.

Tak więc oddzielenie analizy składniowej od analizy leksykalnej ma tę zaletę, że można pracować z prostszą gramatyką bezkontekstową i zamknąć niektóre podstawowe (często rutynowe) zadania w analizatorze leksykalnym (divide et impera).

EDYTOWAĆ

Nie znam się na kombinatorach parsera, więc nie jestem pewien, jak powyższe rozważania mają zastosowanie w tym kontekście. Mam wrażenie, że nawet jeśli w kombinatorach parsera istnieje tylko jedna gramatyka bezkontekstowa, rozróżnienie między dwoma poziomami (analiza leksykalna / parsowanie) może pomóc uczynić tę gramatykę bardziej modułową. Jak powiedziano, dolna warstwa analizy leksykalnej może zawierać podstawowe parsery wielokrotnego użytku dla identyfikatorów, literałów i tak dalej.

Giorgio
źródło
2
Leksemy nie należą do gramatyki naturalnej, lecz zgodnie z konwencją, ponieważ wszystkie leksyksy są zbudowane na silnikach wyrażeń regularnych. Ogranicza ekspresyjną moc języków, które możesz zaprojektować.
SK-logic
1
Czy możesz podać przykład języka, dla którego właściwe byłoby zdefiniowanie leksemów, których nie można opisać jako zwykły język?
Giorgio
1
na przykład w kilku językach specyficznych dla domeny, które zbudowałem, identyfikatorami mogły być wyrażenia TeX, które uprościły ładne drukowanie kodu, np. wyrażenie takie \alpha'_1 (K_0, \vec{T}), gdzie \ alpha'_1, K_0 i \ vec {T} są identyfikatorami.
SK-logika
1
Biorąc pod uwagę gramatykę bezkontekstową, zawsze możesz wziąć nieterminalne N i traktować słowa, które mogą one wywodzić, jako jednostki, które same w sobie mają sens (np. Wyrażenie, termin, liczba, wyrażenie). Można to zrobić niezależnie od tego, jak parsujesz tę jednostkę (parser, parser + lexer itp.). IMO wybór parsera i leksykonu jest bardziej techniczny (jak zaimplementować parsowanie) niż semantyczny (jakie jest znaczenie bloków kodu, który analizujesz). Może coś przeoczam, ale te dwa aspekty wyglądają dla mnie prostopadle.
Giorgio
3
Zgadzam się zatem z tobą: jeśli zdefiniujesz dowolne podstawowe bloki konstrukcyjne ( leksemy ) i chcesz użyć analizatora leksykalnego do ich rozpoznania, nie zawsze jest to możliwe. Zastanawiam się tylko, czy taki jest cel leksyk. O ile rozumiem, cel analizatora leksykalnego jest bardziej techniczny: usunięcie parsera z żmudnych szczegółów implementacji niskiego poziomu.
Giorgio
3

Po prostu leksykanie i parsowanie powinny być oddzielone, ponieważ są to różne złożoności. Lexing to DFA (deterministyczny automat skończony), a parser to PDA (automat push-down). Oznacza to, że parsowanie z natury zużywa więcej zasobów niż leksykon, a istnieją specjalne techniki optymalizacji dostępne tylko dla DFA. Ponadto pisanie skończonej maszyny stanów jest znacznie mniej złożone i łatwiejsze do zautomatyzowania.

Marnujesz się, używając algorytmu parsowania.

DeadMG
źródło
Jeśli użyjesz analizatora leksykalnego do analizy leksykalnej, PDA nigdy nie użyje stosu, po prostu będzie działał jako DFA: po prostu zużywa dane wejściowe i przeskakuje między stanami. Nie jestem w 100% pewien, ale myślę, że techniki optymalizacji (zmniejszenie liczby stanów), które można zastosować do DFA, można również zastosować do PDA. Ale tak: łatwiej jest napisać analizator leksykalny jako taki bez użycia mocniejszego narzędzia, a następnie napisać na nim prostszy parser.
Giorgio
Ponadto sprawia, że ​​całość jest bardziej elastyczna i łatwa w utrzymaniu. Załóżmy na przykład, że mamy parser dla języka Haskell bez reguły układu (tj. Z średnikami i nawiasami klamrowymi). Jeśli mamy osobny leksykon, moglibyśmy teraz dodać reguły układu, po prostu wykonując kolejne przejście przez tokeny, dodając nawiasy klamrowe i średniki w razie potrzeby. Lub, dla prostszego przykładu: załóżmy, że zaczynamy od języka obsługującego znaki ASCII tylko w identyfikatorach, a teraz chcemy obsługiwać litery Unicode w identyfikatorach.
Ingo
1
@Ingo i dlaczego miałbyś to robić w osobnym lekturze? Po prostu rozłóż te terminale.
SK-logic
1
@ SK-logic: Nie jestem pewien, czy rozumiem twoje pytanie. Dlaczego osobny leksykon może być dobrym wyborem, który starałem się uzasadnić w swoim poście.
Ingo
Giorgio, nie. Stos jest kluczowym składnikiem normalnego parsera w stylu LALR. Wykonywanie leksykacji za pomocą analizatora składni jest ohydnym marnotrawstwem pamięci (zarówno pamięci statycznej, jak i dynamicznie przydzielanej) i będzie znacznie wolniejsze. Model Lexer / Parser jest wydajny - użyj go :)
riwalk
1

Jedną z głównych zalet oddzielnej analizy składniowej / leksykalnej jest reprezentacja pośrednia - strumień tokenu. Można to przetwarzać na różne sposoby, które w innym przypadku nie byłyby możliwe przy połączeniu lex / parsowania.

To powiedziawszy, odkryłem, że dobra, dobra rekurencyjna rekurencja może być mniej skomplikowana i łatwiejsza w pracy z uczeniem się jakiegoś generatora parsera i konieczności wymyślenia, jak wyrazić słabość gramatyka w ramach reguł generatora parsera.

sylvanaar
źródło
Czy możesz wyjaśnić więcej na temat gramatyk, które są łatwiej wyrażane na prefabrykowanym strumieniu niż wykonywane w czasie analizy? Mam tylko doświadczenie w implementacji języków zabawek i niewiele formatów danych, więc być może coś mi umknęło. Czy zauważyłeś jakąkolwiek charakterystykę wydajności między ręcznie walcowanymi zestawami parsera RD / lex a generatorami zasilanymi przez BNF (zakładam, że)?
Eli Frey