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

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?

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.

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.

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.

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.

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.