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