PDF de programación - Compiladores

Compiladores

Ingeniería Informática, 4º curso

Segundo cuatrimestre:

 Análisis semántico
 Generación de código
 Representación de la información: gestión de la memoria
 Estudio de algunos compiladores



Profesores: Bernardino Arcay



Carlos Dafonte
Departamento de Tecnoloxías da Información e as Comunicacións.
Universidade da Coruña

ÍNDICE

5 ANÁLISIS SEMÁNTICO. ....................................................................................... 1
5.1 Definiciones dirigidas por la sintáxis. ............................................................ 1
5.1.1 Grafos de dependencias..........................................................................................................3
5.2 Esquema de traducción ................................................................................... 4
5.3 Comprobaciones en tiempo de compilación. ................................................. 5
5.3.1 Sistemas de tipos. ...................................................................................................................6
5.3.2 Una gramática y sus comprobaciones de tipos. ......................................................................6
5.3.3 Equivalencia de expresiones de tipos. ....................................................................................8
5.3.4 Codificación de tipos..............................................................................................................8
5.3.5 Conversión de tipos. ...............................................................................................................9
5.3.6 Sobrecarga de funciones y operadores..................................................................................10
6 GENERACIÓN DE CÓDIGO. .............................................................................. 13
6.1 Lenguajes intermedios................................................................................... 13
6.1.1 Notación Polaca Inversa (RPN)............................................................................................13
6.1.2 Cuartetos...............................................................................................................................13
6.1.3 Tercetos. ...............................................................................................................................15
6.2 Generación de código intermedio................................................................. 16
6.2.1 Generación de RPN desde expresiones aritméticas. .............................................................16
6.2.2 Generación de cuartetos........................................................................................................17
6.3 Generación de código desde lenguaje intermedio....................................... 18
6.3.1 Definición de la máquina objeto...........................................................................................18
6.3.2 Generación de código desde RPN. .......................................................................................19
6.3.3 Generación de código desde cuartetos..................................................................................20
7 OPTIMIZACIÓN DE CÓDIGO............................................................................ 22
7.1 Algoritmo de Nakata. .................................................................................... 24
7.2 Un ejemplo de optimización manual............................................................ 28
7.3 Lazos en los grafos de flujo. .......................................................................... 28
7.4 Análisis global del flujo de datos. ................................................................. 29
7.4.1 Alcance de definiciones en estructuras de control................................................................31
7.4.2 Notación vectorial para representar genera y desactiva........................................................34
Solución iterativa de las ecuaciones de flujo de datos. ............................... 37
7.5.1 Análisis alcance de definiciones...........................................................................................37
7.5.2 Análisis de expresiones disponibles. ....................................................................................40
7.5.3 Análisis de variables activas.................................................................................................43
8 ERRORES. ............................................................................................................. 46
8.1 Tipos de errores. ............................................................................................ 46
8.2 Recuperación de errores léxico-gráficos...................................................... 47
8.2.1 Corrección de errores de sustitución.....................................................................................47
8.2.2 Corrección de errores de borrado. ........................................................................................49
8.2.3 Corrección de errores de inclusión. ......................................................................................49
8.3 Análisis sintáctico en “modo pánico”........................................................... 50
INTÉRPRETES. .................................................................................................... 51
9.1 Estructura de un intérprete actual............................................................... 51
9.2 Arquitectura “neutral” de Java.................................................................... 53

7.5

9



ii

BIBLIOGRAFÍA.


Aho, A.V.; Sethi, R. ; Ullman, J.D.
"Compiladores: Principios, técnicas y herramientas"
Addison-Wesley, Reading, Massachussetts (1991).

Louden D. K. [2004], Construcción de compiladores. Principios y Práctica,
Paraninfo Thomson Learning.

Garrido, A. ; Iñesta J.M. ; Moreno F. ; Pérez J.A. [2004] Diseño de
compiladores, Publicaciones Universidad de Alicante.

Sanchis, F.J.; Galán, J.A.
"Compiladores, teoría y construcción"
Ed. Paraninfo (1987).

Aho, A.V.; Ullman, J.D.
"The theory of parsing, translation and compiling", I y II
Prentice-Hall (1972).

Aho, A.V.; Ullman J.D.
"Principles of compiler design"
Addison-Wesley, Reading, Massachussetts.

Hopcroff, J.E. ; Motwani R. ; Ullman, J. D. [2002] Introducción a la teoría de
autómatas, lenguajes y computación, Addison-Wesley, Madrid.

Allen I.; Holub
"Compiler design in C"
Prentice-Hall (1991).

Sánchez, G.; Valverde J.A.
"Compiladores e Intérpretes"
Ed. Díaz de Santos (1984).

Sudkamp T.A.
“Languages and machines”
Addison-Wesley.

iii



5 ANÁLISIS SEMÁNTICO.


En esta fase se pretende encontrar errores semánticos; en este capítulo nos
centraremos principalmente en la recopilación de información sobre los tipos
para posteriormente realizar la generación de código.

Para la realización del análisis semántico se emplea la estructura jerárquica
definida durante el análisis sintáctico para reconocer los operadores,
operandos de expresiones y proposiciones.

Dentro del análisis semántico, una de las funciones principales es la de
verificar si los operadores tienen los operandos del tipo correcto según el
lenguaje. Por ejemplo, puede significar un error sumar un número real y un
número entero en un lenguaje, sin embargo, en otro, es correcto pero se
precisa realizar una conversión.

Las acciones semánticas nos van a permitir asociar información a las
producciones gramaticales, de forma que incorporamos reglas semánticas e
introducimos atributos a los símbolos de la gramática.

Para trabajar con reglas o acciones semánticas se utilizan dos notaciones:

1) Definiciones dirigidas por la sintáxis.
2) Esquemas de traducción.

En general, el metodo consistirá en construir el árbol sintáctico, crear el grafo
de dependencias y evaluar las reglas semánticas. Los pasos serían:


CADENA  ÁRBOL  GRAFO DE DEPEN.  EVALUACIÓN REGLAS SEMÁNTICAS



5.1 Definiciones dirigidas por la sintáxis.

Una definición dirigida por la sintáxis es una generalización de una gramática
independiente del contexto en la que cada símbolo gramatical tiene un
conjunto de atributos asociados (pueden ser sintetizados o heredados).

Forma de una definición dirigida por la sintáxis.

Sea una GIC, G = (N, T, P, S), cada producción A   tiene asociado un
conjunto de reglas semánticas de la forma b = f(c1, c2, ..., ck), donde f es una
función, c1, c2, ..., ck son atributos de los símbolos gramaticales de la
producción y b puede ser:
a) Un atributo sintetizado de A (a partir de atributos de la parte derecha).

1

b) Un atributo heredado de uno de los símbolos gramaticales que está en el
lado derecho de la producción (calculado a partir de atributos de la parte
izquierda y/o de sus hermanos en la parte derecha).


Se dice que un atributo es sintetizado si su valor en un nodo del árbol de
análisis sintáctico se determina a partir de los valores de los atributos de los
hijos del nodo.

Se dice que un atributo es heredado si su valor en un nodo de un árbol de
análisis sintáctico está definido a partir de los atributos en el padre y/o de los
hermanos de dicho nodo.

Una definición dirigida por la sintáxis que usa exclusivamente atributos
sintetizados se llama definición con atributos sintetizados.

Ejemplo.- Definición con atributos sintetizados.


L  E \n
E  E1 + T
E  T
T  T1 * F
F  (E)
F  dígito
T  F

Print (E.val)
E.val = E1.val + T.val
E.val = T.val
T.val = T1.val x F.val
F.val = E.val
F.val = dígito