Formális nyelvek gyakorlat (12) 2001., május 1., kedd Az elsõ példa elõadáson szerepelt megoldással. 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!