Parseo simple

El siguiente ejercicio proviene del mismo lugar que uno publicado unos días atrás. Los datos del ejercicio que se mantienen igual, no se vuelven a exponer. En particular, la Parsing Action y Goto table son los mismos que en dicho artículo.


Lo que cambia es el input string, y obviamente el seguimiento del parser, manteniéndose iguales la pa (parsing action), la goto (goto table) y las reglas gramaticales.


Input string: a,,b

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

* Solamente el estado inicial (0) no está asociado a ninguna raíz.

Otro ejercicio del artículo "LR Parsing"

El siguiente ejercicio proviene del mismo lugar que uno publicado unos días atrás. Los datos del ejercicio que se mantienen igual, no se vuelven a exponer. En particular, la Parsing Action y Goto table son los mismos que en dicho artículo.
Lo que cambia es el input string, y obviamente el seguimiento del parser, manteniéndose iguales la pa (parsing action), la goto (goto table) y las reglas gramaticales.

Input string: a,ba

Acción	Raíces del árbol de derivación (y estado asociado)*	Input remanente
Inicialización: 0	(0)	a,ba $end
pa(0, ‘a’) => apilar	(0), ‘a’	,ba $end
goto(0, ‘a’) => 3	(0), ‘a’ (3)	,ba $end
pa(3, ‘,’) => reducir (3)	(0), ‘ELEMENT’	,ba $end
goto(0, ‘ELEMENT’) => 2	(0), ‘ELEMENT’ (2)	,ba $end
pa(2, ‘,’) => reducir (2)	(0), ‘LIST’	,ba $end
goto(0, ‘LIST’) => 1	(0), ‘LIST’ (1)	,ba $end
pa(1, ‘,’) => apilar	(0), ‘LIST’ (1), ‘,’	ba $end
goto(1, ‘,’) => 5	(0), ‘LIST’ (1), ‘,’ (5)	ba $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, ‘a’) => error	(0), ‘LIST’ (1), ‘,’ (5), ‘b’	a $end

 * Solamente el estado inicial (0) no está asociado a ninguna raíz.

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.