Kiedy stosować kombinator parserów? Kiedy używać generatora parsera?

Niedawno zanurzyłem się w świat parserów, chcąc stworzyć własny język programowania.

Odkryłem jednak, że istnieją dwa nieco odmienne podejścia do pisania parserów: Parser Generators i Parser Combinators.

Co ciekawe, nie udało mi się znaleźć żadnego zasobu, który wyjaśniłby, w jakich przypadkach które podejście jest lepsze; Przeciwnie, wiele zasobów (i osób) zapytaliśmy o przedmiot nie wiedział o drugim podejściu, tylko wyjaśniając swoje podejście jak w podejściu i nie wspomnieć o drugiej w ogóle:

• Słynna książka smok idzie do Lexing / skanowania i wspomina (F) lex, ale nie wspomina w ogóle parser kombinatorów.
• Wzorce implementacji języka w dużej mierze zależą od generatora analizatora parserów ANTLR wbudowanego w Javę i w ogóle nie wspominają o kombinatorach parserów.
• Wprowadzenie do samouczka Parsec na temat Parsec, który jest kombinatorem parserów w Haskell, w ogóle nie wspomina o generatorach parserów.
• Boost :: spirit , najbardziej znany C ++ Parser Combinator, w ogóle nie wspomina o generatorach parserów.
• Świetny objaśniający wpis na blogu, który mógłbyś wymyślić kombinatory parserów, w ogóle nie wspomina o generatorach parserów.

Prosty przegląd:

Generator analizatora składni

Generator parsera pobiera plik zapisany w DSL, który jest dialektem formy Extended Backus-Naur , i przekształca go w kod źródłowy, który może (po skompilowaniu) stać się parserem dla języka wejściowego opisanego w tej DSL.

Oznacza to, że proces kompilacji odbywa się w dwóch osobnych krokach. Co ciekawe, same generatory parsera są również kompilatorami (a wiele z nich jest rzeczywiście hostami własnymi ).

Kombinator parserów

Kombinator parserów opisuje proste funkcje zwane parserami, które wszystkie przyjmują dane wejściowe jako parametr i próbują wyłapać pierwsze znaki z tych danych wejściowych, jeśli się zgadzają. Zwracają krotkę (result, rest_of_input), gdzie resultmoże być pusta (np. nilLub Nothing), jeśli analizator składni nie był w stanie przeanalizować niczego z tego wejścia. Przykładem może być digitparser. Inne parsery mogą oczywiście traktować parsery jako pierwsze argumenty (ostatni argument nadal pozostaje łańcuchem wejściowym), aby je połączyć : np. many1Próbuje dopasować inny parser tyle razy, ile to możliwe (ale przynajmniej raz, albo sam się nie powiedzie).

Teraz możesz oczywiście łączyć (komponować) digiti many1, aby utworzyć nowy parser, powiedzmy integer.

choiceMożna również napisać parser wyższego poziomu, który pobiera listę parserów, wypróbowując kolejno każdy z nich.

W ten sposób można budować bardzo złożone leksery / parsery. W językach obsługujących przeciążanie operatorów wygląda to również bardzo podobnie do EBNF, nawet jeśli jest ono napisane bezpośrednio w języku docelowym (i można korzystać ze wszystkich funkcji pożądanego języka docelowego).

Proste różnice

Język:

• Generatory analizatorów składni są zapisywane w kombinacji DSL z EBNF i kodem, do którego instrukcje te powinny generować, gdy są zgodne.
• Kombinatory parsera są pisane bezpośrednio w języku docelowym.

Lexing / parsowanie:

• Generatory parsera mają bardzo wyraźną różnicę między „leksemem” (który dzieli ciąg na tokeny, które mogą być oznaczone, aby pokazać, z jaką wartością mamy do czynienia) a „parserem” (który pobiera listę wyjściową tokenów z leksyka i próbuje je połączyć, tworząc abstrakcyjne drzewo składniowe).
• Kombinatory parsera nie mają / nie potrzebują tego rozróżnienia; zwykle proste parsery wykonują pracę „leksera”, a bardziej szczegółowe parsery nazywają je prostszymi, aby zdecydować, który rodzaj węzła AST należy utworzyć.

Pytanie

Jednak nawet biorąc pod uwagę te różnice (a ta lista różnic jest prawdopodobnie daleka od ukończenia!), Nie mogę dokonać świadomego wyboru, kiedy użyć której z nich. Nie rozumiem, jakie są konsekwencje / konsekwencje tych różnic.

Jakie właściwości problemu wskazują, że lepiej byłoby rozwiązać problem za pomocą generatora analizatora składni? Jakie właściwości problemu wskazują, że lepiej byłoby rozwiązać problem za pomocą i Parsera Kombinatora?

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:

• wyrażenia arytmetyczne.
• zwisające inne

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:

W przypadku danych wejściowych, które z pewnością są wolne od błędów składniowych lub gdy ogólne poprawność / poprawność poprawności składniowej jest w porządku, kombinatory parsera są znacznie prostsze w obsłudze, szczególnie w funkcjonalnych językach programowania. Są to sytuacje takie jak programowanie łamigłówek, czytanie plików danych itp.

Funkcja, która sprawia, że ​​chcesz dodać złożoność generatorów analizatora składni, to komunikaty o błędach. Chcesz komunikatów o błędach, które kierują użytkownika do wiersza i kolumny, i mam nadzieję, że są zrozumiałe dla człowieka. Aby to zrobić poprawnie, potrzeba dużo kodu, a lepsze generatory parsera, takie jak antlr, mogą ci w tym pomóc.

Jednak automatyczne generowanie może tylko do tej pory dotrzeć, a większość komercyjnych i długowiecznych kompilatorów open source kończy ręcznie pisać swoje parsery. Zakładam, że gdybyś czuł się komfortowo, nie zadałbyś tego pytania, więc zaleciłbym skorzystanie z generatora parsera.

Sam Harwell, jeden z opiekunów generatora analizatora parserów ANTLR, napisał niedawno :

Odkryłem, że [kombinatory] nie spełniają moich potrzeb:

1. ANTLR zapewnia mi narzędzia do zarządzania takimi niejednoznacznościami. Podczas programowania istnieją narzędzia, które mogą pokazać mi niejednoznaczne wyniki analizy, dzięki czemu mogę wyeliminować te niejednoznaczności w gramatyce. W czasie wykonywania mogę wykorzystać niejednoznaczność wynikającą z niepełnego wprowadzania danych do IDE, aby uzyskać dokładniejsze wyniki w funkcjach takich jak uzupełnianie kodu.
2. W praktyce odkryłem, że kombinatory parsera nie były odpowiednie do osiągnięcia moich celów wydajnościowych. Część tego sięga wstecz
3. Gdy wyniki analizy są używane do takich funkcji, jak tworzenie konspektu, uzupełnianie kodu i inteligentne wcięcia, subtelne zmiany w gramatyce mają wpływ na dokładność tych wyników. ANTLR zapewnia narzędzia, które mogą przekształcić te niedopasowania w błędy kompilacji, nawet w przypadkach, w których typy byłyby kompilowane. Mogę z ufnością prototypować nową funkcję językową, która wpływa na gramatykę, wiedząc, że cały dodatkowy kod tworzący IDE zapewni pełne doświadczenie dla nowej funkcji od samego początku. Moje rozwidlenie ANTLR 4 (na którym opiera się cel C #) jest jedynym znanym mi narzędziem, które nawet próbuje zapewnić tę funkcję.

Zasadniczo kombinatory parsera są fajną zabawką, ale po prostu nie są przeznaczone do poważnej pracy.

Jak wspomina Karl, generatory parsera mają zwykle lepsze raportowanie błędów. Dodatkowo:

• wydają się być szybsze, ponieważ generowany kod może specjalizować się w składni i generować tabele skoków dla lookahead.
• mają lepsze oprzyrządowanie, identyfikują niejednoznaczną składnię, usuwają lewą rekurencję, wypełniają gałęzie błędów itp.
• mają tendencję do lepszego radzenia sobie z definicjami rekurencyjnymi.
• wydają się być bardziej wytrzymałe, ponieważ generatory pracują dłużej i wykonują więcej płyty kotłowej dla Ciebie, zmniejszając ryzyko zepsucia go.

Z drugiej strony, kombinatory mają swoje zalety:

• są w kodzie, więc jeśli twoja składnia zmienia się w czasie wykonywania, możesz łatwiej mutować rzeczy.
• są one zwykle łatwiejsze do połączenia i faktycznie zużywają (wydajność generatorów parsera jest zazwyczaj bardzo ogólna i niewygodna w użyciu).
• są w kodzie, więc debugowanie jest łatwiejsze, gdy gramatyka nie spełnia oczekiwań.
• mają tendencję do płytszej krzywej uczenia się, ponieważ działają jak każdy inny kod. Generatory parsera mają własne dziwactwa, aby nauczyć się, jak działać.