Analisis Lexico

ANLISIS LXICO
Ing. de Computacin y Sistemas Autmatas y Compiladores Ing. Carlos Gaytn Toledo
Descripcin Funcional
El analizador lxico o scanner lee los caracteres del programa fuente para reconocer las palabras o lexemas y clasificarlos en componentes lxicos o tokens que son entregados al analizador sintctico.
21/11/2012
La compilacin empieza con el analizador sintctico quien solicita un token para realizar su trabajo; el analizador lxico lee smbolos y enva el token correspondiente que requiere el analizador sintctico y espera una nueva solicitud de token. El analizador lxico est supeditado por el analizador sintctico. Durante estas etapas se tiene comunicacin con la tabla de smbolos que concentra informacin de las entidades empleadas en el programa.
21/11/2012 3
21/11/2012
Componentes Lxicos o tokens
palabras reservadas: if, while, do, break identificadores: asociados a variables, nombres de funciones, tipos definidos por el usuario, etiquetas,... Por ejemplo: velocidad, y11, suma, _100 operadores: = * + - / == smbolos especiales: ; [ ] ( ) { } , constantes numricas: valores enteros, valores en coma flotante, etc.: 982, 0xF678, -83.2E+2,... constantes de caracteres: cadenas de caracteres, hola mundo,... Comentarios: /** abcde **/
21/11/2012 5
Administrar el archivo del programa fuente: abrirlo, leerlo, cerrarlo y gestionar posibles errores de lectura. Eliminar comentarios, espacios en blanco, tabuladores y saltos de lnea (caracteres no validos para formar un token). Incluir archivos: # include ... Expandir macros y funciones inline: # define ... Contabilizar lneas y columnas para emitir mensajes de error. Reconocer las marcas de fin de archivo. Insertar los identificadores en la Tabla de Smbolos. Reconocer errores lxicos.
21/11/2012 6
Otras funciones del Analizador Lxico
Token, patrones y lexemas

Token: Es una unidad lxica indivisible con significado nico dentro del lenguaje. Por ejemplo: Identificadores, Enteros, palabras reservadas, espacios en blanco, Patrn: regla que describe cmo se forma un token. Los patrones se especifican mediante expresiones regulares Lexema: Cadena de caracteres del programa fuente que concuerda con un patrn. Atributos: Informacin adicional asociada a un token y que ser utilizada en el anlisis semntico y/o en la etapa de sntesis
21/11/2012 7
Token, patrones y lexemas

Token
cte_entera pr_if pr_do op_div op_mayig
Patrn
Digito seguido de mas dgitos Letra i seguida de letra f Letra d seguida de letra o Smbolo / Smbolo > seguido de =
Lexemas
total, b52, i 1492, 1, 512 if do / >=
identificador Letra seguida de letras o dgitos
cte_cadena
Smbolos entre comillas
hola!!!
21/11/2012
Funcionamiento del Scanner
21/11/2012
Funcionamiento del Scanner

Ejemplo:
TK_FLOAT TK_ID(match0) TK_PARIZQ TK_CHAR TK_ID(s) TK_PARDER TK_LLAVIZQ TK_IF TK_PARIZQ TK_NOT TK_ID(strncmp) TK_PARIZQ TK_ID(s) TK_COMA TK_STRING(0.0) TK_COMA TK_NUM(3) TK_PARDER TK_PARDER TK_RETURN TK_REAL(0.0) TK_PYC TK_LLAVDER
float match0(char s) /* find a zero */ {if (!strncmp(s, "0.0", 3)) return 0.0; }
21/11/2012
10
Diseo del Analizador Lxico

1) Definir el conjunto de tokens que reconocer el Analizador. 2) Elaborar la tabla de tokens, detallando: token, cdigo asignado al token y patrn (ER)
3) Construir un AFD para la ER asociada a cada token.

4) Combinar todos los AFDs en un nico AFD mnimo equivalente cuyo DT tiene las siguientes diferencias: El DT debe leer caracteres hasta reconocer un token, y luego retornar el token que ha reconocido El DT no puede tener estados de absorcin.
21/11/2012 11

De los estados finales no deben salir transiciones. En el caso de los tokens no especficos, se debe leer hasta hallar un smbolo que no forma parte del patrn. En este ltimo estado se debe devolver al buffer de entrada el smbolo ledo (que puede ser parte del siguiente token), marcando el estado con un asterisco.
0..9 0..9 0 1 0 0..9 1 DT
12
0..9 otro 2 * retornar Entero
AFD
21/11/2012

Ejemplo:
retornar 2 retornar 2 retornar 3
retornar 1 TOKEN CODIGO ENTERO 1 SUMA 2 2INCREMENTO 3

21/11/2012
E.R. -?[0-9]+ + +++

13

retornar 2
retornar 1 retornar 3
E.R. [0-9]+ [0-9]+ . [0-9]+ [a-zA-Z][a-zA-Z0-9]* + * / ( )
14
retornar 4
21/11/2012
TOKEN CODIGO retornar 5 ENTERO 1 2 retornar 6 REAL ID 3 4 retornar 7 SUMA RESTA 5 6 retornar 8 MULTIPLICACION DIVISION 7 8 retornar 9 PARIZQ PARDER 9
Implementacin del Analizador Lxico

Aspectos a considerar para la implementacin: Estrategias de implementacin Prioridad de tokens Reconocimiento de palabras reservadas Gestin de errores Estrategias de implementacin: Programa simulador de la Tabla de Transiciones Programa simulador del Diagrama de Transiciones Utilizacin de generadores de analizadores lxicos
21/11/2012 15

Programa simulador de la Tabla de Transiciones Inicializa una variable con el estado inicial y actualiza esta variable con la informacin de la tabla cada vez que se lee un smbolo de entrada, hasta que se lee el ultimo carcter del lexema que est siendo analizado.
21/11/2012
16
21/11/2012
17
Programa simulador del Diagrama de Transiciones Traduccin del DT a pseudo cdigo (los estados del AFD estn implcitos en el algoritmo). Utiliza una variable para almacenar el estado actual y una estructura tipo case doble anidada. El primer case comprueba el estado actual y el siguiente el carcter en la entrada. Las transiciones asocian un nuevo valor a la variable estado y avanza en la entrada. El cdigo es largo y difcil de mantener si se introducen nuevos caracteres en el alfabeto o nuevos estados.
18
21/11/2012

Estado = 0; Repite Leer siguiente smbolo de la palabra; Case estado is 1 : if smbolo == + then estado = 3; elsif smbolo = - then estado = 2; elsif smbolo = digito then estado = 2; else rutine _ error; 2 : devolver smbolo; retornar SUMA; 3 : if smbolo == + then estado = 5; elsif smbolo = - then estado = 4; elsif smbolo = digito then estado = 4; else rutine _ error; fin del case; hasta fin de cadena;
21/11/2012 19

Generadores de Analizadores Lxicos
Son programas que generan el analizador lxico escrito en un lenguaje de programacin especifico, a partir de las expresiones regulares de los tokens y las acciones asociadas para cada expresin regular.
21/11/2012
20

Generadores de Analizadores Lxicos
21/11/2012
21

Prioridad de tokens Reconocer el token asociado al lexema ms largo Por ejemplo: DO / DOT, el generador se quedara con el ms largo (DOT) como identificador. > / >= En generadores automticos Anteponer el patrn para el token ms largo Despus el ms corto El lexema asociar al que est primero
21/11/2012 22

Reconocimiento de Palabras Reservadas
Incluir todas las PR en una tabla, y cuando el analizador lxico reconozca un identificador, comprobar si es una PR: Si lo es, pasar al Ana. Sintctico el cdigo asociado a la PR. Si no lo es, es un ID, luego insertar en la TS en caso de que no est en ella, pasando al analizador sintctico el token identificador y como atributo su direccin en la TS.
21/11/2012
23

a..z,A..Z,0..9 otro a..z, A..Z 0..9 0..9 0..9 + retornar 6 : = otro
21/11/2012
* retornar EsReservada(lexema)
* retornar 2 0..9 otro otro 0..9 otro
* retornar 3
** retornar 2
TOKEN ID ENTERO REAL PR_WHILE PR_WHEN SUMA RESTA DOSPTOS OP_ASIG CODIGO 1 2 3 4 5 6 7 8 9 E.R. [a-zA-Z][a-zA-Z0-9]* -?[0-9]+ -?[0-9]+ . [0-9]+ while when + > := 24
otro
* retornar 7
retornar 9
* retornar 8

Otra opcin es inicializar la TS con las PR (en orden alfabtico para facilitar la bsqueda). Cuando se encuentre un identificador se busca en la TS. SI lo encuentra en la zona reservada para ellas ENTONCES es una palabra reservada; SINO, ser un identificador, que, como tal, ser aadido a la TS.
21/11/2012
25

Gestin de errores lxicos Un error lxico se detecta cuando una cadena de caracteres no concuerda con ningn patrn. Errores tpicos: Utilizar caracteres que no pertenecen al alfabeto del lenguaje. Escribir mal una palabra. Acciones de recuperacin: Rechazar los caracteres ledos (lexema) y volver al estado inicial o al estado final anterior si existe.
21/11/2012 26

Modo Pnico: ignorar los caracteres siguientes hasta leer uno que permita una transicin desde el estado actual. Acciones de recuperacin inteligente: Borrar un carcter extrao. Insertar un carcter que falta. Reemplazar un carcter incorrecto. Intercambiar dos caracteres adyacentes.
21/11/2012 27

Analisis Lexico

Cargado por

Copyright:

Formatos disponibles

Analisis Lexico

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Analisis Lexico

Cargado por

Copyright:

Formatos disponibles

ANLISIS LXICO

Ing. de Computacin y Sistemas Autmatas y Compiladores Ing. Carlos Gaytn Toledo

Otras funciones del Analizador Lxico

Token, patrones y lexemas

Token, patrones y lexemas

identificador Letra seguida de letras o dgitos

Smbolos entre comillas

Funcionamiento del Scanner

Funcionamiento del Scanner

Diseo del Analizador Lxico

3) Construir un AFD para la ER asociada a cada token.

Diseo del Analizador Lxico

0..9 otro 2 * retornar Entero

Diseo del Analizador Lxico

retornar 1 TOKEN CODIGO ENTERO 1 SUMA 2 2INCREMENTO 3

E.R. -?[0-9]+ + +++

Diseo del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

* retornar 2 0..9 otro otro 0..9 otro

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

Implementacin del Analizador Lxico

También podría gustarte