Notas compiladores

Índice
1. Introducción ................................................................................................................................ 7
1.1 Tipos de traductores ......................................................................................................... 7
1.2 Autómatas........................................................................................................................... 10
1.2.1 Autómatas finitos (FA – finite automata) .................................................................... 10
1.2.1.1 Autómatas finitos deterministas (DFA – deterministic finite automata) .............. 11
1.2.1.2 Autómatas finitos no deterministas (NFA – nondeterministic finite automata) ... 12
1.2.2 Autómata de Pila (PDA –push-down automaton) ...................................................... 13
1.2.2.1 Autómatas de pila ................................................................................................. 13
1.3 Gramáticas formales ........................................................................................................... 14
1.3.1 Gramática Regular....................................................................................................... 15
1.3.2 Gramática libre de contexto (CFG – Context Free Grammar) .................................... 16
1.4 Fases de un compilador ....................................................................................................... 16
2. Análisis Léxico......................................................................................................................... 21
2.1 Definición de un reconocedor de cadenas no trivial ........................................................... 22
2.1.1 Las operaciones regulares ............................................................................................ 23
2.1.2 Definición formal de una expresión regular................................................................ 23
2.2 Programar sistemáticamente el reconocedor en lo referente a la obtención del autómata,
almacenarlo eficientemente y manejar adecuadamente el archivo fuente ................................ 24
2.2.1 Conversión de una expresión regular a un autómata finito no determinista (NFA) .... 24
2.2.2 Conversión de un autómata finito nodeterminista (NFA) a su correspondiente
autómata finito determinista (DFA) ...................................................................................... 34
2.2.3 Codificación de un DFA en pseudocódigo .................................................................. 41
3. Análisis sintáctico..................................................................................................................... 45
3.1 Construcción de tablas parse LR(1) .................................................................................... 52
Algoritmo para construir el FA que servirá de base para la tabla parse LR(1) ........................ 52
3.2 Análisis sintáctico LALR(1)............................................................................................... 56
3.2.1 Primer principio del análisis sintáctico LALR(1) ........................................................ 56
3.2.2 Segundo principio del análisis sintáctico LALR(1) ..................................................... 56
3.3 Análisis sintáctico LR(1) canónico ..................................................................................... 57
3.3.1 Autómatasfinitos de elementos LR(1) ........................................................................ 57
3.3.3 Definición de transiciones LR(1) (parte 1) .................................................................. 58
3.4 Conjuntos primero .............................................................................................................. 59
4. Análisis Léxico...