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 a 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.