Konstrukce LR analyzátorů

Konstrukce LR analyzátorů je v matematické informatice automatizovaný proces konstrukce LR syntaktických analyzátorů (anglicky LR parsers). Pro jejich složitost je obtížné naprogramovat LR parsery ručně. Proto byly vytvořeny generátory analyzátorů. LR parsery jsou obvykle implementované jako analyzátory řízené tabulkou analyzátoru – jednotlivé typy se liší hlavně metodou konstrukce této tabulky.

Konstrukce tabulky pro LR(0) analýzu[editovat | editovat zdroj]

Jako příklad použijeme následující gramatiku:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Položky[editovat | editovat zdroj]

Konstrukce tabulky analýzy vychází z konceptu LR(0) položek (anglicky LR(0) items). Tyto položky vzniknou z pravidel formální gramatiky doplněním tečky na libovolné místo na pravé straně pravidla. LR(0) položka má obecně tvar [A→β₁•β₂] kde (A→β₁β₂) je pravidlo gramatiky. Například k pravidlu (E → E + B) existují 4 položky:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

K pravidlům tvaru A → ε existuje jen jedna položka A → •. Položky slouží k vyznačení stavu syntaktického analyzátoru. Například položka [E → E • + B] znamená, že analyzátor rozpoznal ve vstupním proudu řetězec odpovídající neterminálu E (vygenerovaný z tohoto neterminálu) a nyní očekává na vstupu symbol '+', za kterým se nachází řetězec odpovídající neterminálu B.

Množiny položek[editovat | editovat zdroj]

Stav analyzátoru obvykle není možné popsat jedinou položkou, protože analyzátor zpravidla neví předem, které pravidlo použije pro redukci. Pokud například existuje také pravidlo (E → E * B) pak po načtení řetězce odpovídajícího neterminálu E budou použité obě položky, které mají tečku za E: [E → E • + B] a [E → E • * B]. Proto je stav analyzátoru určen množinou položek, v našem případě množinou { E → E • + B, E → E • * B }.

Uzávěr množiny položek[editovat | editovat zdroj]

Položka s tečkou před neterminálním symbolem, jako E → E + • B, označuje, že parser má zpracovat B jako následující neterminální symbol. Množina položek musí obsahovat všechny položky popisující stav konečného automatu, v němž začíná zpracování symbolu B. To znamená, že pokud existují taková pravidla jako B → 1 a B → 0, pak množina položek musí obsahovat také B → • 1 a B → • 0. Toto pravidlo funguje rekurentně: pokud položka, kterou přidáváme, obsahuje tečku (bezprostředně) před neterminálním symbolem, je třeba doplnit položky pro tento symbol. Obecně je to možné zformulovat takto:

„

Pokud v množině máme položku tvaru A → α•Bβ a gramatika obsahuje pravidlo tvaru B → γ, pak v této množině položek musí být také položka B → •γ, kde A a B jsou neterminální symboly, a α,β a γ jsou libovolné řetězce (mohou být i prázdné) skládající se z terminálních a neterminálních symbolů.

“

Každá množina položek může být tímto způsobem rozšířena tím, že opakovaně doplňujeme další položky, ve kterých je neterminální symbol předcházený tečkou, dokud je možné další přidávat. Toto rozšiřování množiny položek nazýváme vytvořením uzávěru (anglicky Closure) množiny položek a uzávěr množiny položek S označujeme Closure(S). Každá množina položek, které jsou dosažitelné z počátečního stavu, bude tvořit stav analyzátoru.

Algoritmus konstrukce uzávěru Closure(S) vypadá takto:

opakuj
  pro každou položku [A → α•Bβ] ∈ S
    pro každé pravidlo (B → η)
      přidej do množiny S položku [B → •η]
dokud bylo něco přidáno do množiny S.

Zúplněná gramatika[editovat | editovat zdroj]

Než začneme popisovat přechody mezi stavy analyzátoru, je třeba rozšířit gramatiku o dodatečné pravidlo:

(0) Z → E

Kde Z je nový počáteční symbol. Analyzátor použije toto pravidlo pro redukci pouze v okamžiku, kdy bude přijat celý vstupní text. Zúplnění gramatika je nutné, pokud se počáteční symbol objevuje v pravidlech gramatiky více než jednou.

Gramatika dostane tvar:

(0) Z → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

Pro tuto gramatiku rozšířenou o první pravidlo definujeme množiny položek a přechody mezi nimi.

Konstrukce tabulky[editovat | editovat zdroj]

Nalezení dosažitelných množin položek a přechodů mezi nimi[editovat | editovat zdroj]

První krok konstrukce tabulek spočívá v popsání přechodů mezi zúplněnými množinami položek. Přechody jsou definovány tak, jako bychom měli konečný automat, který čte jak terminální tak neterminální. Počátečním stavem tohoto automatu je uzávěr první položky přidaného pravidla: Z → • E:

Množina položek 0

Z → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

Symbol "+" před položkou označuje, že byla přidaná do množiny při konstrukci uzávěru. Původní položky, před kterými není "+", se nazývají báze množiny položek.

Vytváříme množinu J všech stavů automatu, kde každý stav je definován nějakým uzávěrem množiny položek. Na počátku je J tvořena pouze počátečním stavem S₀. Začneme od S₀ a postupně definujeme stavy, které jsou dosažitelné z S₀. Přechody mezi množinami položek jsou tvořeny symboly (terminálními nebo neterminálními), které se objevují po tečce. V případě množiny položek s číslem 0 máme terminální symboly '0' a '1' a neterminální E a B. Nalezení množiny položek, do které lze přejít pomocí symbolu X, provádíme následujícím postupem:

Goto(S_a,X)

na počátku je výsledná množina S prázdná
pro každou položku tvaru [A → α•Xβ] ∈ S_a přidáme do výsledné množiny [A → αX•β], neboli pro každou položku v množině S_a, v níž je tečka před X, do množiny přidáme položku, ve které tečku přesuneme za symbol X
pokud výsledná množina S není prázdná, nahradíme ji jejím uzávěrem S = Closure(S), a máme dvě možnosti:
- nalezli jsme v J množinu S_j, která má stejnou množinu položek; pak odstraníme S a přidáme přechod Goto(S_a,X)=S_j
- taková množina položek v J zatím není; pak přiřadíme nové množině další volný index k, a přidáme přechod Goto(S_a,X)=S_k.

Pro terminální symbol '0' bude výsledkem:

Množina položek 1

B → 0 •

pro terminální symbol '1':

Množina položek 2

B → 1 •

pro neterminální symbol E:

Množina položek 3

Z → E •

E → E • * B

E → E • + B

a pro neterminální symbol B:

Množina položek 4

E → B •

Je třeba poznamenat, že provedení uzávěru nepřidalo v žádném z těchto případů žádnou novou položku. Postup opakujeme tak dlouho, dokud nacházíme nové množiny. Pro množin položek s čísly 1, 2 a 4 neexistují žádné přechody, protože se tečka nenachází před žádným symbolem. Pro množinu položek číslo 3 vidíme, že tečka je před terminálními symboly ' *' a '+'. Pro '*' přechod povede do:

Množina položek 5

E → E * • B

+ B → • 0

+ B → • 1

a pro '+':

Množina položek 6

E → E + • B

+ B → • 0

+ B → • 1

Pro množinu položek číslo 5 musíme probrat terminální symboly '0' a '1' a neterminální symbol B. V případě obou terminálních symbolů vidíme, že výsledné množiny jsou stejné, jako již nalezené množiny 1 a 2. Pro symbol B přechod povede do:

Množina položek 7

E → E * B •

Pro množinu položek číslo 6 musíme také probrat terminální symboly '0' a '1' a neterminální symbol B. Stejně jako v předchozím případě, jsou výsledné množiny položek pro terminální symboly stejné jako množiny 1 a 2. Pro symbol B přechod povede do:

Množina položek 8

E → E + B •

Ostatní dvě množiny položek nemají tečky před symbolem, takže přidávání nových množin ukončíme. Výsledná tabulka přechodů automatu vypadá takto:

Množina položek	*	+	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

Konstrukce tabulek action a goto[editovat | editovat zdroj]

Na základě této tabulky a nalezených množin položek zkonstruujeme tabulky action a goto takto:

sloupce pro neterminální symboly se zkopírují do tabulky goto
sloupce pro terminální symboly se zkopírují do tabulky action jako akce přesunu (anglicky shift)
do tabulky action přidáme dodatečný sloupec pro '$' (konec vstupního proudu); sloupec bude obsahovat acc (přijmout) pro množiny položek obsahujícího položku Z → E •.
pokud množina položek i obsahuje položku tvaru A → α • nebo A → α je pravidlem m pro m > 0, pak řádek pro stav i v tabulce action bude celý vyplněn akcí redukce rm.

Výsledkem jsou tabulky

	action					goto
stav	*	+	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

Poznámka o rozdílech mezi LR(0) a SLR a LALR[editovat | editovat zdroj]

Všimněte si, že pouze krok 4 výše uvedené procedury vytváří akce redukce, a že všechny akce redukce musí zabírat celý řádek tabulky, což způsobuje, že redukce se provede nezávisle na dalším symbolu ve vstupním proudu. Díky tomu se jedná o tabulky LR(0): před rozhodnutím, jakou redukci použít, není třeba prohlížet další symboly na vstupu. Gramatika, která potřebuje prohlížet zatím nezpracované symboly, aby vybrala správnou redukci, bude potřebovala tabulky analýzy, jejichž řádky budou obsahovat v různých sloupcích různé akce redukce; pro konstrukci takových tabulek není výše uvedená procedura vhodná.

Procedury konstruující SLR nebo LALR analyzátor mohou vytvářet tabulky, ve kterých akce redukce nezabírá celé řádky. Tyto analyzátory proto mohou analyzovat větší množství gramatik než LR(0) analyzátory.

Konflikty při konstrukci tabulek[editovat | editovat zdroj]

Automat musí být konstruovaný takovým způsobem, který zaručuje determinismus. Jednak když akce redukce jsou přidávané do tabulky action, může se stát, že ta samá buňka je vyplněná jak akcí redukce tak akcí přesun (to je konflikt přesun-redukce) nebo dvěma různými akcemi redukce (konflikt redukce-redukce). Když to se stane, znamená to, že gramatika není LR(0).

Malý příklad gramatiky, která není LR(0), s konfliktem přesun-redukce:

(1) E → 1 E

(2) E → 1

Jednou z množin položek, které nacházíme, je:

Množina položek 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

a obsahuje konflikt přesun-redukce, protože v buňce tabulky action pro tento stav a symbol '1' je současně přesun do stavu 1 a redukce pravidlem 2.

Malý příklad gramatiky, která není LR(0), s konfliktem redukce-redukce:

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

V tomto případě dostáváme následující množinu položek:

Množina položek 1

A → 1 •

B → 1 •

Což je konflikt redukce-redukce, protože v buňkách tabulky action pro tento stav bude současně redukce pravidlem 3 a pravidlem 4.

Oba výše uvedené příklady mohou být vyřešené tak, že dovolíme, aby analyzátor používal množiny Follow pro neterminální symbol A pro rozhodnutí, zda použít jedno z pravidel A pro redukci; použijeme pravidlo A → α pro redukci, pokud následující symbol ve vstupním proudu patří do množiny Follow pro A. Takové řešení se nazývá SLR (Simple LR parser, jednoduchý LR analyzátor).

SLR tabulky[editovat | editovat zdroj]

Uvažujme nevelkou gramatiku, která při vytváření LR(0) tabulek dávala konflikt redukce-redukce; gramatika po doplnění nového počátečního symbolu bude mít tvar:

(0) Z → E

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

Množiny First a Follow pro tuto gramatiku budou vypadat takto:

Symbol	First	Follow
Z	1	$
E	1	$
A	1	1
B	1	2

Množiny položek vypadají takto:

S₀

Z → • E

+ E → • A 1

+ E → • B 2

+ A → • 1

+ B → • 1

S₁ = Goto(S₀, E)

Z → E •

S₂ = Goto(S₀, A)

E → A • 1

S₃ = Goto(S₀, B)

E → B • 2

S₄ = Goto(S₀, 1)

A → 1 •

B → 1 •

S₅ = Goto(S₂, 1)

E → A 1 •

S₆ = Goto(S₃, 2)

E → B 2 •

Při konstrukci tabulek zapisujeme přesuny do sloupců pro neterminální symboly v tabulce goto a pro terminální symboly v tabulce action jako při konstrukci LR(0) tabulky, stejně jako akceptace pro množinu položek, kde vystupuje Z → E •. Rozdíl bude při vpisování redukce, která bude vepsána pouze do těch sloupců tabulky, které odpovídají terminálním symbolům nacházejícím se v množině Follow pro symbol na levé straně pravidla, který vznikne při redukci.

Konkrétně v množině položek číslo 4

A → 1 •

B → 1 •

máme dvě položky s tečkou na konci, které se vztahují k pravidlu 3 (A → 1) i 4 (B → 1). Pravidlo 3 má na levé straně symbol A, pro který Follow(A) = {1} a pravidlo 4 má symbol B, pro který Follow(B) = {2}. Proto vpisujeme redukci podle pravidla 3 do sloupce terminálního symbolu 1 a redukci podle pravidla 4 do sloupce odpovídajícího symbolu 2. V množinách položek vztahujících se ke stavům 5 a 6 automatu máme redukci podle pravidel 1 a 2, které mají na levé straně symbol E, jehož množina Follow(E) = { $ }

Výsledkem jsou tabulky:

	action			goto
stav	1	2	$	E	A	B
0	s4			1	2	3
1			acc
2	s5
3		s6
4	r3	r4
5			r1
6			r2

Kanonický LR(1) analyzátor[editovat | editovat zdroj]

Na rozdíl od LR(0) položek [A→β₁•β₂] mají LR(1) položky tvar [A→β₁•β₂, v], kde (A→β₁β₂) je pravidlo gramatiky a v je terminální symbol nebo znak $ konce proudu. Symbol v nazýváme náhledem (anglicky lookahead).

Algoritmus konstrukce uzávěru Closure(S) vypadá takto:

 
opakuj
  pro každou položku [A → α•Bβ, v] ∈ S
    pro každé pravidlo (B → η)
      pro každý symbol b ∈ First(βv)
        přidej do množiny S položku [B → •η, b]
dokud bylo něco přidáno do množiny S.

First(βv) obsahuje všechny symboly z First(β) (kromě ε), a pokud First(β) obsahuje ε, pak First(βv) obsahuje také symbol v.

Vytváříme množinu J, což je množina všech stavů automatu, který začíná počáteční množinou S₀. Množina S₀ je uzávěrem položek [Z → • E, $]

Goto(S_a,X)

na počátku je výsledná množina S prázdný
pro každou položku tvaru [A → α•Xβ, a] ∈ S_a přidáme do výsledné množiny [A → αX•β, a], neboli pro každou položku v množině S_a, v níž je tečka před X, do výsledné množiny přidáme položku s tím samým náhledem, ve kterém přesuneme tečku za symbol X
pokud výsledná množina S není prázdná, nahradíme ji jejím uzávěrem S = Closure(S), a máme dvě možnosti:
- nalezli jsme v J množinu S_j, která má stejnou množinu položek (včetně náhledů) jako množina S; pak odstraníme S a přidáme přechod Goto(S_a,X)=S_j
- taková množina položek v J zatím není; pak přiřadíme nové množině další volný index k, a přidáme přechod Goto(S_a,X)=S_k.

Při konstrukci tabulek vpisujeme přesuny do sloupců pro neterminální symboly v tabulce goto a pro terminální symboly v tabulce action jako při konstrukci LR(0) tabulky; akceptace vpisujeme do sloupce $ v tom stavu, kde máme položku [Z → E •, $]; redukci vpisujeme do sloupce v pro položku tvaru [A → α•, v].

Položky s množinou náhledových symbolů[editovat | editovat zdroj]

Místo sady položek v množině jako

L → •*R, $
L → •*R, =

které se liší jen náhledem, je možné zadat reprezentace tvaru [A→β₁•β₂, Ω], kde Ω je množina náhledů. Kromě určitého uspořádání v množině položek, budou položky s množinami náhledů užitečné při konstrukci LALR analyzátoru. Výše uvedené dvě položky mohou být zapsané jako jedna: [L→•*R, $=].

Algoritmus konstrukce uzávěru Closure(S) bude mít tvar:

 
opakuj
  pro každou položku [A → α•Bβ, Ω] ∈ S

    v množině Ω mají být symboly z First(βv) pro v∈Ω, neboli
    inicializujeme množinu Δ symboly First(β) kromě ε, 
    a pokud First(β) obsahuje ε, pak do Δ přidáme všechny symboly z Ω

      pro každé pravidlo (B → η)

        přidej do množiny S položku [B → •η, Δ], pokud identická neexistuje
        s výjimkou náhledů [B → •η, Γ],
        pokud existuje, pak do Γ přidej všechny symboly z Δ

dokud bylo něco přidáno do množiny S.

Algoritmus je možné také rozdělit na dvě fáze, aby bylo možné využít propagaci náhledů při konstrukci LALR tabulky:

1. Vytváříme uzávěr podobně jako pro LR(0), ale nepoužíváme náhledy; nově přidané (nebázové) položky budou inicializované prázdnými množinami:

opakuj
  pro každou položku [A → α•Bβ, Ω] ∈ S
    pro každé pravidlo (B → η)
      přidej do množiny S položku [B → •η, ø]
dokud bylo něco přidáno do množiny S.

2. Aplikujeme blízké šíření (v rámci jedné množiny položek) náhledů:

 
opakuj
  pro každou položku [A → α•Bβ, Ω] ∈ S

    v množině Ω mají být symboly z First(βv) pro v∈Ω, neboli
    inicializujeme množinu Δ symboly First(β) kromě ε, 
    a pokud First(β) obsahuje ε, pak do Δ přidáme všechny symboly z Ω

      pro každé pravidlo (B → η)
        pro položku [B → •η, Γ] přidej do Γ všechny symboly z Δ
dokud bylo něco přidáno do množiny S.

Goto(S_a,X)

na počátku je výsledná množina S prázdná
pro každou položku tvaru [A → α•Xβ, Ω] ∈ S_a přidáme do výsledné množiny [A → αX•β, Ω]
pokud výsledná množina S není prázdná, nahradíme ji jejím uzávěrem S = Closure(S), a máme dvě možnosti:
- nalezli jsme v J množinu S_j, která má stejnou množinu položek (včetně náhledů) jako množina S; pak odstraníme S a přidáme přechod Goto(S_a,X)=S_j
- taková množina položek v J zatím není; pak přiřadíme nové množině další volný index k, a přidáme přechod Goto(S_a,X)=S_k.

Při konstrukci tabulek shift a goto postupuje jako v předchozím případě, a když je v množině položka tvaru [A → α•, Ω], pak redukci vepíšeme do sloupce odpovídajícího symbolům v∈Ω.

Příklad[editovat | editovat zdroj]

Uvažujme gramatiku:

(1) S → L=R

(2) S → R

(3) L → *R

(4) L → a

(5) R → L

Doplníme ji o počáteční symbol a pravidlo:

(0) Z → S

A vytváříme množiny položek:

S₀

Z → •S, $

+ S → •L=R, $

+ S → •R, $

+ L → •*R, $=

+ L → •a, $=

+ R → •L, $

Goto(S₀, S) = S₁

Goto(S₀, L) = S₂

Goto(S₀, R) = S₃

Goto(S₀, *) = S₄

Goto(S₀, a) = S₅

S₁ = Goto(S₀, S)

Z → S•, $

S₂ = Goto(S₀, L)

S → L•=R, $

R → L•, $

Goto(S₂, =) = S₆

S₃ = Goto(S₀, R)

S → R•, $

S₄ = Goto(S₀, *) = Goto(S₄, *)

L → *•R, $=

+ R → •L, $=

+ L → •*R, $=

+ L → •a, $=

Goto(S₄, L) = S₇

Goto(S₄, R) = S₈

Goto(S₄, *) = S₄

Goto(S₄, a) = S₅

S₅ = Goto(S₀, a) = Goto(S₄, a)

L → a•, $=

S₆ = Goto(S₂, =)

S → L=•R, $

+ R → •L, $

+ L → •*R, $

+ L → •a, $

Goto(S₆, L) = S₉

Goto(S₆, R) = S₁₀

Goto(S₆, *) = S₁₁

Goto(S₆, a) = S₁₂

S₇ = Goto(S₄, L)

R → L•, $=

S₈ = Goto(S₄, R)

L → *R•, $=

S₉ = Goto(S₆, L) = Goto(S₁₁, L)

R → L•, $

S₁₀ = Goto(S₆, R)

S → L=R•, $

S₁₁ = Goto(S₆, *) = Goto(S₁₁, *)

L → *•R, $

+ R → •L, $

+ L → •*R, $

+ L → •a, $

Goto(S₁₁, L) = S₉

Goto(S₁₁, R) = S₁₃

Goto(S₁₁, *) = S₁₁

Goto(S₁₁, a) = S₁₂

S₁₂ = Goto(S₆, a) = Goto(S₁₁, a)

L → a•, $

S₁₃ = Goto(S₁₁, R)

L → *R•, $

	action				goto
stav	=	*	a	$	S	L	R
0		s4	s5		1	2	3
1				acc
2	s6			r5
3				r2
4		s4	s5			7	8
5	r4			r4
6		s11	s12			9	10
7	r5			r5
8	r3			r3
9				r5
10				r1
11		s11	s12			9	13
12				r4
13				r3

LALR(1) analyzátor[editovat | editovat zdroj]

Sloučení LR(1) stavů[editovat | editovat zdroj]

Definujeme jádro (anglicky Core) množiny LR(1) položek:

S je množina LR(1) položek
Core(S) = {[A → α•β] | [A → α•β, u] ∈ S}

LALR(1) analyzátor vznikne z LR(1) analyzátoru sloučením stavů s identickým jádrem. Pro systému množin S₀,S₁,...S_m dostaneme T₀,T₁,...T_n, kde T_a = S_i0 ∪ S_i1 ∪ ... ∪ S_ik. Sloučení podléhají množiny náhledů. Ve výše uvedeném příkladě je možné sloučit

S₄ a S₁₁
S₅ a S₁₂
S₇ a S₉
S₈ a S₁₃

Dostáváme 10 stavů, pro které aktualizujeme tabulku přechodů Goto

Stav LR(1)	Stav LALR(1)	Stav LR(1)	Stav LALR(1)
0	0	7	7
1	1	8	8
2	2	9	7
3	3	10	9
4	4	11	4
5	5	12	5
6	6	13	8

Přímá konstrukce[editovat | editovat zdroj]

Místo generovaní všech LR(1) množin, které pak spojujeme, je možné vyjít od konstrukce tabulky LR(0) bez náhledových symbolů, a pak ji vyplnit těmito symboly.^[1]^[2]. Algoritmus se skládá ze dvou fází:

1. Vytváříme LR(0) tabulku společně s tabulkou přechodů Goto bez ohledu na náhledy; a když používáme ne z [A→β₁•β₂] a [A→β₁•β₂, Ω], pak množinu náhledů Ω ponecháme prázdnou - výjimkou je [Z → • E, $], který je inicializovaný znakem konce proudu.

2. Fáze propagací náhledových symbolů.

opakuj
pro dalších množiny položek od 0 do m
- pro množinu S_a pokud je změněna
  - proveď výše popsané blízké šíření na množině položek S_a
  - pokud S_k = Goto(S_a, X), pak množiny náhledů bázových položek S_k [A → αX•β, Γ] budou doplněny o symboly jim odpovídajících položek [A → α•Xβ, Ω] z S_a; pokud kompletace způsobí nějakou změnu, pak množinu S_k označíme jako modifikovanou
dokud se přidaly nové symboly

Příklad[editovat | editovat zdroj]

Pro výše uvedené gramatiky vypadá LALR(1) tabulka takto:

	action				goto
stav	=	*	a	$	S	L	R
0		s4	s5		1	2	3
1				acc
2	s6			r5
3				r2
4		s4	s5			7	8
5	r4			r4
6		s4	s5			7	9
7	r5			r5
8	r3			r3
9				r1

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Generowanie parserów LR na polské Wikipedii.

↑ Delphi Yacc & Lex; A parser generator toolset for Delphi and Kylix; Version 1.4 User Manual [online]. 2005 [cit. 2018-08-29]. Dostupné online.
↑ Delphi Yacc & Lex [online]. [cit. 2018-08-29]. Dostupné online.

Literatura[editovat | editovat zdroj]

MOLNÁR, Ľudovít; ČEŠKA, Milan; MELICHAR, Bořivoj. Gramatiky a jazyky. 1. vyd. Bratislava: Alfa, 1987. 188 s. S. 150–184. (slovensky)
CHYTIL, Michal. Automaty a gramatiky. 1. vyd. Praha: SNTL, 1984. 331 s. S. 220–252.
AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jeffrey D. Compilers : Principles, Techniques, and Tools. [s.l.]: Reading: Addison-Wesley Publishing Company, 1987. 796 s. Dostupné online. ISBN 0-201-10088-6. (anglicky)
WAITE, W. M.; GOOS, G. Konstrukcja kompilatorów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1989. (polsky)

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Teoria Automatów i Języków Formalnych, Teoria Kompilacji dr inž. Janusz Majewski, mgr inž. Marcin Kuta, mgr inž. Marta Majewska

[1] Delphi Yacc & Lex; A parser generator toolset for Delphi and Kylix; Version 1.4 User Manual [online]. 2005 [cit. 2018-08-29]. Dostupné online.

[2] Delphi Yacc & Lex [online]. [cit. 2018-08-29]. Dostupné online.

[1]

[2]