Algoritmos

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 DafonteDepartamento 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 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

2.7 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

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

2.10 Resumen. ..................................................................................................... 20

2.11 Ejercicios..................................................................................................... 21

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...