Semana
1
Las Fases De Un
Compilador
Un compilador opera en fases,
cada una de las cuales transforma al programa fuente de una representación a
otra. Las fases se descomponen en:
Toda compilación tiene un
front end y back end.
Análisis léxico: encuentra las
palabras del programa. Revisa el programa y obtiene una expresión regular como
la siguiente: id([A-Z][a-z])([A-Z][a-z][0-9]).
Análisis Sintáctico: Crea el
árbol del programa en base a las posiciones. Por
ejemplo:
A -> id
‘:=’ exp
exp ->
expt exp
Producciones
exp -> exp *
exp
Análisis
Semántico: toma el resultado del análisis sintáctico y lo
mejora.
Manejador de
la tabla de símbolos: guarda los símbolos.
Análisis
sintáctico descendente:
La
construcción descendente de un árbol de análisis sintáctico se hace empezando en
la raíz.
Type è simple |
id
| ARRAY [simple] of type
Simple è
INTEGER
|CHAR
|NUM DOT DOT NUM
Luego e un
examen de izquierda a derecha se obtiene:
ARRAY [NUM DOT DOT NUM]
OFINTEGER
Semana
2
Análisis
Sintáctico
Es el proceso de determinar si una cadena de componentes léxicos puede
ser generada por una gramática
La
siguiente gramática es un ejemplo de análisis sintáctico descendiente.
Para entender el
análisis sintáctico es útil pensar en un árbol, aunque en realidad el compilador
no lo construya.
Por ejemplo, el árbol sintáctico de la
cadena:
array [ num dotdot ] of
integer
es el siguiente:
Inicialmente el componente léxico array es el símbolo de preanálisis, y
la raíz del árbol, etiquetada con el no Terminal inicial tipo. La idea es
construir el resto del árbol de manera que la cadena generada sea la misma de
entrada. Para que ocurra una concordancia, el no Terminal tipo debe derivar una
cadena que empiece con el símbolo de preanálisis array.
Cuando el nodo que se esta considerando es un Terminal y concuerda con el
símbolo de preanálisis, se avanza en el árbol de análisis sintáctico y en la
entrada. El siguiente componente léxico de la entrada se convierte en el nuevo
símbolo de preanálisis y se considera el siguiente hijo del
árbol.
Semana 3
Analizador
Léxico
La Tarea principal del analizador léxico
es leer caracteres y producir una salida en forma de una secuencia de tokens que utiliza el parser en el
análisis sintáctico. Esto se ilustra en la siguiente
figura:
Gramáticaà
Producción Terminal: Es un símbolo que
aparece a la derecha; y no a la izquierda de la
hilera.
Lenguaje Gramatical à
G = (Producciones – Terminales—no
Terminales-- Inicial)
L(G) = {w Hilera è
*w}
Inicial: type
No temrinales:
{type simple}
Expresión Gramatical Normalà
Exp è Exp +
ID
Exp è ID
ID = identificador à letra seguida de más letras o
números.
Recursividad
Izquierda:
Si una gramática se encicla la recursividad izquierda toma la gramática y la
arregla generando una nueva gramática.
La diferencia entre un Token y un Lexema es que hablamos de Token en terminos de gramática y
de Lexema en términos del programa.
Autómata Determinista
Finito
1) Conjunto de estados finitos
(Q).
2) Conjunto de símbolos finitos de entrada
(a,b).
3) Estado Inicial (qo).
4) Estados finales de aceptación
(F).
Estados = circulos
Símbolos = letras y
flechas
Reconocer lenguaje à recibir hilera à determinar si es del sistema o
no.
Función Transición:
Flechas
Autómata No
Determinista
Ocurre cuando una letra tiene más de un
estado.
[a - z][0 - 9]
[a -
z]
