Az LR elemző felépítése. Léptetés. Redukálás. Kiegészített grammatika. Mit kell redukálni? Kiegészített grammatika. elemző. elemző

Emlékeztető

Emlékeztető: elemzési irányok Felülről lefelé

Alulról felfelé S

LR elemzések (az LR(0) elemzés) Fordítóprogramok előadás (A,C,T szakirány)

S

(1)

(1)

(3)

(3)

A

B

A

B

(2)

(2)

a

a

(3) b

S →(1) AB →(2) aaB →(3) aab Ez egy legbal levezetés! 1

Fordítóprogramok előadás (A,C,T szakirány)

LR elemzések (az LR(0) elemzés)

2

Emlékeztető


(1)

(1)

a

a

(2) b

aab ←(1) Ab ←(2) AB ←(3) S Ez egy legjobb levezetés inverze! LR elemzések (az LR(0) elemzés)

Emlékeztető

Emlékeztető: alulról felfelé elemzések

Emlékeztető: alulról felfelé elemzési stratégiák visszalépéses keresés (backtrack): ha nem sikerül eljutni a startszimbólumig, lépjünk vissza, és válasszunk másik redukciót ⇒visszalépéses alulról felfelé elemzések (nem tananyag) lassú ha hibás a szöveg, az csak túl későn derül ki

Az elemzendő szöveg összetartozó részeit helyettesítjük nemterminális szimbólumokkal (redukció) és így alulról, a kezdőszimbólum felé építjük a fát.

Fő kérdés: „Mit redukáljunk?”

3



4

Emlékeztető



Emlékeztető

Emlékeztető: alulról felfelé elemzési stratégiák

Emlékeztető: alulról felfelé elemzési stratégiák

visszalépéses keresés (backtrack): ha nem sikerül eljutni a startszimbólumig, lépjünk vissza, és válasszunk másik redukciót ⇒visszalépéses alulról felfelé elemzések (nem tananyag)

visszalépéses keresés (backtrack): ha nem sikerül eljutni a startszimbólumig, lépjünk vissza, és válasszunk másik redukciót ⇒visszalépéses alulról felfelé elemzések (nem tananyag)

lassú ha hibás a szöveg, az csak túl későn derül ki

lassú ha hibás a szöveg, az csak túl későn derül ki

precedenciák használata: az egyes szimbólumok között adjunk meg precedenciarelációkat és ennek segítségével határozzuk meg a megfelelő redukciót ⇒precedencia elemzések (nem tananyag)

precedenciák használata: az egyes szimbólumok között adjunk meg precedenciarelációkat és ennek segítségével határozzuk meg a megfelelő redukciót ⇒precedencia elemzések (nem tananyag)

ma már kevéssé használt operátorokkal felépített kifejezések esetén természetes a használata

ma már kevéssé használt operátorokkal felépített kifejezések esetén természetes a használata

előreolvasás: olvassunk előre a szövegben valahány szimbólumot, és az alapján döntsünk a redukcióról ⇒LR elemzések minden programozási nyelvhez lehet (LR) elemzőt készíteni majdnem mindegyikhez lehet gyors (LALR) elemzőt készíteni 4



4



Alapfogalmak

Alapfogalmak

Az LR elemző felépítése

Léptetés

x β

y

a

x ab y

elemző

x ab y

elemző

a β

β

xay : bemenet β: aktuális mondatforma egy része (veremben tároljuk)

elemző

A bemenet következő szimbólumát a verem tetejére helyezzük.

két lehetséges művelet: léptetés és redukálás LR: Left to right, using a Rightmost derivation (Balról jobbra, legjobb levezetéssel)

5



6


Alapfogalmak

Alapfogalmak

Redukálás

Kiegészített grammatika

Az elemzés végét arról fogjuk felismerni, hogy egy redukció eredménye a kezdőszimbólum lett.

Az A → α szabály szerinti redukció. x a y α


Ez csak akkor lehet, ha a kezdőszimbólum nem fordul elő a szabályok jobboldalán.

x a y

elemző

A β

β

elemző

A verem tetején lévő szabály-jobboldalt helyettesítjük a megfelelő nemterminális szimbólummal.

7



8


Alapfogalmak


Alapfogalmak

Kiegészített grammatika

Mit kell redukálni?

Az elemzés végét arról fogjuk felismerni, hogy egy redukció eredménye a kezdőszimbólum lett. Ez csak akkor lehet, ha a kezdőszimbólum nem fordul elő a szabályok jobboldalán. Ezt nem minden grammatika teljesíti, de mindegyik kiegészíthető: legyen S ′ az új kezdőszimbólum legyen S ′ → S egy új szabály

az LR elemzésekhez mindig kiegészített nyelvtanokat fogunk használni

8



9



Alapfogalmak

Alapfogalmak



Egyszerű részmondat (emlékeztető): α a γαβ mondatforma egyszerű részmondata, ha S ⇒∗ γAβ ⇒ γαβ.

Egyszerű részmondat (emlékeztető): α a γαβ mondatforma egyszerű részmondata, ha S ⇒∗ γAβ ⇒ γαβ. Nyél: a mondatformában a legbaloldalibb egyszerű részmondat.

9



9


Alapfogalmak


Alapfogalmak


A nyél meghatározása

Probléma: „Mi a nyél?”

Egyszerű részmondat (emlékeztető): α a γαβ mondatforma egyszerű részmondata, ha S ⇒∗ γAβ ⇒ γαβ.

léptetni vagy redukálni kell? ha több lehetőség is van, melyik szabály szerint kell redukálni?

Nyél: a mondatformában a legbaloldalibb egyszerű részmondat. Épp a nyelet kell megtalálni a redukcióhoz.

9



10

Alapfogalmak


Alapfogalmak

A nyél meghatározása


LR(k) grammatikák

Magyarázat az LR(k) definíciójához Tegyük fel, hogy léptetésekkel és redukálásokkal eljutottunk az αβw mondatformához, és itt β a nyél: S ⇒∗ αAw ⇒ αβw .

Probléma: „Mi a nyél?” léptetni vagy redukálni kell? ha több lehetőség is van, melyik szabály szerint kell redukálni?

LR(k) grammatika: k szimbólum előreolvasásával eldönthető, hogy mi legyen az elemzés következő lépése.

10



11



Alapfogalmak

LR(k) grammatikák

Magyarázat az LR(k) definíciójához

Alapfogalmak

LR(k) grammatikák


Tegyük fel, hogy léptetésekkel és redukálásokkal eljutottunk az αβw mondatformához, és itt β a nyél: S ⇒∗ αAw ⇒ αβw .


Tegyük fel, hogy egy ugyanígy kezdődő mondatforma, az αβy felbontható αβy = γδx módon, és ebben δ a nyél, azaz S ⇒∗ γBx ⇒ γδx.

Tegyük fel, hogy egy ugyanígy kezdődő mondatforma, az αβy felbontható αβy = γδx módon, és ebben δ a nyél, azaz S ⇒∗ γBx ⇒ γδx. Az LR(k) tulajdonság azt mondja, hogy w -ből és y -ból előreolvasva k szimbólumot, egyértelműen eldönthető az elemzés következő lépése.

11


Alapfogalmak


11


LR(k) grammatikák


Alapfogalmak


LR(k) grammatikák

LR(k) definíciója


Definíció: LR(k) grammatika

Tegyük fel, hogy egy ugyanígy kezdődő mondatforma, az αβy felbontható αβy = γδx módon, és ebben δ a nyél, azaz S ⇒∗ γBx ⇒ γδx.

Egy kiegészített grammatika LR(k) grammatika (k ≥ 0), ha S ⇒∗ αAw ⇒ αβw S ⇒∗ γBx ⇒ γδx αβy = γδx és FIRSTk (w ) = FIRSTk (y ) esetén α = γ, β = δ és A = B.

Az LR(k) tulajdonság azt mondja, hogy w -ből és y -ból előreolvasva k szimbólumot, egyértelműen eldönthető az elemzés következő lépése. Ezért ha FIRSTk (w ) = FIRSTk (y ), akkor αβw és αβy esetén is ugyanazt kell csinálni: mivel αβw esetén az A → β szabály szerint redukáltunk, ugyanezt kellett csinálni αβy estén is, vagyis α = γ, β = δ, A = B és y = x. 11


Alapfogalmak


12


LR(k) grammatikák

LR(k) definíciója


Az LR(0) elemzés menete

Példa Grammatika

Definíció: LR(k) grammatika Egy kiegészített grammatika LR(k) grammatika (k ≥ 0), ha S ⇒∗ αAw ⇒ αβw S ⇒∗ γBx ⇒ γδx αβy = γδx és FIRSTk (w ) = FIRSTk (y ) esetén α = γ, β = δ és A = B.

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒ abcd

LR(0) grammatika: előreolvasás nélkül eldönthető az elemzés következő lépése.

12



13





Példa

Példa Grammatika

Grammatika 1 2

S′ → S

1

S′ → S

S → aAd

2

S → aAd

3

A → bA

4

A→c

3

A → bA

4

A→c

S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒ abcd

abcd#

abcd#

elemző

elemző

#

13


14

léptetés

elemző

a #





Példa

Példa

Grammatika

Grammatika

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒abcd

abcd# elemző

a #

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

abcd# léptetés




abcd#

elemző

b a #

elemző

b a #

16

abcd# léptetés



c b a #

elemző



Példa

Példa

Grammatika

Grammatika

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

S ′ ⇒ S ⇒ aAd ⇒abAd ⇒ abcd

abcd# c b a #

17

abcd#

#


15


elemző

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

abcd# redukálás (4)


A b a #


S ′ ⇒ S ⇒aAd ⇒abAd ⇒ abcd

abcd# A b a #

elemző

18

elemző



A a #


elemző



Példa

Példa

Grammatika

Grammatika

1

S′ → S

1

S′ → S

2

S → aAd

2

S → aAd

3

A → bA

3

A → bA

4

A→c

4

A→c

S ′ ⇒ S ⇒aAd ⇒abAd ⇒ abcd

abcd# A a #

19

abcd#

abcd# d A a #

léptetés

elemző


d A a #

elemző


20


elemző



Az elemző automata működése

Léptetés vagy redukálás? LR(0) elemzés: előreolvasás nélkül kell döntenünk!

Grammatika 1

S′ → S

2

S → aAd

3

A → bA

4

A→c

S ′ ⇒S⇒ aAd ⇒ abAd ⇒ abcd

abcd#

abcd# elfogadás

elemző

S #

elemző

S′ #




22



Léptetés vagy redukálás?




Példa

LR(0) elemzés: előreolvasás nélkül kell döntenünk! S′ → S

Ötlet: készítsünk egy véges determinisztikus automatát az átmeneteit a verembe kerülő szimbólumok határozzák meg

S

léptetéskor terminális redukáláskor nemterminális

0

S′ → S S 0

1 a

d

3 A 2

b

b

4

A

a

A 2

5

4

6 A

S → aAd 7

A → bA

c 5

A→c abcd#

A → bA

elemző #0

A→c LR elemzések (az LR(0) elemzés)

b

b

S → aAd 7

d

3

c

c


6

1

c

amikor elfogadó állapotba jut, akkor kell redukálni

22

elemző

S #



Példa

21

S ′ ⇒S⇒aAd ⇒abAd ⇒ abcd

23






Példa

Példa S′ → S S 0

1 A

a

d

3 2

b

b

6

7

2

#0



7

A → bA

c A→c

25

abcd# léptetés

elemző

a2 #0



elemző

b4 a2 #0



Példa

S → aAd

abcd#

elemző

a2 #0

6 A

4 5

léptetés


b

b

A→c

abcd#

elemző

A

a

d

3

c

abcd#



1 A

a

d

3 2

b

b

6

7

0

A → bA

A

a

2

c5 b4 a2 #0


7

A → bA

c A→c

27

abcd# A7 b4 a2 #0

redukálás

elemző



elemző



Példa

S → aAd

abcd# c5 b4 a2 #0

elemző


6 A

4 5

abcd#


b

b

A→c

léptetés

d

3

c

abcd# elemző

1

c 5

b4 a2 #0

S′ → S

S → aAd

S

A

4

c



1 a

d

3 A 2

b

b

4

6

5

S

A

7

elemző

0

A → bA

1 a

b

b

4

A3 a2 #0

A

A3 a2 #0 29

elemző

S → aAd 7

A → bA

A→c

abcd#

elemző


6

c 5

abcd#


A 2

A→c

redukálás

d

3

c

abcd# A7 b4 a2 #0

S′ → S

S → aAd

c

c

28

0

A → bA

1

c 5

26

S′ → S

S → aAd

S

A

4

c

24


abcd# léptetés


d6 A3 a2 #0

elemző





Példa


1 a

d

3 A 2

b

b

4

6

5

S

A

7

elemző

0

A → bA

1 a

2

b

b

4

S1 #0

A

S → aAd 7

A → bA

A→c

abcd#

elemző


6

c 5

redukálás


A

A→c

abcd#

d

3

c

abcd# d6 A3 a2 #0

S′ → S

S → aAd

c

c

30


elemző

S1 #0 31

Az elemző automata felépítése

abcd# elfogadás


S ′#0

elemző



LR(0) elemek

LR(0) elemek

Hogyan építsük fel az automatát?

Hogyan építsük fel az automatát? Az automata állapotai azt mutatják meg, hogy melyik szabály építésében hol tartunk. Például: [S → a.Ad ] jelentse azt, hogy az a szimbólumot már elemeztük, az Ad rész még hátra van.

32



32





LR(0) elemek

LR(0) elemek



Az automata állapotai azt mutatják meg, hogy melyik szabály építésében hol tartunk. Például: [S → a.Ad ] jelentse azt, hogy

Az automata állapotai azt mutatják meg, hogy melyik szabály építésében hol tartunk. Például: [S → a.Ad ] jelentse azt, hogy

az a szimbólumot már elemeztük, az Ad rész még hátra van.

az a szimbólumot már elemeztük, az Ad rész még hátra van.

Definíció: LR(0) elem

Definíció: LR(0) elem

Ha A → α a grammatika egy helyettesítési szabálya, akkor az α = α1 α2 tetszőleges felbontás esetén [A → α1 .α2 ] a grammatika egy LR(0) eleme.

Ha A → α a grammatika egy helyettesítési szabálya, akkor az α = α1 α2 tetszőleges felbontás esetén [A → α1 .α2 ] a grammatika egy LR(0) eleme. Ha a szabály jobboldala n szimbólumot tartalmaz, akkor n + 1 darab LR(0)-elem tartozik hozzá. A → .aAd , A → a.Ad , A → aA.d , A → aAd .

32



32





A lezárás művelet


Az automata egy állapotához több LR(0)-elem is tartozhat.

Az automata egy állapotához több LR(0)-elem is tartozhat.

Ezeket a halmazokat fogjuk kanonikus halmazoknak hívni.

Ezeket a halmazokat fogjuk kanonikus halmazoknak hívni.

Milyen LR(0) elemek tartoznak egy halmazba? Például: Ha [A → a.Ad] állapotban vagyunk, akkor az A → bA és A → c szabályokat kezdhetjük építeni, azaz [A → .bA] és [A → .c] is hozzátartozik a halmazhoz.

33



33






Az olvasás művelet

Az automata egy állapotához több LR(0)-elem is tartozhat. Ezeket a halmazokat fogjuk kanonikus halmazoknak hívni.

Hogyan lépünk át az automata egyik állapotából a másikba?

Milyen LR(0) elemek tartoznak egy halmazba? Például: Ha [A → a.Ad] állapotban vagyunk, akkor az A → bA és A → c szabályokat kezdhetjük építeni, azaz [A → .bA] és [A → .c] is hozzátartozik a halmazhoz.

Definíció: lezárás (closure) Ha I a grammatika egy LR(0) elemhalmaza, akkor closure(I) a legszűkebb olyan halmaz, amely az alábbi tulajdonságokkal rendelkezik: I ⊆ closure(I) ha [A → α.Bγ] ∈ closure(I), és B → β a grammatika egy szabálya, akkor [B → .β] ∈ closure(I). 33



34









Ha [A → a.Ad ] állapotban vagyunk, és A kerül a verem tetejére, akkor [A → aA.d ] állapotba jutunk.

Ha [A → a.Ad ] állapotban vagyunk, és A kerül a verem tetejére, akkor [A → aA.d ] állapotba jutunk. Definíció: olvasás (read) Ha I a grammatika egy LR(0) elemhalmaza, X pedig terminális vagy nemterminális szimbóluma, akkor read (I, X ) a legszűkebb olyan halmaz, amely az alábbi tulajdonsággal rendelkezik: ha [A → α.X β] ∈ I, akkor closure([A → αX .β]) ⊆ read (I, X ).

34



34





LR(0) kanonikus halmazok

LR(0) kanonikus halmazok

Definíció: LR(0) kanonikus halmazok

Definíció: LR(0) kanonikus halmazok

closure([S ′ → .S]) a grammatika egy kanonikus halmaza.

1

closure([S ′ → .S]) a grammatika egy kanonikus halmaza.

1

2

Ha I a grammatika egy kanonikus elemhalmaza, X egy terminális vagy nemterminális szimbóluma, és read (I, X ) nem üres, akkor read (I, X ) is a grammatika egy kanonikus halmaza.

2

Ha I a grammatika egy kanonikus elemhalmaza, X egy terminális vagy nemterminális szimbóluma, és read (I, X ) nem üres, akkor read (I, X ) is a grammatika egy kanonikus halmaza.

3

Az első két szabállyal az összes kanonikus halmaz előáll.

3

Az első két szabállyal az összes kanonikus halmaz előáll.

Az automata felépítése: A closure([S ′ → .S]) legyen a kezdőállapot. Ha I ′ = read (I, X ), akkor az automatában legyen X I I′ átmenet. A végállapotok azok a kanonikus halmazok, amelyekben olyan elemek vannak, ahol a pont a szabály végén van. 35



35




Példa

Példa

Példa grammatika

Példa grammatika 1 2 3 4

1

S′ → S 0

S → aAd A → bA A→c



S′ → S

2

S → aAd

3

A → bA

4

A→c

37

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

0



Példa

S′ → S S 0

Példa grammatika

1 a

2

I0 = closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} I1 = read (I0 , S) = {[S ′ → S.]} I2 = read (I0 , a) = closure([S → a.Ad ]) = {[S → a.Ad ], [A → .bA], [A → .c]}

38

1

S



Példa

Példa grammatika

S′ → S

I0 = closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} I1 = read (I0 , S) = closure([S ′ → S.]) = {[S ′ → S.]}

I0 = closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]}

36




1

S′ → S

2

S → aAd

3

A → bA

4

A→c

I0 I1 I2 I3

39

S′ → S S 0

1 a

3 A 2

= closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} = read (I0 , S) = {[S ′ → S.]} = read (I0 , a) = {[S → a.Ad ], [A → .bA], [A → .c]} = read (I2 , A) = closure([S → aA.d ]) = {[S → aA.d ]}





Példa

Példa

Példa grammatika 1

S′

2

S → aAd

→S

3

A → bA

4

A→c

I0 I1 I2 I3 I4

40

S′ → S S 0

1

3 A

a

Példa grammatika

2

b

1

4

= closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} = read (I0 , S) = {[S ′ → S.]} = read (I0 , a) = {[S → a.Ad ], [A → .bA], [A → .c]} = read (I2 , A) = {[S → aA.d ]} = read (I2 , b) = closure([A → b.A]) = {[A → b.A], [A → .bA], [A → .c]}



S → aAd

3

A → bA

4

A→c

41

2

S → aAd

3 4

I0 I1 I2 I3 I4 I5 I6 42

S′ → S S 0

1 A

a

d

3 2

A → bA

6

4

c 5

1

S′ → S

2

S → aAd

3

A → bA

4

A→c

I0 I1 I2 I3 I4 I5 I6 I7


43

Példa grammatika

A → bA A→c

S

1 A

a

d

3 2

b

6 S → aAd A 7

4

A → bA

c 5

A→c

{[S ′

= → .S]) = → .S], [S → .aAd ]} = read (I0 , S) = {[S ′ → S.]} = read (I0 , a) = {[S → a.Ad ], [A → .bA], [A → .c]} = read (I2 , A) = {[S → aA.d ]} = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} = read (I2 , c) = {[A → c.]} = read (I3 , d ) = {[S → aAd .]} = read (I4 , A) = closure([A → bA.]) = {[A → bA.]} Fordítóprogramok előadás (A,C,T szakirány)



S′ → S S 0

1 a

d

3 A 2

b

b 4

6

Példa grammatika

S → aAd A 7

c

1

A → bA

5 A→c ... I4 = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} I5 = read (I2 , c) = {[A → c.]} ... read (I4 , b) = closure([A → b.A]) = {[A → b.A], [A → .bA], [A → .c]} = I4

44

A→c

Példa

S′ → S

4

4


S′ → S 0

closure([S ′


Példa

3

b

5


A→c

= closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} = read (I0 , S) = {[S ′ → S.]} = read (I0 , a) = {[S → a.Ad ], [A → .bA], [A → .c]} = read (I2 , A) = {[S → aA.d ]} = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} = read (I2 , c) = {[A → c.]} = read (I3 , d ) = closure([S → aAd .]) = {[S → aAd .]}

S → aAd

2 c

Példa grammatika

S → aAd b

A→c

2

A

a



1

3

Példa

Példa grammatika S′ → S

0

1

= closure([S ′ → .S]) = {[S ′ → .S], [S → .aAd ]} = read (I0 , S) = {[S ′ → S.]} = read (I0 , a) = {[S → a.Ad ], [A → .bA], [A → .c]} = read (I2 , A) = {[S → aA.d ]} = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} = read (I2 , c) = closure([A → c.]) = {[A → c.]}


Példa

1

S

S′ → S

2

I0 I1 I2 I3 I4 I5

S′ → S



S′ → S S

S′ → S

2

S → aAd

3

A → bA

4

A→c

0

1 a

d

3 A 2 c

b

b 4

6 S → aAd A 7

c

5 A→c ... I4 = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} I5 = read (I2 , c) = {[A → c.]} ... read (I4 , b) = I4 read (I4 , c) = closure([A → c.]) = {[A → c.]} = I5

45



A → bA


Az elemző helyessége

LR(0) elemző táblázat S′ → S S 0 állapot 0 1 2 3 4 5 6 7 46

Véges-e az elemző létrehozása?

1 a

d

3 A 2

b

b

A

4

c

akció léptetés OK léptetés léptetés léptetés redukálás (A → c) redukálás (S → aAd ) redukálás (A → bA)


6

S 1

S → aAd c

a grammatikának véges sok szabálya van

A→c

7

A → bA

5

A

a 2

d

b

c

3

4

5

7

4

5

véges sok LR(0) eleme van

6


47











a closure függvény kiszámítása véges sok lépésben befejeződik

a closure függvény kiszámítása véges sok lépésben befejeződik

a read függvény kiszámítása véges sok lépésben befejeződik

a read függvény kiszámítása véges sok lépésben befejeződik a véges sok LR(0)-elem hatványhalmaza is véges a lehetséges kanonikus halmazok száma is véges

47



47






Helyes-e az elemző?

a grammatikának véges sok szabálya van véges sok LR(0) eleme van a closure függvény kiszámítása véges sok lépésben befejeződik

Az automata pontosan akkor jut-e végállapotba, ha redukálni kell?

a read függvény kiszámítása véges sok lépésben befejeződik

A megfelelő a redukciót írja-e elő?

a véges sok LR(0)-elem hatványhalmaza is véges a lehetséges kanonikus halmazok száma is véges Az elemző táblázat (az automata) létrehozása véges sok lépésben befejeződik.

47



48





Járható prefix

Járható prefix

Definíció: járható prefix


Ha az αβx mondatforma nyele β, akkor az αβ prefixeit az αβx járható prefixeinek nevezzük.

Ha az αβx mondatforma nyele β, akkor az αβ prefixeit az αβx járható prefixeinek nevezzük. A járható prefixeket olvassuk végig a nyél végének eléréséhez. Példa: S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒ abcd Az abAd mondatforma nyele a bA. A járható prefixei: a, ab, abA

49



49





Járható prefix

Járható prefixre érvényes LR(0) elemek Definíció: járható prefixre érvényes LR(0) elemek


A grammatika egy [A → α.β] LR(0)-eleme érvényes a γα járható prefixre nézve, ha S ′ ⇒∗ γAx ⇒ γαβx

Ha az αβx mondatforma nyele β, akkor az αβ prefixeit az αβx járható prefixeinek nevezzük. A járható prefixeket olvassuk végig a nyél végének eléréséhez. Példa: S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒ abcd Az abAd mondatforma nyele a bA. A járható prefixei: a, ab, abA Maximális járható prefix: olyan járható prefix, amihez nem lehet újabb szimbólumot hozzávenni, hogy járható prefixet kapjunk. Egy járható prefix épp akkor maximális, ha a végén van a nyél. 49



50





Járható prefixre érvényes LR(0) elemek

Az LR(0) elemzés helyessége

Definíció: járható prefixre érvényes LR(0) elemek A grammatika egy [A → α.β] LR(0)-eleme érvényes a γα járható prefixre nézve, ha S ′ ⇒∗ γAx ⇒ γαβx

Tétel: az LR(0) elemzés nagy tétele Egy γ járható prefix hatására az elemző automatája a kezdőállapotból olyan állapotba kerül, amelyhez tartozó kanonikus halmaz éppen a γ járható prefixre érvényes LR(0) elemeket tartalmazza.

Az érvényes LR(0) elemek az adott járható prefix „lehetséges folytatásait” adják meg. Példa: az ab járható prefixre érvényes LR(0)-elemek: [A → b.A], [A → .bA], [A → .c]. S ′ ⇒ S ⇒ aAd ⇒ abAd S ′ ⇒ S ⇒ aAd ⇒ abAd ⇒ abbAd S ′ ⇒ S ⇒ aAd ⇒ abcd A maximális járható prefixekre érvényes LR(0) elemek azok, ahol a pont a szabály végén van. 50



51





Az LR(0) elemzés helyessége

Konfliktusok a táblázatban Hol használtuk ki, hogy LR(0) a grammatika?

Tétel: az LR(0) elemzés nagy tétele Egy γ járható prefix hatására az elemző automatája a kezdőállapotból olyan állapotba kerül, amelyhez tartozó kanonikus halmaz éppen a γ járható prefixre érvényes LR(0) elemeket tartalmazza. Az elemző tehát addig fog léptetést előírni, amíg a veremben lévő járható prefix maximális nem lesz. Ha a járható prefix maximális, akkor az elemző redukálást ír elő.

51



52





Konfliktusok a táblázatban

Konfliktusok a táblázatban

Hol használtuk ki, hogy LR(0) a grammatika?

Hol használtuk ki, hogy LR(0) a grammatika?

Konfliktus: Ha egy Ik kanonikus halmaz alapján nem lehet egyértelműen eldönteni, hogy az adott állapotban milyen akciót kell végrehajtani.

Konfliktus: Ha egy Ik kanonikus halmaz alapján nem lehet egyértelműen eldönteni, hogy az adott állapotban milyen akciót kell végrehajtani.

léptetés/redukálás konfliktus: az egyik elem léptetést, egy másik redukálást ír elő redukálás/redukálás konfliktus: az egyik elem az egyik szabály szerinti, a másik egy másik szabály szerinti redukciót ír elő

léptetés/redukálás konfliktus: az egyik elem léptetést, egy másik redukálást ír elő redukálás/redukálás konfliktus: az egyik elem az egyik szabály szerinti, a másik egy másik szabály szerinti redukciót ír elő

Az LR(0) tulajdonság biztosítja a táblázat konfliktusmentes kitöltését!

52



52



Az LR elemző felépítése. Léptetés. Redukálás. Kiegészített grammatika. Mit kell redukálni? Kiegészített grammatika. elemző. elemző

Recommend Documents