No title

Teorie automat a formlnch jazyk II podle pednek doc. Mojmra Ketnskho Sazbu v LATEXu pipravil Duan Dobe

Obsah

1 Deterministick syntaktick analza shora dol 1.1 1.2 1.3 1.4 1.5 1.6

LL(k) gramatiky : : : : : : : : : : : Syntaktick anal za LL(1) gramatik : Anal za SLL(k) gramatik : : : : : : Metoda rekurzivn ho sestupu : : : : : Transformace gramatik na LL(1) : : Syntaktick anal za LL(k) gramatik :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

2 Deterministick syntaktick analza zdola nahoru

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

: : : : : :

1

: 1 : 3 : 4 : 5 : 9 : 11

13

2.1 Sestrojen LR(0) analyztoru : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 2.2 Jednoduch LR(k) gramatiky : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17 2.3 Anal za LR(k) gramatik : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17

1 DETERMINISTICK SYNTAKTICK ANALZA SHORA DOL

1

1 Deterministick syntaktick analza shora dol 1.1 LL(k) gramatiky

LL(k) gramatiky a jejich anal za (from Left to right Leftmost parse).

Denice 1.1

Nech G = (N P S ) je CFG, k 1 cel slo.

Denujeme funkci FIRSTkG() : (N )+ ! k takto:

FIRSTkG() = fw 2 j ( ) w ^ jwj k) _ ( ) w ^ jwj = kg Dle denujeme funkci FOLLOWkG : N ! k takto:

FOLLOWkG(A) = fw 2 j S ) uA w 2 FIRSTkG()g Oznaen : Nech w = a1 : : : an , k 1 cel slo. klademe (
Denice 1.2

Nech G = (N P S ) je CFG, k 1 cel slo. ekneme, e G je LL(k) gramatika, prv kdy pro libovoln dv nejlevj derivace

(1) S ) wA ) w ) wx(2) S ) wA ) w ) wy podm nka k : x = k : y zna = . G je LL , 9k : G je LL(k) L je LL(k) , 9G9k : G je LL(k) a L=L(G).

Denice 1.3

Nech G = (N P S ) je CFG. Jestlie pro kad A 2 N plat , e vechna A-pravidla maj prav strany za naj c rzn mi terminln mi symboly, pak G nazveme jednoduchou LL(1) gramatikou.

V ta 1.4

Nech G = (N P S ) je CFG. Pak G je LL(k), prv kdy plat : Jsou-li A ! a A ! dv rzn pravidla v P, pak pro vechny nejlevj vtn formy wA plat :

FIRSTk () \ FIRSTk () = : Dkaz: Z denice LL(k) a FIRST. Pedpokldejme, e prnik je neprzdn , tedy existuje x, kter tam pat . Z denice FIRST:

S ) wA ) w ) wxy S ) wA ) w ) wxz


2

k : xy = k : xz, protoe x 2 FIRSTk . Protoe 6= , G nen LL(k). Pedpokldejme, e G nen LL(k). Pak existuj dv rzn derivace S ) wA ) w ) wx S ) wA ) w ) wy takov, e k : x = k : y, ale 6= , to jest A ! a A ! jsou rzn a FIRSTk () a FIRST () obsahuj etzec k : x a tedy nejsou disjunktn . 2

Dsledek 1.5

Dsledky denice LL(k) Nech G = (N P S ) je CFG bez " pravidel. G je LL(k), prv kdy

8A 2 N 8p 2 P A ! 1 : : : A ! n plat FIRST1(i) \ FIRST1(j ) = pro 1 i = 6 j n.

Nech G = (N P S ) je CFG. G je LL(1) gramatika, prv kdy 8A 2 N 8p1 p2 2 P A ! A ! plat : FIRST1(FOLLOW (A)) \ FIRST1(FOLLOW (A)) = Denice 1.6 Nech G = (N P S ) je CFG. G je siln LL(k) gramatika (pro k 1 cel), jestlie 8A 2 N 8p1 p2 2 P A ! A ! plat : FIRSTk (FOLLOWk(A)) \ FIRSTk (FOLLOWk (A)) = Poznmka 1.7 Kad siln LL(k) (SLL(k)) gramatika je LL(k) gramatikou.

Pklad 1.1

Uvedeme p klad gramatiky, kter je LL(2) a nen SLL(2).

S ! aAaa j bAba A ! bj" FOLLOW2(S ) = f"g, FOLLOW2(A) = faa bag S FIRST2(aAaa:FOLLOW2(S )) = fab aag, FIRST2(bAba:FOLLOW2 (S )) = fbbg, Mnoiny jsou disjunktn . A FIRST2(b:FOLLOW2(A)) = fba bbg, FIRST2(":FOLLOW2(A)) = faa bag, Mnoiny nejsou disjunktn , proto nen SLL(2).

Poznmka 1.8

Kad SLL(1) je LL(1) a naopak.


3

1.2 Syntaktick analza LL(1) gramatik

Syntaktick anal za LL(1) gramatik jde provdt jednostavov m zsobn kov m automatem. Pechodov funkce M je zadna takto:

dom(M ) = (N ) ( f"g) im(M ) = f jA ! je i-t pravidlo v P g fodstra, pijmi, chybag Je-li G = (N P S ), pak 1. Je-li A ! i-t pravidlo, klademe M (A a) = pro vechna a 2 FIRST1(). Je-li t " 2 FIRST1(), pak M (A b) = pro vechna b 2 FOLLOW1(A). 2. M (a a) = odstra. 3. M ($ ") = pijmi. 4. M (x a) = chyba. Syntaktick anal za: (vstup, zsobn k, v stup), (ax, A, i) poten kogurace (w, S $, ")

`: 1. 2. 3. 4.

(ax A ) ` (ax b i), jestlie M (A a) = (ax a ) ` (x a ) (" $ ) . . . koncov kongurace (x ) ` "chyba"

V ta 1.9

Kad LL(k) gramatika je jednoznan.

Dkaz: Nech gramatika G nen jednoznan. pak existuje w 2 L(G) tak, e existuj dv rzn derivace vty w:

1. S ) wA ) w ) wx = w~ 2. S ) wA ) w ) wy = w~ kde A ! a A ! jsou dv rzn pravidla, FIRSTk (x) = FIRSTk (y), ale 6= , tedy G nen LL(K). 2


4

V ta 1.10

Je-li G levorekurzivn , pak nen LL(k) pro dn k.

Dkaz: Bu A 2 N , A je levorekurzivn .

(

" A ) A ) 6) "

V prvn m p pad je A )+ A jednoznan, tedy nen LL(k). Ve druhm nech ) v, v 2 + a dle A ) u. 1. S ) wA0 ) wAk 0 ) wuvk 0 2. S ) vA0 ) wAk 0S ) wAk+10S ) wuvk+10 k : vk = k : vk+1 uvk = k : uvk+1 2

Pklad 1.2

Gramatika

E ! E + T jT T ! T F jF F ! ij(E ) je levorekurzivn a proto nen LL(1). Nkdy je mon gramatiku upravit.

1.3 Analza SLL(k) gramatik Algoritmus 1.1

Vytvoen SLL(k) tabulky M pro SLL(k) gramatiku G = (N P S ). M : N $ k ;! f j i : A ! 2 P g fchybag. Je-li i : A ! 2 P i-t pravidlo, pak M (A x) = pro vechna x 2 FIRSTk () takov, e jxj = k. Je-li i : A ! 2 P i-t pravidlo, pak M (A x) = pro vechna x 2 FIRSTk (FIRSTk ():FOLLOWk(A)).

Algoritmus 1.2

Syntaktick anal za pro SLL(k) gramatiku. Algoritmus A. Vstup: M - SLL(k) tabulka pro danou SLL(k) gramatiku G. V stup: Je-li w 2 L(G), pak lev rozbor vty w (ozn. ), jinak chybov hlen . Metoda: Ozname w = k : x, kde x je dosud nepeten st vstupn ho etzce. 1. Poten kongurace je (w S $ ") 2. (x A ) ` (x i), pro M (A w) = 3. (ax0 a ) ` (x0 )


5

4. (" $ ) je koncov kongurace. 5. jinak (x X ) ` chyba.

Denice 1.11

ekneme, e algoritmus syntaktick anal zy je sprvn, pro bezkontextovou gramatiku G =

(N P S ), jestlie L(G) = fwj A(w) je denovno a A(w) 6=chybag. Je-li A(w) = , pak je lev rozbor vty w.

Jestlie A pou v tabulku M a A je sprvn pro w, pak i M je sprvn pro w.

V ta 1.12

Algoritmus vytvoen SLL(k) tabulky vytv sprvnou tabulku pro A.

Dkaz: Jestlie G je SLL(k), pak pro libovoln argument M je denovna nejv e jedna poloka tvaru < a i >.

S ) w () (w S $ ") ` (" $ )

Dkaz indukc : a) (xy S $ ") ` (y $ ), pak S ) x. b) S ) x, k : y 2 FIRSTk (), pak (xy S $ ") ` (y $ ).

2

1.4 Metoda rekurzivn ho sestupu

Pi metod rekurzivn ho sestupu se vyu vaj znm syntaktick diagramy. Vznikaj c program sestv ze vzjemn rekurzivn ch procedur, kadmu neterminlu odpov d `zhruba' jedna procedura. Tedy postupn: Z neterminl sestroj me syntaktick diagramy. Ze syntaktick ch diagram sestroj me rekurzivn procedury.

Poznmka 1.13

Gramatika je v BNF (Backusova Normln Forma), m-li na prav stran alternativy tvaru A ! aC jbDj : : :. GBNF (zobecnn BNF) pidv do syntaxe zpisu gramatiky symboly +, f: : :g a (: : :) pro iterace apod.

Algoritmus 1.3

Vytvoen syntaktick ch diagram z gramatiky v GBNF

Vstup: Gramatika v GBNF


6

V stup: syntaktick diagramy Metoda: Pro kad A 2 N , A := 1j : : : jn vytvo graf, jeho struktura je urena prav mi stranami 1j : : : jn dle nsleduj c ch pti pravidel. Kad x 2 v i je reprezentovno grafem

- x

-

Kad B 2 N v i je reprezentovno grafem

- B

-

A ::= 1 j : : : jn jsou zobrazena na graf - 1

- 2 . . .

- n = 1 : : : n jsou zobrazena na graf - 1 - . . . 2 = fg je zobrazeno na graf

- n

Pklad 1.3

Gramatika v GBNF

A ::= xj(B ) B ::= AC C ::= f+Ag


# - ! "- - - - -

7

se pevede na

x

(

)

B

A

C

+

A

Systm graf z v stupu algoritmu je vhodn redukovat na dostaten mal poet rozumn velk ch graf pomoc substituce.

Pklad 1.4

- # ! - # "- !

Z pedchoz ho p kladu tak dostaneme graf

"- (

- x

)

A

A

+

A po zjednoduen

x

(

Algoritmus 1.4

A +

)

Transformace syntaktick ch diagram na program Kad graf peve pomoc nsleduj c ch pti krok na procedury Graf - x Peve na if ch=`x' then read(ch) else error


Graf Peve na call A Graf

- A

# ! "-

S1 . . . Sn

#" !

Peve na case ch of L1 : T(S1 ) ... Ln : T(Sn ) endcase kde Li = FIRST (Si), T (Si) je Si po transformaci. Graf - S1 - . . . - Sn Peve na begin T (S1)% ... T (Sn) end

Iterace

S

Se pevede na while ch in L do T(S ), kde L = FIRST (S )

Pklad 1.5

program PARSER%

var ch:char proc A%

begin if ch=`x' then

8


9

read(ch) elseif ch=`(' then begin read(ch)% A% while ch=`+' do begin read(ch)% A% endwhile% if ch=`)' then read(ch)

else

end% BEGIN

error("oekvm `)'")

endif endif

read(ch)% A%

END

1.5 Transformace gramatik na LL(1)

Transformovat gramatiku na LL(1) znamen odstranit kolize FIRST-FIRST a FIRST-FOLLOW. K odstrann kolize FIRST-FIRST me vst kombinace tchto krok:

Odstrann lev rekurze Substituce levho rohu

A ! B B ! 1 j : : : jn =) A ! 1j : : : jn

Lev faktorizace (vyt kn ) ! A0 A ! 1j : : : jn =) A 0 A ! 1j : : : jn Pklad 1.6

Pi kolizi FIRST-FIRST: A ! FIRST () \ FIRST ( ) 6= provedeme levou faktorizaci, je-li to mon. Nech nap klad = fa ig N = fS SLg

SL ! SiSL S ! a kolize: FIRST (S ) \ FIRST (SiSL) = fag.

1 DETERMINISTICK SYNTAKTICK ANALZA SHORA DOL Tuto gramatiku pevedeme na

V sledn Gramatika je LL(1).

10

SL ! SS 0 S 0 ! "jiSL S ! a

Pklad 1.7

Nelze-li aplikovat levou faktorizaci, provedeme substituci levho rohu a po n levou faktorizaci. A ! aB jCB C ! aC jbB B ! cB jD

Tato gramatika nen LL(1), protoe FIRST (aB ) \ FIRST (CB ) = fag. Po substituci levho rohu dostaneme A ! aB jaCB jbBB B ! cB jd C ! aC jbB Gramatika po lev faktorizaci ji bude LL(1):

! aA0jbBB ! B jCB ! CB jd ! aC jbB V p pad kolize FIRST-FOLLOW ( A ! j , ) ", FOLLOW (A) FIRST ( ) 6= ) se A A0 B C

pou vaj tyto transformace: Pohlcen terminlu: G = (N P S ), B 2 N , a 2 , 2 (N ")

A ! Ba B ! 1j : : : jn transformujeme na gramatiku G0 = (N f Ba]g P 0 S ), P 0 = fA ! Ba g fA ! Ba] g f Ba] ! 1aj : : : jnag Extrakce pravho kontextu: G = (N P S ), A X Y 2 N , 2 (N ) , a 2 FIRST (Y B ). P : X ! AY B Y ! ai Y ! j i = 1 : : : m, j = 1 : : : k, a 2 FIRST (j ), P 0 = P ; fX ! AY g fX ! Aa1 j : : : jAam jA1 j : : : jAk g, L(G) = L(G0 ).


11

Pklad 1.8

Gramatiku, kter nen LL(1)

Transformujeme na

A B C D

! ! ! !

BDC "jaaC cjbC a

A ! BaC B ! "jaaC C ! cjbC Dal transformac je pohlcen terminlu, Ba] 2 N : A ! Ba]C Ba] ! ajaaCa C ! cjbC Lev faktorizace: A ! Ba]C Ba] ! aE E ! "jaCa C ! cjbC A nakonec substituce: A ! aEC E ! "jaCa C ! cjbC V sledn gramatika je LL(1).

1.6 Syntaktick analza LL(k) gramatik Denice 1.14

Nech je abeceda, L1 L2 , k 1. Denujeme opertor k takto: L1 k L2 = fwj9x 2 L1 9y 2 L2 : w = k : xyg

Poznmka 1.15

FIRSTk ( ) = FIRSTk () k FIRSTk ( ).

Denice 1.16

Nech G = (N P S ) je bezkontextov gramatika. Pro kad A 2 N a L k denujeme TAL & LL(k) tabulka pro (A L) & jako parciln funkci TAL : k ! fA ! 1j : : : jsg P (k ) takto: 1. TAL(u) = `error0, jestlie neexistuje A ! 2 P : FIRSTk () k L obsahuj c etz u. 2. TAL(u) = (A ! < Y1 : : : Ym >), jestlie A ! je jedin pravidlo v P takov, e u 2 FIRSTk () k L a je-li = x0 B1 x1 : : : Bm xm , pak Yi = FIRSTk (xiBi+1 xi+1 : : : Bm xm ) k L pro i = 1 2 : : : n.


12

3. V ostatn ch p padech nen TAL(u) denovno. (Me nastat jen u gramatik, kter nejsou LL(k).)

Algoritmus 1.5

Konstrukce LL(k) tabulek pro LL(k) gramatiku

Vstup: bezkontextov gramatika G = (N P S ), G je LL(k). V stup: J & mnoina LL(k) tabulek. Metoda: Inicializace ' konstrukce tabulky T0 LL(k) pro S a f"g. J := fT0g. Iterace ' pro kadou tabulku LL(k) 2 J s polokou T (u) = (A ! x0 B1 x1 : : : Bm xm < Y1 : : : Ym >) do J := J fTB Yig pro vechna i 2< 1 m >. Opakuj, dokud se do J d pidat njak LL(k) tabulka. i

Algoritmus 1.6

Konstrukce rozkladov tabulky pro LL(k) gramatiku G = (N P S )

Vstup: LL(k) gramatika G = (N P S ), mnoina LL(k) tabulek J . V stup: rozkladov tabulka pro G: (J f$g) k ! ((Ti ) f1 : : : jpjg) f odstra, pijmi, chyba g. Metoda: Je-li i : A ! x0 B1 x1 : : : Bm xm 2 P a TAL 2 J , pak pro vechna u takov, e TAL(u) = (A ! x0 B1x1 : : : Bm xm < Y1 : : : Ym >) klademe M (TAL u) = (x0 TB1 Y1 : : : TBm Ymxm i). M (a av) =odstra pro libovoln v 2 (k;1) . M ($ ") =pijmi. M (x a) =chyba v ostatn ch p padech.

2 DETERMINISTICK SYNTAKTICK ANALZA ZDOLA NAHORU

13

2 Deterministick syntaktick analza zdola nahoru Denice 2.1

Nech G = (N P S ) je bezkontextov gramatika s pravidly o slovan mi 1 : : : p, p = jP j a S )iR1 1 )iR2 : : : )iR n = w je prav derivace vty w. Pak posloupnost sel pravidel in : : : i2 i1 nazveme prav rozbor vty w. n

Poznmka 2.2

Pechod od i+1 k i m b t deterministick . Mon typy nedeterminism jsou ten redukce A ! : B ! :

redukce redukce

A ! B !

Denice 2.3

Nech G = (N P S ) je bezkontextov gramatika. P idru enou gramatikou ke gramatice G nazveme gramatiku G0 = (N fS 0g P fS 0 ! S g S 0), kde S 0 62 N .

Denice 2.4

Nech G = (N P S ) je bezkontextov gramatika, G0 jej pidruen gramatika, k 0 cel. ekneme, e G je LR(k) gramatikou, prv kdy nsleduj c ti podm nky: 1. S 0 )R Aw )R w 2. S 0 )R Bx )R y 3. k : w = k : y zna , e Ay = Bx (tedy = , A = B , y = x).

Poznmka 2.5

Denice postihuje oba typy nedeterminismu.

Denice 2.6

Nech G = (N P S ) je bezkontextov gramatika. polo kou gramatiky G nazveme kad v raz tvaru A ! : pro A ! 2 P . Jestlie = ", pak v raz A ! : nazveme pln polo ka. Nech dle ! 2 (N ) . ekneme, e A ! : je platn polo ka pro etz !, prv kdy existuje prav vtn forma Au (u 2 ) takov, e = !. etz ! nazveme v tomto p pad platn (perspektivn ) p edpona (viable pre x). Mnoinu vech platn ch poloek pro etz budeme znait I ( ).

Poznmka 2.7

Smujeme k tvrzen , e mnoina platn ch poloek tvo regulrn jazyk.


14

Lemma 2.8

Jestlie A ! :B 2 I ( ), pak t B ! 2 I ( ) pro vechna pravidla B ! 2 P .

Dkaz: Protoe A ! :B 2 I ( ), existuje prav vtn forma Aw takov, e = . Bw )R Bvw je prav vtn forma a tedy B ! : je platn poloka pro etz = , to jest B ! : 2 I ( ). (operace uzvru) 2

Lemma 2.9

Jestlie platn poloka B ! : 2 I (x) x 2 N , pak existuje c ! x: 2 I (x) takov, e )R Bz z 2 .

Dkaz: B ! : 2 I (x), tedy z denice existuje prav vtn forma Bu, = x. Pak existuje i prav vtn forma Cv a pravidlo C ! x 2 P takov, e x = x, a tedy C ! x: je platn poloka pro x = x 2

Lemma 2.10

Jestlie B ! : 2 I (x) a 6= ", pak = 0x a B ! 0:x 2 I ( ).

Dkaz: Z pedpokladu B ! : 2 I (x) plyne existence prav vtn formy B takov, e = x. Protoe 6= ", 0x = , tedy 0 = . 2

Dsledek 2.11

Jestlie I (x) 6= , pak I ( ) 6= .

Lemma 2.12

(operace nsledn ka) Jestlie A ! :x 2 I ( ), pak A ! x: 2 I (x)

Dkaz: Jestlie A ! : je platn pro , existuje prav vtn forma Au = , pak x = x, tedy A ! x: je platn pro x 2 I (x). 2

Lemma 2.13

Pro libovolnou 2 (N ) a x 2 (N ) lze I (x) urit na zklad znalosti I ( ) takto: I (x) je nejmen mnoina M takov, e 1. fY ! x: jY ! :x 2 I ( )g M 2. jestlie A ! :B 2 M , pak i B ! : 2 M

Dkaz:

M I (x) libovoln poloka spluj c 1.,2., (1. viz. lemma 2.12 , 2. viz. lemma 2.8). mjme libovolnou mnoinu M , spluj c 1.,2. Zvolme libovolnou poloku z I (x) B ! : a ukame, e pat do M . Pro = " viz. lemma 2.9, pro 6= " viz. lemma 2.10.

2


15

V ta 2.14

Nech G = (N P S ) je libovoln bezkontextov gramatika. Na (N ) denujeme relaci takto: 1 2, prv kdy I (1) = I (2 ). Pak je pravou kongruenc konenho indexu (Relac ekvivalence zprava invariantn konen m indexem). Dkaz:

Je zejm, e jde o ekvivalenci, je denovna pomoc rovnosti. m konen index, protoe existuje jen konen mnoho rzn ch mnoin poloek pro gramatiku G. 1 2 ) I (1x) = I (2x) plyne z pedchoz ho lemmatu.

2

Lemma 2.15

I (") je nejmen mnoina M takov, e 1. fS ! :jS ! g M 2. jestlie A ! :B 2 M , pak i B ! :# 2 M pro kad B ! # 2 P .

2

Dkaz: Viz. lemma 2.13.

Denice 2.16

Nech G = (N P S ) je libovoln bezkontextov gramatika. Polokov m automatem pro G nazveme ptici A = (Q ; q0 F ), kde Q = fI ( )j 2 (N )g ;=N q0 = I (") : (I ( ) x) = I (x) F : Q ; f g

Pklad 2.1 S A A B

! ! ! !

aAb AcB B d

2 DETERMINISTICK SYNTAKTICK ANALZA ZDOLA NAHORU Poloky S0 I (") S ! :aAB S1 I (a) S ! a:Ab A ! :AcB A ! :B B ! :d S2 I (aA) S ! aA:b A ! A:cB S3 I (aB ) A ! B: S4 B ! d: S5 S ! aAb: S6 A ! Ac:B B ! :d

Nsledn ci a : S1

A : S2 B : S3 d : S4 b : S5 c : S6 `redukuj' `redukuj' `redukuj' B : S7 d : S4

2.1 Sestrojen LR(0) analyztoru Algoritmus 2.1 Vpoet pln mnoiny LR(0) stav Operace uzvru. function UZ(S)

begin

UZ:=S

repeat forall A ! :B 2 S , B ! ! 2 P , B ! :! 62 UZ do UZ := UZ fB ! :!g until dn dal poloka se do UZ ned pidat. end

return(UZ)

Operace nsledn ka. function Nasl(S,X) Nasl(S,X):=UZ(fA ! x: jA ! :x 2 S g)

BEGIN

C :={UZ(S 0 ! :S )}%

repeat forall Z 2 C X 2 N : Nasl(Z X ) 6= ^ Nasl(Z X ) 62 C do C :=C fNasl(Z X )g until dn dal mnoina poloek se do C ned pidat return(C )

END Denice 2.17

Stav polokovho automatu je neadekvtn , jestlie plat :

16


17

tento stav obsahuje alespo jednu *plnou poloku A ! : a alespo jednu ne*plnou poloku B ! : , kde 1 : 2 Tento stav obsahuje alespo dv rzn *pln poloky. Poznmka 2.18 Lze ukzat, e gramatika G je LR(0), prv kdy polokov automat pro G nem dn neadekvtn stavy.

2.2 Jednoduch LR(k) gramatiky Denice 2.19

Bezkontextovou gramatiku G = (N P S ) nazveme jednoduchou LR(k) gramatikou, jestlie pro mnoinu L stav polokovho automatu gramatiky G a dv rzn poloky A ! : a B ! : z q q 2 L plat alespo jedna z nsleduj c ch podm nek: 1. 6= " 6= " 2. = " 6= " a 1 : 2 , FOLLOWk (A) \ FIRSTk (:FOLLOWk (B )) = 3. 6= " = " a 1 : 2 , FOLLOWk (B ) \ FIRSTk (:FOLLOWk(A)) = 4. = " = " a FOLLOWk (A) \ FOLLOWk (B ) =

2.3 Analza LR(k) gramatik Denice 2.20

Nech G = (N P S ) je bezkontextov gramatika, k 0 cel. Libovolnou dvojici < A ! : L >, kde A ! : je poloka gramatiky G v L k nazveme k-polo kou gramatiky G. ekneme, e k-poloka < A ! : L > je platn pro etz !, ! 2 (N ) , prv kdy existuje prav vtn forma Au takov, e = ! a k : u 2 L. Mnoinu vech k-poloek platn ch pro etz ozname Ik ( ).

Denice 2.21 Nech G = (N P S ) je bezkontextov gramatika, k 0 cel, G0 je pidruen gramatika. Nech K0 je mnoina vech poloek pro gramatiku G0 a denujme pechodovou funkci 0 : K0 (N ) ! K0 takto: pro kad K 2 K0, x 2 (N ) je 0(K x) nejmen mnoina M takov, e 1. M f< Y ! x: L > j < Y ! :x L >2 K g 2. jestlie < A ! :B L >2 M , pak pro kad pravidlo B ! ! 2 P , 2 M . Dle ozname K0 2 K0 jako nejmen mnoinu M takovou, e 1. M f< S 0 ! :S ?>g


18

2. jestlie < A ! :B:L >2 M , pak pro kad pravidlo B ! ! 2 P , 2 M. Konen ozname K mnoinu vech prvk z K0 dosaiteln ch z K0 pomoc pedchoz funkce 0 . nech dle zna restrikci 0 na K (N ). Konen automat A = (K N K0 F ), kde F = K ; f g nazveme k-polo kovm automatem pro G (charakteristick m konen m LR(k) automatem).

Poznmka 2.22

Lze ukzat, e G je LR(k), prv kdy plat 1. Jsou-li < A ! : L1 > 2 K , (K 2 K) takov, e L1 \ L2 = , pak A ! = B ! . 2. Jsou-li < A ! : L1 > 2 K , (K 2 K), kde 1 : 2 2 , pak L1 \ FIRSTk (2 :L2 ) = .

Denice 2.23

Nech G = (N P S ) je bezkontextov gramatika, k 0 cel. Denujme funkci EFFk (EmptyFree First) takto: EFFk (!) = ft 2 k jt 2 FIRSTk (!) ^ ! ) ) tv, kde 6= Atvg.

Algoritmus 2.2

Algoritmus konstrukce k-polokovho automatu pro G

Vstup: Pidruen gramatika G0 V stup: k-polokov automat pro G Metoda:

function Uz(in Z) begin repeat forall < A ! : u > B ! w 2 P v 2 FIRSTk (:u) :62 Z do Z := Z fg until (dn nov k-poloka se do Z ned pidat) end

return(Z)

function Nasl(Z,X) begin J := f< A ! x: u > j < A ! :x u >2 Z g end

return(Uz(J ))


19

begin K := ff< S 0 ! :S ?>gg K := { Uz(K) } repeat forall Z 2 K A 2 N : Nasl(Z A) 6= and Nasl(Z A) 62 K do K := K fNasl(Z A)g until dn nov stav se do K ned pidat end Denice 2.24

Nech q je stav LR(k) automatu. klademe jdro(q) = fA ! :beta j < A ! :beta L >2 qg.

Metoda konstrukce: 1. Zkonstruuj LR(k) automat K = fK0 K1 : : : Kng. 2. Pro kad jdro v LR(k) automatu najdi vechny stavy s t mt jdrem a nahra je jejich sjednocen m. 3. Nech Y 0 = fY0 : : : Ymg je v sledn mnoina stav po kroku 2. Analyzan akce ti/redukuj se pevedou p mo z LR(1) automatu. Nevzniknou-li takto analyzan kon,ikty, pak G je LALR(k), jinak G nen LALR(k). 4. Funkci Nasl vytvo me takto: Nech stav Y vznikl sjednocen m LR(1) stav Ki1 : : : Ki , X 2 N , Nasl(Y X ) = K , kde K je sjednocen m vech stav, kter maj stejn jdro jako Nasl(Ki X ) j 2< 1 r >. r

j

Poznmka 2.25 f stavy LALR g = f stavy LR(0) g. Denice 2.26

Nech G = (N P S ). Ozname Q mnoinu vech stav LR(0) automatu A Q0 mnoinu vech stav LR(k) automatu. P esn prav kontext LR(0) poloky A ! : ve stavu q 2 Q denujeme takto: ERCk (q < A ! : >) = ft 2 k j 9q0 2 Q0 : q =jdro(q0)^ < A ! : t >2 q0g ERC znamen Exact Right Context.

Denice 2.27

Nech G = (N P S ) je bezkontextov gramatika , k 1 cel, Q mnoina stav LR(0) automatu pro gramatiku G. ekneme, e G je LALR(k), jestlie 8q 2 Q, 8p 2 P jsou nsleduj c mnoiny vzjemn po dvou disjunktn : Sq = ft j < A ! : 2 q 6= " t 2 EFFk (:ERCk (q < A ! >))g Sqp = ERCk (q )


20

Poznmka 2.28

G je LALR(1), prv kdy pro A ! : a B ! : 1. 6= " ^ 6= " 2. 6= " ^ = " ^ FIRST (:LA(q A)) \ LA(q B ) = 3. = " ^ 6= " ^ FIRST (:LA(q B )) \ LA(q A) = 4. 6= " ^ = " ^ LA(q A) \ LA(q B ) =

Algoritmus 2.3

Uren prav ch kontext generovan ch a prav ch kontext en ch pro k = 1.

Vstup: Bze stav LR(0) automatu pro G, ozna me ji I . V stup: Prav kontexty generovan polokami ve stavu I pro jdro stavu Nasl(I X ). Prav kontexty en polokami ve stavu I pro jdro stavu Nasl(I X ). Metoda: nech # 62 N . Prav kontext ? je pro poloku S 0 ! :S generovn.

forall poloky 2 I do begin J := UZ (fg) if < A ! :X a >2 J ^ a =6 # then a je generovn pro poloku < A ! X: >2 Nasl(I X )% if < A ! :X # >2 J then prav kontext se dd ( ) z poloky 2 I na poloku < A ! X: >2 Nasl(I X ) end Algoritmus 2.4

Efektivn v poet pesn ch prav ch kontext (LA) pro bzov poloky stav LALR(1) automatu.

Vstup: G = (N P S ) V stup: ERC Metoda: 1. Zkonstruuj bzi LR(0) automatu pro G.


21

2. Pomoc pedchoz ho algoritmu uri pro kadou bzi stavu I a pro kad X 2 N prav kontexty, kter jsou pro Nasl(I X ) generovny, resp. zeny. 3. Zi tabulku tvaru: dky budou oznaeny polokami bz , sloupce budou obsazeny prav mi kontexty ERC ( stav, poloka ). 3.1. inicializuj prvn sloupec takto: do tabulky zapi jen generovan prav kontexty, ostatn := . 3.2. iterace: (Round-Robin) Pro kad stav I a kadou poloku i 2 I a symbol X , je-li jejich kontext en na poloku j 2 Nasl(I X ), do change := false for NewERC := ERC (Nasl(I X ) j ) ERC (I i), if NewERC 6= ERC (Nasl(I X ) j ) then ERC (Nasl(I X ) j ) := NewERC , change := true% until not change

LITERATURA

Literatura -1] Chytil, M.: Teorie automat a formln ch jazyk. SPN, Praha 1982 -2] /eka, M., Bene, M., Hruka, T.: Pekladae. Nakladatelstv VUT, Brno 1993

22

No title

Recommend Documents