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?
parsing
lexer
parser-combinator
Eli Frey
źródło
źródło
Odpowiedzi:
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
if
wyglą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.
źródło
if = string "if" >> expr >> string "then" >> expr >> string "else" >> expr
.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.
źródło
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ż
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.
źródło
\alpha'_1 (K_0, \vec{T})
, gdzie \ alpha'_1, K_0 i \ vec {T} są identyfikatorami.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.
źródło
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.
źródło