ANALIZADOR L XICO

FACULTAD DE INFORMÁTICA
UNIVERSIDAD POLITÉCNICA DE MADRID

UNIVERSIDAD POLITÉCNICA DE MADRID
FACULTAD DE INFORMÁTICA

TRABAJO FIN DE CARRERA
INTERPRETE DE UN LABORATORIO VIRTUAL DE ADN

AUTOR: JAVIER GÓMEZ CONTRERAS
TUTOR: JUAN B. CASTELLANOS PENUELA

#

Javier Gómez Contreras

/^jjg^

Interprete de un laboratorio virtual de ADN
Facultad de Informática

Universidad Politécnica de Madrid

ifgJl^SSSp'

ÍNDICE
1

PROLOGO

4

2

AGRADECIMIENTOS

5

3

OBJETIVOS

6

4

DESARROLLO

7
\

4.1

Teoría de grafos

4.2
Gramáticas formales
4.2.1
Lenguaje formal
4.2.2
Operaciones con lenguajes
4.2.3
Gramática formal
4.2.4
Clasificación de gramáticas

7
9
9
9
9
10

.

4.3
Autómatas Finitos
4.3.1
Expresiones regulares
4.3.2
Autómata finito no determinista
4.3.3
Autómata finito determinista
4.3.4Reconocimiento de patrones

11
11
11
13
13

4.4
Técnicas de laboratorio
4.4.1
Funciones de computación
4.4.1.1
Annealing
4.4.1.2
Amplificación
4.4.1.3
Corte
4.4.1.4
Destrucción
4.4.1.5
Detección
4.4.1.6
Extracción
4.4.1.7
Lectura
4.4.1.8
Marcado
4.4.1.9
Melting
4.4.1.10
Mezcla
4.4.1.11
Separación
4.4.1.12
Síntesis
4.4.1.13
Substitución
4.4.1.14
Unión

14
14
15
15
15
16
16
16
16
16
16
16
16
17
17
174.5
Experimento L. M. Adleman
4.5.1
Trayectoria L.M. Adleman
4.5.2
Experimento de L.M. Adleman
4.5.3
Implementación normal
4.5.4
Implementación molecular
4.5.5
Consideraciones
4.5.6
Conclusiones
4.6

Fundamentos de compilación

,

18
18
20
21
22
24
25
27

Javier Gómez Contreras

A$*¡£¡¡&>

Interprete de un laboratorio virtual de ADN I ffi ]
Facultad de Informática

Universidad Politécnica de Madrid4.6.1
Analizador léxico
4.6.1.1
¿Qué es un analizador léxico?
4.6.1.2
Funciones del analizador léxico
4.6.1.3
Necesidad del analizador léxico
4.6.1.4
Conceptos de tokens, patrones y lexemas
4.6.1.5
Diseño de un analizador léxico
4.6.1.6
Acciones semánticas
4.6.1.7
Errores léxicos
4.6.2
Tabla de Simbolos
4.6.2.1
Consideraciones sobre la tabla de símbolos
4.6.2.2
Funciones de la tabla de símbolos4.6.2.3
Tamaño de la tabla de símbolos
4.6.2.4
Organización de a tabla de símbolos
4.6.2.5
Ámbito de una variable
4.6.2.6
Tabla de símbolos por ámbito
4.6.2.7
Tabla de símbolos única
4.6.3
Análisis sintáctico
4.6.3.1
¿Qué es el análisis sintáctico?
4.6.3.2
Manejo de errores sintácticos
4.6.3.3
Gramática que acepta un analizador sintáctico
4.6.3.4
Árbol sintáctico
4.6.3.5
Gramática ambigua
4.6.3.6Gramática en forma normal de Chomsky
4.6.3.7
Gramática en forma normal de Greibach
4.6.3.8
Tipos de análisis
4.6.4
Análisis semántico
4.6.4.1
Gramáticas atribuidas
4.6.4.2
Definiciones dirigidas por sintaxis
4.6.4.3
Forma de una definición dirigida por sintaxis
4.6.4.4
Atributos sintetizados
4.6.4.5
Atributos heredados
4.6.4.6
Grafo de dependencias
4.6.4.7
Orden de evaluación
4.6.4.8
Esquemas detraducción
4.6.5
Generación de código intermedio
4.6.5.1
Tipos y Representaciones del código intermedio
4.6.5.2
Árboles semánticos y grafos acíclicos dirigidos
4.6.5.3
Código de tres direcciones
4.6.5.4
Generación de código de tres direcciones en sentencias de control
4.6.5.4.1 Sentencia IF-THEN-ELSE
4.6.5.4.2 Sentencia WHILE
4.6.5.4.3 Sentencia REPEAT
4.6.5.4.4 Sentencia CASE
4.6.5.5
Bloquesbásicos y diagramas de
flujo
4.6.6
Entorno de ejecución
4.6.6.1
Organización de la memoria en tiempo de ejecución
4.6.6.2
El código
4.6.6.3
La memoria estática
4.6.6.4
La pila
4.6.6.5
El montículo
4.7

Requisitos

^á^^íS

27
27
27
28
28
29
29
30
31
32
32
32
33
33
34
34
35
35
36
37
38
38
38
38
39
40
40
40
41
42
42
42
43
43
45
45
46
46
50
50
54
55
55
58
62
62
63
64
66
70
72

4.8
Análisis
4.8.1
Tecnología73
73

-2-

Javier Gómez Contreras

¿0Z¡&&

Interprete de un laboratorio virtual de ADN I fS j
Facultad de Informática

Universidad Politécnica de Madrid

4.8.1.1
Requisitos mínimos
4.8.2
Ciclo de vida
4.8.3
Desarrollos posteriores

^sá^S»

73
73
74

4.9
Diseño
4.9.1
Analizador léxico
4.9.2
Analizador sintáctico
4.9.3
Analizador semántico
4.9.4
Código intermedio
4.9.5
Tabla de símbolos
4.9.6...