4.1 Aspectos generales de un analizador léxico
El analizador léxico es la primera fase de un compilador.
Su principal función consiste en 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 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.
Como el analizador léxico es .la parte del compilador que lee el texto fuente. También puede realizar 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 os 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.
4.2 Autómatas finitos
Una maquina de estado finito o autómata finito, es un modelo computacional que consiste de
un conjunto de estados, un estado de inicio, un alfabeto de entrada y una función de transición
que traza un mapa a un siguiente estado, a partir del símbolo de entrada y el estado actual.
En particular, los autómatas finitos se pueden utilizar para describir el proceso de
reconocimiento de patrones en cadenas de entrada. El sistema recibe una cadena constituida
por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que ese autómata
reconoce. De esta manera se pueden construir analizadores léxicos, construyendo programas
de computadora que realicen las operaciones de un autómata.
Es claro que existe una fuerte relación entre los autómatas y las expresiones regulares,
Grafos y árboles
Un grafo, consiste en un conjunto finito de vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones entre los elementos de un conjunto.
La imagen es una representación del siguiente grafo:
V:={1,2,3,4,5,6}
E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1~2.
Un árbol es un dígrafo que posee las siguientes propiedades:
Existe un vértice, llamado raíz, que no tiene predecesores y del cual parte una trayectoria hacia cada vértice.
Cada vértice, diferente de la raíz, tiene exactamente un predecesor.
Los sucesores de cada vértice están ordenados a partir de la izquierda.
Se deben de dibujar los árboles con la raíz en la cima y todos los arcos apuntando hacia abajo. Las flechas de los arcos, por tanto, no necesitan indicar la dirección y no se indicará. Los sucesores de cada vértice se dibujarán de izquierda a derecha. El siguiente ejemplo es el diagrama de la oración "La rápida zorra saltó sobre el perro perezoso.
4.3 Clases, estados y tokens
¿Que es un token?
También llamado componente léxico.
es una cadena de caracteres que tiene un
significado coherente en cierto lenguaje de
programación.
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.
Son los elementos en que el preprocesado
desmenuza el código fuente. En un lenguaje
de programación, los tokens son el
equivalente a las palabras y signos de
puntuación en el lenguaje natural escrito. Los
tokens están separados por elementos de
separación que reciben el nombre genérico de
separadores.
¿Qué son las Clases?
Es una construcción que permite crear tipos
personalizados propios mediante la
agrupación de variables de otros tipos,
métodos y eventos. Una clase es como un
plano. Define los datos y el comportamiento
de un tipo.
Las clases se declaran mediante la palabra
clave class:
C#
Public class Customer
{ //Fields, properties, methods and events
go here...
}
¿Qué son los Estados?
El estado de un programa es el producto de
su entorno y su memoria.
Define sencillamente el estado de un
programa como un conjunto de pares (v, val)
que representan todas las variables activas y
sus valores asignados actualmente en alguna
etapa durante la ejecución del programa.
4.3 Matriz de transición
de estados y matriz de salidas
una tabla de transición de estados es una tabla que muestra qué estado se moverá un autómata finito dado, basándose en el estado actual y otras entradas. Una tabla de estados es esencialmente una tabla de verdad en la cual algunas de las entradas son el estado actual, y las salidas incluyen el siguiente estado, junto con otras salidas.
Una tabla de estados es una de las muchas maneras de especificar una máquina de estados, otras formas son un diagrama de estados, y una ecuación característica.
Cuando se trata de un autómata finito no determinista, entonces la tabla de transición muestra todos los estados que se moverá el autómata.
Tablas de estados de una dimensión
También llamadas tablas características, las tablas de estados de una dimensión son más como tablas de verdad que como las versiones de dos dimensiones. Las entradas son normalmente colocadas a la izquierda, y separadas de las salidas, las cuales están a la derecha. Las salidas representarán el siguiente estado de la máquina. Aquí hay un ejemplo sencillo de una máquina de estados con dos estados, y dos entradas combinacionales:
A B Estado Actual Siguiente Estado Salida
0 0 S1 S2 1
0 0 S2 S1 0
0 1 S1 S2 0
0 1 S2 S2 1
1 0 S1 S1 1
1 0 S2 S1 1
1 1 S1 S1 1
1 1 S2 S2 0
S1 y S2 representarían probablemente los bits individuales 0 y 1, dado que un simple bit solo tiene dos estados.
Tablas de Estados de dos dimensiones
Las tablas de transición de estados son normalmente tablas de dos dimensiones. Hay dos formas comunes para construirlas.
La dimensión vertical indica los Estados Actuales, la dimensión horizontal indica eventos, y las celdas (intersecciones fila/columna) de la tabla contienen el siguiente estado si ocurre un evento (y posiblemente la acción enlazada a esta transición de estados).
Tabla de Transición de Estados
Events
State E1 E2 ... En
S1 - Ay/Sj ... -
S2 - - ... Ax/Si
... ... ... ... ...
Sm Az/Sk - ... -
(S: estado, E: evento, A: acción, -: transición ilegal)
La dimensión vertical indica los Estados Actuales, la dimensión horizontal indica los siguientes estados, y las intersecciones fila/columna contienen el evento el cual dirigirá al siguiente estado particular.
Tabla de Transición de Estados
next
current S1 S2 ... Sm
S1 Ay/Ej - ... -
S2 - - ... Ax/Ei
... ... ... ... ...
Sm - Az/Ek ... -
(S: estado, E: evento, A: acción, -: transición imposible)
Ejemplo
Un ejemplo de una tabla de transición de estados para una máquina M junto con el correspondiente diagrama de estados está dado abajo.
Tabla de Transición de Estados
Entrada
Estado 1 0
S1 S1 S2
S2 S2 S1
Diagrama de estados
DFAexample.svg
Todas las entradas posibles a la máquina están enumeradas a través de las columnas de la tabla. Todos los estados posibles están enumerados a través de las filas. Desde la tabla de transición de estados anterior, es fácil ver que si la máquina está en S1 (la primera fila), y la siguiente entrada es el carácter 1, la máquina permanecerá en S1. Si llega un carácter 0, la máquina realizará la transición a S2 como puede verse desde la segunda columna. En el diagrama esto es denotado por la flecha desde S1 a S2 etiquetada con un 0.
Para un autómata finito no determinista (AFND), una nueva entrada puede causar que la máquina esté en más de un estado, dado que es no determinista. Esto se denota en una tabla de transición de estados por un par de llaves { } con un conjunto de todos los estados objetivo entre ellos. Se da un ejemplo abajo.
Tabla de Transición de Estados para un AFND
Entrada
Estado 1 0 ε
S1 S1 { S2, S3 } Φ
S2 S2 S1 Φ
S3 S2 S1 S1
Aquí, una máquina no determinista en el estado S1 leyendo una entrada de 0 causará que esté en dos estados al mismo tiempo, los estados S2 y S3. La última columna define la transición legal de estados del carácter especial, ε. Este carácter especial permite a los AFND moverse a un estado diferente cuando no hay ninguna entrada. En el estado S3, el AFND puede moverse a S1 sin consumir ningún carácter de entrada. Los dos casos anteriores configuran al autómata finito no determinista.
4.5. Elaboración del SCANNER
Análisis léxico (Scanner)
La fase de rastreo (scanner), tiene las funciones de leer el programa fuente como un archivo de
caracteres y dividirlo en tokens. Los tokens son las palabras reservadas de un lenguaje,
secuencia de caracteres que representa una unidad de información en el programa fuente. En
cada caso un token representa un cierto patrón de caracteres que el analizador léxico
reconoce, o ajusta desde el inicio de los caracteres de entrada. De tal manera es necesario
generar un mecanismo computacional que nos permita identificar el patrón de transición entre
los caracteres de entrada, generando tokens, que posteriormente serán clasificados. Este
mecanismo es posible crearlo a partir de un tipo especifico de maquina de estados llamado
autómata finito.
Comentarios
Publicar un comentario