viernes, 3 de febrero de 2017

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.