Sintaxis - Segundo Parcial
Sintaxis - Segundo Parcial
Sintaxis - Segundo Parcial
Compilador: Complejo programa que lee un programa fuente (escrito en un lenguaje fuente, de
alto nivel) y lo traduce a un programa objeto equivalente (en un lenguaje objeto, más cercano al
lenguaje de maquina).
Capitulo 4
La etapa de compilación conocida como análisis se forma por 3 etapas: Análisis Léxico, Análisis
Sintáctico y Análisis Semántico. Todas interactúan con la tabla de símbolos.
Análisis Léxico
Es realizado por el Scanner. Consiste en recorrer el flujo de caracteres que forman el programa
fuente, detectar los lexemas y traducirlos en una secuencia de tokens.
El Scanner se implementa como una función sin parámetros que retorna valores de tipo token,
uno por vez, en la medida que es invocada por el Parser.
El Scanner ignora los espacios separadores de lexemas en el texto del programa fuente.
Cada lexema está formado por la mayor secuencia posible de caracteres para el token
correspondiente; esto requiere que a veces se lea el primer carácter que no pertenece a ese
lexema (centinela).
Ese carácter extra debe ser retornado al flujo con la función ungetc.
Ej.: int Abcd (void) { … } Abcd: pertenece a un LR infinito, requiere el centinela (espacio).
{ : Pertenece a un LR finito, no requiere centinela.
+ :Requiere centinela ya que podría ser ++ o +=
Para que el Parser pueda saber cuándo el Scanner le paso el ultimo token detectado en el flujo de
entrada, se crea un token fdt (fin de texto).
Para llevar a cabo estas estas acciones son necesarias funciones auxiliares:
void AgregarCaracter(Int); añade un carácter al buffer.
TOKEN EsReservada(void); dado un id retorna el token correspondiente.
void LimpiarBuffer(void);
feof de ANSI C, para detectar el fdt.
fgetcde ANSI C, para leer cada carácter del flujo de entrada.
las funciones ANSI C isspace, isalpha, isalnum, isdigit.
En muchos casos, los lexemas son almacenados en la TS y se representara mediante un índice que
indica la posición en la TS. Entonces el Scanner retornara el par ordenado:
(palabraReservada, índice).
Además podemos encontrar en tablas reservadas:
Identificadores (identificador, índice)
Literales-cadena (literal-cadena, índice)
Cntes. numéricas (tipoConstanteNumerica, índice) o (tipoConstanteNumerica, valor)
Análisis Sintáctico
Es realizado por el Parser (conjunto de procedimientos PAS que implementa la Gramática
Sintáctica y funciones auxiliares: ProximoToken(), Match(t) y ErrorSintáctico(token)). Este verifica
si los tokens que recibe de Scanner forman secuencias o construcciones validas (son
sintácticamente correctas), según la gramática sintáctica del LP.
Si encuentra un error sintáctico, el Parser emite el diagnostico correspondiente.
A medida que las estructuras semánticas son reconocidas, el Parser llama a las correspondientes
rutinas semánticas que realizaran el Análisis Semántico y producen una salida en un lenguaje de
bajo nivel para una MV.
El Parser está formado por un grupo de rutinas que convierte el flujo de tokens en un árbol de
análisis sintáctico. Este árbol representa a la secuencia analizada, donde los tokens que forman la
construcción son las hojas del árbol.
Al derivar una secuencia de tokens, si existe más de un noterminal en una cadena de derivación,
debemos elegir cual es el próximo noterminal que se va a expandir.
Derivación por izquierda: Se reemplaza el primer noterminal.
Derivación por derecha: Se reemplaza el último noterminal.
La derivación siempre comienza en el axioma de la GIC y finaliza con una secuencia de terminales.
Una GIC que permite dos derivaciones a izquierda para obtener la misma cadena de terminales se
denomina ambigua y debe ser evitada.
Las GIC que pueden ser utilizadas en los diferentes Análisis Sintácticos son:
Gramática LL: Es una GIC que puede ser utilizada en un AnálisisSintáctico LL.
GramáticaLR: Es una GIC que p
uede ser utilizada en un Análisis Sintáctico LR.
GramáticaLL(1): Si un noterminal tiene varias producciones, el Parser puede decidir cuál lado
derecho debe aplicar con solo conocer el próximo token del flujo de entrada (llamado símbolo de
preanálisis), por lo que es muy útil y eficiente.
A partir de esta se realiza el Análisis Sintáctico Descendiente.
Sin embargo sus principales problemas son
No pueden ser recursivas a izquierda.
No pueden tener un noterminal con dos o más producciones cuyos lados derechos
comiencen con el mismo terminal.
Estas restricciones en las producciones permitieron desarrollar los PAS.
Las operaciones que deben realizarse para transformar la GIC en una GIC equivalente apta para ser
utilizada por el ParserLL(1):
Factorización a izquierda: Para evitar el segundo problema es necesario modificar las
producciones de ese noterminal de tal forma que el prefijo común quede aislado en una
sola producción.
Ej.: <sentencia if>if (<condición>) <sentencia> else <sentencia> |
If (<condición>) <sentencia>
Corregido: <sentencia if>if(<condición>) <sentencia><opción else>
<opción else> else <sentencia> | ɛ
Eliminar recursividad a izquierda: Se logra transformando la recursividad a derecha por
una recursividad a izquierda.
Ej.: XXa | b Corregido: XbZ
Z aZ | ɛ
Obtención del conjunto PRIMERO: Permite la obtención del conjunto de todos los posibles
símbolos de preanálisis.
Sea la producción A ->X1 …Xm (con Xi pudiendo ser un terminal o noterminal); entonces
PRIMERO(X1…Xm) es el conjunto de terminales que puede iniciar cualquier cadena de
derivación que se obtenga a partir de X1…Xm.
Por cada símbolo Xi hay que fijarse:
o Si Xi es terminal, entonces Xi є PRIMERO.
o Si Xi es noterminal, se calculan los conjuntos PRIMERO las producciones de Xi.
o Si Xi puede generar ɛ, entonces Xi puede ser eliminada.
Ej.: E1 T1 E2 PRIMERO (E1) = PRIMERO (T1 E2)
E2 + T1 E2 | - T1 E2 | ɛ PRIMERO (T1 E2) = PRIMERO (T1)
T1 F1 T2 PRIMERO (T1) = PRIMERO (F1 T2)
T2 * F1 T2 | / F1 T2 | ɛ PRIMERO (F1 T2) = PRIMERO (F1)
F1 ( E1) | num PRIMERO (FI) = { ( , num }
Gramática LR(1): Solo requiere conocer el próximo token (símbolo preanálisis) para hacer un
AnálisisSintáctico correcto. El Análisis Sintáctico Ascendiente se hace a partir de esta.
Análisis Semántico
Está inmerso dentro del Análisis Sintáctico, es el comienzo de la etapa de Síntesis del compilador.
No se refiere a la interpretación del significado, sino que consiste en la realización de tareas de
verificación y conversión que no puede realizar el Análisis Sintáctico. El Análisis Semántico debe
verificar que se cumplan todas las reglas sensibles al contexto, como por ejemplo, que una
variable haya sido declarada antes de su utilización, verificación de tipos (para que cada operador
trabaje sobre operandos permitidos), etc.
Para ello, el análisis semántico utiliza mucho la tabla de símbolos.
Las rutinas semánticas llevan a cabo dos funciones:
1) Chequean la semántica estática de cada construcción: Verifican que la construcción sea legal y
tenga un significado, que las variables estén definidas, que los tipos sean correctos, etc.
2) Si la construcción es semánticamente correcta, hacen la traducción: Generan el código para una
Maquina Virtual (MV)que, a través de sus instrucciones, implementa la construcción analizada.
Libro 3
Capítulo 1
Autómatas Finitos
Un autómata finito es un mecanismo que reconoce un determinado LR (acepta cadenas que
pertenecen al lenguaje y rechaza las que no). Existen:
Autómatas Finitos Determinísticos (AFDs)
Autómatas Finitos No Determinísticos (AFNs)
o Autómatas Finitos No Determinísticos con transiciones-ɛ
La tabla de transiciones de un AFN con transiciones- ɛ debe tener una columna por cada carácter
del alfabeto, más una por el símbolo ɛ.
Capítulo 2
Algoritmo de Thompson
Este algoritmo permite obtener un AFN con transiciones-ɛ a partir de una Expresión Regular dada.
Características:
Al estado inicial no llegan transiciones.
El estado final debe ser único.
Del estado final no parten transiciones.
De cualquier estado no final pueden partir: 1 transición etiquetada con un carácter del
alfabeto, o 1 o 2 transiciones ɛ.
M1+M2
M1M2
M1*
Capítulo 3
Algoritmo de Clausuras-ɛ (o construcción de subconjuntos)
Para todo AFN existe un AFD que reconoce el mismo lenguaje, es decir, para todo AFN existe un
AFD equivalente. El algoritmo para construir un AFD a partir de un AFN se basa en el conocimiento
de dos tipos de conjuntos: Clausura-ɛ y el conjunto Hacia.
Clausura- ɛ: Es el conjunto de estados formado por q y todos aquellos estados a los cuales
se llega desde q con transiciones-ɛ. Nunca puede ser vacío porque contiene, como
mínimo, a su propio estado.
TT a ɛ
Clausura-ɛ (0) = {0, 3, 4, 6}
0- {1} {3,6}
Clausura-ɛ (1) = {1, 2, 4}
1 - {2}
Clausura-ɛ (2) = {2, 4}
2+ - {4} Clausura-ɛ (3) = {3, 4}
3 - {4} Clausura-ɛ (4) = {4}
4 {5} - Clausura-ɛ (5) = {5}
5+ - - Clausura-ɛ (6) = {6}
6+ {6} -
Intersección:
Reconoce las cadenas que son reconocidas tanto por M1 como por M2.
M1 = (Q1, Σ, T1, q1, F1) -> Mint = (Q1 x Q2, Σ, Tint, (q1 x q2), F1 x F2)
M1 = (Q2, Σ, T2, q2, F2)
Para que un nuevo estado sea inicial debe ser el producto entre los iníciales de sus respectivas
tablas. Y para que sea final, producto entre 2 finales.