A feladat:

(a) Mutasd meg, hogy az $S\ensuremath{\rightarrow} SA\;\vert\;A$, $A\ensuremath{\rightarrow} aA\;\vert\;b$ nyelvtan nem LR(0) elemezhető!
(b) Készíts a fenti nyelvtanhoz LR(1) elemzőt!
(c) Elemezd az előbb kapott LR(1) elemzővel a bab szót!

A megoldás:

(a)

Próbáljunk meg LR(0) elemzőt csinálni és majd látjuk, hogy nem lehet. Így derül ki, hogy a nyelvtan nem LR(0) elemezhető.

$\mathbf{T_0=\epsilon}$ T0S=T1
   
$S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S$ $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} $
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SA$ $S\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} A$
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} A$ $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA$
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA$ $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b$
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b$  
   


Az első táblába, a T0-ba bekerül mindenképpen az $S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S$. Aztán emiatt, amikor a lezárást csináljuk, bekerül a 2. és 3. szabály. Az utolsó kettő szabály pedig a 3 szabály miatt kerül be. Ebben a táblában még nincs konfliktus, a szabályok alapján az egyetlen tennivaló a shiftelés.

A második táblába alapítóként bekerül az első két szabály. Az utolsó kettő a 2. szabályból jön, az A kifejtésével.
Ebben a halmazban már konfliktus van: az $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} $ miatt Accept lenne, de az $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA$ és az $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b$ miatt meg shift. Tehát nem megy az LR(0) elemzés, tovább nem is érdemes csinálni a halmazokat.

(b) Az LR(1) elemző:

$\mathbf{T_0=\epsilon}$ T0S=T1 T0A=T2
     
$S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S,\;\epsilon$ $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} ,\;\epsilon$ $S\ensuremath{\rightarrow} A\ensuremath{\mathbf{.}} ,\;\epsilon\vert a\vert b$
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SA,\;\epsilon$ $S\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} A,\;\epsilon\vert a\vert b$  
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} A,\;\epsilon$ $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA,\;\epsilon\vert a\vert b$  
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SA,\;a\vert b$ $A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b,\;\epsilon\vert a\vert b$  
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} A,\;a\vert b$    
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA,\;\epsilon$    
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b,\;\epsilon$    
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA,\;a\vert b$    
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b,\;a\vert b$    
     
T0a=T3 T0b=T4 T1A=T5
     
$A\ensuremath{\rightarrow} a\ensuremath{\mathbf{.}} A,\;\epsilon\vert a\vert b$ $A\ensuremath{\rightarrow} b\ensuremath{\mathbf{.}} , \epsilon\vert a\vert b$ $S\ensuremath{\rightarrow} SA\ensuremath{\mathbf{.}} ,\;\epsilon\vert a\vert b$
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aA,\;\epsilon\vert a\vert b$    
$A\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} b,\;\epsilon\vert a\vert b$    
     
T1a=T3 T1b=T4 T3A=T6
     
    $A\ensuremath{\rightarrow} aA\ensuremath{\mathbf{.}} ,\;\epsilon\vert a\vert b$
     
T3a=T3 T3b=T4  
     



Magyarázat a halmazok kiszámításához:

T0:
$S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S$ kerül bele először, a követő nyelv azért lesz $\epsilon$, mert amikor eszeint a szabály szerint akarunk letörni, azaz amikor a pont már a jobboldal után áll majd, vagyis S lesz csak a veremben, akkor az inputon nem lesz már semmi.

Ezen elem lezárásaként bevesszük a következő két elemet, mindkettő követőnyelve az $\epsilon$, mert ezekben a jobboldalakat majd egy olyan S-sé törjük majd le, amelyik az 1. szabályban szerepel, de amikor az az S a veremben lesz, akkor az input már üres.

A 2. szabályban is áll azonban S a pont mögött, így újra bevesszük az $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SA$ és $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} A$ szabályokat, de a követő nyelv ekkor már az $\{a,b\}$ lesz. Azért, mert ezekben a szabályokkal azt a helyzetet írjuk le, amikor majd a jobboldalakat egy olyan S-sé törjük le, amilyen a 2. szabályban van, vagyis egy olyanná, ami mögött A áll. A letöréskor az inputon az ezen A-ból keletkező első terminálist látjuk majd, ami a vagy b.

A 3. szabály miatt bevesszük a 6. és 7. szabályokat, a követő nyelv azért az $\epsilon$ mert a jobboldalakat olyan A-vá törjük majd le, amilyen a 3. szabályban van, az meg olyan, hogy amikor már ő kerül a verem tetejére, akkor az inputon $\epsilon$ látszik.

A 4. szabály miatt újra a 4. és az 5. szabályt kéne bevennünk, de mégegyszer nem tesszük ezt, mivel ha egy olyan elem jönne, ami mindenben (szabály és követő nyelv is) megegyezik egy korábbival, akkor azt nem vesszük be újra.

Az 5. szabály miatt a 8. és 9. szabályokat vesszük be, a követő nyelv azért az, ami, mert ezen elemek jelentése az, hogy a jobboldalakat majd egy olyan A-vá törjük le, (5. szabály) amiről tudjuk, hogy megjelenésekor az inputon a vagy b jön.
A többi szabályt nem lehet tovább facsarni, mert bennük nem áll pont mögött nemterminális.

T1:
Alapítóelemként bekerül az első két szabály. Ilyenkor a követő nyelvvel nem kell vesződni, azt az elem örökli onnan, ahonnan jön. A második szabályban tulajdonképpen két T0-beli szabálynak (a 2.-nak és a 4.-nek) a folytatását vontuk össze, ezt később is így tesszük: ha van két elem, amik csak a követő nyelvben különböznek, akkor azokat egyben írjuk le. Az első elemmel nincs tennivaló. A 2. miatt pedig bevesszük a 3. és 4. szabályokat, a követő nyelv azért az, ami, mert egy olyan A-ból jönnek (a 2. szabályból) aminek veremtetőn való megjelenésekor az inputon $\epsilon\;\vert\;a\;\vert\;b$ állhat (ez oda van írva a 2. szabályba).

T2:
T0-ból alapítóelemként jön az egyetlen szabály.

T3:
Bekerül az első elem alapítóként, a maradékok meg a lezárás miatt, a követő nyelv ugyanúgy megy, mint korábban.

T4, T5,T6:
Egyszerű, ahogy T2 keletkezettt, ugyanúgy.

A többi átmenetnél úgy ismerjük föl, hogy egy olyan halmaz keletkezik, ami már volt, hogy kiszámoljuk (fejben), hogy milyen elemek lesznek majd az új halmazban és észrevesszük, hogy ilyen felállású halmaz már van.

A fenti halmazokból az elemzőtábla:


  a b $\epsilon$ a b S A
T0 S S   T3 T4 T1 T2
T1 S S A T3 T4   T5
T2 2 2 2        
T3 S S   T3 T4   T6
T4 4 4 4        
T5 1 1 1        
T6 3 3 3        


Magyarázat a táblához:

Ugrórész:
A halmazoknál talált átmenetet kódoljuk bele: ha például T0S=T1, akkor a T0 sorában az S-es oszlopba T1-t írunk.

Action:
1. Ha van $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} $ kezdetű elem egy halmazban (pl. T1), akkor azon előretekintésnek megfelelő oszlopba, ami ehhez az elemhez tartozik (most $\epsilon$) A-t írunk, azaz Accept.
2. Ha van olyan nem $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} $-s szabály, ami éppen befejeződött, azaz van $A\ensuremath{\rightarrow}\alpha \ensuremath{\mathbf{.}} $ kezdetű elem egy halmazban (pl. T2), akkor a szabálynak a számát (amit az elején kiosztottunk neki) beírjuk az összes olyan oszlopba, aminek megfelelő előretekintés az adott elemhez tartozik a halmazban (T2-nél ez a szabály az $S\ensuremath{\rightarrow} A$, a szám a 2, az előretekintés pedig $\epsilon$ vagy a vagy b).
3. Ha van olyan szabály valami halmazban, ahol terminális áll a pont mögött, akkor shiftelünk azokra az előretekintésekre, amilyen terminális a pont mögött áll. Például T1-ben van a meg b a pont után, ezért ezen két előretekintésre shift lesz. Vigyázat! LR(1)-nél shifteléskor az elemben felírt követő nyelv semmi szerepet nem játszik.

(c)

Az elemzés (elöl a veremtartalom, a veremtető a jobboldalon, aztán az input, aztán az output):
$(T_0\;,\;bab\;,\;\epsilon)\ensuremath{\rightarrow} $
$(T_0bT_4\;,\;ab\;,\;\epsilon)\ensuremath{\rightarrow} $
$(T_0AT_2\;,\;ab\;,\;4)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;ab\;,\;42)\ensuremath{\rightarrow} $
$(T_0ST_1aT_3\;,\;b\;,\;42)\ensuremath{\rightarrow} $
$(T_0ST_1aT_3bT_4\;,\;\epsilon\;,\;42)\ensuremath{\rightarrow} $
$(T_0ST_1aT_3AT_6\;,\;\epsilon\;,\;424)\ensuremath{\rightarrow} $
$(T_0ST_1AT_5\;,\;\epsilon\;,\;4243)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;\epsilon\;,\;42431)\ensuremath{\rightarrow} $Accept.

Magyarázat az elemzés egy pontjához:
A 4. sor után azért nem Accept van, hanem shift, mert az előretekintés nem $\epsilon$, hanem a.