Download - Compiladores (23/04/2015 01:35)- 4.1 - Compiladores Tema 3 Análisis Lexicográfico Scanners
Compiladores (04/21/23 19:16) - 4.1 -
Compiladores
Tema 3
Análisis Lexicográfico
Scanners
Compiladores (04/21/23 19:16) - 4.2 -
Scanner
Scanner(autómata finito determinista
o específico)
Programa fuente(secuencia de caracteres)
Secuencia de símbolos
Categoría sintáctica: número, identificador, if, suma, abrir paréntesis
Atributos: valor, nombre, string.
Símbolo
Compiladores (04/21/23 19:16) - 4.3 -
Ejemplos de Símbolos
• Identificador:
– Forma: una letra seguida de letras o números. Ej. a, b1, c3D– Atributo nombre: string con la secuencia de caracteres que
forma el identificador en mayúsculas. Ej. “A”, “B1”, “C3D”• Número:
– Forma: secuencia de dígitos que puede empezar con el signo menos y puede contener un punto. Ej. 10, -3, 15.4, -54.276, .10
– Atributo valor: double con el valor numérico.– Precisión: entero o real.
• Punto y Coma:
– Forma: ;• Palabra clave if:
– Forma: if, If, IF, iF• Fin de fichero:
– Forma: carácter EOF de C.
Compiladores (04/21/23 19:16) - 4.4 -
Separación en Símbolos
• Los comentarios, saltos de línea, espacios y tabs no forman parte de la secuencia de símbolos.
• Al definir los símbolos se ha de considerar como se separan.– Entre dos símbolos se encuentra cararcteres
separadores (espacios, tabs, comentarios, etc.)
– Siempre se intenta leer el símbolo más largo
• Ejemplos:– if ( a > 10 ) bc = 30 * - 4
– if ( a >= 10 ) bc = 30 * - 4
– int * * a ;
– zz /* comentario */ + dd
Compiladores (04/21/23 19:16) - 4.5 -
Especificación
• Símbolos: identificador, abrir paréntesis, string, etc.
– Forma:• Expresiones regulares para cada categoría
sintáctica.
– Atributos:• Algoritmo para el cálculo de cada atributo a
partir de la secuencia de caracteres del símbolo.
• Separadores: espacios, comentarios, salto de línea, tab, etc.
– Forma:• Expresión regular que especifica las
secuencias de caracteres que separan los símbolos.
• Otros: errores, final de fichero, salto de línea, etc.
Compiladores (04/21/23 19:16) - 4.6 -
Expresiones Regulares
• es una expresión regular que representa el conjunto vacío.
• es una expresión regular que representa el conjunto con un único elemento que es la secuencia vacía
• un string s es una expresión regular que representa un conjunto que solo contiene s. Para evitar confusiones, los metacaracteres que contenga s van entre comillas (‘|’,’-’,...).
• V es el conjunto de todos los caracteres (vocabulario).
Compiladores (04/21/23 19:16) - 4.7 -
Expresiones RegularesOperadores
• AB Concatenación
{ab| aA y bB}
• A|B unión {x| xA ó xB}
• A* repetición • A+ repetición de uno o más • An repetición de n veces• (A-B) resta{x| xA y xB}
Compiladores (04/21/23 19:16) - 4.8 -
Ejemplos de Expresiones Regulares
• dígito d=0|1|2|3|4|5|6|7|8|9
• entero_sin_signo=d+
• entero=(+|-|)d+
• real=d+.d+(|e(+|-|) d+)
• letra l=a|...|z|A...|Z
• identificador=l(l|d)*
• string=“(V-”)*”
Compiladores (04/21/23 19:16) - 4.9 -
Scanner implementado a mano
• El scanner es un procedimiento que lee un símbolo del programa fuente– Entrada: caracteres de un istream
istream *IScan; // Stream de entrada
– Salida: símbolo en variable globalenum Categoria {
SNumero,SIdentificador,SString, Sif...
};
Categoria ScanCat; // Categorita sintáctica
double ScanEntero; // Valor numérico
double ScanReal; // Valor numérico
bool ScanEsEntero; // Tipo de número
string ScanString; // String del símbolo
• Condiciones que cumple el scanner– Lee caracteres hasta conseguir leer un
símbolo
– En caso de duda lee el símbolo más largo
– Al salir del scanner, el último carácter leído pertenece al símbolo. Si se ha leído alguno más se devuelve a la entrada
Compiladores (04/21/23 19:16) - 4.10 -
Scanner en C++
void Scanner()
{
int c;
for (;;) {
c=IScan->get();
switch (c) {
// Separadores
case '\r':
case '\n':
case '\t':
case ' ':
break;
default:
if ((c>='a' && c<='z') || (c>='A' && c<='Z') || (c=='_')) {
ScanIdentificador(c);
return;
}
else {
COut << "No se tratar el caracter "
<< (char) c << endl;
}
}
}
}
Compiladores (04/21/23 19:16) - 4.11 -
Scanner de Identificadores en C++
void ScanIdentificador(int c)
{
char buf[256];
int i;
for (i=0; (c>='a' && c<='z') ||
(c>='A' && c<='Z') ||
(c=='_') ||
(c>='0' && c<='9');) {
if (i>254) {
throw CVException(“Identificador demasiado largo");
}
buf[i++]=c;
c=IScan->get();
}
buf[i]='\0';
ScanCat=SIdentificador;
ScanString=buf;
IScan->putback(c);
}
Compiladores (04/21/23 19:16) - 4.12 -
Autómatas Finitos
• Autómata finito determinista (K,T,M,S,Z)– K conjunto finito de estados.
– T conjunto de terminales (símbolos/caracteres de entrada).
– M:KTK función de transición.
– SK estado inicial.
– ZK conjunto de estados finales.
• Autómata finito no determinista (K,T,M,S,Z)– M:KTPK) función de transición.
Compiladores (04/21/23 19:16) - 4.13 -
Representación de los Autómatas Finitos
1 Estado Transición
1 1Estado inicial
Estado final
1 2 3 4a b
d
c
Acepta las secuencias: abc(dc)*
Ej. abc, abcdc, abcdcdc, abcdcdc...
Compiladores (04/21/23 19:16) - 4.14 -
Paso de Expresión Regular a AFND
a
Exp. a
Exp.
Exp. A|B
AFNDde A
AFNDde B
Compiladores (04/21/23 19:16) - 4.15 -
Paso de Expresión Regular a AFND
Exp. AB
AFNDde A
AFNDde B
Compiladores (04/21/23 19:16) - 4.16 -
Paso de Expresión Regular a AFND
Exp. A*
AFNDde A
Compiladores (04/21/23 19:16) - 4.17 -
Ejemplo del Paso de Exp. Regular a AFND
Expresión: ab|ac*
AFND: ab
AFND: ac*
Expresión: ab
Expresión: ac*
AFND: a
AFND: b
Compiladores (04/21/23 19:16) - 4.18 -
Ejemplo del Paso de Exp. Regular a AFND
Expresión: ac*
AFND: a
AFND: c*
Expresión: a a
Expresión: b b
Expresión: c c
Expresión: c* AFND: c
Compiladores (04/21/23 19:16) - 4.19 -
Ejemplo del Paso de Exp. Regular a AFND
abExpresión: ab|ac*
a
2
1
c
3
4
AFND
• Problema:– Un a AFND puede seguir más de un
camino durante su interpretación.
• Solución:– Pasar de AFND a AFD.
Compiladores (04/21/23 19:16) - 4.20 -
Paso de AFND a AFD
• El conjunto de estados del nuevo AFD es el conjunto de las partes del conjunto de estados del AFND.
• El estado inicial del AFD es el mismo que el del AFND.
• Un estado del AFD es final si contiene algún estado final del AFND.
Compiladores (04/21/23 19:16) - 4.21 -
Cálculo del Conjunto de Transiciones
• Poner el estado inicial en el conjunto de estados K del AFD. El conjunto de transiciones M=
• Repetir hasta que K y M no varíen:– Para cada estado de K y carácter de entrada
aplicar las transiciones posibles del AFND y acumular en K y M el nuevo estado y la nueva transición.
Compiladores (04/21/23 19:16) - 4.22 -
Ejemplo del Paso de AFND a AFD
abExpresión: ab|ac*
a
2
1
c
3
4
AFND
I S F1 a 2,42,4 b 32,4 c 44 c 4
Tabla de Transiciones AFD
ba1
c
3
4
2,4
c
AFD
Compiladores (04/21/23 19:16) - 4.23 -
Implementación de un AFD
• Variable de estado S.• Tabla de transiciones T: dado un estado y un
carácter de entrada específica el nuevo o error.
• Algoritmo:– S=estado inicial.
– Repetir• C=leer_caracter()
• si T[S][C]==error entonces salir del bucle
• S=T[S][C]
– si S no es final error
Compiladores (04/21/23 19:16) - 4.24 -
Ejemplo de Tabla de Transiciones
Tabla de Transiciones
ba1
c
3
4c
a b c1 2 Err Err2 Err 3 43 Err Err Err4 Err Err 4
2
Compiladores (04/21/23 19:16) - 4.25 -
Scanner Basado en AFD
• Un AFD no es un scanner. Falta– Poder leer una secuencia de símbolos y
separadores
– Diferenciar las categorías sintácticas de los símbolos
Compiladores (04/21/23 19:16) - 4.26 -
Consideraciones Prácticas
• Las palabras reservadas se pueden considerar como identificadores para evitar crear un AFD demasiado grande (2n estados del AFND).
• Hay que marcar el final del código fuente. Este indicador pertenecerá al alfabeto.
• Los símbolos tienen atributos que hay que calcular.
Compiladores (04/21/23 19:16) - 4.27 -
Consideraciones Prácticas
• Los estados finales del AFD se han de marcar con el símbolo que reconocen.
• Como hay que reconoce más de un símbolo puede ser necesario tener que leer varios caracteres hacia delante.
• La creación de un scanner se puede hacer directamente sin considerar los autómatas finitos.
Compiladores (04/21/23 19:16) - 4.28 -
Errores Lexicográficos
• Tener un símbolo de error que se pasa al parser.
• Señalar el error e ignorarlo.
• Tratamiento específico.
• Falta información para corregir los errores lexicográficos.