next up previous
Next: About this document ...




A táblázatok:



Semmi = 0  b = 1 d = 2 
		 		


$P\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} bDSe,\;0$


$P\ensuremath{\rightarrow} b\ensuremath{\mathbf{.}} DSe,\;0$


$D\ensuremath{\rightarrow} d\ensuremath{\mathbf{.}} vD,\;1$
		

$D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dvD,\;1$


$D\ensuremath{\rightarrow} d\ensuremath{\mathbf{.}} v\;,1$
		

$D\ensuremath{\rightarrow} .dv,\;\;1$
				
v = 3 		u = 4 		v = 5 
		 		


$D\ensuremath{\rightarrow} dv\ensuremath{\mathbf{.}} D ,\;1$


$S\ensuremath{\rightarrow} u\ensuremath{\mathbf{.}} vS ,\;3$


$S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} S,\;3$


$D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dvD ,\;3$


$S\ensuremath{\rightarrow} u\ensuremath{\mathbf{.}} v ,\;3$


$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uvS,\;5$


$D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dv ,\;3$


$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,\;5$


$D\ensuremath{\rightarrow} dv\ensuremath{\mathbf{.}} ,\;1$


$S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,\;3$


$P\ensuremath{\rightarrow} bD\ensuremath{\mathbf{.}} Se,\; 0$


$P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,\;0$


$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uvS,\; 3$


$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,\; 3$
				
u = 6 		v = 7 		e = 8 
		 		


$S\ensuremath{\rightarrow} u\ensuremath{\mathbf{.}} vS ,\;5$


$S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} S ,\;5$


$P\ensuremath{\rightarrow} bDSe\ensuremath{\mathbf{.}} ,\;0$


$S\ensuremath{\rightarrow} u\ensuremath{\mathbf{.}} v ,\;5$


$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uvS ,\;7$
		

$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,\;7$
		

$S\ensuremath{\rightarrow} uv \ensuremath{\mathbf{.}} ,\; 5$
		

$S\ensuremath{\rightarrow} uvS\ensuremath{\mathbf{.}} ,\;3$
		

$P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,\;0$
				


Magyarázat a táblázathoz:

A 0. halmazba betesszük az egyetlen mondatszimbólum-baloldalú szabályt az előírt alakban és kész.

Az 1. halmazba alapítóként bekerül a $P\ensuremath{\rightarrow} b\ensuremath{\mathbf{.}} DSe,0$ szabály, mert az első betű a szóan b. Mivel a pont mögött nemterminális (D) áll, beveszük a másik két szabályt, kifejtve így a pont mögött álló nemterminálist.

A 2. csoport alpítóelemei a $D\ensuremath{\rightarrow} d\ensuremath{\mathbf{.}} vD,1$ és $D\ensuremath{\rightarrow} d\ensuremath{\mathbf{.}} v,1$ szabályok, mert mindkettőt egy 1. halmazbeli elemből kapjuk a d átlépésével. További elemek ide nem kerülnek, mert nincsen nemterminális közvetlenül pont után és véget sem ért egy szabály sem.

A 3. csoportba alapítóként kerülnek a $D\ensuremath{\rightarrow} dv\ensuremath{\mathbf{.}} D,1$ és a $D\ensuremath{\rightarrow} dv\ensuremath{\mathbf{.}} ,1$ szabályok, mindkettőben a v-t léptük át. Az első szabályban D áll a pont után, ezért bevesszük a $D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dvD,3$ és a $D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dv,3$ szabályokat. A $D\ensuremath{\rightarrow} dv\ensuremath{\mathbf{.}} ,1$ szabály miatt pedig a következőt tesszük: az 1. halmazban megkeressük ezen szabály ``előzményét'', a $D\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} dv,1$ szabályt és megkeressük azt a szabályt, aki miatt ez az előzmény bekerült az 1. halmazba, ez most a $P\ensuremath{\rightarrow} b\ensuremath{\mathbf{.}} DSe,0$ szabály. Ebben átlépjük a D nemterminálist a ponttal és a 3. halmazba berakjuk a $P\ensuremath{\rightarrow} bD\ensuremath{\mathbf{.}} Se,0$ szabályt is. Itt viszont S áll a pont után, tehát be kell vennünk a két utolsó szabályt is.

A 4. csoport alapítótagjait úgy kapjuk, hogy megnézzük, melyik 3. halmazbeli szabályban áll u a pont mögött. Két ilyen szabály van, ezek lesznek az alapítóelemek a 4. halmazban és egyben egyedüliek is, mivel további teendő nincs velük.

Az 5. halmaz hasonlóan jön, mint a hogy a 3. jött: alapítóként bekerülnek az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} S,3$ és $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,3$ szabályok. Az első miatt bevesszük az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uvS,5$ és $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,5$ szabályokat. Az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,3$ szabály miatt pedig a 3. halmazban megkeressük ``előzmény''-szabályt, vagyis az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,3$-at és megkeressük azt a szabályt is, aki miatt ez az előzmény bekerült az 3. halmazba, ez a $P\ensuremath{\rightarrow} bD\ensuremath{\mathbf{.}} Se,0$ szabály. Ebben átlépjük az S nemterminálist a ponttal és végül az 5. halmazba berakjuk a $P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,0$ szabályt is.

A 6. halmaz alapító és egyben egyedüli elemeit hasonlóan kapjuk, mint a 4. halmaz esetén.

A 7. halmazba alapítóként bekerül az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} S,5$ és $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,5$ szabály. Az első miatt bekerül még az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uvS,7$ és az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,7$ szabály is. Az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,5$ szabály miatt az 5. halmazban megkeressük az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,5$ szabályt, majd azt ami miatt ez oda bekerült, ez az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} S,3$ szabály. Emiatt az $S\ensuremath{\rightarrow} uvS\ensuremath{\mathbf{.}} ,3$-t berakjuk a 7. halmazba, de ennek megint a végén van a pont. Így megkeressük a 3. halmazban az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} uv,3$-at és a $P\ensuremath{\rightarrow} bD\ensuremath{\mathbf{.}} Se,0$ szabályt. Ez utóbbiban az S-t átlépve, berakjuk a 7. halmazba a $P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,0$ szbályt is.

A 8. halmaz egyetlen alapító eleme az $P\ensuremath{\rightarrow} bDSe\ensuremath{\mathbf{.}} ,0$ lesz és további elem nem is jön be.

Mivel az utolsó halmazban van olyan elem, ami a 0.-ban is volt, azzal az egy különbséggel, hogy a pont most nem alöl, hanem hátul áll, a szó generálható a nyelvtannal.

A táblázatokból visszakereséssel jön a levezetési fa: visszanézzük, hogy melyik szabály miért került be a táblákba.
Hátulról kezdjük: az utolsó táblában a $P\ensuremath{\rightarrow} bDSe\ensuremath{\mathbf{.}} ,\;0$ a 7. táblában levő $P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,\;0$ miatt jött be. A $P\ensuremath{\rightarrow} bDS\ensuremath{\mathbf{.}} e,\;0$ szabály azért került be, mert ugrottuk az S-t, azt meg azért tettük, mert az $S\ensuremath{\rightarrow} uvS\ensuremath{\mathbf{.}} ,\;3$ szabály végére értünk, annak meg azért értünk a végére, mert az $S\ensuremath{\rightarrow} uv\ensuremath{\mathbf{.}} ,5$ szabálynak a végére értünk. Satöbbi, satöbbi... Így visszajutunk és közben építjük a fát. Mire az elejére érünk, az első táblához, addigra teljes lesz a fa.



 
next up previous
Next: About this document ...
Judit Csima
2000-04-14