A feladat:

(a) Készíts LR(0) elemzőt az $S\ensuremath{\rightarrow} aP$, $P\ensuremath{\rightarrow} Qb$, $Q\ensuremath{\rightarrow} QS\;\vert\;\epsilon$ nyelvtanhoz!
(b) Elemezd az előbb kapott elemzővel az aabb szót! (a)

Megoldás:

Először nézzük, hogy a halmazok hogyan jönnek ki:

$\mathbf{T_0=\epsilon}$	T0S=T1	T0a=T2
$S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S$	$S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}}$	$S\ensuremath{\rightarrow} a\ensuremath{\mathbf{.}} P$
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aP$		$P\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} Qb$
		$Q\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} QS$
		$Q\ensuremath{\rightarrow}\ensuremath{\mathbf{.}}$
T2P=T3	T2Q=T4	T4b=T5
$S\ensuremath{\rightarrow} aP\ensuremath{\mathbf{.}}$	$P\ensuremath{\rightarrow} Q\ensuremath{\mathbf{.}} b$	$P\ensuremath{\rightarrow} Qb\ensuremath{\mathbf{.}}$
	$Q\ensuremath{\rightarrow} Q\ensuremath{\mathbf{.}} S$
	$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} aP$
T4S=T6	T4a=T2
$Q\ensuremath{\rightarrow} QS\ensuremath{\mathbf{.}}$

Magyarázat a halmazokhoz:

T₀:
Az $S'\ensuremath{\rightarrow} S$ belekerül mindenképpen. Mivel ebben S áll a pont mögött, a lezáráskor beletesszük a 2. szabályt is.
T₀-ból úgy lépünk tovább, hogy megnézzük, hogy milyen szimbólumok állnak a pont mögött T₀-beli szabályban (most ez a és S) és képezzük a T₀ + adott szimbólum alakú újabb halmazokat, ez most T₀S=T₁ és T₀a=T₂. Ezen halmazok elemeit majd később kiszámoljuk.

T₁:
Mivel T₁=T₀S, az alapító (és egyben egyetlen) elemet úgy kapjuk, hogy a T₀-beli 1. szabályban átemeljük a pontot az S-en.

T₂:
Mivel ez a halmaz T₀-ból jön a-val, az alapító eleme az 1. elem lesz. Ebből lezárással jön a 2. és a 3., végül mind a 2. mind a 3. szabályból jöhet lezárással a $Q\ensuremath{\rightarrow}\ensuremath{\mathbf{.}}$ szabály (de persze csak egyszer írjuk ki), ami a $Q\ensuremath{\rightarrow}\epsilon$-nak felel meg, de az $\epsilon$-t nem írjuk, csak a $\ensuremath{\mathbf{.}}$-t.

T₁-ből nem tudunk újabb halmazt származtatni, mert nincs benne olyan szabály, ahol pont után bármi lenne. T₂-ből jön a T₃ (P-vel) és a T₄ (Q-val).

T₃:
Csak egy elem van, az alpító elem, amit T₂-ből kapunk.

T₄:
Alapítóként bekerül az első két szabály, aztán a 2. miatt még a 3. is.

T₅=T₄b és T₆=T₄S:
Csak egy-egy elemük van, az egy-egy alapító elem, melyeket T₄-ből kapunk.

T₄a=T₂:
Mert ugyanazok a szabályok jelennek meg, mint T₂-ben.

Az elemzőtábla:

		a	b	S	P	Q
T0	S	T2		T1
T1	A
T2	4				T3	T4
T3	1
T4	S	T2	T5	T6
T5	2
T6	3

Magyarázat az elemzőtáblához:

Az ugrórészt aszerint töltjük ki, hogy hogyan származnak egymásból a T_i halmazok. Például, mivel T₀a=T₂, ezért a T₀-s sorba az a-s oszlopba azt írjuk, hogy T₂.

Az action rész:
Ha van $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}}$ elem egy halmzaban (ilyen a T₁, akkor A).
Ha van valami más befejeződő szabály (mint például T₂-ben a $Q\ensuremath{\rightarrow}\ensuremath{\mathbf{.}}$), akkor a szabály száma (ami itt most a 4).
Ha van pont után terminális valahol, akkor meg S(hift). (Például T₀-ban a 2. szabályban.)
Ha ütközés lenne valahol (két különböző dolgot akarnánk ugyanoda suvasztani, akkor nem LR(0) elemezhető a nyelvtan, de most itt ilyen nincsen).

(b)

Az elemzés:
$(T_0\;,\;aabb\;,\;\epsilon)\ensuremath{\rightarrow}$
$(T_0aT_2\;,\;abb\;,\;\epsilon)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4\;,\;abb\;,\;4)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4aT_2\;,\;bb\;,\;4)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4aT_2QT_4\;,\;bb\;,\;44)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4aT_2QT_4bT_5\;,\;b\;,\;44)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4aT_2PT_3\;,\;b\;,\;442)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4ST_6\;,\;b\;,\;4421)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4\;,\;b\;,\;44213)\ensuremath{\rightarrow}$
$(T_0aT_2QT_4bT_5\;,\;\epsilon\;,\;44213)\ensuremath{\rightarrow}$
$(T_0aT_2PT_3\;,\;\epsilon\;,\;442132)\ensuremath{\rightarrow}$
$(T_0ST_1\;,\;\epsilon\;,\;4421321)\ensuremath{\rightarrow}$Accept.

Pici magyarázat az elemzéshez:
Mindig aszerint cselekszünk, hogy milyen T van a verem tetején (azaz a verem milyen állapotban van). Ha T_i van a verem tetején, akkor a T_i-nek megfelelő sor action része játszik.

Ha ez S(hift) (pl. 1. sor, ahol a T₀-ban shiftelni kell), akkor berakjuk a következő szimbólumot az inputról a verembe, és az ugrótábla alapján kiszámítjuk az új veremállapotot (T₀-hoz és a-hoz T₂ az új állapot).

Ha az action egy letörés (mint például a 6. sorban, a T₅ állapotban), akkor megkeressük a verem tetején a T-k között annak a szabálynak a jobboldalát ami szerint le akarunk törni (ez most a 2. szabály jobboldala, vagyis aP), ezt kivesszük a veremből és visszaírjuk a szabály baloldalát (ez most az S). Ezután kiszámítjuk, hogy mi lesz az új állapot. Úgy tesszük ezt, hogy megnézzük, hogy milyen állapotba került a verem, amikor kivettük a jobboldalt (ez most T₄) és megnézzük, hogy a baloldal hatására (S) mi lesz az új állapot (az ugrótábla mutatja, hogy T₆).

Ha Accept a tennivaló, akkor befejezzük az elemzést és megállunk. Még egy nehezebb pont: amikor a 4. szabály szerint törünk le (pl. 2. sor), akkor a semmit, ami most a szabály jobboldala a verem legtetején keressük, és helyettesítjük Q-val, a szabály baloldalával. Ez tehát olyan, mintha csak beraknánk egy Q-t a verem tetejére.