Emlékeztető: LR(0) elemzés. LR elemzések (SLR(1) és LR(1) elemzések)

Emlékeztető

Emlékeztető: LR(0) elemzés A lexikális elemző által előállított szimbólumsorozatot balról jobbra olvassuk, a szimbólumokat az elemző vermébe tesszük.

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

1

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

LR elemzések (SLR(1) és LR(1) elemzések)

2


Emlékeztető

Emlékeztető

Emlékeztető: LR(0) elemzés



A lexikális elemző által előállított szimbólumsorozatot balról jobbra olvassuk, a szimbólumokat az elemző vermébe tesszük.

A lexikális elemző által előállított szimbólumsorozatot balról jobbra olvassuk, a szimbólumokat az elemző vermébe tesszük.

Léptetés: egy új szimbólumot teszünk a bemenetről a verem tetejére.

Léptetés: egy új szimbólumot teszünk a bemenetről a verem tetejére.

Redukálás: a verem tetején lévő szabály-jobboldalt helyettesítjük a szabály bal oldalán álló nemterminálissal.

Redukálás: a verem tetején lévő szabály-jobboldalt helyettesítjük a szabály bal oldalán álló nemterminálissal. LR(0): az alkalmazandó műveletről előreolvasás nélkül döntünk. A háttérben egy véges determinisztikus automata működik: az automata átmeneteit a verem tetejére kerülő szimbólumok határozzák meg ha az automata végállapotba jut, redukálni kell egyéb állapotban pedig léptetni

2



2


Emlékeztető

Emlékeztető




Lezárás (closure) művelet: segítségével adhatók meg az egy kanonikus halmazba tartozó LR(0)-elemek.

Az automata állapotai a kanonikus halmazok. „Melyik szabály építésében hol tartunk éppen?” elemei az LR(0)-elemek

Lezárás closure([S → a.Ad ]) = {[S → a.Ad ], [A → .bA], [A → .c]}

Kanonikus halmaz és jelentése A {[S → a.Ad ], [A → .bA], [A → .c]} kanonikus halmaz jelentése: „Az adott állapotban az S → aAd , A → bA és A → c szabályok jobboldalait építhetjük. A S → aAd szabályból az a szimbólumot már elemeztük, az Ad rész még hátra van. A másik két szabály építése most kezdődhet.”

3



4



Emlékeztető

Emlékeztető



Lezárás (closure) művelet: segítségével adhatók meg az egy kanonikus halmazba tartozó LR(0)-elemek.

S′ → S S

Lezárás closure([S → a.Ad ]) = {[S → a.Ad ], [A → .bA], [A → .c]}

0

Olvasás (read) művelet: megadja, hogy egy kanonikus halmazból egy adott szimbólum olvasásával melyik kanonikus halmazba jutunk. Ezek lesznek az automata átmenetei.



5

S 0 állapot 0 1 2 3 4 5 6 7 6

a

2

b

4

6 A c

S → aAd c 7

A → bA

A→c 5


Probléma az LR(0)-elemzéssel

d b

6 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)


b

b

Konfliktusok

3 A

2


Emlékeztető

1

A

Elfogadó állapot: „a hozzá tartozó elemeknek a végén van a pont”

Emlékeztető: LR(0) elemzés S′ → S

a

d

3

... I2 = {[S → a.Ad ], [A → .bA], [A → .c]} ... I4 = read (I2 , b) = {[A → b.A], [A → .bA], [A → .c]} I5 = read (I2 , c) = read (I4 , c) = {[A → c.]}

Olvasás read ({[S → a.Ad ], [A → .bA], [A → .c]}, b) = = closure([A → b.A]) = = {[A → b.A], [A → .bA], [A → .c]} 4

1

S 1

S → aAd c

Az LR(0) tulajdonság biztosította, hogy a táblázat egy cellájába sem kerül két különböző műveletet, azaz a táblázat konfliktusmentes. Mi történik, ha nem LR(0) a grammatika?

A→c

7

A → bA

5

A

a 2

d

b

c

3

4

5

7

4

5

6


7





Konfliktusok

Konfliktusok



A helyes zárójelezés


S′ → S S → ǫ | (S)S

S′ → S S → ǫ | (S)S S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒() S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒ ((S)S) ⇒ ((S)) ⇒(())

7



7





Konfliktusok

Példa: helyes zárójelezés

Az LR(0) tulajdonság biztosította, hogy a táblázat egy cellájába sem kerül két különböző műveletet, azaz a táblázat konfliktusmentes. Mi történik, ha nem LR(0) a grammatika? Példa grammatika


1

S′ → S S → ǫ | (S)S

2

S′ → S S → ǫ | (S)S

0 S →ǫ

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

S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒() S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒ ((S)S) ⇒ ((S)) ⇒(()) Az piros részek elolvasása után: az első esetben S → ǫ szerinti redukciót kell végrahajtani, a második esetben léptetni kell. Előreolvasás nélkül nem tudunk dönteni, nem LR(0) grammatika. 7



8






S′ → S

S′ → S

2

S

S′ → S S → ǫ | (S)S

0

S

1

S′

2

S → ǫ | (S)S

→S

closure([S ′


10

S′ → S

1 S

S′ → S 0

S →ǫ I0 I1 I2 I3

11



Példa grammatika S → ǫ | (S)S

S →ǫ

Példa: helyes zárójelezés S′ → S

2

2

{[S ′




1

(

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

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


0 S →ǫ

S →ǫ

9

1

Példa grammatika

1

Példa grammatika 1


(

3 S 2

S →ǫ


1

S′ → S

2

S → ǫ | (S)S

S 0 S →ǫ

(

3 ( S 2

S →ǫ

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

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


1

Példa grammatika

12







1 2

S

S′ → S S → ǫ | (S)S

( S

(

0 S →ǫ

)

2

4

S →ǫ

S →ǫ


1

S′

2

S → ǫ | (S)S

S

→S


1 S 0 S →ǫ

14

4

S →ǫ

S →ǫ

{[S ′


S → (S)S


3 ( S

(

2 S →ǫ

(

5 )


1

S

S

4

0

S →ǫ

S →ǫ


S → (S)S

S′ → S

I0 = closure([S ′ → .S]) = {[S ′ → .S], [S → .], [S → .(S)S]} I1 = read (I0 , S) = {[S ′ → S.]} I2 = read (I0 , () = {[S → (.S)S], [S → .], [S → .(S)S]} I3 = read (I2 , S) = {[S → (S.)S]} read (I2 , () = {[S → (.S)S], [S → .], [S → .(S)S]} = I2 I4 = read (I3 , )) = {[S → (S).S], [S → .], [S → .(S)S]} I5 = read (I4 , S) = {[S → (S)S.]} read (I4 , () = {[S → (.S)S], [S → .], [S → .(S)S]} = I2 15

S

2


Példa grammatika S → ǫ | (S)S

(

Konfliktusok az LR(0) elemző táblázatban S′ → S

2

5 )

→ .S]) = → .S], [S → .], [S → .(S)S]} I0 = I1 = read (I0 , S) = {[S ′ → S.]} I2 = read (I0 , () = {[S → (.S)S], [S → .], [S → .(S)S]} I3 = read (I2 , S) = {[S → (S.)S]} read (I2 , () = {[S → (.S)S], [S → .], [S → .(S)S]} = I2 I4 = read (I3 , )) = {[S → (S).S], [S → .], [S → .(S)S]} I5 = read (I4 , S) = {[S → (S)S.]}


S′ → S

3 ( S

S →ǫ


1

0

closure([S ′

I0 = closure([S ′ → .S]) = {[S ′ → .S], [S → .], [S → .(S)S]} I1 = read (I0 , S) = {[S ′ → S.]} I2 = read (I0 , () = {[S → (.S)S], [S → .], [S → .(S)S]} I3 = read (I2 , S) = {[S → (S.)S]} read (I2 , () = {[S → (.S)S], [S → .], [S → .(S)S]} = I2 I4 = read (I3 , )) = {[S → (S).S], [S → .], [S → .(S)S]} 13

1

Példa grammatika

3

1

Példa grammatika

S → (S)S

S′ → S

S′ → S

0 1 2 3 4 5 16

(

3 ( S 2

(

S →ǫ

5 )

S 4 S →ǫ

akció léptetés / redukálás (S → ǫ) OK léptetés / redukálás (S → ǫ) léptetés léptetés / redukálás (S → ǫ) redukálás (S → (S)S)


Az SLR(1) elemzés

S 1

( 2

3

2 4 (

5

)


Az SLR(1) elemzés

Az SLR(1) elemzés alapötlete

Az SLR(1) elemzés alapötlete

Olvassunk előre egy szimbólumot!

Olvassunk előre egy szimbólumot!

léptessünk, ha az automata tud lépni az előreolvasott szimbólummal redukáljunk, ha az előreolvasott szimbólum benne van a szabályhoz tartozó nemterminális FOLLOW1 halmazában

léptessünk, ha az automata tud lépni az előreolvasott szimbólummal redukáljunk, ha az előreolvasott szimbólum benne van a szabályhoz tartozó nemterminális FOLLOW1 halmazában

A helyes zárójelezés S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒() S ′ ⇒ S ⇒ (S)S ⇒ (S) ⇒ ((S)S) ⇒ ((S)) ⇒(()) I2 = {[S → (.S)S], [S → .], [S → .(S)S]} Az piros részek elolvasása után I2 állapotban van az automata: az első esetben S → ǫ szerinti redukciót kell végrahajtani, mert ) ∈ FOLLOW1 (S). a második esetben léptetni kell, mert [S → .(S)S] ∈ I2 . 17



17



Az SLR(1) elemzés

Az SLR(1) elemzés

Az SLR(1) elemzés szabályai

A helyes zárójelezés SLR(1) elemző táblázata S → (S)S

S′ → S 1

Ha az aktuális állapot i, és az előreolvasás eredménye az a szimbólum:

S

ha [A → α.aβ] ∈ Ii és read (Ii , a) = Ij , akkor léptetni kell, és átlépni a j állapotba, ha [A → α.] ∈ Ii (A 6= S ′ ) és a ∈ FOLLOW1 (A), akkor redukálni kell A → α szabály szerint, ha [S ′ → S] ∈ Ii és a = #, akkor el kell fogadni a szöveget, minden más esetben hibát kell jelezni.

0

0 1 2 3 4 5

Ha az i állapotban A kerül a verem tetejére: ha read (Ii , A) = Ij , akkor át kell lépni a j állapotba, egyébként hibát kell jelezni.

18


(

S →ǫ


19

2 S →ǫ

4 S →ǫ

léptetés, 2

redukálás (S → ǫ) léptetés, 4 redukálás (S → ǫ) redukálás (S → (S)S)


# redukálás (S → ǫ) OK redukálás (S → ǫ)

S 1

redukálás (S → ǫ) redukálás (S → (S)S)

5

3


Az SLR(1) elemzés

( léptetés, 2

) redukálás (S → ǫ)

léptetés, 2


léptetés, 2


S 1


5

0 1 2 3 4 5

3

( léptetés, 2


léptetés, 2


léptetés, 2


S 1


5

(())#

(())#

(())#

elemző

elemző

elemző


21


Az SLR(1) elemzés

3

(2 #0

#0


Az SLR(1) elemzés

Példa

Példa ( léptetés, 2


léptetés, 2


léptetés, 2


S 1


5

(())# elemző (2 #0 22

FOLLOW1 (S) = { ), # }

S

Példa


0 1 2 3 4 5

)


léptetés, 2

#0 20

(

5

( léptetés, 2

Az SLR(1) elemzés

Példa

0 1 2 3 4 5

3 ( S


0 1 2 3 4 5

3

( léptetés, 2


léptetés, 2


léptetés, 2

(())#

(2 (2 #0

S 1


5

(())#

elemző



(2 (2 #0 23

elemző


(())# S3 (2 (2 #0

elemző


3

Az SLR(1) elemzés

Az SLR(1) elemzés

Példa

0 1 2 3 4 5



léptetés, 2


léptetés, 2


S 1


5

(())# S3 (2 (2 #0 24

3

( léptetés, 2


léptetés, 2


léptetés, 2

(())# )4 S3 (2 (2 #0

elemző


0 1 2 3 4 5

(())# )4 S3 (2 (2 #0

elemző


25

Az SLR(1) elemzés

( léptetés, 2


léptetés, 2


léptetés, 2


S 1


5

(())#

0 1 2 3 4 5

3


elemző

léptetés, 2


léptetés, 2

S3 (2 #0


S 1


5

(())#

elemző

S3 (2 #0


27

3

(())#

elemző


Az SLR(1) elemzés

)4 S3 (2 #0

elemző


Az SLR(1) elemzés

Példa



léptetés, 2


léptetés, 2


S 1


5

(())# )4 S3 (2 #0 28

(())#


( léptetés, 2

(())#

elemző


0 1 2 3 4 5

5

Példa

S5 )4 S3 (2 (2 #0 26


3

Az SLR(1) elemzés

Példa

0 1 2 3 4 5

S 1

S5 )4 S3 (2 (2 #0

elemző



elemző


0 1 2 3 4 5

3

( léptetés, 2


léptetés, 2


léptetés, 2

(())# S5 )4 S3 (2 #0

S5 )4 S3 (2 #0

elemző


29


S 1


5

(())#

(())#

elemző

elemző


S1 #0 LR elemzések (SLR(1) és LR(1) elemzések)

3

Az SLR(1) elemzés

Az SLR(1) elemzés

Példa

0 1 2 3 4 5

SLR(1) grammatika ( léptetés, 2


léptetés, 2


léptetés, 2


S 1


5

Definíció: SLR(1) grammatika Egy kiegészített grammatika SLR(1) grammatika, ha az SLR(1) elemző táblázata konfliktusmentes.

3

elnevezés: „Simple LR” jobb, mint az LR(0)

(())#

a valódi programnyelvek nyelvtanai általában nem SLR(1) nyelvtanok

elemző

OK

S1 #0 30



31


Probléma az SLR(1) elemzéssel




Példa grammatika S′ → S S →U|E U→a E →V =V V →a



Egy program az egy utasítás vagy egy értékadás. Egy utasítás az egy azonosító szimbólum. Egy értékadás változó legyen egyenlő változó alakú. Egy változó az egy azonosító szimbólum.

Egy program az egy utasítás vagy egy értékadás. Egy utasítás az egy azonosító szimbólum. Egy értékadás változó legyen egyenlő változó alakú. Egy változó az egy azonosító szimbólum.

I0 = {[S ′ → .S], [S → .U], [S → .E ], [U → .a], [E → .V = V ], [V → .a]} ... I4 = read (I0 , a) = {[U → a.], [V → a.]}

32



32








I4 = read (I0 , a) = {[U → a.], [V → a.]}

Egy program az egy utasítás vagy egy értékadás.

FOLLOW1 (U) = {#} és FOLLOW1 (V ) = {=,#} Redukálás / redukálás konfliktus!

Egy utasítás az egy azonosító szimbólum. Egy értékadás változó legyen egyenlő változó alakú. Egy változó az egy azonosító szimbólum.

I0 = {[S ′ → .S], [S → .U], [S → .E ], [U → .a], [E → .V = V ], [V → .a]} ... I4 = read (I0 , a) = {[U → a.], [V → a.]} FOLLOW1 (U) = {#} és FOLLOW1 (V ) = {=,#} Redukálás / redukálás konfliktus! 32



33







I4 = read (I0 , a) = {[U → a.], [V → a.]}

I4 = read (I0 , a) = {[U → a.], [V → a.]}



Az a# szövegből az a elolvasása után az SLR(1) elemző nem tud dönteni a U → a és V → a szerinti redukciók között, mert a következő szimbólum (#) benne van az U és a V FOLLOW1 halmazában is.

Az a# szövegből az a elolvasása után az SLR(1) elemző nem tud dönteni a U → a és V → a szerinti redukciók között, mert a következő szimbólum (#) benne van az U és a V FOLLOW1 halmazában is. Pedig a szöveg elején a V -t csak az = szimbólum követheti...

33



33


Az LR(1) elemzés

Az LR(1) elemzés

Az LR(1) elemzés alapötlete

Az LR(1) elemzés alapötlete


a FOLLOW1 halmaz globális az egész grammatikára

a FOLLOW1 halmaz globális az egész grammatikára

előfordulhat, hogy egy adott állapotban a FOLLOW1 halmaznak nem minden eleme követheti a szabályt

előfordulhat, hogy egy adott állapotban a FOLLOW1 halmaznak nem minden eleme követheti a szabályt Vegyük hozzá az LR(0) elemekhez azokat a szimbólumokat, amik követhetik a szabályt az adott állapotban!

34


Az LR(1) elemzés


34


Az elemző létrehozása

LR(1) elemek

Az LR(1) elemzés



LR(1) elemek

Definíció: LR(1) elem

Definíció: LR(1) elem

Ha A → α a grammatika egy helyettesítési szabálya, akkor az α = α1 α2 tetszőleges felbontás és a terminális szimbólum (vagy a = #) esetén [A → α1 .α2 , a] a grammatika egy LR(1)-eleme. A → α1 .α2 az LR(1) elem magja, a pedig az előreolvasási szimbóluma.

Ha A → α a grammatika egy helyettesítési szabálya, akkor az α = α1 α2 tetszőleges felbontás és a terminális szimbólum (vagy a = #) esetén [A → α1 .α2 , a] a grammatika egy LR(1)-eleme. A → α1 .α2 az LR(1) elem magja, a pedig az előreolvasási szimbóluma. [V → a. , =] jelentése: a V → a szabály építését befejeztük és a szabályt az = szimbólum követheti.

35



35



Az LR(1) elemzés


A lezárás művelet

Az LR(1) elemzés


A lezárás művelet

Ha [V → .V = V , #] állapotban vagyunk, akkor a V → a szabályt kezdhetjük építeni, amit az = szimbólum követhet.

Ha [V → .V = V , #] állapotban vagyunk, akkor a V → a szabályt kezdhetjük építeni, amit az = szimbólum követhet.

Tehát az adott kanonikus halmazhoz [V → .a, =] is hozzátartozik.

Tehát az adott kanonikus halmazhoz [V → .a, =] is hozzátartozik. Definíció: lezárás (closure) Ha I a grammatika egy LR(1) elemhalmaza, akkor closure(I) a legszűkebb olyan halmaz, amely az alábbi tulajdonságokkal rendelkezik: I ⊆ closure(I) ha [A → α.Bγ,a] ∈ closure(I), és B → β a grammatika egy szabálya, akkor ∀b ∈ FIRST1 (γa) esetén [B → .β,b] ∈ closure(I)

36


Az LR(1) elemzés


36



Az olvasás művelet

Az LR(1) elemzés



Az olvasás művelet

Ha [V → .V = V , #] állapotban vagyunk, és V kerül a verem tetejére, akkor [V → V . = V , #] állapotba jutunk.

Ha [V → .V = V , #] állapotban vagyunk, és V kerül a verem tetejére, akkor [V → V . = V , #] állapotba jutunk. Definíció: olvasás (read) Ha I a grammatika egy LR(1) 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 β,a] ∈ I, akkor closure([A → αX .β,a]) ⊆ read (I, X ).

37


Az LR(1) elemzés


37


LR(1) kanonikus halmazok

Az LR(1) elemzés



Az LR(1) elemzés szabályai Ha az aktuális állapot i, és az előreolvasás eredménye az a szimbólum:

Definíció: LR(1) kanonikus halmazok 1


ha [A → α.aβ, b] ∈ Ii és read (Ii , a) = Ij , akkor léptetni kell, és átlépni a j állapotba, ha [A → α., a] ∈ Ii (A 6= S ′ ), akkor redukálni kell A → α szabály szerint, ha [S ′ → S., #] ∈ Ii és a = #, akkor el kell fogadni a szöveget, minden más esetben hibát kell jelezni.

closure([S ′ → .S, #]) 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.

Ha az i állapotban A kerül a verem tetejére: ha read (Ii , A) = Ij , akkor át kell lépni a j állapotba, egyébként hibát kell jelezni.

38



39



Az LR(1) elemzés

Példa

Az LR(1) elemzés

Példa

Példa

Példa grammatika S′ → S

Példa

Példa grammatika

S →U|E

U→a

E →V =V

S′ → S

V →a

S →U|E

U→a

E →V =V

V →a

I0 = closure([S ′ → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]}

40


Az LR(1) elemzés


40

Példa

Az LR(1) elemzés

Példa

U→a

E →V =V

S′ → S

V →a


Az LR(1) elemzés


U→a

E →V =V

V →a

I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]}

40


Példa

Az LR(1) elemzés

Példa


Példa

Példa

Példa grammatika S →U|E

Példa grammatika U→a

E →V =V

S′ → S

V →a

′



S →U|E

U→a

E →V =V

V →a

′

I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]}

40

S →U|E ′

I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]}

S′ → S

Példa

Példa grammatika

S →U|E ′

40


Példa



I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]} I4 = read (I0 , a) = {[U → a., #], [V → a., =]} Nincs konfliktus!

40



Az LR(1) elemzés

Példa

Az LR(1) elemzés

Példa

Példa


Példa grammatika

S →U|E

U→a

E →V =V

S′ → S

V →a

I0 = closure([S ′ → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]} I4 = read (I0 , a) = {[U → a., #], [V → a., =]} Nincs konfliktus! I5 = read (I0 , V ) = {[E → V . = V , #]}

40


Az LR(1) elemzés


40


Az LR(1) elemzés

V →a


Példa

Példa grammatika

S →U|E

U→a

E →V =V

S′ → S

V →a


Az LR(1) elemzés


U→a

E →V =V

V →a

I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]} I4 = read (I0 , a) = {[U → a., #], [V → a., =]} Nincs konfliktus! I5 = read (I0 , V ) = {[E → V . = V , #]} I6 = read (I5 , =) = {[E → V = .V , #], [V → .a, #]} I7 = read (I6 , V ) = {[E → V = V ., #]} I8 = read (I6 , a) = {[V → a., #]}

40


Példa

Az elemző táblázat kitöltése

Az LR(1) elemzés


Példa


I0 = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} read (I0 , S) = I1 x = # S U E V

I0 = {[S ′ → .S, #],[S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} read (I0 , U) = I2 x = # S U E V

1

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8


S →U|E ′

I0 = closure([S → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]} I4 = read (I0 , a) = {[U → a., #], [V → a., =]} Nincs konfliktus! I5 = read (I0 , V ) = {[E → V . = V , #]} I6 = read (I5 , =) = {[E → V = .V , #], [V → .a, #]} I7 = read (I6 , V ) = {[E → V = V ., #]}

41

E →V =V

Példa

′

0

U→a

I0 = closure([S ′ → .S, #]) = = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} I1 = read (I0 , S) = {[S ′ → S., #]} I2 = read (I0 , U) = {[S → U., #]} I3 = read (I0 , E ) = {[S → E ., #]} I4 = read (I0 , a) = {[U → a., #], [V → a., =]} Nincs konfliktus! I5 = read (I0 , V ) = {[E → V . = V , #]} I6 = read (I5 , =) = {[E → V = .V , #], [V → .a, #]}

Példa grammatika

40

S →U|E

Példa

Példa

S′ → S

Példa


42

1

2



Az LR(1) elemzés

Példa

Az LR(1) elemzés



I0 = {[S ′ → .S, #], [S → .U, #],[S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} read (I0 , E ) = I3 x = # S U E V 0

1

2

I0 = {[S ′ → .S, #], [S → .U, #], [S → .E , #],[U → .a, #], [E → .V = V , #],[V → .a, =]} read (I0 , a) = I4 a = # S U E V

3

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

43



Az LR(1) elemzés

44

1

2

3

a

5

0 2

3

3

4

4

5

5

6

6

7

7

8

8


46

47

=

Példa

#

S

U

E

V

1

2

3

5

OK


Az LR(1) elemzés


Példa


I2 = {[S → U., #]}

a

=

léptetés, 4

Példa


0


I1 = {[S ′ → S., #]}

2

Az LR(1) elemzés

3

Az LR(1) elemzés

1


2


1

45

1


I0 = {[S ′ → .S, #], [S → .U, #], [S → .E , #], [U → .a, #], [E → .V = V , #], [V → .a, =]} read (I0 , V ) = I5 a = # S U E V léptetés, 4

léptetés, 4

Példa


0

Példa

I3 = {[S → E ., #]}

#

léptetés, 4

S

U

E

V

1

2

3

5

a 0

=

#

léptetés, 4

1

OK

1

OK

2

redukálás, S → U

2


3

3

redukálás, S → E

4

4

5

5

6

6

7

7

8

8



48


S

U

E

V

1

2

3

5


Az LR(1) elemzés

Példa

Az LR(1) elemzés


Az elemző táblázat kitöltése I4 = {[U → a., #],[V → a., =]}

I4 = {[U → a., #], [V → a., =]}

a 0

=

#

léptetés, 4

1

OK

2


3


4

redukálás, U → a

S

U

E

V

1

2

3

5

a 0

OK

2


V

3

5

redukálás, S → E redukálás, V → a


8

Az LR(1) elemzés


50

Az LR(1) elemzés


Példa


I5 = {[E → V . = V , #]} read (I5 , =) = I6 a


Példa


I6 = {[E → V = .V , #], [V → .a, #]} read (I6 , V ) = I7 =

#

léptetés, 4

S

U

E

V

1

2

3

5

a 0

=

#

léptetés, 4

1

OK

1

OK

2


2


3


3


4

redukálás, V → a

5

léptetés, 6

4


5

léptetés, 6

6

6

7

7

8

8


Az LR(1) elemzés


52

=


Példa

I7 = {[E → V = V ., #]}

#

S

U

E

V

1

2

3

5

a 0

=

#

léptetés, 4

1

OK

2


2


3


3


4


5

léptetés, 6

léptetés, 6 léptetés, 8

6

7

7

7

8

8


5


OK

5

V

3


1


E

2

7

Az LR(1) elemzés

léptetés, 4

4

U

1


I6 = {[E → V = .V , #],[V → .a, #]} read (I6 , a) = I8 a

S


Példa


6

E

2

7


0

U

1

6

8

51

S

5

7

53

#

1

4

6

0

=

léptetés, 4

3

5

49

Példa


54

S

U

E

V

1

2

3

5

redukálás, S → E redukálás, U → a

léptetés, 8

7 redukálás, E → V = V



Az LR(1) elemzés

Példa

Az LR(1) elemzés


Az a# szöveg elemzése

I7 = {[V → a., #]}

a 0

a 0

=

#

léptetés, 4

1

OK

2


3


4


5 6

S

U

E

V

1

2

3

5

léptetés, 6 7 redukálás, E → V = V

8


#

1

OK

2

redukálás, S → U redukálás, V → a

5

léptetés, 6

Az LR(1) elemzés

a



8


56

Az LR(1) elemzés


Példa

#

S

U

E

V

1

2

3

5

a 0

=

#

léptetés, 4

OK

1

OK

2


2


3


3


4


5

léptetés, 6

léptetés, 6

6

léptetés, 8

7

6

8


8


57

a#


Az LR(1) elemzés

a4 #0


58

a 0

=

U2 #0

elemző


Példa

Az LR(1) elemzés


elemző


Példa

Az a# szöveg elemzése #

léptetés, 4

S

U

E

V

1

2

3

5

a 0

=

#

léptetés, 4

1

OK

1

OK

2


2


3


3


4


5

léptetés, 6

4


5

léptetés, 6

6

léptetés, 8

7

6

8


8



a#

5

a# S1 #0

elemző


V

3


S1 #0

E

2

léptetés, 8

7

elemző

U

1


redukálás, E → V = V

a#

S


7

U2 #0

5

a#

a#

elemző

V

3


a4 #0

E

2

léptetés, 8

7

elemző

U

1


redukálás, E → V = V

#0

S


7

a#

59


elemző

1

5

5


=


V

3

léptetés, 8

Példa

léptetés, 4

4

E

2

a#


0

U

1


7

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

S


4 6

léptetés, 8

=

léptetés, 4

3


7

55

Példa

60

elemző


OK LR elemzések (SLR(1) és LR(1) elemzések)

Az LR(1) elemzés

Az elemzés helyessége

Az LR(1) elemző táblázat konfliktusmentessége

Az LR(1) elemzés


Az LR(1) elemző létrehozása véges

az LR(1)-elemek száma véges a closure és read függvények kiszámítása véges

Tétel Egy grammatika pontosan akkor LR(1) grammatika, ha az LR(1) elemző táblázatai konfliktusmentesek.

a kanonikus halmazok száma véges a kanonikus halmazok kiszámítása véges Az LR(1) elemző a megadott módon véges sok lépésben és teljesen automatikusan létrehozható.

61


Az LR(1) elemzés


62


Járható prefix, érvényes LR-elem


Az LR(1) elemzés




járható prefix: a mondatformának olyan prefixei, amelyek legfeljebb a nyél végéig tartanak


ezeket járja be az elemző automata a maximális járható prefixnek a végén ott a teljes nyél


járható prefixre érvényes LR-elemek: a járható prefix „lehetséges folytatásai” melyik szabályok építésében hol tarthatunk egy adott járható prefix elemzése után?

63


Az LR(1) elemzés


63




Az LR(1) elemzés



Az LR(1) elemzés helyessége


Az LR(1)-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(1) elemeket tartalmazza.


járható prefixre érvényes LR-elemek: a járható prefix „lehetséges folytatásai” melyik szabályok építésében hol tarthatunk egy adott járható prefix elemzése után?

Definíció: Járható prefixre érvényes LR(1)-elem A grammatika egy [A → α.β, a] LR(1)-eleme érvényes a γα járható prefixre nézve, ha S ′ ⇒∗ γAx ⇒ γαβx, és x 6= ǫ esetén a az x első szimbóluma, x = ǫ esetén pedig a = #. 63



64



Az LR(1) elemzés


Az LR(1) elemzés helyessége Az LR(1)-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(1) elemeket tartalmazza. Összefoglalva: az LR(1) elemző automatikusan és véges lépésben generálható a nyelvtan szabályaiból minden LR(1) grammatika elemezéséhez használható az elemző mindig a helyes lépést írja elő a fenti tétel miatt

Probléma: túl sok állapota van... 64



Emlékeztető: LR(0) elemzés. LR elemzések (SLR(1) és LR(1) elemzések)

Recommend Documents