Next: About this document ...
Először is át kell alakítani a nyelvtant, hogy ne legyen balrekurzív (hogy ezt
hogyan kell azt lásd a jegyzetben):
,
.
Mivel itt a második két szabályban a jobboldalak ugyanúgy kezdődnek, egy
faktorizációnak nevezett eljárással (szintén a jegyzetben)
szebb nyelvtant kaphatunk (olyan értelemben
szebbet, hogy kisebb lesz a k az LL(k) elemzőben).
Azaz a nyelvtanunk legyen:
,
,
.
Itt még T és S összevonható (a generált nyelv ugyanaz):
,
,
.
Ez már szép nyelvtan, jöhetnek a táblácskák, próbálkozzunk először
gyenge LL(1) elemzővel.
A táblácskák:
Itt már látszik is, hogy LL(1)-gyel nem megy.
Jöjjön a gyenge LL(2).
A táblácskák:
Az elemzőtábla (az alsó részt lehagyva):
|
aa |
ab |
|
S1 |
S1', 2 |
|
,
1 |
S2 |
S2', 2 |
|
|
S1' |
aS2abS1, 3 |
|
|
S2' |
aS2abS2, 3 |
|
|
Az is látható, hogy ez erős LL(2) nyelv is, össze lehetne vonni a
különböző indexű nemterminálisokat.
Egy elemzés (elöl az input, aztán a veremtartalom, a veremtető a baloldalon, végül
az output):
Accept
Next: About this document ...
Csiga
1999-05-16