next up previous
Next: About this document ...




A feladat:

Nézzük az $S\ensuremath{\rightarrow} aAaa\;\vert\;bAba$, $A\ensuremath{\rightarrow} b\;\vert\;\epsilon$ nyelvtant.
(a) Igaz-e, hogy ez a nyelvtan erős LL(2) nyelvtan?
(b) Készítsünk a nyelvtanhoz gyenge LL(2) elemzőt!
(c) Mutassuk meg, hogy ez nem gyenge LL(1) nyelvtan!

A megoldás:

(a) Próbáljunk meg csinálni erős LL(2) elemzőt hozzá, aztán majd látjuk, hogy nem lehet.

A táblácskák:

  S  
aa,ab aAaa,1  
bb bAba,2  
  A  
ba,bb b,3  
aa,ba $\epsilon,4$  


Vagyis a nyelvyan nem erős LL(2), mert a második táblában mindkét szabály esetén lehet ba előretekintés.

(b)

  S1 $\{\epsilon\}$
aa,ab aA1aa,1 $\{aa\}$
bb bA2ba,2 $\{ba\}$



  A1 $\{aa\}$
ba b,3  
aa $\epsilon,4$  
  A2 $\{ba\}$
bb b,3  
ba $\epsilon,4$  



Az elemzőtábla:

  aa ab ba bb a b $\epsilon$
S1 aA1aa,1 aA1aa,1   bA2ba,2      
A1     b, 3   $\epsilon,4$    
A2     $\epsilon,4$ b,4      
a pop pop     pop    
b     pop pop   pop  
$\epsilon$             ACC


Ez a táblázat is mutatja, hogy erős LL(2)-t nem lehet rá csinálni: az A1 és az A2-s sorok között a ba-s oszlopban ütközés van.

(c)

A táblácskák:

  S1 $\epsilon$
a aA1aa,1 $\{a\}$
b bA2ba,2 $\{b\}$



  A1 $\{a\}$
b b,3  
a $\epsilon,4$  
  A2 $\{b\}$
b b,3  
b $\epsilon,4$  



Az utolsó táblában van az ütközés.



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