Download Sistemas Operativos II

Análisis Léxico
M.C. Juan Carlos Olivares Rojas
Agenda
• Introducción a los Autómatas
expresiones regulares.
finitos
y
• Analizador de léxico.
• Manejo de localidades temporales de memoria
(buffers).
• Creación de tablas de símbolos.
• Manejo de errores léxicos.
• Generadores de código léxico: Lexy Flex.
Ensamblado en Java
• ¿Qué es un autómata? Es un modelo
matemático que sirve para determinar si una
cadena pertenece a un lenguaje no.
• A = (Q, Σ, &, F) donde
•
•
•
•
Q = conjunto de estados
Σ= alfabeto de entrada
& = funciones de transición
F = conjunto de estados de aceptación
AFD
• La característica que tienen los Autómatas
Finitos Deterministas (AFD) es que solo existe
una función de transición definida para un
símbolo
de
entrada.
Esto
elimina
ambigüedades
• Una expresión regular es una forma abreviada
de representar lenguajes:
• a Representa el lenguaje de las letras a
• a* Representa el lenguaje que tiene 0 hasta n
a’s
AFD
• El principio de diseño de un Lenguaje de
Programación radica en la utilización de un
autómata genérico y de ese autómata partir de
varios subautómatas.
• Los autómatas suelen representarse
expresiones regulares. Ejemplo:
• Identificador: letra (letra | digito | gb)*
con
AFD
• Generar la expresión regular para identificar
URL válidas.
• Ejemplo:
• http://www.patito.com/recurso.php?id=0
• ftp://ftp.sindominio.com/pub/archivo
• file://casa.decera.com/recurso+20+dos
• ¿Cómo queda la expresión regular?
AFD
• Dada la siguiente expresión regular como
queda el autómata que lo representa:
• Alpha (alpha | num | sim)*
• Donde alpha es un carácter de a..Z
• Num es un dígito de 0 a 9
• Sim es uno de los siguientes símbolos
AFD
• ¿Cómo se programa un autómata?
• Los autómatas tienen su representación en
forma de grafos que a su vez se representan
en forma de tablas de transiciones, se cuenta
con un estado inicial y una función de siguiente
estado. Al terminar de leer la cadena se verifica
si el estado es algún estado de aceptación.
Práctica 5
• Programar un autómata para reconocer la
URLs que son válidas.
• Se deberá tener una matriz de transiciones y
una función de estado siguiente. No se
permitirán validaciones por otros medios.
• Se deberán leer cadenas contenidas en un
archivo de texto plano y deberá devolver que
cadenas si son URLs
Expresiones Regulares y
Gramáticas
• ¿Qué similitudes existen entre las expresiones
regulares y gramáticas?
• Una gramática sirve para generar cadenas de
un determinado lenguaje pero también sirve
para generarla.
• Existente una relación uno a uno entre
Lenguajes, Autómatas, Expresiones regulares y
gramáticas.
Analizador Léxico
• El análisis léxico es la primera fase de la
compilación.
• Un analizador léxico:
• Lee caracteres de entrada y generar como
salida una secuencia de componentes léxicos
(generalmente representados por números).
Analizador Léxico
• Un analizador léxico:
• Elimina espacios en blanco (considerados por
el lenguaje como tabuladores, etc.)
• Eliminar comentarios
• Proporcionar información acerca de errores
léxicos (caracteres inexistentes o tokens
inexistentes)
Tabla de Símbolos
• La tabla de símbolos se compone de un lexema
y un identificador del componente léxico.
• Los componentes léxicos se conforman de un
patrón (expresión regular que lo valida).
• El patrón se codifica como un autómata.
Tokens, Lexemas y Patrones
Análisis Léxico
• También recibe el análisis lineal, se llama léxico
o exploración.
• Ejemplo:
• Posicion:= inicial + velocidad * 60
• Posicion: identificador
• := símbolo de asignación
• Inicial: identificador
Análisis Léxico
•
•
•
•
+: signo de suma
Velocidad: identificador
*: signo de multiplicación
60: numero
• Las palabras clave de muchos lenguajes son
lexemas tal cual. Por ejemplo para reconocer
un token if, se necesita de un patrón “if”.
Analizador Léxico
• La tabla de símbolo debe insertar y buscar
componentes léxicos (aunque en el análisis
léxico sólo se inserten, se debe recordar que la
tabla de símbolos es utilizada por el analizador
sintáctico y por otras fases del proceso de
traducción.
• Los componentes léxicos se tratan como
terminales de la gramática del lenguaje fuente.
Existen muchas herramientas para utilizar
expresiones regulares.
Definiciones Regulares
• Dan nombres a las expresiones regulares.
Permiten referenciar las expresiones regulares
recursivamente
•
•
•
•
•
Ejemplo:
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 | ε)
Abreviaturas
• * cero o más casos
• + uno o más casos
• ? 0 ó 1 vez (opcional)
• [a-zA-Z] mayúsculas y minúsculas
• [0-9] dígitos
Definiciones Regulares
• Digito[0-9]
• Entero digito+
• Decimal .digito+exponente?
• Exponente (E | e) (+|-)?digito+
• Real  entero decimal?
Analizador Léxico
Examen 2
• Entrega: viernes 9
• Análisis de Requerimientos dado un archivo
*.class correcto, encontrar los mnemónicos que
tiene disponible el ensamblador (alias javap –c
Archivo)
• Complejidad al detectar el encabezado
(formato *.class) y después la complejidad del
código
Examen 2
Examen
• Se puede observar que de este pequeño hola
mundo se tienen dos métodos.
• El primero de ellos de 5 bytes, revisando sus
mnemónicos se puede observar que su códigos
de operación en byte es:
• 0x2a
• 0xb7 0x00 0x01
• b1
•
•
•
•
•
BB FE AF EA 77 03 05 2a b7 00 01 b1 12
Formato valido
aload_o
Invokespecial 0 1
Return
Examen 2
Examen 2
• Esto se puede buscar en el archivo *.class.
• El detalle radica en que el código no viene sólo
sino en una estructura Attribute denominada
code_attribute (ver unidad pasada). Nótese por
ejemplo que un byte antes del código marcado
nos indica el tamaño del código de ese método.
Examen 2
• Reformulación del proyecto. Dado nuestro
propio formato comenzará de la siguiente
forma: 4 bytes de número mágico: BB FE AF
EA, 2 bytes para indicar la versión y subversión
del compilado, 2 bytes para indicar el tamaño
del código, instrucciones del ensamblador de
java y un byte al final como código de
comprobación (tamaño total del archivo % 255).
Examen 2
• Se deberá validar que sus archivos *.obj tengan
este formato. Se hará la impresión de los
mnemónicos contenidos (puede ser modo texto
o visual).
• Se ocupa conocer
mnemónicos
el
tamaño
de
los
• ¿Para el viernes autómata o examen 2? Por lo
tanto que queda para el lunes.
Mnemónicos en Java
• astore <varnum>:
referencia.
saca
de
la
pila
una
• baload: recupera un byte de un arreglo de
bytes y lo convierte a un entero que se coloca
en la pila de operandos.
• bipush <n>: coloca un entero de 8 bits en la pila
(lo convierte a un entero de 32 bits)
Mnemónicos en Java
• d2f: saca de la pila un flotante de doble
presición para convertile a un flotante sencillo y
volverlo a colocar en la pila (esta operación
puede causar pérdida de precisión).
• dadd: toma dos dobles de la pila, los suma y
coloca el resultado en la pila.
• dup_x1: duplica el valor de la cima de la pila y
la coloca una posición debajo.
Mnemónicos en Java
• fneg: niega un flotante.
• goto <label>: brinca a la dirección especificada
por la etiqueta (cadena de texto), label ocupa
dos bytes por lo que esta instrucción es de 3
bytes.
• iand: realiza una operación lógica “Y” entre
dos enteros en la cima de la pila, el
resultado lo deja en la pila.
Mnemónicos en Java
• ifeq <label>: realiza un pop en la pila para
comparar si el valor apuntado por etiqueta es
igual al de la pila. Esta es una instrucción de 3
bytes
• istore <varnum>: saca un valor de la pila y lo
almacena en una variable local.
• jsr_w <label>: salta a una subrutina, label hace
referencia a un valor doble, por lo que esta
instrucción es de 5 bytes.
Manejo de localidades temporales
de memoria (buffers)
• La forma más fácil de realizar el escanner de
un código es a través de carácter por carácter
pero esto es sumamente ineficiente.
• La forma más eficiente es realizar una copia a
la memoria de todo el código fuente.
Manejo de Buffers
• La desventaja de este último enfoque es que la
gran mayoría de las ocasiones es impráctico
por las dimensiones de los programas. Para
solucionar este problema se sugiere utilizar
buffers.
• Existen muchas formas de dividir el trabajo,
pero siempre se deberá llevar dos punteros,
uno al carácter actual y otro al inicial del
lexema.
Creación de Tabla de Símbolos
• En general el proceso de análisis léxico puede
describirse
simplemente
como
el
reconocimiento de caracteres de un lenguaje
para generar una tabla de símbolos.
• El primer paso consiste en crear un escáner, el
cual se encarga de verificar que no existan
caracteres no presentes en el lenguaje.
Tabla de Símbolos
• La tabla de símbolos va a guardar cada palabra
analizada, la va identificar como un lexema y le
va asociar un identificador numérico para
posteriormente utilizarlo.
• La tabla de símbolos debe estar en memoria
para realizar un análisis rápido.
Errores Léxicos
• Son pocos los errores que se pueden detectar
al hacer análisis léxico
• Por ejemplo:
– fi (a == f(x))
• ¿Es error léxico? No, es error sintáctico
• Puede existir algún error si ninguno de los
patrones no concuerda con el prefijo de
entrada.
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 otro
correcto
• Intercambiar dos caracteres adyacentes
Técnicas para realizar analizadores
léxicos
• Utilizar un analizador léxico como LEX. 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 manejar
explícitamente la E/S
Patrones en Java
• El lenguaje Java es un lenguaje de alto nivel de
propósito general que cuenta entre sus cosas
con un motor para reconocimento de patrones
de texto.
• El paquete javax.util.regex.*; el cual dispone de
dos clases: Pattern y Matcher.
Patrones en Java
• La clase Pattern se utiliza para especificar los
patrones y la clase Matcher se utiliza para
procesar las cadenas y ver si coinciden con el
patrón.
• El método compile de la clase Pattern permite
especificar la expresión regular utilizando
prácticamente la misma simbología de
comodines de expresiones regulares.
Patrones en Java
• Un objeto de la clase Matcher se crea a través
del método matcher() del objeto instanciado de
la clase Pattern.
• La clase matcher tiene los siguientes métodos:
matches para una coincidencia exacta,
lookingAt cuando se encuentra el patrón en
parte de la cadena, find permite buscar
subcadenas que coincidan con el patrón.
Patrones en Java
• El método find permite utilizar los métodos start
y end para encontrar la primera y última
coincidencia.
• El método replaceAll(), permite cambiar una
subcadena por otra.
Patrones en Java
import java.util.regex.*;
public class ValidarEmail {
public static void main(String[] args) throws Exception {
String cadena = “jcolivar@hotmail.com";
Pattern p = Pattern.compile("\\w\\+@\\w\\.\\w");
Matcher m = p.matcher(input);
if (m.find()) System.err.println("Las direcciones email
no empiezan por punto o @");
}
}
Generadores de Código Léxico
• FLEX es la versión de software libre del popular
generador de analizadores léxicos LEX para
sistemas *NIX, genera código C aunque existen
otras herramientas que generan código en
otros lenguajes (Jflex para Java)
• Analizador.lex  flex lex.yy.c
Programa ejecutable analizador
• $gcc lex.yy.c –o analizador –l fl
gcc
Estructura Lex
%{
Definiciones globales ‘C’
}%
Definiciones flex
%% Acciones
%% Código ‘C’ auxiliar
Definiciones de Expresiones
Regulares
• %% Separadores de secciones
• Def expresión
• Acciones
• {def} {código ‘C’ asociado}
• “@”{código ‘C’ asociado}
Ejemplo Scanner Flotante
%{
#include <stdio.h>
int ocurrencias;
%}
digito [0-9]
punto [\.]
exp [eE]
signo[\+\-]
digitos {digito}+
Ejemplo de Scanner Flotante
decimal {punto} {digitos}({exp}{signo}{digitos})?
flotante {digitos}{decimal}?
%%
{flotante} { printf(“flotante encontrado\n”);
ocurrenicas++; }
“@” { printf(“Arroba\n”); }
. { printf(“Inválido: %s\n”, yytext); }
%%
Ejemplo de Scanner Flotante
int main(int argc, char* argv[]) {
FILE *f;
F = fopen(argv[1], “r”);
yyin= f;
while(yylex());
printf(“%dflotantes encontrados\n”, ocurrencias);
fclose(f);
return 0;
}
JFlex
• Es otra forma de incluir expresiones regulares
para crear scanners pero ahora con lenguaje
java.
• Se tiene que manejar una sintaxis muy similar a
lex con sus respectivas variantes.
• Las expresiones regulares se definen dentro de
un archivo con extension .lex o jflex (realmente
la extensión no importa). A continuación se
muestra un ejemplo.
JFlex
/*Aqui van todas las bibliotecas*/
import javax.swing.JOptionPane;
%%
/*Definiciones regulares
configuracion*/
%class Flotante
%unicode
%full
%int
y
parametros
de
JFlex
%line
%column
%{
/*Codigo Java genérico*/
int ocurrencias;
public int getOcurrencias(){
return ocurrencias;
}
%}
JFlex
/*Definiciones regulares*/
digito=[:digit:]
blancos=[\n\r\t\f\b]
punto =[.]
exp=[eE]
signo=[+-]
digitos={digito}+
decimal={punto}{digitos}(("e"|"E"){signo}{digitos})
?
JFlex
flotante={signo}?{digitos}{decimal}?
/*Sección de acciones*/
%%
/*Palabras reservadas */
<YYINITIAL>
"break"
JOptionPane.showMessageDialog(null,
encontro un break"); }
<YYINITIAL> {
{flotante}
{
"Se
JFlex
{
JOptionPane.showMessageDialog(null,
encontro un flotante: "+ yytext());
ocurrencias++; }
"Se
{blancos} {/*se ignora*/}
. { /*ignoramos el token*/ }
}
• //Falta construir la clase principal o bien
incrustarla dentro del código main
JFlex
import java.io.*;
public class ScannerFlotante {
public static void main(String[] args) {
try {
FileReader arch = new FileReader(args[0]);
Flotante f = new Flotante(arch);
f.yylex();
System.out.print("Numero
de
flotantes
encontrados:" + f.getOcurrencias());
} catch (Exception e) {
JFlex
e.printStackTrace();
}
}
}
• La invocación de Jflex se realiza jflex
archivo.lex, sino se pasan argumentos se abre
una interface gráfica.
• La clase generada se llama Flotante.java (si no
se expecifica se crea una clase Yylex.java)
JFlex
• Al igual que lex, se puede complementar el
código con algún otro código de Java, por
ejemplo APIs para el manejo de gráficos.
• Jflex genera autómatas finitos no determinista
que luego convierte a autómatas finitos
determinista para posteriormente minimizar su
estado.
Referencias
• Aho, Sethi, Ullman. Compiladores Principios,
técnicas y herramientas Ed. Addison Wesley.
• Beck,. Software de Sistemas, Introducción a la
programación de Sistemas Ed. Addison-Wesley
Iberoamericana.
• Kenneth C. Louden. Construcción de
compiladores Principios y práctica. Ed.
Thomson.
Referencias
• Java Virtual Machine Specification
¿Preguntas?