Un analizador léxico o analizador lexicográfico (en inglés scanner) es un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción, siendo la entrada para el analizador sintáctico (en inglés parser).
Interesante video sobre el análisis léxico
2.1 Función del análisis lexicográfico
El analizador léxico es la primera fase el compilador. Función principal del analizador léxico: 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 iteración se esquematiza como sigue:
Funciones secundarias: Como el analizador léxico es la parte del compilador que lee el texto fuente, también realiza las siguientes funciones secundarias:
- Eliminar del programa fuente comentarios y espacios en blanco (caracteres de espacio en blanco, caracteres TAB, caracteres de nueva línea).
- Relacionar los mensajes de error con el lenguaje fuente.
Razones para dividir la fase de análisis de la compilación en análisis léxico y análisis sintáctico
- Permite un diseño más sencillo. Esta división permite simplificar una u otra de dichas fases. Por ejemplo, el análisis sintáctico es más complejo si considera espacios en blanco o los comentarios.
- Se mejora la eficiencia del compilador. Utilizando técnicas independientes para el análisis léxico, el programa fuente puede leer y dividir en componentes léxicos más especializados.
- Se mejora la transportabilidad del compilador. Los símbolos especiales o estándar del programa fuente se pueden aislar en el analizador léxico, permitiendo que el programa fuente pueda pasar de una fase a otra.
2.2 Lexemas, expresiones regulares y tokens
Componente léxico (token) Son las unidades lógicas que genera el analizador léxico. Formar caracteres en tokens es muy parecido a formar palabras en un lenguaje natural. Es el conjunto de cadenas de entrada que produce como salida el mismo componente léxico. Cada token es una secuencia de caracteres que representa una unidad de información en el programa fuente. Los componentes léxicos más comunes son los siguientes:
1.- palabras clave o reservadas
2.- operadores aritméticos
3.- operadores relacionales
4.- operadores lógicos
5.- operador de asignación
6.- identificadores
7.- constantes
8.- cadenas
9.- literales
Sea L el conjunto {A, B, C, D, ...,Z, a, b, c, d,...,z} y D el conjunto {0, 1, 2, ..., 9}. Algunos ejemplos de nuevos lenguajes creados a partir de L y D:
Identificador. (Letra seguida de letras y dígitos). Se puede definir a partir de dos símbolos: letra y dígito.
letra (letra|dígito)*
Nota: Una expresión regular se construye a partir de expresiones regulares más simples, hasta llegar a símbolos del alfabeto:
Constante entera
(sin signo) digito+ (con signo) (+|-) digito+
Constante de punto flotante sin exponente
(+|-) digito+.digito+
Por conveniencia de notación, es deseable dar nombres a las expresiones regulares. Para distinguir los nombres de los símbolos, se imprimen en negritas los nombres de las definiciones regulares.
id à letra(letra|digito)*
const à digito+
punto_flotante à (+|-)digito+.digito+
Por ejemplo, como ya se estableció antes, el conjunto de identificadores es el conjunto de cadenas de letras y dígitos que empiezan con una letra.
La definición o expresión regular para ese conjunto quedaría como sigue:
letra à A|B|C|...|Z|a|b|c|...|z
digito à 0|1|2|3|...|9
id à letra(letra|digito)*
Definición regular para el conjunto de números sin signo como 5280, 39.37, 6.336E4, 1.89E-4
digito à 0|1|2|3|...|9
digitos à digito digito*
fraccion_optativa à .digitos|€
exponente_optativo à (E(+|-|€) digitos)|€
num à digitos fraccion_optativa exponente_optativo
Las expresiones regulares se utilizan para describir los componentes léxicos de un lenguaje o tokens. Las expresiones regulares utilizan varios tipos de operadores para definir los componentes léxicos:
· Paréntesis. Para agrupar símbolos
· Operación concatenación. Se permite la concatenación de cadenas.
· Operación alternativa. Se representa por |, y permite la elección entre dos o más alternativas.
Con estos elementos podemos definir los componentes léxicos. Por ejemplo, para desarrollar la expresión regular para identificador, definimos su patrón y a partir se define su expresión regular.
Lexema
Representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como una unidad léxica. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico.
Patrón
Regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programas fuente. En otras palabras, es la descripción del componente léxico mediante una regla.
NOTA: Cada palabra reservada del lenguaje representa un componente léxico diferente.
Atributos de los componentes léxicos.
El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados. Los componentes léxicos influyen en las decisiones del análisis sintáctico y los atributos en la traducción de los componentes léxicos:
- Apuntador a la entrada de la Tabla de símbolos donde se guarda la información sobre el componente léxico.
- El lexema para un identificador
- El número de línea en que se encontró por primera vez.
2.3 Manejo de buffers de entrada
Código de preanálisis con centinelas
delantero := delantero +1;
If delantero▲ := eof then begin
If delantero está al final de la primera mitad then begin
recargar la segunda mitad;
delantero := delantero + 1
end
else if delantero está al final de la segunda mitad then begin
recargar la primera mitad;
pasar delantero al principio de la primera mitad
end
else
terminar el análisis léxico
end
N à número de caracteres en un bloque de disco eof à marca el final del archivo fuente Se mantienen dos apuntadores al buffer de entrada (Comienzo_lexema y Delantero) Al principio, los dos apuntadores apuntan al primer carácter del próximo lexema que hay que encontrar:
1. El APUNTADOR DELANTERO examina hacia delante hasta encontrar una concordancia con un patrón. Una vez determinado el siguiente lexema, el apuntador delantero se coloca en el carácter de su extremo derecho.
2. El APUNTADOR DE LEXEMA se queda al inicio del lexema y lo procesa.
Después de haber procesado el lexema, ambos apuntadores se colocan en el carácter situado inmediatamente después del lexema. Con este esquema, los comentarios y espacios en blanco se consideran como patrones que no producen componentes léxicos.
Cuando el apuntador delantero está a punto de sobrepasar por la marca intermedia del buffer, se llena la mitad derecha con N nuevos caracteres de entrada. Cuando el apuntador delantero está a punto de sobrepasar el extremo derecho del buffer, se llena la mitad requerida con N nuevos caracteres de entrada y el apuntador delantero se regresa al principio del buffer.
Código para avanzar el apuntador delantero
(En Pascal) If delantero está al final de la primera mitad then begin
recargar la segunda mitad;
delantero := delantero + 1
end
else if delantero está al final de la segunda mitad then begin
recargar la primera mitad;
pasar delantero al principio de la primera mitad
end
else
delantero := delantero + 1
Técnica de “Centinelas”
Si se utiliza la pareja de buffers, cada vez que se mueva el apuntador delantero se debe comprobar si se ha salido de una mitad del buffer, si así ocurriera se deberá cargar la segunda mitad. Es decir, para hacer avanzar el apuntador se realizan dos pruebas. Se pueden reducir estas dos pruebas a una si se amplía cada mitad del buffer para admitir un carácter centinela (carácter especial que no puede ser parte del programa fuente – eof) al final.
Buffer. Área del almacenamiento primario destinada a contener datos durante transferencia de entrada salida. Durante la entrada los datos son cargados en el buffer, al terminar la transferencia ya se puede trabajar con ellos. El analizador léxico es la única fase del compilador que lee el programa fuente carácter a carácter, por lo que es posible que se consuma mucho tiempo en la fase de análisis léxico, aunque las fases posteriores sean más complejas. La velocidad del análisis léxico supone un problema en el diseño de compiladores. Como se puede consumir mucho tiempo moviendo caracteres, se han desarrollado técnicas especializadas en el manejo de buffers para reducir el número de operaciones necesarias para procesar un caracter de entrada.
Técnica de “Pareja de buffers”
En la técnica de pareja de buffers se utiliza un buffer dividido en dos mitades de N caracteres cada uno:
2.4 Especificación de los componentes léxicos
Expresiones regulares
Notación o representación para especificar patrones para un componente léxico. Cada patrón concuerda con una serie de cadenas, de modo que las expresiones regulares servirán como nombres para conjuntos de cadenas.
Cadenas y lenguajes
Alfabeto o clase de carácter. Denota cualquier conjunto finito de símbolos (letras o caracteres). Conjunto {0,1} alfabeto binario a, b, c, d, e, ... , z alfabeto Código ASCII, EBCDIC alfabetos del computador Cadena (frase o palabra). Es una secuencia finita de símbolos tomadas de un alfabeto. Lenguaje. Se refiere a cualquier conjunto de cadenas de un alfabeto fijo. Por ejemplo, todas las palabras u oraciones en español, todas las palabras reservadas o instrucciones del lenguaje C.
Operaciones aplicadas a lenguajes Para el análisis léxico, consideramos principalmente:
- unión
- concatenación
- cerradura
También se puede extender el operador de “exponenciación” a los lenguajes definiendo L° como { }
1. LUD es el conjunto de letras y dígitos.
2. LD es el conjunto de cadenas que consta de una letra seguida de un dígito.
3. L4 es el conjunto de todas las cadenas de cuatro letras.
4. L* es el conjunto de todas las cadenas de letras, incluyendo la cadena vacía ( ).
5. L(LUD)* es el conjunto de todas las cadenas de letras y dígitos que comienzan con una letra.
6. D+ es el conjunto de todas las cadenas de uno o más dígitos.
Abreviaturas en la notación
1. Uno o más casos de. +
2. Cero o un caso. ?
Por ejemplo, usando los operadores + y ? se puede reescribir la definición regular para num:
digito à 0|1|2|3|...|9
digitos à digito
fraccion_optativa à (.digitos)?
exponente_optativo à (E(+|-)? digitos)?
num à digitos fraccion_optativa exponente_optativo
3. Cero o más casos. *
4. Clases de caracteres. Notación abreviada para las expresiones regulares.
Conjuntos no regulares
Aquellos lenguajes que no se pueden describir con ninguna expresión regular.
2.5 Reconocimiento de los componentes léxicos
Consideremos el siguiente formato gramatical:
prop à if expr prop
| if expr prop else prop
| €
expr à termino op_rel termino
| termino
termino à id | num
*Donde if, else, opr_rel, id, num, generan conjuntos de cadenas dadas por la siguiente definición regular:
If à if
else à else
op_relà < | <= | == | >= | > | < >
id à letra (letra|digito)* num à digitos fraccion_optativa exponente_optativo
letra à a|b|c|d| ... |z|A|B|C|...|Z
digito à 0|1|2|3|...|9
digitos à digito digito*
fraccion_optativa à .digitos|€
exponente_optativo à (E(+|-|€) digitos)|€
* El analizador léxico reconoce las palabras clave del lenguaje (if, else)
* op_rel, id, num, los representa por su expresión regular.
Se supone que los lexemas están separados por espacios en blanco, formados por secuencias nulas de espacios en blanco, caracteres TAB y caracteres de nueva línea.
El analizador léxico eliminará los espacios en blanco. Esto lo hará comparando una cadena con la definición de la expresión regular eb siguiente:
delim à blanco | TAB | linea_nueva
eb à delim+
Si se encuentra una concordancia para eb (espacio en blanco), el analizador léxico no devuelve un componente léxico al analizador sintáctico, sino que se dispone a encontrar un componente léxico a continuación del espacio en blanco y lo devuelve al analizador sintáctico.
2.6 Autómatas finitos
Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito.
La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.
El origen de los autómatas finitos probablemente se remonta a su uso implícito en máquinas electromecánicas, desde principios del siglo XX.1 Ya en 1907, el matemático ruso Andréi Márkov formalizó un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.
Esta capacidad de "recordar" es utilizada posteriormente por los autómatas finitos, que poseen una memoria primitiva similar, en que la activación de un estado también depende del estado anterior, así como del símbolo o palabra presente en la función de transición.
Posteriormente, en 1943, surge una primera aproximación formal de los autómatas finitos con el modelo neuronal de McCulloch-Pitts. Durante la década de 1950 prolifera su estudio, frecuentemente llamándoseles máquinas de secuencia; se establecen muchas de sus propiedades básicas, incluyendo su interpretación como lenguajes regulares y su equivalencia con las expresiones regulares.1 Al final de esta década, en 1959, surge el concepto de autómata finito no determinista en manos de los informáticos teóricos Michael O. Rabin y Dana Scott.3
En la década de 1960 se establece su conexión con las series de potencias y los sistemas de sobreescritura.4 Finalmente, con el desarrollo del sistema operativo Unix en la década de 1970, los autómatas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines prácticos, específicamente en el diseño de analizadores léxicos (comando lex) y la búsqueda y reemplazo de texto (comandos ed y grep). A partir de ese tiempo, los autómatas finitos también se comienzan a utilizar en sistemas dinámicos.
Este autómata finito está definido sobre el alfabeto Σ={0,1}, posee dos estados s1 y s2, y sus transiciones son δ(s1,0)=s2, δ(s1,1)=s1, δ(s2,0)=s1 y δ(s2,1)=s2. Su estado inicial es s1, que es también su único estado final. El lenguaje regular que reconoce puede expresarse mediante la expresión regular (00 | 11 | (01 | 10)(01 | 10)) * .
Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
• Los estados se representan como vértices, etiquetados con su nombre en el interior.
• Una transición desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
• El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
• El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.
|
|
La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición. La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.
2.7 AUTOMATAS FINITOS NO DETERMINISTICOS
AFD que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y par de unos.
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).
En un AFD no pueden darse ninguno de estos dos casos:
- Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
- Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.
AFND con transiciones δ(q0,b)=q0 y δ(q0,b)=q1, que acepta el lenguaje regular sobre el alfabeto {a,b} conformado por todas las palabras que terminan en b; es decir, que equivale a la expresión regular (a|b)*b+.
AFND-ε a cuyo estado 2 se puede acceder pasando por el estado 3, sin procesar símbolos de entrada.
Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:
- Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;
- Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.
Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.
Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su función de transición. Mientras en un AFD esta función se define de la siguiente manera:
En un AFND se define como:
Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).
La interpretación que se suele hacer en el cómputo de un AFND es que el autómata puede estar en varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina "adivina" a qué estado debe ir, eligiendo una transición entre varias posibles.
Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.
2.8 AUTOMATAS FINITOS DETERMINISTICOS
Un DFA es un caso especial de NFA en el que ningún estado tiene transiciones para diversos estados bajo el mismo símbolo y no se permiten transiciones épsilon. Los diagramas de transición son autómatas determinísticos. Por ejemplo, el DFA de (a | b)* a b b puede ser:
que podría ser muy aproximado al diagrama de transición que construiríamos para la expresión.
Para llegar de la expresión regular al autómata determinístico se emplea el método de Thompson que permite hacerla transformación y preparar la construcción del analizador de léxico.
Que podría ser muy aproximado al diagrama de transición que construiríamos para la expresión.
Para llegar de la expresión regular al autómata determinístico se emplea el método de Thompson que permite hacerla transformación y preparar la construcción del analizador de léxico.
2.9 PASO DE UNA EXPRESIÓN REGULAR A UN AFN
NOTA: Link del libro” COMPILADORES. PRINCIPIOS TECNICAS Y HERRAMIENTAS” en donde encontrarán todos los temas que hemos visto en clase y los que están mostrados en este blog
2.10 DISEÑO DE UN GENERADOR DE ANALIZADORES LÉXICOS
Programa de Análisis Léxico en C++
Si te interesa conocer más sobre el análisis léxico consulta los siguientes documentos:
No hay comentarios.:
Publicar un comentario