Notas de compiladores

Notas para la Materia de Compiladores
Jos´ Antonio Camarena Ibarrola e Marzo de 2008

2

´ Indice general
1. Introducci´n o 1.1. Objetivo . . . . . . . . . . . . . . 1.2. Justificaci´n . . . . . . . . . . . . o 1.3. Usuarios . . . . . . . . . . . . . . 1.4. Definiciones . . . . . . . . . . . . 1.5. El An´lisis L´xico . . . . . . . . . a e 1.6. El An´lisis Sint´ctico . . . . . . . a a 1.7.El An´lisis Sem´ntico . . . . . . . a a 1.8. Generador de C´digo Intermedio o 1.9. El Optimizador de C´digo . . . . o 1.10. La Tabla de S´ ımbolos . . . . . . . 1.11. Manejo de Errores . . . . . . . . 5 . 6 . 6 . 6 . 7 . 8 . 9 . 9 . 9 . 10 . 10 . 10

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

2. An´lisis L´xico a e 11 2.1. Construcci´n de Analizadores L´xicos . . . . . . . . . . . . . . 11 o e 2.2. El Generador de Analizadores lexicos: lex . . . . . . . . . .. . 13 3. An´lisis Sint´ctico a a 3.1. An´lisis Sint´ctico Descendente . . . . . . . . . . . . . . . . a a 3.1.1. Parser descendente recursivo . . . . . . . . . . . . . . 3.1.2. Parser predictivo descendente para gram´ticas LL(1) a 3.2. An´lisis Sint´ctico Ascendente . . . . . . . . . . . . . . . . . a a 3.2.1. Parsers LR . . . . . . . . . . . . . . . . . . . . . . . 3.3. El generador deanalizadores sint´cticos: yacc . . . . . . . . a . . . . . . 17 17 18 19 32 33 41

3

4

´ INDICE GENERAL

Cap´ ıtulo 1 Introducci´n o
Escribir un compilador es normalmente el primer gran Sistema de Software que un estudiante de Ingenier´ en Computaci´n desarrolla y requiere ıa o conocimientos de las siguientes ´reas: a Programaci´n de Computadoras o Arquitectura de Computadoras Teor´ deAut´matas y Lenguajes Formales ıa o Ingenier´ de Software ıa Programaci´n de Sistemas o El estudiante requiere entonces toda la ayuda posible. Estas Notas fueron escritas con el ´nimo de facilitar la compresi´n de las t´cnicas que se utilizan a o e para desarrollar las partes de un compilador que son el analizador lexicogr´fia co, el analizador sint´tico, el generador de c´digo intermedio y eloptimizador a o de c´digo. Hasta el momento, estas notas se centran en los dos primeros o m´dulos pero incluyen una introducci´n a las valiosas herramientas conocio o das como lex y yacc (o sus clones conocidos como flex y bison), este ultimo ´ no solo es util en el an´lisis sint´ctico sino en la generaci´n de c´digo. ´ a a o o

5

6

´ CAP´ ITULO 1. INTRODUCCION

1.1.

Objetivo

Proveer alalumno con principios y t´cnicas utiles para la construcci´n e ´ o de Compiladores. El alumno deber´ ser capaz de implementar la traducci´n a o de un lenguaje de programaci´n de alto nivel al lenguaje de m´quina de un o a computador.

1.2.

Justificaci´n o

El estudiante debe aprender como implementar compiladores utilizando la tecnolog´ actual, estas notas deber´n serle de gran ayuda. ıa a1.3.

Usuarios

Estudiantes de Ingenier´ en COmputaci´n de la Facultad de Ingenier´ ıa o ıa El´ctrica e

1.4. DEFINICIONES

7

1.4.

Definiciones

Un compilador es un TRADUCTOR de un lenguaje de programaci´n de o alto nivel a un lenguaje ensamblador el cual ser´ traducido a su vez a c´digo a o objeto por alg´n ensamblador [1], [2], [3]. El conjunto de compiladores es u unsubconjunto del producto cartesiano del conjunto de Lenguajes de alto nivel, el conjunto de computadoras y el conjunto de sistemas operativos. Por Ejemplo el compilador de C++ para McCintosh en ambiente Linux se podr´ ıa representar por: (C++,MAC,Linux) Otros ejemplos podr´ ser: ıan (Modula2,PC,DOS), (Pascal,Risc,Unix), (Java,Sun,OS/2), Etc.... Para colmo, se generan versiones nuevas frecuentemente de...