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 van 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. 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!