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 (ez utóbbit majdnem végig, 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!