licenciatura informatica

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

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

2

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

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 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.4Recursividad. ........................................................................................................................11
Reglas con factor repetido por la izquierda. .........................................................................13
Ambigüedad. ........................................................................................................................13Simplificació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 reglascadena. ..................................................................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
2.11
3

Resumen. ..................................................................................................... 20
Ejercicios..................................................................................................... 21

ANÁLISIS LÉXICO............................................................................................... 223.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...