A feladat:


Egy CF nyelvet az $S\ensuremath{\rightarrow} SaSb\;\vert\;\epsilon$ nyelvtan definiál.
Készíts erre a nyelvre (erős) LL(k) elemzőt minél kisebb k-val! Ezután elemezd az aababb szót!

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} aSb\hat S,\; 2$,
$\hat S\ensuremath{\rightarrow}\epsilon,\; 3$.

Ez már szép nyelvtan, csináljunk erős LL(1) elemzőt hozzá.

A táblácskák:

	S
$a,b,\epsilon$	${\hat S}$,1

	${\hat S}$
a	$aSb\hat{S},2$
$\epsilon ,b$	$\epsilon,3$

Az elemzőtábla:

	a	b	$\epsilon$
S	$\hat{S}, 1$	${\hat S}$,1	$\hat{S_1}$, 1
${\hat S}$	$aSb\hat{S},2$	$\epsilon,3$	$\epsilon$, 3
a	pop
b		pop
$\epsilon$			ACC

Az aababb elemzése (elöl az input, aztán a veremtartalom, a veremtető a baloldalon, végül az output):
$(aababb,\;S,\;\epsilon)\ensuremath{\rightarrow}$
$(aababb,\;\hat{S},\;1)\ensuremath{\rightarrow}$
$(aababb,\;aSb\hat{S},\;12)\ensuremath{\rightarrow}$
$(ababb,\;Sb\hat{S},\;12)\ensuremath{\rightarrow}$
$(ababb,\;\hat Sb\hat{S},\;121)\ensuremath{\rightarrow}$
$(ababb,\;aSb\hat Sb\hat{S},\;1212)\ensuremath{\rightarrow}$
$(babb,\;Sb\hat Sb\hat{S},\;1212)\ensuremath{\rightarrow}$
$(babb,\;\hat Sb\hat Sb\hat{S},\;12121)\ensuremath{\rightarrow}$
$(babb,\;b\hat Sb\hat{S},\;121213)\ensuremath{\rightarrow}$
$(abb,\;\hat Sb\hat{S},\;121213)\ensuremath{\rightarrow}$
$(abb,\;aSb\hat Sb\hat{S},\;1212132)\ensuremath{\rightarrow}$
$(bb,\;Sb\hat Sb\hat{S},\;1212132)\ensuremath{\rightarrow}$
$(bb,\;\hat Sb\hat Sb\hat{S},\;12121321)\ensuremath{\rightarrow}$
$(bb,\;b\hat Sb\hat{S},\;121213213)\ensuremath{\rightarrow}$
$(b,\;\hat Sb\hat{S},\;121213213)\ensuremath{\rightarrow}$
$(b,\;b\hat{S},\;1212132133)\ensuremath{\rightarrow}$
$(\epsilon,\;\hat{S},\;1212132133)\ensuremath{\rightarrow}$
$(\epsilon,\;\epsilon,\;12121321333)$
Accept