Introducción a los Compiladores Definición y Conceptos Básicos.

Introducción a los Compiladores Definición y Conceptos Básicos.

Análisis léxico

Autómatas Finitos

Un analizador léxico o analizador lexicográfico (en inglés scanner) es la primera fase de un compilador, consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción, siendo la entrada para el analizador sintáctico (en inglés parser).

La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas que definen el léxico. Estas reglas consisten comúnmente en expresiones regulares que indican el conjunto de posibles secuencias de caracteres que definen un token o lexema.

En algunos lenguajes de programación es necesario establecer patrones para caracteres especiales (como el espacio en blanco) que la gramática pueda reconocer sin que constituya un token en sí.

¿Qué es un token?

Es una agrupación de caracteres reconocidos por el analizador léxico que constituyen los

símbolos con los que se forman las sentencias del lenguaje.

Lo que el analizador léxico devuelve al analizador sintáctico es el nombre de ese símbolo junto

con el valor del atributo (si ese token lo necesita, ya que no todos los tokens llevan atributo,

como por ejemplo: una palabra reservada "if").

Ventajas de contar con un analizador léxico:

1) Se simplifica el diseño, puesto que hay una herramienta

especializada en el tratamiento del fichero que contiene el

código fuente.

2) Aumenta la portabilidad del compilador, pudiendo tenerse

versiones diferentes para distintos formatos del texto de

código fuente (ASCII, EBCDIC, etc.).

3) Mejora la eficiencia al ser una herramienta especializada

en el tratamiento de caracteres.

4) Detección de determinados errores fáciles de corregir a

este nivel (5.25 por 5,25).

Funciones del Analizador Léxico

1) Convierte el programa fuente en una cadena de tokens

2) Para reconocer el token usa un patrón, una regla que describe cómo se forman las cadenas que corresponden a un token.

3) Salta comentarios y espacios en blanco (tabuladores,

saltos de línea...)

4) Tener el registro de la línea del archivo fuente que está

siendo analizada

5) Genera mensajes de error léxico, y se recupera del error

6) Convierte los valores literales al tipo que corresponda

7) Si la entrada debe obedecer a un formato, verifica el

formato Ej. Fortran, Cobol

8) Pontificia U. Javeriana Cali - Ingeniería de Sistemas y Co

Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un

lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto

de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El

autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a los

símbolos de x conduce desde el estado inicial a un estado final.

Si para todo estado del autómata existe como máximo una transición definida para cada

símbolo del alfabeto, se dice que el autómata es determinístico (AFD). Si a partir de algún

estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el

autómata es no determinístico (AFND).

Este modelo está conformado por un alfabeto, un conjunto de estados finito, una función de transición, un estado inicial y un conjunto de estados finales. 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.

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:

Q: es un conjunto finito de estados;

Σ: es un alfabeto finito;

q0 ∈ Q: es el estado inicial;

δ:Q x Σ-> Q: es una función de transición;

F C Q: es un conjunto de estados finales o de aceptación.

Lenguaje de un AFD

Llamamos lenguaje del autómata finito determinista A, L(A), al conjunto de palabras para las cuales el autómata llega a un estado de aceptación.

Si empleamos la función de transición extendida (definida más adelante), podemos definir el lenguaje como L(A):={w∈Σ∗ ∶ ˆδ(q0,w)∈F}