PDF de programación - Compiladores

Compiladores

Ingeniería Informática, 4º curso
Master en Informática, 1er curso



Primer cuatrimestre:

 Introducción
 Lenguajes y gramáticas
 Análisis Léxico
 Análisis Sintáctico



Profesores: Bernardino Arcay



Carlos Dafonte
Departamento de Tecnoloxías da Información e as Comunicacións.
Universidade da Coruña
Curso 2009/2010 Rev.061009




ÍNDICE



1

2.7

INTRODUCCIÓN.................................................................................................... 1
1.1 Estructura de un compilador.......................................................................... 2
1.2 Ejemplo de las fases de un compilador. ......................................................... 3
2 LENGUAJES Y GRAMÁTICAS. ............................................................................ 5
2.1 Notación de Chomsky (1959). ......................................................................... 6
2.2 Clasificación de Chomsky. .............................................................................. 7
2.3 Gramáticas de contexto libre (GCL).............................................................. 8
2.4 Diagramas de Conway..................................................................................... 9
2.5 Reglas BNF. .................................................................................................... 10
2.6
Problemas en las GCL................................................................................... 11
2.6.1 Recursividad.........................................................................................................................11
2.6.2 Reglas con factor repetido por la izquierda. .........................................................................13
2.6.3 Ambigüedad. ........................................................................................................................13
Simplificación de gramáticas. ....................................................................... 14
2.7.1 Detección de un lenguaje vacío. ...........................................................................................14
2.7.2 Eliminación de reglas lambda ().........................................................................................14
2.7.3 Eliminación de reglas unitarias o reglas cadena. ..................................................................16
2.7.4 Eliminación de símbolos inútiles..........................................................................................17
2.8 Gramática limpia. .......................................................................................... 19
Forma normal de Chomsky (FNC). ............................................................. 19
2.9
2.10
Resumen...................................................................................................... 20
Ejercicios..................................................................................................... 21
2.11
3 ANÁLISIS LÉXICO............................................................................................... 22
3.1 Tipos de máquinas reconocedoras o autómatas.......................................... 23
3.2 Autómatas Finitos.......................................................................................... 23
3.3 Conversión de una Gramática Regular en un Autómata finito................. 25
3.4 Expresión regular. ......................................................................................... 26
3.5 Algoritmo de Thompson................................................................................ 27
3.6 Transformación de un AFND- en un AFD................................................ 28
3.7 Traductores finitos (TF)................................................................................ 30
3.8
Implementación de autómatas...................................................................... 31
3.8.1 Tabla compacta.....................................................................................................................31
3.8.2 Autómata programado. .........................................................................................................33
3.9 Ejemplo. Scanner para números reales sin signo en Pascal....................... 33
Acciones semánticas................................................................................... 36
3.10
3.11
Generador LEX.......................................................................................... 37



ii

3.11.1
3.11.2
3.11.3
3.11.4

Partes de un programa LEX .............................................................................................37
Expresiones regulares.......................................................................................................38
Paso de valores en Lex.....................................................................................................39
Ejemplos...........................................................................................................................39
4 Análisis sintáctico (Parsing). ................................................................................. 43
4.1 Máquinas teóricas, mecanismos con retroceso............................................ 46
4.1.1 Autómatas con pila (AP). .....................................................................................................46
4.1.2 Esquemas de traducción (EDT)............................................................................................50
4.1.3 Traductores con pila (TP).....................................................................................................52
4.2 Algoritmos sin retroceso................................................................................ 53
4.2.1 Análisis sintáctico ascendente por precedencia simple.........................................................54
4.2.2 Análisis sintáctico ascendente por precedencia de operadores.............................................64
4.2.3 Analizadores descendentes LL(K)........................................................................................67
4.2.4 Analizadores ascendentes LR(k). .........................................................................................73
4.2.5 Generador de analizadores sintácticos YACC......................................................................89



iii

BIBLIOGRAFÍA.

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

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.

iv


1

INTRODUCCIÓN.

Un lenguaje es un conjunto de oraciones finito o infinito, cada una de ellas de
longitud finita (es decir, constituídas cada una de ellas por un número finito
de elementos).

Compilación: Proceso de traducción en el que se convierte un programa
fuente (en un lenguaje de alto nivel) en un lenguaje objeto, generalmente
código máquina (en general un lenguaje de bajo nivel).

La Teoría de compiladores se usa para:

 Realizar compiladores.
 Diseñar procesadores de texto.
 Manejo de datos estructurados (XML).

 Traductores de lenguajes naturales.
 Etc.

Inteligencia Artificial (en el diseño de interfaces hombre-máquina).


Se denominan tokens a los lexemas, las unidades mínimas de información
(por ejemplo, una instrucción FOR). La identificación de estos elementos es la
finalidad del análisis léxico.

Sintaxis de un lenguaje: Conjunto de reglas formales que nos permiten
construir las oraciones del lenguaje a partir de los elementos mínimos.

Semántica: Es el conjunto de reglas que nos permiten analizar el significado
de las frases del lenguaje para su interpretación.

Intérprete: Conjunto de programas que realizan la traducción de lenguaje
fuente a objeto, “paso a paso”, no de todo el programa (aparecieron por
problemas de memoria).

Ensamblador: Compilador sencillo donde el lenguaje es simple, con una
relación uno-a-uno entre la sentencia y la instrucción máquina.

Compilación cruzada: La compilación se realiza en una máquina A y la
ejecución se realiza en otra máquina B.

Link (encadenar, enlazar): Es el proceso por el cual un programa dividido en
varios módulos, compilados por separado, se unen en un solo.

Pasadas en compilación: Recorridos de todo el programa fuente que realiza
el compilador. Cuantas más pasadas, el proceso de compilación es más
completo, aunque más lento.

Traductor o compilador incremental, interactivo o conversacional: Es un
tipo de compilador que, al detectar un error, intenta compilar el código del
entorno en donde está el error, no todo el programa de nuevo.

1



El programa fuente es el conjunto de oraciones escritas en el lenguaje
fuente, y que normalmente estará en un fichero.

Bootstraping: