Jakie są główne zalety i wady analizy składniowej LL i LR?

Kiedy buduję parser na język programowania, co zarabiam, a co straciłem wybierając jeden lub drugi?

Przeciwstawię analizę składniową LL i LR szeregowi kryteriów:

Złożoność

LL wygrywa tutaj, ręce w dół. Możesz łatwo ręcznie napisać parser LL. W rzeczywistości jest to często wykonywane: kompilator Microsoft C # jest ręcznie napisanym parserem rekurencyjnego zapisu (źródło tutaj , poszukaj komentarza Patricka Kristiansena - post na blogu jest również bardzo interesujący).

Parsowanie LR używa raczej sprzecznej z intuicją metody parsowania tekstu. Działa, ale zajęło mi trochę czasu, aby owinąć głowę wokół tego, jak dokładnie działa. Dlatego ręczne napisanie takiego parsera jest trudne: mniej więcej zaimplementujesz generator parsera LR.

Ogólność

LR wygrywa tutaj: wszystkie języki LL są językami LR, ale jest więcej języków LR niż języków LL (język jest językiem LL, jeśli można go przeanalizować za pomocą analizatora składni LL, a językiem jest język LR, jeśli można go przeanalizować za pomocą parser LR).

LL ma sporo niedogodności, które będą Ci przeszkadzać przy wdrażaniu niemal dowolnego języka programowania. Zobacz tutaj na przegląd.

Istnieją jednoznaczne języki, które nie są językami LR, ale są one dość rzadkie. Prawie nigdy nie spotkasz takich języków. LALR ma jednak kilka problemów.

LALR to mniej więcej hack dla parserów LR, aby zmniejszyć tabele. Tabele dla analizatora składni LR mogą zwykle być ogromne. Parsery LALR rezygnują z możliwości analizowania wszystkich języków LR w zamian za mniejsze tabele. Większość parserów LR faktycznie używa LALR (choć nie potajemnie, zwykle można znaleźć dokładnie to, co implementuje).

LALR może narzekać na konflikty polegające na redukcji zmiany i redukcji. Jest to spowodowane włamaniem do tabeli: „składa” podobne wpisy razem, co działa, ponieważ większość wpisów jest pusta, ale gdy nie są puste, generuje konflikt. Tego rodzaju błędy nie są naturalne, trudne do zrozumienia, a poprawki są zwykle dość dziwne.

Błędy kompilatora i odzyskiwanie po błędzie

LL wygrywa tutaj. W analizie składni LL zwykle dość łatwo jest wyemitować przydatne błędy kompilatora, w szczególności w analizatorach napisanych ręcznie. Wiesz, czego oczekujesz, więc jeśli się nie pojawi, zwykle wiesz, co poszło nie tak i jaki byłby najbardziej rozsądny błąd.

Ponadto w parsowaniu LL odzyskiwanie po błędzie jest znacznie łatwiejsze. Jeśli dane wejściowe nie są poprawnie analizowane, możesz spróbować przeskoczyć nieco do przodu i dowiedzieć się, czy reszta danych wejściowych jest poprawnie analizowana. Jeśli na przykład niektóre instrukcje programowania są zniekształcone, możesz pominąć i przeanalizować następną instrukcję, aby złapać więcej niż jeden błąd.

Korzystanie z parsera LR jest o wiele trudniejsze. Możesz spróbować zwiększyć gramatykę, aby akceptowała ona błędne dane wejściowe i drukowała błędy w obszarach, w których coś poszło nie tak, ale zwykle jest to dość trudne. Szansa, że ​​skończysz z gramatyką inną niż LR (lub inną niż LALR), również rośnie.

Prędkość

Szybkość nie jest tak naprawdę problemem ze sposobem, w jaki analizujesz dane wejściowe (LL lub LR), ale raczej jakością wynikowego kodu i wykorzystaniem tabel (możesz używać tabel zarówno dla LL, jak i LR). LL i LR są zatem porównywalne pod tym względem.

Spinki do mankietów

Oto link do strony, która również kontrastuje LL i LR. Poszukaj sekcji u dołu.

Tutaj możesz znaleźć rozmowę dotyczącą różnic. Nie jest jednak złym pomysłem krytyczne spojrzenie na wyrażane tam opinie, toczy się tam święta wojna .

Aby uzyskać więcej informacji, tutaj i tutaj są dwa moje własne posty na temat parserów, chociaż nie dotyczą one wyłącznie kontrastu między LL i LR.