Ejercicios del artículo "LR Parsing",

A continuación, un ejercicio propuesto por el artículo LR Parsing, de A.V. Aho y S. C. Johnson

pa (Parsing Action)

	Siguiente símbolo de entrada
Estado	'a'	'b'	','	'$'
0	shift	shift	error	error
1	error	error	shift	accept
2	error	error	Red. 2	Red 2
3	error	error	Red. 3	Red. 3
4	error	error	Red. 4	Red. 4
5	shift	shift	error	error
6	error	error	Red. 1	Red 1

Ejemplo: pa(5, ‘b’)= shift;  pa(4, 'a')= error

Nota de traducción: shift=apilar; Red.=reducir

Reglas gramaticales
(1) LIST --> LIST ',' ELEMENT
(2) LIST --> ELEMENT
(3) ELEMENT --> 'a'
(4) ELEMENT --> 'b'

goto (Goto table)

	Label of new root
Estado de más a la derecha	LIST	ELEMENT	‘a’	‘b’	‘,’
0	1	2	3	4
1					5
2
3
4
5		6	3	4
6

Ejemplo: goto(0, LIST)= 1;   goto(1, ',')= 5

Los espacios vacíos nunca deberían ser consultados por el parser.

Input string: a,b,a

Acción	Raíces del árbol de derivación (y estado asociado)*	Input remanente
Inicialización: 0	(0)	a,b,a $end
pa(0, ‘a’) => apilar	(0), ‘a’	,b,a $end
goto(0, ‘a’) => 3	(0), ‘a’ (3)	,b,a $end
pa(3, ‘,’) => reducir (3)	(0), ‘ELEMENT’	,b,a $end
goto(0, ‘ELEMENT’) => 2	(0), ‘ELEMENT’ (2)	,b,a $end
pa(2, ‘,’) => reducir (2)	(0), ‘LIST’	,b,a $end
goto(0, ‘LIST’) => 1	(0), ‘LIST’ (1)	,b,a $end
pa(1, ‘,’) => apilar	(0), ‘LIST’ (1), ‘,’	b,a $end
goto(1, ‘,’) => 5	(0), ‘LIST’ (1), ‘,’ (5)	b,a $end
pa(5, ‘b’) => apilar	(0), ‘LIST’ (1), ‘,’ (5), ‘b’	,a $end
goto(5, ‘b’) => 4	(0), ‘LIST’ (1), ‘,’ (5), ‘b’ (4)	,a $end
pa(4, ‘,’) => reducir (4)	(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’	,a $end
goto(5, ‘ELEMENT’) => 6	(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’ (6)	,a $end
pa(6, ‘,’) => reducir (1)	(0), ‘LIST’	,a $end
goto(0, ‘LIST’) => 1	(0), ‘LIST’ (1)	,a $end
pa(1, ‘,’) => apilar	(0), ‘LIST’ (1), ‘,’	a $end
goto(1, ‘,’) => 5	(0), ‘LIST’ (1), ‘,’ (5)	a $end
pa(5, ‘a’) => apilar	(0), ‘LIST’ (1), ‘,’ (5), ‘a’	$end
goto(5, ‘a’) => 3	(0), ‘LIST’ (1), ‘,’ (5), ‘a’ (3)	$end
pa(3, $end) => reducir (3)	(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’	$end
goto(5, ‘ELEMENT’) => 6	(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’ (6)	$end
pa(6, $end) => reducir (1)	(0), ‘LIST’	$end
goto(0, ‘LIST’) => 1	(0), ‘LIST’ (1)	$end
pa(1, $end) => accept	(0), ‘LIST’ (1)	$end

* Solamente el estado inicial, [0], no está asociado a ninguna raíz.