pokladem, že gramatika (3 je redukovaná. M proto obsahuje jedinou trojici {[A], a, [x]\ jejíž třetí složka je [x]. Proto [Mj = = {([Á], ax, c)}, kde r je jednoznačně určeno podle lemmatu 5.3.4. [Mv] je jednobodová, a proto má souvislou charakteristiku.
Důsledek 5.3.9. Každý stav l(y) položkového automatu pro gramatiku & má souvislou charakteristiku.
Důkaz. Vyplývá okamžitě z lemmat 5.3.7, 5.2.13, 5.3.6 a 5.3.8. Z předchozího tvrzení už se snadno dokáže, že <§ je LR(0) gramatika.
Důkaz věty 5.3.1. Z definice množiny souvislé charakteristiky vyplývá, že taková množina může obsahovat nejvýše jednu trojici, jejíž třetí složka je e nebo Z. Každá úplná položka A-> a. má charakteristiku ([Á], a, e). Každá položka A -* a. p, v níž je napravo od tečky terminál, má charakteristiku ([A], a, ľ). Proto každá množina souvislé charakteristiky může zahrnovat nejvýše jednu úplnou položku a v tom případě žádnou položku s terminálem bezprostředně napravo od tečky.
Každá množina I(y) je podle tvrzení 5.3.9 souvislé charakteristiky, a proto splňuje podmínku 2 definice LR(0) gramatiky (viz 5.2.19). Podmínka 1 je splněna také, neboť počáteční neterminál S se v žádném pravidle nevyskytuje na pravé straně.
Z vět 5.2.26 a 5.3.1 dostáváme následující výsledek.
Věta 5.3.10. Jazyk lze popsat LR(0) gramatikou, právě když jej lze rozpoznat deterministickým zásobníkovým automatem prázdným zásobníkem.
5.4.      LR(k) gramatiky
V 51. 5.3 jsme zavedli položkový automat, jakožto zdroj informace použitelné k deterministické analýze LR(0) gramatik. Stavy tohoto automatu jsou množiny položek.
Nyní zavedeme obecnější pojem /c-položky, který umožní příslušnou informaci získávat pro analýzu širší třídy gramatik.
Definice 5.4.1. Nechť 9 = (77, Z, S, P) je bezkontextová gramatika a k Si 1 přirozené číslo, k-položkou gramatiky ^ nazveme
242
každou dvojici (A -> a. p, l), kde A -> a. /? je položka ^ a L £ Z*k. i        Symbolem Z*k označujeme množinu všech slov v abecedě Z, jejichž délka nepřesahuje k. V dalším textu už budeme odkaz na gramatiku 9 vynechávat.
i
Definice 5.4.2. Řekneme, že /c-položka (A -» a. p, L) je platná k-položka pro řetěz co e (ľ u 77)*, jestliže existuje pravá větná forma n Au taková, že rja = co a k(u) e L.
j Poznámka 5.4.3. Jestliže (A -> a. /i, L) je platná /c-položka pro
řetěz co, potom je zřejmě A -> a. /j platná položka pro co.
Úmluva 5.4.4. Symbolem Ik(y) budeme označovat množinu I        všech platných fc-položek pro řetěz y.
j Definice 5.4.5. Nechť Jt' je množina všech množin /c-položek
I (pro danou gramatiku). Definujme funkci ô': $P x (Z u 17) -> Jť1 takto: pro každé KeJť' a x e (Z u 77) je ô'(jf, x) nejmenší množina M taková, že
1. M 2 {(Y -> ax. p, L); [Y-> a. Xp, L) e K};
2. jestliže (A -> a. Bp, Ĺ) e M, potom pro každé pravidlo B -> S gramatiky je (b ->. 9, k{pĹ)) e M.
Definice 5.4.6. Definujme množinu K0 e Jť', kde ' má týž význam jako v předchozí definici, jakožto nejmenší množinu M
i        takovou, že
|
í 1. M 2 {(S ->.a, {e}); S -> aeP};
2. jestliže (A ->.bp, L) e M, potom také pro každé pravidlo B-vSeP je [b -+.&,k{pl))eM.
Symbolem Jf" označme množinu prvků množiny Jť' dosažitelných z K0 (přechodovou funkcí 5') a symbolem ô označme restrikci ô' na Jľ x (Z u 77).
Konečný automat
si = (jf, Z u TI, ô, K0, F),
kde F — JT — {0}, nazveme k-položkovým automatem pro danou gramatiku.
243
Definice 5.4.7. Nechť k > 0. Bezkontextová gramatika <Š = (77,1, S, P)
je LR(/c) gramatika, jestliže platí tyto tři podmínky:
1. Počáteční symbol se nevyskytuje na pravé straně žádného pravidla;
2. jestliže (A -> a.,L,), (73 -> j5.,L2) jsou dvě /c-položky (úplné /(-položky) vyskytující se současně v nějakém stavu Ke/ a takové, že L, n L2 # 0, potom pravidlo /4 -»a je totožné s pravidlem B -* /í;
3. jestliže se v některém stavu Ke.Tľ současně s úplnou k-po-ložkou (A -* L,) vyskytne fr-položka tvaru (B-►/?.?, L2), v níž se bezprostředně napravo od tečky vyskytuje terminál, potom L, n k(yL2) = 0.
Poznámka 5.4.8. Z definic 5.2.17 a 5.4.6 vyplývá, že pro každý řetěz y je
{A -» a. 0; (X -> a. j8, L) e 5(K0, y) pro nějaké L} £ .
Z tohoto zjištění a z definice 5.4.7 pak plyne, že každá LR(0) gramatika je LR(fc) gramatikou pro libovolné k ^ 1.
Analogicky lze dokázat, že každá LR(fc) gramatika je LR(lc + 1)
pro každé fcžO.
symboly gramatiky
stavy
h -položkového automatu
Obr. 43
244
Jazyk generovaný libovolnou LR(fc) gramatikou
9 = {n,z,s, p)
je možné analyzovat typem deterministického analyzátoru, který je schematicky zachycen na obr. 43.
Takový analyzátor je modifikací deterministického automatu s výstupní páskou. Změna se týká pouze vstupní hlavy, která v tomto případě snímá zároveň obsah k sousedních políček. Po zpracování libovolného počátečního úseku vstupního slova má proto LR(/c) analyzátor k dispozici informaci i o následující /c-tici vstupních symbolů. Zásobník je obsluhován obdobným způsobem, s jakým jsme se setkali už v čl. 5.3 u deterministické analýzy LR(0) jazyků. Díky tomu je v každém okamžiku výpočtu obsah zásobníku tvaru
(pravý konec opět odpovídá vrcholu zásobníku), kde q0, ...,qn jsou stavy /c-položkového automatu pro <3, xv xn e E u 77, n ^ 0, q0 je počáteční stav a
qi = %>,*! ...X;)
pro všechna i, 1 5á i á n.
Způsob, jakým se obsah zásobníku aktualizuje při přenosu dalšího vstupního symbolu do zásobníku i při redukci obsahu podle některého pravidla gramatiky zůstává naprosto stejný jako u LR(0) analýzy.
Změna nastává pouze u postupu, kterým se v každém kroku výpočtu rozhoduje, zda dojde k přesunu do zásobníku nebo k redukci a ve druhém případě pak ještě podle kterého pravidla se redukce provádí.
U LR(0) gramatik se příslušné rozhodování provádělo na základě položky nacházející se na vrcholu zásobníku. U LR(/c) analyzátoru se další postup určí podle těchto dvou údajů:
1. množiny q /c-položek nacházející se na vrcholu zásobníku;
2. následující /c-tice u vstupních symbolů. Z nich se příští krok určí takto:
a) Jestliže q obsahuje fc-položku (A -> a., L) takovou, že u e L
245
a A není počáteční symbol, provede se redukce podle pravidla A -* a. [Podrobněji: ze zásobníku se odebere vrchních 2 . |ce| symbolů, tj. symboly tvořící a a stavy umístěné nad každým z nich. Tím se na vrcholu zásobníku objeví jistý stav q'. Nad něj se uloží dvojice symbolů Aq", kde q" = ô(q', A). Na výstupu se vytiskne číslo pravidla A a.]
Jestliže A je počáteční symbol, ukončí se po provedení redukce výpočet vyprázdněním zásobníku a přijetím slova.
b) Jestliže q obsahuje /c-položku (A -> a. /?, L) takovou, že prvním symbolem /j je terminál a m e k(flĹ), potom se provede přesun do zásobníku. [Podrobněji: do zásobníku se přesune další vstupní symbol b — který je nutně totožný s prvním symbolem /? — a nad něj se uloží symbol 5(q, ř>).]
c) Jestliže nenastane ani možnost a), ani b), ukončí se výpočet zamítnutím zkoumaného slova.
Vlastnosti LR(/c) gramatiky požadované v definici 5.4.7 zaručují, že ze všech eventualit uvedených sub a) až c) nastane právě jedna.
Příklad 5.4.9. Přesvědčíme se, že gramatika <S:
1.	S	-» AB,
2.	S	-+A,
3.	A	-* aAb,
4.	A	-* e,
5.	B	-> W3,
6.	B	-* c
je LR(l) gramatika a sestrojíme k ní LR(l) analyzátor.
Diagram 1-položkového automatu pro ^je sestrojen na obr. 44. Na diagramu jsme opět pro přehlednost vypustili stav odpovídající prázdné množině 1-položek (zde by to byl stav q12) a všechny přechody do něj vedoucí. V diagramu je použito vžitého zkratkového značení. Jednoprvkový jazyk {x} značíme pouze x; množinu položek
{A^a.p,L1\...,{A-^a.p,Ln)
zkráceně zapisujeme
A ->a./?, Lj \ L2
A s~a.Ab,e \{b,c) A^.aAb, b A^.,b
b (jLr\A^aA.b/e\{b,c]\
Obr. 44
Gramatika 0 je LR(l), neboť počáteční symbol se nevyskytuje na pravé straně žádného pravidla a 1-položkový automat na obr. 44 také splňuje podmínky z definice 5.4.7. Tak např. ve stavu q0 jsou obsaženy dvě úplné položky
Pí = {A -> ., e) a p2 = (A^ ., {b, c})
a dvě položky s terminálem bezprostředně napravo od tečky:
p3 = {A ->■ .aAb, e)ap4 = (4-> .aAb, {b, c}).
Ke konfliktu mezi px a p2 (viz podmínku 2 z definice 5.4.7) nedochází, neboť odpovídají témuž pravidlu a navíc
{e} n{b,c} = 0.
246
247
Podobně nedochází ke konfliktu mezi pl a p3 nebo pA (podmínka 3), protože
{e} n í(aAb{e}) = [e] n l{aAb{b, c}) = 0 .
Ke konfliktu mezi p2 a p3 nebo p4 nedochází, protože
{b, c} n l(a,4b{e}) = {b, c) n l(aAb{b, c}) = 0.
Na základě 1-položkového automatu z obr. 44 lze tedy sestrojit LR(1) analyzátor pro gramatiku (S. Akce tohoto analyzátoru v závislosti na vrchním symbolu v zásobníku (tj. stavu 1-položkového
	a	Vstupní symbol b c		e
	přesun a	A -* e; 4	y4 -» e; 4	<4 -» e; 4
Qi		přesun b	přesun c	přijmout; 2
<?2	přesun a	A -» e; 4		
<b		přesun b		
li		A -* aAb; 3	A -»a^6; 3	A^aAb; 3
15				přijmout; 1
				B -> c; 6
li	přesun a	A -* e; 4		
Is		přesun b	přesun c	
				B -> bB; 5
?io		přesun b		
iu		A^aAb; 3		
In				
Tab. 15
automatu) a následujícím vstupním symbolu (nebo e, což odpovídá tomu, že slovo bylo dočteno do konce) popíšeme tab. 15.
Akce označovaná v tabulce „X -» r\; i" znamená: zredukovat podle pravidla X -> r\ (včetně příslušné aktualizace zásobníku) a vytisknout i. Vstupní hlava se neposouvá.
Akce označovaná „přijmout; i" znamená: vyprázdnit zbytek zásobníku a vytisknout i. Výpočet končí přijetím slova.
Akce označovaná „přesun x" znamená: uložit symbol x do zásobníku (a přidat nad něj příslušný symbol stavu položkového automatu) a posunout vstupní hlavu.
Prázdná políčka v tabulce označují situace, ve kterých analyzátor končí a vydá hlášení, že analyzované slovo nepatří do L(^). Speciálně taková situace nastává vždy, když se na zásobníku objeví symbol q12 odpovídající prázdné množině položek.
Příklad 5.4.10. Nad slovem aabbc pracuje analyzátor sestrojený v př. 5.4.9 takto (první člen trojice označuje vždy zbytek vstupního slova, druhý člen obsah zásobníku a třetí obsah výstupní pásky):
(aabbc; q0; e) h (abbc; q0aq2; e) h
1- (bbc; q0aq2aq1; e) h (bbc; q0aq2aq7Aq10;4) h
h (bc;q0aq2aq1Aq10bqll;4) h (fec;q0aqíAq3;43) h
I- (c; q0aq2Aq3bq4; 43) h (c; q0Aql; 433) h
h (e; g04íiCg6; 433) h (e; q0AqlBq5; 4336) h
I- slovo je přijato, jeho pravý rozbor je 43361.
5.5.      LR jazyky a deterministické jazyky
Definice 5.5.1. Jazyk nazveme LR(/c) jazykem, jestliže existuje LR(/c) gramatika, která jej generuje. Řekneme, že jazyk je LR jazykem, jestliže je LR(/c) jazykem pro nějaké přirozené číslo k 2: 0.
Cílem tohoto článku je dokázat, že libovolný jazyk je LR, právě když je deterministický. Jedna část tvrzení plyne z toho, že LR(/c) analyzátory lze simulovat deterministickým zásobníkovým automatem.
Věta 5.5.2. Každý LR jazyk je deterministický.
248
249
10
Důkaz. V článku 5.2 jsme ukázali, jak převést LR(O) analyzátor na deterministický zásobníkový automat. Jednalo se o způsob obsluhování zásobníku (pozn. 5.2.25) a tentýž způsob lze využít při přechodu od LR(/c) analyzátoru k deterministickému zásobníkovému automatu pro libovolné k ä: 0. V případě k 3; 1 vyvstává ještě problém, jak nahradit možnost prohlížení k symbolů dopředu na vstupní pásce, kterou má LR(/c) analyzátor. V možnostech deterministického automatu je uchovávat informaci o fc-tici symbolů v konečné paměti řídicí jednotky. Deterministický automat tedy může např. provádět manipulaci se zásobníkem se zpožděním až po přečtení potřebných k symbolů. Zde ovšem vzniká další potíž. Kdyby automat pouze udržoval konstantní předstih hlavy, mohlo by se stát, že hlava opustí pravý konec slova dříve, než má automat možnost dokončit simulaci výpočtu. Tomu lze poměrně snadno odpomoci, pokud je pravý konec vstupní pásky označen speciálnim koncovým znakem. Na tomto znaku se vstupní hlava zastaví.
Od deterministického automatu s koncovým znakem lze pak přejít k ekvivalentnímu deterministickému zásobníkovému automatu bez koncového znaku, protože podle tabulky 8 jsou deterministické jazyky uzavřeny vůči pravému kvocientu s regulárním jazykem.
Ukážeme, že platí i věta obrácená k větě 5.5.2.
Věta 5.5.3. Každý deterministický jazyk je LR(1) jazyk.
Důkaz věty je bezprostředním důsledkem následujících tří lemmat.
Lemma 5.5.4. Nechť L je libovolný bezkontextový jazyk, # přidaný symbol a ^ redukovaná bezkontextová gramatika generující jazyk L#. Jestliže některý stav l-položkového automatu pro $ obsahuje i-položku tvaru (A -* a. # /?, £), potom Ĺ = {e} a       = e.
Důkaz. Indukcí se snadno ověří, že kdyby existovalo neprázdné slovo ueĹ, nebo 1(/?) ^ e, existovalo by odvození
S =>* ôAuv =>* Sa # fiuv =>* w1 # w2
pro nějaké w2 # e, což je spor s předpokladem, že Wj # w2 £ L #.
250
Lemma 5.5.5. Nechť L# je LR(0) jazyk, přičemž symbol # se nevyskytuje v žádném slově jazyka L. Potom L je LR(l) jazyk.
Důkaz. Nechť <8 je LR(0) gramatika taková, že L(^) = L#. Sestrojme 1-položkový automat s£ pro (S. Jakmile některý stav q automatu .sé obsahuje 1-položku tvaru \A -» a. # j5, L), je podle 5.5.4 Ĺ = {e}. Navíc platí, že q neobsahuje žádnou úplnou 1-položku. Jinak by odpovídající stav položkového automatu obsahoval jednak A -* a. # /?, jednak úplnou položku, a to by bylo ve sporu s předpokladem, že <3 je LR(0) gramatika. Podobně q neobsahuje žádnou další 1-položku s terminálem bezprostředně za tečkou.
Sestrojme nyní gramatiku která se od bude lišit pouze tím, že # bude v (S' patřit mezi neterminály a oproti ^ bude mít navíc pravidlo # -* e.
Okamžitě je zřejmé, že L(^') = L.
Z konstrukce l-položkového automatu plyne, že 1-položkový automat pro y se od l-položkového automatu pro ^ liší pouze ve stavech, které u gramatiky ^ obsahovaly 1-položku typu (A -* tt. # /!, e). Odpovídající stav u vždy navíc obsahuje 1-položku (# -»., e). Ostatní stavy se shodují. Z toho je vidět, že i 1-položkový automat pro eš' splňuje podmínky z definice LR(1) gramatiky. Stavy, ve kterých je nyní navíc 1-položka (# ->., e), už u gramatiky ^ neobsahovaly jinou úplnou 1-položku. Pokud takový stav obsahuje nějakou 1-položku (X -> y . xô, L) s terminálem x, potom kolize s 1-položkou (# ->., e) opět nenastává, protože
l{xô . L) = {x} a {x} n {e} = 0.
[Samozřejmě nenastává ani kolize s (A -*■ a . # p, e), protože # je v neterminálem.]
Lemma 5.5.6. Jestliže L je deterministický jazyk a # nově přidaný symbol, potom L # je LR(0) jazyk.
Důkaz. Jazyk L# je podle 4.4.11 rozpoznatelný deterministickým zásobníkovým automatem pomocí prázdného zásobníku. Proto je podle 5.3.1 LR(0) jazyk.
251
Důkaz věty 5.5.3. Buď L libovolný deterministický jazyk a # nějaký nově přidaný symbol. Potom L# je podle 5.5.6 LR(0) jazyk, a tedy L je podle 5.5.5 LR(1) jazyk.
Věta 5.5.7. Jazyk je deterministický, právě když je to LR jazyk.
Důkaz plyne bezprostředně z vět 5.5.2 a 5.5.3.
Důsledek 5.5.8. Každý LR jazyk je LR(l) jazyk.
Důkaz. Každý LR jazyk je deterministický podle 5.5.2, a tedy jej podle 5.5.5 generuje vhodná LR(1) gramatika.
Poznámka 5.5.9. Z 5.5.7 pochopitelně neplyne, že každá LR gramatika je LR(1). Naopak, lze ukázat, že pro každé k > 0 existuje LR(/c) gramatika, která není LR(/c — 1).
5.6.      LL(A) gramatiky
Zobecněním pojmu LL(l) gramatiky dostaneme pojem LL(/c) gramatiky.
Definice 5.6.1. Budiž k S; 1 přirozené číslo. O bezkontextové gram'atice 9 = (77, Z, S, P) říkáme, že je LL(/c) gramatika, jestliže pro libovolná dvě pravidla A -> a, A -» P (a # p) gramatiky a libovolnou levou větnou formu uAr\ (u e Z*) platí, že
k[uri) n kifirj) = 0 .
Čtenář, který už si osvojil, jak souvisí levé derivace s analýzou shora, dokáže jistě odhadnout dosah této definice pro analýzu. Levá větná forma uAn odpovídá situaci, kdy v zásobníku je uloženo slovo An (levý konec slova zde opět znamená vrchol zásobníku). Jestliže je splněna podmínka z definice LL(fc) gramatiky, znamená to, že /c-tice terminálních symbolů, která se postupně objeví na vrcholu zásobníku an (tj. zásobníku po přepsání podle pravidla A -> a), se v žádném případě nemůže objevit na vrcholu při zpracování zásobníku Pn a obráceně. Klíč k určení, které z pravidel A -> a, A ~* P použít, tedy lze najít v následující k-tici vstupních symbolů.
Definice 5.6.2. Budiž k ^ 1 přirozené číslo. Silnou LL(fc) gramatikou nazveme každou bezkontextovou gramatiku
9 = In, z, s, p)
i
splňující tuto podmínku: Pro libovolná dvě pravidla A-*% a -»P (a / P) gramatiky a libovolné levé větné formy uAn, ivli9 (w, v e Z*) je
k(«ri) n k(p&) = 0.
Poznámka 5.6.3. Než vyjasníme zdánlivý nesoulad mezi defi-| nicí LL(1) gramatiky z čl. 5.1 a definicemi 5.6.1, 5.6.2, uvědomme si, že požadavek kladený na silnou LL(/c) gramatiku je silnější než požadavek kladený na LL(/c) gramatiku. Proto je každá silná LL(k) gramatika také LL(/c) gramatikou. Obráceně to platit nemusí (pro k Si 2), jak ukážeme.
Příklad 5.6.4. Přesvědčíme se, že gramatika S ^ 0X0011/110, A ->■ 1 \e
je LL(2), ale není to silná LL(2) gramatika. S-pravidla mají na začátku pravých stran odlišné terminály, takže stačí prozkoumat pouze X-pravidla. Existují pouze dvě levé formy obsahující A, a to 0/400 a 1X10. Ověřme pro obě podmínku z definice 5.6.1: 2(100) n 2(e00) = 0 a 2(110) n 2(el0) = 0, gramatika je tedy LL(2).
Na druhé straně 2(100) n 2(el0) = {10}, což znamená, že gramatika není silná LL(2) gramatika.
Poznámka 5.6.5. Uchýlíme-li se opět k interpretaci definice 5.6.2 v termínech analýzy shora, je možné silné LL(k) gramatiky charakterizovat jako takové, u nichž přepsání symbolu A na vrcholu zásobníku řetězem a při nějakém výpočtu vede k postupnému vydání /c-tice terminálních symbolů odlišných od fc-tic, které se objeví po přepsání A na P i při libovolném jiném výpočtu. Díky tomu je návrh analyzátorů pro silné LL(k) gramatiky jednodušší než v obecném LL(fc) případě.
252
253