10. gyakorlat

1. feladat A Cocke-Younger-Kasami módszer segítségével határozzuk meg az aabbbc szó összes jobboldali levezetését, ha a nyelvtan a következõ: S -> AB A -> aAb | ab B -> bBc | bc 2. feladat Legyen a nyelvtanunk a következõ: S -> bDPe D -> dvD | dv P -> uvP | uv Elemezzük az Earley-algoritmussal a bdvuvuve szót! 3. feladat Adott az alábbi nyelvtan: S -> aSbS | aS | epszilon Elemezzük az Earley-algoritmussal az aab, illetve az abb szót! 4. feladat A CYK elemzéssel elemezzük az S -> aSa | bSb | aa | bb nyelvtanban az abbbba és az abbba szót! 5. feladat A CYK algoritmussal elemezzük az E -> E+E | E*E | a nyelvtanban az a+a*a+a, illetve az a++a szót! Döntsük el, hogy generálhatók-e nyelvtannal! Egyértelmûen generálhatók? Adjuk meg a levezetési fákat is! 6. feladat Earley-algoritmussal elemezzük az a+a*a szót az E -> E+E | E*E | a nyelvtanban! Gondoljuk végig, hogy hol látszik az elemzésben az, hogy nem egyértelmû a nyelvtan! 7. feladat Tekintsük az alábbi nyelvtant: S -> AB A -> aAb | ab B -> bBc | epszilon LL(1) elemezhetõ-e a nyelvtan? Készítsünk LL(2) elemzõt, és elemezzük az abbc mondatot! LL(1) elemezhetõ-e a nyelv? Ha igen, hogyan? Készítsük el a gyenge LL(k) nyelvtanokra jellemzõ táblácskákat (a nemterminálisok megkülönböztetésével)! 8. feladat Tekintsük az alábbi nyelvtant: S -> aSbS | bSaS | epszilon k mely értékeire lesz LL(k) elemezhetõ? 9. feladat Készíts LL(k) elemzõt a reguláris kifejezések nyelvére, természetesen k értékét minél jobban leszorítva! (Az alábbi nyelvtan balrekurzív, tehát elõször meg kell szüntetni a közvetlen balrekurziót.) A -> A+B | B B -> BC | C C -> D* | D D -> (A) | a | b 10. feladat Ismeretes az egyszerûsített posztfix lengyel jelölésû aritmetika nyelve. Egy, a nyelvet generáló nyelvtan: E -> EE+ | EE* | a Készíts erre a nyelvre LL(k) elemzõt, legyen k minimális, és elemezz egy legalább 6 karakterbõl álló mondatot!

Varró Gergely gervarro@cs.bme.hu

Utolsó módosítás dátuma: 2004. április 23.