facultad de ingeniería de sistemas -...

Facultad de Ingeniería de Sistemas Facultad de Ingeniería de Sistemas

Lenguajes y Compiladores

Análisis Léxico

1

Análisis léxicoAnálisis léxico

� La tarea del análisis léxico es reconocer símbolosdentro de la cadena de caracteres que es el programa fuente. Una vez reconocido un símbolo válido es transformado a una representación más manejable por el parser.

Teoría Lenguajes 2

manejable por el parser.

� Esta tarea es realizada por el analizador léxico.

� Lexema o token: símbolo válido reconocido por el analizador léxico.

CaracteresPrograma fuente

tokensAnalizador léxico

Analizador sintáctico


� Funciones básicas de un léxico:� Reconocer identificadores y palabras reservadas

� Reconocer constantes numéricas y alfanuméricas

� Reconocer los comentarios

� Eliminar los blancos

Teoría Lenguajes 3

� Eliminar los blancos

� Generalmente los símbolos reconocidos por un léxico son elementos de un lenguaje regular, es decir generados por una gramática regular.


� Sea G(T, N. P, S) una gramática regularT = {a, b, c}N = { S, B, C}P = {S →→→→ Sa Bb ,

B → Cc ,

Teoría Lenguajes 4

B → Cc ,

C → a }S = { S }Se puede generar la siguiente frase:

acba


Derivaciones usadas:S →→→→ Sa

→→→→ Bba→→→→ Ccba→→→→ acba

Teoría Lenguajes 5

→→→→ acba

Para reconocer la frase hay que recorrerla de izquierda a derecha y si se llega al símbolo terminal inicial se dice que es una frase válida (fue reconocida).


a c b a

C

B C

B

S

B

S

S

Teoría Lenguajes 6

a c b a

C

B

a c b a

C

a c b a

C

*

Autómata finito determinista (FDA)Autómata finito determinista (FDA)

� Autómata: Dispositivo que acepta una entrada y genera una salida adecuada.

� Autómata Finito Determinista: Reconoce cadenas de un alfabeto para lo cual posee un conjunto finito de estados internos entre los cuales existe un estado

Teoría Lenguajes 7

estados internos entre los cuales existe un estado inicial (s0) y uno o varios estados finales.

s0

a

Estado

Cadena deentrada

s1

c

s2

b

s3

a

considerandos3 Estado final

*

Autómata finito deterministaAutómata finito determinista

� Se dice que un autómata finito es determinista si para cada par (estado, carácter) sólo existe una transición posible, es decir sólo existe un estado al cual puede cambiar.

� Los autómatas finitos también son conocidos con el

Teoría Lenguajes 8

� Los autómatas finitos también son conocidos con el nombre de aceptador de estados o reconocedor(porque toma una cadena de entrada y reconoce si pertenece o no a un cierto lenguaje)

Autómata finito deterministaAutómata finito determinista

� Formalmente se define un autómata como una quíntupla: A = (P, V, M, s0, F), donde:� P es un conjunto de estados finito y no vacío

� V es el alfabeto de entrada

� M es una función de transición de estados que

Teoría Lenguajes 9

� M es una función de transición de estados que establece una correspondencia de P x V a P

� s0 Estado inicial, con s0 ∈ P

� F conjunto de estados finales tal que F ⊂ P

Diagramas de transiciónDiagramas de transición

� También se usan diagramas con información añadida para representar autómatas finitos deterministas. Estos diagramas son grafos dirigidos conocidos con el nombre de diagramas de transición.

� Los nodos del grafo se denominan estados.

Teoría Lenguajes 10

� Los nodos del grafo se denominan estados.

� Las aristas están etiquetadas con caracteres del alfabeto y se denominan transiciones.

� Existe un estado inicial o estado de partida.� Algunos estados se denominan estados de aceptación

o estados finales.


� Este diagrama muestra que es posible la transición del estado s0 al estado s1´ si se recibe el carácter a

� También se usan Tablas de transición para

s0 s1a

óa


� También se usan Tablas de transición para representar autómatas. Consiste en un arreglo bidimensional cuyas columnas se asocian a los caracteres de entrada y las filas a los estados del autómata, el contenido del arreglo indica el estado al cual se realiza la transición.


Entrada

Esta

s2s1

a


ados

s2s1

Gramáticas regulares y autómatos finitosGramáticas regulares y autómatos finitos

� Es posible tener un autómata finito para una gramática regular.

� Para construir un autómata a partir de la gramática debemos tener en cuenta:� Cada no terminal representa un estado


� Cada no terminal representa un estado

� Cada terminal produce las transiciones

� Se crearán estados especiales (que no son no terminales):

» Uno que representa el estado inicial

» Otro que representa un estado al cual se llega sólo si se analiza una frase incorrecta

Autómata y diagrama Autómata y diagrama

a c ba

A seguir se muestra el diagrama de estados correspondiente a la gramática regular usada en el ejemplo anterior.


BCI S

E

a c b

c, b

a, b c, a

c, b

Diagrama y Tabla de transiciónDiagrama y Tabla de transición

� La tabla de transición para el diagrama sería:

ESTADO a b cI C E E

ENTRADA


I C E ES S B CB E S EC E E B

Expresiones RegularesExpresiones Regulares

� Se puede simplificar la especificación de un lenguaje regular introduciendo una “abreviatura” conocida como expresión regular.

Operación Nombre DefiniciónL ∪ M Unión L ∪ M = { s s ∈ L ó s ∈ M }


L ∪ ML M

Unión L ∪ M = { s s ∈ L ó s ∈ M }

L M Concatenación L M = { st s ∈ L y t ∈ M }L* Cerradura de Kleene

Cero o más concatenaciones∪∞ Li

I = 0

L+ Cerradura positivaUna o más concatenaciones

∪∞ Li

I = 1


� Ejemplos:� a* b* denota frases del tipo

» aaabbbbbbb

» aaaaa

» bbbb


» bbbb

» ε

� a+ b+ denota frases del tipo» aaabbbbbbb

» aaaaab

» abbbb

» ab


� (ab)*

� (a ∪ b)*

� (a b) *

� (aa *) b

a+ b


� a+ b

� Para la gramática del lenguaje G (diapositiva 4) la expresión regular correspondiente sería: acba*

� Muestre el diagrama de transición para la primera expresión regular (ab)*

Autómata no determinista (FNA)Autómata no determinista (FNA)

� Autómata no determinista es un autómata que para un par (estado, carácter) tiene más de un estado de transición y permite transiciones para la entrada vacía ε.

� Si para cada par estado actual - entrada existe mas


� Si para cada par estado actual - entrada existe mas de un estado siguiente indica que se puede elegir entre las distintas posibilidades. No existe nada que determine la elección. De ahí el nombre no determinista.

� Ejemplo:

Autómata no deterministaAutómata no determinista

a b

Q0 { Q1, Q4} { Q3}Q1 { Q1} { Q2}Q ∅ ∅

Q0

Q1Q2

b

a

a

ab


Q2 ∅ ∅Q3 ∅ ∅Q4 ∅ { Q4} Q3 Q4

b

b


� Si M es un AFN el lenguaje aceptado por M se define como:

L(M) = {w | w es una cadena aceptada por M}� Para determinar si w ∈ L(M) debemos recorrer el

diagrama de transición correspondiente y encontrar


diagrama de transición correspondiente y encontrar un camino que termine en un estado de aceptación luego de haber consumido toda la cadena. En la búsqueda se elige el camino de forma no determinista.


� Para decir que w ∉ L(M) se debe agotar todas las posibles formas de recorrer el diagrama para esa cadena. En algunos casos se recorrerán caminos con una elección no correcta del estado siguiente, lo que desencadenará en un estado no válido. En esta situación será necesario retroceder y retomar la


desencadenará en un estado no válido. En esta situación será necesario retroceder y retomar la búsqueda del camino eligiendo otro estado.

� En términos de programación esto no es eficiente por tanto trataremos de usar AFD o transformar los AFN en AFD.

Análisis LéxicoAnálisis Léxico

� Lee una cadena de entrada y genera una secuencia de componentes léxicos.

� Debe eliminar los caracteres en blanco y comentarios

� Cada componente léxico está bien definido y tiene un significado propio.


significado propio.

� Se debe distinguir entre componente léxico y la cadena que lo representa. Para cada cadena (palabra) el léxico debe determinar de que componente léxico (token) se trata. Generalmente los tokens se devuelven codificados.

Análisis LéxicoAnálisis Léxico

Token Ejemplo DescripciónPL Var Var Palabra reservada VarPL Case Case Palabra reservada CaseNum 4.25, 9 Constante numéricaString 'Título' Constante literalSE > Símbolo especialId Cont, temp, I Identificadores


Id Cont, temp, I Identificadores

El léxico debe eliminar todos los “adornos” del programa fuente (comentarios, blancos).Separa cadenas y las relaciona con tokens.Se puede usar diagramas de transición para reconocer las cadenas válidas.

Aspectos de ImplantaciónAspectos de Implantación

� El léxico entrega al sintáctico un token codificado.

� Generalmente el token consta de dos partes

Código: indica si el tipo de token (identificador,

Código Atributo asociado


� Código: indica si el tipo de token (identificador, palabra reservada, constante, etc).

� Atributos. Contiene códigos o cadenas que complementan la información del código. Su contenido depende del tipo de token.


Token Código AtributoPalabra reservada 1 Código de la palabra reservadaIdentificador 2 Cadena del identificadorSímbolo especial 3 Código del símbolo especialConstante numérica 4 Cadena de la constanteConstante alfanumérica 5 Cadena de la constante


La tabla mostrada es un ejemplo de codificación de tokensen donde cada palabra reservada/símbolo especial tiene el mismo código y en el atributo asociado se especifica de que palabra/símbolo se trata.Otra forma de codificar es asignar a cada palabra/símbolo un código diferente en cuyo caso no se necesitará del atributo.


� El léxico se puede implantar con diagramas/tablas de transición. Se deben entonces definir las gramáticas regulares para cada tipo de componente léxico y construir los diagramas/tablas de transición. Estos diagramas de estado se pueden unir en un único diagrama que reconozca todos los componentes


diagramas de estado se pueden unir en un único diagrama que reconozca todos los componentes léxicos, incluyendo comentarios.

� Es importante diseñar los componentes léxicos de manera tal que facilite su implantación y evitar reglas tan flexibles que pueden complicar la realización del léxico (por ejemplo Fortran IV).


� Tratamiento de comentarios: en algunos lenguajes los comentarios pueden ser anidados, por ejemplo:{este es el primer comentario

{este es el segundo comentario{y este es el último comentario}


{y este es el último comentario}}

}� Reconocimiento de componentes formados por dos

caracteres como := >= == etc.� Tratamiento de cadenas que abren/cierran con un

carácter especial.

Errores del léxicoErrores del léxico

� Son pocos los errores que se pueden detectar en el análisis léxico� Carácter que no pertenece al alfabeto. En este caso la

recuperación de error más usada es conocida con el nombre de “Panic Mode” (modo de pánico): se busca un carácter válido o un componente léxico válido.


nombre de “Panic Mode” (modo de pánico): se busca un carácter válido o un componente léxico válido.

� No hay más símbolos en la entrada por tanto no es posible seguir entregando componentes léxico

Casos Especiales Casos Especiales

� Se abre una cadena (‘), se encuentra el fin del archivo y no hay cierra cadena.

� Comentarios que inician pero no terminan

� Comentarios anidados


facultad de ingeniería de sistemas -...

Documents