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