Sziasztok!

A mai óra a anyaga az LR(k) elemzés volt. Először az LR(0), aztán az LR(1) elemzést néztük meg részletesen és példán keresztül is. Az alábbi feladatokból volt az 1., a 2a és a 2b eleje, de ezt nem fejeztük be. A 3.-ra meg egyáltalán nem került sor.

Óra végén említettem, hogy azért ez a két LR (LR(0) és LR(1)) érdekes főleg, mert az LR(1) elemezhető nyelvek osztálya megegyezik a determinisztikus CF nyelvek osztályával és ennél többet nem is remélhetünk, azaz ami LR(k) elemezhető nyelv valami k-val az LR(1) is. Persze lehet, hogy nem ugyanazzal a nyelvtannal, de van olyan nyelvtan, amivel.

Otthoni teendők: Próbáljátok befejezni a 2b-t (ameddig megcsináltuk, onnan már nem nehéz) és a 2c-t, illetve megcsinálni a 3.-t. A megoldásaikat felteszem majd nemsokára, ha lesz időm leírni őket.

A jövő héten kis zh lesz, anyaga várhatóan az elemzők, főleg LL(k) és LR(k).

LR(k) elemzés

Formális nyelvek gyakorlat (11)

2000. április 25., kedd

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

2. (a) Mutasd meg, hogy az $S\ensuremath{\rightarrow} SA\;\vert\;A$, $A\ensuremath{\rightarrow} aA\;\vert\;b$ nyelvtan nem LR(0) elemezhető!
(b) Készíts a fenti nyelvtanhoz LR(1) elemzőt!
(c) Elemezd az előbb kapott LR(1) elemzővel a bab 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$