Formális nyelvek gyakorlat (10-11)

2005. november 24. és december 1., csütörtök



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!

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!

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!

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 (azzal a $k$-val, amivel gyenge)! 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!