Automatas

ANÁLISIS LÉXICO Y AUTÓMATAS

INTRODUCCIÓN
Para hablar de autómatas, primero debemos hacer una introducción al análisis léxico y la construcción de analizadores léxicos.
Según Aho en su libro Compiladores principios técnicas y herramientas, "Una forma sencilla de crear un analizador léxico consiste en la construcción de un diagrama que ilustre la estructura de los componentes léxicos dellenguaje fuente, y después hacer la traducción "a mano" del diagrama a un programa para encontrar los componente léxicos."1
En nuestro curso, el anterior párrafo describe la técnica que llevaremos a cabo para hacer un analizador léxico-sintáctico de un pequeño lenguaje matemático que inventaremos.
Arriba    Presentación

FUNCIÓN DEL ANALIZADOR LÉXICO
Como ya se ha dicho en otras lecturas de estesitio, el análisis léxico o lineal (también llamado scanner), es la primera de las fases de la etapa de análisis de un proceso de compilación y su objetivo es reconocer y clasificar todas las palabras o mejor conocidos como  componentes léxicos (o tokens) de un código fuente. Para esto, el analizador léxico debe leer el código fuente caracter a caracter y entonces, irá armando uno a uno loscomponentes léxicos que después entregará al analizador sintáctico. Cuando el analizador sintáctico le envía la orden de obtener el siguiente componente léxico, el analizador lee los caracteres de entrada hasta identificar el token.
 

Figura 1. Interacción de un analizador léxico con el analizador sintáctico
El analizador léxico como parte del compilador, puede hacer otras tareas secundarias comoson, eliminar del programa fuente comentarios y espacios en blanco, así como relacionar los mensajes de error del compilador con el programa fuente
Componentes léxicos, patrones y lexemas
Estos tres nombres tienen significado específico en análisis sintáctico. En general hay un conjunto de cadenas de entrada para el cual se produce como salida el mismo componente léxico. Este conjunto de cadenasse construye mediante una regla llamada patrón asociado al componente léxico. Se dice que el patrón concuerda con cada cadena del conjunto. Un lexema es una secuencia de caracteres en el programa fuente con la que concuerda el patrón para un componente léxico. Por ejemplo, en la proposición de Pascal
                     const PI=3.1416;
la subcadena PI es un lexema para el componente léxico"Identificador"
Componente Léxico | Lexemas de Ejemplo | Descripción Informal del Patrón |
const | const | const |
if | if | if |
relación | <,<=,=,<>,>,>= | < o <= o = o <> o > o >= |
id | PI, cuenta, d2 | letra seguida de letras o dígitos |
num | 3.1416, o, 6.02E-23 | cualquier constante numérica |
literal | "Hola mundo", 'c', TRUE | cualquiercadena entre " y " excepto " o cualquier caracter entre ' y ', excepto ' olos valores TRUE o FALSE |
Tabla 1. Ejemplo de componentes léxicos
Los componentes léxicos se tratan como símbolos terminales de la gramática del lenguaje fuente, con nombres en negrilla para representarlos. Los lexemas para el componente léxico que concuerdan con el patrón representan cadenas de caracteres en el programafuente que se pueden tratar juntos como una unidad léxica.
En la mayoría de lenguajes de programación, se consideran componentes léxicos las siguientes construcciones: palabras claves, operadores, identificadores, constantes, cadenas literales y signos de puntuación.
Un patrón es una regla que describe el conjunto de lexemas que pueden representar a un determinado componente léxico en los programasfuente.
En muchos lenguajes, ciertas cadenas son reservadas, es decir, su significado está predefinido y el usuario no lo puede modificar. Si las palabras claves no son reservadas, entonces el analizador léxico debe distinguir entre una palabra clave y un identificador definido por el usuario.
Atributos de componentes léxicos
Cuando concuerda con un componente léxico más de un patrón, el...