1. No category

COMPILADORES
Universidad
Tecnológica de la
Mixteca
__________________________
__________________________
Compiladores
M.C. Gabriel Gerónimo Castillo
Laboratorio Edumóvil
Universidad Tecnológica de la Mixteca
[email protected]
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Temario
1. Introducción al proceso de compilación
__________________________
__________________________
__________________________
2. Análisis Léxico
_________________________
3. Análisis Sintáctico
__________________________
4. Análisis Semántico
5. Generadores de Código
6. Optimización de Código
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Referencias
__________________________
•! Compiladores Principios, técnicas y herramientas. Alfred V. Aho, Ravi Sethi,
Jeffrey D. Ullman.!Adisson Wesley.
•! Compiladores Conceptos fundamentales. Teufel, Schmidt, Teufel. Adisson
Wesley Iberoamericana.
__________________________
__________________________
_________________________
__________________________
•! Modern compiler implementation in C. Appel. Cambridge
•! Teoría de Autómatas y Lenguajes Formales. Dean Kelley. PrenticeHall
Cambridge
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Introducción al proceso
de compilación
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Tipos de sistemas de compilación
dependiendo del tipo de código y funcionamiento
__________________________
__________________________
Fuente
Compiladores
Objeto
__________________________
_________________________
Ensamblador: Traducen programas escritos en lenguaje ensamblador a
código de máquina.
Compilador: Traducen programas escritos en lenguaje de alto nivel a código
intermedio o a código de máquina.
Intérprete: Un intérprete no genera código objeto sino que analiza y ejecuta
directamente cada proposición del código fuente.
Preprocesador: Sustituye los macros, incluye archivos o la extensión del
lenguaje.
NOTAS DEL CURSO
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Análisis Léxico
__________________________
__________________________
Consiste en reconocer los componentes léxicos dentro del flujo, es decir,
transformar un flujo de caracteres en un flujo de componentes léxicos.
Por ejemplo la proposición
produciendo lo siguiente:
__________________________
i = 10 ;
i
=
10
;
_________________________
Identificador
Asignación
Número
Delimitador
__________________________
Los identificadores reconocidos se organizan en una tabla de símbolos, que
contiene un registro de campos de atributos asociado a dicho identificador.
__________________________
!
!
!
!
__________________________
__________________________
La tabla de símbolos se construye con el análisis léxico y sintáctico, para ser
usada en el análisis semántico y la generación de código.
__________________________
Los espacios en blanco que separan los componentes léxicos normalmente se
eliminan.
__________________________
Análisis Léxico
__________________________
__________________________
__________________________
La primer tarea de un compilador es agrupar una secuencia de caracteres
de entrada en tokens.
_________________________
__________________________
El analizador léxico o escaner típicamente accesa a la tabla de símbolos
para almacenar y/o retirar información de ciertos conceptos del lenguaje
como son variables, tipos, funciones.
VUB-DINF/2009/2
__________________________
__________________________
13
�LBRACE�
�DECLARE symbol table ref=0�
10
�NAME symbol table ref=3�
�SEMICOLON�
e syntax of Micro is described by the �NAME
rules insymbol
Figuretable
1.2.ref=3�
We will see in Chap�ASSIGN�
3 that such rules can be formalized into
what is called a grammar.
�LPAREN�
VUB-DINF/2009/2
�NUMBER
value=33�
ote that NUMBER and NAME have not
been further
defined. The idea is, of
�PLUS�
�LBRACE�represents
urse, that NUMBER represents a sequence
of digits and that NAME
�DECLARE symbol table ref=0�
�NUMBER value=3�
tring of letters and digits,
starting
with
a
letter.
�NAME symbol table ref=3�
Código fuente: �RPAREN�
�SEMICOLON�
�MINUS�
simple Micro program is shown in Figure
1.3
�NAME symbol table ref=3�
�ASSIGN�
�NUMBER value=35�
�LPAREN�
�SEMICOLON�
{
�NUMBER value=33�
�WRITE symbol table ref=2�
declare �NAME
xyz; symbol table ref=3��PLUS�
�NUMBER value=3�
xyz = (33+3)-35;
�RPAREN�
�SEMICOLON�
�MINUS�
write xyz;
�RBRACE�
�NUMBER value=35�
__________________________
__________________________
UB-DINF/2009/2
Análisis Léxico
}
Figure 1.5: Result of lexical analysis of
Figure 1.3: A Micro program
__________________________
13
�SEMICOLON�
�WRITE symbol table ref=2�
�NAME symbol table ref=3�
program
in Figure 1.3
�SEMICOLON�
�RBRACE�
Después
finalizar
escaner,table
la tabla
deexample
símboloscould
queda:
After the
scannerde
finishes,
theelsymbol
in the
look like
Figure 1.5:consists
Result of lexical
analysis of program in Figure 1.3
e semantics of Micro should be clear2 : a Micro program
of a sequence
read/write or assignment statements. There
are integer-valued
variables (which
0After
“declare”
DECLARE
the scanner finishes, the symbol table in the example could look like
ed to be declared before they are used) and
are restricted to addition
1 expressions
“read”
READ
2 “write”
WRITE 0 “declare” DECLARE
d substraction.
3
“xyz”
NAME
1
2
3
“read”
“write”
“xyz”
READ
WRITE
NAME
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
where the third column indicates the type of symbol.
3.2 x86 code
where the third column indicates the type of symbol.
Clearly, the main difficulty in writing a lexical analyzer will be to decide, while
Clearly, the main difficulty in writing a lexical analyzer will be to decide, while
readingwill
characters
whencharacters
a token
ofbywhich
type
is
finished.
Weiswill
e target language
be codeone
for by
the one,
x86reading
processor
family.
Figure
1.4
shows
one
one, when
a token
of which type
finished. We will
see in Chapter
2and
that finite
regular
expressions
and
finite automata
provide a powerful
see in
2 thatfor
regular
expressions
provide
a powerful
rt of the output
ofChapter
the compiler
the program
of Figure
1.3. automata
The
full output
NOTAS DEL CURSO and convenient method to automate this job.
and
convenient
to automate this job.
n be found in
Section
B.6.2,method
page 157.
86 processors have a number of registers, some of which are special purpose,
1.3.4 Syntax analysis
ch as the esp register which always points to the top of the stack (which grows
1.3.4 Syntax analysis
Once lexical
analysis is finished,
the parser
wnwards). More information on x86 assembler
programming
can be
foundtakes
in over to check whether the se-
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Análisis Sintáctico
VUB-DINF/2009/2
14
__________________________
Such matching can conveniently be represented as a parse tree. The parse tree
corresponding to the token sequence of Figure 1.5 is shown in Figure 1.6.
__________________________
<program>
<LBRACE>
<statement>
<SEMICOLON>
<statement>
<declaration>
(xyz)
<NAME>
<ASSIGN>
<statement> <SEMICOLON>
<MINUS>
<WRITE>
<term>
<LPAREN> <expression> <RPAREN>
<statement_list>
<write_statement>
<expression>
(xyz)
<term>
_________________________
<SEMICOLON> <statement_list>
<assignment>
<DECLARE> <NAME>
__________________________
<RBRACE}
<statement_list>
<>
<expression>
<NUMBER>
<term>
(35)
<term>
<PLUS>
<term>
(33)
<NUMBER>
(3)
__________________________
__________________________
<var>
<NAME>
<NUMBER>
__________________________
(xyz)
Figure 1.6: Parse tree of program in Figure 1.3
Note that in the parse tree, a node and its children correspond to a rule in the
syntax specification of Micro: the parent node corresponds to the left hand side
of the rule while the children correspond to the right hand side. Furthermore, the
yield3 of the parse tree is exactly the sequence of tokens that resulted from the
lexical analysis of the source text.
__________________________
__________________________
__________________________
Análisis Sintáctico
Hence the job of the parser is to construct a parse tree that fits, according to the
syntax specification, the token sequence that was generated by the lexical analyzer.
In Chapter 3, we’ll see how context-free grammars can be used to specify the
syntax of a programming language and how it is possible to automatically generate
parser programs from such a context-free grammar.
Revisa 1.3.5
si los símbolos
Semantic aparecen
analysis en el orden correcto (es decir, revisa si el
programa fuente fue diseñado de acuerdo con la sintaxis del de lenguaje
Having established
that the source
text is syntactically
correct,fuente
the compiler
mayformar
programación)
y combina
los símbolos
del código
para
now perform additional checks such as determining the type of expressions and
unidades gramaticales (frases gramaticales).
3
The yield of a tree is the sequence of leafs of the tree in lexicographical (left-to-right) order
En general, las unidades gramaticales se organizan y representan con
árboles de análisis sintáctico o árboles sintácticos.
Árbol Sintáctico
__________________________
Ejemplo:
__________________________
h=x+y-x+y
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Análisis Semántico
__________________________
__________________________
Se considera el significado de una unidad gramatical, es decir, se debe
interpretar. Esto se puede lograr traduciendo la entrada a una forma de
representación intermedia.
__________________________
_________________________
__________________________
Por ejemplo, en la proposición h = x + y - x + y
__________________________
Si nunca se hubiese definido la variable h, la proposición de asignación no
tendría sentido. También por ejemplo, la asignación de una variable
booleana a una variable real tampoco tendría sentido. Este tipo de
inconsistencia será reconocido por el análisis de tipos.
__________________________
__________________________
__________________________
__________________________
Generador de Código
__________________________
__________________________
El código objeto se genera en la última fase de la compilación. En esta
fase el código intermedio se transforma en código de máquina y la
memoria necesaria quedará determinada.
__________________________
Ésta es la única fase que depende del hardware, dado que el conjunto de
instrucciones varía de una computadora a otra.
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Fases de un compilador
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
__________________________
__________________________
__________________________
_________________________
Análisis Léxico
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Analizador Léxico vs Analizador
Sintáctico
__________________________
__________________________
__________________________
_________________________
Componente
léxico
Programa
fuente
Analizador
léxico
__________________________
Analizador
sintáctico
__________________________
Obtén el siguiente
componente léxico
__________________________
__________________________
Tabla de
símbolos
__________________________
__________________________
Análisis Léxico
__________________________
__________________________
__________________________
Entrada
‘6’ ’.’ ‘1’
‘+’
‘r’ ‘i’ ‘g’ ‘h’ ‘t’
‘*’
‘2’ ‘1’
A. Léxico
Número
6.1
Operador +
Variable
right
Operador *
Entero
21
Numero
Variable
Parser
_________________________
ADD
__________________________
MUL
Entero
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Definiciones
__________________________
__________________________
Símbolo. Es una entidad abstracta. Normalmente los símbolos son letras
(a,b,...,z, A, B,...Z), dígitos (0,1,...,9) y otros caracteres (+,-,*,/,?,...)
__________________________
_________________________
Alfabeto ! . Es un conjunto finito de símbolos, no vacío.
V1= {A,B, C, D, E, F, G, ..., X, Y, Z}
V2= {a, b, c, d, 0, 1, 2, 3, 4, *, #, +}
V3= {0,1}
V4= {if, while, do, repeat, until, else}
Para definir que un símbolo a pertenece a un alfabeto V se utiliza la
notación a! V
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Definiciones
__________________________
Cadena. Es una secuencia finita de símbolos de un determinado Alfabeto.
__________________________
Longitud de cadena. Es el número de símbolos que contiene.
__________________________
_________________________
|a + 2 * b| ! 5
|if a > b then a = b ;| ! 9
__________________________
Cadena vacía. Aquella cadena que no tiene símbolos y se denota por ε,
entonces su longitud es:
|ε|! 0
__________________________
Concatenación de cadenas. Sean ! y " dos cadenas cualesquiera, se denota
concatenación de ! y " a una nueva cadena !" constituida por los símbolos
de la cadena ! seguidos por los de la cadena ".
__________________________
El elemento neutro de la concatenación es ε.
Lenguaje
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
El término Lenguaje se refiere a cualquier conjunto de cadenas de un
alfabeto fijo.
Se puede tener el lenguaje ∅, que es el conjunto vacío, o {ε} el conjunto
que sólo contiene la cadena vacía.
Existen varias operaciones que se pueden aplicar a los lenguajes, para el
análisis léxico, los que interesan son la Unión, Concatenación y la
Cerradura, así como la Exponenciación ( L0 = ε, y Li = Li-1 L)
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Lenguajes regulares
__________________________
__________________________
Definición
Sea ∑ un alfabeto. El conjunto de los lenguajes regulares sobre ∑ se
definen recursivamente como sigue:
__________________________
1. ∅ es un lenguaje regular.
__________________________
2. {ε}, el conjunto que contiene la cadena vacía, es un lenguaje regular.
__________________________
3. ∀a∈∑, {a} es un lenguaje regular.
__________________________
4. Si A y B son lenguajes regulares, entonces A!B, AB, A* son lenguajes
regulares.
_________________________
__________________________
__________________________
__________________________
5. Ningún otro lenguaje sobre ∑ es regular.
Operaciones sobre
Lenguajes
__________________________
__________________________
__________________________
Operación
Definición
Unión: L!M
L∪M= { s | s está en L o s está en M }
Concatenación: LM
LM= { st | s está en L y t está en M }
Cerradura de Kleene: L* L* = i=0U∞Li
Cerradura Positiva: L+ L+ = i=1U∞Li
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Lenguaje
Ejemplo: Sea
L = {A, B, . . . , Z, a, b, . . . , z}
D ={ 0, 1, 2, . . . , 9}
Algunos lenguajes creados a partir de L y D aplicando operaciones sobre
lenguajes son:
1. L!D es el conjunto de letras y dígitos
2. LD es el conjunto de cadenas que consta de una letra seguido de un dígito
3. L4 es el conjunto de todas las cadenas de cuatro letras
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
4. L* es el conjunto de todas las cadenas de letras, incluyendo ∊
__________________________
5. L (L!D)* es el conjunto de todas las cadenas de letras y dígitos que
comienzan con una letra
__________________________
6. D+ es el conjunto de todas las cadenas de uno o más dígitos
NOTAS DEL CURSO
__________________________
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Expresiones regulares
__________________________
__________________________
Una expresión regular r representa un lenguaje L(r).
Una expresión regular se construye a partir de expresiones regulares más
simples utilizando un conjunto de reglas definidas.
Las reglas de definición especifican cómo se forma L(r) combinando de
varias maneras los lenguajes representados por las subexpresiones de r.
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Expresiones regulares
__________________________
__________________________
Definición. Reglas de las expresiones regulares del alfabeto ∑
1. ∅ es un lenguaje regular.
__________________________
_________________________
2. ε es una expresión regular designada por {ε}, es decir, el conjunto que
contiene la cadena vacía, es un lenguaje regular.
__________________________
3. Si a ∈ ∑, entonces a es una expresión regular designada por {a}
__________________________
4. Suponiendo que r y s sean expresiones regulares representadas por los
lenguajes L(r) y L(s), entonces
a) (r) | (s) es una expresión regular representada por L(r) ! L(s)
b) (r)(s) es una expresión regular representada por L(r)L(s)
c) (r)* es una expresión regular representada por L(r)*
d) (r) es una expresión regular representada por L(r)
__________________________
5. Ninguna otra secuencia de símbolos es una expresión regular.
Comparando la definición anterior con la definición de lenguajes
regulares se deduce que toda expresión regular sobre ∑ denota un
lenguaje regular sobre ∑.
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Equivalencias
Teorema.
Sean r, s y t expresiones regulares sobre el mismo alfabeto ∑. Entonces:
1. r ! s = s ! r
2. r ! ∅ = r = ∅ ∪ r
3. r ! r = r
4. (r ! s) ∪ t = r ∪ (s ! t)
5. rε= εr = r
6. r∅ = r∅ = ∅
7. (rs) t = r (st)
8. r (s ! t) = rs ! rt y (r ! s) t = rt ! st
9. r* = r** = r*r* = (ε ! r)* = r* (r ! ε) = (r ! ε) r* = ε ! rr*
10. (r ! s)* = (r* ! s*)* = (r*s*)* = (r*s)* r* = r* (sr*)*
11. r (sr)* = (rs)* r
12. (r*s)* = ε ! (r ! s)* s
13. (rs*)* = ε ! r (r ! s)*
14. s (r ! ε)* (r ! ε) ! s = sr*
15. rr* = r*r
Convenciones de escritura
de expresiones regulares
Se pueden evitar los paréntesis innecesarios si se adoptan las convenciones:
1. El operador unario * tiene la mayor precedencia y es asociativo por la
izquierda,
2. La concatenación tiene la segunda mayor precedencia y es asociativo por la
izquierda,
3. | tiene la menor precedencia y es asociativo por la izquierda.
Ejemplo:
(a)| ((b)*(c)) es equivalente a a|b*c
Estas dos expresiones designan el conjunto de cadenas que tienen una
sola a, o cero o más b seguidas de una c.
Propiedades algebraicas de las
expresiones regulares
Axioma
r|s = s|r
r|(s|t) = (r|s)|t
(rs)t= r(st)
r (s|t) = rs | rt
(s|t) r = sr | tr
εr=r
rε=r
r* = (r| ε)*
r** = r*
NOTAS DEL CURSO
Descripción
| es conmutativo
| es asociativo
la concatenación es asociativa
la concatenación distribuye sobre |
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
∊ es el elemento identidad para la concatenación
__________________________
la relación entre * y ε
__________________________
* es idempotente
__________________________
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Definiciones regulares
__________________________
__________________________
Por conveniencia de notación, puede ser deseable dar nombres a las
expresiones regulares y definir expresiones regulares utilizando dichos
nombres como si fueran símbolos.
__________________________
Si ! es un alfabeto, entonces una definición regular es una secuencia de
__________________________
definiciones de la forma
d1 ! r1
d2 ! r2
...
dn ! rn
donde cada di es un nombre distinto, y cada ri es una expresión regular sobre ! !
{d1, d2, . . ., di-1}
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Definiciones regulares
__________________________
__________________________
Ejemplo.
Definiciones regulares para identificadores de un lenguaje:
__________________________
_________________________
letra ! A | B | . . . | Z | a | b | . . . | z
__________________________
digito ! 0 | 1 | 2 | . . . | 9
__________________________
id ! letra (letra | digito)*
digitos ! digito digito*
__________________________
fraccion ! . digito | ε
__________________________
exponente ! ( E ( + | - | ε ) digitos ) | ε
__________________________
numero ! digitos fraccion exponente
Abreviatura en la notación
__________________________
__________________________
__________________________
1. Uno o mas casos. El operador unario + significa “uno o más casos
de”.
r * = r + | ε y r + = r r*
__________________________
2. Cero o un caso. El operador unario ? significa “cero o un caso de”.
r? = r | ε
__________________________
3. Clases de caracteres. La notación [abc] es equivalente a a | b | c, [az] es equivalente a a | b | . . . | z
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Reconocimiento de
componentes léxicos
Ejemplo. Consideremos el siguiente fragmento gramatical
prop ! if expr then prop | if expr then prop else prop | ε
expr ! termino oprel termino | termino
termino ! id | num
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
if ! if
then ! then
else ! else
oprel ! < | <= | = | <> | > | >=
id ! letra (letra | digito)*
num ! digito+ (. digito+)? (E(+ | - )? digito +)?
__________________________
__________________________
__________________________
delim ! blanco | tab | lineanueva
eb ! delim+
__________________________
Patrones de expresiones regulares
para componentes léxicos
__________________________
__________________________
Expresión
regular
Componente
léxico
Valor del atributo
__________________________
eb
-
-
if
if
-
_________________________
then
then
-
else
else
-
id
id
apuntador a la entrada de la tabla
num
num
apuntador a la entrada de la tabla
<
oprel
MEN
<=
oprel
MEI
=
oprel
IGU
<>
oprel
DIF
>
oprel
MAY
>=
oprel
MAI
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Diagramas de transiciones
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Diagramas de transiciones
__________________________
Es una colección finita de círculos (estados), los cuales se pueden rotular,
conectados por flechas que reciben el nombre de arcos o aristas.
__________________________
Cada uno de estos arcos se etiqueta con un símbolo o categoría de
símbolos (p.e. dígito, letra, numero) que representa la cadena de entrada que
se analiza.
_________________________
__________________________
__________________________
Uno de los círculos se designa con un apuntador, y representa la posición
inicial (estado Inicial), y por lo menos uno se representa como un círculo
doble, llamado posición final (estado de Aceptación).
__________________________
Decimos que una cadena de símbolos es aceptada por un diagrama de
transiciones si los símbolos que aparecen en la cadena (de izquierda a
derecha) corresponden a una secuencia de arcos rotulados que conducen
del círculo designado por el apuntador a un círculo doble.
__________________________
Diagramas de transición para
>=
Inicio
>
0
7
otro
__________________________
__________________________
__________________________
__________________________
__________________________
=
6
__________________________
_________________________
*
8
__________________________
__________________________
Si surge un fallo mientras se está siguiendo un diagrama de
transiciones, se debe retroceder el apuntador delantero hasta
donde estaba en el estado inicial de dicho diagrama, y activar el
siguiente diagrama de transiciones.
__________________________
__________________________
__________________________
__________________________
Diagramas de transición para el
componente léxico oprel
Inicio
0
<
1
=
return (oprel, MEI)
2
>
=
5
otro
4
>
6
=
otro
7
8
NOTAS DEL CURSO
return (oprel, DIF)
3
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
*
return (oprel, MEN)
return (oprel, MAI)
*
return (oprel, MAY)
__________________________
__________________________
__________________________
__________________________
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Algoritmo de Diagrama de
transición
ALGORITMO
Estado=1
Leer símbolo
while !EOF
case Estado
1: if símbolo==Letra
Estado=3
else if símbolo==Dígito
Estado=2
else Error
2: Error
3. if símbolo==Letra
Estado=3
else if símbolo==Dígito
Estado=3
else Error
Leer símbolo
end_while
if Estado!=3 Error
Tabla de transiciones
Es un arreglo bidimensional cuyos elementos proporcionan el resumen de
un diagrama de transiciones.
ALGORITMO
Letra
Dígito
FDC
1
3
2
Error
2
Error
Error
Error
3
3
3
Aceptar
Estado=1
do
Lee símbolo
case símbolo
Letra: Entrada=”Letra”
Dígito: Entrada=”Dígito”
EOF: Entrada=”FDC”
default: ERROR
fin_case
Estado=Tabla[Estado,Entrada]
if Estado==”ERROR”
SALIR A RUTINA DE ERROR
while (Estado!=”Aceptar”)
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Diagrama de transiciones de un
número real
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Tabla de transiciones construida a partir
de diagrama de transición anterior
__________________________
__________________________
Dígito
.
E
+
-
FDC
__________________________
1
2
Error
Error
Error
Error
Error
_________________________
2
2
3
5
Error
Error
Error
__________________________
3
4
Error
Error
Error
Error
Error
__________________________
4
4
Error
5
Error
Error Aceptar
5
7
Error
Error
6
6
Error
6
7
Error
Error
Error
Error
Error
7
7
Error
Error
Error
Error Aceptar
__________________________
__________________________
__________________________
__________________________
A. Léxico basado en la tabla
de transiciones anterior
__________________________
__________________________
__________________________
ALGORITMO
_________________________
Estado=1
do
Lee símbolo
case símbolo
0 a 9: Entrada=”Dígito”
EOF: Entrada=”FDC”
., E, +, -: Entrada=símbolo
default: ERROR
fin_case
Estado=Tabla[Estado,Entrada]
if Estado==”ERROR”
SALIR A RUTINA DE ERROR
while (Estado!=”Aceptar”)
__________________________
Ejercicios
1. Diseñe un diagrama de transiciones para reconocer expresiones aritméticas de longitud
arbitraria que comprenden enteros positivos separados por signos de suma, resta, multiplicación o
división.
2. Escriba una analizador léxico a partir del siguiente diagrama de transiciones.
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
3. Construya una tabla de transiciones a partir del diagrama del ejercicio 2 y escriba un
analizador léxico basado en esa tabla.
NOTAS DEL CURSO
__________________________
__________________________
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
Ejercicios
__________________________
__________________________
4. Describa las cadenas que acepta el autómata finito determinista representado en el siguiente
diagrama de transiciones.
letra
letra
__________________________
_________________________
__________________________
__________________________
dígito
dígito
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
Autómatas Finitos
Deterministas
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
ADF
Definición:
Un autómata finito determinista (AFD) es una quíntupla (Q, !, ", qo, F)
donde
. Q es un conjunto finito de estados
. ! es el alfabeto de entrada finito
. ": Q x ! ! Q es una función de transición
. qo ! Q es el estado inicial
. F " Q es el conjunto de estados finales o de aceptación
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO
COMPILADORES
__________________________
__________________________
__________________________
_________________________
__________________________
__________________________
__________________________
__________________________
__________________________
__________________________
NOTAS DEL CURSO
M.C. GABRIEL GERÓNIMO CASTILLO