Formális nyelvek gyakorlat (10)

1999. április 20., kedd

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

2. A nyelvtan most a posztfixes nyelvtan: $E\ensuremath{\rightarrow} EE+\;\vert\;EE*\;\vert\;a$. Az Earley algoritmussal elemzendő az aaa+a*+ szó.

3. Még mindig az Earley algoritmus: a nyelvtan az $S\ensuremath{\rightarrow} SaSb\;\vert\;\epsilon$. Az elemzendő szó: aababbab.

4. Beadandó házi feladat!!!!
LL(k) elemző kell az infix aritmetikás nyelvtanra: $E\ensuremath{\rightarrow} E+T\;\vert\;T$, $T\ensuremath{\rightarrow} T*F\;\vert\;F$, $F\ensuremath{\rightarrow} (E)\;\vert\;a$. Olyan kicsi k-val, amilyen kicsivel csak lehet. (Megjegyzés: k=1 a megoldás.) Csináljunk ``gyenge'' elemzőt, majd abból erőset. Állapítsuk meg, hogy az ``erős'' elemző ugyan kisebb, de később (több lépés után) veszi észre a hibát például az a+a)*a hibás szóban.

5. Egy környezetfüggetlen nyelvet az alábbi nyelvtan definiál: $S\ensuremath{\rightarrow} SaSab\;\vert\;\epsilon$.
Készítsen erre a nyelvre LL(k) elemzőt, minél kisebb k-val. Ezután elemezze az aaababaab szót az elemzővel.