Esquemas de Traducción

Definición 2.4.1   Un esquema de traducción es una gramática independiente del contexto en la cual se han insertado fragmentos de código en las partes derechas de sus reglas de producción. Los fragmentos de código asi insertados se denominan acciones semánticas. Dichos fragmentos actúan, calculan y modifican los atributos asociados con los nodos del árbol sintáctico. El orden en que se evalúan los fragmentos es el de un recorrido primero-profundo del árbol de análisis sintáctico.

Obsérvese que, en general, para poder aplicar un esquema de traducción hay que construir el árbol sintáctico y después aplicar las acciones empotradas en las reglas en el orden de recorrido primero-profundo. Por supuesto, si la gramática es ambigua una frase podría tener dos árboles y la ejecución de las acciones para ellos podría dar lugar a diferentes resultados. Si se quiere evitar la multiplicidad de resultados (interpretaciones semánticas) es necesario precisar de que árbol sintáctico concreto se esta hablando.

Por ejemplo, si en la regla $A \rightarrow \alpha \beta$ insertamos un fragmento de código:

$A \rightarrow \alpha \{ action \} \beta$

La acción $\{ action \}$ se ejecutará después de todas las acciones asociadas con el recorrido del subárbol de $\alpha$ y antes que todas las acciones asociadas con el recorrido del subárbol $\beta$.

El siguiente esquema de traducción recibe como entrada una expresión en infijo y produce como salida su traducción a postfijo para expresiones aritmeticas con sólo restas de números:

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

Las apariciones de variables sintácticas en una regla de producción se indexan como se ve en el ejemplo, para distinguir de que nodo del árbol de análisis estamos hablando. Cuando hablemos del atributo de un nodo utilizaremos el punto (.). Aquí VAL es un atributo de los nodos de tipo $NUM$ denotando su valor numérico y para accederlo escribiremos NUM.VAL. Análogamente expr.TRA denota el atributo traducción de los nodos de tipo $expr$.

Ejercicio 2.4.1   Muestre la secuencia de acciones a la que da lugar el esquema de traducción anterior para la frase 7 -5 -4.

En este ejemplo, el cómputo del atributo expr.TRA depende de los atributos en los nodos hijos, o lo que es lo mismo, depende de los atributos de los símbolos en la parte derecha de la regla de producción. Esto ocurre a menudo y motiva la siguiente definición:

Definición 2.4.2   Un atributo tal que su valor en todo nodo del árbol sintáctico puede ser computado en términos de los atributos de los hijos del nodo se dice que es un atributo sintetizado.