W ciągu ostatnich kilku dni przeprowadziłem wiele badań, aby lepiej zrozumieć, dlaczego istnieją te oddzielne technologie oraz jakie są ich mocne i słabe strony.
Niektóre z już istniejących odpowiedzi wskazywały na niektóre z ich różnic, ale nie dały pełnego obrazu i wydawały się być nieco opiniotwórcze, dlatego właśnie ta odpowiedź została napisana.
Ta ekspozycja jest długa, ale ważna. znoś mnie (lub jeśli jesteś niecierpliwy, przewiń do końca, aby zobaczyć schemat blokowy).
Aby zrozumieć różnice między kombinatorami parserów i generatorami parserów, najpierw trzeba zrozumieć różnicę między różnymi rodzajami parsowania, które istnieją.
Rozbiór gramatyczny zdania
Analiza składniowa jest procesem analizy ciągu symboli zgodnie z gramatyką formalną. (W Computing Science) parsowanie służy do umożliwienia komputerowi zrozumienia tekstu napisanego w języku, zwykle tworząc parsowanie, które reprezentuje tekst pisany, przechowując znaczenie różnych zapisanych części w każdym węźle drzewa. To drzewo analizy może być następnie wykorzystane do różnych celów, takich jak tłumaczenie go na inny język (używany w wielu kompilatorach), interpretacja instrukcji pisanych bezpośrednio w jakiś sposób (SQL, HTML), umożliwiając narzędziom takim jak Linters
wykonywanie pracy itp. Czasami parsowanie drzewa nie jest jawnegenerowane, ale działanie, które należy wykonać na każdym typie węzła w drzewie, jest wykonywane bezpośrednio. Zwiększa to wydajność, ale pod wodą nadal istnieje ukryte drzewo analizy.
Analiza składniowa jest problemem trudnym obliczeniowo. Przeprowadzono ponad pięćdziesiąt lat badań na ten temat, ale wciąż pozostaje wiele do nauczenia się.
Z grubsza mówiąc, istnieją cztery ogólne algorytmy pozwalające komputerowi analizować dane wejściowe:
- Parsowanie LL. (Bezkontekstowe, parsowanie od góry.)
- Analiza LR. (Bezkontekstowe, analizowanie oddolne).
- Przetwarzanie PEG + Packrat.
- Earley Parsing.
Zauważ, że te typy analizowania są bardzo ogólnymi, teoretycznymi opisami. Istnieje wiele sposobów implementacji każdego z tych algorytmów na fizycznych komputerach, z różnymi kompromisami.
LL i LR mogą patrzeć tylko na gramatykę bezkontekstową (tzn. Kontekst wokół pisanych tokenów nie jest ważny, aby zrozumieć, w jaki sposób są używane).
Przetwarzanie PEG / Packrat i parsowanie Earleya są używane znacznie rzadziej: parsowanie Earleya jest przyjemne, ponieważ może obsłużyć o wiele więcej gramatyk (w tym niekoniecznie bezkontekstowych), ale jest mniej wydajne (jak twierdzi smok książka (sekcja 4.1.1); Nie jestem pewien, czy te twierdzenia są nadal dokładne).
Gramatyka wyrażeń parsujących + parsowanie Packrat to metoda, która jest względnie wydajna i może obsługiwać więcej gramatyk niż LL i LR, ale ukrywa niejednoznaczności, o czym będzie mowa poniżej.
LL (pochodzenie od lewej do prawej, pochodzenie od lewej)
Jest to prawdopodobnie najbardziej naturalny sposób myślenia o analizie składni. Chodzi o to, aby spojrzeć na następny token w ciągu wejściowym, a następnie zdecydować, które z wielu możliwych wywołań rekurencyjnych należy podjąć w celu wygenerowania struktury drzewa.
To drzewo jest zbudowane „z góry na dół”, co oznacza, że zaczynamy od korzenia drzewa i podróżujemy według reguł gramatycznych w taki sam sposób, jak przechodzimy przez łańcuch wejściowy. Można to również postrzegać jako konstruowanie ekwiwalentu „postfiksowego” dla czytanego strumienia tokenu „infix”.
Parsery wykonujące parsowanie w stylu LL można napisać tak, aby wyglądały bardzo podobnie do oryginalnej gramatyki, która została określona. Ułatwia to ich zrozumienie, debugowanie i ulepszenie. Klasyczne kombinatory parsera to nic innego jak „klocki lego”, które można połączyć, aby zbudować parser w stylu LL.
LR (pochodzenie od lewej do prawej, skrajne prawo)
Analiza składni LR przebiega w drugą stronę, od dołu do góry: na każdym kroku górne elementy na stosie są porównywane z listą gramatyki, aby sprawdzić, czy można je zredukować
do gramatyki na wyższym poziomie. Jeśli nie, następny token ze strumienia wejściowego jest przesuwany i umieszczany na stosie.
Program jest poprawny, jeśli na końcu otrzymamy pojedynczy węzeł na stosie, który reprezentuje regułę początkową z naszej gramatyki.
Patrz przed siebie
W każdym z tych dwóch systemów czasami trzeba zajrzeć do większej liczby tokenów z danych wejściowych, zanim będzie można podjąć decyzję o wyborze. To jest (0), (1), (k)lub (*)-syntax widać po nazwach tych dwóch ogólnych algorytmów, takich jak LR(1) czy LL(k). kzwykle oznacza „tyle, ile potrzebuje twoja gramatyka”, podczas gdy *zwykle oznacza „ten parser wykonuje backtracking”, który jest mocniejszy / łatwiejszy do wdrożenia, ale ma znacznie większe wykorzystanie pamięci i czasu niż parser, który może po prostu analizować liniowo.
Zauważ, że parsery w stylu LR mają już wiele znaczników na stosie, kiedy mogą zdecydować się „patrzeć w przyszłość”, więc mają już więcej informacji do wysłania. Oznacza to, że często potrzebują mniej „wyprzedzającego” niż parser w stylu LL dla tej samej gramatyki.
LL vs. LR: Niejednoznaczność
Czytając dwa powyższe opisy, można się zastanawiać, dlaczego parsowanie w stylu LR istnieje, ponieważ parsowanie w stylu LL wydaje się o wiele bardziej naturalne.
Jednak podczas analizowania w stylu LL występuje problem: Left Recursion .
Pisanie gramatyki takiej jak:
expr ::= expr '+' expr | term
term ::= integer | float
Ale parser w stylu LL utknie w nieskończonej pętli rekurencyjnej podczas analizowania tej gramatyki: Podczas wypróbowania najbardziej lewej możliwości exprreguły, ponownie powtarza się do tej reguły bez zużywania jakichkolwiek danych wejściowych.
Istnieją sposoby rozwiązania tego problemu. Najprościej jest przepisać swoją gramatykę, aby taka rekurencja nie miała miejsca:
expr ::= term expr_rest
expr_rest ::= '+' expr | ϵ
term ::= integer | float
(Tutaj ϵ oznacza „pusty ciąg”)
Ta gramatyka jest teraz rekurencyjna. Pamiętaj, że od razu jest o wiele trudniej czytać.
W praktyce lewostronna rekurencja może się zdarzyć pośrednio z wieloma innymi krokami pośrednimi. To sprawia, że trudno jest uważać. Ale próba rozwiązania tego problemu utrudnia czytanie gramatyki.
Zgodnie z sekcją 2.5 Dragon Book:
Wygląda na to, że mamy konflikt: z jednej strony potrzebujemy gramatyki ułatwiającej tłumaczenie, z drugiej strony potrzebujemy znacznie innej gramatyki, która ułatwia analizowanie. Rozwiązaniem jest rozpoczęcie od gramatyki w celu łatwego tłumaczenia i staranne przekształcenie jej w celu ułatwienia analizy. Eliminując lewą rekurencję, możemy uzyskać gramatykę odpowiednią do użycia w translatorze predykcyjnym z opadaniem rekurencyjnym.
Parsery w stylu LR nie mają problemu z tą lewą rekurencją, ponieważ budują drzewo od podstaw.
Jednak mentalne tłumaczenie gramatyki takiej jak wyżej na parser w stylu LR (często implementowany jako automat skończony )
jest bardzo trudne (i podatne na błędy), ponieważ często istnieją setki lub tysiące stanów + przejścia stanowe do rozważenia. Dlatego parsery w stylu LR są zwykle generowane przez generator parserów, który jest również znany jako „kompilator kompilatora”.
Jak rozwiązać niejasności
Widzieliśmy dwie metody rozwiązania dwuznaczności rekurencji po lewej powyżej: 1) przepisz składnię 2) użyj parsera LR.
Ale są też inne rodzaje niejednoznaczności, które trudniej rozwiązać: Co zrobić, jeśli dwie różne zasady obowiązują w tym samym czasie?
Niektóre typowe przykłady to:
Parsery w stylu LL i LR mają z nimi problemy. Problemy z analizowaniem wyrażeń arytmetycznych można rozwiązać, wprowadzając pierwszeństwo operatora. W podobny sposób można rozwiązać inne problemy, takie jak Dangling Else, wybierając jedno zachowanie pierwszeństwa i pozostając przy nim. (Na przykład w C / C ++, wiszące inne zawsze należy do najbliższego „if”).
Innym „rozwiązaniem” tego problemu jest użycie gramatyki wyrażeń parsera (PEG): Jest to podobne do gramatyki BNF stosowanej powyżej, ale w przypadku niejasności zawsze „wybierz pierwszą”. Oczywiście tak naprawdę nie „rozwiązuje” problemu, ale raczej ukrywa, że w rzeczywistości istnieje dwuznaczność: użytkownicy końcowi mogą nie wiedzieć, jakiego wyboru dokonuje parser, co może prowadzić do nieoczekiwanych rezultatów.
Więcej informacji, które są o wiele bardziej dogłębne niż ten post, w tym dlaczego ogólnie nie jest możliwe, aby dowiedzieć się, czy twoja gramatyka nie ma żadnych dwuznaczności, a konsekwencją tego jest wspaniały artykuł na blogu LL i LR w kontekście: Dlaczego parsowanie narzędzia są twarde . Mogę gorąco polecić; bardzo mi pomogło zrozumieć wszystkie rzeczy, o których teraz mówię.
50 lat badań
Ale życie toczy się dalej. Okazało się, że „normalne” parsery w stylu LR zaimplementowane jako automaty stanów skończonych często wymagały tysięcy stanów + przejść, co stanowiło problem w rozmiarze programu. Tak więc napisano warianty, takie jak Simple LR (SLR) i LALR (Look-ahead LR), które łączą inne techniki zmniejszania automatu, zmniejszając powierzchnię dyskową i pamięć programów parsera.
Innym sposobem rozwiązania wymienionych powyżej dwuznaczności jest zastosowanie technik ogólnych , w których w przypadku niejasności obie możliwości są zachowywane i analizowane: albo jedno z nich może nie przeanalizować w dół linii (w takim przypadku drugą możliwością jest „poprawne”), a także zwracanie obu (i w ten sposób pokazanie, że istnieje dwuznaczność) w przypadku, gdy oba są poprawne.
Co ciekawe, po opisaniu algorytmu Uogólnionego LR okazało się, że można zastosować podobne podejście do implementacji parserów Uogólnionego LL , który jest podobnie szybki (złożoność czasowa O $ (n ^ 3) $ dla niejednoznacznych gramatyk, $ O (n) $ za całkowicie jednoznaczne gramatyki, aczkolwiek z większą księgowością niż prosty parser LR, co oznacza wyższy stały współczynnik), ale znowu pozwala na zapisanie parsera w stylu rekurencyjnego opadania (z góry na dół), który jest o wiele bardziej naturalny pisać i debugować.
Kombinatory parserów, generatory parserów
Tak więc dzięki tej długiej prezentacji dochodzimy do sedna pytania:
Jaka jest różnica między kombinatorami parserów i generatorami parserów i kiedy należy używać jednego z nich?
Są to naprawdę różne rodzaje zwierząt:
Kombinatory parserów zostały stworzone, ponieważ ludzie pisali odgórne parsery i zdali sobie sprawę, że wiele z nich ma wiele wspólnego .
Generatory parserów zostały utworzone, ponieważ ludzie chcieli budować parsery, które nie miały problemów, jakie miały parsery w stylu LL (tj. Parsery w stylu LR), co okazało się bardzo trudne ręcznie. Do typowych należą Yacc / Bison, które implementują (LA) LR).
Co ciekawe, w dzisiejszych czasach krajobraz jest nieco zamulony:
Możliwe jest napisanie Kombinatorów parserów, które działają z algorytmem GLL , rozwiązując problemy niejednoznaczności, jakie miały klasyczne parsery w stylu LL, a jednocześnie były tak samo czytelne / zrozumiałe, jak wszystkie rodzaje parsowania z góry na dół.
Generatory parserów można również napisać dla parserów w stylu LL. ANTLR robi dokładnie to i wykorzystuje inne heurystyki (Adaptive LL (*)), aby rozwiązać dwuznaczności, jakie miały klasyczne parsery w stylu LL.
Ogólnie rzecz biorąc, utworzenie generatora analizatora składni LR i debugowanie danych wyjściowych generatora analizatora składni w stylu (LA) LR działającego na gramatyce jest trudne, z powodu przetłumaczenia oryginalnej gramatyki na formę LR „od wewnątrz”. Z drugiej strony, narzędzia, takie jak Yacc / Bison mieli wieloletnie optymalizacji, a widziałem wiele stosowania w środowisku naturalnym, co oznacza, że wiele osób teraz uważać ją za tym , aby zrobić parsowanie i są sceptyczni wobec nowych podejść.
Który powinieneś użyć, zależy od tego, jak twarda jest twoja gramatyka i jak szybko musi być analizator składni. W zależności od gramatyki, jedna z tych technik (/ implementacje różnych technik) może być szybsza, mieć mniejszą pamięć, mieć mniejszą pamięć dyskową lub być bardziej rozszerzalna lub łatwiejsza do debugowania niż inne. Twój przebieg może się różnić .
Uwaga dodatkowa: na temat analizy leksykalnej.
Analiza leksykalna może być stosowana zarówno w kombinatorach parseratorów, jak i generatorach parserów. Chodzi o to, aby mieć „głupi” parser, który jest bardzo łatwy do wdrożenia (a zatem szybki), który wykonuje pierwszy przebieg kodu źródłowego, usuwając na przykład powtarzające się białe spacje, komentarze itp. I ewentualnie „tokenizując” w bardzo z grubsza sposób różne elementy, które składają się na Twój język.
Główną zaletą jest to, że ten pierwszy krok sprawia, że prawdziwy parser jest znacznie prostszy (a przez to być może szybszy). Główną wadą jest to, że masz oddzielny krok tłumaczenia, a np. Zgłaszanie błędów z numerami wierszy i kolumn staje się trudniejsze z powodu usunięcia białych znaków.
Lexer na końcu jest „tylko” innym parserem i może być zaimplementowany przy użyciu dowolnej z powyższych technik. Ze względu na swoją prostotę często stosuje się inne techniki niż dla głównego parsera, a na przykład istnieją dodatkowe „generatory leksykalne”.
Tl; Dr:
Oto schemat blokowy, który ma zastosowanie w większości przypadków:
javac, Scala). Daje to największą kontrolę nad wewnętrznym stanem parsera, co pomaga w generowaniu dobrych komunikatów o błędach (które w ostatnich latach…