Sziasztok! A mai órán ez volt: 1. Kis zh, eredmények itt. 2. A nagy zh kiosztása, eredmények ugyanott, ahol a kis zh-é. Pótzh nemsokára lesz, a jövõ héten pontosabbat tudok mondani, addig is, ami biztos: Pótzh-t bárki írhat és senkinek sem kötelezõ írnia. Az elsõ 20 perc után ott lehet hagyni a pótzh-t és ki lehet jönni, akkor olyan, mintha nem is írtál volna. Ha viszont maradsz, akkor a félévi pontszámba a pótzh és a rendes zh átlaga számít. 3. A mai óra anyaga általános elemzõk: ezek olyan elemzõk, amik minden CF nyelvre mennek, nem kell, hogy a nyelv egyértelmû legyen, meg az se kell, hogy a nyelvtan, amiben elemzünk ne legyen balrekurzív. Két ilyen algoritmust tanulunk: a Cocke-Younger-Kasami (CYK) és az Earley algoritust. Megcsináltuk az órán az 1. és a 2. feladatot (majdnem végig, ezt házi befejezni, a következõ óra elején beszélünk még róla), a többi elemzõs feladat gyakorolni van. Ha csináltok velük valamit, szívesen kijavítom. Segítségül: nagyon röviden a CYK algoritmusról Plusz a feladatok megoldásai is fent vannak, lásd lejjebb. Ja, és még a jegyzetben is van kidolgozott példa mindkettõre, ott is lehet tájékozódni. 1. A Coke-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õ: $$\begin{eqnarray*}S &\ensuremath{\rightarrow} & AB, \\ A &\ensuremath{\rightarrow} & aAb \mid ab, \\ B &\ensuremath{\rightarrow} & bBc \mid bc \end{eqnarray*}$$ Megoldás nagyon részletesen 2. Legyen a nyelvtanunk a következõ: $P\ensuremath{\rightarrow} bDSe$ , $D\ensuremath{\rightarrow} dvD\;\vert\;dv$ , $S\ensuremath{\rightarrow} uvS\;\vert\;uv$ . Elemezzük az Earley algoritmussal a bdvuvuve szót! Megoldás eléggé részletesen 3. Még mindig az Earley algoritmus: a nyelvtan az $S\ensuremath{\rightarrow} SaSb\;\vert\;\epsilon$ . Az elemzendõ szó: aababbab . Gyakorolni 4. A CYK elemzéssel elemezzük az $S\ensuremath{\rightarrow} aSa\;\vert\;bSb\;\vert\;aa\;\vert\;bb$ nyelvtanban az abbbba és az abbba szót! Megoldás 5. A CYK algoritmussal (elemzéssel) elemezzük az $E\ensuremath{\rightarrow} E+E\;\vert\;E*E\;\vert\;a$ nyelvtanban az (a) a+a*a+a szót (b) a++a szót! Döntsük el, hogy generálhatók-e a nyelvtannal, egyértelmûen generálhatók-e és adjuk meg a levezetési fákat is! Megoldás 6. Earley algoritmussal elemezzük az a+a*a szót az $E\ensuremath{\rightarrow} E+E\;\vert\;E*E\;\vert\;a$ nyelvtanban. Gondoljuk végig, hogy hol látszik az elemzésben az, hogy nem egyértelmû a nyelvtan!