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

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.

 

Las funciones de síntesis

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

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.

 

 

 

 

Comportamiento del analizador sintáctico

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:

a₁a₂a₃a₄....

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.

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.

 

Procedimientos de análisis LL(1).

 

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= X₁X₂....X_p...X_n, y= Y₁Y₂....Y_m, entonces

= X₁X₂....X_p...X_nY₁Y₂....Y_m

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 S_k símbolos del consecuente de la regla k, por el antecedente de dicha regla A_k. 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:

= X₁X₂...A_k

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:

= X₁X₂....X_p...X_nY₁= Y₂....Y_m

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:

 

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 ->₁·₂]

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 = {I₀,I₁,I₂,...}

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 I₀, compuesto por todos los ítems pertenecientes al cierre del primer ítem asociado al axioma. Es decir:

I₀ = 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:

I₀  = {[S -> ·E$],[E -> ·E+T],[E -> ·E-T],[E -> ·T],      [T -> ·(E)],[T -> ·a]}

I₁  = {[S -> E·$],[E -> E·+T],[E -> E·-T]}

I₂  = {[E -> T·]}

I₃  = {[T -> a·]}

I₄  = {[T -> (·E)],[E -> ·E+T],[E -> ·E-T],[E -> ·T],      [T -> ·(E)],[T -> ·a]}

I₅  = {[E -> E$·]}

I₆  = {[E -> E+·T],[T -> ·(E)],[T -> ·a]}

I₇  = {[E -> E-·T],[T -> ·(E)],[T -> ·a]}

I₈  = {[E -> E+T·]}

I₉  = {[E -> E-T·]}

I₁₀ = {[T -> (E·)],[E -> E·+T],[E -> E·-T]}

I₁₁ = {[T -> (E)·]}

 

Se dice que un ítem [A ->₁·₂] es válido para una subcadena viable₁ (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==>*₁₂

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, ₂<>), 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, ₂=) 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

 

TABLA DE TRANSICIONES

 

 

El reconocimiento de la cadena a-a+a$ sería el siguiente:

* * *

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=(Q^N,T_e^N,^N,q₀^N,F^N)

·                    Q^N== Conjunto de todos los items.

·                    T_e^N=NT

·                    q₀^N=[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:

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.