LR analyzátor

LR analyzátor je druh analyzátoru pro kontext-uvolnit gramatiky to je velmi běžně používané počítačem programovací jazyk kompilátoři (a jiné sdružené nástroje). LR analyzátory četly jejich vstup od Left spravovat a produkovat Rightmost původ (od této doby LR, vyrovnat se LL analyzátoru). Termín “LR (k) analyzátor” je také používán; tady k se odkazuje na množství unconsumed “pohled dopředu” symboly vstupu, které jsou použity ve výrobě rozebrat rozhodnutí. Obvykle k je 1 a je často vynechán. Kontext-volná gramatika je nazývána LR (k) jestliže tam existuje LR (k) analyzátor pro to.

V typickém užívání když my se odkazujeme na LR analyzátor my znamenáme zvláštní analyzátor schopný rozpoznávat zvláštní jazyk specifikovaný kontextem uvolnit gramatiku. To není neobvyklé, nicméně, se odkazovat na LR analyzátor znamenat program řidiče, který může být zásobený vhodným stolem produkovat široké množství různých zvláštních LR analyzátorů.

LR rozebrat má mnoho výhod:

Doslova všechny programovací jazyky mohou být rozloženy používat LR analyzátor (nebo malá variace thereof).
LR analyzátory mohou být realizovány velmi efektivně.
Všech analyzátorů, které snímají jejich vstup zanechal správně, LR analyzátory objeví syntaktické chyby (to je, když jejich vstup neodpovídá gramatice) jak brzy jako to možný dělat.

LR analyzátory jdou těžko produkovat po ruce; oni jsou obvykle budováni analyzátorovým generátorem nebo kompilátor-kompilátor. Spoléhat se na jak rozebrat stůl vznikne tyto analyzátory jsou nazývány Jednoduchým LR analyzátorem (SLR v krátkosti), Pohled-dopředu LR analyzátor (LALR), a Kanonický LR analyzátor. Tyto druhy analyzátorů mohou zabývat se zvýšeně velkými soubory gramatik; LALR analyzátory mohou zabývat se více gramatikami než SLR, kanonické LR analyzátory práce na více gramatikách než LALR analyzátory. Program Yacc produkuje LALR analyzátory a je docela populární.

Tabulka s obsahem

1 architektura LR analyzátorů

1.1 akce a Goto stůl
1.2 rozebrat algoritmus
1.3 příklad

2 budovat LR (0) rozebrat stoly

2.4 položky
2.5 položka zapadne
2.6 uzavření položky zapadne
2.7 rozšířená gramatika
2.8 nacházet dostupné položkové soubory a přechody mezi nimi
2.9 budovat akci a stůl goto

2.9.1 poznámka o LR (0) proti SLR a LALR rozebrat

2.10 konflikty v postavených stolech

Architektura LR analyzátorů

Stůl-založený vzestupný analyzátor může být schématicky představován jak v čísle 1.

        + -- - + -- - + -- - + -- - + Vstup: | 1 | + | 1 | $ | + -- - + -- - + -- - + -- - + ^ | Stack: | + -- -- -- -- -- + + -- - + | | | 6 |  Výstup + -- - + | | | 3 | + -- -- -- -- -- + + -- - + | | 0 | + -- + -- -- -- -- + + -- - + | | + -- -- -- -- -- + + -- -- -- -- -- + | Akce | | Goto | | stůl | | stůl | + -- -- -- -- -- + + -- -- -- -- -- +

 Číslo 1. architektura stolu-založený vzestupný analyzátor

Analyzátor má vstupní buffer, hromada na kterém to drží seznam států to bylo v, stůl akce a goto stůl to říct to jakému novému státu to měli by pohyb nebo které mluvnické pravidlo to by mělo používat daný stát to je nyní v a terminál nebo nonterminal to jen četlo na potoku vstupu. Vysvětlit to jeho workings my budeme používat následující malou gramatiku:

(1) E a rarr; E * B

(2) E a rarr; E + B

(3) E a rarr; B

(4) B a rarr; 0

(5) B a rarr; 1

Akce a stůl Gota

Dva LR (0) rozebrat stoly pro tento pohled gramatiky takto:

	akce					goto
stát	*	+	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

Stůl akce je indexován stavem analyzátoru a terminálem (včetně terminálu speciality $ to ukáže konec potoku vstupu) a obsahuje tři druhy akcí: posun to je psáno jak ' sn ' a ukáže, že příští stát je n, se snížit to je psáno jak ' rm ' a ukáže to redukce s mluvnickým pravidlem m should být vykonáván a přijmout to to je psáno jak ' acc ' a inidcates že analyzátor přijímá řetězec v potoku vstupu.

Goto stůl je indexován stavem analyzátoru a nonterminal a jednoduše ukáže co příští stav analyzátoru bude jestliže to rozpoznalo jistý nonterminal.

Rozebrat algoritmus

LR rozebrat algoritmus nyní pracuje takto:

Hromada je inicializována s [ 0 ]. Dnešní stav bude vždy být stát, který je nahoře hromady.
Daný dnešní stav a aktuální terminál na vstupu dělí akce je vyhledána v akční tabulce. Jsou tam čtyři případy:
- posun sn :
  - aktuální terminál je odstraněn od potoku vstupu, a
  - stát n je tlačil se na hromadě a stane se současným stavem,
- se snížit rm:
  - číslo m je psán k potoku výstupu,
  - pro každý symbol v pravé straně pravidla m stát je odstraněn od hromady a
  - daný stát to je pak nahoře hromady a left-hand strana pravidla m nový stát je vyhledán v goto tabulce a dělal nový dnešní stav tím, že tlačí to na hromadě.
- přijmout to: řetězec je přijímán
- žádná akce: syntaktická chyba je ohlásena
Předchozí krok je opakován, než řetězec je přijímán nebo syntaktická chyba je ohlásena.

V praxi analyzátor obvykle pokusí se se dostat z syntaktické chyby tím, že ignoruje neočekávané symboly a/nebo vkládat chybějící symboly, a pokračovat rozebrat, ale toto je venku rozsah tohoto článku.

An příklad

Vysvětlit to proč tento algoritmus pracuje my teď pokračujeme s představením jak řetězec jako “1 + 1” by byl rozebrán takový analyzátor. Když analyzátor začne to vždy začíná počátečním stavem 0 a následující hromada:

[ 0 ]

První terminál že analyzátor vidí je ' 1 ' a shodovat se ke stolu akce to by mělo pak jít do státu 2 končit následující hromadou:

[ 0 ' 1 ' 2 ]

Vrchol zásobníku je ukazován na pravé straně. Pro příčinu našeho vysvětlení my také ukazujeme symbol, který způsobil přechod k příštímu státu ačkoli přísně mluvit to není díl hromady.

V stavu 2 stůl akce říká, že kterýkoliv terminál, který my vidíme na potoku vstupu my bychom měli dělat redukci s mluvnickým pravidlem 5. Jestliže stůl je správný pak toto znamená, že analyzátor jen rozpoznal pravou stranu pravidla 5, který je opravdu případ. Tak v tomto případě my píšeme 5 k potoku výstupu, vyjmout jeden stát od hromady a tlak na hromadě stát od buňky v goto stolu pro stát 0 a B, tj., stát 4, na hromadě. Výsledná hromada je:

[ 0 B 4 ]

Nicméně, také v stavu 4 stůl akce říká, že my také děláme redukci s pravidlem 3. Tak my píšeme 3 k potoku výstupu, vyjmout jeden stát od hromady, a najít nový stát v goto stolu pro stát 0 a E, který je stát 3. Výsledná hromada:

[ 0 E 3 ]

Příští terminál že analyzátor vidí je ' + ' a shodovat se ke stolu akce to by mělo pak jít do státu 6:

[ 0 E 3 ' + ' 6 ]

Poznamenat, že výsledná hromada může být interpretována jako minulost konečného státního automatu to jen četlo nonterminal E následovaný terminálem ' + '. Stůl přechodu tohoto automatu je definován posunovýma akcemi ve stolu akce a goto akcemi ve stolu goto.

Příští terminál je nyní ' 1 ' a toto znamená, že my vykonáváme posun a jdeme do státu 2:

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

Jen jak předchozí ' 1 ' toto jeden je redukován k B dávat následující hromadu:

[ 0 E 3 ' + ' 6 B 8 ]

Znovu poznamenat, že hromada si dopisuje se seznamem stavů konečného automatu, který četl nonterminal E, následoval ' + ' a pak nonterminal B. v stavu 8 my vždy hrajeme se snížit s pravidlem 2. Si všimnout toho vrchol 3 státy na hromadě si dopisují s 3 symboly v pravé straně pravidla 2.

[ 0 E 3 ]

Konečně, my jsme četli ' $ ' od potoku vstupu, který znamená to shodovat se ke stolu akce (dnešní stav je 3) analyzátor přijímá řetězec vstupu. Čísla pravidla, která chtějí pak byla psaná k výstupu potok bude [5, 3, 5, 2] který je opravdu rightmost původ řetězce “1 + 1” opačně.

Budovat LR (0) rozebrat stoly

Položky

Konstrukce těchto rozebrat stoly je založený na pojmu LR (0) položka (jednoduše volal položku tady) který být mluvnická pravidla se zvláštní tečkou sčítala někde v pravé straně. Například pravidlo E a rarr; E + B má pokračování čtyři korespondenční položky:

E a rarr; · E + B

E a rarr; E · + B

E a rarr; E + · B

E a rarr; E + B ·

Výjimka jsou pravidla formy a rarr; a epsilon; se kterým jediný položka a rarr; · odpovídá si. Tato pravidla budou použitá naznačovat ten stav analyzátoru. Položka E a rarr; E · + B, například, ukáže, že analyzátor rozpoznal řetězec dopisovat si s E na potoku vstupu a teď čeká, že čte ' + ' následoval další řetězec dopisovat si s E.

Soubory položky

To je obvykle nemožné charakterizovat stav analyzátoru s jedinou položkou, protože to nemůže vědět to v zálohách, které rozhodnou, že to jde do použití pro redukci. Například jestliže tam je také pravidlo E a rarr; E * B pak položky E a rarr; E · + B a E a rarr; E · * B oba si zažádají po řetězci dopisovat si s E byl čten. Proto my budeme charakterizovat stav analyzátoru souborem položek, v tomto případě soubor {E a rarr; E · + B, E a rarr; E · * B}.

Uzavření souborů položky

Položka s bodem v předku nonterminal, takový jak E a rarr; E + · B, ukáže, že analyzátor čeká, že rozebere nonterminal B příští. Zajistit položku soubor obsahuje všechna možná pravidla analyzátor může být uprostřed rozebrat, to musí zahrnovat všechny položky popisovat jak B sám bude rozebraný. Toto znamená to jestliže tam jsou pravidla takový jak B a rarr; 1 a B a rarr; 0 pak soubor položky musí také zahrnovat položky B a rarr; · 1 a B a rarr; · 0. Obecně toto může být vytvořeno takto:

Jestliže tam je položka formy a rarr; v·Bw v položka zapadla a v gramatice je pravidlo formy B a rarr; w ' pak položka B a rarr; · w ' should také být v souboru položky.

Nějaký soubor položek může být rozšířen takový že to vyhoví tomuto pravidlu: jednoduše pokračovat přidat vhodné položky až do celého nonterminals preceeded tečkami jsou vysvětleny. Minimální rozšíření je nazýváno uzavřením položky ustálený a psaný jako clos(Já) kde Já je soubor položky. To jsou tyto uzavřené položkové soubory že my budeme brát jako stavy analyzátoru, ačkoli jediný ones to být vlastně reachable od začít stát bude zahrnut ve stolech.

Rozšířená gramatika

Předtím my začneme určovat přechody mezi různými státy, gramatika je vždy rozšířena se zvláštním pravidlem

(0) S a rarr; E

kde S je symbol nového začátku a E staří odstartovat symbol. Analyzátor bude používat toto pravidlo pro redukci přesně, když to přijímalo řetězec vstupu.

Pro náš příklad my vezmeme stejnou gramatiku jako dříve a zvýšíme to:

(0) S a rarr; E

(1) E a rarr; E * B

(2) E a rarr; E + B

(3) E a rarr; B

(4) B a rarr; 0

(5) B a rarr; 1

To je pro toto rozšířil gramatiku že my budeme určovat soubory položky a přechody mezi nimi.

Nacházet dostupné položkové soubory a přechody mezi nimi

První krok budovat stoly sestává z určovat přechody mezi uzavřenými položkovýma soubory. Tyto přechody budou předurčené jak jestliže my zvažujeme konečný automat, který může číst terminály také jako nonterminals. Začít stav tohoto automatu je vždy uzavření první položky většího pravidla: S a rarr; · E:

Položka zapadla 0

S a rarr; · E

+ E a rarr; · E * B

+ E a rarr; · E + B

+ E a rarr; · B

+ B a rarr; · 0

+ B a rarr; · 1

' + ' Před položkou signalizuje položky, které byly sčítaly pro uzavření. Originální položky bez ' + ' být nazýván jádrem souboru položky.

Začínat od začít stát my budeme nyní určovat všechny státy, které mohou být podávány od tohoto státu. Možné přechody pro soubor položky mohou být najity tím, že se dívá na symboly (terminály a nonterminals) my objevíme těsně za tečkami; v případě souboru položky 0 tito jsou terminály ' 0 ' a ' 1 ' a nonterminal E a B. To shledá položka dala to symbol x vede k my řídíme se následujícím postupem:

Vzít soubor všech položek v aktuálním položkovém souboru kde tam je tečka v přední straně x.
Pohybovat se ve všech těchto položkách pozadí tečky x.
Zavřete výsledný soubor položek.

Pro terminál ' 0 ' toto skončí:

Položka zapadla 1

B a rarr; 0 ·

a pro terminál ' 1 ' v:

Položka zapadla 2

B a rarr; 1 ·

a pro nonterminal E v:

Položka zapadla 3

S a rarr; E ·

E a rarr; E · * B

E a rarr; E · + B

a pro nonterminal B v:

Položka zapadla 4

E a rarr; B ·

Poznamenejte, že ve všech případech uzavření nepřidá nějaké nové položky. My pokračujeme v tomto procesu, než už žádné nové položkové soubory se nalézají. Pro soubory položky 1 a 2 tam bude být žádné přechody protože tečka není před nějakým symbolem. Pro soubor položky 3 my vidíme, že tečka je před terminály ' * ' a ' + '. Pro ' * ' přechod jde do:

Položka zapadla 5

E a rarr; E * · B

+ B a rarr; · 0

+ B a rarr; · 1

a pro ' + ' přechod jde do:

Položka zapadla 6

E a rarr; E + · B

+ B a rarr; · 0

+ B a rarr; · 1

Pro soubor položky 5 my musíme zvažovat terminály ' 0 ' a ' 1 ' a nonterminal B. pro terminály my vidíme, že výsledné uzavřené položkové soubory jsou se rovnat k už našel položce soubory 1 a 2, příslušně. Pro nonterminal B přechod jde do:

Položka zapadla 7

E a rarr; E * B ·

Pro soubor položky 6 my také musíme zvažovat terminál ' 0 ' a ' 1 ' a nonterminal B. Als tady výsledné položkové soubory pro terminály jsou se rovnat k už našel položce soubory 1 a 2. Pro nontermal B přechod jde do:

Položka zapadla 8

E a rarr; E + B ·

Tyto finální položkové soubory mají žádné symboly za jejich tečkami tak už žádnou novou položkou soubory jsou přidány a my jsme dokončeni. Stůl přechodu pro automat teď dívá se takto:

soubor položky	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Vybudování děje a stůl goto

Od tohoto stolu a najitých položkových souborů my vybudujeme děj a goto stůl takto:

sloupce pro nonterminals jsou kopírovány ke stolu goto
sloupce pro terminály jsou kopírovány ke stolu akce jako akce posunu
zvláštní sloupec pro ' $ ' (konec vstupu) je přidán ke stolu akce, který obsahuje acc pro každý soubor položky, který obsahuje S a rarr; E ·.
jestliže položka zapadla i obsahuje položku formy a rarr; w · a a rarr; w je pravidlo m s m > 0 pak řádek pro stát i při práci stůl je kompletně naplněný s redukovat akci rm.

Čtenář může potvrdit, že toto vyplývá opravdu při práci a goto stůl, který byl představován dříve na.

Poznámka o LR (0) proti SLR a LALR rozebrat

Si všimnout toho se snížit akce produkovaly nad procedurou vždy zabírat celou stolní řadu, vyvolání snížení nastat bez ohledu na příští symbol v potoku vstupu. Toto je proč tito jsou LR (0) rozebrat stoly: oni jsou jen vhodní k gramatikám, které nevyžadují lookahead. Gramatika, která potřebuje, aby lookahead disambiguate redukce by potřebovala řadu stolu obsahovat různý redukovat akce v různých sloupcích, a nahoře procedura není schopná vytvářet takové řady.

Refinements k LR (0) předložit proceduru stavby (jmenovitě SLR, LALR) být schopný postavit redukovat akce, které nezabírají celé řady. Proto, oni jsou schopní vykonávat různé redukce (nebo dokonce se posune) od stejného analyzátorového státu pro různé vstupní symboly, dovolit jim rozebrat gramatiky ne parseable LR (0) stůl.

Konflikty v postavených stolech

Automat, který je postaven je mimochodem to je budováno vždy deterministický automat. Nicméně, když se snížit akce jsou přidány ke stolu akce to může stát se, že stejná buňka je vyplněna s redukovat akci a akci posunu ( posun-redukovat konflikt) nebo s dva různý redukovat akce ( se snížit-redukovat konflikt). Nicméně, to může být ukazováno to když toto se stane gramatika není LL (0) gramatika.

Malý příklad non-LL (0) gramatika s posunem-se snížit konflikt je:

(1) E a rarr; 1 E

(2) E a rarr; 1

Jeden z položky zapadne my pak objevíme je:

Položka zapadla 1

E a rarr; 1 · E

E a rarr; 1 ·

+ E a rarr; · 1 E

+ E a rarr; · 1

Tam je posun-degradovat konflikt v tomto souboru položky protože v buňce v stolu akce pro tento soubor položky a terminál ' 1 ' tam bude být oba posunová akce ke státu 1 a redukovat akci s pravidlem 2.

Malý příklad non-LL (0) gramatika s se snížit-se snížit konflikt je:

(1) E a rarr; 1

(2) E a rarr; B 2

(3) a rarr; 1

(4) B a rarr; 1

V tomto případě my dostaneme následující položkový soubor:

Položka zapadla 1

A rarr; 1 ·

B a rarr; 1 ·

Tam je se snížit-degradovat konflikt v tomto položka zapadla, protože v buňkách v akci stůl pro tento soubor položky tam bude oba redukovat akci pro pravidlo 3 a jeden pro pravidlo 4.

Oba příklady nahoře mohou být řešeny tím, že nechá použití analyzátoru následovat soubor (viz LL analyzátor) nonterminal se rozhodnout jestliže to bude používat jednoho s pravidla pro redukci; to bude jen používat pravidlo a rarr; w pro redukci jestliže příští symbol na potoku vstupu je v následovat soubor . Toto řešení vyústí v takzvané jednoduché LR analyzátory.