Formális nyelvek gyakorlat (13) 2001., május 8. Ennek az a) és b) részét elõadáson végigszámoltuk. 1. (a) Készíts $LR(1)$ elemzõt az $S\ensuremath{\rightarrow}SA\;\vert\;A$, $A\ensuremath{\rightarrow}aA\;\vert\;b$ nyelvtanhoz! (b) Elemezd az elõbb kapott $LR(1)$ elemzõvel a $bab$ szót! (c) Mutasd meg, hogy a fenti nyelvtan nem $LR(0)$ elemezhetõ! Megoldás 2. (a) Készíts $LR(0)$ elemzõt az $S\ensuremath{\rightarrow}aP$, $P\ensuremath{\rightarrow}Qb$, $Q\ensuremath{\rightarrow}QS\;\vert\;\epsilon$ nyelvtanhoz! (b) Elemezd az elõbb kapott elemzõvel az $aabb$ szót! Megoldás 3. (a) Csinálj $LR(1)$ elemzõt az $S\ensuremath{\rightarrow}Ab\;\vert\;Ac$, $A\ensuremath{\rightarrow}AB\;\vert\;a$, $B\ensuremath{\rightarrow}a$ nyelvtanhoz! (b) Elemezd az elõbb kapott elemzõvel az $aaab$ szót! (c) Az (a) pontban kapott elemzõt megszemlélve döntsd el, hogy a nyelvtan $LR(0)$ nyelvtan-e (indoklás!!). (d) Elemezz egy olyan szót is, ami nem generálható a nyelvtannal, például: $acb$. Megoldás Gyakorolni: 4. $LR(0)$ elemzõ kell: $S\ensuremath{\rightarrow}aAc\;\vert\;b$, $A\ensuremath{\rightarrow}aSc\;\vert\;b$. Ha megvan az elemzõ, akkor elemezzük vele az $aabcc$ szót! Megoldás 5. Adjunk $LR(k)$ elemzõt minél kisebb $k$-val az $S\ensuremath{\rightarrow}SaSb\;\vert\;\epsilon$ nyelvtanhoz és elemezzük az $ababab$ szót! Megoldás 6. Az alább következõ három nyelvtanról döntsük el, hogy $LR(k)$ nyelvtanok-e és ha úgy találjuk, hogy azok, akkor adjuk meg azt a legkisebb $k$-t is, amivel $LR(k)$ elemezhetõek. A nyelvtanok: (a) $S\ensuremath{\rightarrow}SaSb\;\vert\;c$ (b) $S\ensuremath{\rightarrow}aSb\;\vert\;ab$ (c) $S\ensuremath{\rightarrow}aSa\;\vert\;bSb\;\vert\;a\;\vert\;b$