lunes, 13 de marzo de 2017

Ejercicio LR Parsing sección 6.2, "Constructing the Collection of Accessible Sets of Items"

Ejercicio propuesto por el enunciado

The reader should verify that these two items 
[ACCEPT → LIST .]
[LIST → LIST . ',' ELEMENT]
are the only items valid for the viable prefix LIST.

La verificación será realizada a partir de los items generados por la gramática
ACCEPT → LIST
LIST → LIST ',' ELEMENT
LIST → ELEMENT
ELEMENT → 'a'
ELEMENT → 'b'
estableciendo γ y α a valores apropiados según cada ítem y comprobando que los 2 del enunciado son los únicos que validan los datos del enunciado contra la definición de valid item. La tabla siguiente comprende la resolución del ejercicio según lo explicado.

Ítem
γ
α
β
A
γ.A
¿γA válido? / ¿Hay alguna forma de hacer γα=LIST para γA?
ACCEPT → ⋅ LIST
LIST
''
LIST
ACCEPT
LIST ACCEPT
no / sí
ACCEPT → LIST ⋅
''
LIST
''
ACCEPT
ACCEPT
sí / sí
LIST → ⋅ LIST ',' ELEMENT
LIST
''
LIST ',' ELEMENT
LIST
LIST LIST
no / sí
LIST → LIST ⋅ ',' ELEMENT
''
LIST
',' ELEMENT
LIST
LIST
sí / sí
LIST → LIST ',' ⋅ ELEMENT
''
LIST ','
ELEMENT
LIST
LIST
sí / no
LIST → LIST ',' ELEMENT ⋅
''
LIST ',' ELEMENT
''
LIST
LIST
sí / no
LIST → ⋅ ELEMENT
LIST
''
ELEMENT
LIST
LIST LIST
no / sí
LIST → ELEMENT ⋅
''
ELEMENT
''
LIST
LIST
sí / no
ELEMENT → ⋅ 'a'
LIST
''
'a'
ELEMENT
LIST ELEMENT
no / sí
ELEMENT → 'a' ⋅
''
'a'
''
ELEMENT
ELEMENT
sí / no
ELEMENT → ⋅ 'b'
LIST
''
'b'
ELEMENT
LIST ELEMENT
no / sí
ELEMENT → 'b' ⋅
''
'b'
''
ELEMENT
ELEMENT
sí / no