Sig: Ejercicio Sup: Recursión por la Izquierda Ant: Eliminación de la Recursión Err: Si hallas una errata ...

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. Consideremos de nuevo el esquema de traducción de infijo a postfijo de expresiones aritméticas de restas:

$expr \rightarrow expr_1 - NUM$	{ $expr{T} = $expr[1]{T}." ".$NUM{VAL}." - "}
$expr \rightarrow NUM$	{ $expr{T} = $NUM{VAL} }

En este caso introducimos un atributo H para los nodos de la clase $r$ el cuál acumula la traducción a postfijo hasta el momento. Observe como este atributo se computa en un nodo $r$ a partir del correspondiente atributo del el padre y/o de los hermanos del nodo:

$expr \rightarrow NUM$ { $r{H} = $NUM{VAL} } $r$ { $expr{T} = $r{T} }
$r \rightarrow - NUM$ { $r_1{H} = $r{H}." ".$NUM{VAL}." - " } $r_1$ { $r{T} = $r_1{T} }
$r \rightarrow \epsilon$ { $r{T} = $r{H} }

El atributo H es un ejemplo de atributo heredado.

Sig: Ejercicio Sup: Recursión por la Izquierda Ant: Eliminación de la Recursión Err: Si hallas una errata ...