parser LR

W informatyce parsery LR są rodzajem parsera oddolnego , który analizuje deterministyczne języki bezkontekstowe w czasie liniowym. Istnieje kilka wariantów parserów LR: parsery SLR , parsery LALR , kanoniczne parsery LR(1) , minimalne parsery LR(1) i parsery GLR . Parsery LR mogą być generowane przez generator parserów z gramatyki formalnej definiowanie składni języka, który ma być analizowany. Są szeroko stosowane do przetwarzania języków komputerowych .

Parser LR ( wyprowadzenie od lewej do prawej, wyprowadzenie najbardziej od prawej w odwrotnej kolejności) odczytuje tekst wejściowy od lewej do prawej bez tworzenia kopii zapasowej (dotyczy to większości parserów) i tworzy wyprowadzenie najbardziej na prawo w odwrotnej kolejności: wykonuje od dołu do góry parse – nie parsowanie LL odgórne ani parsowanie ad-hoc. Po nazwie LR często występuje kwalifikator numeryczny, jak w przypadku LR(1) lub czasami LR( k ) . Aby uniknąć cofania się lub zgadywania, parser LR może zerknąć do przodu na k wyprzedzające symbole wejściowe przed podjęciem decyzji, jak przeanalizować wcześniejsze symbole. Zazwyczaj k wynosi 1 i nie jest wymienione. Nazwa LR jest często poprzedzona innymi kwalifikatorami, jak w przypadku SLR i LALR . Notacja LR ( k ) dla gramatyki została zasugerowana przez Knuth jako „przetłumaczalna z lewej na prawą ze związanym k ”.

Parsery LR są deterministyczne; wytwarzają pojedynczą poprawną analizę bez zgadywania lub cofania się w czasie liniowym. Jest to idealne rozwiązanie dla języków komputerowych, ale parsery LR nie są odpowiednie dla języków ludzkich, które wymagają bardziej elastycznych, ale nieuchronnie wolniejszych metod. Niektóre metody, które mogą analizować dowolne języki bezkontekstowe (np. Cocke-Younger-Kasami , Earley , GLR ) mają wydajność w najgorszym przypadku w czasie O( n 3 ). Inne metody, które wycofują się lub dają wiele analiz, mogą nawet zająć wykładniczy czas, gdy źle zgadną.

Powyższe właściwości L , R i k są w rzeczywistości wspólne dla wszystkich parserów redukujących przesunięcie , w tym parserów pierwszeństwa . Ale zgodnie z konwencją nazwa LR oznacza formę analizy składniowej wymyśloną przez Donalda Knutha i wyklucza wcześniejsze, mniej wydajne metody pierwszeństwa (na przykład parser Operator-precence ). Parsery LR mogą obsługiwać większy zakres języków i gramatyk niż parsery pierwszeństwa lub parsowanie LL z góry na dół . Dzieje się tak, ponieważ parser LR czeka, aż zobaczy całą instancję jakiegoś wzorca gramatycznego, zanim zaakceptuje to, co znalazł. Parser LL musi zdecydować lub zgadnąć, co widzi, znacznie wcześniej, kiedy widział tylko lewy symbol wejściowy tego wzorca.

Przegląd

Drzewo analizy od dołu do góry, na przykład A*2 + 1

Drzewo analizy oddolnej zbudowane w ponumerowanych krokach

Parser LR skanuje i analizuje tekst wejściowy w jednym przejściu do przodu nad tekstem. Parser buduje drzewo analizy przyrostowo, od dołu do góry i od lewej do prawej, bez zgadywania i cofania się. W każdym punkcie tego przebiegu parser gromadzi listę poddrzew lub fraz tekstu wejściowego, które zostały już przeanalizowane. Te poddrzewa nie są jeszcze połączone, ponieważ parser nie osiągnął jeszcze prawego końca wzorca składni, który je połączy.

W kroku 6 w przykładowej analizie składniowej tylko „A*2” zostało przeanalizowane niekompletnie. Istnieje tylko zacieniony lewy dolny róg drzewa analizy. Żaden z węzłów drzewa analizy o numerach 7 i wyższych jeszcze nie istnieje. Węzły 3, 4 i 6 są korzeniami izolowanych poddrzew odpowiednio dla zmiennej A, operatora * i liczby 2. Te trzy węzły główne są tymczasowo przechowywane w stosie analizy. Pozostała nieprzeanalizowana część strumienia wejściowego to „+ 1”.

Zmień i ogranicz działania

Podobnie jak w przypadku innych parserów z redukcją przesunięć, parser LR działa, wykonując pewną kombinację kroków przesunięcia i kroków redukcji.

  • Krok Shift przesuwa się w strumieniu wejściowym o jeden symbol. Ten przesunięty symbol staje się nowym drzewem analizy pojedynczego węzła.
  • Krok Reduce stosuje ukończoną regułę gramatyczną do niektórych ostatnich drzew analizy, łącząc je razem jako jedno drzewo z nowym symbolem korzenia.

Jeśli dane wejściowe nie zawierają błędów składniowych, parser kontynuuje te kroki, aż wszystkie dane wejściowe zostaną zużyte, a wszystkie drzewa analizy zostaną zredukowane do jednego drzewa reprezentującego całe legalne dane wejściowe.

Parsery LR różnią się od innych parserów z redukcją przesunięć tym, w jaki sposób decydują, kiedy redukować i jak wybierać między regułami o podobnych zakończeniach. Ale ostateczne decyzje i sekwencja kroków przesunięcia lub zmniejszenia są takie same.

Duża część wydajności parsera LR wynika z determinizmu. Aby uniknąć zgadywania, parser LR często patrzy w przód (w prawo) na następny zeskanowany symbol, zanim zdecyduje, co zrobić z poprzednio zeskanowanymi symbolami. Skaner leksykalny działa o jeden lub więcej symboli przed parserem. Symbole wyprzedzające są „kontekstem po prawej stronie” dla decyzji analizowania.

Stos parsowania od dołu do góry

Parser oddolny w kroku 6

Podobnie jak inne parsery z redukcją przesunięć, parser LR leniwie czeka, aż przeskanuje i przeanalizuje wszystkie części jakiejś konstrukcji, zanim zatwierdzi, czym jest połączona konstrukcja. Następnie parser działa natychmiast na kombinacji, zamiast czekać dalej. W przykładzie drzewa analizy fraza A zostaje zredukowana do wartości, a następnie do produktów w krokach 1-3, gdy tylko pojawi się lookahead *, zamiast czekać później na uporządkowanie tych części drzewa analizy. Decyzje dotyczące sposobu obsługi A są oparte wyłącznie na tym, co już widział parser i skaner, bez uwzględnienia rzeczy, które pojawiają się znacznie później po prawej stronie.

Redukcje reorganizują ostatnio analizowane rzeczy, bezpośrednio na lewo od symbolu wyprzedzającego. Tak więc lista już przeanalizowanych rzeczy działa jak stos . Ten stos analizy rośnie w prawo. Podstawa lub spód stosu znajduje się po lewej stronie i zawiera najbardziej wysunięty na lewo, najstarszy fragment analizy. Każdy krok redukcji działa tylko na skrajne prawe, najnowsze fragmenty analizy. (Ten akumulacyjny stos analizy jest bardzo różny od predykcyjnego, rosnącego w lewo stosu analizy używanego przez parsery zstępujące ).

Oddolne kroki analizy, na przykład A*2 + 1

Krok Przeanalizuj stos Nieprzeanalizowane Przesuń/zmniejsz
0 pusty A*2 + 1 zmiana
1 ID *2 + 1 Wartość → identyfikator
2 Wartość *2 + 1 Produkty → Wartość
3 Produkty *2 + 1 zmiana
4 Produkty * 2 + 1 zmiana
5 Produkty * wew + 1 Wartość → wew
6 Produkty * Wartość + 1 Produkty → Produkty * Wartość
7 Produkty + 1 Sumy → Produkty
8 sumy + 1 zmiana
9 Sumy + 1 zmiana
10 Sumy + wew eof Wartość → wewn
11 Sumy + Wartość eof Produkty → Wartość
12 Sumy + produkty eof Sumy → Sumy + Produkty
13 sumy eof zrobione

Krok 6 stosuje regułę gramatyczną z wieloma częściami:

Produkty → Produkty * Wartość

To pasuje do szczytu stosu zawierającego przeanalizowane frazy „... Produkty * Wartość”. Krok zmniejszania zastępuje to wystąpienie prawej strony reguły, „Produkty * Wartość”, symbolem lewej strony reguły, tutaj większym Produktem. Jeśli parser zbuduje kompletne drzewa analizy, trzy drzewa produktów wewnętrznych, * i wartości zostaną połączone nowym korzeniem drzewa produktów. W przeciwnym razie semantyczne z wewnętrznych produktów i wartości są wyprowadzane do późniejszego przebiegu kompilatora lub są łączone i zapisywane w nowym symbolu produktów.

Kroki analizy LR na przykład A*2 + 1

W parserach LR decyzje dotyczące przesunięcia i zmniejszenia są potencjalnie oparte na całym stosie wszystkiego, co zostało wcześniej przeanalizowane, a nie tylko na pojedynczym, najwyższym symbolu stosu. Jeśli zostanie to zrobione w niesprytny sposób, może to prowadzić do bardzo powolnych parserów, które stają się coraz wolniejsze w przypadku dłuższych danych wejściowych. Parsery LR robią to ze stałą szybkością, podsumowując wszystkie istotne informacje lewego kontekstu w jedną liczbę zwaną stanem parsera LR(0) . Dla każdej metody analizy gramatyki i LR istnieje stała (skończona) liczba takich stanów. Oprócz przechowywania już przeanalizowanych symboli, stos analizy zapamiętuje również numery stanów, do których dotarło wszystko aż do tych punktów.

Na każdym etapie analizy cały tekst wejściowy jest dzielony na stos wcześniej przeanalizowanych fraz, bieżący symbol wyprzedzający i pozostały nieprzeskanowany tekst. Następna akcja parsera jest określona przez jego aktualny numer stanu LR(0) (najbardziej na prawo na stosie) i symbol wyprzedzania. W poniższych krokach wszystkie czarne szczegóły są dokładnie takie same, jak w innych parserach z redukcją przesunięć innych niż LR. Stosy parsera LR dodają informacje o stanie w kolorze fioletowym, podsumowując czarne frazy po lewej stronie stosu i jakich możliwości składni można się spodziewać w następnej kolejności. Użytkownicy parsera LR zazwyczaj mogą ignorować informacje o stanie. Stany te zostały wyjaśnione w dalszej części.


Krok
Parse Stan stosu [ Stan symbolu ]*
Spójrz przed siebie
Nieskanowane		 Akcja parsera

Reguła gramatyczna
Następny stan
0

0

ID *2 + 1 zmiana 9
1

0 identyfikator 9

* 2 + 1 zmniejszyć Wartość → identyfikator 7
2

0 Wartość 7

* 2 + 1 zmniejszyć Produkty → Wartość 4
3

0 Produkty 4

* 2 + 1 zmiana 5
4

0 Produkty 4 * 5

int + 1 zmiana 8
5

0 Produkty 4 * 5 wew 8

+ 1 zmniejszyć Wartość → wew 6
6

0 Produkty 4 * 5 Wartość 6

+ 1 zmniejszyć Produkty → Produkty * Wartość 4
7

0 Produkty 4

+ 1 zmniejszyć Sumy → Produkty 1
8

0 Sumy 1

+ 1 zmiana 2
9

0 Sumy 1 + 2

int eof zmiana 8
10

0 Sumy 1 + 2 cal 8

eof zmniejszyć Wartość → wew 7
11

0 Sumy 1 + 2 Wartość 7

eof zmniejszyć Produkty → Wartość 3
12

0 Sumy 1 + 2 Produkty 3

eof zmniejszyć Sumy → Sumy + Produkty 1
13

0 Sumy 1

eof zrobione

W początkowym kroku 0 strumień wejściowy „A*2 + 1” jest dzielony na

  • pusta sekcja na stosie parsowania,
  • tekst wyprzedzający „A” zeskanowany jako symbol identyfikacyjny i
  • pozostały nieprzeskanowany tekst „*2 + 1”.

Stos analizy zaczyna się od przechowywania tylko stanu początkowego 0. Kiedy stan 0 widzi identyfikator wyprzedzający , wie, że powinien przesunąć ten identyfikator na stos, przeskanować następny symbol wejściowy * i przejść do stanu 9.

W kroku 4 całkowity strumień wejściowy „A*2 + 1” jest obecnie dzielony

  • przeanalizowana sekcja „A *” z 2 ułożonymi w stos frazami Produkty i * ,
  • tekst z wyprzedzeniem „2” zeskanowany jako symbol int i
  • pozostały nieprzeskanowany tekst „+ 1”.

Stany odpowiadające ułożonym w stos frazom to 0, 4 i 5. Bieżący, skrajny prawy stan na stosie to stan 5. Kiedy stan 5 widzi int z wyprzedzeniem, wie, że powinien przenieść tę int na stos jako własną frazę i zeskanuj następny symbol wejścia + i przejdź do stanu 8.

W kroku 12 cały strumień wejściowy został zużyty, ale tylko częściowo zorganizowany. Bieżący stan to 3. Kiedy stan 3 widzi eof z wyprzedzeniem , wie, że ma zastosować uzupełnioną regułę gramatyczną

Sumy → Sumy + Produkty

przez połączenie trzech skrajnych prawych fraz stosu dla sum, + i produktów w jedną rzecz. Stan 3 sam nie wie, jaki powinien być następny stan. Można to znaleźć, wracając do stanu 0, tuż na lewo od redukowanej frazy. Kiedy stan 0 widzi tę nową ukończoną instancję sumy, przechodzi do stanu 1 (ponownie). To konsultowanie starszych stanów jest powodem, dla którego są one przechowywane na stosie, zamiast zachowywać tylko bieżący stan.

Gramatyka dla przykładu A*2 + 1

Parsery LR są zbudowane z gramatyki, która formalnie definiuje składnię języka wejściowego jako zestaw wzorców. Gramatyka nie obejmuje wszystkich reguł językowych, takich jak wielkość liczb czy konsekwentne stosowanie nazw i ich definicji w kontekście całego programu. Parsery LR używają gramatyki bezkontekstowej , która zajmuje się tylko lokalnymi wzorami symboli.

Użyta tutaj przykładowa gramatyka jest niewielkim podzbiorem języka Java lub C:

r0: Cel → Sumy eof
r1: Sumy → Sumy + Produkty
r2: Sumy → Produkty
r3: Produkty → Produkty * Wartość
r4: Produkty → Wartość
r5: Wartość → int
r6: Wartość → id

Symbole końcowe gramatyki to wieloznakowe symbole lub „tokeny” znalezione w strumieniu wejściowym przez skaner leksykalny . Tutaj obejmują one + * i int dla dowolnej stałej całkowitej, id dla dowolnej nazwy identyfikatora oraz eof dla końca pliku wejściowego. Gramatyka nie dba o to, jakie int lub id pisownia jest, ani nie dba o spacje lub podziały wierszy. Gramatyka używa tych symboli końcowych, ale ich nie definiuje. Są to zawsze węzły liści (na dolnym krzaczastym końcu) drzewa analizy.

Terminy pisane wielką literą, takie jak sumy, są symbolami nieterminalnymi . Są to nazwy pojęć lub wzorców w języku. Są one zdefiniowane w gramatyce i nigdy same nie występują w strumieniu wejściowym. Są to zawsze wewnętrzne węzły (powyżej dołu) drzewa analizy. Dzieje się tak tylko w wyniku zastosowania przez parser pewnych reguł gramatycznych. Niektóre nieterminale są zdefiniowane za pomocą dwóch lub więcej reguł; to są alternatywne wzorce. Reguły mogą odnosić się do siebie, co nazywa się rekurencyjnymi . Ta gramatyka wykorzystuje reguły rekurencyjne do obsługi powtarzających się operatorów matematycznych. Gramatyki dla pełnych języków wykorzystują reguły rekurencyjne do obsługi list, wyrażeń w nawiasach i instrukcji zagnieżdżonych.

Dowolny język komputerowy można opisać za pomocą kilku różnych gramatyk. Parser LR(1) może obsłużyć wiele, ale nie wszystkie popularne gramatyki. Zwykle możliwe jest ręczne zmodyfikowanie gramatyki, tak aby pasowała do ograniczeń parsowania LR(1) i narzędzia generatora.

Gramatyka parsera LR sama w sobie musi być jednoznaczna lub musi być uzupełniona rozstrzygającymi regułami pierwszeństwa. Oznacza to, że istnieje tylko jeden poprawny sposób zastosowania gramatyki do danego prawniczego przykładu języka, co skutkuje unikalnym drzewem analizy z tylko jednym znaczeniem i unikalną sekwencją działań przesuwania/zmniejszania dla tego przykładu. Analiza LR nie jest użyteczną techniką w przypadku języków ludzkich z niejednoznaczną gramatyką, która zależy od wzajemnego oddziaływania słów. Języki ludzkie są lepiej obsługiwane przez parsery, takie jak uogólniony parser LR , parser Earleya lub algorytm CYK który może jednocześnie obliczyć wszystkie możliwe drzewa analizy w jednym przebiegu.

Przeanalizuj tabelę przykładowej gramatyki

Większość parserów LR jest sterowana tabelami. Kod programu parsera jest prostą ogólną pętlą, która jest taka sama dla wszystkich gramatyk i języków. Znajomość gramatyki i jej implikacji składniowych jest zakodowana w niezmiennych tablicach danych zwanych tablicami analizy (lub tablicami analizy ). Wpisy w tabeli pokazują, czy przesunąć, czy zredukować (i według jakiej reguły gramatycznej) dla każdej legalnej kombinacji stanu parsera i symbolu wyprzedzającego. Tabele parsowania informują również, jak obliczyć następny stan, biorąc pod uwagę tylko bieżący stan i następny symbol.

Tabele analizy są znacznie większe niż gramatyka. Tabele LR są trudne do dokładnego obliczenia ręcznego dla dużych gramatyk. Są więc mechanicznie wyprowadzane z gramatyki przez jakieś narzędzie do generowania parserów, takie jak Bison .

W zależności od sposobu generowania stanów i tabeli analiz wynikowy parser jest nazywany parserem SLR (simple LR) , parserem LALR (ang. look-ahead LR) lub kanonicznym parserem LR . Parsery LALR obsługują więcej gramatyk niż parsery SLR. Kanoniczne parsery LR obsługują jeszcze więcej gramatyk, ale używają znacznie większej liczby stanów i znacznie większych tabel. Przykładowa gramatyka to SLR.

Tabele analizy LR są dwuwymiarowe. Każdy bieżący stan parsera LR(0) ma swój własny wiersz. Każdy możliwy następny symbol ma swoją własną kolumnę. Niektóre kombinacje stanu i następnego symbolu nie są możliwe dla prawidłowych strumieni wejściowych. Te puste komórki wyzwalają komunikaty o błędach składniowych.

Lewa połowa tabeli akcji zawiera kolumny dla symboli terminali z wyprzedzeniem. Komórki te określają, czy następną akcją parsera jest przesunięcie (do stanu n ), czy zmniejszenie (zgodnie z regułą gramatyczną r n ).

Prawa połowa tabeli Goto zawiera kolumny dla symboli nieterminalnych . Te komórki pokazują, do którego stanu należy przejść po tym, jak lewa strona pewnej redukcji utworzyła oczekiwaną nową instancję tego symbolu. To jest jak akcja przesunięcia, ale dla nieterminali; symbol terminala z wyprzedzeniem pozostaje niezmieniony.

Kolumna tabeli „Current Rules” dokumentuje znaczenie i możliwości składniowe dla każdego stanu, opracowane przez generator parsera. Nie jest uwzględniony w rzeczywistych tabelach używanych w czasie analizowania. Znacznik • (różowa kropka) pokazuje, gdzie obecnie znajduje się parser, w ramach niektórych częściowo uznanych reguł gramatycznych. Rzeczy po lewej • zostały przeanalizowane, a rzeczy po prawej są spodziewane wkrótce. Stan ma kilka takich bieżących reguł, jeśli parser nie zawęził jeszcze możliwości do jednej reguły.

bież Patrz przed siebie LHS Goto
Państwo Aktualne zasady int ID * + eof sumy Produkty Wartość
0 Cel → • Sumy eof 8 9 1 4 7
1
Cel → Sumy • eof Sum → Sumy • + Produkty
2		 zrobione
 
2 Sumy → Sumy + • Produkty 8 9 3 7
3
Sumy → Sumy + Produkty • Produkty → Produkty • * Wartość
5		 r1
 		 r1
 
4
Sumy → Produkty • Produkty → Produkty • * Wartość
5		 r2
 		 r2
 
5 Produkty → Produkty * • Wartość 8 9 6
6 Produkty → Produkty * Wartość • r3 r3 r3
7 Produkty → Wartość • r4 r4 r4
8 wartość → int • r5 r5 r5
9 Wartość → identyfikator • r6 r6 r6

W stanie 2 powyżej parser właśnie znalazł i przesunął znak + reguły gramatycznej

r1: Sumy → Sumy + • Produkty

Następna oczekiwana fraza to Produkty. Produkty zaczynają się od symboli terminali int lub id . Jeśli lookahead jest jednym z nich, parser przesuwa je i przechodzi odpowiednio do stanu 8 lub 9. Po znalezieniu produktów parser przechodzi do stanu 3, aby zgromadzić pełną listę sum i znaleźć koniec reguły r0. Produkty mogą również zaczynać się od wartości nieterminalnej. Dla każdego innego lookahead lub nieterminala parser ogłasza błąd składniowy.

W stanie 3 parser właśnie znalazł frazę Products, która może pochodzić z dwóch możliwych reguł gramatycznych:

r1: Sumy → Sumy + Produkty •
r3: Produkty → Produkty • * Wartość

Wyboru między r1 a r3 nie można podjąć, patrząc wstecz na poprzednie frazy. Parser musi sprawdzić symbol wyprzedzający, aby powiedzieć, co robić. Jeśli uprzedzenie to * , to jest w regule 3, więc parser przesuwa się w * i przechodzi do stanu 5. Jeśli uprzedzenie to eof , to jest na końcu reguły 1 i reguły 0, więc parser jest skończony.

W stanie 9 powyżej, wszystkie niepuste komórki, które nie zawierają błędów, dotyczą tej samej redukcji r6. Niektóre parsery oszczędzają czas i miejsce w tabelach, nie sprawdzając symbolu wyprzedzającego w tych prostych przypadkach. Błędy składniowe są następnie wykrywane nieco później, po kilku nieszkodliwych redukcjach, ale wciąż przed następną akcją zmiany lub decyzją parsera.

Poszczególne komórki tabeli nie mogą zawierać wielu alternatywnych działań, w przeciwnym razie parser byłby niedeterministyczny ze zgadywaniem i śledzeniem wstecznym. Jeśli gramatyka nie jest LR(1), niektóre komórki będą miały konflikty przesunięcia/zmniejszenia między możliwą akcją przesunięcia a akcją redukcji lub zredukują/zredukują konflikty między wieloma regułami gramatycznymi. Parsery LR(k) rozwiązują te konflikty (tam, gdzie to możliwe), sprawdzając dodatkowe symbole uprzedzające poza pierwszym.

Pętla parsera LR

Parser LR rozpoczyna się od prawie pustego stosu analizy składni zawierającego tylko stan początkowy 0 oraz z podglądem przechowującym pierwszy zeskanowany symbol strumienia wejściowego. Parser następnie powtarza następujący krok pętli, aż do zakończenia lub utknięcia na błędzie składniowym:

Najwyższym stanem na stosie analizowania jest jakiś stan s , a bieżącym podglądem jest jakiś symbol terminala t . Wyszukaj następną akcję parsera z wiersza s i kolumny t tabeli akcji wyprzedzającej. Tą czynnością jest przesunięcie, zmniejszenie, wykonanie lub błąd:

  • Shift n :
Przesuń dopasowany terminal t na stos analizy i zeskanuj następny symbol wejściowy do bufora wyprzedzającego.
Przenieś następny stan n na stos analizy jako nowy bieżący stan.
  • Zmniejsz r m : Zastosuj regułę gramatyczną r m : Lhs → S 1 S 2 ... S L
Usuń dopasowane symbole L znajdujące się najwyżej (i przeanalizuj drzewa i powiązane numery stanów) ze stosu analizy.
Ujawnia to wcześniejszy stan p , który oczekiwał instancji symbolu Lhs.
Połącz drzewa analizy L razem jako jedno drzewo analizy z nowym symbolem korzenia Lhs.
Wyszukaj następny stan n z wiersza p i kolumny Lhs tabeli LHS Goto.
Umieść symbol i drzewo dla Lhs na stosie analizy.
Przenieś następny stan n na stos analizy jako nowy bieżący stan.
Wyprzedzanie i strumień wejściowy pozostają niezmienione.
  • Gotowe: Lookahead t to znacznik eof . Koniec parsowania. Jeśli stos stanu zawiera tylko sukces raportu o stanie początkowym. W przeciwnym razie zgłoś błąd składni.
  • Błąd: Zgłoś błąd składni. Analizator składni kończy działanie lub podejmuje próbę odzyskania.

Stos parsera LR zwykle przechowuje tylko stany automatu LR(0), ponieważ można z nich wyprowadzić symbole gramatyczne (w automacie wszystkie przejścia wejściowe do jakiegoś stanu są oznaczone tym samym symbolem, który jest symbolem związanym z tym stanem) . Co więcej, te symbole prawie nigdy nie są potrzebne, ponieważ stan jest wszystkim, co ma znaczenie przy podejmowaniu decyzji analizowania.

Analiza generatora LR

Ta część artykułu może zostać pominięta przez większość użytkowników generatorów parserów LR.

stany LR

Stan 2 w przykładowej tabeli analizy dotyczy częściowo przetworzonej reguły

r1: Sumy → Sumy + • Produkty

To pokazuje, jak parser się tu dostał, widząc sumy, a następnie + , szukając większych sum. • Znacznik przesunął się poza początek reguły. Pokazuje również, w jaki sposób analizator składni spodziewa się ostatecznie uzupełnić regułę, znajdując następnie kompletne Produkty. Potrzebnych jest jednak więcej szczegółów na temat analizowania wszystkich części tych produktów.

Częściowo przeanalizowane reguły dla stanu nazywane są jego „podstawowymi elementami LR (0)”. Generator parsera dodaje dodatkowe reguły lub elementy dla wszystkich możliwych kolejnych kroków w tworzeniu oczekiwanych Produktów:

r3: Produkty → • Produkty * Wartość
r4: Produkty → • Wartość
r5: Wartość → • int
r6: Wartość → • id

Znacznik • znajduje się na początku każdej z dodanych zasad; parser jeszcze nie potwierdził i nie przeanalizował żadnej ich części. Te dodatkowe elementy nazywane są „zamknięciem” podstawowych elementów. Dla każdego nieterminalnego symbolu następującego bezpośrednio po • generator dodaje reguły definiujące ten symbol. Dodaje to więcej • znaczników i prawdopodobnie różnych symboli zwolenników. Ten proces zamykania jest kontynuowany, dopóki wszystkie symbole popychacza nie zostaną rozwinięte. Nieterminale obserwujące dla stanu 2 zaczynają się od produktów. Wartość jest następnie dodawana przez zamknięcie. Terminale podążające to int i identyfikator .

Pozycje jądra i zamknięcia razem pokazują wszystkie możliwe legalne sposoby przejścia od obecnego stanu do przyszłych stanów i pełne frazy. Jeśli symbol towarzysza pojawia się tylko w jednym elemencie, prowadzi on do następnego stanu zawierającego tylko jeden przedmiot podstawowy z przesuniętym • znacznikiem . Więc int prowadzi do następnego stanu 8 z rdzeniem

r5: Wartość → int •

Jeśli ten sam symbol obserwującego pojawia się w kilku elementach, parser nie może jeszcze stwierdzić, która reguła ma tutaj zastosowanie. Zatem ten symbol prowadzi do następnego stanu, który pokazuje wszystkie pozostałe możliwości, ponownie z • znacznikiem. Produkty pojawiają się zarówno w r1, jak i r3. Produkty prowadzą więc do następnego stanu 3 z rdzeniem

r1: Sumy → Sumy + Produkty •
r3: Produkty → Produkty • * Wartość

Innymi słowy, oznacza to, że jeśli parser widział pojedynczy produkt, może to zrobić lub może jeszcze mieć jeszcze więcej rzeczy do pomnożenia razem. Wszystkie podstawowe przedmioty mają ten sam symbol przed • znacznikiem; wszystkie przejścia do tego stanu są zawsze z tym samym symbolem.

Niektóre przejścia będą dotyczyć rdzeni i stanów, które zostały już wyliczone. Inne przejścia prowadzą do nowych stanów. Generator zaczyna się od reguły celu gramatyki. Stamtąd kontynuuje eksplorację znanych stanów i przejść, aż wszystkie potrzebne stany zostaną znalezione.

Stany te nazywane są stanami „LR(0)”, ponieważ używają wyprzedzania k = 0, tj. bez wyprzedzania. Jedyne sprawdzanie symboli wejściowych ma miejsce, gdy symbol jest przesunięty. Sprawdzanie wyprzedzających redukcji jest wykonywane oddzielnie przez tablicę analizy składniowej, a nie przez same wyliczone stany.

Maszyna stanów skończonych

Tabela parsowania opisuje wszystkie możliwe stany LR(0) i ich przejścia. Tworzą skończoną maszynę stanów (FSM). FSM to prosty silnik do analizowania prostych niezagnieżdżonych języków bez użycia stosu. W tej aplikacji LR zmodyfikowany „język wejściowy” FSM ma zarówno symbole terminalne, jak i nieterminalne i obejmuje każdą częściowo przeanalizowaną migawkę stosu pełnej analizy LR.

Przypomnij sobie krok 5 przykładu kroków analizy:


Krok
Stan stosu Stan symbolu ...
Spójrz przed siebie
Nieprzeskanowane
5

0 Produkty 4 * 5 wew 8

+ 1

Stos analizy przedstawia serię przejść stanu, od stanu początkowego 0 do stanu 4, a następnie do stanu 5 i bieżącego stanu 8. Symbole na stosie analizy to symbole przesunięcia lub goto dla tych przejść. Innym sposobem, aby to zobaczyć, jest to, że skończona maszyna stanów może przeskanować strumień „Produkty * int + 1” (bez użycia kolejnego stosu) i znaleźć skrajną lewą kompletną frazę, która powinna zostać zmniejszona jako następna. I to jest rzeczywiście jego praca!

Jak zwykły FSM może to zrobić, gdy oryginalny nieprzeanalizowany język ma zagnieżdżanie i rekurencję i zdecydowanie wymaga analizatora ze stosem? Sztuczka polega na tym, że wszystko na lewo od szczytu stosu zostało już całkowicie zmniejszone. Eliminuje to wszystkie pętle i zagnieżdżenia z tych fraz. FSM może ignorować wszystkie starsze początki fraz i śledzić tylko najnowsze frazy, które mogą zostać dokończone jako następne. Niejasna nazwa tego w teorii LR to „żywy przedrostek”.

Zestawy z wyprzedzeniem

Stany i przejścia dostarczają wszystkich potrzebnych informacji dla akcji shift i goto tabeli analizy składniowej. Generator musi również obliczyć oczekiwane zestawy wyprzedzające dla każdej akcji redukcji.

W parserach SLR te zestawy wyprzedzające są określane bezpośrednio z gramatyki, bez uwzględniania poszczególnych stanów i przejść. Dla każdego nieterminalnego S generator SLR opracowuje Follows(S), zbiór wszystkich symboli końcowych, które mogą bezpośrednio następować po jakimś wystąpieniu S. W tabeli analizy składniowej każda redukcja do S używa Follow(S) jako swojego LR(1 ) zestaw z wyprzedzeniem. Takie zestawy follow są również używane przez generatory dla parserów LL top-down. Gramatyka, która nie ma konfliktów przesunięcia/zmniejszenia lub redukcji/zmniejszenia podczas używania zestawów podążania, nazywana jest gramatyką SLR.

LALR mają te same stany, co parsery SLR, ale używają bardziej skomplikowanego, bardziej precyzyjnego sposobu wypracowania minimalnej niezbędnej redukcji wyprzedzającej dla każdego indywidualnego stanu. W zależności od szczegółów gramatyki może się okazać, że jest to to samo, co zestaw Follow obliczony przez generatory parsera SLR lub może się okazać, że jest to podzbiór lookaheadów SLR. Niektóre gramatyki są w porządku dla generatorów parsera LALR, ale nie dla generatorów parsera SLR. Dzieje się tak, gdy gramatyka ma fałszywe konflikty przesunięcia/zmniejszenia lub redukcji/zmniejszenia przy użyciu zestawów Follow, ale nie ma konfliktów przy użyciu dokładnych zestawów obliczonych przez generator LALR. Gramatyka nazywa się wówczas LALR(1), ale nie SLR.

Parser SLR lub LALR pozwala uniknąć zduplikowanych stanów. Ale ta minimalizacja nie jest konieczna i czasami może powodować niepotrzebne konflikty wyprzedzające. Kanoniczny LR parsery używają zduplikowanych (lub „podzielonych”) stanów, aby lepiej zapamiętać lewy i prawy kontekst użycia nieterminala. Każde wystąpienie symbolu S w gramatyce można traktować niezależnie za pomocą własnego zestawu wyprzedzającego, aby pomóc w rozwiązywaniu konfliktów redukcji. To obsługuje kilka dodatkowych gramatyk. Niestety, znacznie powiększa to rozmiar tabel analizy, jeśli jest wykonywane dla wszystkich części gramatyki. Ten podział stanów można również wykonać ręcznie i wybiórczo za pomocą dowolnego parsera SLR lub LALR, tworząc dwie lub więcej nazwanych kopii niektórych nieterminali. Gramatyka, która jest wolna od konfliktów dla kanonicznego generatora LR, ale ma konflikty w generatorze LALR, nazywa się LR (1), ale nie LALR (1), a nie SLR.

Parsery SLR, LALR i kanoniczne LR dokonują dokładnie tego samego przesunięcia i ograniczają decyzje, gdy strumień wejściowy jest poprawnym językiem. Gdy dane wejściowe mają błąd składniowy, parser LALR może wykonać dodatkowe (nieszkodliwe) redukcje przed wykryciem błędu, niż zrobiłby to kanoniczny parser LR. A parser SLR może zrobić jeszcze więcej. Dzieje się tak, ponieważ parsery SLR i LALR używają hojnego przybliżenia nadzbioru do prawdziwych, minimalnych symboli wyprzedzających dla tego konkretnego stanu.

Odzyskiwanie błędów składniowych

Parsery LR mogą generować nieco pomocne komunikaty o błędach dla pierwszego błędu składniowego w programie, po prostu wyliczając wszystkie symbole terminali, które mogły pojawić się jako następne, zamiast nieoczekiwanego złego symbolu wyprzedzającego. Ale to nie pomaga parserowi w ustaleniu, jak przeanalizować pozostałą część programu wejściowego, aby szukać dalszych, niezależnych błędów. Jeśli parser źle naprawi pierwszy błąd, jest bardzo prawdopodobne, że źle przeanalizuje wszystko inne i wygeneruje kaskadę nieprzydatnych, fałszywych komunikatów o błędach.

W generatorach parsera yacc i bison parser ma mechanizm ad hoc, który pozwala porzucić bieżącą instrukcję, odrzucić niektóre przeanalizowane frazy i tokeny wyprzedzające otaczające błąd i ponownie zsynchronizować analizę w pewnym niezawodnym ograniczniku na poziomie instrukcji, takim jak średniki lub nawiasy klamrowe. Często działa to dobrze, umożliwiając parserowi i kompilatorowi przejrzenie reszty programu.

Wiele błędów w kodowaniu składniowym to zwykłe literówki lub pominięcia trywialnego symbolu. Niektóre parsery LR próbują wykryć i automatycznie naprawić te typowe przypadki. Parser wylicza każde możliwe wstawienie, usunięcie lub podstawienie pojedynczego symbolu w punkcie błędu. Kompilator przeprowadza próbną analizę każdej zmiany, aby sprawdzić, czy wszystko działa poprawnie. (Wymaga to cofnięcia się do migawek stosu analizy i strumienia wejściowego, które zwykle nie są potrzebne parserowi). Wybierana jest najlepsza naprawa. Daje to bardzo pomocny komunikat o błędzie i ponownie synchronizuje analizę. Jednak naprawa nie jest wystarczająco wiarygodna, aby trwale zmodyfikować plik wejściowy. Naprawa błędów składniowych jest najłatwiejsza do spójnego wykonania w parserach (takich jak LR), które mają tabele analizy i jawny stos danych.

Warianty parserów LR

Generator parsera LR decyduje, co powinno się stać dla każdej kombinacji stanu parsera i symbolu wyprzedzającego. Decyzje te są zwykle przekształcane w tabele danych tylko do odczytu, które sterują ogólną pętlą parsera, która jest niezależna od gramatyki i stanu. Ale są też inne sposoby przekształcenia tych decyzji w aktywny parser.

Niektóre generatory parserów LR tworzą osobny dostosowany kod programu dla każdego stanu zamiast tabeli analizy. Te parsery mogą działać kilka razy szybciej niż ogólna pętla parsera w parserach sterowanych tabelami. Najszybsze parsery wykorzystują wygenerowany kod asemblera.

W rekurencyjnej odmianie parsera wynurzania jawna struktura stosu analizy jest również zastępowana niejawnym stosem używanym przez wywołania podprogramu. Redukcje kończą kilka poziomów wywołań podprogramów, co jest niezgrabne w większości języków. Tak więc rekurencyjne parsery wznoszenia są generalnie wolniejsze, mniej oczywiste i trudniejsze do ręcznej modyfikacji niż rekurencyjne parsery zejścia .

Inna odmiana zastępuje tabelę analizy regułami dopasowywania wzorców w językach innych niż proceduralne, takich jak Prolog .

GLR Uogólnione parsery LR wykorzystują techniki oddolne LR, aby znaleźć wszystkie możliwe analizy tekstu wejściowego, a nie tylko jedną poprawną analizę. Jest to niezbędne w przypadku gramatyki niejednoznacznej, takiej jak używana w językach ludzkich. Wiele ważnych drzew analizy jest obliczanych jednocześnie, bez cofania się. GLR jest czasami pomocny w przypadku języków komputerowych, których nie da się łatwo opisać bezkonfliktową gramatyką LALR(1).

Parsery lewego rogu LC wykorzystują techniki oddolne LR do rozpoznawania lewego końca alternatywnych reguł gramatycznych. Gdy alternatywy zostaną zawężone do jednej możliwej reguły, parser przełącza się na odgórne techniki LL(1) w celu przeanalizowania reszty tej reguły. Parsery LC mają mniejsze tabele analizy niż parsery LALR i lepszą diagnostykę błędów. Nie ma powszechnie używanych generatorów dla deterministycznych parserów LC. Parsery LC z wieloma analizami są pomocne w przypadku języków ludzkich z bardzo dużą gramatyką.

Teoria

Parsery LR zostały wynalezione przez Donalda Knutha w 1965 jako wydajne uogólnienie parserów pierwszeństwa . Knuth udowodnił, że parsery LR były najbardziej uniwersalnymi parserami, które byłyby nadal wydajne w najgorszych przypadkach. [ potrzebne źródło ]

„Gramatyka LR( k ) może być wydajnie analizowana z czasem wykonania zasadniczo proporcjonalnym do długości łańcucha”.
Dla każdego k ≥1 „język może zostać wygenerowany przez gramatykę LR ( k ) wtedy i tylko wtedy, gdy jest deterministyczny [i bezkontekstowy], wtedy i tylko wtedy, gdy może być wygenerowany przez gramatykę LR (1)”.

Innymi słowy, jeśli język byłby wystarczająco rozsądny, aby umożliwić wydajny jednoprzebiegowy parser, można by go opisać gramatyką LR( k ). I ta gramatyka zawsze może być mechanicznie przekształcona w równoważną (ale większą) gramatykę LR(1). Tak więc metoda parsowania LR(1) była teoretycznie wystarczająco potężna, aby obsłużyć każdy rozsądny język. W praktyce gramatyka naturalna dla wielu języków programowania jest zbliżona do LR(1). [ potrzebne źródło ]

Kanoniczne parsery LR opisane przez Knutha miały zbyt wiele stanów i bardzo duże tablice analizy, które były niepraktycznie duże dla ograniczonej pamięci komputerów tamtej epoki. Parsowanie LR stało się praktyczne, gdy Frank DeRemer wynalazł parsery SLR i LALR ze znacznie mniejszą liczbą stanów.

Aby uzyskać szczegółowe informacje na temat teorii LR i sposobu, w jaki parsery LR są wyprowadzane z gramatyk, zobacz The Theory of Parsing, Translation, and Compiling, Volume 1 (Aho and Ullman).

Parsery Earleya stosują techniki i • notację parserów LR do zadania generowania wszystkich możliwych analiz składniowych dla niejednoznacznych gramatyk, takich jak języki ludzkie.

Podczas gdy gramatyki LR( k ) mają taką samą moc generatywną dla wszystkich k ≥1, przypadek gramatyk LR(0) jest nieco inny. Mówimy, że język L ma właściwość prefix , jeśli żadne słowo w L nie jest właściwym przedrostkiem innego słowa w L . Język L ma gramatykę LR(0) wtedy i tylko wtedy, gdy L jest deterministycznym językiem bezkontekstowym z właściwością prefiksu. W konsekwencji język L jest deterministyczny bezkontekstowy wtedy i tylko wtedy, gdy L $ ma gramatykę LR ( 0), gdzie „ $” nie jest symbolem alfabetu L.

Dodatkowy przykład 1+1

Analiza oddolna 1+1

Ten przykład analizowania LR wykorzystuje następującą małą gramatykę z symbolem celu E:

(1) mi → mi * b
(2) mi → mi + b
(3) mi → b
(4) b → 0
(5) b → 1

aby przeanalizować następujące dane wejściowe:

1 + 1

Tabele akcji i goto

Dwie tablice analizujące LR(0) dla tej gramatyki wyglądają następująco:

państwo działanie iść do
  * + 0 1 $ mi B
0     s1 s2   3 4
1 r4 r4 r4 r4 r4    
2 r5 r5 r5 r5 r5    
3 s5 s6     wg    
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    

Tablica akcji jest indeksowana przez stan parsera i terminala (w tym specjalny terminal $ wskazujący koniec strumienia wejściowego) i zawiera trzy typy akcji:

  • shift , które jest zapisywane jako ' n ' i wskazuje, że następnym stanem jest n
  • reduce , które jest zapisywane jako 'r m ' i wskazuje, że należy przeprowadzić redukcję z regułą gramatyczną m
  • accept , który jest zapisywany jako „acc” i wskazuje, że parser akceptuje ciąg znaków w strumieniu wejściowym.

Tabela goto jest indeksowana przez stan parsera i nieterminala i po prostu wskazuje, jaki będzie następny stan parsera, jeśli rozpozna on określony nieterminal. Ta tabela jest ważna, aby znaleźć następny stan po każdej redukcji. Po redukcji, następny stan jest znajdowany przez wyszukanie tablicy goto dla szczytu stosu (tj. bieżącego stanu) i LHS zredukowanej reguły (tj. nieterminalnej).

Etapy analizowania

Poniższa tabela ilustruje każdy etap procesu. Tutaj stan odnosi się do elementu na górze stosu (element najbardziej na prawo), a następna akcja jest określana na podstawie powyższej tabeli akcji. Znak $ jest dołączany do łańcucha wejściowego w celu oznaczenia końca strumienia.

Państwo Strumień wejściowy Strumień wyjściowy Stos Następna akcja
0 1+1$ [0] Zmiana 2
2 +1 $ [0,2] Zmniejsz 5
4 +1 $ 5 [0,4] Zmniejsz 3
3 +1 $ 5,3 [0,3] Zmiana 6
6 1 $ 5,3 [0,3,6] Zmiana 2
2 $ 5,3 [0,3,6,2] Zmniejsz 5
8 $ 5,3,5 [0,3,6,8] Zmniejsz 2
3 $ 5,3,5,2 [0,3] Zaakceptować

Opis przejścia

Parser zaczyna od stosu zawierającego tylko stan początkowy („0”):

0 [ ]

Pierwszym symbolem z ciągu wejściowego, który widzi parser, jest „1”. Aby znaleźć następną akcję (przesunięcie, zmniejszenie, akceptację lub błąd), tabela akcji jest indeksowana z bieżącym stanem („bieżący stan” to po prostu wszystko, co znajduje się na szczycie stosu), który w tym przypadku wynosi 0, oraz bieżący symbol wejścia, którym jest „1”. Tabela akcji określa przejście do stanu 2, więc stan 2 jest umieszczany na stosie (ponownie, wszystkie informacje o stanie znajdują się na stosie, więc „przejście do stanu 2” jest tym samym, co umieszczanie 2 na stosie). Wynikowy stos to

0 [ '1' 2 ]

gdzie wierzchołek stosu to 2. Dla wyjaśnienia symbolu (np. „1”, B) pokazano, który spowodował przejście do następnego stanu, chociaż ściśle mówiąc nie jest on częścią stosu.

W stanie 2 tabela akcji mówi, aby zmniejszyć z regułą gramatyczną 5 (niezależnie od tego, jaki terminal parser widzi w strumieniu wejściowym), co oznacza, że ​​parser właśnie rozpoznał prawą stronę reguły 5. W tym przypadku parser zapisuje 5 do strumienia wyjściowego, zdejmuje jeden stan ze stosu (ponieważ prawa strona reguły ma jeden symbol) i umieszcza na stosie stan z komórki w tablicy goto dla stanu 0 i B, tj. , stan 4. Wynikowy stos to:

0 [ 4 ] _

Jednak w stanie 4 tabela akcji mówi, że parser powinien teraz redukować zgodnie z regułą 3. Zapisuje więc 3 do strumienia wyjściowego, zdejmuje jeden stan ze stosu i znajduje nowy stan w tablicy goto dla stanu 0 i E, czyli stan 3. Wynikowy stos:

0 [ E 3 ]

Następny terminal, który widzi parser, to „+” i zgodnie z tabelą akcji powinien przejść do stanu 6:

0 [ mi 3 '+' 6 ]

Wynikowy stos można interpretować jako historię automatu skończonego , który właśnie odczytał nieterminal E, po którym następuje terminal „+”. Tablica przejść tego automatu jest zdefiniowana przez akcje shift w tablicy akcji i akcje goto w tablicy goto.

Następnym terminalem jest teraz „1”, co oznacza, że ​​parser wykonuje przesunięcie i przechodzi do stanu 2:

0 [ mi 3 '+' 6 '1' 2 ]

Podobnie jak poprzednia „1”, ta jest zredukowana do B, dając następujący stos:

0 [ mi 3 '+' 6 b 8 ]

Stos odpowiada liście stanów automatu skończonego, który odczytał nieterminalne E, po którym następuje „+”, a następnie nieterminalne B. W stanie 8 parser zawsze wykonuje redukcję zgodnie z regułą 2. Trzy najwyższe stany na stos odpowiada 3 symbolom po prawej stronie reguły 2. Tym razem zdejmujemy 3 elementy ze stosu (ponieważ prawa strona reguły ma 3 symbole) i szukamy stanu goto dla E i 0 , w ten sposób wypychając stan 3 z powrotem na stos

0 [ E 3 ]

Na koniec parser odczytuje znak „$” (symbol końca wejścia) ze strumienia wejściowego, co oznacza, że ​​zgodnie z tabelą akcji (aktualny stan to 3) parser akceptuje ciąg wejściowy. Numery reguł, które zostaną następnie zapisane w strumieniu wyjściowym, będą miały postać [5, 3, 5, 2], co jest rzeczywiście najbardziej wysuniętym na prawo pochodną łańcucha „1 + 1” w odwrotnej kolejności.

Konstruowanie tablic parsowania LR(0).

Rzeczy

Konstrukcja tych tablic parsowania opiera się na pojęciu elementów LR(0) (zwanych tutaj po prostu elementami ), które są regułami gramatycznymi ze specjalną kropką dodaną gdzieś po prawej stronie. Na przykład reguła E → E + B ma następujące cztery odpowiadające sobie elementy:

mi → • mi + b
mi → mi • + be
mi → mi + • b
mi → mi + b •

Reguły postaci A → ε mają tylko jeden element A → • . Na przykład element E → E • + B wskazuje, że parser rozpoznał ciąg znaków odpowiadający E w strumieniu wejściowym i teraz oczekuje na odczytanie „+”, po którym następuje inny ciąg znaków odpowiadający B.

Zestawy przedmiotów

Zwykle nie jest możliwe scharakteryzowanie stanu parsera za pomocą pojedynczego elementu, ponieważ może on z góry nie wiedzieć, której reguły użyje do redukcji. Na przykład, jeśli istnieje również reguła E → E * B, to pozycje E → E • + B i E → E • * B będą miały zastosowanie po odczytaniu łańcucha odpowiadającego E. Dlatego wygodnie jest scharakteryzować stan parsera za pomocą zbioru elementów, w tym przypadku zbioru { E → E • + B, E → E • * B }.

Rozszerzenie zestawu przedmiotów o rozszerzenie nieterminali

Pozycja z kropką przed nieterminalem, taka jak E → E + • B, wskazuje, że parser spodziewa się przeanalizować nieterminal B jako następny. Aby mieć pewność, że zestaw elementów zawiera wszystkie możliwe reguły, które parser może analizować, musi on zawierać wszystkie elementy opisujące, w jaki sposób samo B będzie analizowane. Oznacza to, że jeśli istnieją reguły takie jak B → 1 i B → 0, to zestaw pozycji musi również zawierać pozycje B → • 1 i B → • 0. Ogólnie można to sformułować w następujący sposób:

Jeżeli w zbiorze przedmiotów znajduje się element postaci A → v • Bw , aw gramatyce istnieje reguła postaci B → w' , to element B → • w' również powinien znajdować się w zbiorze elementów.

Zamknięcie zestawów przedmiotów

W ten sposób dowolny zestaw elementów można rozszerzyć, rekurencyjnie dodając wszystkie odpowiednie elementy, aż zostaną uwzględnione wszystkie nieterminale poprzedzone kropkami. Minimalne rozszerzenie jest nazywane domknięciem zbioru przedmiotów i zapisywane jako clos ( I ), gdzie I jest zbiorem przedmiotów. To właśnie te zamknięte zestawy pozycji są traktowane jako stany parsera, chociaż tylko te, które są rzeczywiście osiągalne ze stanu początkowego, zostaną uwzględnione w tabelach.

Gramatyka rozszerzona

Zanim zostaną określone przejścia między różnymi stanami, gramatyka jest wzbogacona o dodatkową regułę

(0) S → E eof

gdzie S jest nowym symbolem startu, a E starym symbolem startu. Parser użyje tej reguły do ​​redukcji dokładnie wtedy, gdy zaakceptuje cały ciąg wejściowy.

W tym przykładzie ta sama gramatyka, co powyżej, została rozszerzona w następujący sposób:

(0) S → mi eof
(1) mi → mi * b
(2) mi → mi + b
(3) mi → b
(4) b → 0
(5) b → 1

To dla tej rozszerzonej gramatyki zostaną określone zestawy przedmiotów i przejścia między nimi.

Konstrukcja stołu

Znajdowanie osiągalnych zestawów przedmiotów i przejść między nimi

Pierwszym krokiem konstruowania tabel jest wyznaczenie przejść między zamkniętymi zbiorami pozycji. Te przejścia zostaną określone tak, jakbyśmy rozważali automat skończony, który może czytać zarówno terminale, jak i nieterminale. Stanem początkowym tego automatu jest zawsze zamknięcie pierwszego elementu dodawanej reguły: S → • E:

Zestaw pozycji 0
S → • E eof
+ E → • E * B
+ E → • E + B
+ E → • B
+ B → • 0
+ B → • 1

Pogrubiony znak „ + ” przed elementem wskazuje elementy, które zostały dodane do zamknięcia (nie mylić z matematycznym operatorem „+”, który jest terminalem). Oryginalne elementy bez znaku „ + ” nazywane są jądrem zestawu przedmiotów.

Począwszy od stanu początkowego (S0), wszystkie stany, które można osiągnąć z tego stanu, są teraz określone. Możliwe przejścia dla zestawu elementów można znaleźć, patrząc na symbole (terminale i nieterminale) znajdujące się po kropkach; w przypadku zestawu pozycji 0 tymi symbolami są terminale „0” i „1” oraz nieterminale E i B. Aby znaleźć zestaw pozycji, który każdy symbol prowadzi do następującej procedury dla każdego z symboli:

  1. Weźmy podzbiór, S , wszystkich elementów w bieżącym zestawie, w którym przed interesującym nas symbolem, x , znajduje się kropka .
  2. Dla każdego elementu w S przesuń kropkę na prawo od x .
  3. Zamknij wynikowy zestaw elementów.

Dla terminala „0” (tj. gdzie x = „0”) daje to:

Zestaw przedmiotów 1
B → 0 •

a dla terminala „1” (tj. gdzie x = „1”) daje to:

Zestaw przedmiotów 2
B → 1 •

a dla nieterminalnego E (tj. gdzie x = E) skutkuje to:

Zestaw pozycji 3
S → E • eof
E → E • * B
E → E • + B

a dla nieterminala B (tj. gdzie x = B) skutkuje to:

Zestaw pozycji 4
E → B •

Domknięcie nie we wszystkich przypadkach dodaje nowe elementy – na przykład w nowych zestawach powyżej nie ma nieterminali następujących po kropce.

Powyższa procedura jest kontynuowana, dopóki nie zostaną znalezione nowe zestawy przedmiotów. W przypadku zestawów przedmiotów 1, 2 i 4 nie będzie przejść, ponieważ kropka nie znajduje się przed żadnym symbolem. Jednak w przypadku zestawu przedmiotów 3 mamy kropki przed zaciskami „*” i „+”. Dla symbolu przejście przechodzi do:

Zestaw pozycji 5
E → E * • B
+ B → • 0
+ B → • 1

a dla przejście przechodzi do:

Zestaw pozycji 6
E → E + • B
+ B → • 0
+ B → • 1

Teraz rozpoczyna się trzecia iteracja.

W przypadku zestawu pozycji 5 należy wziąć pod uwagę terminale „0” i „1” oraz nieterminal B, ale wynikowe zamknięte zestawy pozycji są równe odpowiednio już znalezionym zestawom pozycji 1 i 2. Dla nieterminala B przejście prowadzi do:

Zestaw przedmiotów 7
E → E * B •

W przypadku zestawu pozycji 6 należy wziąć pod uwagę terminal „0” i „1” oraz nieterminal B, ale tak jak poprzednio, wynikowe zestawy pozycji dla terminali są równe już znalezionym zestawom pozycji 1 i 2. W przypadku nieterminala B przejście idzie do:

Zestaw pozycji 8
E → E + B •

Te ostatnie zestawy przedmiotów 7 i 8 nie mają żadnych symboli poza ich kropkami, więc nie są już dodawane nowe zestawy przedmiotów, więc procedura generowania przedmiotów jest zakończona. Automat skończony, którego stanami są zestawy przedmiotów, pokazano poniżej.

Tabela przejść dla automatu wygląda teraz następująco:

Zestaw przedmiotów * + 0 1 mi B
0     1 2 3 4
1            
2            
3 5 6        
4            
5     1 2   7
6     1 2   8
7            
8            

Konstruowanie akcji i tabel goto

Na podstawie tej tabeli i znalezionych zestawów elementów tabela akcji i goto jest tworzona w następujący sposób:

  1. Kolumny dla nieterminali są kopiowane do tabeli goto.
  2. Kolumny terminali są kopiowane do tabeli akcji jako akcje przesunięcia.
  3. Do tabeli akcji dodawana jest dodatkowa kolumna dla „$” (koniec danych wejściowych). Akcja acc jest dodawana do kolumny '$' dla każdego zestawu pozycji, który zawiera pozycję w postaci S → w • eof.
  4. Jeśli zbiór pozycji i zawiera element postaci A → w • i A → w jest regułą m dla m > 0, to wiersz dla stanu i w tabeli akcji jest całkowicie wypełniony akcją redukcji r m .

Czytelnik może zweryfikować, czy faktycznie skutkuje to przedstawioną wcześniej tabelą akcji i goto.

Uwaga na temat parsowania LR(0) kontra SLR i LALR

Tylko krok 4 powyższej procedury generuje akcje redukujące, więc wszystkie akcje redukujące muszą zajmować cały wiersz tabeli, powodując, że redukcja wystąpi niezależnie od następnego symbolu w strumieniu wejściowym. Właśnie dlatego są to tabele analizy LR(0): nie wykonują żadnego wyprzedzania (to znaczy patrzą w przód na symbole zerowe) przed podjęciem decyzji, którą redukcję wykonać. Gramatyka, która wymaga wyprzedzania w celu ujednoznacznienia redukcji, wymagałaby wiersza tabeli analizy składniowej zawierającego różne akcje redukcji w różnych kolumnach, a powyższa procedura nie jest w stanie utworzyć takich wierszy.

Udoskonalenia procedury konstruowania tabeli LR (0) (takie jak SLR i LALR ) umożliwiają konstruowanie działań redukujących, które nie zajmują całych wierszy. Dlatego są w stanie przeanalizować więcej gramatyk niż parsery LR (0).

Konflikty w skonstruowanych tablicach

Automat jest skonstruowany w taki sposób, że gwarantuje determinizm. Jednak po dodaniu akcji redukcji do tabeli akcji może się zdarzyć, że ta sama komórka zostanie wypełniona akcją redukcji i akcją przesunięcia (konflikt przesunięcie- redukcja ) lub dwoma różnymi akcjami redukcji ( konflikt redukcja-redukcja ). Można jednak wykazać, że kiedy tak się dzieje, gramatyka nie jest gramatyką LR(0). Klasycznym przykładem konfliktu przesunięcia-redukcji z rzeczywistego świata jest zwisający problem else .

Mały przykład gramatyki innej niż LR(0) z konfliktem redukcji przesunięcia to:

(1) mi → 1 mi
(2) mi → 1

Jeden ze znalezionych zestawów przedmiotów to:

Zestaw pozycji 1
P → 1 • E
E → 1 •
+ E → • 1 E
+ E → • 1

W tym zbiorze elementów występuje konflikt przesunięcia-zmniejszenia: podczas konstruowania tabeli akcji zgodnie z powyższymi regułami komórka dla [zestawu pozycji 1, terminal '1'] zawiera s1 (przejście do stanu 1) i r2 ( zmniejszenie z gramatyką zasada 2).

Mały przykład gramatyki innej niż LR(0) z konfliktem redukcji-redukcji to:

(1) mi → za 1
(2) mi → za 2
(3) za → 1
(4) za → 1

W takim przypadku uzyskuje się następujący zestaw pozycji:

Zestaw pozycji 1
A → 1 •
B → 1 •

W tym zestawie pozycji występuje konflikt redukcji-redukcji, ponieważ w komórkach tabeli akcji dla tego zestawu pozycji będzie zarówno akcja redukcji dla reguły 3, jak i jedna dla reguły 4.

Oba powyższe przykłady można rozwiązać, pozwalając parserowi użyć następującego zestawu (patrz parser LL ) nieterminala A , aby zdecydować, czy zamierza użyć jednej z reguł A s do redukcji; użyje reguły A → w do redukcji tylko wtedy, gdy następny symbol w strumieniu wejściowym znajduje się w następującym zbiorze A . Efektem tego rozwiązania są tzw. Simple LR parsery .

Zobacz też

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=LR_parser&oldid=1125561057 ”