Traducción dirigida por la sintaxis en el diseño del compilador – Part 1

Parser usa un CFG (Gramática libre de contexto) para validar la string de entrada y generar resultados para la siguiente fase del compilador. La salida podría ser un árbol de análisis o un árbol de sintaxis abstracta. Ahora, para intercalar el análisis semántico con la fase de análisis de sintaxis del compilador, usamos la traducción dirigida por la sintaxis. 

Conceptualmente, tanto con la definición dirigida por la sintaxis como con los esquemas de traducción, analizamos el flujo del token de entrada, construimos el árbol de análisis y luego recorremos el árbol según sea necesario para evaluar las reglas semánticas en los Nodes del árbol de análisis. La evaluación de las reglas semánticas puede generar código, guardar información en una tabla de símbolos, emitir mensajes de error o realizar cualquier otra actividad. La traducción del flujo de tokens es el resultado obtenido al evaluar las reglas semánticas.

Definición 
Sintaxis La traducción dirigida tiene reglas aumentadas a la gramática que facilitan el análisis semántico. SDT implica pasar información de abajo hacia arriba y/o de arriba hacia abajo al árbol de análisis en forma de atributos adjuntos a los Nodes. Las reglas de traducción dirigidas por la sintaxis usan 1) valores léxicos de Nodes, 2) constantes y 3) atributos asociados con los no terminales en sus definiciones. 

El enfoque general de la traducción dirigida por la sintaxis es construir un árbol de análisis sintáctico o un árbol de sintaxis y calcular los valores de los atributos en los Nodes del árbol visitándolos en algún orden. En muchos casos, la traducción se puede realizar durante el análisis sin generar un árbol explícito. 
Ejemplo 
 

E -> E+T | T
T -> T*F | F
F -> INTLIT 

Esta es una gramática para validar sintácticamente una expresión que contiene sumas y multiplicaciones. Ahora, para llevar a cabo el análisis semántico, aumentaremos las reglas SDT a esta gramática, para pasar alguna información al árbol de análisis y comprobar si hay errores semánticos, si los hay. En este ejemplo, nos centraremos en la evaluación de la expresión dada, ya que no tenemos afirmaciones semánticas para verificar en este ejemplo muy básico. 
 

E -> E+T     { E.val = E.val + T.val }   PR#1
E -> T       { E.val = T.val }           PR#2
T -> T*F     { T.val = T.val * F.val }   PR#3
T -> F       { T.val = F.val }           PR#4
F -> INTLIT  { F.val = INTLIT.lexval }   PR#5

Para comprender mejor las reglas de traducción, tomamos la primera regla de producción SDT aumentada a [ E -> E+T ]. La regla de traducción en consideración tiene val como atributo para ambos no terminales: E y T. El lado derecho de la regla de traducción corresponde a los valores de atributo de los Nodes del lado derecho de la regla de producción y viceversa. Generalizando, SDT son reglas aumentadas a un CFG que asocian 1) un conjunto de atributos a cada Node de la gramática y 2) un conjunto de reglas de traducción a cada regla de producción usando atributos, constantes y valores léxicos. 

Tomemos una string para ver cómo ocurre el análisis semántico: S = 2+3*4. El árbol de análisis correspondiente a S sería 

Para evaluar las reglas de traducción, podemos emplear un recorrido de búsqueda primero en profundidad en el árbol de análisis. Esto es posible solo porque las reglas SDT no imponen ningún orden específico en la evaluación hasta que los atributos de los niños se calculan antes que los padres para una gramática que tiene todos los atributos sintetizados. De lo contrario, tendríamos que encontrar el plan más adecuado para atravesar el árbol de análisis y evaluar todos los atributos en uno o más recorridos. Para una mejor comprensión, nos moveremos de abajo hacia arriba de izquierda a derecha para calcular las reglas de traducción de nuestro ejemplo. 

El diagrama anterior muestra cómo podría ocurrir el análisis semántico. El flujo de información ocurre de abajo hacia arriba y todos los atributos de los hijos se calculan antes que los de los padres, como se discutió anteriormente. Los Nodes del lado derecho a veces se anotan con el subíndice 1 para distinguir entre hijos y padres. 
Información adicional 
Los atributos sintetizados son atributos que dependen únicamente de los valores de atributo de los Nodes secundarios. 
Por lo tanto, [ E -> E+T { E.val = E.val + T.val } ] tiene un atributo sintetizado val correspondiente al Node E. Si se sintetizan todos los atributos semánticos en una gramática aumentada, un recorrido de búsqueda primero en profundidad en cualquier orden es suficiente para la fase de análisis semántico. 

Los atributos heredados son atributos que dependen de los atributos de los padres y/o hermanos. 
Por lo tanto, [ Ep -> E+T { Ep.val = E.val + T.val, T.val = Ep.val } ], donde E y Ep son los mismos símbolos de producción anotados para diferenciar entre padre e hijo, tiene un atributo val correspondiente al Node T.