licenciatura informatica
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...
Regístrate para leer el documento completo.