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.
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.
No hay comentarios:
Publicar un comentario