Download Algoritmo para Convertir una Expresión Regular en un

Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
Capítulo 3: Algoritmos Usados por el Generador de Autómatas
Finitos Determinísticos
3.1
Introducción
En este capítulo se presentan los algoritmos usados por el generador de
autómatas finitos determinísticos que sirve como base principal para la
construcción de un analizador lexicográfico.
A diferencia del capítulo 2, en este capítulo se documenta en detalle
cada aspecto de los algoritmos, y se incluyen ejemplos que clarificarán su
funcionamiento.
Durante su lectura no se debe olvidar que el tratamiento de lenguajes
con expresiones regulares es un caso especial de análisis sintáctico
(implícitamente se está trabajando con una gramática del Tipo 3), al que
comúnmente se lo denomina análisis lexicográfico. La teoría aquí presentada
se puede aplicar a muchas áreas de la ciencia, y no sólo al análisis
lexicográfico.
3.2
Arbol Sintáctico para una Expresión Regular
3.2.1 Descripción
Se construirá un árbol sintáctico para la expresión regular a partir del
análisis sintáctico de la misma.
Como ya se sabe, en un árbol hay 2 tipos de nodos: nodos hojas y nodos
que no son hojas que aquí representarán operaciones. En un árbol sintáctico de
una expresión regular los nodos hojas representarán un caracter (o símbolo
terminal) que aparece en el texto fuente, el resto de los nodos representarán
operaciones con ellos.
El lenguaje para expresiones regulares con el que trabajaremos es el que
se presenta en la sección 10.3. En la misma se definen 5 operaciones, lo que
nos da 6 tipos de nodos posibles a saber:
1. Nodo hoja: se representa con un círculo y dentro del mismo el caracter
que hay en esa posición.
19
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
2. Nodo concatenación: se representa con un círculo con un punto adentro.
3. Nodo disyunción: se representa con un círculo con un | adentro.
4. Nodo asterisco: se representa con un círculo y un * adentro.
5. Nodo opcional: se representa con un círculo y un ? adentro.
6. Nodo uno o más: se representa con un círculo y un + adentro.
El árbol puede ser construido trabajando con cualquier técnica de
análisis sintáctico que permita construir el árbol sintáctico respetando el orden
de examen de los terminales de izquierda a derecha (puede ser LL(k) o LR(k)).
Ejemplo: sea la expresión regular la siguiente:
( '+' | '-' ) ? d +
El árbol sintáctico sería:
.
?
+
d
|
'+'
'-'
Fig. 3 Arbol sintáctico para ( '+' | '-' ) ? d +
A los efectos de poder implementar los algoritmos de generación se
trabaja con la expresión regular aumentada "ExpReg #" donde el numeral (#)
significa fin de la expresión regular. Al construir el árbol sintáctico para la
expresión regular aumentada, el nodo raíz del árbol será un nodo
concatenación el cual tendrá como subárbol izquierdo el árbol sintáctico
construido y como subárbol derecho la hoja etiquetada con #. Para el ejemplo
20
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
dado se tendrá:
.
.
?
#
+
4
d
|
3
'+'
'-'
1
2
Fig. 4 Arbol sintáctico para ( '+' | '-' ) ? d + #
En el árbol sintáctico presentado en la figura 4 se muestran las hojas
numeradas de 1 a N. La numeración de las hojas se realizará por el orden de
aparición de las mismas en la expresión regular.
3.2.2 Funciones aplicables a nodos de un árbol sintáctico
Definiremos 4 funciones que operan sobre nodos de un árbol sintáctico
construido para una expresión regular dada: Anulable, PrimeraPos, UltimaPos
y SiguientePos. El sufijo Pos significa posición del árbol. Las funciones
devuelven algún valor referente a esa posición del árbol.
La función Anulable devuelve como resultado Verdadero o Falso. Es
recursiva por definición y se la caracteriza por medio de la siguiente tabla:
21
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
Tipo de nodo
Hoja con número i
Anulable(Nodo)
Falso
.
Anulable(si) y Anulable(sd)
si
sd
|
Anulable(si) o Anulable(sd)
si
sd
*
Verdadero
s
+
Anulable(s)
s
?
s
Verdadero
Fig. 5 Función Anulable
Las funciones PrimeraPos y UltimaPos son también recursivas.
Devuelven como resultado un conjunto cuyos elementos son los números de
las hojas siguientes a la posición actual. Las funciones quedan caracterizadas
mediante la siguiente tabla:
22
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
Tipo de nodo
PrimeraPos(Nodo)
Hoja con número i
.
si
sd
UltimaPos(Nodo)
{i}
{i}
Si Anulable(sd) Entonces
Si Anulable(si) Entonces
PrimeraPos(si) U PrimeraPos(sd) UltimaPos(sd) U UltimaPos(si)
Sino UltimaPos(sd)
Sino PrimeraPos(si)
|
PrimeraPos(si) U PrimeraPos(sd) UltimaPos(sd) U UltimaPos(si)
si
sd
*
PrimeraPos(s)
UltimaPos(s)
PrimeraPos(s)
UltimaPos(s)
PrimeraPos(s)
UltimaPos(s)
s
+
s
?
s
Fig. 6 Funciones PrimeraPos y UltimaPos
La función SiguientePos se calcula únicamente para los nodos hoja,
pero su cálculo requiere el completo recorrido del árbol sintáctico. Se define
por las dos reglas siguientes:
1. Si n es un nodo concatenación con subárbol izquierdo si y subárbol
derecho sd, e i es una posición dentro de UltimaPos(si), entonces todas
las posiciones de PrimeraPos(sd) están en SiguientePos(i).
2. Si n es un nodo asterisco e i es una posición dentro de UltimaPos(n),
entonces todas las posiciones de PrimeraPos(n) están en SiguientePos(i).
Ejemplo: para el ejemplo dado (ver figura 4) tenemos:
Funciones PrimeraPos y UltimaPos:
Para el nodo disyunción:
PrimeraPos( | ) = { 1, 2 }
UltimaPos( | ) = { 1, 2 }
23
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
Para el nodo opcional:
PrimeraPos( ? ) = { 1, 2 }
UltimaPos( ? ) = { 3 }
Para el nodo concatenación de más a la izquierda:
PrimeraPos( . ) = { 1, 2, 3 }
UltimaPos( . ) = { 3 }
Para el nodo concatenación raíz:
PrimeraPos( . ) = { 1, 2, 3 }
UltimaPos( . ) = { 4 }
Las funciones SiguientePos(i) para cada hoja son:
SiguientePos(1) = { 3 }
SiguientePos(2) = { 3 }
SiguientePos(3) = { 3, 4 }
SiguientePos(4) = { }
3.3
Construcción de un AFD a partir de una expresión regular
3.3.1 Construcción del AFD
La construcción de un autómata finito determinístico (AFD) a partir de
una expresión regular se realiza mediante el siguiente procedimiento:
1. Construir el árbol sintáctico para la expresión regular aumentada
ExpReg #, donde # es un marcador de final que se añade a ExpReg y
que difiere de los caracteres que pueden aparecer en ExpReg (no debe
estar dentro del conjunto de terminales).
2. Calcular las funciones Anulable, PrimeraPos, UltimaPos y SiguientePos
haciendo recorridos en profundidad del árbol.
3. Construir EstadosD (la letra D por Determinístico), el conjunto de
estados del AFD, por medio del procedimiento descripto en el punto
siguiente. Los estados dentro de EstadosD son conjuntos de posiciones;
al principio, cada estado está "no marcado", y un estado se convierte en
24
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
"marcado" justo antes de considerar sus transiciones de salida. El estado
inicial del AFD es PrimeraPos(raíz), y los estados de aceptación son
todos los que contienen la posición asociada con el marcador #.
3.3.2 Cálculo del conjunto de estados y de la tabla de transiciones
El procedimiento de cálculo del conjunto de estados y de la tabla de
transiciones del autómata finito determinístico para la expresión regular es el
que se muestra en la figura siguiente:
Al principio, el único estado no marcado en EstadosD es PrimeraPos(raíz), donde raíz
es la raíz del árbol sintáctico construido para ExpReg #.
Mientras haya un estado E sin marcar en EstadosD hacer
Marcar E
Para cada símbolo de entrada a hacer
sea U el conjunto de posiciones que están en
SiguientePos(p) para alguna posición p en E, tal que el
símbolo en la posición p es a.
Si U no está vacío y no está en EstadosD entonces
Añadir U como estado no marcado a EstadosD.
Transición[E, a] = U.
Sino Transición[E, a] = no definida
FinPara
FinMientras
Fig. 7 Algoritmo para la construcción del conjunto de estados y
la tabla de transiciones para el AFD de la expresión
regular.
3.3.3 Ejemplo de construcción del AFD a partir de la expresión regular
Para la expresión regular utilizada en los puntos precedentes tenemos
los siguientes pasos:
1. Inicialmente EstadosD = { {1, 2, 3} }.
El único estado del conjunto está sin marcar.
25
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
2. Sea E = { 1, 2, 3 } el estado actual, al que luego se le dará el número 0:
U'+' = { 3 }
Transición[ {1, 2, 3}, '+' ] = { 3 }
U'-' = { 3 }
Transición[ {1, 2, 3}, '-' ] = { 3 }
Ud = { 3, 4 }
Transición[ {1, 2, 3}, d ] = { 4, 3 }
EstadosD = { {1, 2, 3}0, {3}, {3, 4} }
3. Sea E = { 3 } el estado actual, al que luego se le dará el número 1:
U'+' = { }
Transición[ {3}, '+' ] = no definido
U'-' = { }
Transición[ {3}, '-' ] = no definido
Ud = { 3, 4 }
Transición[ {3}, d ] = { 3, 4 }
EstadosD = { {1, 2, 3}0, {3}0, {3, 4} }
4. Sea E = { 3, 4 } el estado actual, al que luego se le dará el número 2:
U'+' = { }
Transición[ {3, 4}, '+' ] = no definido
U'-' = { }
Transición[ {3, 4}, '-' ] = no definido
Ud = { 3, 4 }
Transición[ {3, 4}, d ] = { 3, 4 }
EstadosD = { {1, 2, 3}0, {3}0, {3, 4}0 }
5. No hay más estados sin marcar, por lo tanto termina la iteración.
Los estados (conjunto de posiciones siguientes) fueron numerados de 0
a n-1, donde n es el cardinal del conjunto EstadosD.
Hay un solo estado final y es el {3, 4} (al que se le dio el número 2),
puesto que es el que contiene la posición que corresponde al #, que fue
numerada con 4. El conjunto de estados finales queda así:
Estados Finales = { {3, 4} }
La tabla de transiciones de estados para el autómata finito determinístico
que reconoce cadena de caracteres con la estructura " ( '+' | '-' ) ? d +" es la
siguiente:
Estado
0
1
2
'+'
1
no definido
no definido
'-'
1
no definido
no definido
d
2
2
2
La gráfica del autómata finito determinístico para el ejemplo dado es:
26
Algoritmos Usados por el Generador de Autómatas Finitos Determinísticos
0
d
d
'+' / '-'
1
2
d
Fig. 8 Autómata finito determinístico construido para la
expresión regular ( '+' | '-' ) ? d +
3.4
Funcionamiento de un autómata finito determinístico
El siguiente procedimiento ilustra el funcionamiento de un autómata
finito determinístico:
EstadoActual = 0;
Buscar un caracter de entrada y guardarlo en c
Hacer
Si c no es FinDeArchivo entonces
EstadoNuevo = Transición[EstadoActual, c];
Buscar un caracter de entrada y guardarlo en c
Si EstadoNuevo es un estado del autómata entonces
EstadoActual = EstadoNuevo;
FinSi
FinSi
Mientras EstadoActual sea igual a EstadoNuevo;
Si EstadoActual es un elemento del conjunto de estados finales entonces
La cadena de entrada leída hasta este momento cumple con la
expresión regular.
FinSi
Fig. 9 Algoritmo para el funcionamiento de un Autómata Finito
Determinístico.
27
Algoritmos usados por el Generador de Analizadores Sintácticos
Capítulo 4: Algoritmos usados por el Generador de Analizadores
Sintácticos
4.1
Introducción
En este capítulo se presentan los algoritmos usados por el Generador de
Analizadores Sintácticos SLR. Se tratará de clarificar bien los conceptos
teóricos utilizados, lo que no hace la bibliografía que se utilizó (luego de la
lectura de la bibliografía, en el mejor de los casos quedan muchos conceptos
flotando y sin relación alguna, y lo más común es que no se los entienda).
Los analizadores sintácticos generados trabajan con la técnica SLR(1) o
SLR para simplificar, la que es un caso especial de LR(k). A diferencia de la
técnica LR(1) canónica y de la técnica LALR, esta técnica genera tablas
mucho más pequeñas (se minimiza el número de estados del autómata de pila).
Se la puede aplicar a casi todas las gramáticas de contexto libre que pueda
necesitar un programador (el desarrollo de lenguajes de programación con
gramáticas complejas puede requerir trabajar con la técnica LALR, pero si la
técnica SLR es aplicable entonces el analizador será más eficiente).
La técnica LR ha sido descripta por Knuth [1965], pero no resultó
práctica porque el tamaño de las tablas que se debían construir eran demasiado
grandes (recordar que en ese tiempo 16 kbytes era mucha memoria). En 1969
Korenjak mostró que mediante esa técnica se podían producir analizadores
sintácticos de tamaño razonable para las gramáticas de los lenguajes de
programación. En 1969 y 1971, DeRemer inventó los métodos "LR simples"
(SLR por Simple LR) y "LR con símbolo de anticipación" (LALR por
lookahead-LR) que son más simples que los de Korenjak.
La utilización de la técnica SLR (y del resto de las LR) simplifica
mucho el trabajo del desarrollo de un traductor, siempre y cuando se disponga
de un programa generador de las tablas de análisis sintáctico. Si no se dispone
de un generador de las tablas, la construcción de las mismas puede llegar a
desalentar la construcción del traductor puesto que se requiere un dominio
profundo de los algoritmos de construcción y de la teoría en la que se basan.
Una persona puede entender bien los algoritmos de construcción de las tablas,
y aún así cometer muchos errores.
28