Formális nyelvek gyakorlat (11)

1999. április 27., kedd

Gondoljuk meg, hogy


(a) mit jelent az, hogy egy nyelvtan LL(0) tulajdonságú
(b) miért hal meg az LL(k) elemzés, ha a nyelvtan balrekurzív.



Feladatok az LR(k) elemzőkről


1. Csináljunk LR(1) elemzőt az $S\ensuremath{\rightarrow} Ab\;\vert\;Ac$, $A\ensuremath{\rightarrow} AB\;\vert\;a$, $B\ensuremath{\rightarrow} a$ nyelvtanhoz és elemezzük az aaab szót. Elemezzünk egy olyan szót is, ami nem eleme a generált nyelvnek!

2. Csináljunk LR(1) elemzőt a posztfix aritmetikás nyelvtanhoz: $E\ensuremath{\rightarrow} EE+\;\vert\;EE*\;\vert\;a$. Elemezzük az aaa+* szót!

3. Most meg LR(0) elemző kell. A nyelvtan: $S\ensuremath{\rightarrow} aAc\;\vert\;b$, $A\ensuremath{\rightarrow} aSc\;\vert\;b$. Elemezzük az aabcc szót.

4. LR(1) elemző kell: $S\ensuremath{\rightarrow} SA\;\vert\;A$, $A\ensuremath{\rightarrow} aA\;\vert b$. (Könnyű.)

5. Egy nyelv karakterkészlete a $\Sigma=\{a,b\}$. A nyelv mondataiban pontosan kétszer annyi a karakter van, mint b és a mondatok prefixeiben legalább kétszer annyi a karakter van, mint b. Készítsen nyelvtant erre a nyelvre és csináljon a nyelvtanhoz minél egyszerűbb LR(k) elemzőt. (Bonyolult.)

6. LR(0) elemző kell: $S\ensuremath{\rightarrow} A\;\vert\;B$, $A\ensuremath{\rightarrow} aAb\;\vert\;c$, $B\ensuremath{\rightarrow} aBbb\;\vert\;d$. Elemezzünk egy legalább 5 hosszú szót az elemzővel!