Formális nyelvek gyakorlat (12)

2005. december 8., csütörtök



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ő!


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!


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$.

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!

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!

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$