Jaki jest najpotężniejszy parser?

28

Jako poboczny projekt piszę język przy użyciu Pythona. Zacząłem od użycia klonu Flex / Bison o nazwie Ply, ale zbliżam się do krawędzi tego, co mogę wyrazić za pomocą tego stylu gramatyki, i nie jestem zainteresowany zhakowaniem mojego języka z powodu niedopasowania impedancji z narzędzie. Dlatego nie jestem przeciwny pisaniu własnych.

Jaki jest zatem najsilniejszy typ parsera? Mile widziane cytaty do artykułów (a także więcej artykułów wprowadzających).

(Wiem, że „potężny” nie jest precyzyjnie zdefiniowany, ale bądźmy z nim trochę luźni i zobaczmy, gdzie idą odpowiedzi)

Paul Biggar
źródło
1
Downvoted: nie poziom badań.
Warren Schudy,
3
@Warren: Sprawdziłem FAQ przed zapytaniem - to nie wydaje się być wymogiem.
Paul Biggar
1
istnieją dwa najczęściej zadawane pytania, jeden dla strony ogólnej i jeden dla CStheory. CStheory wskazuje, że pytania, na które można odpowiedzieć, np. Czytając Wikipedię, są nie na temat; patrz „Jakie pytania są zbyt podstawowe?” w meta.cstheory.stackexchange.com/questions/225/… .
Warren Schudy,
1
@Warren: Przeczytałem najczęściej zadawane pytania. Czytałem wikipedię, ale czułem, że to wymaga rzeczywistego wglądu.
Paul Biggar
1
Masz na myśli parsery produkcyjne czy teoretyczne, tj. Takie, które obejmują typy gramatyczne inne niż CFG?
Raphael

Odpowiedzi:

33

Gramatyka jest zwykle definiowana jako gramatyka bezkontekstowa - dokładna definicja jest podana na stronie Wikipedii, ale działa tak samo jak w PLY, która jest oparta na Bison , która z kolei oparta jest na yacc .

Mówi się tutaj, że PLY używa parsera LALR . Jest to zasadniczo parser LR, w którym tabele odnośników są skondensowane, prawdopodobnie wprowadzając konflikty parsowania, zmniejszając część ekspresji gramatyki LR (tj. Gramatykę bez kontekstu, którą parser LR może analizować). Jeśli chcesz dowiedzieć się o ograniczeniach tego konkretnego oddziału parserami i tych z innych analizatorów, przegląd wszystkich rodzajów technik dekodowaniu (LL, LR i inne) jest podana tutaj .

Aby odpowiedzieć na twoje pytanie: istnieją algorytmy analizujące, które potrafią parsować dowolny język bezkontekstowy, nawet jeśli język jest dwuznaczny (tzn. Istnieje więcej niż jeden sposób interpretacji danych wejściowych):

O(n3|G|)n|G|

O(n3)O(n2)

Tutaj znajdziesz artykuł omawiający praktyczną implementację (adaptację) algorytmu Earley. Wnioskują: „Biorąc pod uwagę ogólną analizę składni Earleya w porównaniu z analizą LALR (1) ((która jest mniej więcej tym, co robi PLY)) i biorąc pod uwagę, że nawet najgorszy czas PEP ((implementacja algorytmu Earleya)) nie byłby zauważalny przez użytkownik, jest to doskonały wynik ”.

Ostatni typ parsera to parser GLR . Jest to uogólniona wersja parsowania LR, zdolna do parsowania dowolnego języka bezkontekstowego.

Dojrzała implementacja GLR to ASF + SDF . Bison może również generować parser GLR, choć jego implementacje nieco różnią się od „standardowego” algorytmu GLR. Elkhound algorytmu jest algorytm hybrydowy GLR / LALR. Wykorzystuje LALR, gdy jest to możliwe, i GLR, gdy jest to potrzebne, aby być zarówno szybki, jak i zdolny do parsowania dowolnej gramatyki.

Poza gramatykami bezkontekstowymi istnieją gramatyki kontekstowe , ale ogólnie są one trudne do przeanalizowania i nie dodają zbyt dużej ekspresji: możesz z nimi zrobić więcej, ale w większości aplikacji dodatkowe zastosowania nie są istotne, chyba że analizujesz język naturalny.

Ostatnim krokiem są nieograniczone gramatyki . W tym momencie gramatyka jest kompletna dla Turinga, więc nie ma żadnych ograniczeń co do tego, ile czasu zajmie parsowanie określonego języka, co jest niepożądane w przypadku większości aplikacji przetwarzających. Dodatkowa moc prawie nigdy nie jest potrzebna. Jeśli chcesz wykorzystać całą tę moc, dostępna jest maszyna językowa .

Wreszcie, implementacja własnego parsera-generatora nie jest trywialną sprawą, w szczególności aby była szybka. Właśnie osobiście skończyłem tworzenie własnej wersji flexa (generatora leksykonu) i chociaż wydawało się to ćwiczeniem w stosunkowo prostych problemach algorytmicznych, dostanie się do porządku stało się dość skomplikowane, szczególnie gdy próbowałem obsługiwać Unicode. Zastanów się nad użyciem już istniejącej implementacji zamiast pisania własnej.

Alex ten Brink
źródło
1
Doskonała odpowiedź !! Wszelkie przemyślenia na temat dopasowania PEG?
Paul Biggar
2
PEG są „inne” niż CFG: istnieją CFG, które nie są PEG i odwrotnie. Nawiązuję tu do: stackoverflow.com/questions/1857022/... .
Alex ten Brink
Może to również być interesujące: blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars .
Alex ten Brink
1
W rzeczywistości większość popularnych generatorów parserów (yacc, Antlr, bizon) zezwala na koncepcje inne niż CF według predykatów lub dowolnego kodu sprawdzającego, czy można zastosować jedną regułę. decydowanie o pierwszeństwie. Można to wykorzystać do implementacji semantyki statycznej głównie dlatego, że podstawowa składnia pozostaje w zasadzie wolna od kontekstu.
Raphael
1
Języki rekurencyjne są dokładnie tymi, które można rozstrzygać, zawsze zatrzymując maszyny Turinga. Dlatego każdy język kontekstowy jest również rekurencyjny, ale ponieważ języki kontekstowe są rozstrzygalne w czasie wykładniczym, istnieją języki rekurencyjne, które nie są wrażliwe na kontekst. Nieograniczone gramatyki są jeszcze potężniejsze: problem zatrzymania można opisać gramatyką nieograniczoną, ale nie jest to język rekurencyjny.
Alex ten Brink
15

Artykuł na tegorocznym ICFP 2010, Total Parser Combinators , opisuje możliwą do zakończenia bibliotekę kombinatora parserów, a także stwierdza, że ​​w tej bibliotece „kombinatory parsera są tak wyraziste, jak to możliwe”, biorąc pod uwagę, że parser gwarantuje zakończenie. Niestety nie pamiętam wyjaśnień autora dotyczących tego, co oznacza „tak wyrazisty, jak to możliwe”, ale z pewnością wydaje się mieć znaczenie dla twojego pytania dotyczącego „władzy”.

Rob Simmons
źródło
1
Mam samochód, który nie zanieczyszcza, w rzeczywistości też się nie porusza ... Pytanie brzmi: jaki język jest analizowany przez tę bibliotekę? Oczywiście nie oznacza to, że ta praca nie jest interesująca.
babou
2

Jeśli chcesz wyjść poza gramatyki bezkontekstowe do analizowania języków programowania, ale nadal analizujesz w czasie wielomianowym, możesz skorzystać z parsowania gramatyki wyrażeń lub gramatyki logicznej - te ostatnie są również dostępne w wersjach LL i LR (patrz tutaj ). W formalnej teorii języków badane są także potężne, ale rozpoznawalne w czasie linearne języki Church-Rosser , ale nie znam żadnych zaimplementowanych dla nich generatorów parserów.

W przetwarzaniu języka naturalnego smaki są różne, na przykład radzenie sobie z dwuznacznością (także: naturalna dwuznaczność), a swobodny porządek słów odgrywa bardzo ważną rolę. W tym przypadku słowa kluczowe w nieznacznym stopniu kontekstowe języki i ponowne uruchomienie automatów mogą pomóc w rozpoczęciu czytania.

Hermann Gruber
źródło
1
Biorąc pod uwagę sposób, w jaki pytanie zostało zadane, oraz zarzut, że CF jest zbyt ograniczający, twoja odpowiedź jest zdecydowanie najlepsza. Tak to idzie ...
babou
0

Narzędzia generatora parsera:

ANTLR jest bardzo dobry. Możesz też zajrzeć na JavaCC


źródło
Nie jestem informatykiem (pomimo tego, co mówi mój stopień naukowy;), więc moje słowa mogą tutaj lekko ważyć. Zgadzam się z Sazzadem - ANTLR to bardzo potężne narzędzie. Jest bardzo kompletny i jeszcze nie znalazłem żadnych problemów z generatorem analizatora składni (LL (k), jeśli dobrze pamiętam). Z drugiej strony muszę jeszcze wdrożyć kompilator dla nieco złożonej gramatyki ...
Jörgen Sigvardsson
5
Myślę, że nie rozumiesz sedna pytania i być może całej witryny. Chodzi o teorię analizy, a nie implementacje i narzędzia.
Paul Biggar,