Analisis y
Diseño de un Analizador Sintáctico
Se
desea implementar un analizador léxico y sintáctico de un pequeño subconjunto
del lenguaje de consulta de Bases de Datos SQL. Como sabé una sentencia de este lenguaje viene definida por tres
clausulas o partes: la clausula SELECT, la clausula FROM
y la clausula WHERE.
Un
ejemplo de una consulta que permite mostrar los nombres y apellidos de los
estudiantes de edad superior a 20, es:
select estudiantes.nombre, estudiantes.apellidos
from
estudiantes
where (estudiantes.edad>20);
Otro
tipo de sentencias un tanto mas complejas son las que usan la función group by.
Por
ejemplo si queremos mostrar la edad media de los alumnos por titulación a la que
pertenecen y que estén en segundo curso. Hemos supuesto que toda esta
información está en una única tabla (Tabla estudiantes).
select avg(estudiantes.edad)
from
estudiantes
where (estudiantes.curso=2)
group by
estudiantes.titulacion;
Otro
caso a considerar es el caso en el que la información se encuentre en varias
tablas. Por ejemplo, supongamos que queremos mostrar los nombres de las
asignaturas del alumno con DNI 25400000.
select asignaturas.nombre
from
estudiantes, asignaturas
where (estudiantes.DNI=2540000) and (estudiantes.modulo=asignaturas.modulo)
Análisis
Léxico (1ª sesión)
Se
trata de implementar un analizador léxico, en el que exista una función que
devuelva el siguiente token dentro del programa
fuente, es decir, que devuelva el tipo de token en
forma de constante entera, y su lexema, en forma de cadena. En esta primera fase
de la práctica, y con la finalidad de comprobar que funciona correctamente, esta
función será llamada por la función main, que solicitará nuevos tokens
hasta que se agote el texto del fichero de que contiene las consultas en SQL. El
programa deberá imprimir una lista de tokens de la
forma (tipo_de_token, lexema) como resultado,
deteniéndose en el caso de un error léxico e indicando la línea y columna del
texto fuente donde éste se produjo. Los componentes léxicos a reconocer son los
siguientes:
TKN_NUM =
digito+ (. digito+)?
TKN_ID =
letra (letra | digito)*
siendo digito
= 0 | 1 | ... |
9 letra = a | b | ... | z | A | B | ... |
Z
Símbolos
especiales
TKN_APAR
(
TKN_CPAR
)
TKN_PTOCOMA
;
TKN_PTO
.
Palabras
reservadas:
SELECT
TKN_SELECT
FROM
TKN_FROM
WHERE
TKN_WHERE
GROUP
TKN_GROUP
BY TKN_BY
Funciones
sobre campos agregados:
AVG
TKN_AVG //calcula el promedio
SUM
TKN_SUM //calcula la suma
MAX
TKN_MAX //calcula el máximo
MIN
TKN_MIN //calcula el mínimo
Operadores:
TKN_MENOR
<
TKN_MAYOR
>
TKN_MENORIG
<=
TKN_MAYORIG
>=
TKN_IG
=
TKN_DISTINTO
!=
TKN_Y
and
TKN_O or
NOTA:
La distinción entre identificadores y palabras reservadas debe hacerse mediante
el método de añadir las palabras reservadas a una lista de tokens predefinidos y comprobar cada candidato si es un
identificador o palabra reservada.
Análisis
Sintáctico (2ª y 3ª sesión)
Partiendo
del analizador léxico ya programado, se trata de implementar un analizador
sintáctico direccional determinista descendente basado en el uso de una
gramática LL(1). El programa deberá imprimir como
resultado la lista de producciones que generan la derivación más a la izquierda.
En el caso de que haya errores sintácticos, el programa debe proporcionar la
información sobre la línea y columna del texto original donde se produjo el
error, e intentar efectuar una recuperación del error en modo de
pánico.
Diseño
de una gramática LL(1)
Construir
una Gramática LL(1) que genere el lenguaje a reconocer:
un subconjunto del lenguaje SQL.
- Una
sentencia SQL se compone de al menos de la clausula
SELECT y FROM. La clausula WHERE y GROUP BY son opcionales. Si aparecen todas el orden es: SELECT,
FROM, WHERE y GROUP BY.
- En la
clausula SELECT pueden aparecer varios identificadores
separados por comas, o funciones de agregados.
- Los
identificadores pueden venir indicados mediante el atributo o bien mediante
nombre_de_la_tabla.atributo.
- En la
clausula FROM pueden aparecer varios nombres de tablas
separados por comas.
- En la
clausula WHERE pueden aparecer combinaciones de
expresiones relacionales y operadores lógicos. Recordad que los operadores
lógicos tienen mayor prioridad que los relacionales y que puede existir
anidamiento en las expresiones.
-
Supondremos que el programador puede escribir más de una sentencia SQL
consecutiva.
- Una
sentencia viene separada de otra por el carácter
;
Implementación
del analizador sintáctico descendente
Implementar
el analizador sintáctico predictivo recursivo
correspondiente para la gramática que habéis diseñado.
Implementación
de un sencillo traductor dirigido por la sintaxis
Imaginemos
que queremos enseñar SQL a una persona que no sabe inglés y que queremos
traducir todos los ejemplos de nuestro manual de referencia al castellano (o
valenciano). Es decir, donde aparece SELECT, debe aparecer la palabra
SELECCIONAR. Igual para el resto de palabras reservadas. Añade las acciones
semánticas a tu código para que durante el proceso de análisis sintáctico se
realice la traducción y vuelque a un fichero de salida las sentencias
traducidas. También habría que traducir los operadores AND por Y, OR por
O.
El
primer ejemplo traducido a castellano sería:
seleccionar estudiantes.nombre, estudiantes.apellidos
desde
estudiantes
donde (estudiantes.edad>20);
Implementación
de un mecanismo de recuperación de errores
Implementa
un sencillo mecanismo de recuperaciones de errores sintácticos por el método de
recuperación en modo de pánico.
Modifica
la especificación léxica del analizador léxico y crea una nueva especificación y
acción de un analizador sintáctico para poder realizar un análisis sintáctico y
generar un fichero html (generador páginas Web) a
partir de una fuente escrito en L-02.
Al
programa generador Web se le pasa como argumento un fichero
en
especificación L-02 y
debe generar:
-
fichero html (PEDIDO EN LA PRÁCTICA
ANTERIOR)
-
fichero texto con la lista de tipos de definiciones de elementos y nº
columna
y fila
donde aparecen (PEDIDO EN LA PRÁCTICA ANTERIOR)
-
fichero texto con los errores encontrados (preferible que muestre
información
sobre el
error, del tipo columna y fila del fuente donde ha ocurrido,
etc.).
(NUEVO)
El
generador Web debe detectar los errores e informar de ellos a través del
fichero
de
errores. Para realizar el tratamiento de errores debemos tener en cuenta
las
siguientes
condiciones que se imponen a una especificación L-02
válida:
- la
sección Pagina siempre debe existir
- la
sección Cabecera puede o no existir, pero si existe debe ir acompañada
de
la
declaración Titulo
- la
sección Cuerpo siempre debe existir.
- El
resto de errores que crea oportunos detectar el alumno. En este caso,
se
debe
indicar en la documentación que se ha ampliado el tratamiento
de
errores y las
nuevas situaciones de errores que detecta.
Construyendo
un analizador sintáctico
Un
analizador sintáctico, es una clase que recibe lo siguiente:
1.
Una
clase donde se almacenarán los atributos de cada símbolo.
2.
Una
gramática libre de contexto donde el símbolo de inicio solo produce una
variable.
3.
Una
función de síntesis para cada producción, encargada de sintetizar los atributos
necesarios.
4.
Para
cada producción una opcional regla para deshacer ambigüedades.
5.
Una
instancia de una clase de léxico que derive de la clase abstracta de léxico
básico.
6.
Una
opcional función de error para manejarlos y recuperarse en la medida de lo
posible.
El
analizador ira leyendo del léxico y aplicando las reducciones necesarias
(llamando a las funciones de síntesis proporcionadas). El resultado habitual es
un árbol sintáctico construido de manera ascendente. Cada nodo de ese árbol es
del tipo genérico que se le pasa como parámetro al parser mencionado en la lista anterior.
El tipo
de los nodos solo tiene un requisito de base. Es necesario que tenga un campo
llamado ``text'' accesible con el operador ``.'' para que el sintáctico almacene los tokens en las hojas del árbol. Este campo no contendrá datos
en los nodos superiores a menos que las funciones de síntesis lo usen para algo.
Como
normalmente se aplica el patrón visitor, el tipo de
los nodos sera algo como esto:
struct lval_t
{
string text;
nodeTree *node;
};
La
clase nodeTree sera de un
tipo abstracto que derivará en los distintos tipos de construcciones
sintácticas. Las funciones de síntesis serán las encargadas de construir estos
nodos a partir de los hijos. Estas tienen el siguiente prototipo:
V join_copia(vector<V>::iterator v);
Donde V
es el tipo de los nodos, como por ejemplo el ``lval_t'' definido antes.
Como se
ve, una función de síntesis toma un iterador a un
vector de nodos. Este vector es realmente la pila de valores. La razón por la
que se pasa un iterador es porque este apunta ya
directamente a la parte de arriba de la pila que se tiene que reducir. Con la
STL, este iterador se comporta como un vector, así que
en realidad es como si estuviéramos pasando un vector de nodos hijos del que se
va a construir. Un ejemplo sería el siguiente: imaginemos que tenemos una
producción como la que sigue:
Su función de síntesis podría ser la siguiente:
lval_t join_suma(vector<lval_t>::iterator v)
{
lval_t resultado;
resultado.node=new nodeSuma(v[0],v[2]);
//aqui v[1] seria el '+' en el campo text, no se usa
return resultado;
}
Conviene
usar siempre punteros en la estructura ``lval_t'' o
como se la llame para que no se tengan que hacer copias de los
objetos.
Primero
definimos el tipo que va a almacenar los atributos de cada nodo del árbol. Como
nosotros no vamos a construir un árbol sino que vamos a interpretar el código en
tiempo de ``sintáctico'', lo único que necesitamos guardar es el valor de la
expresión. Así pues ponemos un entero y el campo obligatorio text.
struct lval
{
string text;
int num;
};
Veremos
ahora el código de algunas de las funciones de síntesis. Por ejemplo la de suma :
lval join_suma(vector<lval>::iterator v)
{
lval res;
res.num=v[0].num+v[2].num;
return res;
}
Sencillo,
simplemente se suman el primer y el tercer elemento. El segundo es el operador
de suma que no nos sirve para nada. En esta filosofía el léxico está bien
restringido, no hace cosas como convertir cadenas a números. De esta manera no
interfiere con la representación interna del árbol. El sintáctico y el léxico
están bien separados. Por eso es necesaria la variable num de la gramática. Su función de síntesis se encarga de
interpretar la cadena de dígitos y convertirla a un número con la representación
que hemos elegido.
lval join_int(vector<lval>::iterator v)
{
lval res;
res.num=atoi(v[0].text.c_str());
return res;
}
Cuando
se reduce un número desde un identificador, lo único que se hace es sacar el
valor de una tabla hash. Veamos la función de síntesis
de la producción del operador de asignación.
lval join_asign(vector<lval>::iterator v)
{
lval res;
variables[v[0].text]=v[2].num;
res.num=v[2].num;
cout<<"Asignado "<<v[2].num<<" a "<<v[0].text<<endl;
return res;
}
No
debería de haber problemas con todas las demás funciones que manejamos. Más o
menos es siempre lo mismo dado que es un lenguaje muy sencillo.
La
función de error, si se proporciona, es llamada por el parser siempre que encuentre un error sintáctico a la
entrada. El prototipo es fijo y se le dan una serie de datos que se consideraron
necesarios.
bool merror(vector<lval>::iterator b,vector<lval>::iterator e,
list<int> &ex,int &tok,lex_t &lex);
Los dos
primeros parámetros definen el rango en la pila de valores que fueron creados.
En el caso de que el error sea irrecuperable la función ha de encargarse de
liberar memoria reservada. El siguiente parámetro es la lista de tokens que el parser esperaba
encontrarse en ese momento. Luego va el token que se
encontró, pero pasado por referencia. Lo que quiere decir que la función de
error podrá modificar ese token para intentar
recuperarse del error.
Finalmente
se pasa una referencia al léxico que se esta usando. Cuando la función haya
terminado de hacer lo que tenga que hacer ha de devolver un bool. Si devuelve
true el parser interpreta
que el error es fatal y para el proceso de parsing. Si
devuelve false el parser
intentará seguir adelante, pero si la función no hizo nada con el token y el léxico que se le dio el error se volverá a
repetir.
Nosotros
vamos a construir una sencilla función de error que simplemente ignora los tokens erróneos.
bool merror(vector<lval>::iterator b,vector<lval>::iterator e,
list<int> &ex,int &tok,lex_t &lex)
{
if(tok==T_EOF)
{
cout<<"Unexpected end of file, giving up...\n";
return true;
}
cout<<"Ignoring unexpected token "<<lex.text()<<" at line "<<
lex.line()<<endl;
tok=lex.nextToken();
return false;
}
Hacemos
una excepción con el token de final de fichero, que
lógicamente no podemos ignorar. Cuando se encuentra un token que no se esperaba se ignora y se pasa al siguiente
haciendo uso del léxico que se da.
El
proceso de análisis sintáctico y la ejecución son ahora dos pasos completamente
separados, no se procederá a la ejecución del código de cualquier archivo hasta
que éste en su totalidad, así como todo el código requerido se haya analizado
completa y satisfactoriamente_
Uno de
los nuevos requisitos introducidos con esta separación es que todos los archivos
requeridos y de inclusión tienen que ser sintácticamente completos ahora_ Ya no
es permitida la separación de diferentes segmentos de una estructura de control
a través de varios archivos_ Esto quiere decir que ahora no puede iniciar un
ciclo for o
while, una
sentencia if o un
bloque switch en un
archivo, y tener el final del ciclo, sentencias else,
endif,
case o
break en un
archivo diferente_
Aun es
perfectamente legal incluir código adicional al interior de ciclos u otras
estructuras de control, únicamente las palabras claves de control y los
corchetes correspondientes {___} tienen
que estar en la misma unidad de compilación (archivo o cadena procesada por eval()).
Esto no
debe generar una repercusión significativa ya que separar el código de esta
manera debe ser considerado como muy mal estilo, en cualquier
caso.
Algo
más que ya no es posible, aunque es rara veces visto en código PHP 3, es
devolver valores desde un archivo requerido.Devolver
un valor desde un archivo de inclusión es posible aun.
Función
del análisis sintáctico.
Analizar
sintácticamente una tira o cadena de tokens no
es más que encontrar para ella el árbol sintáctico o de derivación que tiene
como raíz el axioma de la gramática, y como nodos terminales la sucesión
ordenada de símbolos que componen la cadena analizada. En caso de no existir
este árbol sintáctico, la cadena no pertenecerá al lenguaje, y el analizador
sintáctico ha de emitir el correspondiente mensaje de
error.
Existen
dos formas de analizar sintácticamente una cadena:
·
Análisis
descendente:
Partiendo del axioma inicial de la
gramática se va descendiendo utilizando las derivaciones izquierdas, hasta
llegar a construir la cadena analizada.
·
Análisis
ascendente:
Se va construyendo el árbol
desde sus nodos terminales. Es decir, se construye desde los símbolos de la
cadena hasta llegar al axioma de la gramática. En este caso, se emplean
normalmente las derivaciones más a la derecha hasta la localización de la raíz.
Los
principales métodos de análisis sintáctico son:
o
Análisis descendente:
Análisis
descendente con retroceso.
Si bien
en la práctica nunca se usa, se estudia a continuación el análisis descendente
con retroceso, por ser el más general de los análisis descendentes, y por su
valor didáctico.
Para la
realización del análisis descendente con retroceso contamos con una gramática,
cuyas reglas se enumeran:
(1) A --> 1(2) A --> 2 : : : : B --> 1 : B --> 2 : B --> 3 : : : : C --> 1 : : :
y de una
cadena, supuestamente perteneciente al lenguaje definido por la gramática:
a1a2a3a4....
Paso
1.
Inicialmente se parte de la forma sentencial
S
, que
contiene únicamente el axioma de la gramática.
Paso
2. Dada
una forma sentencial generada anteriormente, se
sustituye el símbolo no terminal situado más a la izquierda por la primera de
las alternativas posibles para dicho símbolo, generando asi una nueva forma sentencial.
Anotamos en una pila el número de la regla empleada.
En caso
de que no existiera ningún símbolo no terminal en la forma sentencial, se habría llegado a producir la sentencia que
estábamos analizando, estando almacenado su parse
izquierdo en la pila; si no, se continúa en el paso
4.
Paso
3. Se
anula la última producción utilizada (situada en la cima de la pila), volviendo
a obtener la forma sentencial anterior, y se retira de
la pila el último numero. En esta forma sentencial se
utiliza ahora la siguiente de las alternativas disponibles para el símbolo no
terminal situado más a la izquierda, anotando en la pila el número de la regla
empleada. En caso de que no haya más alternativas, se repite el paso
3 para la forma sentencial
obtenida.
Si
llega el momento en que se agotan todas las posibles alternativas del axioma
inicial, (la pila se habría quedado vacía), entonces se puede garantizar que la
cadena analizada no pertenece al lenguaje.
Paso
4. Se
comprueba si todos los símbolos terminales consecutivos que hayan aparecido a la
izquierda de la forma sentencial encajan con alguna
subcadena izquierda de la tira analizada. En caso
afirmativo, se va al paso
2. Si no, se va al paso
3.
Ejemplo:
Sea la
gramática:
(1) S
--> cAd>
(2)
A --> bcB
(3)
A --> a
(4)
B --> b
A
continuación, se va a realizar el análisis (paso a paso) de la sentencia
cad
:
Paso
1:
Inicialmente se parte de la forma sentencial
S
.
Paso
2: El
símbolo no terminal situado más a la izquierda es S
, en
las reglas de la gramática la primera (y única) alternativa para el símbolo
S
es
S-->cAd
.
Empleando esta regla se obtiene la forma sentencial
cAd
. La
pila contiene el número 1
. Ir al
paso
3.
Paso
3: La
subcadena de símbolos terminales consecutivos que han
aparecido a la izquierda de la forma sentencial es
c
y la
tira a analizar es cad
. Por
tanto, se supone válida esta producción y se continúa por el paso
2.
Paso
2: Ahora
la forma sentencial es cAd
, cuyo
primer símbolo no terminal es A
, y la
primera de las producciones para A
es
A-->bcB
.
Aplicándola se obtiene la nueva forma sentencial
cbcBd
. La
pila de análisis contiene ahora el parse
1-2
.
Paso
4: La
subcadena izquierda de símbolos terminales es ahora
cbc
, que
no encaja con el principio de la tira analizada. Por tanto, vamos al paso
3.
Paso
3: Se
anula la producción anterior, obteniendo nuevamente la forma sentencial cAd
.
Retiramos el símbolo superior de la pila de análisis, quedando ésta como antes
(es decir, 1
). Se
aplica ahora la segunda de las alternativas del símbolo no terminal
A
, que
es A-->a
,
obteniéndose la forma sentencial cad
. En la
pila de análisis se introduce el número de la regla aplicada quedando ésta como
1-3
.
Paso
4: La
subcadena izquierda de símbolos terminales es
cad
, que
coincide exactamente con la tira analizada.
Paso
2: La
forma sentencial no incluye ningún símbolo no
terminal, por lo que el proceso termina satisfactoriamente. El parse izquierdo de la cadena está contenido en la
pila.
Es
evidente que una condición necesaria para poder realizar este tipo de análisis,
tal como se ha descrito anteriormente, es que la gramática no sea recursiva por
la izquierda y, en general, que no tenga ciclos por la izquierda. Por ejemplo,
supongamos la gramática:
A
--> Aa | a
Según
el método que se sigue para el análisis, se generaría la siguiente secuencia de
formas sentenciales :
A
==> Aa ==> Aaa ==>
Aaaa ==>
...
Igualmente
sucede si la gramática tiene ciclos, ya que por definición de
ciclo:
A
==>+ A...
Para
solucionar este problema podemos hallar una gramática equivalente no recursiva
por la izquierda y sin ciclos, o bien modificar ligeramente el
algoritmo.
La
implementación en Pascal de este algoritmo, mediante el uso de un procedimiento
recursivo, puede encontrase en el programa ejemplo RPM. Su ejecución para la
gramática:
1.
E
--> T
2.
E
--> T+E
3.
T
--> F
4.
T
--> F*T
5.
F
--> a
6.
F
--> b
7.
F
--> (E)
y para
el reconocimiento de la cadena
a*(a+b)
da como
resultado la siguiente secuencia.
Pila |
Formas
Sentenciales |
1- |
T |
1-3- |
F |
1-3-5- |
a |
1-3-6- |
b |
1-3-7- |
(E) |
1-4- |
F*T |
1-4-5- |
a*T |
1-4-5-3- |
a*F |
1-4-5-3-5- |
a*a |
1-4-5-3-6- |
a*b |
1-4-5-3-7- |
a*(E) |
1-4-5-3-7-1- |
a*(T) |
1-4-5-3-7-1-3- |
a*(F) |
1-4-5-3-7-1-3-5- |
a*(a) |
1-4-5-3-7-1-3-6- |
a*(b) |
1-4-5-3-7-1-3-7- |
a*((E)) |
1-4-5-3-7-1-4- |
a*(F*T) |
1-4-5-3-7-1-4-5- |
a*(a*T) |
1-4-5-3-7-1-4-6- |
a*(b*T) |
1-4-5-3-7-2- |
a*(T+E) |
1-4-5-3-7-2-3- |
a*(F+E) |
1-4-5-3-7-2-3-5- |
a*(a+E) |
1-4-5-3-7-2-3-5-1- |
a*(a+T) |
1-4-5-3-7-2-3-5-1-3- |
a*(a+F) |
1-4-5-3-7-2-3-5-1-3-5- |
a*(a+a) |
1-4-5-3-7-2-3-5-1-3-6- |
a*(a+b) |
En la
columna derecha se muestran las formas sentenciales
que se van obteniendo durante el análisis, y en la izquierda, los números de las
reglas utilizadas para producirlas (es decir, el parse
izquierdo de cada una de estas formas senteciales).
El
último valor obtenido en la columna izquierda es el parse izquierdo de la cadena
analizada.
Análisis
descendente sin retroceso.
En el
análisis descendente con retroceso se generan formas sentenciales a partir del axioma, dando marcha atrás en
cuanto se detecta que la forma generada no es viable, (es decir, no conduce a
ninguna sentencia del lenguaje). Este proceso de vuelta atrás es lento. Para
mejorar la eficiencia del mismo, sería muy útil saber a priori qué
alternativa del símbolo no terminal es más conveniente
usar.
Veamos
de nuevo el ejemplo del apartado anterior:
Ejemplo: Sea
la gramática
(1)
S --> cAd
(2) A --> bcB
(3) A --> a
(4) B -->
b
y la
sentencia cad
.
Partiendo del axioma, sólo se puede aplicar la regla 1, obteniendo la forma
sentencial cAd
. Si se
compara con la sentencia cad
, se
observa que ambas comienzan con el caracter c
. Por
tanto, la subcadena Ad
ha de
generar el resto de la sentencia, o sea, ad
. En
este instante existen dos alternativas que se pueden emplear para modificar la
forma sentencial, que corresponden a la aplicación de
las reglas 2 y 3.
La
aplicación de la regla 2 provoca la aparición del carácter b
al
principio de la subcadena restante, mientras que la
regla 3 provoca la aparición del carácter a
. Por
tanto, como la subcadena que falta por generar para
producir la sentencia final es ad
(empieza por a
),
puede deducirse que en este instante la regla que debe emplearse es la regla 3,
y no la 2.
El
método de análisis que hemos seguido consiste en leer la cadena de entrada de
izquierda a derecha, (L: Left to rigth) utilizando reglas de
producción izquierda (L: Left most) e inspeccionando un (1) solo símbolo de la
entrada para elegir la regla conveniente. Este análisis se denomina LL(1).
Desafortunadamente,
hay casos en los que este procedimiento no sirve. Supóngase, por ejemplo, que la
gramatica fuese:
(1)
S --> cAd
(2) A --> aB
(3) A --> a
(4) B --> b
Al
analizar la tira de entrada cad
, tras
realizar la primera producción obtendríamos la forma sentencial cAd
,
quedando como subcadena a analizar ad
(que
comienza con a
). Pero
ahora hay dos reglas aplicables que comienzan por a
(las
reglas número 2 y 3). Por tanto, no es posible decidir de forma automática qué
regla debe emplearse.
Por
otra parte, si se pretende que el análisis sea sin retroceso, es indispensable
que la gramática no tenga ciclos por la izquierda (y consiguientemente, que no
sea recursiva por la izquierda).
No
todas las gramáticas admiten un análisis descendente sin retroceso en el que se
pueda predecir la alternativa que debe usarse. En el siguiente apartado se verá
una condición necesaria y suficiente para que una gramática admita un análisis
LL(1).
Análisis
ascendente:
Análisis
ascendente con retroceso.
El
análisis ascendente, como ya se ha visto, consiste en construir el árbol
sintáctico de una cadena dada, partiendo de los nodos terminales del mismo,
hasta llegar a su raíz. Estos nodos terminales no son otros que los distintos
símbolos terminales de la cadena de entrada.
En
todos los análisis ascendentes se plantea la necesidad de reducir una subcadena de nodos, para obtener así una metanoción, o símbolo no terminal, común a todos los
símbolos de la subcadena. A esta operación se le llama
reducción
.
Por
otra parte, a las sucesivas lecturas de un símbolo de la cadena de entrada se
les llama desplazamientos
.
Cualquier
análisis ascendente utilizará estas dos operaciones, además de las operaciones
aceptar
y
error
, que
determinan el final del proceso.
El
primero de los métodos ascendentes que vamos a ver es el análisis ascendente con
retroceso. Este análisis, al igual que todos los métodos con retroceso, se basa
en la prueba sistemática de todas las combinaciones posibles de reducciones y
desplazamientos, continuando con el proceso siempre que sea posible, y dando
marcha atrás cuando no quede otra alternativa.
En la
cadena de entrada, y en las distintas formas sentenciales que se van a ir generando para su
reconocimiento, se distinguen dos subcadenas: la
primera de ellas corresponde a los símbolos que se han leido hasta el momento; y la segunda será la subcadena que queda por leer. Cada vez que se lee un
símbolo, se realiza el desplazamiento de un símbolo de la subcadena derecha a la subcadena
izquierda, o lo que es lo mismo, se desplaza una posición la separación entre
las subcadenas izquierda y
derecha.
Inicialmente,
se parte de la cadena de entrada, de la cuál se ha leído el primer símbolo. Por
tanto, la subcadena izquierda contiene un solo
símbolo, y la subcadena derecha el
resto.
El
algoritmo siguiente se repite hasta que se obtiene el axioma en la subcadena izquierda, estando la derecha vacía.
La
forma sentencial que se está analizando en un instante
dado se puede representar como, siendola subcadena izquierda yla subcadena derecha.
Si
tomamos=
X1X2....Xp...Xn, y=
Y1Y2....Ym,
entonces
=
X1X2....Xp...XnY1Y2....Ym
sería la
forma sentencial analizada. Se va a considerar que las
reglas gramaticales son de la forma:
A1 -> Z1 1 Z1 2 .... Z1 S1A2 -> Z2 1 Z2 2 .... Z2 S2: : : :Ak -> Zk 1 Zk 2 .... Zk Sk
Como ya
se ha anticipado, llamamos reducción
de la
cadena, según la regla k, a la
sustitucion de los (n-p+1
)
símbolos derechos de la cadenaque coinciden exactamente con los
Sk símbolos del consecuente de la regla
k, por el antecedente de dicha regla Ak. Por supuesto, sólo será posible efectuar la
reducción en el caso de que todos los símbolos del consecuente encajen con el
extremo derecho de la subcadena. El resultado de la reducción
sería:
= X1X2...Ak
Se
llama desplazamiento
al
paso del símbolo izquierdo de la cadenaal extremo derecho de la cadena. Por supuesto, ésto sólo es posible si la longitud dees mayor que cero (es decir, si la
cadenaes distinta de la tira nula. El resultado
sería:
=
X1X2....Xp...XnY1= Y2....Ym
Se
describe a continuación, en pseudo-codigo, el
algoritmo recursivo de reconocimiento con retroceso que realiza el análisis
ascendente:
procedure Ensayar (,);begin for k:=1 to Numero de reglas do if consecuente de regla k = Parte derecha de then begin Realizar Reduccion k, en la subcadena if =Axioma and = then Aceptar else Ensayar(,) Anular Reduccion end if <> then begin Realizar un desplazamiento de un símbolo de a if =Axioma and = then Aceptar else Ensayar(,) Anular Desplazamiento endend
En el
algoritmo anterior se ha supuesto que el procedimiento Aceptar
conlleva la finalización del proceso de análisis.
La
implementación práctica de dicho algoritmo corresponde al programa ejemplo
RPMASC. El siguiente es un ejemplo de la ejecución de este
programa.
Ejemplo: Sea
la gramática gramática:
1.
E
-> E+T
2.
E
-> T
3.
T
-> T*F
4.
T
-> F
5.
F
-> (E)
6.
F
-> a
cuyo axioma
es E
. Los
símbolos no terminales de la gramática son {E,F,T}
, y los
símbolos terminales son {(,),*,+,a}
.
Tomando como entrada la cadena a+a*a
, la
traza de ejecución del análisis ascendente con retroceso para esta cadena
es:
Pila |
Expresión
Regular |
Operación |
|
a|+a*a |
Desplazamiento |
6- |
F|+a*a |
Reducción |
6-4- |
T|+a*a |
Reducción |
6-4-2- |
E|+a*a |
Reducción |
6-4-2- |
E+|a*a |
Desplazamiento |
6-4-2- |
E+a|*a |
Desplazamiento |
6-4-2-6- |
E+F|*a |
Reducción |
6-4-2-6-4- |
E+T|*a |
Reducción |
6-4-2-6-4-1- |
E|*a |
Reducción |
6-4-2-6-4-1- |
E*|a |
Desplazamiento |
6-4-2-6-4-1- |
E*a| |
Desplazamiento |
6-4-2-6-4-1-6- |
E*F| |
Reducción |
6-4-2-6-4-1-6-4- |
E*T| |
Reducción |
6-4-2-6-4-1-6-4-2- |
E*E| |
Reducción |
6-4-2-6-4-2- |
E+E|*a |
Reducción |
6-4-2-6-4-2- |
E+E*|a |
Desplazamiento |
6-4-2-6-4-2- |
E+E*a| |
Desplazamiento |
6-4-2-6-4-2-6- |
E+E*F| |
Reducción |
6-4-2-6-4-2-6-4- |
E+E*T| |
Reducción |
6-4-2-6-4-2-6-4-2- |
E+E*E| |
Reducción |
6-4-2-6-4- |
E+T*|a |
Desplazamiento |
6-4-2-6-4- |
E+T*a| |
Desplazamiento |
6-4-2-6-4-6- |
E+T*F| |
Reducción |
6-4-2-6-4-6-3- |
E+T| |
Reducción |
6-4-2-6-4-6-3-1- |
E| |
Reducción |
6-4-2-6-4-6-3-1- |
E| |
Fin
de proceso. Correcto |
Procedimientos
de análisis LR(0).
Para la
construcción de tablas de análisis LR(0)
es preciso realizar unas definiciones previas:
Se
denomina ítem LR(0) de una gramática a una terna (A,,)Nx(NT)*x(NT)*,
siendo A->una
regla gramatical de P. En
general, los ítems se escriben como una regla de producción separada en dos
partes por un punto:
[A
->1·2]
Para
hacer mayor énfasis, y distinguir los items de las
reglas gramaticales colocaremos unos corchetes al referirnos a los items.
Cada
regla de la gramática dará origen a uno o más items.
De hecho, la única regla que da origen a un solo ítem es aquella cuyo
consecuente es la tira nula (X
->), que
genera el ítem [X
-> ·]
LLamamos
ítem completo a aquellos de la forma [A
->·]
Al
conjunto de todos los items de una gramática lo
denotaremos como.
Ejemplo: Sea
una gramática con las reglas
S
-> E$
E -> E+T
E -> E-T
EE -> T
T -> (E)
T ->
a
A
partir de la misma podemos hallar los siguientes items:
= {[S -> ·E$] , [E -> ·E+T] , [E
-> ·E-T], [S
-> E·$] , [E -> E·+T] , [E -> E·-TT], [S -> E$·] , [E
-> E+·T] , [E -> E-·T], [E -> ·T] , [E -> E+T·] , [E -> E-T·], [E -> T·] , [T -> ·(E)] , [T -> ·a] , [E -> T·] , [T -> (·E)] , [T -> a·] , [T -> (E·)] , [T
-> (E)·]}
Función
de cierre.
Sobre
un conjunto I de
ítems se define la función cierre(I) como
el conjunto de ítems resultante de aplicar las siguientes
reglas:
cierre(I)
: P() --->
P()
Regla
1. Todos
los ítems pertenecientes a I
pertenecen también a cierre(I).
Regla
2. Si
[A
->·B] es un
ítem perteneciente a cierre(I), y
existe una regla de producción de la forma B
->,
entonces el ítem [B
-> ·]
pertenece a cierre(I).
Regla
3.
Repetir la regla anterior hasta que no se añada ningún nuevo ítem al conjunto
cierre(I).
Ejemplo: Sea
el conjunto I
compuesto por el ítem
I
= {[S -> ·E$]}
Inicialmente
se calcula cierre(I) por la
primera de las reglas, obteniéndose:
cierre(I)
= {[S -> ·E$]}
Según
la segunda de las reglas se añade a cierre(I) todos
aquellos ítems de la forma [E->] , ya
que el símbolo no terminal E
aparece justo a la derecha del punto del primer ítem. Queda,
por tanto:
cierre(I)
={[S -> ·E$],[E -> ·E+T],[E -> ·E-T],[E ->
·T]}
Se
vuelve a aplicar la regla 2 al conjunto obtenido anteriormente. En este caso
tendremos que incorporar al mismo todos aquellos ítems de la forma [E
-> ·] (que
ya están) y los de la forma [T
-> ·], con
lo que resulta:
cierre(I)
= {[S -> ·E$],[E -> ·E+T],[E -> ·E-T],
[E -> ·T],[T -> ·(E)],[T -> ·a]}
Nuevamente
se intenta la regla 2, pero esta vez no se añade ningún nuevo elemento a
cierre(I), ya
que tenemos todos los ítems de la forma [E
-> ·] y de
la forma [T
-> ·], y los
nuevos ítems que han aparecido tienen un símbolo no terminal a la derecha del
punto separador, por lo que no generan ningún nuevo ítem por la operación de
cierre.
Función
de transición.
Se
define la función de transición, que se aplica a un conjunto de
ítems y a un símbolo (terminal o no terminal) de la gramática, y da como
resultado un nuevo conjunto de ítems.
: P() x {NT} ------>
P{}
(I,X) ---->(I,X)
(I,X) es
igual al cierre del conjunto de todos los ítems de la forma [A
->X·], tales
que [A
->·X]
pertenece a I.
Ejemplo: Sea
el conjunto de items
I = {[S -> ·E$],[E -> ·E+T],[E ->
·E-T],[E -> ·T], [T ->
·(E)],[T -> ·a]}
Y sea
el símbolo X
= E
El
conjunto(I,E)
es:
cierre({[S
-> E·$],[E -> E·+T],[E -> E·-T]})<
En este
caso el cierre coincide con el conjunto, y por tanto:
(I,E)
= {[S -> E·$],[E -> E·+T],[E -> E·-T]}
Para el
mismo conjunto de ítems I, y
para el símbolo (
se
obtendría:
(I,() = cierre({[T -> (·E)]}) =
{[T -> (·E)],[E
-> ·E+T],[E -&> ·E-T],
[E -> ·T],[T ->
·(E)],[T -> ·a]}
Para el
mismo conjunto de items I, y
para el símbolo a, se
obtendría:
(I,a) = {[T -> a·]}
Construcción
de la colección de conjuntos de items LR(0).
Sea
C un
conjunto de items LR(0) compuesto por los conjuntos de items
C
= {I0,I1,I2,...}
Supondremos
que la gramática de partida tiene una sola regla asociada al axioma S. En
caso de que ésto no sea así, se añade a la gramática
la regla S'->S, y se
toma como axioma el símbolo S'. Esta
nueva gramática se denomina gramática aumentada.
El
algoritmo empleado es el siguiente:
Paso
1. Se
construye el conjunto inicial de items I0,
compuesto por todos los ítems pertenecientes al cierre del primer ítem asociado
al axioma. Es decir:
I0
= cierre([S'->·])
La
colección C de
conjuntos de items tiene ya un
elemento.
Paso
2. Para
cada conjunto de items I
perteneciente a la colección C, y
para cada símbolo X
(terminal o no terminal) de la gramática se halla el conjunto(I,X). Si
este conjunto es no vacío, y no pertenece ya a la colección C, se añade a la
misma.
Paso
3. Se
repite el paso 2 hasta que no se incorpore ningún conjunto nuevo a la colección
C.
Este
proceso es finito. Dado que el número de reglas de una gramática es finito, y que el número de símbolos en el consecuente de cada
una de las reglas también lo es, el número de posibles ítems también lo es.
Siendo finito el número de items es también finito el
número de conjuntos de items que podemos formar a
partir de ellos, por lo que el proceso descrito anteriormente tiene fin en un
número finito de pasos.
Ejemplo:
Para la gramática anterior
S
-> E$
E -> E+T
E -> E-T
EE -> T
T -> (E)
T ->
a
La
colección de items estará compuesta por los doce
conjuntos siguientes:
I0
= {[S -> ·E$],[E ->
·E+T],[E -> ·E-T],[E -> ·T], [T ->
·(E)],[T -> ·a]}
I1
= {[S -> E·$],[E ->
E·+T],[E -> E·-T]}
I2
= {[E ->
T·]}
I3
= {[T ->
a·]}
I4
= {[T -> (·E)],[E ->
·E+T],[E -> ·E-T],[E -> ·T], [T ->
·(E)],[T -> ·a]}
I5
= {[E ->
E$·]}
I6
= {[E -> E+·T],[T ->
·(E)],[T -> ·a]}
I7
= {[E -> E-·T],[T ->
·(E)],[T -> ·a]}
I8
= {[E ->
E+T·]}
I9
= {[E ->
E-T·]}
I10
= {[T -> (E·)],[E -> E·+T],[E -> E·-T]}
I11
= {[T -> (E)·]}
Se dice
que un ítem [A
->1·2] es
válido para una subcadena viable1 (es
decir, una subcadena que puede ser la parte izquierda
de alguna forma sentencial del lenguaje) si existe una
secuencia de derivaciones de la forma:
S
==>*A==>*12
En
general, un ítem puede ser válido para muchas subcadenas. El hecho de que un ítem sea válido para una
determinada subcadena proporciona información acerca
de qué es lo que se debe hacer al encontrar una subcadena de este tipo en la pila, ya que si el ítem no es
completo (es decir, 2<>), esto
indica que aún no se ha encontrado un pivote que pueda ser reducido. Por el
contrario, cuando existe un ítem completo válido asociado a una determinada
subcadena, (es decir, 2=) es
posible efectuar en la misma una reducción mediante la aplicación de la regla
gramatical correspondiente.
Para
construir la máquina de análisis LR(0) se
utiliza el siguiente procedimiento:
Paso
1. Los
estados de la máquina LR(0) corresponden
a cada uno de los conjuntos de items I de la
colección C. El
estado inicial será el asociado al conjunto de items
que contenga al ítem asociado al axioma, [S'
-> ·S]
Paso
2. La
tabla de transiciones es la definida por la función de transiciónentre conjuntos de items. Como se ve, la tabla de transiciones está definida
sobre el producto cartesiano de la colección C, o
conjunto de estados de la máquina, por el conjunto de símbolos terminales
y no terminales (NT) de la
gramática.
Paso
3. La
tabla de acciones para la máquina LR(0)
depende exclusivamente del estado en el que se encuentre la máquina, ya que el
análisis debe efectuarse sin inspeccionar ningún símbolo de la entrada. La
acción a realizar en cada estado es la siguiente:
Si el
conjunto de ítems asociado al estado contiene un solo ítem, y éste es completo
(es decir, si el único ítem del conjunto es de la forma [A
->·]), la
acción asociada a dicho estado es la reducción mediante la regla A
->(Acción
= Reducción),
salvo en el caso en que esta regla esté asociada al axioma, en el que el
análisis concluye con la aceptación de la cadena de entrada (Acción
= Aceptar).
En caso
de que el conjunto de items asociado a un estado no
contenga ningún ítem completo, la acción a realizar es desplazamiento.
(Acción
= Desplazamiento)
.
Si
existe algún estado cuyo conjunto de items asociado
contiene más de un ítem, siendo alguno de ellos completo, se dice que la
gramática no cumple las restricciones LR(0), o simplemente que la gramática no es
LR(0), y el análisis por este método no es posible.
Ejemplo:
Para la gramática anterior
(0)
S -> E$
(1) E -> E+T
(2) E -> E-T
(3) E -> T
(4) T ->
(E)
(5) T -> a
El
conjunto de estados de la máquina LR(0)
es:
{0,1,2,3,4,5,6,7,8,9,10,11}
siendo el
estado inicial el 0.
Las
tablas de análisis son:
TABLA
DE ACCIONES
Estado |
Acción |
0 |
D |
1 |
D |
2 |
R3 |
3 |
R5 |
4 |
D |
5 |
A |
6 |
D |
7 |
D |
8 |
R1 |
9 |
R2 |
10 |
D |
11 |
R4 |
TABLA
DE TRANSICIONES
|
a |
+ |
- |
( |
) |
$ |
E |
T |
0 |
3 |
|
|
4 |
|
|
1 |
2 |
1 |
|
6 |
7 |
|
|
5 |
|
|
2 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
4 |
3 |
|
|
4 |
|
|
10 |
2 |
5 |
|
|
|
|
|
|
|
|
6 |
3 |
|
|
4 |
|
|
|
8 |
7 |
3 |
|
|
4 |
|
|
|
9 |
8 |
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
10 |
|
6 |
7 |
|
11 |
|
|
|
11 |
|
|
|
|
|
|
|
|
El
reconocimiento de la cadena a-a+a$ sería
el siguiente:
|
Pila |
Entrada |
Acción |
(
1) |
0 |
a-a+a$ |
Desplazamiento |
(
2) |
0a3 |
-a+a$ |
Reducción
T -> a |
(
3) |
0T2 |
-a+a$ |
Reducción
E -> T |
(
4) |
0E1 |
-a+a$ |
Desplazamiento |
(
5) |
0E1-7 |
a+a$ |
Desplazamiento |
(
6) |
0E1-7a3 |
+a$ |
Reducción
T -> a |
(
7) |
0E2-7T9 |
+a$ |
Reducción
E -> E-T |
(
8) |
0E1 |
+a$ |
Desplazamiento |
(
9) |
0E1+6 |
a$ |
Desplazamiento |
(10) |
0E1+6a3 |
$ |
Reducción
T -> a |
(11) |
0E1+6T8 |
$ |
Reducción
E -> E+T |
(12) |
0E1 |
$ |
Desplazamiento |
(13) |
0E1$5 |
|
Aceptar |
*
* *
Un
método alternativo de plantear la construcción de la colección de conjuntos de
items que formarán los estados de la máquina LR(0) es la aplicación de la teoría de
autómatas finitos de la siguiente forma:
Paso
1: Se
construye un autómata finito no determinista AFN de la
siguiente forma:
AFN=(QN,TeN,N,q0N,FN)
·
QN==
Conjunto de todos los items.
·
TeN=NT
·
q0N=[S'
-> ·S]<.
Primer ítem asociado al axioma de la gramática.
·
F={[A
->·] pertenecientes a}. Items completos.
·
N. La
función de transición entre estados de la máquina no determinista.
Se
define así :
Por
cada ítem de la forma [A
->·b], donde
b
pertenece a T
(conjunto de símbolos terminales de la gramática) se tiene
que:
[A
-> b·]
pertenece a N([A
-> ·b],b)
donde
B
pertenece a N
(conjunto de símbolos no terminales de la gramática).
Si
[A
-> B·]
pertenece a N([A
-> ·B],B),
entonces [B
-> ·]
pertenece a N([A
-> ·B],),
para todos los posibles valores de .
Paso
2: Una
vez construido el AFN se
aplica el algoritmo de construcción de subconjuntos para hallar el Autómata
Finito Determinista mínimo (AFDM),
obteniendo así el mismo resultado que con el procedimiento descrito
anteriormente en este epígrafe.
Los
análisis con retroceso se basan en la prueba sistemática de todas las
alternativas posibles, dando marcha atrás tan pronto como se detecte que el
camino seguido es erróneo. Pueden usarse para cualquier gramática de contexto
libre, aunque tienen tres grandes inconvenientes: Primero, emplean mucho
más tiempo para el análisis que los demás analizadores, dependiendo éste incluso
de la ordenación de las reglas gramáticales;
Segundo, no dan un buen diagnóstico de los errores que encuentran;
Tercero, complican la generación de código cuando ésta se realiza al par
que el análisis sintáctico.
Los
métodos más eficientes de análisis (tanto ascendente como descendente) no
funcionan para todas las gramáticas de contexto libre, sino sólo para las
gramáticas que cumplen unas determinadas condiciones.
Afortunadamente,
en la mayoría de los casos, pueden encontrase para los lenguajes de programación
gramáticas de tipo LL
o LR
que los generen.
Para
representar el árbol sintáctico que conduce hasta una cadena se asigna a cada
regla de la gramática un número. Se define el parse como la secuencia ordenada de números (de
reglas) aplicadas para construir dicho árbol.
Hay dos
tipos de parse, que son:
·
El
parse-izquierdo: Son los números de las
reglas de derivacion izquierda utilizadas para generar
la cadena a partir del axioma, por tanto correspondiente a un análisis
descendente.
·
El
parse-derecho: Son los números de las
reglas de derivación derecha utilizadas para generar la cadena a partir del
axioma, en orden inverso. El tomar el orden inverso viene condicionado por ser
el análisis ascendente el que normalmente utiliza las reglas de derivación
derecha, con lo que el orden en el que aparecen al realizar el análisis es
invertido.
Ejemplos:
Dada
la gramática 1.
E
--> T 2.
E
--> T+E 3.
T
--> F 4.
T
--> F*T 5.
F
--> a 6.
F
--> b 7.
F
--> (E) y
la sentencia "a*(a+b)" El
parse izquierdo es: 1-4-5-3-7-2-3-5-1-3-6 y
el derecho: 5-5-3-6-3-1-2-7-3-4-1 |
|
Simultáneamente
a la fase de análisis sintáctico, además de reconocer las secuencias de tokens, y analizar su estructura, pueden realizarse una
serie de tareas adicionales, como:
Recopilar información de los distintos
tokens y almacenarla en la tabla de símbolos.
Realizar algun
tipo de análisis
semántico, tal como la comprobación de tipos.
Generar código intermedio.
Avisar de los errores que se detecten.