Análisis léxico y tablas de símbolos.

Al iniciarse el proceso de compilación, el código fuente de un programa no es más que un flujo de caracteres, así que la tarea del análisis léxico es reconocer símbolos en este flujo de caracteres y presentarlos en una representación más útil para el análisis sintáctico.

• Eliminar espacios, comentarios, etc.
• Reconocer identificadores y palabras clave.
• Reconocer constantes y numerales.
• Generar un listado para el compilador.

Antes de ocuparnos del analizador léxico mismo, haremos algunos comentarios sobre los autómatas finitos, ya que estos modelos son muy convenientes para describir la forma en que deben analizarse los símbolos de los lenguajes formales. ( Generados por gramáticas regulares).

Autómatas finitos.

Los analizadores léxicos deben reconocer componentes léxicos en un flujo de caracteres, y estos componentes son elementos de un lenguaje regular, es decir, pueden ser generados por una gramática regular. La gramática G ( T, N, P, S ) presentada a continuación es un ejemplo de una gramática regular.

EJEMPLO :

T = { a, b }

N = { A, B, C }

P = { A ® A a ½ B a

B ® C b

C ® C a ½ a }

S = { A }

Que genera el lenguaje

L ( G ) = { a^m b aⁿ ½ m, n ³ 1 }.

La frase aaba que pertenece a L ( G ) tiene la siguiente derivación:

A ® Ba

• Cba
• Caba
• Aaaba

Ahora el proceso de reconocimiento lee una frase de izquierda a derecha y la acepta como elemento del lenguaje si puede reducirla al símbolo inicial de la gramática. Esto se muestra en la figura siguiente para la frase aaabaa.

Podemos ver que por cada paso o estado hay un símbolo no terminal al principio de la frase parcialmente reducida. Cada reducción depende del símbolo no terminal actual y del siguiente carácter de entrada ( El siguiente símbolo terminal ).

Autómatas finitos deterministas.

Los modelos matemáticos de los dispositivos que aceptan una entrada y producen una salida apropiada se denominan autómatas. La característica de un autómata es que la entrada pasa por varios estados para producir la salida. Teniendo esto en cuenta, se puede establecer una correspondiente entre el mencionado problema de reconocimiento ( o análisis léxico ) y un autómata.

El autómata más simple es el autómata finito determinista ( FDA ). Haciendo referencia a Salomaa. Un FDA se describe heurísticamente como sigue:

• DEFINICIÓN:

Un FDA es un dispositivo de reconocimiento que discrimina entre palabras de entrada en un alfabeto finito como se ilustra en la figura siguiente.

Este dispositivo consta de una memoria con un conjunto finito de estados internos ( P ), entre los cuales hay un estado inicial especificado y un conjunto designado F de estados finales.

Dada una cadena a₁a₂.ka_k perteneciente a V ( la cerradura del alfabeto de entrada V ), el dispositivo comienza en el estado inicial s₀ y analiza la primera letra a₁. El estado siguiente se determina de forma única por el estado actual y la letra analizada; el estado s₁, analiza la letra a₂, pasa al estado s₀ a otro estado s₁ ( eventualmente, s₁ = s₀ ). En el estado s₁, analiza la letra a₂, pasa al estado s₂ y analiza la letra a₂, pasa al estado s₂ y analiza la siguiente letra a₃, etc., hasta llegar al extremo derecho de la palabra. Observe que en cada paso la transición al siguiente estado, s_i+1 ( 0 £ i £ k – 1 ), es determinada de forma única por el estado s_i y la letra analizada a_i+1. Una palabra de entrada a₁a₂...a_k determina entonces de manera única el estado terminal s_k. La palabra de entrada es aceptada por el autómata si s_k pertenece al conjunto designado de estados finales F; en caso contrario, la palabra es rechazada.

init (estado, leer_pos, EOT);

(*el estado es estado_inicial, leer_pos está

en el primer carácter de entrada, el fin de

texto (EOT) toma el valor cierto *)

WHILE NOT EOT DO

readch (c);

(*lee un carácter, incrementa la posición y

asigna EOT *).

siguiente_estado (c, estado);

(*cambia el estado de acuerdo con el estado

actual y c*).

END;

IF estado IN estado:final THEN

aceptar_palabra

ELSE

rechazar_palabra

END;

Algoritmo de FDA.

Un autómata de este tipo se denomina determinista si, para cada estado y carácter de entrada, el autómata tiene un solo estado de transición al cual puede cambiar (no se permiten transiciones para la entrada vacia ε). La figura anterior representa la descripción heurística antes dada como un algoritmo rudimentario. Un autómata finito se basa en las 5 entidades esenciales siguientes:

• Un conjuntos de estados P, finito y no vacio.
• El alfabeto en la entrada V;
• Una funcion de transición de estados M, que establece una correspondencia de P x V aP;
• El estado inicial o estado de partida s₀ ε P;
• Un conjunto de estados finales F ⊂ P.

Así un autómata finito A puede definirse como un quíntuplo:

A=(P, V, M, s₀, F)

Diagramas y tablas de transición.

Se puede representar un autómata gráficamente, con una especie de diagramas de transición. Los estados de los autómatas se representara con círculos marcados con el nombre del estado ( las circunferencias mas obscuras indican estados finales ). Los estados ( círculos ) se conectan por medio de arcos marcados con caracteres de entrada permitidos. Los arcos indican la transición de un estado a otro haciendo referencia a los valores de entrada específicos. En la siguiente figura se muestra la transición de un estado s₁ a un estado s₂ dependiente de la entrada a.

Una tabla de transiciones es otra forma de representar un autómata.

Gramática regulares y autómatas finitos.

Es posible diseñar un autómata finito A para cada gramática regular G. Este autómata A acepta las frases del lenguaje definido por G, es decir,

L ( G ) = L ( A ).

En la figura 3 se muestra el diagrama de transición de un autómata finito determinista que acepta el lenguaje L ( G ) = { a^m baⁿ │m, n ³ 1 }. Hay dos estados que no tienen equivalencia con el conjunto de símbolos no terminales. El estado inicial 1 que sirve exclusivamente como punto departida y el estado E, al cual solo es posible llegar si se analiza una frase incorrecta.

En la tabla 1 se muestra la tabla de transiciones del autómata de la figura 3.

Autómatas finitos no deterministas.

Si existe más de un estado de transición se llama autómata finito no determinista; en especial, se permiten transiciones para la entrada vacía Î . El ejemplo siguiente ilustrara está situación. Considere el autómata A₁ de la tabla 2.

El estado inicial es X y el final Y. Podemos ver que al estar en el estado X y leer una entrada 1 podemos cambiar al estado Y o permanecer en el estado X. El autómata A1 solo acepta frases que comienzan con 1; no hay transición de X al leer un 0.

La frase 1,1 será aceptada por que hay una secuencia de transiciones hasta el estado final Y. Sin embargo, también hay una secuencia de transiciones donde podemos permanecer en el estado inicial X, que no es un elemento del conjunto de estados finales.

Para construir un FDA a partir un FNA, suponemos que cada estado del FDA corresponde a un conjunto de FNA. El estado inicial s0 del FDA corresponde a un conjunto s 0 de estado del FNA, que contiene el estado inicial del FNA y todos los estados a los que se puede llegar desde este estado inicial si la entrada es Î .

Analizador Léxico.

El analizador léxico y el analizador sintáctico ( en este caso, suponemos que el analizador léxico actúa como servidor de analizador sintáctico ). El analizador léxico lee caracteres de entrada

( el código fue: te ) y produce secuencias de símbolos y valores de símbolos que son analizados sintácticamente por el analizador sintáctico. Por consiguiente, el proceso de análisis léxico o de reconocimiento pueden entenderse como la transformación de un flujo de caracteres en un flujo de símbolos "reducidos" . En este caso el término reducido significa que la entrada es filtrada para eliminar aquellos elementos del texto del programa que solo sirven para ser legible el programa.

Significa que la entrada es filtrada para eliminar aquellos elementos del texto del programa que sólo sirvan para hacer legible el programa.

Números.

El analizador léxico debe transformar un numeral en el símbolo del numeral y su valor. Esto puede lograrse, por ejemplo, con el algoritmo para números enteros.

Núm := 0; símbolo := numeral;

WHILE ch IN Dígitos DO

digito := ORD ( ch ) – ORD ( 0 ) ;

IF núm < = ( MaxInt – digito ) DIV 10 THEN

Núm := núm * 10 + dígito;

Readch ( ch );

ELSE

núm := 0;

Error ( … ) ( * saltar los dígitos restantes * )

END;

END;

Reconocimiento de numerales.

El algoritmo contiene la constante MaxInt que representa el mayor entero posible en un computador especifico. Se usa para evitar desbordamientos.

Tablas de símbolos.

Una de símbolos es una estructura de información para manejar los nombres ( identificadores y palabras reservadas ) del código fuente. Se usa durante la comprobación semántica o dependiente del contexto, además del proceso de generación de código. La información almacenada en la tabla será completada durante las fases de análisis y luego se empleará en la generación de código. En general una tabla de símbolos consta de nombres y atributos.

La información almacenada en una tabla de símbolos varía de un compilador a otro y de un lenguaje a otro; es decir, la información que se incluirá en una tabla de símbolos depende del lenguaje y del diseñador del compilador.

Por supuesto, el campo nombres contiene los nombres ( identificadores ), mientras que los atributos pueden ser, entre otros:

• Tipo o valor de un nombre, o ambos;
• La dimensión o el número de parámetros de un procedimiento;
• Un apuntador al lugar donde se declara y referencia un nombre;
• Algún tipo de dirección, por lo regular un desplazamiento;

Si un nombre en una tabla de símbolos se refiere a una constante, es necesario almacenar el tipo y el valor de la constante. Los apuntadores al lugar donde se declara y referencia un nombre pueden apoyar la generación de listados de errores, mientras que la información del alcance sólo será necesaria en lenguajes orientados a bloques que permiten la declaración del mismo nombre en distintos bloques.

Análisis léxico de PL/0

Para diseñar un analizador léxico de PL/0 se emplea un autómata finito, como se le definió anteriormente. Representa un diagrama de transición rudimentario del autómata que reconoce los símbolos del lenguaje PL/0.

El analizador léxico debe reconocer los siguientes símbolos:

• Palabras reservadas.
• Nombres de identificadores.
• Numerales y
• Operadores.