Formális nyelvek gyakorlat (13)

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



1. Készítsünk precedencia elemzőt az $S\ensuremath{\rightarrow} aSc\;\vert bSd\;\vert\;ac\;\vert\;bd$ nyelvtanhoz és elemezzük az $abdc$ szót!

2. (a) Mutassuk meg, hogy az $E\ensuremath{\rightarrow} E+T\;\vert\;T$, $T\ensuremath{\rightarrow} T*F\;\vert\;F$, $F\ensuremath{\rightarrow} (E)\;\vert\;a$ nyelvtan nem erős precedencia nyelvtan és egyúttal készítsünk hozzá gyenge precedencia elemzőt!
(b) Elemezzük a gyenge elemzővel az $a+a$ szót!

3. Van-e egyszerű precedencia elemző az alábbi nyelvtanokhoz? Ha van, akkor azt is nézzük meg, hogy erős-e avagy gyenge.
(a) $S\ensuremath{\rightarrow} SA\;\vert A$, $A\ensuremath{\rightarrow} (S)\;\vert\;()$
(b) $S\ensuremath{\rightarrow}$ if $E$ then $S$ else $S\;\vert\;a$, $E\ensuremath{\rightarrow} E$ or $b\;\vert\;b$
(c) $S\ensuremath{\rightarrow} A;A$, $A\ensuremath{\rightarrow} [S]\;\vert\;[i]\;\vert\;i$

4. Van a következő nyelvtan: $S\ensuremath{\rightarrow}0S11\;\vert11$
(a) Egyszerű precedencia nyelvtan-e ez?
(b) Hát az igaz-e, hogy van hozzá (2,1) precedencia elemző?

5. Készítsünk operátor-precendencia elemzőt a 2. feladat nyelvtanához és elemezzük vele az $a+a$ szót!

6. Adott az alábbi nyelvtan mely logikai kifejezéseket generál.

$$\begin{eqnarray*} A& \ensuremath{\rightarrow}& A\vee B\;\vert\;B\\ B&\ensuremat... ...rightarrow}&p(X)\;\vert\;(A) \\ X & \ensuremath{\rightarrow}&x \end{eqnarray*}$$

a) Készítsen operátor precedencia elemzőt a nyelvtanhoz!
b) Elemezze segítségével az $p(x)\wedge\neg p(x)$ mondatot!

7. (a) Operátor precedencia elemző kell a következő nyelvtanhoz:

$$\begin{eqnarray*} S& \ensuremath{\rightarrow}& (L)\;\vert\;a\\ L&\ensuremath{\rightarrow}&L,S\;\vert\;S \end{eqnarray*}$$

(b) Ha ez megvan, akkor elemezd az elemzővel az $(a,(a,a))$ szót!

8. Adott az alábbi nyelvtan:

$$\begin{eqnarray*} S& \ensuremath{\rightarrow}& XAAAB\\ B&\ensuremath{\rightarro... ...th{\rightarrow}& 1X \\ XY & \ensuremath{\rightarrow}& \epsilon \end{eqnarray*}$$

Adja meg a nyelv verbális specifikációját! (Magyarul: Mi a generált nyelv?)