Parser LR
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Należy w nim poprawić: styl tłumaczenia, dodać linki, poprawić błędy. Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Parser LR (ang. Left to right, identifying the Right-most production) – to analizator składniowy (ang. parser) dla gramatyk bezkontekstowych, który przetwarza wejście od lewej do prawej metodą wstępującą i produkuje prawostronne wyprowadzenie. Terminu parser LR(k), gdzie k jest liczbą naturalną lub zerem, używa się do oznaczenia analizatorów podejmujących decyzje na podstawie k podglądanych symboli na wejściu które są użyte w podjęciu decyzji parsowania. Zwykle k jest równe 1 i jest często pomijane. Parser LR(k) zazwyczaj oznacza kanoniczny parser LR(k). Jednakże parser SLR i LALR również są typu LR. Gramatyka bezkontekstowa nazywa się gramatyką LR(k), jeżeli istnieje dla niej parser LR(k).
Mówimy że parser LR wykonuje parsowanie bottom-up ponieważ próbuje wyprowadzić produkcję najwyższego poziomu przez budowę z liści.
Wiele języków programowania jest opisanych przez gramatykę która jest LR(1) lub bliska do bycia taką i z tego powodu parsery LR są często używane przez kompilatory do analizy syntaktycznej kodu źródłowego.
W typowym użyciu "parser LR" oznacza konkretny parser zdolny rozpoznać konkretny język określony gramatyką bezkontekstową.
Parsowanie LR ma wiele korzyści:
- Wiele języków programowania może być parsowane przy użyciu parsera LR. Godnym uwagi wyjątkiem jest C++.
- Parsery LR mogą być zaimplementowane bardzo wydajnie.
- Ze wszystkich parserów które skanują wejście od lewej do prawej, parsery LR wykrywają błędy składniowe (to jest wtedy, gdy wejście nie zgadza się z gramatyką) tak szybko jak to możliwe.
Parsery LR są trudne do wyprodukowania ręcznego; są one zwykle konstruowane przez generator parserów. W zależności od tego jak jest generowana tabela parsowania, te parsery są zwane Simple LR (SLR), Look-ahead LR parser (LALR), i kanoniczny parser LR. Zbiory gramatyk określone przez te rodzaje parserów mają następującą własność 
Popularny Yacc tworzy parsery LALR(1).
Spis treści |
[edytuj] Architektura parserów LR
Konwencjonalny parsery LR są prezentowane i implementowane jako automaty ze stosem bazujące na tabelach.
Sterowany tabelą parser bottom-up jest przedstawiony schematycznie na rysunku 1. Mamy następujący opis prawostronnego wyprowadzenia przez ten parser.
[edytuj] Przypadek ogólny
Parser jest automatem ze stanami, na który składa się:
- bufor wejścia
- stos na którym przechowywana jest lista stanów w których był automat
- tabela goto w której opisane jest, do którego nowego stanu powinniśmy przejść
- an tabela akcji która daje regułę gramatyki do zastosowania w bieżącym stanie i dla aktualnego symbolu terminalnego w strumieniu wejściowym.
[edytuj] Algorytm parsowania
Ponieważ parser LR czyta strumień wejściowy od lewej do prawej ale potrzebuje wyprodukować prawostronne wyprowadzenie, używa redukcji zamiast wyprowadzeń do przetwarzania strumienia wejściowego. Oznacza to, że algorytm działa tworząc "lewostronną redukcję" wejścia. Końcowym rezultatem po odwróceniu będzie prawostronne wyprowadzenie.
Algorytm parsowania LR działa następująco:
- Stos jest inicjowany przez [0]. Bieżącym stanem będzie zawsze ten stan, który jest na szczycie stosu.
- Biorąc bieżący stan i bieżący symbol terminalny w strumieniu wejściowym, akcja jest brana z tabeli akcji. Mamy cztery przypadki:
- przesunięcie (shift) sn:
- bieżący symbol terminalny jest usuwany ze strumienia wejściowego
- stan n jest wkładany na stos i staje się bieżącym statem
- redukcja (reduce) rm:
- liczba m oznaczająca numer reguły wyprowadzania jest wypisywana do strumienia wyjściowego
- dla każdego symbolu (terminalnego lub nieterminalnego) z prawej strony reguły m stan jest usuwany ze stosu
- biorąc stan który jest następnie na szczycie stosu i symbol nieterminalny który jest po lewej stronie reguły m, nowy stan jest brany z tabeli goto i staje się nowym bieżącym stanem przez włożenie go na stos
- akceptacja: strumień symboli terminalnych jest zaakceptowany
- brak akcji: zgłaszanyt jest błąd syntaktyczny
- przesunięcie (shift) sn:
- Krok 2 jest powtarzany dotąd aż strumień zostanie zaakceptowany lub zostanie zgłoszony błąd składni.
[edytuj] Konkretny przykład
Aby wyjaśnić jak to działa użyjemy następującej małej gramatyki której startowym symbolem jest E:
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
i parsujemy następujący strumień wejściowy:
- 1 + 1
[edytuj] Tabele action i goto
Dwie tabele LR(0) parsowania dla tej gramatyki wyglądają następująco:
| action | goto | |||||||
| stan | * | + | 0 | 1 | $ | E | B | |
| 0 | s1 | s2 | 3 | 4 | ||||
| 1 | r4 | r4 | r4 | r4 | r4 | |||
| 2 | r5 | r5 | r5 | r5 | r5 | |||
| 3 | s5 | s6 | acc | |||||
| 4 | r3 | r3 | r3 | r3 | r3 | |||
| 5 | s1 | s2 | 7 | |||||
| 6 | s1 | s2 | 8 | |||||
| 7 | r1 | r1 | r1 | r1 | r1 | |||
| 8 | r2 | r2 | r2 | r2 | r2 | |||
Tabela action jest indeksowana przez stan automatu parsującego i symbol terminalny (włączając w to specjalny terminal $ oznaczający koniec strumienia wejściowego) i zawiera trzy rodzaje akcji:
- przesunięcie (shift), które zapisujemy jako 'sn' i oznacza że następnym stanem jest n
- redukcja (reduce), którą zapisujemy jako 'rm' i oznacza że powinna być wykonana redukcja regułą gramatyki o numerze m
- akceptacja (accept), którą zapisujemy jako 'acc' i oznacza że parser akceptuje cały łańcuch symboli strumienia wejściowego
Tabela 'goto jest indeksowana przez stan parsera i symbol nieterminalny i wskazuje następny stan w jaki przejdzie automat parsujący jeśli lewa strona ostatnio użytej do redukcji reguły będzie pewnym symbolem nieterminalnym.
[edytuj] Procedura parsowania
Poniższa tabela pokazuje każdy krok w procesie. Tutaj stan odnosi się do elementu na szczycie stosu (element najbardziej na prawo) i następna akcja jest określona przez odniesienie się do tabeli powyżej. Zauważmy że symbol $ jest dołączany do strumienia wejściowego oznaczając koniec strumienia.
| Stan | Strumień Input | Strumień Output | Stos | Następna akcja |
|---|---|---|---|---|
| 0 | 1+1$ | [0] | Shift 2 | |
| 2 | +1$ | [0,2] | Reduce 5 | |
| 4 | +1$ | 5 | [0,4] | Reduce 3 |
| 3 | +1$ | 5,3 | [0,3] | Shift 6 |
| 6 | 1$ | 5,3 | [0,3,6] | Shift 2 |
| 2 | $ | 5,3 | [0,3,6,2] | Reduce 5 |
| 8 | $ | 5,3,5 | [0,3,6,8] | Reduce 2 |
| 3 | $ | 5,3,5,2 | [0,3] | Accept |
[edytuj] Analiza działania
Parser rozpoczyna swoją pracę ze stosem zawierającym jedynie początkowy stan ('0'):
- [0]
Pierwszym symbolem łańcucha wejściowego który parser widzi jest '1'. Aby dowiedzieć się jaka jest następna akcja (przesunięcie,redukcja,akceptacja lub błąd), tabela action jest indeksowana bieżącym stanem (pamiętajmy że "bieżący stan" jest stanem który jest na szczycie stosu), który w tym wypadku jest 0 i bieżącym symbolem wejściowym którym jest '1'. Tabela action określa przejście do stanu 2 i tak stan 2 jest wkładany na stos (ponownie, pamiętajmy że wszystkie informacje o stanie automatu znajdują się na stosie, więc "przejście do stanu 2" jest tym samym co włożenie 2 na stos). W wyniku tego stos ma postać:
- [0 '1' 2]
gdzie na szczycie stosu jest stan 2. W celu objaśnienia jest pokazany również symbol (np.'1 ', B), który spowodował przejście do następnego stanu, chociaż ściśle rzecz biorąc nie jest częścią stosu.
W stanie 2 tabela action pokazuje nam że niezależnie od symbolu widzianego na wejściu powinniśmy dokonać redukcji 5-tą regułą gramatyki. Jeśli tabela jest poprawna, oznacza to że parser właśnie rozpoznał prawą stronę reguły 5 co rzeczywiście ma tu miejsce. W tym przypadku wypisujemy numer reguły którym jest 5 do strumienia wyjściowego, zdejmujemy ze stosu jeden stan (ponieważ prawa strona reguły ma jeden symbol) i wkładamy na stos stan z komórki tabeli goto dla stanu 0 i symbolu nieterminalnego B (z lewej strony produkcji 5) czyli stan numer 4. Stos przybiera postać:
- [0 B 4]
Jednak w stanie 4 tabela action informuje że powinniśmy teraz wykonać redukcję regułą 3. Tak więc wypisujemy 3 do strumienia wynikowego, zdejmujemy jeden stan ze stosu i znajdujemy nowy stan w tabeli goto dla stanu 0 i symbolu nieterminalnego E, którym jest stan o numerze 3. Stos ma postać:
- [0 E 3]
Następnym symbolem terminalnym który widzi parser jest '+' i zgodnie z tabelą action należy przejść do stanu 6:
- [0 E 3 '+' 6]
Zauważmy że wynikowy stos może być interpretowany jako historia deterministycznego automatu skończonego który właśnie przeczytał symbol nieterminalny E z następującym za nim symbolem terminalnym '+'. Tablica przejść tego automatu jest zdefiniowana przez akcje shift w tabeli action i akcje goto w tabeli goto.
Następnym symbolem terminalnym jest teraz '1' i znaczy to że wykonujemy przesunięcie i idziemy do stanu 2:
- [0 E 3 '+' 6 '1' 2]
Podobnie jak poprzednia '1', ta jest redukowana do B co daje następujący stos:
- [0 E 3 '+' 6 B 8]
Zauważmy znowu że stos odpowiada liście stanów automatu skończonego który przeczytał symbol nieterminalny E, za nim '+' a następnie nieterminal B. W stanie 8 zawsze wykonujemy redukcję regułą 2. Zauważmy że ostatnie 3 stany na stosie odpowiadają trzem symbolom prawej strony produkcji (reguły) 2.
- [0 E 3]
Na koniec czytamy '$' ze strumienia wejściowego co oznacza że zgodnie z tabelą action (bieżący stanem jest 3) parser akceptuje wejściowy napis. Numery reguł które zostały wypisane do strumienia wynikowego to [5, 3, 5, 2] co jest istotnie odwrotnym prawostronnym wyprowadzeniem ciągu "1 + 1".
