UNIDAD 4

4.1 Funciones del analizador léxico.

Un analizador léxico aísla el analizador sintáctico de la representación de lexemas de los componentes léxicos.

Funciones:

1- Eliminación de espacios en blanco

2-reconocimiento de identificadores y palabras claves

3- Analizador léxico ”scanner” lee la secuencia de los caracteres del programa fuente, y los agrupa para formar unidades con significado propio.

El analizador léxico es la primera fase de un compilador.

Esta interacción, suele aplicarse convirtiendo al analizador léxico en una subrutina o corrutina del analizador sintáctico. Recibida la orden "obtén 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.

Funciones secundarias.

Ciertas funciones secundarias en la interfaz del usuario, como eliminar del programa fuente comentarios y espacios en blanco en forma de caracteres de espacio en blanco, caracteres TAB y de línea nueva. Otra función es relacionar los mensajes de error del compilador con el programa fuente. Por ejemplo, el analizador léxico puede tener localizado el número de caracteres de nueva línea detectados, de modo que se pueda asociar un número de línea con un mensaje de error.

En algunos compiladores, el analizador léxico se encarga de hacer una copia del programa fuente en el que están marcados los mensajes de error. Si el lenguaje fuente es la base de algunas funciones de pre procesamiento de macros, entonces esas funciones del preprocesador también se pueden aplicar al hacer el análisis léxico.

Maigualida Pérez Melgarejo.

Bibliografía:

Louden, K.C. (1997), Compiler Construction: Principles and Practice, Tema 2, p´aginas: 31-93.

4.2 Componentes léxicos patrones y lexemas

·         Léxico:

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:

Ø  palabras clave o reservadas

Ø  Operadores aritméticos

Ø  Operadores relacionales

Ø  Operadores lógicos

Ø  Operador de asignación

Ø  Identificadores

Ø  Constantes

Ø  Cadenas

Ø  Literales

Ø  Signos de puntuación

Ø  Librerías

 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.

·  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.

 Edgarda Santiago Reyes

Bibliografia:

http://compiladorsistemas.blogspot.com/2010/11/lexemas-patrones-y-tokens.html

http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro32/22_componentes_lxico patrones_y_lexemas.html

4.3.-Creación de tabla de tokens.

Tabla: conjunto de pares clave-valor, llamados elementos de la tabla. La tabla de símbolos es una componente necesaria de un compilador. Al declarar un identificador (normalmente una sola vez), éste es insertado en la tabla. Cada vez que se utilice el identificador se realizará una búsqueda en la tabla para obtener la información asociada (el valor).

·         Búsqueda: dada la clave de un elemento, encontrar su valor.

·         Inserción: Dado un par clave-valor, añadir un elemento nuevo a la tabla.

·         Cambio de valor: Buscar el elemento y cambiar su valor.

·         Borrado: Eliminar un elemento de la tabla.

·         Longitud de búsqueda (o tiempo de acceso)

De una clave: Li = número de comparaciones con elementos de la tabla para encontrar esa clave. Máxima: LM = número máximo de comparaciones para encontrar cualquier clave. Media (esperada): Lm = número medio de comparaciones para encontrar un valor. 

Si la frecuencia de todas las claves es la misma:

Lm = (S Li)/N

Si la frecuencia de todas las claves no es la misma:

Lm = S pi.Li

Grado de ocupación:

s = n/N donde n=número de elementos en la tabla y N=capacidad máxima de la tabla.

Función de búsqueda: B : K→E asocia a cada clave k un elemento B(k).

Valor asociado a una clave k: v(B(k)). Puede ser múltiple, en cuyo caso normalmente se convierte en un puntero. Si está en la tabla puede almacenarse consecutivamente o en subtablas paralelas. Tablas de símbolos (identificadores) La clave es el identificador. El valor está formado por:

·         Atributos del identificador. Puntero a la posición de memoria asignada. La clave puede sustituirse por un puntero. Los identificadores pueden estar empaquetados. La longitud del identificador puede especificarse en la tabla o delante del nombre, o ser implícita.

·         Tablas consecutivas: Todos los elementos ocupan posiciones de memoria adyacentes. Tablas ligadas: cada elemento apunta al siguiente. Tablas doblemente ligadas: cada elemento apunta al siguiente y al anterior. Tablas no ordenadas Inserción: en el primer lugar vacío.

 Componentes léxicos (tokens): unidad mínima de información que significa algo a la hora de compilar; concepto de palabra; las fases de un lenguaje constan de cadenas de componentes léxicos.

Lexema: Una secuencia de caracteres de entrada que comprenden un solo componente léxico se llama lexema; cadena de caracteres que extrae el componente abstracto del componente léxico.

Patrón: Descripción de la forma que han de tomarlos lexemas para ajustarse a un componente léxico.

Ejemplo.

Marisa Martínez Bautista  

Bibliografía.

http://10380054.galeon.com/u5.htm

 

4.4 Errores léxicos

El análisis léxico constituye la primera fase, aquí se lee el programa fuente de izquierda a derecha y se agrupa en componentes léxicos (tokens), que son secuencias de caracteres que tienen un significado. Además, todos los espacios en blanco, líneas en blanco, comentarios y demás información innecesaria se elimina del programa fuente. También se comprueba que los símbolos del lenguaje (palabras clave, operadores,...) se han escrito correctamente.

Como la tarea que realiza el analizador léxico es un caso especial de coincidencia de patrones, se necesitan los métodos de especificación y reconocimiento de patrones, y éstos métodos son principalmente las expresiones regulares y los autómatas finitos. Sin embargo, un analizador léxico también es la parte del traductor que maneja la entrada del código fuente, y puesto que esta entrada a menudo involucra un importante gasto de tiempo, el analizador léxico debe funcionar de manera tan eficiente como sea posible.

Son pocos los errores simplemente en el nivel léxico ya que tiene una visión muy restringida de un programa fuente. El analizador léxico debe devolver el componente léxico de un identificador y dejar a otra fase se ocupe de los errores.

Suponga que una situación en la cual el analizador léxico no puede continuar por que ninguno de los patrones concuerda con un prefijo de la entrada. Tal vez la estrategia de recuperación más sencilla sea recuperación “EN MODO PANICO” (este método de recuperación es donde se borra caracteres sucesivos de la entrada hasta que el analizador léxico pueda encontrar un componente léxico bien formado). ¡¡Los programas no siempre son correctos!!

El compilador tiene que:

1. Reportar clara y exactamente la presencia de errores
2. Recuperarse de cada error lo suficientemete rápido para poder detectar errores subsiguientes:

• Tratar de evitar mensajes falsos de error
• Un error que produce un token erroneo
• Errores léxicos posibles

Un token o componente léxico es una cadena de caracteres que tiene un significado coherente en cierto lenguaje de programación. Ejemplos de tokens, podrían ser palabras clave (if, while, int), identificadores, números, signos, o un operador de varios caracteres. Son los elementos más básicos sobre los cuales se desarrolla toda traducción de un programa, surgen en la primera fase, llamada análisis léxico.

Rodolfo Rodríguez Medina

Bibliografía.

http://manejodeerrores.blogspot.com/

4.5.-Generadores de analizadores Léxicos.

Un analizador léxico es un modo destinado a leer caracteres del archivo de entrada, donde se encuentra la cadena a analizar, reconocer subcadenas que correspondan a símbolos del lenguaje y retornar los tokens correspondientes y sus atributos.

o   Generador LEX:

Es un programa para generar analizadores léxicos, se utiliza comúnmente con el programa yacc que se utiliza para generar análisis sintáctico, escrito originalmente por Eric Schmidt y Mike Lesk, es el analizador léxico estándar de POSIX. Lex toma como entrada una especificación de analizador léxico y devuelve como salida el código fuente implementando el analizador léxico en C.

Esquema general: un programa fuente de LEX tiene el siguiente aspecto.

De estas tres secciones, solo la segunda es obligatoria, y cualquiera de ellas pueden estar vacia.

o   Generador FLEX

Es una herramienta para la generación de programas que realizan corcondancia de patrones en texto, es una herramienta para generar escanes. FLEX lee los archivos de entrada dados, o la entrada estándar si no se ha indicado ningún nombre de archivo, con la descripción de un escáner a generar. La descripción se encuentra en forma de parejas de expresiones regulares y código C, denominadas reglas.

o   Generador JTLexx

Permite expresar conjuntamente sintaxis y semántica al estilo de los esquemas de traducción.  A su vez el proceso de conjunto de atributos es implementado por JTLex por un autómata finito traductor con las ventajas de eficiencia que esto supone. Una especificación JTLex permite no solo asociar procedimiento, o acción a cada expresión regular, sino también a cada ocurrencia de un símbolo dentro de la expresión.

Esquema de funcionamiento:

Gramática:

Blanca Estela Reyes Castillo

Bibliografia.

https://prezi.com/mghu3fnrdwd7/generador-de-analizadores-lexicos/ 

                                  

4.6 Aplicaciones (caso de estudio)

Además de para construir compiladores e intérpretes, los analizadores léxicos se pueden emplear para muchos programas \convencionales”. Los ejemplos más claros son aquellos programas que tienen algún tipo de entrada de texto donde hay un formato razonablemente libre en cuantos espacios y comentarios. En estos casos es bastante engorroso controlar donde empieza y termina cada componente y es fácil liarse con los punteros a char. Un analizador léxico simplifica notablemente la interfaz y si se dispone de un generador automático, el problema se resuelve en pocas líneas de código.

Edgarda Santiago Reyes

Bibliografia:

http://compiladorsistemas.blogspot.com/2010/11/lexemas-patrones-y-tokens.html

http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro32/22_componentes_lxico patrones_y_lexemas.html

                                                 UNIDAD 3.- AUTOMATAS FINITOS.

3.1 CONCEPTO DEFINICIÓN Y CLASIFICACIÓN DE AUTÓMATA FINITO (AF)

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

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.

Definición formal Formalmente:

E: alfabeto de entrada.
Q: conjunto de estados; es conjunto finito no vacío.
f: función de transición. f(p,a)=q
q0 : (perteneciente a Q) estado inicial.
F : (perteneciente a Q) conjunto de estados finales o de aceptación.

En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición. 

Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

CLASIFICACIÓN DE AF LOS AUTÓMATAS SE PUEDEN CLASIFICAR EN:

· Deterministas; Cada combinación (estado, símbolo de entrada) produce un solo estado.

· No Deterministas; Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

REPRESENTACION:

TABLA	a	b
->p	q
*q	q3	r
q3		r
r	q3

Tablas de transición:
• Filas encabezadas por los estados( Q )
• Columnas encabezadas por los símbolos de entrada ( E )

Diagramas de transición:

• Nodos etiquetados por los estados(Q)
• Arcos entre nodos etiquetados con ( E )
• Q0 se señala con ->
• El estado final se señala con * o con doble circulo

Ejemplo: Sea el AFD1 = ({a,b}, {p,q,r}, f, p, {q}) donde f está

definida por:
f(p,a) = q f(p,b) = r
f(q,a) = q f(q,b) = r
f(r,a) = r f(r,b) = r

Escribir su tabla de transición y dibujar su diagrama de transición.
estados (Q): p, q, r
estado inicial: p
estado final: q

Bibliografia:

Enrique Alfonseca Cubero, Manuel Alfonseca Cubero, Roberto Moriyón Salomón." Teoría de autómatas y lenguajes formales". McGraw-Hill (2007). Capítulos 3 y 7

http://automatas-finitos.blogspot.com/

Maigualida Pérez Melgarejo

3.2 CONVERSIÓN DE AUTÓMATA FINITO NO DETERMINISTA A AUTÓMATA FINITO DETERMINISTA.

Todo AFND estricto, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.

Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q₀>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones 

1.    A se transforma en A_AFD=<Q_A,T, g_A,F_A,q_0A>', tal que:

a.    V_A=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.

b.    F_A={x | }.

c.    g_A={<r,x,q> | }.

d.    q_0A={q₀}

2.    Luego se eliminan de A_AFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q_0A.

Ejemplo

Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>, que reconoce a las cadenas de as y bs que comienzan con cualquiera cantidad de estas letras y terminan forzosamente en ab. 

Primero se obtiene autómata derivado A_AFD=<V_AFD,T_AFD,g_AFD,F_AFD,{q0}> a partir del conjunto potencia de los estados de A donde:

·         V_AFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.

·         T_AFD={a,b}.

·         F_AFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.

Luego se retiran los estados inaccesibles {q1}, {f}, {q1,f}, {q0,q1,f}, determinados mediante la clausura de {q0}, y queda:

·         A_AFD={{q0,{q0,q1},{q0,f}},{a,b},{<{q0},b,{q0}>,<{q0},a,{q0,q1}>,<{q0,q1},a,{q0,q1}>,<{q0,q1},b,{q0,f}>,<{q0,f},a,{q0,q1}>,<{q0,f},b,{q0}>},{ {q0,f} },{q0}}.

Bibliografía:

https://www.ecured.cu/Transformaci%C3%B3n_de_aut%C3%B3mata_finito_no_determinista_a_aut%C3%B3mata_finito_determinista

Blanca Estela Reyes Castillo

3.3 REPRESENTACIÓN DE ER USANDO AFND.

ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En estas tres secciones demostraremos esto mediante convertir ER→AFND → AFD → ER. Las dos primeras conversiones son muy relevantes en la práctica, pues permiten construirverificadores o buscadores eficientes a partir de ERs.

Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas (el alumno no tiene los prerrequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”.

Este algoritmo es dirigido por sintaxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. Supongamos que N(s)y N(t)son AFND’s para las expresiones regulares sy t,

 respectivamente.

   a)   Para la expresión regular s | t(alternancia), construir el siguiente AFND, N(s|t):
  
   b)   Para la expresión regular st(concatenación), construir el AFND, N(st) :c) 

   c)   Para la expresión regular s*, construir el AFND, N(s*) :

    bibliografia

https://www.scribd.com/doc/226694899/Unidad-III-y-IV-Lenguajes-y-Automatas-i

3.4 MINIMIZACION DE ESTADOS EN UN AF.

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

Eliminar los estados inaccesibles del autómata.

Construir una tabla con todos los pares (p, q) de estados restantes.

Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):

Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto, marcar la entrada (p, q).

De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

Agrupar los pares de estados no marcados.

Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFD inicial ya era mínimo.

finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g.

Ejemplo:

Dado un AFD M = (Q, Σ, δ, q0, F), se trata de encontrar un AFD M′ con L(M) = L(M′) y tal que M′ tenga el mínimo numero de estados posible. Para ello, el método consiste en encontrar todos los estados que son equivalentes, es decir, que son indistinguibles en el autómata. Por cada clase de estados equivalentes, el autómata mínimo necesitara un solo estado.

Dados dos estados q, q′ ∈ Q, q y q ′ son indistinguibles o equivalentes si para cualquier cadena w ∈ Σ ∗ se cumple una de las dos siguientes opciones:

·         δ(q, w) ∈ F y δ(q ′ , w) ∈ F

·         δ(q, w) 6∈ F y δ(q ′ , w) ∈ F 1

El método para minimizar un autómata consiste básicamente en encontrar todos los estados que son indistinguibles entre si y sustituirlos por un único estado. Para ello lo principal es averiguar que estados son distinguibles y cuales no.

El método para saber que estados son indistinguibles es el siguiente:

a. Si hay algún estado inalcanzable eliminarlo

b. (i := 0) Marcar todos los estados que pueden distinguirse con la cadena

vacía (es decir, todos los finales se pueden distinguir de los no finales).

c. (i := i + 1) Marcar como distinguibles q y q′

si con algún a ∈ Σ tenemos δ(q, a) y δ(q′, a) dos estados que ahora son distinguibles.

d. Si en el paso anterior se han distinguido nuevos estados, entonces volver

al paso c.

Bibliografia:

John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman. "Introducción a la teoría de autómatas, lenguajes y computación" (3ª edición). Ed, Pearson Addison Wesley.

Sects. 2.1-2.2; Sects. 2.3-2.8; HMU, Chap. 4;HMU, Sects. 3-1-3.7

http://www.sc.ehu.es/jiwnagom/MAC1-ALF/MAC-archivos/Tema2-parte3.pdf

https://sites.google.com/site/tautomatasfinal/minimizacion.

Edgarda Santiago Reyes

3.5 APLICACIONES (DEFINICIÓN DE UN CASO DE ESTUDIO)

• Interruptor de luz

• Control de máquinas de bebidas

• Analizadores/generadores de palabras

• Control de las tareas de un robot

• Búsqueda y sustitución de palabras

• Tratamiento de masas de textos

• Analizadores léxicos de compiladores y traductores

• etc.

Máquina de bebidas:

1. Las bebidas cuestan 25 céntimos.

2. Monedas que admite la máquina:

1. De cuarto, 25 céntimos (Q).

2. Dimea, 10 céntimos (D).

3. Nickel, 5 céntimos (N).

3. La máquina acepta cualquier combinación

de monedas hasta 25 céntimos.

4. La máquina requiere la cantidad exacta.

Bibliografía:

http://www.sc.ehu.es/jiwnagom/MAC1-ALF/MAC-archivos/Tema2-parte3.pdf

Marisa Martínez Bautista