domingo, 30 de abril de 2017

Notas finales sobre el artículo de Aho y Johnson

Esto viene a ser un cierre a una serie de escritos en torno a un artículo titulado L.R. Parsing, autoría de A.V. Aho y S.C. Johnson. Varias de ellas son glosas y otras ejercicios resueltos. Al pie se detallan las referencias.

Notas finales:
Entre right parse y righmost derivation puede establecerse una relación, entendida como que cada una de las reescrituras de una right derivación se emparentan con cada uno de los estadíos de un right parse de modo que los símbolos de dicho estadío son prefijo de la cadena reescrita, y lo que no es prefijo, es una cadena de símbolos terminales igual al input que falta incorporar al right parse en ese estadío. Además, dicho prefijo no es cualquiera, sino que es siempre un viable prefix.

La closure operation tiene un operando y un resultado, ambos definidos bajo el nombre de "ítem". El hecho de que para esta operación se exija que los símbolos del lookahead set previo estén concatenados a la cadena de cuya derivación se extraerá el nuevo lookeahead set tiene un significado importante. Algunas derivaciones podrían realizarse que sean válidas en forma aislada pero que no pudieran formar una right sentential form en el lugar desde donde se están generando. Concatenando a estas derivaciones los símbolos del lookahead set previo queda en evidencia su falta de sentido, y por otro lado, la validez de las derivaciones que sí la tienen.

Artículos anteriores de esta serie:
Ejercicio de La Sección 6.4, "Computing Lookahead Sets"
Ejercicio LR Parsing Sección 6.2, "Constructing the Collection of Accessible Set of Items"
Ejercicio Propuesto En El Artículo LR Parsing En La Sección 6.1, "Sets Of Items"
Notas Sobre El Artículo L.R. Parsing
Parseo Simple
Otro Ejercicio del Artículo L.R. Parsing
Ejercicios del Artículo L.R. Parsing

lunes, 10 de abril de 2017

Ejercicio de la sección 6.4 computing lookahead sets

The reader should verify that the complete collection of sets of items for G₁ is:

I₀: [ACCEPT → ⋅ LIST], {'$'}
[LIST → ⋅ LIST ',' ELEMENT], {',', '$'}
[LIST→ ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT →  ⋅ 'b'], {',', '$'}
I₁: [ACCEPT → LIST ⋅ ], {'$'}
[LIST → LIST ⋅ ',' ELEMENT], {',', '$'}
I₂: [LIST → ELEMENT ⋅ ], {',', '$'}
I₃: [ELEMENT → 'a' ⋅ ], {',', '$'}
I₄: [ELEMENT → 'b' ⋅ ], {',', '$'}
I₅: [LIST → LIST ',' ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT → ⋅ 'b'], {',', '$'}
I₆: [LIST → LIST ',' ELEMENT ⋅ ], {',', '$'}



Teniendo en cuenta que hay 2 formas de generar los sets de items, se elegirá uno teniendo en cuenta lo siguiente.
Una de las formas tiene más que ver con las definiciones de viable prefix y valid item, y la otra con un símbolo especial (ACCEPT) que expande la gramática con una nueva regla, una operación llamada closure que completa los items de cada set. Ambas tienen en cuenta uno y sólo un símbolo de desplazamiento en el cálculo de cada nuevo estado, El 2do. método es más natural a lo realizado por un parser en ejecución: partir de un estado, desplazar un símbolo y cambiar a un nuevo estado. El 1er. método requiere una cadena auxiliar para usarla de viable prefix al aplicar la definición de valid item. Es auxiliar en el sentido de que sólo forma parte del proceso de construcción pero no del parser construido.
Finalmente, por simplicidad se elegirá el 2do. método para este ejercicio.
Los sets de items I₀, I₁, I₂, I₃ e I₄ ya fueron calculados en la sección 6.2, de la cual el cálculo de los lookehead sets no formaba parte. También fueron calculados, en la sección 6.4, los lookahead sets para I₀ e I₃, más allá de que este último sea referido en dicha sección como I₂, cosa que aquí no tiene importancia.
Dando por hecho los sets de items y lookahead sets mencionados, se procederá a completar la collección, aplicando las definiciones de las secciones 6.2 y 6.4.

El único ítem de I₁ surge de desplazarse a través de LIST sobre el ítem [ACCEPT → ⋅ LIST] {$} y conservando su lookahead set al no haber closure operation aplicable. Como resultado se tiene:
I₁: [ACCEPT → LIST ⋅ ], {'$'}

Para I₂ el razonamiento por ende es el mismo lookahead set que el del ítem del cual procede, que es [LIST→ ⋅ ELEMENT], {',', '$'}. Según esto:
I₂: [LIST → ELEMENT ⋅ ], {',', '$'}

Lo mismo pasa con el único ítem de I₄ (I₃, como se dijo, se da por hecho), cuyo antecesor es [ELEMENT →  ⋅ 'b'], {',', '$'}, y 'b' el símbolo "atravesado" (a través del cual nos desplazamos), siendo pues:
I₄: [ELEMENT → 'b' ⋅ ], {',', '$'}

Se resolverá un nuevo set de items por medio de GOTO(I₁, ','):
Desplazándose a través de un símbolo ',' sobre un ítem de I₁ único donde esto tiene sentido se genera el ítem [LIST → LIST ',' ⋅ ELEMENT], {',', '$'}. Siendo que no hay símbolos entre ELEMENT y el final de la regla, su lookahead set tiene el mismo potencial de formar right sentential form en presencia de esta instancia de ELEMENT como así de todas sus derivaciones por derecha, de modo que el lookahead set no cambia. Conociendo la closure operation sobre ELEMENT, el estado completo queda:
[LIST → LIST ',' ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT → ⋅ 'b'], {',', '$'}
Que viene a ser I₅.

GOTO(I₅, ELEMENT) da como resultado exactamente I₆, no habiendo ni closure operation que valga ni posibilidad de que el lookahead set sea modificado, por razonamientos similares a los seguidos hasta aquí.

Por más GOTO(I,X) que se intente, ya no queda forma de expandir la colección de sets de items. Queda pues verificado el enunciado.