Next: About this document ...
A feladat:
Egy CF nyelvet az
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
szabályok
helyett az
,
szabályokat veszük be. Ezzel a közvetlen balrekurzió már
nincsen és ez most elég is):
,
,
.
Ez már szép nyelvtan, csináljunk
erős LL(1) elemzőt hozzá.
A táblácskák:
|
S |
|
![$a,b,\epsilon$](img8.gif) |
,1 |
|
Az elemzőtábla:
|
a |
b |
![$\epsilon$](img13.gif) |
S |
![$\hat{S}, 1$](img14.gif) |
,1 |
,
1 |
![${\hat S}$](img9.gif) |
![$aSb\hat{S},2$](img10.gif) |
![$\epsilon,3$](img12.gif) |
,
3 |
a |
pop |
|
|
b |
|
pop |
|
![$\epsilon$](img13.gif) |
|
|
ACC |
Az aababb elemzése (elöl az input, aztán a veremtartalom, a veremtető a baloldalon, végül
az output):
Accept
Next: About this document ...
Judit Csima
2000-04-20