tds
DESCRIPTION
compiladorTRANSCRIPT
![Page 1: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/1.jpg)
Traducción Dirigida por Traducción Dirigida por la Sintáxisla Sintáxis
Diseño y Construcción de Compiladores2008
Área de Autómatas y Lenguajes
![Page 2: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/2.jpg)
Traducción Dirigida por la SintáxisTraducción Dirigida por la Sintáxis
El significado de una sentencia de entrada está relacionado con su estructura sintáctica.
Encierran aquellos formalismos utilizados para especificar las traducciones para las construcciones de los lenguajes de programación guiadas por una GLC.
◦ Se Asocian Atributos a los símbolos de la gramática.
◦ Se computan los valores de atributos por reglas semánticas asociadas a las producciones de la gramática.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 2
![Page 3: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/3.jpg)
Traducción Dirigida por la SintáxisTraducción Dirigida por la Sintáxis
La evaluación de las reglas semánticas puede:◦Generar Código.◦Insertar información en la Tabla de Símbolos.◦Relizar el Chequeo Semántico.◦Dar mensajes de error◦Etc.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 3
![Page 4: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/4.jpg)
Traducción Dirigida por la SintáxisTraducción Dirigida por la Sintáxis
Existen dos notaciones para asociar información a las reglas semánticas:
Definiciones Dirigidas por la Sintáxis: es una especificación de alto nivel que oculta detalles de implementación.
Esquemas de traducción: están más orientados a la implementación porque indican el orden en el cual se evalúan las reglas semánticas.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 4
![Page 5: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/5.jpg)
ÍndiceÍndice
Gramáticas de Atributos
Definiciones Dirigidas por la Sintáxis.◦ Definiciones S-Atribuidas◦ Definiciones L-Atribuidas
◦ Implementación de las Definiciones Dirigidas por la Sintáxis: Grafo de Dependencias Definiciones S-Atribuidas Definiciones L-Atribuidas
Esquemas de Traduccion
Compiladores 2008 - Traducción Dirigida por la Sintáxis 5
![Page 6: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/6.jpg)
Gramáticas de AtributosGramáticas de AtributosCompiladores 2008 - Traducción Dirigida por la Sintáxis 6
![Page 7: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/7.jpg)
Gramáticas de AtributosGramáticas de Atributos
Una Gramática de Atributos define la sintaxis y la semántica de un lenguaje.
También define la información que se necesita almacenar en el Árbol de Sintaxis Abstracta para llevar a cabo el Análisis Semántico y la Generación de Código.
Dicha información se almacena como atributos de los nodos del Árbol de Sintáxis Abstracta.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 7
![Page 8: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/8.jpg)
Gramáticas de AtributosGramáticas de Atributos
Sea G=<N,T,P,S> una Gramática Libre de Contexto.G es una Gramática de Atributos (GA) si:
Cada X N T está asociado con dos conjuntos disjuntos, H(X), el conjunto de los atributos hereddos y S(X) el conjunto de los atributos sintetizados. X N T.
El conjunto de atributos de G es Atr= H S. Donde H= X N H(X), S= X
N T S(X).
X0 X1X2….Xm P y aj Atr(Xi), 0 i m, entonces Xi.aj es el atributo aj de Xi y Dxi,aj es el dominio de valores de Xi.aj.
Una regla semántica asociada con X0 X1X2….Xm P es de la forma Xi.aj=f(b1
j1,…..,bkjk), 0 jl m, 0 i m, donde cada bl
jl Atr(Xjl).
Compiladores 2008 - Traducción Dirigida por la Sintáxis 8
![Page 9: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/9.jpg)
Atributos SintetizadosAtributos SintetizadosCompiladores 2008 - Traducción Dirigida por la Sintáxis 9
X0
X1 Xi Xn
Atributo Sintetizado: Un atributo a es sintetizado si, dada una regla de una gramática AX1X2….Xn la ecuación asociada con a es de la forma:
A.a=f(X1.a1,….X1.ak,….,Xn.a1,…Xn.ak).En otras palabras a es un atributo sintetizado si su valor depende de los valores de atributos de sus hijos.
![Page 10: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/10.jpg)
Atributos HeredadosAtributos Heredados
Atributo Heredado: Un atributo que no es sintetizado es un atributo heredado. En otras palabras un atributo heredado es aquel cuyo valor de atributo está definido en términos de los valores de atributos del padre o de sus hermanos.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 10
X0
X1 Xi Xn
![Page 11: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/11.jpg)
Ejemplos de Gramáticas de Ejemplos de Gramáticas de AtributosAtributos
Dada la siguiente gramática G1:
a. NRO DIG | NRO DIGb. DIG 0|1|2|3|4|5|6|7|8|9
Calcular el valor de los números generados por G usando un atributo sintetizado val.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 11
![Page 12: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/12.jpg)
Ejemplos de Gramáticas de Ejemplos de Gramáticas de AtributosAtributos
La siguiente gramática expresa declaraciones en una sintaxis similar a la usada por el lenguaje C:G2:
a. DECL TYPE VAR-LISTb. TYPE INT | FLOATc. VAR-LIST ID, VAR-LIST | ID
Usando un atributo heredado determine el tipo de los identificadores
Compiladores 2008 - Traducción Dirigida por la Sintáxis 12
![Page 13: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/13.jpg)
Ejemplos de Gramáticas de Ejemplos de Gramáticas de AtributosAtributos
Ejercicio: La siguiente gramática permite expresar números en decimal y octal:G3:
a. BNRONRO Bb. B O|Dc. NRO NRO DIG | DIGd. DIG 0|1|2|3|4|5|6|7|8|9
Defina los atributos y reglas semánticas necesarias para calcular el valor del número.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 13
![Page 14: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/14.jpg)
Definiciones Dirigidas por la Definiciones Dirigidas por la SintáxisSintáxis
Compiladores 2008 - Traducción Dirigida por la Sintáxis 14
![Page 15: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/15.jpg)
DDSDDS
DDS: Son Gramáticas de Atributos en las cuales no se especifica el orden de evaluación de las reglas semánticas.
Las gramáticas de atributos G1 y G2 son ejemplos de definiciones dirigidas por la sintaxis.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 15
![Page 16: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/16.jpg)
DDS-FormatoDDS-Formato
Cada producción A está asociada con un conjunto de reglas semánticas de la foma:
b=f(c1,c2,...,ck) donde f es una función y
b es un atributo Sintetizado de A y c1,c2,...,ck son atributos de los símbolos en A, o
b es un atributo Heredado de un símbolo de la gramática en , y c1,c2,...,ck son atributos de los símbolos de la gramática en o atributos de A.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 16
![Page 17: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/17.jpg)
DDSDDS
Se asume que los símbolos terminales tienen atributos sintetizados proporcionados por el Analizador Lexicográfico.
Las llamadas a procedimientos definen valores de atributos sintetizados ficticios (Dummy) del no terminal del lado izquierdo de la producción.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 17
![Page 18: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/18.jpg)
DDS-Evaluación de AtributosDDS-Evaluación de Atributos
Si en una DDS el orden de evaluación de los atributos no esta especificado entonces como se realiza la evaluación de los atributos?
Respuesta:◦Utilizando un grafo de dependencias.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 18
![Page 19: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/19.jpg)
DDS-Evaluación de AtributosDDS-Evaluación de Atributos
La implementación de una DDS consiste en encontrar un orden de evaluación de los atributos.◦Cada atributo tiene que estar disponible
cuando la computación se realiza.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 19
![Page 20: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/20.jpg)
DDS-Grafo de DependenciasDDS-Grafo de Dependencias
Un Grafo de Dependencia muestra las interdependencias entre los atributos de varios nodos en un Árbol de Parse.◦ Hay un nodo para cada atributo.◦ Si un atributo b depende de un atributo c hay un arco desde el nodo
c al nodo b.
Regla de Dependencia: Si un atributo b, en el nodo n, en un árbol de derivación depende del atributo c luego la regla semántica que define a b se debe evaluar después de la regla semántica que define a c.
La interdependencia entre atributos heredados y sintetizados se puede dibujar como un grafo dirigido. Este grafo se conoce con el nombre de Grafo de Dependencias.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 20
![Page 21: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/21.jpg)
DDS-Grafo de DependenciasDDS-Grafo de DependenciasCompiladores 2008 - Traducción Dirigida por la Sintáxis 21
![Page 22: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/22.jpg)
Grafo de Dependendia - EjemploGrafo de Dependendia - Ejemplo
Gramática G3
N Prod. R. Sem.
1 NRO1 NRO2 DIG {NRO1.val=NRO2.val+DIG.val}
2 NRO DIG {NRO.val=DIG.val}
3 DIG 0 {DIG.val=0}
4 ……. ……
Compiladores 2008 - Traducción Dirigida por la Sintáxis 22
Grafo de Dependencias para la Producción 1
NRO1.val
NRO2.valDIG.val
![Page 23: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/23.jpg)
Grafo de Dependendia - EjemploGrafo de Dependendia - EjemploCompiladores 2008 - Traducción Dirigida por la Sintáxis 23
NRO.val
NRO.val DIG.val
NRO.val DIG.val
DIG.val
Grafo de Dependencias
Árbol de Parse
Grafo de Dependencias para la Cadena 345
![Page 24: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/24.jpg)
DDS: Grafo de Dependencias-DDS: Grafo de Dependencias-Orden de EvaluaciónOrden de Evaluación
Construir el árbol de parsing para la entrada x.
Construir el Grafo de Dependencias.
Construir el Ordenamiento Topológico.
Evaluar las reglas semánticas en el orden indicado por el Ordenamiento Topológico.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 24
![Page 25: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/25.jpg)
Grafo de Dependendia - EjemploGrafo de Dependendia - EjemploCompiladores 2008 - Traducción Dirigida por la Sintáxis 25
Ejercicio: Construir Grafos de Dependencias para las Gramáticas G1 y G2 para diferentes cadenas aceptadas por las mismas.
![Page 26: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/26.jpg)
Grafo de Dependendia – Orden de EvaluaciónGrafo de Dependendia – Orden de Evaluación
Se utiliza un Ordenamiento Topológico Algoritmo Destructivo (Sólo para propósito pedagógico).
Algoritmo: Ordenamiento Topológico(G,T)Entrada: G grafo de dependencias.Salida: T el ordenamiento topológico de G.
Open el conjunto de nodos a tratar.Open←minimales(G);Mientras Open Hacer
Sea x OpenEliminar x de G Insertar x en TOpen ← Open – {x}Open ← minimales(G)
Fin MientrasRetornar T
Compiladores 2008 - Traducción Dirigida por la Sintáxis 26
![Page 27: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/27.jpg)
Compiladores 2008 - Traducción Dirigida por la Sintáxis 27
a
b
c
g
d e
f
b
c
g
d e
fc
g
d e
fc
g
e
f
a a b a a d
Grafo de Dependendia – Orden Grafo de Dependendia – Orden de Evaluaciónde Evaluación
Completar el ejemplo!
![Page 28: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/28.jpg)
Grafo de Dependendia – Orden Grafo de Dependendia – Orden de Evaluaciónde Evaluación
Compiladores 2008 - Traducción Dirigida por la Sintáxis 28
NRO.val
NRO.val DIG.val
NRO.val DIG.val
DIG.val
De el orden de evaluación del siguiente grafo de dependencias
![Page 29: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/29.jpg)
EjerciciosEjercicios
Ejercicio: Elaborar un algoritmo que permita extraer un Ordenamiento Topológico sin destruir el grafo subyacente.
Ejercicio: Elaborar un algoritmo no destructivo que permita extraer un Ordenamiento Topológico Inverso.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 29
![Page 30: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/30.jpg)
Grafo de Dependencias-Orden Grafo de Dependencias-Orden de Evaluaciónde Evaluación
Problemas con el método:◦Falla si el grafo de dependencias tiene un ciclo.◦Consume tiempo debido a la construcción del grafo
de dependencias.
Solución:◦Diseñar la DDS de tal forma que los atributos se
puedan evaluar en un orden fijo evitando la construcción del grafo de dependencias (este método es el utilizado por muchos compiladores).
Compiladores 2008 - Traducción Dirigida por la Sintáxis 30
![Page 31: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/31.jpg)
DDSDDS
En las DDS no circulares se puede establecer un orden de evaluación fijo en tiempo de construcción del compilador.
Hay dos clases importantes de definiciones no circulares:◦S-Atribuidas◦L-Atribuidas
Compiladores 2008 - Traducción Dirigida por la Sintáxis 31
![Page 32: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/32.jpg)
DDS S-AtribuidaDDS S-AtribuidaCompiladores 2008 - Traducción Dirigida por la Sintáxis 32
![Page 33: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/33.jpg)
DDS S-AtribuidaDDS S-Atribuida
DDS S-Atribuida: Es una DDS que sólo utiliza atributos sintetizados.
Esta clase de DDS es interesante porque los valores de atributo pueden ser obtenidos a través de un barrido Post Orden del Árbol de Parse.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 33
![Page 34: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/34.jpg)
DDS S-AtribuidaDDS S-AtribuidaCompiladores 2008 - Traducción Dirigida por la Sintáxis 34
Ejercicio: Determine Cuáles de las GA presentadas previamente son DDS S-Atribuidas?
![Page 35: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/35.jpg)
DDS S-AtribuidaDDS S-Atribuida
Los atributos sintetizados se pueden evaluar usando un parser bottom-up cuando se analiza la cadena de entrada evitando la construcción del grafo de dependencias.
El parser mantiene los valores de los atributos sintetizados en su pila.
Cuando se realiza una reducción A, el atributo para A se calcula a partir de los atributos de que se encuentran en la pila.
De esta manera una DDS S-Atribuida se puede implementar extendiendo la pila de un parser LR.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 35
![Page 36: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/36.jpg)
DDS S-Atribuida EvaluaciónDDS S-Atribuida EvaluaciónCompiladores 2008 - Traducción Dirigida por la Sintáxis 36
Estado Valor
Z Z.x
Y Y.x
X X.x
…… ……
• Se incorporan campos extras a la pila para mantener los valores de los atributos sintetizados.
• Por ejemplo si se está trabajando con un solo atributo sintetizado la pila tiene la siguiente forma
• El tope de la pila se mantiene con un puntero top.• Antes de que la reducción AXYZ se realize, se calcula el
atributo sintetizado de A:A.a=f(val[top],val[top-1],val[top-2])
![Page 37: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/37.jpg)
DDS S-AtribuidaDDS S-AtribuidaCompiladores 2008 - Traducción Dirigida por la Sintáxis 37
Ejercicio: Utilice la gramática G3 para evaluar la cadena 345 usando la aproximación propuesta para las gramáticas S-Atribuidas.Muestre el contenido de la pila.
![Page 38: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/38.jpg)
DDS L-AtribuidaDDS L-AtribuidaCompiladores 2008 - Traducción Dirigida por la Sintáxis 38
![Page 39: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/39.jpg)
DDS L-AtribuidaDDS L-Atribuida
Son útiles para expresar la dependencia de una construcción en el contexto en el cual aparece.
A diferencia de los atributos sintetizados el orden en el cual aparecen los atributos heredados es importante.
Es siempre posible reescribir la DDS con sólo atributos sintetizados. No obstante es más natural usar atributos heredados y sintetizados.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 39
![Page 40: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/40.jpg)
DDS L-AtribuidaDDS L-Atribuida
Definición: Una DDS es L-Atribuida si cada atributo heredado de Xj, 1 j n, en el lado derecho de una producción del tipo X0X1…Xj-
1Xj….Xn depende solo de:
Los atributos sintetizados de X1…Xj-1, a la izquierda de Xj.
Los atributos heredados de X0.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 40
![Page 41: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/41.jpg)
DDS L-AtribuidaDDS L-Atribuida
Importante:
◦Toda definición S-Atribuida es L-Atribuida.
◦Teorema: Los atributos heredados en DDS L-Atribuidas se pueden computar por un recorrido Pre-Orden del árbol de parse.
◦Las definiciones L-Atribuidas cubren todas las traducciones que se pueden realizar sin construir explicitamente el árbol de parse.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 41
![Page 42: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/42.jpg)
Evaluación de DDS L-AtribuidasEvaluación de DDS L-Atribuidas
Las DDS L-Atribuidas son una clase de DDS cuyos atributos siempre se pueden evaluar por un recorrido del árbol de parse.
El procedimiento mezcla los recorridos Post Orden (sintetizado) y Pre-Orden (heredado).
Compiladores 2008 - Traducción Dirigida por la Sintáxis 42
![Page 43: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/43.jpg)
Evaluación de DDS L-AtribuidasEvaluación de DDS L-Atribuidas
Algoritmo: L-Eval (n)Entrada N: un nodo del árbol de parse anotado.Salida: La evaluación de atributos
ComenzarPara cada hijo m de n, desde izquierda a
derecha HacerEvaluar los atributos heredados de m;L-Eval(m)
Fin ParaEvaluar los atributos sintetizados de n
Fin
Compiladores 2008 - Traducción Dirigida por la Sintáxis 43
![Page 44: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/44.jpg)
Esquemas de TraducciónEsquemas de TraducciónCompiladores 2008 - Traducción Dirigida por la Sintáxis 44
![Page 45: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/45.jpg)
Esquemas de TraducciónEsquemas de Traducción
Los esquemas de traducción están más orientados a la implementación que las DDS porque indican el orden de evaluación de las reglas semánticas.
Definición: Un ET es una gramática libre del contexto que cumple con las siguientes condiciones:
• Los atributos están asociados con los símbolos de la gramática.
• Las acciones semánticas están encerradas entre { y } y están embebidas dentro del lado derecho de las producciones.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 45
![Page 46: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/46.jpg)
Esquemas de TraducciónEsquemas de Traducción
Los ET pueden tener atributos sintetizados y heredados.
Las acciones semánticas son tratadas como símbolos terminales
Los esquemas de traducción son útiles para evaluar definiciones L-Atribuidas en tiempo de parsing.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 46
![Page 47: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/47.jpg)
Esquemas de TraducciónEsquemas de Traducción
N. G. L-Attr
1 DT L
2 Tint
3 Treal
4 L1L2,id
5 Lid
N. ET para G
1 DT{L.in=T.type} L
2 Tint {T.tipo=integer}
3 Treal {T.tipo=real}
4 L1 {L1.in=L.in} L2,id{addtype(id.entry,L.in}
5 L id{addtype(id.entry, L.in}
Compiladores 2008 - Traducción Dirigida por la Sintáxis 47
![Page 48: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/48.jpg)
Esquemas de TraducciónEsquemas de TraducciónCompiladores 2008 - Traducción Dirigida por la Sintáxis 48
Ejercicio: Construir el Árbol de Parse para la siguiente declaración:Real id1, id2, id3.
Ejercicio: Evaluar el ET.
![Page 49: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/49.jpg)
ET DiseñoET Diseño
1er Caso: Atributos Sintetizados: se puede construir un ET creando una acción semántica que es una asignación y se ubica esta acción al final de la parte derecha de la producción.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 49
Producción Regla Semántica
1) TE + T1 T.val= E.val + T1.val
2) NRO1 NRO2 DIG NRO1=NRO2.val * 10 + DIG.val
3) DIG0 DIG.val=0
![Page 50: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/50.jpg)
ET DiseñoET Diseño
2do Caso: Atributos heredados y sintetizados.◦ Un Atributo heredado por un símbolo de la parte derecha de una
producción se debe calcular en una acción que se realice antes de dicho símbolo.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 50
Producción Producción con Acciones
X0X1…Xj-1Xj…Xn X0X1…Xj-1 {Xj.h}Xj…Xn
X0X1…Xj-1Xj…Xn X0X1…Xj-1Xj{Xj.h}…..Xn
DT LID D T{LID.t=T.tipo} LID
![Page 51: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/51.jpg)
ET DiseñoET Diseño
2do Caso: Atributos heredados y sintetizados.◦ Una acción no debe referenciar a un atributo sintetizado de un
símbolo de la gramática que esté a la derecha de dicho símbolo.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 51
Producción Producción con Acciones
X0X1…Xj-1{Acción}Xj…Xn
Acción: no hace ref. a un atributo calculado a la derecha de Xj
![Page 52: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/52.jpg)
ET DiseñoET Diseño
2do Caso: Atributos heredados y sintetizados.◦ Acciones que calculen atributos sintetizados para el símbolo no
terminal de la parte izquierda de una producción deben ser ubicados al final de la parte derecha de la producción.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 52
Producción Regla Semántica
1) TE + T1 T.val= E.val + T1.val
2) NRO1 NRO2 DIG NRO1=NRO2.val * 10 + DIG.val
3) DIG0 DIG.val=0
![Page 53: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/53.jpg)
ET Técnica de ConstrucciónET Técnica de Construcción
Entrada: Un esquema de traducción dirigido por la sintaxis con la gramática subyacente LL(k) fuerte.
Salida: Código para un traductor dirigido por la sintaxis.
Método: La técnica propuesta es una modificación al método de construcción de parsers descentes recursivos vistos anteriormente.
A N, construir una función asociada pero teniendo un
parámetro formal para cada atributo heredado por A y que retorne los valores de los atributos sintetizados de A. El cuerpo de la función deberá contener una variable local para cada atributo de cada símbolo de la gramática que aparezca en las producciones de A.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 53
![Page 54: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/54.jpg)
ET Técnica de ConstrucciónET Técnica de Construcción
Como sucede con el método clásico el código para el no terminal A decide que producción usar basado en el lookahead.
El código asociado con cada producción hace lo siguiente, considerando
los tokens, los no teminales y acciones en la parte derecha de una producción de izquierda a derecha:
Para el token x con atributo sintetizado x.val se salva su valor en la
variable local declarada para x.val. Luego, se llama al match del símbolo y se obtiene el próximo token.
Para el no terminal B, se genera una asignación c:=B(b1,b2,...,bn)
donde b1,b2,...,bn son las variables para los atributos heredados de B y c es la variable para el atributo sintetizado de B.
Para una acción, copiar el código en el parser, reemplazando cada
referencia a un atributo por la variable local para tal atributo.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 54
![Page 55: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/55.jpg)
AplicacionesAplicacionesCompiladores 2008 - Traducción Dirigida por la Sintáxis 55
![Page 56: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/56.jpg)
Análisis EstáticoAnálisis Estático
Una aplicación científica o industrial se puede estudiar a partir de las componentes estáticas que utilizan, por ejemplo: Tipos de datos, Registros, Variables, Constantes, Funciones, etc.
Los temás vistos en esta clase se pueden utilizar para extraer esta información y dejarla disponible para que el usuario tenga rápido acceso a ella en el código fuente del programa.
En otras palabras se pueden usar las DDS o ET para extraer la información antes mencionada desde el código fuente.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 56
![Page 57: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/57.jpg)
Análisis EstáticoAnálisis Estático
Un visualizador de los elementos estáticos de un sistema.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 57
![Page 58: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/58.jpg)
Análisis DinámicoAnálisis Dinámico
La información estática es importante. No obstante conocer el comportamiento del programa puede ayudar a la tarea de simplificar la inspección del código.
El Análisis Dinámico se interesa por conocer cuales son las componentes del sistema bajo estudio utilizadas para llevar a cabo una funcionalidad específica.
Una de las formas de llevar a cabo esta tarea consiste en “Instrumentar el Código Fuente”. Esto significa: “Insertar sentencias dentro del código fuente del sistema que posibiliten la identificación de las componentes utilizadas”.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 58
![Page 59: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/59.jpg)
Análisis DinámicoAnálisis Dinámico
int f(int x, int y) int f(int x, int y){ { int r; int r; r=2*x + 3*y printf(“Entra: f”); return r; r=2*r+3*y;} printf(“Sale:f”);
}Int main() int main()
{ { f(2,3); printf(“ENTRA main”);} f(2,3);
printf(“SALE main”);}
La ejecución del sistema de la derecha informará que función ejecutó el sistema.Luego Ud. Puede almacenar esas trazas de ejecución para obtener conclusiones acerca del
funcionamiento del sistema.
Se anima Ud. a construir un DDS o un ET que logre este efecto para la gramática proporcionada por la materia?
Compiladores 2008 - Traducción Dirigida por la Sintáxis 59
![Page 60: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/60.jpg)
Vista de componentes recuperadas con Análisis Dinámico.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 60
![Page 61: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/61.jpg)
Visualización de SoftwareVisualización de Software
Una de las formas de estudiar sistemas es representar gráficamente algunas de sus características.
Para alcanzar este objetivo se necesita extraer información del código fuente y luego diseñar una vista de esa información.
Por ejemplo, una vista clásica es el grafo de funciones. Dicho grafo se define de la siguiente manera:◦ G=(P;E)
P{x/ x es una función del sistema} E={(x,y) / xP y P x llama a y}
Compiladores 2008 - Traducción Dirigida por la Sintáxis 61
![Page 62: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/62.jpg)
Visualización de SoftwareVisualización de Software
El grafo de funciones se puede extraer usando un ET.Un ejemplo de una visualización innovadora de esta
estructura es la siguiente
Compiladores 2008 - Traducción Dirigida por la Sintáxis 62
![Page 63: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/63.jpg)
Otra forma de presentar la relación llamador-llamado entre las funciones del sistema.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 63
![Page 64: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/64.jpg)
SistemasSistemas
Las DDS o ET de traducción se pueden utilizar para desarrollar software de aplicación.
Un ejemplo de esto será propocionado para su lectura.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 64
![Page 65: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/65.jpg)
Software IndustrialSoftware IndustrialCompiladores 2008 - Traducción Dirigida por la Sintáxis 65
1
3
4
2
A
B
C E
X2
X1
Y
1
0
![Page 66: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/66.jpg)
BibliografíaBibliografía
Compilers Principles, Techniques and Tools. Aho, Setti y Ullman.
Compiler Desing. Reinhard Wilhelm y Dieter Maurer.
Compiler Construction: Principles and Practice. Kenneth C. Louden.
Compiler Construction. Niklaus Wirth.
LISS, A linguagem eo ambiente de programação. Trabajo de fin de carrera en la UM.
Implementação do WebApp Viewer: Uma Ferramenta para compreender aplicações Web. Trabajo de fin de carrera en la UM.
Compiladores 2008 - Traducción Dirigida por la Sintáxis 66
![Page 67: Tds](https://reader031.vdocumento.com/reader031/viewer/2022020803/54b603e14a7959e6128b4581/html5/thumbnails/67.jpg)
Compiladores 2008 - Traducción Dirigida por la Sintáxis 67
Muchas Gracias por su atención! Diseño y Construcción de Compiladores
2008