Sziasztok!


A mai óra anyaga: LL(k)elemzés. Címszavakban a következőkről van szó (pontosabban lásd a jegyzetet, illetve az első három feladat megoldása részletesen végigszámolva fent van(első, második, harmadik):

1. LL(k) nyelvtanok, erős LL(k) nyelvtan. Erre volt órán az 1. feladat.

2. Lehet egy nyelvtan úgy is LL(k) , hogy nem erős LL(k) , hanem gyenge LL(k) , erre megnéztük a 2/a és b-t.

3. Hogyan lehet észrevenni egy gyenge LL(k) elemzőről, hogy az erős és miért éri meg ekkor is gyengét csinálni, noha az nagyobb macera.
Nem volt már rá idő , de nézzétek meg, előadáson szerepel: két elemző mikor ekvivalens, mikor gyengén ekvivalens és mikor nem ekvivalens. Ehhez volt a 3. példa.

4. Faktorizáció: Ha egy nyelvtan LL(k) és van két olyan szabálya, hogy $A\ensuremath{\rightarrow}\alpha \beta$ és $A\ensuremath{\rightarrow}\alpha \gamma$ , azaz két szabály, aminek baloldala ugyanaz és a jobboldalak ugyanúgy kezdődnek, akkor egy faktorizációnak nevezett eljárással csökkenthető a k : az $A\ensuremath{\rightarrow}\alpha X$ és $X\ensuremath{\rightarrow}\beta\;\vert\;\gamma$ szabályokat vesszük be inkább. Meggondolni, hogy ez mért jó és használni ezt a módszert például a 6. feladatban.

Gyakoroljatok!!!!

Csináljátok meg az utolsó példát mindenképpen, hogy lássatok valami nehezet is. Ha bármilyen példát megcsináltok és szeretnétek tudni, hogy jó-e, akkor szivesen kijavítom, meg a konzin is meg lehet kérdezni.

Formális nyelvek gyakorlat (11)
2000. november 20., hétfő




1. Egy CF nyelvet az $S\ensuremath{\rightarrow} SaSb\;\vert\;\epsilon$ nyelvtan definiál.
Készíts erre a nyelvre (erős) LL(k) elemzőt minél kisebb k -val! Ezután elemezd az aababb szót!

Megoldás

2. Nézzük az $S\ensuremath{\rightarrow} aAaa\;\vert\;bAba$ , $A\ensuremath{\rightarrow} b\;\vert\;\epsilon$ nyelvtant.
(a) Igaz-e, hogy ez a nyelvtan erős LL(2) nyelvtan?
(b) Készítsünk a nyelvtanhoz gyenge LL(2) elemzőt!
(c) Mutassuk meg, hogy ez nem gyenge LL(1) nyelvtan!

Megoldás

3. Egy CF nyelvet az $S\ensuremath{\rightarrow} SaSab\;\vert\;\epsilon$ nyelvtan definiál.
(a) Készíts erre a nyelvre gyenge LL(k) elemzőt minél kisebb k -val!
(b) Ezután elemezd az aaababaab szót!
(c) Készíts az (a)-ban adott gyenge elemzőből erőset, aztán nézd meg, hogy hogyan viselkedik a gyenge és az erős az aabab szón!

Megoldás

Aki gondolkodni is akar, nem csak számolni:

4. Gondoljuk meg, hogy
(a) mit jelent az, hogy egy nyelvtan LL(0) tulajdonságú?
(b) miért nem LL(k) elemezhető egy balrekurzív nyelvtan?
(c) miért biztos az, hogy egy nemegyértelmű nyelvtan nem LL(k) elemezhető?
(d) van-e olyan L nyelv és olyan k szám, hogy L -re csak gyenge LL(k) elemző készíthető, erős nem?

Gyakorolni

5. Egyszerű
a) Készíts LL(1) elemzőtáblát az alábbi egyszerű szintaxisvezérelt fordítási séma első nyelvtanához,
b) elemezd segítségével az aabbbb jelsorozatot,
c) és állítsd elő a mondat fordítását!



$S\ensuremath{\rightarrow} aAbb,$aA

$A\ensuremath{\rightarrow} S$ ,		Sbb

$A\ensuremath{\rightarrow}\epsilon$ ,		bb  
6. Bonyolultabb
Készíts LL(k) elemzőt az $E\ensuremath{\rightarrow} EE+\;\vert\;EE*\;\vert\;a$ nyelvtan által generált nyelvre minél kisebb k -val! A lokális FOLLOW függvények alapján történő felhasítással biztosítsd a legrészletesbb hibajelzést! Vizsgáld meg, hogy az elemző elkészítésére használt nyelvtan erős LL(k) nyelvtan-e! Ha erős, akkor hasonlítsd össze az erős és a gyenge elemzőt és keress olyan jelsorozatot amin a két elemző máshogy működik!