UNIDAD III
Analisis de Lexico
3.1 Analizador de Lexico
La tarea del análisis de léxico es “reconocer símbolos” en un flujo de caracteres y presentarlos en una
representación mas util para el análisis sintáctico.
Un analizador de lexico lee el programa fuente carácter por carácter y lo descompone en símbolos
basicos llamados TOKENS.
El analizador de lexico trata por ejemplo de detectar si los caracteres leidos corresponden a una
palabra reservada o un identificador, o si es una constante numerica o literal, o si se trata de algun
operador, etc.
Programa fuente
como un flujo de
caracteres
Analizador
De léxico
Flujo de símbolos
(tokens)
Analizador
Sintáctico
Por ejemplo, un programa fuente como el siguiente:
VAR i:INTEGER;
BEGIN
i :=0;
END
En realidad es leido como un flujo de caracteres
V A R i : I N T E G E R ; \n ......
Al leer el programa fuente carácter por carácter ¿ Cómo reconocer cada componente del lenguaje ?, ¿ Cómo
saber cuándo es una palabra reservada o un identificador o una cantidad numerica ?
Para diseñar un analizador de léxico se requiere de:
1) Un método para describir los tokens ( expresiones regulares )
2) Un mecanismo para reconocer los tokens ( autómatas )
3) Un mecanismo para realizar acciones sobre los tokens reconocidos, por ejemplo generar una salida,
poner su valor en tablas, etc.
Los analizadores léxicos deben reconocer componentes léxicos (tokens) y estos componentes forman parte de
un lenguaje regular.
Definiciones
Token o componente léxico: Esos son símbolos que se tratan como símbolos terminales de la gramática del
lenguaje fuente. Se consideran componentes léxicos: palabras reservadas, operadores, identificadores,
constantes numericas, cadenas literales y signos de puntuación como paréntesis y punto y coma.
Lexema: Es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un
componente léxico.
Patrón: Es una regla que describe el conjunto de lexemas que puede representar a un determinado componente
léxico en los programas fuentes.
Componente léxico
(Token) Lexemas de ejemplo Descripción de los lexemas
( Patrón ) Const Const Const If If If Oprel <,<=,=,>,=> < ó <= ó = ó > ó => Id PI, cuenta, d2, num1 Letra seguida de letras y dígitos Num 0, 64, 1234 Cualquier constante numérica entera. num.num 0.234, 3.1415, 134.00 Cualquier constante numerica real. Literal “hola muchachas” Cualquier carácter entre comillas ” ”,
excepto “
3.2 Introduccion a los Autómatas Finitos y Expresiones Regulares
Expresiones Regulares
• Para describir con precisión los patrones de componentes léxicos complejos tal como identificadores,
palabras reservadas, constantes numericas o literales, etc. se usa la notación de expresiones regulares.
• Las expresiones regulares son una forma compacta de representar un lenguaje regular producido por una
gramatica regular o gramatica tipo 3.
Tip: Las gramaticas Tipo 2 ( o libres de contexto ) son adecuadas para denotar la secuencia correcta de
tokens de una frase o sentencia. En cambio las gramáticas Tipo 3 ( o regulares ) son adecuadas para
denotar la estructura de cada token.
• Una expresión regular se construye a partir de expresiones regulares más simples.
• Cada expresión regular “r” representa un token.
• Una expresión regular hace uso generalmente de tres operadores:
a) concatenación: representado por “.” o nada.
b) disyunción: “|” o “+”
c) cerradura transitiva o simplemente cerradura: ( )* o { }
Definición de cerradura: Sea A un alfabeto, si utilizamos AA=A
2 para designar todas las cadenas de longitud
2 sobre el alfabeto A. AAA = A2A =A
3 para designar las cadenas de longitud 3 en A y en general:
A . A . A …… A = An-1
A
para designar todas las cadenas de longitud n sobre el alfabeto A, entonces la cerradura positiva de A denota
A+, se define como:
∞
A+
= AUA2
UA 3
U …UAn
= UAi
i=1
Para complementar, la cadena vacía se combina con A+
para formar la cerradura transitiva de A,
denotada por A* y definida como:
A* = U A1
UA2
UA3…UA
n = e U A
+
Ejemplo de cerradura: Considere el conjunto de cadenas A* que puede ser generadas del alfabeto A={x,y},
algunos subconjuntos de A* serian:
A2
= {“xx”, “xy”, “yx”, “yy”}
A3
= {“xxx”, “xyx”, “xxy”, “xyy”, “yxx”, “yxy”, “yyx”, “yyy”}
Reglas para expresiones regulares sobre un alfabeto ∑
Expresión Regular Lenguaje regular que denota
{ € } Conjunto que contiene solo a la cadena vacía donde VT { α } Conjunto de un solo símbolo: (e1)|(e2) siendo e1 y e2 son ER L1 U L2 (e1)|(e2) siendo e1 y e2 son ER L1 L2 (e1)* o {e1} L1*
Ejemplo: Considere el alfabeto ∑ = { 0, 1 }
Expresión Regular Lenguaje que denota Ejemplos de símbolos 1) 110 L{110} 110 no más 2) 0|1 L{0,1} 0, 1 3) (1)* ó 1* L{1
i |i=0,1,2,..} , 1,11,111,1111..2
4) (0|1)(0|1) o bien 00|01|10|11 L{00,01,10,11} 00,01,10,11 5) (0|1)* L{ x | x {0,1}* } , 011, 00, 11, 000, 111, 01, 10,
101001 6) (0)* (1)* L{ 0
m 1
n| m,n>=0} , 01, 0011, 000, 111….infinito
Reconocedor
Definiciones regulares
Si es un alfabeto de símbolos básicos, entonces una definición regular es una secuencia de definiciones de la
forma:
d1 r1
d2 r2
……
dn rn
donde:
di es un nombre distintivo, ri es una expresión regular sobre símbolos de ∑ U { di,
d2,…,dn}
Ejemplo: Definición regular para denotar a los identificadores
Letra -> a|b|c|d|…|z|A|B|…|Z
Digito -> 0|1|2|3|4|5|9
Id -> letra ( letra | digito )*
La definición regular anterior es mas compacta que utilizar la gramática regular equivalente siguiente:
I -> L
I -> LA
A -> LA
A -> DA
A -> L
A -> D
L -> a|b|c|…A|B|C|Z
D -> 0|1|2|3|..|9
Autómatas (Reconocedores)
Autómata o reconocedor, también llamado frecuentemente maquina lógica:
1.- Es un modelo formal.
2.- Puede utilizar una notación grafica en forma de diagrama de estados.
3.- Se utilizan para reconocer cadenas o símbolos de un lenguaje.
Cadena Si pertenece al lenguaje (Lenguaje Regular)
No pertenece al lenguaje
Tipos de autómatas:
1. Maquina de Turing:
Es el reconocedor de lenguaje producido por una gramática tipo 0.
2. Autómata lineal restringido:
Es el reconocedor del lenguaje producido por una gramática tipo 1.
3. Autómata de pila (Push Down Autómata):
Es el reconocedor del lenguaje producido por una gramática tipo 2.
4. Autómata finito:
Es el reconocedor del lenguaje producido por una gramática tipo 3.
Automata finito
Un autómata finito consiste de un conjunto finito de estados y un conjunto de transiciones de estado a estado,
que ocurren bajo una entrada de símbolos seleccionados de un alfabeto , para cada símbolo de entrada hay
una transición a otro estado o posiblemente al mismo.
Definición formal:
M = < Q, ∑, γ , q0, F >
donde:
Q = Conjunto finito no vació de estados
∑ = Conjunto de símbolos de entrada (alfabeto)
γ = Función de transición
q0 ε Q = Estado inicial
F incluido en Q = Conjunto de estados finales
• El autómata finito lee los símbolos secuencialmente de izquierda a derecha.
• Inicialmente se parte de q0.
• Una cadena se dice que es aceptada por M si existe alguna (q0 ,W) = P para P ε F.
• El conjunto de cadenas aceptadas por M denotada por L (M) es:
L (M)= {W | γ ( q , w) ε F y W ε ∑ * }
• Cualquier conjunto de cadenas aceptadas por un autómata finito se dice que es regular.
Ejemplo de un Autómata Finito: Sea
M = < Q, ∑, γ , qo, F>
donde: Q = { q0, q1, q2, q3 }
∑ = {0,1}
Funciones:
γ (q0,0)=q2
γ (q1,0)=q3
γ (q2,0)=q0
γ (q3,0)=q1
γ (q0,1)=q1
γ (q1,1)=q0
γ (q2,1)=q3
γ (q3,1)=q2
F = {q0}
El lenguaje regular reconocido por el automata finito M denotador por L(M) es :
L(M)={ ( 0 | 1 )* | el numero de 0‟s y 1‟s es par }
Ejemplo: Verificar si la cadena 110101 pertenece al lenguaje regular reconocido por el automata M
anterior.
Entrada
1 1 0 1 0 1
Estado actual del reconocedor
q0 γ (q0,1)=q1
q1 γ (q1,1)=q0
q0 γ (q0,0)=q2
q2 γ (q2,1)=q3
q3 γ (q3,0)=q1
q1 γ (q1,1)=q0
q0 Estado final por lo tanto la cadena es valida
Autómata finito grafico (Diagramas de transición)
Para representar el comportamiento de un analizador lexicografico podemos hacerlo mediante un diagrama que
se construye bajo las siguientes reglas:
1.- Cada miembro de Q se representa por un círculo etiquetado con el estado en cuestión, por ejemplo:
q3.
2.- Cada uno de las funciones de movimiento se representa con una flecha que va del estado izquierdo
al estado derecho de la función y la flecha es etiquetada con el símbolo de entrada por ejemplo: (q3,
a ) = q1
a
q3 q1
3.- Los estados finales se marcan generalmente con doble círculo.
4.-Al estado inicial se le distingue con una flecha que no sale de ningún otro círculo.
q0
Ejemplo: Trazar el diagrama de transiciones para las siguientes funciones de transición:
γ (q0,a)=q3
γ (q3,b)=q4
γ (q4,a)=q0
a b
a q0 q3
a b
q4
Diagramas de transición de expresiones regulares primitivas
Expresión Regular Diagrama
0
a
a|b
0 a
1
a
0 1
b
a b 0 1 2
a* 0 a
Ejemplo: Sea la expresión regular ( a | b )* abb que representa a las cadenas formadas por
ai
y bj
donde i, j => 0 y estan terminadas en abb
si la descomponemos en las sub-expresiones regulares R1 y R2 tal que
R1 = ( a | b )* R2 = abb
Para R1 para R2 Concatenandolos
0 a a a b a ε a b b 0 1 2 3 4
b
b
Cadenas generadas:
1) abb
2) aaabb
3) bbbabb
4) ababababb
etc
Tipos de autómatas finitos
= Autómata Finito No-Deterministico (AFN)
= Autómata Finito Deterministico ( AFD )
• Autómata Finito No Deterministico:
1. Un AFN tiene transiciones etiquetadas con cadena vacía ( ) o con un simbolo de entrada.
2. Un mismo carácter puede etiquetar dos o mas transiciones.
3. Tiene un estado inicial y puede tener uno o mas estados finales.
4. No es facil de simular con software debido a la ambigüedad presentada por la situación de que de
un estado pueden salir dos o mas transiciones originadas por el mismo símbolo de entrada.
• Autómata Finito Deterministico:
1. Un AFD no tiene transiciones vacías.
2. Para cada estado S y un símbolo de entrada α existe a lo mas una flecha etiquetada con α de
la siguiente manera: α
S
NOTA: Se puede convertir un AFN a un AFD mediante un algoritmo de transformación.
Ejemplo de implementación de un analizador de lexico para identificadores
El automata finito grafico que define a los identificadores es:
0 Letra
Letra o digito
1 Delimitador 2
Se pueden construir rutinas que ejecuten funciones utiles:
Getchar ( ) Lee un carácter y avanza un carácter en el buffer.
Letra ( C ) True si C una letra.
Digito ( C ) Trae si C es digito.
Delimitador ( C ) True si es delimitador.
Retroceder ( C ) Regresa el apuntador a un carácter (el correspondiente al delimitador ya que este
no forma parte del identificador ).
Fallo ( ) Regresa el apuntador e inicia el siguiente autómata.
Insertar ( ) Mete el identificador a la tabla de símbolos y regresa la posición dentro de la tabla.
Return ( ) Regresa id que es el token para un identificador y el apuntador a la tabla de
símbolos.
El pseudocodigo para cada estado del automata finito grafico anterior seria:
Estado 0: c := Getchar ( );
IF Letra ( c ) THEN GOTO ESTADO 1 ELSE FALLO ( );
Estado 1: c := Getchar ();
If Letra ( c ) OR Digito ( c ) THEN
GOTO ESTADO 1
ELSE
IF Delimitador ( c) THEN
GOTO ESTADO 2
ELSE FALLO ();
Estado 2: RETROCEDER ();
RETURN ( id, insertar ( ) )
6
ε
ε
ε
ε
ε
ε
ε
ε
ε
ε
ε
ε
Otro ejemplo: Considerar la sentencia IF-THEN-ELSE soportada en muchos lenguajes de programacion
IF <expr> oprel <expr> THEN BEGIN <acción> END ELSE BEGIN <acción> END
Las expresiones regulares para los tokens de esta sentencia son:
PalabraReservada = BEGIN | END | IF | THEN | ELSE
Identificador = Letra ( Letra | Digito )*
NumEntero = Digito+
Oprel = > | < | = | >= | <= | <>
Letra = a|b|c|…|A|B|C|..|Z
Digito = 0|1|2|….|9
Los autómatas graficos individuales serian:
B E G I N
0ε 1 2 3 4 5
E N D
7 8 9 10
I F 11 12 13
RETURN ( „BEGIN‟ )
RETURN ( „END‟ )
RETURN ( „IF‟ )
14 T 15
H
19 E
20 L
Letra
E N 16 17 18
S E
21 22 23
RETURN ( „THEN‟ )
RETURN ( „ELSE‟ )
RETURN ( „id‟, insertar ( ) ) 24 25 Letra o Digito
Digit
26 27
<
28 29
=
Digito RETURN ( „num‟, insertar () )
RETURN ( „oprel‟ )
RETURN ( „oprel‟ )
30 < 31
32
=
33 34
RETURN ( „oprel‟ )
35 <
38
36
> 37
>
39
RETURN ( „oprel‟ )
RETURN ( „oprel‟ )
RETURN ( „oprel‟ ) =
40 > 41 42
Este analizador de lexico estaria formado por el codigo que implementa cada uno de los autómatas
anteriores.
Cuando un flujo de caracteres de entrada empata con uno de los autómatas entonces se devuelve su
Token correspondiente.
Si ocurre que los caracteres de entrada no empatan con ningun automata significa un error de lexico,
es decir, el carácter de entrada es desconocido para el lenguaje.
3.3 Manejo de localidades temporales de memoria ( buffers )
Buffers de Entrada
Buffer del programa fuente Analizador
De léxico
Buffer de tokens
Buffer de lexemas
Analizador Sintáctico
1. El buffer del programa fuente se implementa como una simple cadena o String.
2. El procesamiento de buffer del programa es carácter por carácter.
3. Los buffers de tokens y lexemas sirven como buffers de entrada al análisis sintáctico, en la practica se
implementan como un solo buffer.
NOTA: Generalmente el termino “Buffer de Entrada” se refiere al buffer que entra al analizador sintactico.
4. Tres datos que puede mantener cada localidad del Buffer de Entrada serian:
1. Token
2. Lexema
3. Entrada o apuntador a la tabla de símbolos
Esquematicamente:
Complex Lexema Entrada
Begin Begin 0 id Num1 1 num S 2 Oparit + 0 literal “hola” 3 End End 0 If If 0 Else Else 0 … …
5. El Buffer de Entrada se implementa mediante una estructura de datos u objetos, con las siguientes
operaciones básicas:
1. Inicializar ( ) elimina toda la información del buffer y pone el puntero del buffer en la
localidad inicial. 2. Insertar ( t, l, e ) inserta una nueva línea en el buffer con token t , lexema l y un
apuntador a la tabla de símbolos e . 3. Siguiente ( ) avanza el puntero del buffer una localidad. 4. Obt_elemento ( x ) devuelve el elemento ubicado en la localidad x. 5. reestablecer ( ) mueve el puntero del buffer a la primera localidad.
Complex Lexema Entrada Begin Begin 0 id Num1 1 num S 2 Oparit + 0 literal “hola” 3 End End 0 If If 0 Else Else 0 $ $ 0
Modelo de clases para una implementacion de Buffer de Entrada
TBufferEnt
1 *
TLinea_BE
- arrBuffer [ MAXBE ] :TLinea_BE + preAnalisis :TLinea_BE - intPtr : entero
+ complex : cadena + lexema : cadena + entrada : entero
+ inicializar ()
+ insertar ( TLinea_BE L) : entero + siguiente () + obt_elemento (entero e) : TLinea_BE + reestablecer ()
¿Como funciona un objeto de la clase TBufferEnt ?
Ptr
preAnalisis
Begin Begin 0
El símbolo $ es una marca de terminacion del buffer.
Inicialmente el buffer esta vacio y solo tiene el símbolo $ en la primer localidad, el indice Ptr se coloca
en la posición inicial.
Los símbolos se van insertando al buffer consecutivamente, desplazando siempre a $ al final del buffer.
El preAnalisis mantiene una copia de la localidad apuntada por Ptr. Conforme Ptr se mueva de
localidad preAnalisis toma los valores de esa localidad.
Código ejemplo de implementación del Buffer de Entrada
class TLinea_BE { public:
AnsiString complex; AnsiString lexema; int entrada; TLinea_BE { lexema = ””; complex = ”” ; entrada = 0 ; }
};
class TBufferEnt {
TLinea_BE arrBuffer [MAXBE]; int intPtr;
public:
};
TLinea_BE preAnalisis; void reestablecer (); void inicializar (); void siguiente (); int inserter ( TLinea_BE &L); TLinea_BE obt_elemento (int e);
3.4 Creacion de tablas de simbolos
Una función esencial de un compilador es registrar los identificadores de usuario (nombres de variables, de
funciones, de tipos, etc.) utilizados en el programa fuente y reunir información sobre los distintos atributos de
cada identificador. Estos atributos pueden proporcionar información sobre la memoria asignada a un
identificador, la dirección de memoria en que se almacenará en tiempo de ejecución, su tipo, su ámbito (la parte
del programa donde es visible), etc.
La tabla de símbolos es un componente importante del compilador. Mediante el eso de esta tabla el compilador
registra y lleva un control de la información acerca de todos los símbolos reconocidos y objetos que este
manejando, tales como:
tipo de dato
nombre
dimension
linea de declaracion
lineas en que se hace referencia
numero de parámetros
etc.
En general la tabla de símbolos se forma por el símbolo o nombre en cuestion y una serie de atributos.
Símbolo Atributo 1 ........ Atributo n
Tipos de Tablas de Símbolos:
de palabras reservadas
de Constantes
Pag. 39
Complex Lexema Tipo 0 1 id Num1 int 2 id promedio float 3 num 45 int 4 num.num 3.1415 float 5 literal “hola” char
de Procedimientos
El uso de diferentes tablas depende de que tan sofisticado sea el compilador.
Modelo de clases para una implementacion de Tabla de Simbolos
El siguiente modelo representa las clases para una tabla de símbolos para identificadores y constantes.
La tabla mantiene solo un atributo llamado “tipo”, usado para registrar el tipo de dato de cada identificador
y constante.
TTablaSimb
1 *
TLinea_TS
- arrTabla [ MAXTS ] :TLinea_TS - intInd : entero
+ complex : cadena + lexema : cadena + tipo : cadena
+ inicializar () + insertar ( TLinea_TS L ) : entero + obt_elemento (entero e) : TLinea_TS + anadeTipo ( entero p, cadena t ) + buscaTipo ( entero p ) : cadena + buscar ( cadena lex ) : entero
¿Como funciona un objeto de la clase TTablaSimb ?
Ind
La entrada 0 de la tabla de símbolos se reserva, no se usa.
Ind es un indice al ultimo elemento insertado.
La operación anadeTipo ( p, t ) va a la localidad p y llena la columna TIPO con el valor t.
La operación buscaTipo ( p ) va a la localidad p y devuelve el valor de la columna TIPO.
La operación buscar ( lex ) hace una busqueda sobre la columna LEXEMA buscando el valor lex, si lex
no se encuentra devuelve 0.