A feladat:

Egy CF nyelvet az $S\ensuremath{\rightarrow} SaSab\;\vert\;\epsilon$ nyelvtan definiál.
(a) Készíts erre a nyelvre gyenge LL(k) elemzőt minél kisebb k-val!
(b) Ezután elemezd az aaababaab szót!
(c) Készíts az (a)-ban adott gyenge elemzőből erőset, aztán nézd meg, hogy hogyan viselkedik a gyenge és az erős az aabab szón!

A megoldás:

Először is át kell alakítani a nyelvtant, hogy ne legyen balrekurzív (Ez úgy megy, hogy az $A\ensuremath{\rightarrow} A{\alpha}_i\;\vert\;{\beta}_j$ szabályok helyett az $A\ensuremath{\rightarrow} {\beta}_j\hat A$, $\hat A\ensuremath{\rightarrow} {\alpha}_i\hat A\;\vert\; \epsilon$ szabályokat veszük be. Ezzel a közvetlen balrekurzió már nincsen és ez most elég is):
$S\ensuremath{\rightarrow}\hat S,\;1$,
$\hat S\ensuremath{\rightarrow} aSab\hat S,\; 2$,
$\hat S\ensuremath{\rightarrow}\epsilon,\; 3$.

Ez már szép nyelvtan, próbálkozzunk először gyenge LL(1) elemzővel.

A táblácskák:

  S1 $\{\;\epsilon\;\}$
$a,\epsilon$ ${\hat S}_1$,1 $\{\;\epsilon\;\}$

  ${\hat S}_1$ $\{\;\epsilon\;\}$
a $aS_2ab\hat{S_1},2$ $\{\;a\;\}$, $\{\;\epsilon\;\}$
$\epsilon$ $\epsilon,3$  



  S2 $\{\;a\;\}$
a $\hat{S_2},1$ $\{a\}$

  $\hat {S_2}$ $\{\;a\;\}$
a $aS_2ab\hat{S_2},2$ $\{\;ab\;\}$,$\{\;a\;\}$
a $\epsilon,3$  



Itt már látszik is, hogy LL(1)-gyel nem megy, mert ebben az utolsó táblácskában mindkét szabály esetén lehetne a-t látni.

Jöjjön a gyenge LL(2).

A táblácskák:

  S1 $\{\;\epsilon\;\}$
$aa,\epsilon$ ${\hat S}_1$,1 $\{\;\epsilon\;\}$

  ${\hat S}_1$ $\{\;\epsilon\;\}$
aa $aS_2ab\hat{S_1},2$ $\{\;ab\;\}$, $\{\;\epsilon\;\}$
$\epsilon$ $\epsilon,3$  



  S2 $\{\;ab\;\}$
aa,ab $\hat {S_2}$,1 $\{\;ab\;\}$

  $\hat {S_2}$ $\{\;ab\;\}$
aa $aS_2ab\hat{S_2},2$ $\{\;ab\;\}$, $\{\;ab\;\}$
ab $\epsilon,3$  



Az elemzőtábla:

  aa ab ba bb a b $\epsilon$
S1 $\hat{S_1}, 1$           ${\hat S}_1$, 1
S2 $\hat{S_2},1$ $\hat{S_2},1$          
${\hat S}_1$ $aS_2ab\hat{S_1},2$           $\epsilon$, 3
$\hat {S_2}$ $aS_2ab\hat{S_2},2$ $\epsilon$,3          
a pop pop     pop    
b     pop pop   pop  
$\epsilon$             ACC



Az aaababaab elemzése (elöl az input, aztán a veremtartalom, a veremtető a baloldalon, végül az output):
$(aaababaab,\;S_1,\;\epsilon)\ensuremath{\rightarrow} $
$(aaababaab,\;\hat{S_1},\;1)\ensuremath{\rightarrow} $
$(aaababaab,\;aS_2ab\hat{S_1},\;12)\ensuremath{\rightarrow} $
$(aababaab,\;S_2ab\hat{S_1},\;12)\ensuremath{\rightarrow} $
$(aababaab,\;\hat{S_2}ab\hat{S_1},\;121)\ensuremath{\rightarrow} $
$(aababaab,\;aS_2ab\hat{S_2}ab\hat{S_1},\;1212)\ensuremath{\rightarrow} $
$(ababaab,\;S_2ab\hat{S_2}ab\hat{S_1},\;1212)\ensuremath{\rightarrow} $
$(ababaab,\;\hat{S_2}ab\hat{S_2}ab\hat{S_1},\;12121)\ensuremath{\rightarrow} $
$(ababaab,\;ab\hat{S_2}ab\hat{S_1},\;121213)\ensuremath{\rightarrow} $
$(babaab,\;b\hat{S_2}ab\hat{S_1},\;121213)\ensuremath{\rightarrow} $
$(abaab,\;\hat{S_2}ab\hat{S_1},\;121213)\ensuremath{\rightarrow} $
$(abaab,\;ab\hat{S_1},\;1212133)\ensuremath{\rightarrow} $
$(baab,\;b\hat{S_1},\;1212133)\ensuremath{\rightarrow} $
$(aab,\;\hat{S_1},\;1212133)\ensuremath{\rightarrow} $
$(aab,\;aS_2ab\hat{S_1},\;12121332)\ensuremath{\rightarrow} $
$(ab,\;S_2ab\hat{S_1},\;12121332)\ensuremath{\rightarrow} $
$(ab,\;\hat{S_2}ab\hat{S_1},\;121213321)\ensuremath{\rightarrow} $
$(ab,\;ab\hat{S_1},\;1212133213)\ensuremath{\rightarrow} $
$(b,\;b\hat{S_1},\;1212133213)\ensuremath{\rightarrow} $
$(\epsilon,\;\hat{S_1},\;1212133213)\ensuremath{\rightarrow} $
$(\epsilon,\;\epsilon,\;12121332133)\ensuremath{\rightarrow} $
Accept

Mivel a fenti gyenge elemzőtáblában nincsen ütközés a különböző indexű, de amúgy azonos nemterminálisokhoz tartozó sorok között, készíthetünk a gyenge táblából erőset, úgy hogy az indexezést elfelejtjük és a sorokat összevonjuk:

  aa ab ba bb a b $\epsilon$
S $\hat {S}, 1$ $\hat {S}, 1$         $\hat {S}, 1$
$\hat{S}$ $aSab\hat{S}, 2$ $\epsilon$,3         $\epsilon$,3
a pop pop     pop    
b     pop pop   pop  
$\epsilon$             ACC


Nézzük meg, hogy hogyan viselkedik egy rossz szóra, például az aabab-re a két elemző:

Előbb e gyenge:

$(aabab,\;S_1,\;\epsilon)\ensuremath{\rightarrow} $
$(aabab,\;\hat{S_1},\;1)\ensuremath{\rightarrow} $
$(aabab,\;aS_2ab\hat{S_1},\;12)\ensuremath{\rightarrow} $
$(abab,\;S_2ab\hat{S_1},\;12)\ensuremath{\rightarrow} $
$(abab,\;\hat{S_2}ab\hat{S_1},\;121)\ensuremath{\rightarrow} $
$(abab,\;ab\hat{S_1},\;1213)\ensuremath{\rightarrow} $
$(bab,\;b\hat{S_1},\;1213)\ensuremath{\rightarrow} $
$(ab,\;\hat{S_1},\;1213)\ensuremath{\rightarrow} $ HIBA!!!

Az erős:

$(aabab,\;S,\;\epsilon)\ensuremath{\rightarrow} $
$(aabab,\;\hat{S},\;1)\ensuremath{\rightarrow} $
$(aabab,\;aSab\hat{S},\;12)\ensuremath{\rightarrow} $
$(abab,\;Sab\hat{S},\;12)\ensuremath{\rightarrow} $
$(abab,\;\hat{S}ab\hat{S},\;121)\ensuremath{\rightarrow} $
$(abab,\;ab\hat{S},\;1213)\ensuremath{\rightarrow} $
$(bab,\;b\hat{S},\;1213)\ensuremath{\rightarrow} $
$(ab,\;\hat{S},\;1213)\ensuremath{\rightarrow} $
$(ab,\;\epsilon,\;1213)\ensuremath{\rightarrow} $ HIBA!!!

Azaz a gyenge hamarabb észrevette a hibát. A két elemző gyengén ekvivalens, de nem ekvivalens.