Sziasztok!

1. Kis zh eredmények itt lesznek.

2. A mai óra anyaga a precedencia elemzés. Hogy ennek mi a lényege, azt lásd a jegyzetben. Kiegészítésül itt van egy kis segédlet, ahhoz, hogy hogyan kell egy egyszerű precedencia elemzőnél a relációkat meghatározni.

3. összefoglalás: Van olyan, hogy egyszerű precedencia elemző, ez olyan, hogy egy szimbólumot néz a veremben és egyet az inputon, ezért is hívják (1,1) elemzőnek, szemben az (m,n) elemzőkkel, ahol m szimbólumot nézünk a veremben és n-et az inputon.

További bontás: az egyszerű elemzők lehetnek erősek (ha minden reláció diszjunkt) vagy gyengék, ha esetleg azt megengedjük, hogy a nyél eleje meg a nyél belseje nem diszjunkt, de ekkor még további feltételeknek kell teljesülnie (lásd a jegyzetet).

4. Van egy tétel, ami szerint ha egy nyelvtan gyengén precedencia elemezhető, akkor lehet csinálni egy másik nyelvtant, ami ugyanazt generélja, de az már erősen is precedencia elemezhető.

5. A feladatok:1., 2. és 4a-t megbeszéltük, a többi gyakorló. (1. és 3. benne van a jegyzetben. Vigyázat! A jegyzetbeli (2,1)-es példa táblázatában az egyik sor hibás.)

6. Tettem fel hibajegyzéket a jegyzethez. Mindenféle kommentárt szivesen fogadok (pl. ha más hibát találtok, vagy ha valami nem is hiba szerintetek).

Precedencia elemzés

Formális nyelvek gyakorlat (12)

2000. május 2., kedd

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. 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ő?

3. (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*a szót!

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

Tavaly vizsgafeladat volt:

5. Az alábbi nyelvtan reguláris kifejezéseket generál.

$$\begin{eqnarray*}A& \ensuremath{\rightarrow} & A+B\;\vert\;B\\ B&\ensuremath{\r... ... &C^*\;\vert\;D \\ D & \ensuremath{\rightarrow} &(A)\;\vert\;a \end{eqnarray*}$$

a)Készítsen precedencia elemzőt a nyelvtanhoz!
b) Elemezze segítségével az a(a+a^*)^* mondatot!