Download - UNI 3-ANALIZADORES LEXICOS
![Page 1: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/1.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 1/38
Unidad III Análisis Léxico
M.C. Juan Carlos Olivares Rojas
![Page 2: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/2.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 2/38
Agenda3.1 Introducción a los Autómatas finitos y
expresiones regulares.3.2 Analizador de léxico.
3.3 Manejo de localidades temporales de
memoria (buffers).
3.4 Creación de tablas de símbolos.
3.5 Manejo de errores léxicos.3.6 Generadores de código léxico: Lex y Flex.
![Page 3: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/3.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 3/38
3.1 Introducción a los Autómatas
finitos y expresiones regulares• ¿Qué es un autómata? Es un modelo
matemático que sirve para determinar si unacadena pertenece a un lenguaje no.
• M = (Q, Σ, &, F) – Q = conjunto de estados
– Σ
= alfabeto de entrada – & = funciones de transición
– F = conjunto de estados de aceptación
![Page 4: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/4.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 4/38
Autómatas finitos• La característica que tienen los autómatas finitos
es que solo existe una función de transición
definida para un símbolo de entrada. Esto eliminaambigüedades
• Una expresión regular es una forma abreviada derepresentar lenguajes:
• a Representa el lenguaje de las letras a• a* Representa el lenguaje que tiene 0 hasta n a’s
![Page 5: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/5.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 5/38
Autómatas• Oprel <|>|<=|>=|=|<>
• Un solo autómata varios sub_autómatas
• Programar un autómata:
• Identificador letra (letra|digito|gb)*
![Page 6: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/6.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 6/38
Expresión Regular• Generar la expresión regular para identificar
correos electrónicos válidos.
• Formato:
• id@dominio
![Page 7: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/7.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 7/38
Expresiones Regulares y una
gramatica• Una gramática sirve para generar cadenas
de un determinado lenguaje pero tambiénsirve para generarla.
• Existente una relación uno a uno entreLenguajes, Autómatas, Expresionesregulares y gramáticas.
![Page 8: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/8.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 8/38
Gramática de un ifprop if expr then prop
| if expr then prop else prop| ε
expr termino oprel termino| termino
termino id
| num
![Page 9: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/9.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 9/38
Gramática de un if• oprel < |>|=|<=|<>|>=|
• id letra (letra | digito)*
• num digito+ (.digito+)?(E(+|-)?digito+)?
• eb delim+
• delim blanco | tab | linenueva
![Page 10: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/10.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 10/38
3.2 Análizador Léxico• Primera fase de la compilación
• Leer caracteres de entrada y generar como salidauna secuencia de componentes léxicos
• Eliminar espacios en blanco
• Eliminar comentarios
• Proporcionar información acerca de errores léxicos
![Page 11: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/11.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 11/38
Componentes léxicos, lexema y
patrones
(dígito)+2, 23, 5124ENTERO204
letra (letra |
dígito | gb)*
var, s1,
suma, prom
IDENTIFICADOR203
<, >, !=, ==<, >, !=, ==OP_RELACIONAL202
ififIF201
PatrónLexemaComponente léxicoID
![Page 12: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/12.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 12/38
Análisis Léxico• El análisis lineal, se llama léxico o
exploración.
• Posicion := inicial + velocidad * 60
• Posicion: identificador
• := símbolo de asignación• Inicial: identificador
![Page 13: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/13.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 13/38
Análisis Léxico• +: signo de suma
• Velocidad: identificador• *: signo de multiplicación
• 60: numero
• Se elimina todos los espacios en blancos
(espacios, tabuladores, salto de línea, etc.)
![Page 14: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/14.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 14/38
Análisis Léxico• Reconocedores de identificadores y palabras
clave
• La tabla de símbolo debe insertar y buscar
componentes léxicos
• La tabla de símbolos es utilizada por el
analizador sintáctico y por otras fases delproceso de traducción
![Page 15: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/15.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 15/38
Función del analizador léxico
Analizador LéxicoAnalizadorSintáctico
Tabla desímbolos
Código
fuente
Componenteléxico
Obtener siguientecomponente léxico
![Page 16: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/16.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 16/38
Análisis léxico• Un patrón es una regla que describe el conjunto de
lexemas que puede representar a un conjuntoléxico
• Los componentes léxicos se tratan comoterminales de la gramática del lenguaje fuente
• La devolución de un componente léxico se hace através de un número entero
![Page 17: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/17.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 17/38
Especificación de componentes
léxicos• Expresiones regulares (patrón)
• Cada patrón concuerda con una serie decadenas
• Las expresiones regulares dan el nombre al
conjunto de cadenas con que concuerdan
![Page 18: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/18.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 18/38
Expresiones regulares• Se construyen a partir de otras expresiones
regulares más simples
• Cada expresión regular r, representa un
lenguaje L(r)
• Letra a u b u c u … u z
• Dígito 1 u 2 u 3 u … u 0• Identificador letra(letra u dígito)*
![Page 19: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/19.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 19/38
Definiciones regulares• Dan nombres a las expresiones regulares
• Nos permiten referenciarlas recursivamente
• Digito 1|2|3|4|5|6|7|8|9|0
• Entero dígito+
• Decimal .dígito+ | .dígito+E(+|-| ε)dígito+• Real entero (decimal | ε)
![Page 20: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/20.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 20/38
Abreviaturas• * cero o más casos
• + uno o más casos
• [a-zA-Z] mayúsculas y minúsculas
• [0-9] dígitos
• ? Cero o un caso
![Page 21: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/21.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 21/38
Abreviaturas• Digito [0-9]
• Entero digito+• Decimal .digito+exponente?
• Exponente (E|e) (+|-)?digito+
• Real entero decimal?
![Page 22: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/22.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 22/38
3.3 Manejo de localidades temporales
de memoria (buffers)• La forma más fácil de leer un programa es
carácter por carácter pero es ineficiente.
• La forma más eficiente es realizar una copia
a la memoria de todo el código fuente. Peroesto en la gran mayoría de las ocasiones esimpráctico por las dimensiones de losprogramas. Para solucionar este problemase sugiere utilizar buffers
![Page 23: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/23.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 23/38
Manejo de buffers• Existen muchas formas de dividir el trabajo,
pero siempre se deberá llevar dos punteros,uno al carácter actual y otro al inicial dellexema.
• El manejo de buffers es esencial pararealizar el análisis de grandes programas demejor manera
![Page 24: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/24.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 24/38
3.4 Creación de tablas de
símbolos• En general el proceso de análisis léxico
puede describirse simplemente como elreconocimiento de caracteres de un lenguajepara generar una tabla de símbolos.
• El primer paso consiste en crear un escáner,el cual se encarga de verificar que no existancaracteres no presentes en el lenguaje.
![Page 25: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/25.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 25/38
Tabla de símbolos• La tabla de símbolos va a guardar cada
palabra analizada, la va identificar como unlexema y le va asociar un identificadornumérico para posteriormente utilizarlo.
• La tabla de símbolos debe estar en memoriapara realizar un análisis rápido.
![Page 26: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/26.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 26/38
3.5 Manejo de errores léxicos• Son pocos los errores que se pueden
detectar al hacer análisis léxico
• fi (a == f(x)) //Error de sintaxis
• Pero puede existir algún error si ninguno de
los patrones con cuerda con el prefijo deentrada
![Page 27: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/27.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 27/38
Técnicas de recuperación de errores• Borrar un carácter extraño
• Insertar un carácter que falta
• Reemplazar un carácter incorrecto por otrocorrecto
• Intercambiar dos caracteres adyacentes
![Page 28: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/28.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 28/38
Técnicas para realizar analizadores
léxicos• Utilizar un analizador léxico como FLEX. El
generador se encarga de manejar buffers
• Escribir el analizador en un lenguaje de alto
nivel haciendo uso de la E/S del lenguaje
• Escribir el lenguaje ensamblador y manejarexplícitamente la E/S
![Page 29: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/29.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 29/38
Análisis Léxico en XML• El análisis léxico en documentos XML lo realiza
cualquier herramienta o API que utilice XML, ya
que debemos cerciorarnos que el lenguaje estébien formado.
• Si el lenguaje no cumple con las reglas deconstrucción de documentos XML, falla el proceso.
• Realizar análisis léxico de XML en Java o C#
![Page 30: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/30.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 30/38
3.6 Generadores de código léxico:
Lex y Flex• FLEX es la versión de software libre del popular
generador de analizadores léxicos LEX para
sistemas *NIX, genera código C aunque existenotras herramientas que generan código en otroslenguajes
• Analizador.lex flex lex.yy.c gcc
Programa ejecutable analizador
• $gcc lex.yy.c –o analizador –lfl
![Page 31: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/31.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 31/38
Programa Lex%{
Definiciones globales ‘C’}%
Definiciones flex
%%Acciones
%%Código ‘C’ auxiliar
![Page 32: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/32.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 32/38
Definiciones regulares en flex• %% Separadores de secciones
• Def expresión
• Acciones
• {def} {código ‘C’ asociado}
• “@” {código ‘C’ asociado}
![Page 33: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/33.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 33/38
Programa que reconoce flotantes%{
#include <stdio.h>
Int ocurrencias;}%Digito[0-9]
Punto [\.]Exp [eE]Signo[\+\-]Digitos {digito}+Decimal {punto} {digitos}({exp}{signo}{digitos})?Flotante {digitos}{decimal}?
![Page 34: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/34.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 34/38
Programa que reconoce flotantes%%
{flotante} { printf(“flotante encontrado\n”);ocurrenicas++; }
“@” { printf(“Arroba\n”); }
. { printf(“Inválido: %s\n”, yytext); }
%%
![Page 35: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/35.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 35/38
Programa que reconoce flotantesmain(int argc, char *argv[])
{FILE *f;
F = fopen(argv[1], “r”);
yyin = f;while(yylex());
printf(“%d flotantes encontrados\n”, ocurrencias);
fclose(f);}
![Page 36: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/36.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 36/38
Programa para reconocer direcciones
IPDigito [0-9]
Punto [\.]
IP {digito}+{punto}{digito}+{punto}+{digito}+{punto}{digito}+
%%{IP} { strcpy(aux, yytext);
strcat(aux, “.”);
for(i =0 ; i<4; i++){
P di i
![Page 37: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/37.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 37/38
Programa para reconocer direcciones
IPcadnum = strtok(aux, “.”);
if(atoi (cadnum)>255)
{
printf(“Error\n”);
break;}
if(i==4)
printf(“Dirección IP: %s\n”, yytext);}
![Page 38: UNI 3-ANALIZADORES LEXICOS](https://reader031.vdocumento.com/reader031/viewer/2022020803/5571fcb6497959916997c811/html5/thumbnails/38.jpg)
5/10/2018 UNI 3-ANALIZADORES LEXICOS - slidepdf.com
http://slidepdf.com/reader/full/uni-3-analizadores-lexicos 38/38
¿Preguntas?