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

Jaka jest rzeczywista różnica między parserami LR, SLR i LALR? Wiem, że SLR i LALR są typami parserów LR, ale jaka jest rzeczywista różnica, jeśli chodzi o ich tabele parsowania?

A jak pokazać, czy gramatyka to LR, SLR czy LALR? W przypadku gramatyki LL musimy tylko pokazać, że żadna komórka tabeli parsowania nie powinna zawierać wielu reguł produkcji. Jakieś podobne zasady dla LALR, SLR i LR?

Na przykład, jak możemy pokazać, że gramatyka

S --> Aa | bAc | dc | bda
A --> d

jest LALR (1), ale nie SLR (1)?

EDYCJA (ybungalobill) : Nie otrzymałem satysfakcjonującej odpowiedzi na temat różnicy między LALR i LR. Tak więc tabele LALR są mniejsze, ale może rozpoznać tylko podzbiór gramatyki LR. Czy ktoś mógłby wyjaśnić różnicę między LALR i LR? LALR (1) i LR (1) wystarczą do odpowiedzi. Oba używają 1 tokenu antycypacyjnego i oba są sterowane tabelami! Czym się różnią?

Parsery SLR, LALR i LR można zaimplementować przy użyciu dokładnie tych samych maszyn sterowanych tabelami.

Zasadniczo algorytm analizy zbiera następny token wejściowy T i sprawdza bieżący stan S (i powiązane tabele wyprzedzenia, GOTO i redukcji), aby zdecydować, co zrobić:

• SHIFT: Jeśli bieżąca tabela mówi SHIFT na tokenie T, para (S, T) jest wypychana na stos analizy, stan jest zmieniany zgodnie z tym, co mówi tabela GOTO dla bieżącego tokenu (np. GOTO (T) ), pobierany jest inny token wejściowy T 'i proces się powtarza
• REDUCE: Każdy stan ma 0, 1 lub wiele możliwych redukcji, które mogą wystąpić w stanie. Jeśli parserem jest LR lub LALR, token jest porównywany z zestawami antycypowania dla wszystkich prawidłowych redukcji dla stanu. Jeśli token pasuje do lookahead ustawionego na redukcję reguły gramatyki G = R1 R2 .. Rn, następuje redukcja stosu i przesunięcie: wywoływana jest akcja semantyczna dla G, stos jest zdejmowany n (z Rn) razy, para ( S, G) jest umieszczany na stosie, nowy stan S jest ustawiany na GOTO (G), a cykl powtarza się z tym samym tokenem T. Jeśli parser jest parserem SLR, istnieje co najwyżej jedna reguła redukcji dla stan, więc akcja redukcyjna może być wykonywana na ślepo bez szukania, która redukcja ma zastosowanie. Jest to przydatne dla parsera SLR wiedzieć, czy jestobniżka lub nie; łatwo jest stwierdzić, czy każdy stan wyraźnie rejestruje liczbę związanych z nim redukcji, a liczba ta jest i tak potrzebna dla wersji L (AL) R w praktyce.
• BŁĄD: Jeśli ani SHIFT, ani REDUCE nie są możliwe, deklarowany jest błąd składni.

Więc jeśli wszyscy używają tej samej maszyny, po co?

Rzekoma zaletą lustrzanek jednoobiektywowych jest prostota wykonania; nie musisz przeglądać możliwych redukcji, sprawdzając zestawy lookahead, ponieważ jest ich co najwyżej jeden, a jest to jedyna realna akcja, jeśli nie ma wyjść SHIFT ze stanu. Która redukcja ma zastosowanie, może być przypisana konkretnie do stanu, więc maszyna parsująca SLR nie musi na to polować. W praktyce parsery L (AL) R obsługują pożytecznie większy zestaw języków, a ich implementacja jest tak niewielka, że ​​nikt nie wdraża lustrzanki cyfrowej poza ćwiczeniami akademickimi.

Różnica między LALR i LR ma związek z generatorem tabel. Generatory parserów LR śledzą wszystkie możliwe redukcje z określonych stanów i ich dokładny zestaw wyprzedzenia; kończysz ze stanami, w których każda redukcja jest powiązana z jej dokładnym wyprzedzeniem ustawionym z lewego kontekstu. To prowadzi do tworzenia raczej dużych zbiorów stanów. Generatory parserów LALR są skłonne łączyć stany, jeśli tablice GOTO i zestawy lookhead dla redukcji są zgodne i nie powodują konfliktów; daje to znacznie mniejszą liczbę stanów, kosztem niemożności rozróżnienia pewnych sekwencji symboli, które LR może rozróżnić. Tak więc parsery LR mogą analizować większy zestaw języków niż parsery LALR, ale mają znacznie większe tablice parsera. W praktyce można znaleźć gramatyki LALR, które są na tyle bliskie językom docelowym, że rozmiar automatu stanowego jest wart optymalizacji;

A więc: wszystkie trzy używają tej samej maszyny. Lustrzanka jest „łatwa” w tym sensie, że można zignorować odrobinę maszyny, ale nie jest warta zachodu. LR analizuje szerszy zestaw języków, ale tabele stanów wydają się być dość duże. To pozostawia LALR jako praktyczny wybór.

Powiedziawszy to wszystko, warto wiedzieć, że parsery GLR mogą parsować dowolny język bezkontekstowy, używając bardziej skomplikowanych maszyn, ale dokładnie tych samych tabel (w tym mniejszej wersji używanej przez LALR). Oznacza to, że GLR jest ściśle silniejszy niż LR, LALR i SLR; prawie jeśli możesz napisać standardową gramatykę BNF, GLR przeanalizuje zgodnie z nią. Różnica w maszynerii polega na tym, że GLR jest skłonny wypróbować wiele analiz, gdy występują konflikty między tabelą GOTO a zestawami lookahead. (Jak GLR robi to skutecznie, jest po prostu geniuszem [nie moim], ale nie pasuje do tego postu SO).

To dla mnie niezwykle przydatny fakt. Buduję analizatory programów, a transformatory kodu i parsery są konieczne, ale „nieciekawe”; interesującą pracą jest to, co robisz z przeanalizowanym wynikiem, więc nacisk kładziony jest na wykonanie pracy po przeanalizowaniu. Korzystanie z GLR oznacza, że ​​mogę stosunkowo łatwo budować gramatyki robocze, w porównaniu do hakowania gramatyki, aby uzyskać użyteczną formę LALR. Ma to duże znaczenie, gdy próbujesz radzić sobie z językami nieakademickimi, takimi jak C ++ lub Fortran, gdzie dosłownie potrzebujesz tysięcy reguł, aby dobrze obsługiwać cały język i nie chcesz spędzać życia na próbach łamania reguł gramatycznych spełniają ograniczenia LALR (a nawet LR).

Jako rodzaj słynnego przykładu, C ++ jest uważany za niezwykle trudny do przeanalizowania ... przez facetów zajmujących się analizowaniem LALR. C ++ można łatwo przeanalizować przy użyciu maszyny GLR, używając prawie zasad podanych na końcu podręcznika C ++. (Mam dokładnie taki parser, który obsługuje nie tylko waniliowy C ++, ale także różne dialekty dostawców. Jest to możliwe tylko w praktyce, ponieważ używamy parsera GLR, IMHO).

[EDYCJA Listopad 2011: Rozszerzyliśmy nasz parser, aby obsługiwał całość C ++ 11. GLR znacznie to ułatwiło. EDYCJA Sierpień 2014: Teraz obsługuję całość C ++ 17. Nic się nie zepsuło ani nie pogorszyło, GLR wciąż miauczy kota.]

Parsery LALR łączą podobne stany w gramatyce LR, aby tworzyć tabele stanów parsera, które są dokładnie tego samego rozmiaru co równoważna gramatyka 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 być LALR, te połączone stany powodują konflikty parsera lub tworzą parser, który nie rozpoznaje w pełni oryginalnej gramatyki LR.

BTW, wspomniałem o kilku rzeczach na ten temat w moim algorytmie tabeli parsowania MLR (k) tutaj .

Uzupełnienie

Krótka odpowiedź jest taka, że ​​tabele parsowania LALR są mniejsze, ale mechanizm parsera jest taki sam. Dana gramatyka LALR będzie generować znacznie większe tabele parsowania, jeśli wszystkie stany LR zostaną wygenerowane, z dużą ilością redundantnych (prawie identycznych) stanów.

Tabele LALR są mniejsze, ponieważ podobne (nadmiarowe) stany są łączone razem, skutecznie odrzucając informacje o kontekście / lookahead, 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ć zakodowane jako tabele LALR, ponieważ bardziej złożone gramatyki mają bardziej skomplikowane lookahead, co skutkuje dwoma lub więcej stanami zamiast jednego scalonego stanu.

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

Jeszcze inna odpowiedź (YAA).

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

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

Generator parsera LALR tworzy maszynę stanów LR (0) i oblicza wyprzedzenia z maszyny stanów LR (0) (poprzez przejścia terminala). Jest to poprawne podejście, ale czasami zgłasza konflikty, które nie istniałyby w maszynie stanowej LR (1).

Kanoniczny generator parsera LR oblicza maszynę stanów LR (1), a wyprzedzenia są już częścią maszyny stanów LR (1). Te tablice parsera mogą być bardzo duże.

Generator parsera minimalnego LR oblicza maszynę stanów LR (1), ale łączy zgodne stany podczas procesu, a następnie oblicza wyprzedzenia z minimalnej maszyny stanów LR (1). Te tabele parsera są tego samego rozmiaru lub nieco większe niż tabele parsera LALR, co daje najlepsze rozwiązanie.

LRSTAR 10.0 może generować parsery LALR (1), LR (1), CLR (1) lub LR (*) w C ++, cokolwiek jest potrzebne do twojej gramatyki. Zobacz ten diagram, który pokazuje różnicę między parserami LR.

[Pełne informacje: LRSTAR to mój produkt]

Załóżmy, że parser bez lookahead szczęśliwie analizuje napisy pod kątem twojej gramatyki.

Korzystając z podanego przykładu, napotyka ciąg dc, co robi? Czy redukuje to do S, ponieważ dcjest poprawnym ciągiem utworzonym przez tę gramatykę? A może próbowaliśmy przeprowadzić analizę, bdcponieważ nawet to jest dopuszczalny ciąg?

Jako ludzie, wiemy, że odpowiedź jest prosta, musimy po prostu pamiętać, czy właśnie przeanalizowaliśmy, bczy 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 robić w tym przypadku; zamiast tego musimy spojrzeć w 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 ilekroć napotka a b, zacznie kroczyć ścieżką do czytania bdc, jako jedna możliwość. Więc kiedy widzi d, wie, czy już idzie ścieżką. Zatem 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 z zamieszaniem. Jesteśmy jednak skłonni zaryzykować kosztem zmniejszenia rozmiaru.

To jest twój parser LALR (1).

Teraz, jak to zrobić algorytmicznie.

Kiedy narysujesz zestawy konfiguracyjne dla powyższego języka, zobaczysz konflikt zmiany biegów w dwóch stanach. Aby je usunąć, możesz rozważyć lustrzankę (1), która podejmuje decyzje patrząc na następcę, ale zauważysz, że nadal nie będzie w stanie. W ten sposób możesz narysować zestawy konfiguracyjne ponownie, ale tym razem z zastrzeżeniem, że za każdym razem, gdy obliczasz zamknięcie, dodatkowe dodawane produkcje muszą mieć ścisłe śledzenie (y). Skorzystaj z dowolnego podręcznika, aby dowiedzieć się, co to powinno być.

Podstawowa różnica między tabelami analizatora składni wygenerowanymi za pomocą SLR a LR polega na tym, że działania redukujące są oparte na ustawieniu Follows dla tabel SLR. Może to być zbyt restrykcyjne, ostatecznie powodując konflikt z redukcją zmian.

Z drugiej strony, parser LR bazuje na redukcji decyzji tylko na zestawie terminali, które faktycznie mogą podążać za redukowanym nieterminalem. Ten zestaw terminali jest często odpowiednim podzbiorem zestawu Follows takiego nieterminala, a zatem ma mniejsze szanse na konflikt z działaniami przesunięcia.

Z tego powodu parsery LR są bardziej wydajne. Jednak tabele analizy LR mogą być bardzo duże.

Parser LALR zaczyna się od pomysłu zbudowania tablicy parsującej LR, ale łączy wygenerowane stany w sposób, który skutkuje znacznie mniejszym rozmiarem tabeli. Wadą jest to, że mała szansa na konflikty byłaby wprowadzona w przypadku niektórych gramatyk, których w przeciwnym razie uniknęłaby tabela LR.

Parsery LALR są nieco mniej wydajne niż parsery LR, ale nadal są silniejsze niż parsery SLR. Z tego powodu YACC i inne tego typu generatory parserów zwykle używają LALR.

PS Dla zwięzłości, SLR, LALR i LR powyżej naprawdę oznaczają SLR (1), LALR (1) i LR (1), więc zakłada się jeden token lookahead.

Parsery SLR rozpoznają odpowiedni podzbiór gramatyk rozpoznawalnych przez parsery LALR (1), które z kolei rozpoznają odpowiedni podzbiór gramatyk rozpoznawalnych przez parsery LR (1).

Każdy z nich jest skonstruowany jako maszyna stanów, gdzie każdy stan reprezentuje pewien zestaw reguł produkcji gramatyki (i pozycji w każdej z nich) podczas analizowania danych wejściowych.

Smok Book przykładem LALR (1) gramatyki, która nie jest SLR jest taka:

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

Oto jeden ze stanów dla tej gramatyki:

S → L•= R
R → L•

•Wskazuje pozycję parsera w każdym z możliwych przedstawień. Nie wie, w której z produkcji się aktualnie znajduje, dopóki nie dobiega końca i nie próbuje skrócić.

Tutaj parser może przesunąć =lub zmniejszyć R → L.

Lustrzanka (aka LR (0)) parser byłoby ustalić, czy może to zmniejszyć poprzez sprawdzenie, czy wejście obok symbol znajduje się w zbiorze obserwacji dnia R(czyli zbiór wszystkich terminali w gramatyce, że może obserwować R). Ponieważ =również znajduje się w tym zestawie, parser SLR napotyka konflikt zmiany biegów.

Jednak parser LALR (1) użyłby zestawu wszystkich terminali, które mogą podążać za tą konkretną produkcją R, która jest tylko $(tj. Końcem 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 przyporządkowania lookaheadów do produkcji stanu SLR z odpowiednich stanów LR (1). Wynikowy parser LALR (1) może wprowadzać konflikty redukuj-redukuj, których nie ma w parserze LR (1), ale nie może wprowadzać konfliktów redukuj-przesuń.

W Twoim przykładzie następujący stan LALR (1) powoduje konflikt zmiany biegów w implementacji lustrzanki jednoobiektywowej:

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

Symbol po /to następujący zestaw dla każdej produkcji w parserze LALR (1). W lustrzance SLR, follow ( A) zawiera a, które również można przesunąć.

Oprócz powyższych odpowiedzi, ten diagram pokazuje, w jaki sposób powiązane są różne parsery:

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 skojarzonej maszynie skończonej (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ć o tych dwóch gramatykach, jest to, że w gramatykach LR (1) możemy mieć mniej konfliktów zmniejszania / zmniejszania. Ale w LALR (1) istnieje większe możliwości redukcji / redukcji konfliktów.