Eliminación de la Recursión por la Izquierda en un Esquema de Traducción

La eliminación de la recursión por la izquierda es sólo un paso: debe ser extendida a esquemas de traducción, de manera que no sólo se preserve el lenguaje sino la secuencia de acciones. Supongamos que tenemos un esquema de traducción de la forma:



$ A \rightarrow A \alpha$ { alpha_action }
$ A \rightarrow A \beta$ { beta_action }
$ A \rightarrow \gamma$ { gamma_action }


para una sentencia como $ \gamma \beta \alpha$ la secuencia de acciones será:

gamma_action beta_action alpha_action

¿Cómo construir un esquema de traducción para la gramática resultante de eliminar la recursión por la izquierda que ejecute las acciones asociadas en el mismo orden?. Supongamos para simplificar, que las acciones no dependen de atributos ni computan atributos, sino que actúan sobre variables globales. En tal caso, la siguiente ubicación de las acciones da lugar a que se ejecuten en el mismo orden:



$ A \rightarrow \gamma$ { gamma_action } $ R$
$ R \rightarrow \beta$ { beta_action } $ R$
$ R \rightarrow \alpha$ { alpha_action } $ R$
$ R \rightarrow \epsilon$

Si hay atributos en juego, la estrategia para construir un esquema de traducción equivalente para la gramática resultante de eliminar la recursividad por la izquierda se complica.

Casiano Rodríguez León
2016-03-27