Jaka jest różnica między parserami LR, SLR i LALR?

Parsery LALR łączą podobne stany w gramatyce LR, aby stworzyć tabele Stanów parserów, które są dokładnie tego samego rozmiaru, co równoważne gramatyki SLR, które są zwykle o rząd wielkości mniejsze niż czyste tabele parsowania LR. Jednak dla gramatyk LR, które są zbyt złożone, aby mogły być LALR, te połączone stany powodują konflikty parserów lub wytwarzają parser, który nie w pełni rozpoznaje oryginalną gramatykę LR.

BTW, wspominam o tym kilka rzeczy w mojej tabeli parsowania MLR (k) algorytm TUTAJ .

Dodatek

Krótka odpowiedź jest taka, że tabele parsowania LALR są mniejsze, ale Maszyny parsera są takie same. Dana gramatyka LALR wytworzy znacznie większe tabele parsowania, jeśli wszystkie stany LR są generowane, z dużą ilością zbędnych (prawie identycznych) Stanów.

Tabele LALR są mniejsze, ponieważ podobne (nadmiarowe) Stany są scalane razem, skutecznie wyrzucając informacje kontekstowe / wyglądające, które kodują oddzielne Stany. Zaletą jest to, że otrzymujesz znacznie mniejsze tabele parsowania dla tej samej gramatyki.

Wadą jest to, że nie wszystkie gramatyki LR mogą być kodowane jako tabele LALR, ponieważ bardziej złożone gramatyki mają bardziej skomplikowane spojrzenia, co skutkuje dwoma lub więcej Stanami zamiast jednego połączonego stanu.

Główną różnicą jest to, że algorytm do tworzenia tabel LR przenosi więcej informacji między przejściami ze stanu do stanu, podczas gdy algorytm LALR nie. Więc algorytm LALR nie może powiedz, czy dany scalony stan powinien być rzeczywiście pozostawiony jako dwa lub więcej oddzielnych Stanów.

Yet another answer (YAA).

Algorytmy parsowania dla SLR( 1), LALR(1) i LR(1) są identyczne, jak powiedział Ira Baxter,
jednak tabele parserów mogą być różne ze względu na algorytm generowania parserów.

Generator parserów SLR tworzy maszynę stanową LR (0) i oblicza look-aheads z gramatyki (FIRST I FOLLOW). Jest to podejście uproszczone i może zgłaszać konflikty, które tak naprawdę nie istnieją w maszynie stanu LR (0).

An LALR generator parserów tworzy maszynę stanową LR (0) i oblicza look-aheads z maszyny stanowej LR(0) (poprzez przejścia końcowe). Jest to poprawne podejście, ale czasami zgłasza konflikty, które nie istniałyby w maszynie stanowej LR(1).

Kanoniczny generator parserów LR oblicza maszynę stanową LR(1) I look-aheads są już częścią maszyny stanowej LR(1). Te tabele parserów mogą być bardzo duże.

Minimalny generator parsera LR oblicza stan LR(1) maszyna, ale łączy zgodne Stany podczas procesu, a następnie oblicza look-aheads z minimalnej maszyny stanu LR (1). Tabele parserów są tej samej wielkości lub nieco większe niż tabele parserów LALR, co daje najlepsze rozwiązanie.

LRSTAR 9.1 może generować Minimalne parsery LR (1) i LR (*) w C++. Zobacz też ten diagram co pokazuje różnicę między parserami LR.

[Full disclosure: LRSTAR is my product]

Przypuśćmy, że parser bez lookahead chętnie parsuje ciągi dla Twojej gramatyki.

Na podanym przykładzie pojawia się ciąg dc, co robi? Czy redukuje to do S, ponieważ {[0] } jest poprawnym ciągiem wytworzonym przez tę gramatykę? A może próbowaliśmy przeanalizować bdc, ponieważ nawet to jest akceptowalny ciąg znaków?

Jako ludzie wiemy, że odpowiedź jest prosta, po prostu musimy pamiętać, czy właśnie parsowaliśmy b czy nie. Ale komputery są głupie :)

Ponieważ parser SLR(1) miał dodatkową moc nad LR (0) do wykonania lookahead, wiemy, że żadna ilość lookahead nie może nam powiedzieć, co mamy zrobić w tym przypadku; zamiast tego musimy spojrzeć wstecz w naszą przeszłość. W ten sposób na ratunek przychodzi kanoniczny parser LR. Pamięta kontekst z przeszłości.

Sposób, w jaki zapamiętuje ten kontekst, polega na tym, że dyscyplinuje się, że kiedykolwiek spotka b, zacznie kroczyć ścieżką do czytania bdc, jako jedna z możliwości. Więc kiedy widzi d wie, czy już kroczy ścieżką. Tak więc parser CLR(1) może robić rzeczy, których Parser SLR(1) nie może!

Ale teraz, ponieważ musieliśmy zdefiniować tak wiele ścieżek, Stany maszyny stają się bardzo duże!

Więc łączymy te same wyglądające ścieżki, ale zgodnie z oczekiwaniami może to spowodować problemy zamieszania. Jesteśmy jednak gotowi podjąć ryzyko kosztem zmniejszenia rozmiaru.

To jest parser LALR(1).

Teraz Jak to zrobić algorytmicznie.

Podczas rysowania zestawów konfiguracyjnych dla powyższego języka, zobaczysz konflikt shift-reduce w dwóch stanach. Aby je usunąć, możesz rozważyć SLR(1), który podejmuje decyzje patrząc na follow, ale zauważysz, że nadal nie będzie w stanie. W ten sposób można narysować zestawy konfiguracyjne ponownie, ale tym razem z ograniczeniem, że ilekroć obliczysz zamknięcie, dodawane dodatkowe produkcje muszą mieć ścisłe przestrzeganie (s). Poleć dowolny podręcznik o tym, co powinno być dalej.

Podstawowa różnica między tabelami parserów generowanymi za pomocą SLR vs LR polega na tym, że akcje reduce są oparte na poniższym zestawie dla tabel SLR. Może to być zbyt restrykcyjne, ostatecznie powodując konflikt shift-reduce.

Parser LR, z drugiej strony, bazuje na decyzji reduce tylko na zestawie terminali, które mogą faktycznie śledzić redukcję nie-terminala. Ten zbiór terminali jest często właściwym podzbiorem poniższego zbioru takich Nie-terminali i dlatego ma mniej możliwość kolidowania z działaniami zmianowymi.

Parsery LR są z tego powodu potężniejsze. Tabele parsowania LR mogą być jednak bardzo duże.

Parser LALR zaczyna się od idei budowania tabeli parsowania LR, ale łączy wygenerowane stany w sposób, który powoduje znacznie mniejszy rozmiar tabeli. Minusem jest to, że mała szansa na konflikty byłaby wprowadzona dla niektórych gramatyk, których w przeciwnym razie uniknęłaby tabela LR.

Parsery LALR są nieco mniejsze potężne niż parsery LR, ale nadal potężniejsze niż parsery SLR. YACC i inne tego typu Generatory parserów używają LALR z tego powodu.

P. S. dla zwięzłości, SLR, LALR i LR powyżej naprawdę oznaczają SLR( 1), LALR(1) i LR(1), więc jeden token lookahead jest implikowany.

Parsery SLR rozpoznają właściwy podzbiór gramatyk rozpoznawanych przez parsery LALR(1), Które z kolei rozpoznają właściwy podzbiór gramatyk rozpoznawanych przez parsery LR(1).

Każdy z nich jest skonstruowany jako maszyna stanowa, z każdym stanem reprezentującym pewien zestaw reguł produkcji gramatyki (i pozycji w każdym) podczas parsowania danych wejściowych.

Smocza Księga przykład gramatyki LALR(1), która nie jest SLR jest taki:

S → L = R | R
L → * R | id
R → L

Oto jeden z Stany dla tej gramatyki:

S → L•= R
R → L•

• wskazuje pozycję parsera w każdej z możliwych produkcji. Nie wie, w której z produkcji jest, dopóki nie dotrze do końca i nie spróbuje zmniejszyć.

Tutaj, parser może albo przesunąć {[4] } lub zmniejszyć R → L.

Parser SLR (aka LR(0)) określiłby, czy może zmniejszyć, sprawdzając, czy następny symbol wejściowy znajduje się w follow set z R (tj. zestaw wszystkich terminali w gramatyce, która może następować R). Ponieważ = znajduje się również w tym zestawie, parser SLR napotyka konflikt shift-reduce.

Parser LALR (1) używa zestawu wszystkich terminali, które mogą podążać za tą konkretną produkcją R, która jest tylko $ (tj. koniec wejścia). Tak więc, nie ma konfliktu.

Jak zauważyli poprzedni komentatorzy, parsery LALR(1) mają taką samą liczbę stanów jak parsery SLR. Algorytm propagacji lookahead jest używany do przypięcia lookaheads do Produkcje stanu lustrzanki z odpowiednich stanów LR (1). Powstały parser LALR(1) może wprowadzać konflikty redukuj-redukuj, które nie są obecne w parserze LR(1), ale nie może wprowadzać konfliktów shift-reduce.

W twoim przykładzie, następujący stan LALR (1) powoduje konflikt shift-reduce w implementacji lustrzanki:

S → b d•a / $
A → d• / c

Symbol po / jest następującym zestawem dla każdej produkcji w parserze LALR (1). W lustrzance, follow(A) zawiera a, które również mogą być przesunięte.

Jedna prosta odpowiedź jest taka, że wszystkie gramatyki LR(1) są gramatykami LALR (1). W porównaniu do LALR(1), LR(1) ma więcej stanów w powiązanej maszynie skończonych Stanów(ponad dwukrotnie więcej stanów). I to jest główny powód, dla którego gramatyki LALR(1) wymagają więcej kodu do wykrywania błędów składniowych niż gramatyki LR(1). I jeszcze jedną ważną rzeczą, którą należy wiedzieć odnośnie tych dwóch gramatyk, jest to, że w gramatykach LR(1) możemy mieć mniej konfliktów reduce/reduce. Ale w LALR (1) jest wieksza mozliwosc redukcji / reduce konflikty.