Análisis lexicográfico

Traductores, Compiladores e Intérpretes

1

Análisis lexicográfico

Este capítulo estudia la primera fase de un compilador, es decir su análisis lexicográfico, o más concisamente análisis léxico. Las técnicas utilizadas para construir analizadores léxicos también se pueden aplicar a otras áreas, como, por ejemplo, a lenguajes de consulta y sistemas de recuperación de información. En cada aplicación, el problema de fondo es la especificación y diseño de programas que ejecuten las acciones activadas por palabras que siguen ciertos patrones dentro de las cadenas a reconocer. Como la programación dirigida por patrones es de mucha utilidad, se introduce un lenguaje de patrón-acción, llamado LEX, para especificar los analizadores léxicos. En este lenguaje, los patrones se especifican por medio de expresiones regulares, y un compilador de LEX puede generar un reconocedor de las expresiones regulares mediante una autómata finito eficiente.

Por otro lado, una herramienta software que automatiza la construcción de analizadores léxicos permite que personas con diferentes conocimientos utilicen la concordancia de patrones en sus propias áreas de aplicación.

¿Que es un analizador léxico?

Se encarga de buscar los componentes léxicos o palabras que componen el programa fuente, según unas reglas o patrones. La entrada del analizador léxico podemos definirla como una secuencia de caracteres.

Usa una gramática (N, T, P, S)

Secuencia de caracteres

l=» LÉXICO

Secuencia de Terminales

£> SINTÁCTICO

Árbol Sintáctico

gramática (N, T, P, S)

N C> Símbolos no terminales. T C> Símbolos terminales P C> Reglas de producción S C> Axioma inicial

El analizador léxico tiene que dividir la secuencia de caracteres en palabras con significado propio y después convertirlo a una secuencia de terminales desde el punto de vista del analizador sintáctico, que es la entrada del analizador sintáctico.

El analizador léxico reconoce las palabras en función de una gramática regular de manera que sus NO TERMINALES se convierten en los elementos de entrada de fases posteriores. En LEX, por ejemplo, esta gramática se expresa mediante expresiones regulares.

2

Funciones del 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 “Dame 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.

Dame el siguiente componente léxico

Programa Fuente

Analizador léxico

Toma

componente

léxico

Analizador sintáctico

Tabla de símbolo

Figura 2 Interacción de un analizador léxico con el analizador sintáctico Otras funciones que realiza :

• Eliminar los comentarios del programa.

• Eliminar espacios en blanco, tabuladores, retorno de carro, etc, y en general, todo aquello que carezca de significado según la sintaxis del lenguaje.

• Reconocer los identificadores de usuario, números, palabras reservadas del lenguaje, ..., y tratarlos correctamente con respecto a la tabla de símbolos (solo en los casos que debe de tratar con la tabla de símbolos).

• Llevar la cuenta del número de línea por la que va leyendo, por si se produce algún error, dar información sobre donde se ha producido.

• Avisar de errores léxicos. Por ejemplo, si @ no pertenece al lenguaje, avisar de un error.

• Puede hacer funciones de preprocesador.

Análisis Lexicográfico

Traductores, Compiladores e Intérpretes

3

Necesidad del analizador léxico

Un tema importante es el porqué se separan los dos análisis lexicográfico y sintáctico, en vez de realizar sólo el análisis sintáctico, del programa fuente, cosa perfectamente posible aunque no plausible. Algunas razones de esta separación son:

• Un diseño sencillo es quizás la consideración más importante. Separar el análisis léxico

del análisis sintáctico a menudo permite simplificar una u otra de dichas fases. El analizador léxico nos permite simplificar el analizador sintáctico.

Agrupar o no -, +, *, / bajo el terminal OPARIT

> NUM (terminal)

LEXICOGRÁFICO

(0 | 1 | 2

SINTÁCTICO

Opción 1:

S ->NUM OPARIT NUM

OPARIT -* MAS|MENOS|DIV|MULT

Opción 2:

S-> NUM MAS NUM | NUM MENOS NUM ¡ NUMDIVNUM I NUMMULTNUM

Si el sintáctico tuviera la gramática de la Opción 1 , el lexicográfico sería:

Opción 1:

( 0 | 1 | 2 | ... | 9) + l= (“+” | “-” | ”*“ | ”/“) c

=:> NUM =:> OPARIT

Si en cambio el sintáctico toma la Opción 2, el lexicográfico sería:

Opción 2:

=:> NUM

^> MAS ^> MENOS ::> MULT DIV

( 0 | 1 | 2 | ... | 9) + c

1 “ *” ,

Es más, si ni siquiera hubiera análisis léxico, el propio análisis sintáctico vería incrementado su número de reglas:

Análisis Lexicográfico

NUM ■> 0

| 1 | 2 | 3

....

| NUM NUM

Traductores, Compiladores e Intérpretes

4

A modo de conclusión, diremos que tenemos dos gramáticas, una que se encarga del análisis léxico y otra que se encarga del análisis sintáctico. ¿Que consideramos componente básico?, ¿Donde ponemos el punto divisor de qué se encarga cada gramática?. Si las divisiones se hacen muy pequeñas estamos complicando la gramática, por ejemplo, en la opción 2, la gramática sintáctica se nos complica un poco. Seguiremos dos reglas para que no se nos complique. La primera es que tendremos que hacer divisiones de forma que no perdamos información, esto quedará más claro en capítulos posteriores, y nos veremos ayudados por el concepto de atributo. La segunda es que por regla general el analizador lexicográfico debe de encargarse de la parte que involucra una gramática

...