Różnica między parserem LL i rekurencyjnym zejściem?

Question

Ostatnio próbowałem nauczyć się, jak działają parsery (dla języków/gramatyk bezkontekstowych), a większość z nich wydaje się mieć sens, z wyjątkiem jednej rzeczy. Zwracam szczególną uwagę na gramatykę LL (k), dla której dwoma głównymi algorytmami wydają się być LL parser (przy użyciu tabeli stosu/parsowania) i Recursive Descent parser (po prostu przy użyciu rekursji).

O ile widzę, algorytm rekursywnego zjazdu działa na wszystkie gramatyki LL (k) i prawdopodobnie więcej, podczas gdy parser LL działa na wszystkich gramatykach LL (k). Parser rekurencyjny jest oczywiście znacznie prostszy niż parser LL do implementacji, jednak (podobnie jak LL jest prostszy niż LR).

Moje pytanie brzmi: jakie są zalety/problemy, które mogą napotkać przy korzystaniu z któregoś z algorytmów? Dlaczego można wybrać LL na rekursywne zejście, biorąc pod uwagę, że działa on na tym samym zestawie gramatyk i jest trudniejszy w implementacji?

Answer 1

LL jest zwykle bardziej wydajną techniką analizy niż rekursywne zejście. W rzeczywistości, naiwny parser rekursywno-zejścia będzie w rzeczywistości najgorszym przypadkiem O (k^n) (gdzie n jest wielkością wejściową). Niektóre techniki, takie jak zapamiętywanie (które daje parser Packrat) mogą to poprawić, a także rozszerzyć klasę gramatyk akceptowaną przez analizator składni, ale zawsze istnieje kompromis dotyczący przestrzeni. Parserzy LL są (według mojej wiedzy) zawsze liniowy.

Z drugiej strony, masz intuicję, że parsery rekursywno-opadowe mogą obsłużyć większą klasę gramatyk niż LL. Zejście rekursywne może obsłużyć dowolną gramatykę, która jest LL (*) (to znaczy nieograniczona wcześniejsza), a także mały zestaw niejednoznacznych gramatyk. Dzieje się tak dlatego, że rekurencyjne pochodzenie jest właściwie bezpośrednio zakodowaną implementacją PEG lub Parser Expression Grammar(s). W szczególności operator rozdzielający (a | b) nie jest przemienny, co oznacza, że ​​a | b nie jest równy b | a. Parser rekursywno-spadkowy spróbuje każdej alternatywy w kolejności. Więc jeśli a dopasuje dane wejściowe, to odniesie sukces, nawet jeśli bbędzie miał wartość dopasowaną do wejścia. Pozwala to na rozwiązywanie klasycznych "długodystansowych" niejednoznaczności, takich jak zwisający problem else po prostu przez prawidłowe uporządkowanie disjunctions.

Z tym wszystkim, jest możliwe do realizacji parser LL (k) przy użyciu rekursywnego pochodzenia, tak aby działał w czasie liniowym. Odbywa się to przez zasadniczo ustawiając predykcyjne zestawy, tak aby każda procedura parse określiła odpowiednią produkcję dla danego wejścia w stałym czasie. Niestety, taka technika eliminuje obsługę całej klasy gramatyk. Po przejściu do analizy predykcyjnej problemy takie jak zwisanie else nie są już rozwiązywane z taką łatwością.

Jeśli chodzi o powód, dla którego LL zostałby wybrany jako rekurencyjny, to jest to głównie kwestia wydajności i łatwości konserwacji. Parsery rekurencyjno-descentowe są znacznie łatwiejsze w implementacji, ale zazwyczaj są trudniejsze do utrzymania, ponieważ gramatyka, którą reprezentują, nie istnieje w żadnej deklaratywnej formie. Większość nietrywialnych przypadków użycia parsera wykorzystuje generator parsera, taki jak ANTLR lub Bison. Przy takich narzędziach nie ma znaczenia, czy algorytm jest zakodowany bezpośrednio przez rekursywne pochodzenie, czy sterowany tabelą LL (k).

W interesie warto również zajrzeć do recursive-ascent, który jest algorytmem parsowania zakodowanym bezpośrednio po modulacji rekurencyjnego pochodzenia, ale zdolnym do obsługi dowolnej gramatyki LALR. Chciałbym również zagłębić się w parser combinators, które są funkcjonalnym sposobem komponowania parserów recursive-descent razem.