Jaki jest najpotężniejszy parser?

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)

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(n^3 |G|)$$n$$|G|$

$O(n^3)$$O(n^2)$

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.

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”.

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.

Narzędzia generatora parsera:

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