Procesadores de lenguajeTema 4 Anlisis semntico
Salvador Snchez, Daniel RodrguezDepartamento de Ciencias de la ComputacinUniversidad de Alcal
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Resumen
Introduccin Gramticas de atributos.
Gramticas S-atribuidas. Gramticas L-atribuidas.
Esquemas de traduccin dirigidos por sintaxis. Grafo de dependencias. Evaluacin de atributos.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Introduccin
El lenguaje es un vehculo por el cual se transmiten instrucciones a un procesador para que las ejecute y produzca ciertos resultados.
Es tarea del compilador extraer el contenido semntico incluido en las sentencias del programa.
Ciertos aspectos relativos a la correccin de un programa no se pueden expresar claramente mediante el lenguaje de programacin.
Es necesario dotar al compilador de rutinas auxiliares para captar todo lo que no se ha expresado mediante la sintaxis del lenguaje
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Introduccin
Semntica: conjunto de reglas que especifican el significado de cualquier sentencia sintcticamentecorrecta y escrita en un determinado lenguaje.
El anlisis semntico, a diferencia de otras fases, no se realiza claramente diferenciado del resto de las tareas del compilador.
Fase en la que se obtiene informacin necesaria para la compilacin tras conocer la estructura sintctica del programa.
Completa las fases de anlisis lxico y sintctico incorporando comprobaciones que no pueden asimilarse al mero reconocimiento de una cadena dentro de un lenguaje
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Introduccin
Errores semnticos de un programa: Conversiones de tipos no permitidas
int x;x = 4.32;Error: Ej1.java [6:1] possible loss of precision
Variables usadas y no definidas Operandos de tipos no compatibles
if (x || 5) x = 0;Error: Ej2.java [7:1] operator || cannot be applied to int,int
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Funciones del anlisis semntico
Las principales funciones son: Identificar cada tipo de instruccin y sus componentes. Completar la Tabla de Smbolos. Realizar comprobaciones estticas:
Se realizan durante la compilacin del programa. Ejemplos: comp. de tipos, unicidad de etiquetas e identificadores,
etc. Realizar comprobaciones dinmicas:
Aquellas que el compilador incorpora al programa traducido. Hacen referencia a aspectos que slo pueden ser conocidos en
tiempo de ejecucin Dependientes del estado de la mquina en la ejecucin o del
propio programa. Validar las declaraciones de identificadores: en muchos lenguajes no se
puede usar una variable si no ha sido declarada con anterioridad.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Introduccin
El anlisis semntico se divide en dos categoras: Anlisis de la exactitud del programa para garantizar una ejecucin
adecuada. Algunos lenguajes (Lisp, Smalltallk) pueden no tener anlisis
esttico. Por ejemplo, ADA es un lenguaje con fuertes restricciones para
que un programa sea ejecutable. Anlisis para mejorar la eficiencia (optimizacin del programa traducido)
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Especificacin de la semntica
No hay una notacin estndar para especificar la semntica esttica de un lenguaje
El anlisis semntico vara mucho de unos lenguajes a otros
Las especificaciones semnticas de un lenguaje pueden hacerse de manera informal o formal:
Especificacin natural: basada en el lenguaje natural. Por ejemplo:
Los identificadores deben definirse antes de utilizarse Los operandos deben ser compatibles entre s
Especificacin formal: definicin ms precisa. Lenguajes formales: Z, B, VDM, etc. Gramticas de atributos (Knuth, 1968)
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Una gramtica de atributos es una gramtica libre de contexto cuyos smbolos pueden tener asociados atributos y las producciones pueden tener asociadas reglas de evaluacin de los atributos.
En la creacin de compiladores se utilizan ecuaciones de atributos o reglas semnticas como mtodo para expresar la relacin entre el clculo de los atributos y las reglas del lenguaje.
Cada produccin (regla sintctica) tiene asociada una accin semntica que se aplica cuando se realiza una reduccin en el anlisis sintctico ascendente.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Traduccin dirigida por la sintaxis:
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Dos notaciones para asociar reglas semnticas con producciones:
Definiciones dirigidas por la sintaxis (DDS) : Son especificaciones de alto nivel El usuario no necesita especificar el orden de la traduccin
Esquemas de traduccin (EDT) : Indican el orden en que deben evaluarse las reglas semnticas Incluyen detalles de implementacin
Con ambas notaciones se analizan los componentes lxicos, se construye el rbol sintctico y finalmente se recorre el rbol para evaluar las reglas semnticas de sus nodos.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Atributo: propiedad de una construccin de un lenguaje. Pueden variar mucho en cuanto a informacin que contienen o tiempo
que tardan en determinarse durante la traduccin/ejecucin. Cada smbolo (terminal o no terminal) puede tener asociado un nmero
finito de atributos.
Ejemplos de atributos: Tipo de una variable Valor de una expresin Ubicacin en memoria de una variable Cdigo objeto de un procedimiento Nmero de dgitos significativos en un nmero
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Fijacin de un atributo: proceso de calcular el valor de un atributo y asociarlo con una construccin del lenguaje.
Tipos de Atributo por su fijacin: Esttico: puede fijarse antes de la ejecucin del programa
Ej.: nmero de dgitos significativos (puede tener un valor mnimo) Dinmico: slo puede fijarse durante la ejecucin del programa
Ej.: valor de una expresin no constante
Los valores de los atributos deben estar asociados con un dominio de valores.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Generalmente se denotan mediante un nombre precedido por un punto y el nombre del smbolo al que estn asociados.
NombreSmbolo.NombreAtributo Ejemplo:
numero numero digito | digito
a) numero digitonumero.valor = digito.valor
b) numero numero digitonumero1.valor = numero2.valor * 10 + digito.valor
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Otra notacin hace referencia a su posicin en la regla de produccin:
Se utiliza el smbolo $. $$ representa el no terminal en la parte izquierda de la produccin Los smbolos de la parte derecha de la produccin se identifican
consecutivamente: $1, $2, $3, ..., $n.
Ejemplo:numero numero digito | digitoa) numero digito
$$.valor = $1.valorb) numero numero digito
$$.valor = $1.valor * 10 + $2.valor
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Ejemplo:
Exp Exp op_arit Exp { si ($1.tipo == $3.tipo) entonces
$$.tipo = $1.tiposi no
$$.tipo = ERROR Escribir(error tipos incompatibles)
fin_si}
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
::= { .Tipo = Mayor_tipo(.Tipo,.Tipo).Tipo = .Tipoif (.Tipo == F && .Tipo == I){
.Tipo = F;.Valor = Float(.Valor);
}if (.Tipo == F && .Tipo == I){
.Tipo = F;.Valor = Float(.Valor);
}switch (.Tipo){I: .Valor = Op_entera(.Clase,
.Valor, .Valor); break;F: .Valor = Op_real(.Clase,
.Valor, .Valor); break;}
}
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Las gramticas de atributos se escriben en forma de tabla:
Las reglas gramaticales, a la izquierda Las reglas semnticas asociadas, a la derecha
Ecuaciones de atributo asociadas
Regla n
Ecuaciones de atributo asociadas
Regla 1
Regla semnticaRegla gramatical
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas de atributos
Ejemplo
E.val = T.valE TE0.val = E1.val + T.valE E + Tprint(E.val)L E n
F.val = E.valF (E)T.val = F.valT FT0.val = T1.val * F.valT T * F
F.val = digito.valor_lexicoF digito
Regla semnticaRegla gramatical
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Definiciones dirigidas por la sintaxis
Cada smbolo gramatical tiene asociado un conjunto de atributos.
El valor de un atributo en un rbol sintctico se calcula mediante una regla semntica asociada a la produccin utilizada en el nodo.
Tipos de atributos:
Sintetizados: Su valor se calcula en funcin de atributos de nodos hijos en el rbol de anlisis sintctico.
A aB { A.atributo = a.atributo + B.atributo }
Heredados: Para un hijo se calculan a travs de los atributos del padre y hermanos en el rbol de anlisis sintctico.
A aB { B.atributo = a.atributo A.atributo }
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Definiciones dirigidas por la sintaxis
Las reglas semnticas establecen las dependencias entre los atributos
Estas dependencias se representan en un grafo.
Del grafo de dependencias se obtiene el orden de evaluacin de las reglas semnticas.
rbol sintctico con anotaciones: rbol sintctico que muestra informacin en cada nodo sobre los atributos.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Definiciones dirigidas por la sintaxis
Forma de una definicin dirigida por la sintaxis: Cada produccin A tiene una o ms reglas semnticas asociadas Cada regla tiene la forma b = f(c1,c2,..,cn) b, que depende de c1,c2,...,cn , puede ser:
Un atributo sintetizado de A. Un atributo heredado de uno de los smbolos del lado derecho de
la produccin. Las funciones f de las reglas se escriben como expresiones.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Definiciones S-atribuidas
Gramtica S-atribuida: todos los atributos asociados con los smbolos gramaticales son sintetizados.
Las reglas de evaluacin de los atributos sintetizados se realizan cuando se aplican reducciones en el anlisis sintctico.
Las reglas de evaluacin de los atributos deben definirse en funcin de los atributos asociados con los smbolos gramaticales hijos.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos sintetizados
Los valores de los atributos S se pueden calcular fcilmente mediante un recorrido ascendente (post-orden) del rbol sintctico:
procedimiento EvaluarSintetizado(A:arbolSintactico){Para cada hijo H de A hacer
EvaluarSintetizado(H);Calcular atributos sintetizados de A
}
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas S-atribuidas
Ejemplo de gramtica S-Atribuida: Calculadora aritmtica sencilla. Se desea evaluar expresiones a la
vez que las analizamos. Sea el conjunto de producciones y acciones siguientes:
L E n { print (E1.val) } (* n = salto lnea *)E E + T { E0.val = E1.val + T3.val }E T { E0.val = T1.val }T T * F { T0.val = T1.val * F3.val }T F { T0.val = F1.val }F (E) { F0.val = E2.val }F digito { F0.val = digito }
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas S-atribuidas
Evaluacin de la expresin 3 * 5 + 4
Resultado: se imprime el resultado de calcular 3 * 5 + 4.
L E nE E + T | T T T * F | F F (E) | digito
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas L-atribuidas
Gramtica L-atribuida: todos los atributos asociados con los smbolos gramaticales son sintetizados o heredados pero cumpliendo que su evaluacin dependa de los atributos asociados con los smbolos precedentes en la derivacin:
Heredan del nodo padre Ej: AXYZ { Y.valor = A.valor }
Heredan de hermanos a su izquierda Ej: AXYZ { Y.valor = X.valor }
Heredan de otros atributos del mismo smbolo Ej: AXYZ { Y.valor = float(Y.int_value)*2 }
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas L-atribuidas
Los atributos heredados permiten expresar la dependencia de una construccin del lenguaje con respecto al contexto en que aparece.
Ejemplos: Saber si un identificador est en la parte izquierda (direccin) o
derecha (valor) de una expresin. Conocer la posicin de un argumento de funcin f(x,y,z) Qu
posicin ocupa dentro de la lista de argumentos el argumento y?
Para su evaluacin el anlisis ptimo es el descendente.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos heredados
Los valores de los atributos heredados se pueden calcular mediante un recorrido descendente (pre-orden) del rbol sintctico:
procedimiento EvaluarHeredado(A:arbolSintactico){Para cada hijo H de A hacer{
Calcular atributos heredados de HEvaluarHeredado(H);
}}
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos heredados
Ejemplo:
D T L { L.her = T.tipo; }T int { T.tipo = entero; }T real { T.tipo = real; }L L , id { L1.her = L0.her; aadetipo(id,L0.her); }L id { aadetipo(id, L.her); }
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Gramticas L-atribuidas
Evaluar la expresin: real id1,id2,id3
D T L T intT real L L , idL id
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Esquemas de traduccin
Esquema de Traduccin: gramtica con atributos cuyas acciones semnticas se expresan entre llaves.
Notacin complementaria donde las acciones se encuentran o bien intercaladas entre los smbolos de la parte derecha de las producciones, o bien al final de las mismas.
Insercin de acciones semnticas al final de cada produccin.
S ::= B1 B2 { B1.atr = 1; B2.atr = 2; }B ::= x { print(B.atr); }
Acciones semnticas intercaladas
Proced ::= procedure {CrearAmbito();} id Args Decl Sentencias;
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Grafo de dependencias
Grafo de Dependencias: para calcular el valor de un atributo es necesario calcular en primer lugar los valores de los atributos de los que depende, estableciendo una dependencia entre atributos.
Cuando aparecen definidos atributos sintetizados y heredados, esnecesario establecer un orden de evaluacin.
Orden de evaluacin: Para cualquier accin semntica de la forma:
X.atr = f(Y1.atr, ..., Yn.atr)
Los valores de los atributos Y1.atr, ..., Yn.atr deben estar disponibles antes de ejecutarla.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Grafo de dependencias
El grafo de dependencias es un grafo dirigido acclico: Un nodo para cada atributo Un arco b c si el atributo c depende del atributo b
Se construye con el siguiente algoritmo:
Nodos: Para cada nodo n del rbol sintctico, hacer: Para cada atributo a asociado al smbolo gramatical del nodo n, construir
un nodo etiquetado con a en el grafo de dependencias.
Arcos: Para cada nodo n del rbol sintctico, hacer: Para cada regla semntica b = f (c1, c2, ..., cn) asociada con la produccin
del nodo n, trazar arcos desde cada ci hasta b.
Los atributos sintetizados se representan marcando el nodo as:
El rbol sintctico se representa en paralelo mediante lneas punteadas.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Grafo de dependencias
E E + E { E0.val = E1.val + E2.val }
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Grafo de dependenciasD T L { L2.her = T1.tipo; }T int { T0.tipo = entero; }T real { T0.tipo = real; }L L , id { L1.her = L0.her; aadetipo(id, L0.her);}L id { aadetipo(id, L0.her); }
Entrada:real id1,id2,id3;
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Orden de evaluacin
Clasificacin topolgica: orden de evaluacin de las reglas semnticas asociadas a cada nodo del rbol de anlisis sintctico.
Se etiqueta cada nodo con un nmero Los atributos independientes se evalan antes que los dependientes El grafo de dependencias debe ser acclico
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Orden de evaluacin
Una clasificacin topolgica se utiliza para generar un programa con el conjunto de reglas de evaluacin ordenadas:
a4 = real;a5 = a4;aadetipo (id3.entrada,a5);a7 = a5;aadetipo (id2.entrada,a7);a9 = a7;aadetipo (id1.entrada,a9);
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Orden de evaluacin
Al mtodo anterior se le conoce como Mtodo de rbol de anlisis gramatical.
Inconvenientes: La complejidad aadida que la construccin del grafo de dependencias supone para la
compilacin (se realiza en tiempo de compilacin). El mtodo debe determinar si el grafo es acclico (en tiempo de construccin).
Alternativa: Mtodo basado en reglas. El escritor del compilador analiza la gramtica y fija un orden de evaluacin de atributos (en
tiempo de construccin del compilador). Basado en reglas: analiza las reglas semnticas y depende de ellas. Slo puede hacerse para gramticas completamente no circulares. Prcticamente todos los compiladores lo utilizan.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin ascendente
Los principales mtodos de anlisis sintctico procesan la entrada de izquierda a derecha, lo que implica que los atributos no pueden tener dependencias hacia atrs.
Este problema se plantea slo para atributos heredados.
Los analizadores ascendentes (LR) son ms adecuados para manejar atributos sintetizados.
Reducen cuando se conoce toda la parte derecha de una produccin.
Es posible implementar traductores ascendentes para atributos heredados utilizando tcnicas avanzadas.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin ascendente
La estructura de la pila se adecua para que cada smbolo de la gramtica disponga de sus atributos asociados.
La evaluacin de los atributos se realiza justo antes de cada reduccin.
El analizador LR contiene una pila de valores adicional para almacenar los valores de los atributos sintetizados.
Si hay ms de un atributo para un smbolo, se almacenan como estructuras.
El Analizador es similar, pero ahora utiliza producciones compuestas por smbolos ms acciones semnticas:
Al aplicar una reduccin se realizan los clculos indicados en las acciones semnticas, utilizando generalmente los elementos de la pila de valores.
Un desplazamiento consiste en la insercin de valores de token tanto en la pila de valores como en la pila de anlisis sintctico.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos
Si una produccin maneja un nico atributo val, la pila contiene tanto los estados como los valores del atributo para los smbolos que ya han sido procesados (desplazados o reducidos anteriormente).
Si un smbolo no tiene atributo val la entrada correspondiente en la tabla est sin definir.
Acciones sobre la pila de valores:
Obtener un valor: Pila.pop(valor) Descartar un valor: Pila.pop() Insertar un valor: Pila.push(valor)
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos
Ejemplo:
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos
Es posible calcular con este mtodo (LR) atributos heredados de hermanos previamente calculados.
Es necesario introducir una produccin adicional.
El valor del atributo se almacena en una variable auxiliar y se calcula en funcin del valor en la cima de la pila antes del reconocimiento de C.
En Yacc/CUP:
A : B { aux = 2 * B.atr } C
{ Calcular B.atr; }B
{ C.her = 2 * B.atr }A BC
{/* utilizar C.her */}C
Regla semnticaRegla gramatical
{ aux = Pila.Cima() }X
{ Calcular B.atr; }B
{ C.her = 2 * aux }A BXC
{/* C.her disponible */}C
Regla semnticaRegla gramatical
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Evaluacin de atributos
El clculo de los atributos depende de la estructura de la gramtica.
Es posible simplificar el clculo mediante una modificacin de las reglas gramaticales.
Teorema de Knuth: Dada una gramtica con atributos, todos los atributos heredados se pueden convertir en sintetizados modificando adecuadamente la gramtica, sin cambiar el lenguaje.
En la prctica no se utiliza demasiado, pues puede generar gramticas y reglas semnticas ms complejas que las originales.
Procesadores de lenguaje Tema 4: Anlisis semnticoSalvador Snchez, Daniel Rodrguez
Bibliografa
Bsica:
Compiladores: principios, tcnicas y herramientas. A.V. Aho, R. Sethi, J.D. Ullman. Addison-Wesley Iberoamerica. 1990.
Construccin de compiladores. Principios y prctica. Kenneth C. Louden. Thomson-Paraninfo. 2004.
Recommended