Cómo modificar las acciones semánticas al eliminar la recursión izquierda de un grammer

Question

¿Hay algún algoritmo que nos diga cómo modificar las acciones semánticas asociadas con una gramática recursiva izquierda? Por ejemplo, tenemos la siguiente gramática y sus acciones semánticas asociadas:

$ S rectarrow id = expr $ {ss = expr.size}

S $ rectarrow $ if expr entonces $ s_1 $ else $ s_2 $ {$ s_1.t = st + 2; $ $ S_2.t = st + 2; $ $ ss = expr.size + s_1.size + s_2.size + 2; $}

S $ rectarrow $ mientras expr hace $ s_1 $ {$ s_1.t = st + 4; $ $ ss = expr.size + s_1.s + 1; $}

S $ rectarrow $ $ s_1 $; $ S_2 $ {$ S_1.T = S_2.T = ST; $ $ SS = S_1.S + S_2.S; ps

Claramente, la versión no recursiva del Grammer es:

S $ rectarrow $ id = expr t

S $ rectarrow $ si expr entonces $ s_1 $ else $ s_2 $ t

S $ rectarrow $ mientras expr do $ s_1 $ t

T $ rectarrow $; $ S_2 $ t

T $ rectarrow $ $ epsilon $

Pero también necesitamos cambiar las acciones semánticas en consecuencia. ¿Alguna idea de cómo se puede hacer esto?

Answer 1

Por lo que he descubierto, no existe una técnica general para modificar las acciones semánticas mientras elimina la recursión izquierda. En cambio, el mejor método es tomar un ejemplo representativo, dibujar su árbol de análisis y luego verificar qué acciones semánticas nos dan el mismo resultado que la gramática anterior.

Answer 2

Tengo una solución parcial (estoy buscando una general). Si su gramática no tiene producciones de Epsilon, entonces no hay terminales anulables. Esto significa que el algoritmo para eliminar la recursión izquierda pasa (aunque introduce producciones de Epsilon).

Si agrega acciones semánticas de la acción de formulario (etiqueta, cuenta) que reconocen la cadena vacía y usa un analizador de cambio/reducción, y examina todas las alternativas **, no es necesario reorganizar el árbol de análisis. Al analizar, si se reconoce un terminal, empuja un atributo a la pila de analizador, esta es una acción de cambio. Cuando se encuentra una acción, aparece N valores de la pila y empuja un nodo con la etiqueta especificada y los valores aparecen de la pila, en reversa, como niños. Esta es la acción de reducir.

El analizador debe propagar la posición actual y la pila de analizador, y las operaciones de cambio y reducción deben realizarse con actualizaciones funcionales, no mutaciones. Entonces está claro que la refactorización de la gramática no cambia la secuencia de cambio y reduce las acciones, por lo que el árbol de análisis resultante es invariante bajo refactorización.

Esto significa que si genera un AST en lugar de un árbol de análisis, debe consultar los atributos por número. La maquinaria funciona porque la pila de analizador y la pila de control están desacopladas y la refactorización solo cambia la pila de control. La dificultad es que la gramática debe ser libre de Epsilon inicialmente porque los términos de acción de reducción son anulables.

** La suposición de todas las alternativas se examinan para que el orden de consideración sea irrelevante. Aunque las refactorizaciones producen gramáticas equivalentes, no existe una garantía automática de que los árboles de análisis resultantes serán los mismos a menos que se examinen todas las posibilidades. En ese caso, el orden permanece indeterminado, pero el conjunto de resultados será igual.