3.1 Introducción a los Autómatas finitos y expresiones regulares
¿Qué es un autómata?
R= Es un modelo matemático que sirve para determinar si una cadena
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
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 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
Autómatas
• Oprel à <|>|<=|>=|=|<>
• Un solo autómata varios sub_autómatas
• Programar un autómata:
• Identificador à letra (letra|digito|gb)*
Expresión Regular
• Generar
la expresión regular para identificar correos electrónicos válidos.
Formato:
•
jcolivar@itmorelia.edu.mx
•
id@dominio
Expresiones Regulares y una gramatica
• 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.
Gramática de un if
Prop à if expr then prop
| if expr then prop else prop
| ε
Expr à termino oprel termino
| termino
termino à id
| num
Gramática de un if
• oprel à
<
|>|=|<=|<>|>=|
• id à
letra
(letra | digito)*
• num à
digito+
(.digito+)?(E(+|-)?digito+)?
• eb à
delim+
• delim à
blanco |
tab | linenueva
3.2
Análizador Léxico
Primera fase de la compilación
• Leer caracteres de entrada y generar como salida
una secuencia de componentes léxicos
• Eliminar espacios en blanco
• Eliminar comentarios
• Proporcionar información acerca de errores léxicos
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
• +: 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.)
• 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 del proceso de traducción
Función del analizador léxico
• Un patrón es una regla que describe el conjunto de lexemas que puede
representar a un conjunto léxico
• Los componentes léxicos se tratan como terminales de la gramática del
lenguaje fuente
• La devolución de un componente léxico se hace a través de un número
entero
Especificación de componentes léxicos
• Expresiones regulares (patrón)
• Cada patrón concuerda con una serie de cadenas
• Las expresiones regulares dan el nombre al conjunto de cadenas con que
concuerdan
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)*
Definiciones regulares
• Dan nombres a las expresiones regulares
• Nos permiten referenciarlas recursivamente
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
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. Pero
esto en la gran mayoría de las
ocasiones es impráctico por las dimensiones de los programas. Para solucionar
este problema se sugiere utilizar buffers
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 del lexema.
• El manejo de buffers es
esencial para realizar el análisis de grandes programas de mejor manera
3.4 Creación de tablas 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.
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 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 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 manejar explícitamente la E/S
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 de construcción de documentos XML, falla el proceso.
• Realizar análisis léxico de XML
en Java o C#
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 existen otras herramientas que generan código en otros lenguajes
• Analizador.lex à flexà lex.yy.c à gcc à Programa ejecutable analizador
• $gcc lex.yy.c –o analizador
–lfl
No hay comentarios:
Publicar un comentario