compiladores primer cuatrimestre

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

INTRODUCCIÓN.................................................................................................... 1
1.1

Estructura de un compilador.......................................................................... 2

1.2

Ejemplo de las fases de un compilador. ......................................................... 3

LENGUAJES Y GRAMÁTICAS. ............................................................................ 52.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 deConway..................................................................................... 9

2.5

Reglas BNF. .................................................................................................... 10

2.6

Problemas en las GCL. .................................................................................. 11

2.6.1
2.6.2
2.6.3

2.7
2.7.1
2.7.2
2.7.3
2.7.4

3

Recursividad.........................................................................................................................11
Reglas con factor repetido por la izquierda. .........................................................................13
Ambigüedad. ........................................................................................................................13

Simplificación de gramáticas........................................................................ 14
Detección de un lenguaje vacío. ...........................................................................................14
Eliminación de reglas lambda ().........................................................................................14
Eliminación de reglas unitarias o reglas cadena...................................................................16
Eliminación de símbolos inútiles..........................................................................................17

2.8

Gramática limpia. .......................................................................................... 19

2.9

Forma normal de Chomsky (FNC). ............................................................. 19

2.10

Resumen...................................................................................................... 20

2.11

Ejercicios..................................................................................................... 21

ANÁLISIS LÉXICO............................................................................................... 22
3.1

Tipos de máquinas reconocedoras oautó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 deThompson................................................................................ 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
3.8.2

3.9

Tabla...