7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 1/26
qwertyuiopasdfghjklzxcvbnmqw
ertyuiopasdfghjklzxcvbnmqwer
yuiopasdfghjklzxcvbnmqwertyu
opasdfghjklzxcvbnmqwertyuiopdfghjklzxcvbnmqwertyuiopasd
ghjklzxcvbnmqwertyuiopasdfgh
klzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxc
bnmqwertyuiopasdfghjklzxcvbn
mqwertyuiopasdfghjklzxcvbnmq
wertyuiopasdfghjklzxcvbnmqwe
rtyuiopasdfghjklzxcvbnmqwerty
uiopasdfghjklzxcvbnmqwertyui
pasdfghjklzxcvbnmqwertyuiopadfghjklzxcvbnmqwertyuiopasdf
hjklzxcvbnmqwertyuiopasdfghjk
zxcvbnmrtyuiopasdfghjklzxcvb
Instituto Tecnológico de
Chilpancingo
Ingeniería en SistemasComputacionales
Lenguajes y Autómatas II
Investigación: Analizadores Léxicos
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 2/26
ANÁLISIS LÉXICO
ANÁLISIS LÉXICO (SCANNER)
El analizador léxico, también conocido como scanner, lee los caracteres
uno a uno desde la entrada y va formando grupos de caracteres con
alguna relación entre sí (tokens), que constituirán la entrada para la
siguiente etapa del compilador. Cada token representa una secuencia de
caracteres que son tratados como una única entidad. Por ejemplo, en
Pascal un token es la palabra reservada BEGIN, en C: WHILE, etc.
Las tiras específicas sólo tienen tipo (lo que representan), mientras que las
tiras no específicas tienen tipo y valor. Por ejemplo, si “Contador” es un
identificador, el tipo de token será identificador y su valor será la cadena
“Contador”.
El Analizador Léxico es la etapa del compilador que va a permitir saber si
es un lenguaje de formato libre o no. Frecuentemente va unido al
analizador sintáctico en la misma pasada, funcionando entonces comouna subrutina de este último. Ya que es el que va leyendo los caracteres
del programa, ignorará aquellos elementos innecesarios para la siguiente
fase, como los tabuladores, comentarios, espacios en blanco, etc.
EL PROCESO DEL ANÁLISIS LÉXICO
El proceso de análisis léxico se refiere al trabajo que realiza el scanner con
relación al proceso de compilación. El scanner representa una interfaz
entre el programa fuente y el analizador sintáctico o parser. El scanner, a
través del examen carácter por carácter del texto, separa el programa
fuente en piezas llamadas tokens, los cuales representan los nombres de las
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 3/26
variables, operadores, etiquetas, y todo lo que comprende el programa
fuente.
El parser, usualmente genera un árbol de sintaxis del programa fuente
como ha sido definido por una gramática. Las hojas del árbol son símbolos
terminales de la gramática. Son esos símbolos terminales o tokens los que el
scanner extrae del código fuente y se los pasa al parser. Es posible para el
parser usar el conjunto de caracteres terminales del lenguaje como el
conjunto de tokens, pero ya que los tokens pueden ser definidos en
términos de gramáticas regulares más simples que en las gramáticas más
complejas utilizadas por los parsers, es deseable usar scanners. Usar solo
parsers es costoso en términos de tiempo de ejecución y requerimientos dememoria, y la complejidad y el tiempo de ejecución puede reducirse con
el uso de un scanner.
La separación entre análisis léxico (scanning) y análisis sintáctico (parsing)
puede tener también otras ventajas. El análisis léxico de caracteres
generalmente es lento en los compiladores, y separándolo del
componente de análisis semántico de la compilación, el énfasis particularpuede darse para hacer más eficiente el proceso.
Un analizador de léxico tiene como función principal el tomar secuencias
de caracteres o símbolos del alfabeto del lenguaje y ubicarlas dentro de
categorías, conocidas como unidades de léxico. Las unidades de léxico
son empleadas por el analizador gramatical para determinar si lo escrito en
el programa fuente es correcto o no gramaticalmente. Algunas de lasunidades de léxico no son empleadas por el analizador gramatical sino
que son descartadas o filtradas. Tal es el caso de los comentarios, que
documentan el programa pero que no tienen un uso gramatical, o los
espacios en blanco, que sirven para dar legibilidad a lo escrito.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 4/26
En la terminología empleada en la construcción de un analizador de léxico
se encuentran los siguientes términos.
¿QUE ES UN ANALIZADOR LÉXICO?
Se encarga de buscar los componentes léxicos (tokens En ingles) o
palabras que componen el programa fuente, según unas reglas o
patrones. La entrada del analizador léxico podemos definirla como una
secuencia de caracteres.
El analizador léxico tiene que dividir la secuencia de caracteres en
palabras con significado propio y después convertirlo a una secuencia de
terminales desde el punto de vista del analizador sintáctico, que es la
entrada del analizador sintáctico.
El analizador léxico reconoce las palabras en función de una gramática
regular de manera que sus NO TERMINALES se convierten en los elementos
de entrada de fases posteriores. En LEX, por ejemplo, esta gramática se
expresa mediante expresiones regulares.
FUNCIONES DEL ANALIZADOR LÉXICO
El analizador léxico es la primera fase de un compilador. Su principal
función consiste en leer los caracteres de entrada y elaborar como salida
una secuencia de componentes léxicos que utiliza el analizador sintáctico
para hacer el análisis. Esta interacción, suele aplicarse convirtiendo al
analizador léxico en una subrutina o corrutina del analizador sintáctico.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 5/26
Recibida la orden “Dame el siguiente componente léxico” del analizador
sintáctico, el analizador léxico lee los caracteres de entrada hasta que
pueda identificar el siguiente componente léxico.
Estos componentes léxicos representan:
palabras reservadas: if, while, do, . . .
identicadores: asociados a variables, nombres de funciones, tipos
definidos por el usuario, etiquetas,... Por ejemplo:
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” operadores: = * + - / == > < &! = . . .
símbolos especiales: ; ( ) [ ] f g ...
constantes numéricas: literales que representan valores enteros, en
coma flotante, etc, 982, 0xF678, -83.2E+2,...
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.
constantes de caracteres: literales que representan cadenas concretas
de caracteres, \hola mundo",...
Interacción de un analizador léxico con el analizador sintáctico
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 6/26
Otras funciones que realiza:
Eliminar los comentarios del programa.
Eliminar espacios en blanco, tabuladores, retorno de carro, etc, y
en general, todo aquello que carezca de significado según la
sintaxis del lenguaje.
Reconocer los identificadores de usuario, números, palabras
reservadas del lenguaje,..., y tratarlos correctamente con
respecto a la tabla de símbolos (solo en los casos que debe de
tratar con la tabla de símbolos).
Llevar la cuenta del número de línea por la que va leyendo, por si
se produce algún error, dar información sobre donde se haproducido.
Avisar de errores léxicos. Por ejemplo, si @ no pertenece al
lenguaje, avisar de un error.
Puede hacer funciones de preprocesador.
NECESIDAD DEL ANALIZADOR LÉXICO
Un tema importante es el porqué se separan los dos análisis lexicográfico y
sintáctico, en vez de realizar sólo el análisis sintáctico, del programa fuente,
cosa perfectamente posible aunque no plausible. Algunas razones de esta
separación son:
Un diseño sencillo es quizás la consideración más importante. Separar el
análisis léxico del análisis sintáctico a menudo permite simplificar una u otra
de dichas fases. El analizador léxico nos permite simplificar el analizadorsintáctico.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 7/26
Necesidad del analizador léxico
Si el sintáctico tuviera la gramática de la Opción 1 , el lexicográfico sería:
Opción 1: ( 0 | 1 | 2 | ... | 9) + NUM
(“+” | “-” | ”*“ | ”/“) OPARIT
Si en cambio el sintáctico toma la Opción 2, el lexicográfico sería:
Opción 2: ( 0 | 1 | 2 | ... | 9) + NUM
“+” MAS
“-” MENOS
“*” MULT
“/” DIV
Es más, si ni siquiera hubiera análisis léxico, el propio análisis sintáctico vería
incrementado su número de reglas:
NUM 0
| 1
| 2
| 3
....
| NUM NUM
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 8/26
VENTAJAS DE SEPARAR EL ANÁLISIS LÉXICO Y EL ANÁLISIS SINTÁCTICO:
Facilita transportabilidad del traductor (por ejemplo, si decidimos en un
momento dado cambiar las palabras reservadas begin y end de inicio y en
de bloque, por f y g, solo hay que cambiar este módulo.
Se simplifica el diseño: el analizador es un objeto con el que se interactúa
mediante ciertos métodos. Se localiza en un único modulo la lectura física
de los caracteres, por lo que facilita tratamientos especializados de E/S.
Se mejora la eficiencia del compilador. Un analizador léxico independiente
permite construir un procesador especializado y potencialmente más
eficiente para esa función.
Gran parte del tiempo se consume en leer el programa fuente y dividirlo en
componentes léxicos. Con técnicas especializadas de manejo de buffers
para la lectura de caracteres de entrada y procesamiento de
componentes léxicos se puede mejorar significativamente el rendimiento
de un compilador.
Otra razón por la que se separan los dos análisis es para que el analizador
léxico se centre en el reconocimiento de componentes básicos complejos.
COMPONENTES LÉXICOS, PATRONES, LEXEMAS
COMPONENTE LÉXICO O TOKEN
El valor asociado a una categoría o unidad de léxico. Se representa como
un número entero o una constante de un byte. Ejemplo: el token de un
identificador puede ser 1 ó id (si id fue definida como 1).
Los tokens son las unidades léxicas básicas de igual forma que las palabras
y signos de puntuación son las unidades básicas de un enunciado. Los
tokens varían del lenguaje al lenguaje e incluso de compilador a
compilador para el mismo lenguaje, la elección de los tokens es tarea del
diseñador del compilador.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 9/26
En la mayoría de lenguajes tendremos tokens para :
palabras clave: IF THEN THEN THEN = ELSE; ELSE ELSE = THEN;
operadores
identificadores
constantes (reales, enteras y de tipo carácter), strings de
caracteres y signos de puntuación
Tipos de tokens:
tiras específicas, tales como palabras reservadas (if, while, begin,
etc.), el punto y coma, la asignación, los operadores aritméticos o
lógicos, etc.tiras no específicas, como identificadores, constantes o etiquetas.
Prioridad de los tokens
Se da prioridad al token con el lexema más largo:
Si se lee “>=” y “>” se reconoce el primero.
Si el mismo lexema se puede asociar a dos tokens, estos patrones
estarán definidos en un orden determinado.
Ejemplo:
While → palabra reservada “while”
letra (letra | digito)* → identificador
Si en la entrada aparece “while”, se elegirá la palabra reservada
por estar primero.Si estas especificaciones iniciales aparecieran en orden inverso, se
reconocería un token identificador.
PATRÓN O EXPRESIÓN REGULAR
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 10/26
Definen las reglas que permiten identificar los componentes léxicos o
tokens.
LEXEMA
Es cada secuencia de caracteres concreta que encaja con un patrón, es
decir, es como una instancia de un patrón.
Ejm: 8, 23, 50 (son lexemas que encajan con el patrón ( 0 | 1 | 2 | ... | 9)
+ )
Una vez detectado que un grupo de caracteres coincide con un patrón,
se ha detectado un lexema. A continuación se le asocia un número, que
se le pasará al sintáctico, y, si es necesario, información adicional, comopuede ser una entrada en la tabla de símbolos.
La tabla de símbolos suelen ser listas encadenadas de registros con parte
variable: listas ordenadas, árboles binarios de búsqueda, tablas hash, etc.
Ejm: Hacer un analizador léxico que nos reconozca los números enteros, los
números reales y los identificadores de usuario. Vamos a hacer este
ejemplo en C.
Terminales Expresión Regular( 0 ... 9) + NUM_ENT
(0 ... 9)*. (0 ... 9) + NUM_REAL
(a ... z) (a ... z 0 ... 9) * ID
Asociado a la categoría gramatical de número entero tendremos el token
NUM_ENT que puede equivaler por ejemplo al número 280; asociado a la
categoría gramatical número real tendremos el token NUM_REAL queequivale al número 281; asociado a la categoría gramatical identificador
de usuario tendremos el token ID que equivale al número 282.
( 0 ... 9) + { return 280;}
(0 ... 9)*. (0 ... 9) + { return 281;}
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 11/26
(a ...z) (a ...z 0...9) * { return 282;}
Si tuviéramos como texto de entrada el siguiente:
95.7 99 hola
El analizador léxico intenta leer el lexema más grande; el 95 encaja con el
primer patrón, pero sigue, al encontrarse el punto, se da cuenta de que
también encaja con el segundo patrón, entonces como este es más
grande, toma la acción del segundo patrón, return NUM_REAL. El 99
coincide con el patrón NUM_ENT, y la palabra con ID. Los espacios en
blanco no coinciden con ningún patrón.
En vez de trabajar con los números 280, 281, 282, se definen
mnemotécnicos.
# define NUM_ENT 280
# define NUM_REAL 281
# define NUM_ID 282
(“ ”\t \n)(0 ... 9) + {return NUM_ENT;}
(0 ... 9) *. (0 ... 9) + {return NUM_REAL;}
(a ... z) (a ... z 0 ... 9)* {return ID;}
Las palabras que entran por el patrón (“ ”\t \n) no tienen acción
asociada, por lo que , por defecto, se consideran solo espaciadores.
Ejemplo:
Programa UNO;
Inicio
Escribe (“Hola”);
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 12/26
Fin.
Cuya tabla de tokens es la siguiente:
Programa Palabra
reservada
UNO Identificador
; Delimitador
Inicio Palabra
reservada
Escribe Palabra
reservada
( Símbolo
“Hola” Identificador
compuesto
) Símbolo
; Delimitador
Fin. Palabra
reservada
DESCRIPCIÓN DE UN ANALIZADOR LÉXICO
El análisis léxico es un análisis de los caracteres:
Parte de éstos y por medio de patrones reconoce los lexemas
Envía al analizador sintáctico el componente léxico y sus atributos
Puede hacer tareas adicionales: eliminar blancos, control líneas.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 13/26
Descripción del analizador léxico
El analizador léxico y el sintáctico forman un par productor-consumidor.
En algunas situaciones, el analizador léxico tiene que leer Algunos
caracteres por adelantado para decidir de qué token se trata.
Par Productor-Consumidor
UNIDADES DE LÉXICO
Categorías en que se clasifican las cadenas de caracteres válidos en un
lenguaje. Los caracteres válidos reciben el nombre de alfabeto. Por
ejemplo, el alfabeto de Pascal es:
A-Z, a-z, 0-9, _, =, :, ;, ,, , -, ', ", *, /, (, ), [, ], ., <, > y las unidades de léxico para
pascal son:
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 14/26
identificadores
literales numéricas
operadores aritméticos
cadenas de caracteres
separadores
operadores relacionales
operadores lógicos
comentarios
Con respecto al lenguaje para controlar al ROBOT, tenemos que sualfabeto es: n,o,r,t,e,s, ,u,i,c y las unidades de léxico son:
órdenes
(norte, sur, este, oeste, inicio)
y espacios en blanco.
EL ROL DEL ANALIZADOR LÉXICO
Aunque el analizador de léxico es la primera etapa del proceso de
compilación, no es quien lo inicia. Pudiera considerarse que el analizador
de léxico hace su procesamiento y envía sus resultados al analizador
gramatical, como secuencialmente se aprecia en el proceso de
compilación; no es así: La compilación empieza con el analizadorgramatical quien solicita un token para realizar su trabajo; el analizador de
léxico reune símbolos y envía el token correspondiente a la unidad de
léxico que conformó al analizador gramatical y espera una nueva solicitud
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 15/26
de token. Como se aprecia en la figura siguiente, el analizador de léxico
está supeditado por el analizador gramatical.
Rol del analizador léxico
Durante estas etapas se tiene comunicación con la tabla de símbolos que
concentra información de las entidades empleadas en el programa.
TRATAMIENTO DE LOS ERRORES
Un traductor debe adoptar alguna estrategia para detectar, informar y
recuperarse para seguir analizando hasta el final.
Las respuestas ante el error pueden ser:
Inaceptables: Provocadas por fallos del traductor, entrada en lazos
infinitos, producir resultados erróneos, y detectar sólo el primer error y
detenerse.
Aceptables: Evitar la avalancha de errores (mala recuperación) y,
aunque más complejo, informar y reparar el error de forma automática.
La conducta de un Analizador de Léxico es el de un Autómata finito o
“scanner”.
Detección del error: El analizador de Léxico detecta un error cuando no
existe transición desde el estado que se encuentra con el símbolo de la
entrada. El símbolo en la entrada no es el esperado.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 16/26
Los errores léxicos se detectan cuando el analizador léxico intenta
reconocer componentes léxicos y la cadena de caracteres de la entrada
no encaja con ningún patrón. Son situaciones en las que usa un carácter
invalido (@,$,",>,...), que no pertenece al vocabulario del lenguaje de
programación, al escribir mal un identificador, palabra reservada u
operador.
Errores léxicos típicos son:
nombre ilegales de identificadores: un nombre contiene caracteres
inválidos.
Números incorrectos: un numero contiene caracteres inválidos o no esta
formado correctamente, por ejemplo 3,14 en vez de 3.14 o 0.3.14.
errores de ortografía en palabras reservadas: caracteres omitidos,
adicionales o cambiados de sitio, por ejemplo la palabra while en vez
de while.
fin de archivo: se detecta un fin de archivo a la mitad de un
componente léxico.
Los errores léxicos se deben a descuidos del programador. En general, la
recuperación de errores léxicos es sencilla y siempre se traduce en la
generación de un error de sintaxis que será detectado mas tarde por el
analizador sintáctico cuando el analizador léxico devuelve un
componente léxico que el analizador sintáctico no espera en esa posición.
Los métodos de recuperación de errores léxicos se basan bien en saltarse
caracteres en la entrada hasta que un patrón se ha podido reconocer; o
bien usar otros métodos más sofisticados que incluyen la inserción, borrado,
sustitución de un carácter en la entrada o intercambio de dos caracteres
consecutivos. Una buena estrategia para la recuperación de errores
léxicos: si en el momento de detectar el error ya hemos pasado por algún
estado final ejecutamos la acción correspondiente al ultimo estado final
visitado con el lexema formado hasta que salimos de el; el resto de
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 17/26
caracteres leídos se devuelven al flujo de entrada y se vuelve al estado
inicial;
Si no hemos pasado por ningún estado final, advertimos que el carácter
encontrado no se esperaba, lo eliminamos y proseguimos con el análisis.
TRATAMIENTO DE PALABRAS RESERVADAS
Son aquellas que los lenguajes de programación “reservan” para usos
particulares.
¿Cómo diferenciarlas de los identificadores?
Resolución implícita: reconocerlas todas como identificadores,
utilizando una tabla adicional con las palabras reservadas que se
consulta para ver si el lexema reconocido es un identificador o una
palabra reservada.
Resolución explícita: se indican todas las expresiones regulares de todas
las palabras reservadas y se integran los diagramas de transiciones
resultantes de sus especificaciones léxicas en la máquina
reconocedora.
CONSTRUCCIÓN DE UN ANALIZADOR LÉXICO
Los analizadores léxicos pueden construirse:
Usando generadores de analizadores léxicos: Es la forma más sencilla
pero el código generado por el analizador léxico es más difícil de
mantener y puede resultar menos eficiente.
Escribiendo el analizador léxico en un lenguaje de alto nivel: permite
obtener analizadores léxicos con más esfuerzo que con el método
anterior pero más eficientes y sencillos de mantener.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 18/26
Escribiendo el analizador léxico en un lenguaje ensamblador: Sólo se
utiliza en casos específicos debido a su alto coste y baja portabilidad.
CONCEPTO DE EXPRESIÓN REGULAR
El objetivo de las expresiones regulares es representar todos los posibles
lenguajes definidos sobre un alfabeto , basándose en una serie de
lenguajes primitivos, y unos operadores de composición. Lenguajes
primitivos serian el lenguaje vació, el lenguaje formado por la palabra
vacía, y los lenguajes correspondientes a los distintos símbolos del alfabeto.
Los operadores de composición son la unión, la concatenación, el cierre y
los paréntesis.
DEFINICIÓN DE EXPRESIÓN REGULAR
Dado un alfabeto finito , las expresiones regulares sobre se definen de
forma recursiva por las siguientes reglas:
Las siguientes expresiones son expresiones regulares primitivas:
, con
Sean y expresiones regulares, entonces son expresiones regulares
derivadas:
+ (union)
. (o simplemente ) (concatenacion)
* (cierre) (A* repetición l|A|AA|AAA..)
()
No hay más expresiones regulares sobre que las construidas mediante
estas reglas.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 19/26
Observación: La precedencia de los operadores es la siguiente (de
mayor a menor):
( )
* cierre
. concatenación
+ unión
Ejemplo: Algunos ejemplos de expresión regular son:
(0 + 1)*01
(aa + ab + ba + bb)*
a*(a + b)(aa)*(bb)*b
OPERACIONES DE EXPRESIONES REGULARES
Selección entre alternativas. la cual se indica mediante el
metacaracter |
Concatenación. La concatenacion entre dos expresionesregulares R y S se expresa por RS.
Repetición. Se indica mediante el metacaracter *
LENGUAJE DESCRITO POR UNA EXPRESIÓN REGULAR
Sea r una expresión regular sobre . El lenguaje descrito por r, L(r), se
define recursivamente de la siguiente forma:
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 20/26
Ejemplo:
L(a*(a+b)) = L(a*)L((a+b)) = L(a)*L(a+b) = L(a)*(L(a) L(b)) =
{a}*({a}{b})
= {, a, aa, aaa,...}{a,b}
= {a, aa, ..., b, ab, aab, ...} = {an| n 1}{ an b | n 0}.
L((aa)*(bb)*b)= {a2nb2m+1 | n,m 0}.
Si = {a,b,c},entonces L(( a + b + c) )= *
L(a*(b + c))
L(0*10*)
TEOREMAS DE EQUIVALENCIA
Tal como indica su nombre, mediante expresiones regulares se pueden
representar lenguajes regulares. De hecho, la clase de lenguajes que se
pueden representar mediante una expresión regular, es equivalente a la
clase de lenguajes regulares.
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 21/26
Hasta ahora hemos visto que los lenguajes regulares pueden describirse
mediante:
Gramáticas lineales por la izquierda,
Gramáticas lineales por la derecha,
Autómatas finitos deterministas,
Autómatas finitos no deterministas.
Por tanto, deben existir algoritmos que permitan obtener un autómata o
una gramática regular a partir de una expresión regular y viceversa.
MATRICES DE TRANSICIÓN
Una matriz o tabla de transiciones es un arreglo bidimensional cuyos
elementos proporcionan el resumen de un diagrama de transiciones. Para
elaborar una tabla de transiciones, debe colocarse cada estado del
diagrama de transiciones en una fila del arreglo y cada símbolo o
categoría de símbolos con posibilidades de ocurrencia en la cadena de
entrada, en una columna. El elemento que se encuentra en la fila mcolumna n es el estado que se alcanzaría en el diagrama de transiciones al
dejar al estado m a través de un arco de etiqueta n. Al no existir algún arco
que salga del estado m, entonces la casilla correspondiente de la tabla se
marca como un estado de error. En la siguiente figura se presenta un
ejemplo de un diagrama de transiciones que representa la sintaxis para un
número de punto flotante, seguido de la tabla de transiciones
correspondiente.
Estado Dígito . E + - FDC
1 2 Error Error Error Error Error
2 2 3 5 Error Error Error
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 22/26
3 4 Error Error Error Error Error
4 4 Error 5 Error Error Aceptar
5 7 Error Error 6 6 Error
6 7 Error Error Error Error Error7 7 Error Error Error Error Aceptar
Existe también La matriz de transición de estados se creó dando valores
de estado a cada uno de los tipos de palabra y utilizando las reglas de
la gramática respecto a la relación que existe entre cada tipo de
palabra
REPRESENTACIÓN DE LOS AUTÓMATAS
Representación de un autómata
Acepta las secuencias: abc(dc)*
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 23/26
Ej. abc, abcdc, abcdcdc, abcdcdc...
AUTÓMATA FINITO DETERMINISTA
Un autómata finito determinista consiste en un dispositivo que puede estar
en un estado de entre un número finito de los mismos; uno de ellos será el
estado inicial y por lo menos uno será estado de aceptación. Tiene un flujo
de entrada por el cual llegan los símbolos de una cadena que pertenecen
a un alfabeto determinado. Se detecta el símbolo y dependiendo de este
y del estado en que se encuentre hará una transición a otro estado o
permanece en el mismo. El mecanismo de control (programa) es quedetermina cual es la transición a realizar. La palabra finito se refiere a que
hay un número finito de estados.
La palabra determinista es porque el mecanismo de control (programa) no
debe tener ambigüedades, es decir, en cada estado solo se puede dar
una y solo una (ni dos ni ninguna) transición para cada símbolo posible (en
el ejemplo anterior, la tabla de transiciones era determinista en ese caso,
no así el diagrama, aunque podría serlo como veremos mas tarde).El autómata acepta la cadena de entrada si la máquina cambia a un
estado de aceptación después de leer el último símbolo de la cadena. Si
después del último símbolo la máquina no queda en estado de
aceptación, se ha rechazado la cadena.
Si la máquina llega al final de su entrada antes de leer algún símbolo la
entrada es una cadena vacía (cadena que no contiene símbolos) y la
representaremos con . Solo aceptará si su estado inicial es deaceptación.
Un autómata finito determinista (AFD) consiste en una quíntupla (Q, , , q0,
F) donde:
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 24/26
Q es un conjunto finito de estados
es el alfabeto de la máquina
:Q x ,Q (es la función total de transición)
q0 Q es el estado inicial
F Q es el conjunto de los estados de aceptación (estados finales).
Lee los caracteres de derecha a izquierda
Para cada carácter leído, si para un a y q, p S se tiene que (q, a) =
p, significa que siempre que el automata este en el estado q y le llega el
carácter a pasará al estado p
Ejemplo:
Automata que acepta cadenas con un número par de ceros y un
numero par de unos:
AFD = {S, A, B, C}, {0,1},, Q, {Q}
M se puede definir extensivamente con:
Representación gráfica:
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 25/26
AUTÓMATA FINITO NO DETERMINISTA
La única diferencia con los AFD está en que en la transición en un estado
determinado puede haber, para un mismo símbolo, más de un arco o no
haber ninguno.
Decimos que un autómata finito no determinista acepta una cadena si es
posible que su análisis deje a la máquina en un estado de aceptación.
Decimos si es posible, pues si se toma el camino equivocado no se
aceptaría una cadena que podría ser válida (una cadena del lenguaje
aceptado por este autómata, designado por L(M).
Un autómata finito no determinista (AFN o AFND) consiste en una quíntupla:(Q, , , q0, F) donde:
Q es un conjunto finito de estados posibles del automata
es el alfabeto de la máquina
:Q x ,2Q (es la función total de transición)
q0 Q es el estado inicial
F Q es el conjunto de los estados de aceptación (estados finales).
Ejemplo:
AFND que reconoce en {a, b, c}* tales que el ultimp símbolo en la
caden de entrada aparecía también anteriormente en la cadena. En
este AFND, seria
F = {q0, q1, q2, q3, q4}, {a, ,b, c}, , q0, { q4}
7/18/2019 ANALIZADORES LÉXICOS
http://slidepdf.com/reader/full/analizadores-lexicos 26/26
Sea la entrada aca:
Concluyendo:
(q0, aca) = { q0, q1, q3} { q1, q4}
= { q0, q1, q3, q4}
Y como (q0, aca) F = {q4}, la cadena se acepta.