Prácticas de Procesadores de lenguaje

Curso 2006/2007

Práctica 2: analizador sintáctico

Objetivo de la práctica

• Esta práctica tiene como objetivo la codificación de un analizador sintáctico mediante el uso del lenguaje de programación C y la herramienta de ayuda a la generación de analizadores sintácticos bison

• En este analizador sintáctico se incorporará en la siguiente práctica el análisis semántico y la generación de código del compilador de ALFA.

Desarrollo de la práctica

Codificación de una especificación para bison

• El alumno debe escribir un fichero de nombre alfa.y que sea una especificación correcta para la entrada de la herramienta bison. Se recomienda al alumno que se familiarice primero con bison mediante las explicaciones que su profesor de prácticas realizará en su laboratorio.

Resolución de conflictos

• Cuando se compile el fichero alfa.y pueden aparecer mensajes de conflictos. Estos conflictos se refieren a los que encuentra el autómata a pila generado por la herramienta bison. Para obtener información acerca de ellos se debe compilar el fichero alfa.y con el flag -v para que se genere el fichero y.output que contiene la descripción completa del autómata y de los conflictos (si existieran). El alumno debe modificar las producciones de la gramática para resolver estos conflictos.

Modificación de la especificación para flex

• El alumno debe modificar el fichero alfa.l de la práctica 1 para poder ser enlazado con el fichero alfa.y. Para ello utilizará de guía las explicaciones que su profesor de prácticas realizará en su laboratorio.

Codificación de un programa de prueba

• El alumno también debe escribir en C un programa de prueba del analizador sintáctico con los siguientes requisitos:

  • Nombre del programa fuente:  prbisonalfa.c

  • Al ejecutable se le invocará de la siguiente manera:

    prbisonalfa [ <nombre fichero entrada> [<nombre fichero salida>] ]
                    

• Es decir, el programa se puede llamar:

• Con 0 argumentos, entonces se utilizan la entrada y la salida estándares

• Con 1 argumentos, entonces se utiliza la salida estándar y el argumento como nombre del fichero de entrada.

• Con 2 argumentos, entonces el primero se interpreta como el nombre del fichero de entrada y el segundo como el nombre del fichero de salida.

• La estructura, formato y contenido de cada fichero se explican a continuación.

Descripción del fichero de entrada

• El fichero de entrada va a contener en programas escritos en lenguaje ALFA (no necesariamente correctos).

Funcionalidad del programa

• El programa debe realizar el análisis sintáctico del fichero de entrada mediante la invocación de la rutina de análisis sintáctico generada por la herramienta bison,y generar la salida que se detalla en el siguiente apartado.

Descripción del fichero de salida

El fichero está formado por un conjunto de líneas de dos tipos, en concreto:

• Una línea por cada producción reducida en el proceso de análisis sintáctico.

• Una línea por cada Token reconocido (desplazado) por el analizado morfológico

Cada línea debe correspondiente a un Token desplazado debe contener la siguiente información y formato:
                        
                    D:    <token>

Donde <token> es el fragmento de entrada reconocido por el analizador morfológico y “D:” y “<token<” van separados por un tabulador.

Cada línea correspondiente a una  regla reducida tendrá el formato siguiente

                    R<nº regla>:    <regla>

Donde <nº regla> es el número que identifica la regla que se reduce según aparece en la gramática y <regla> es el texto de la regla reducida según aparece en la gramática.
“R<nº regla>” y “<regla>” van separados por un tabulador.
Los elementos que forman “<regla>” irán separados por espacios. Ejemplo:

        “<bucle> ::= MIENTRAS <exp> HACER <sentencias> FIN”

Ejemplos

• Ejemplo 1: Si el fichero de entrada es el siguiente:

//

// Programa que eleva un número entero al cuadrado

//

INICIO

   ENTERO x, resultado;

   LEER x;

   resultado=x*x;

   ESCRIBIR resultado

FIN

• El fichero de salida podría ser el siguiente:

D: INICIO

D: ENTERO

R8: <tipo> ::= ENTERO

D: x

R10: <clase_escalar> ::= <tipo>

R5: <clase> ::= <clase_escalar>

R67: <identificador> ::= TOKEN_ID

D: ,

D: resultado

R67: <identificador> ::= TOKEN_ID

D: ;

R15: <identificadores> ::= <identificador>

R16: <identificadores> ::= <identificador> , <identificadores>

R4: <declaracion> ::= <clase> <identificadores> ;

D: LEER

R2: <declaraciones> ::= <declaracion>

D: x

D: ;

R34: <lectura_escritura> ::= LEER <identificador>

R22: <sentencia> ::= <lectura_escritura>

D: resultado

D: =

D: x

D: *

R48: <exp> ::= <identificador>

D: x

D: ;

R48: <exp> ::= <identificador>

R43: <exp> ::= <exp> * <exp>

R24: <asignacion> ::= <identificador> = <exp>

R19: <sentencia> ::= <asignacion>

D: ESCRIBIR

D: resultado

D: FIN

R48: <exp> ::= <identificador>

R36: <lectura_escritura> ::= ESCRIBIR <exp>

R22: <sentencia> ::= <lectura_escritura>

R17: <sentencias> ::= <sentencia>

R18: <sentencias> ::= <sentencia> ; <sentencias>

R18: <sentencias> ::= <sentencia> ; <sentencias>

R1: <programa> ::= INICIO <declaraciones> <sentencias> FIN

• Ejemplo 2: Si el fichero de entrada es el siguiente:

//

// Programa que eleva un número x a la potencia y

//

INICIO

   ENTERO x, y;

   ENTERO i, total;

   LEER x;

   LEER y;

   i=1;

   total=1;

   MIENTRAS (i<=y) HACER

      total=total*x;

      i=i+1

   FIN;

   ESCRIBIR total

FIN

• El fichero de salida podría ser el siguiente:

Resultado Final

• Un fichero empaquetado (.zip), que contenga:

• Todos los fuentes (ficheros .h y .c) necesarios para solucionar el problema.

• Un fichero compatible con la herramienta make que para el objetivo all genere el ejecutable de nombre prbisonalfa.

El nombre del fichero zip será p2_gg_pp.zip, donde gg corresponde al grupo de prácticas y pp al número de pareja. Por ejemplo, el fichero comprimido de la pareja 5 del grupo Ma se llamará p2_ma_05.zip

Observación muy importante

• Las prácticas que no cumplan los requisitos descritos en este enunciado se considerarán como no entregadas

Fechas de entrega

• Grupos del lunes: antes del lunes 16 de abril de 2007

• Grupos del martes: antes del martes 10 de abril de 2007

• Grupos del miércoles: antes del miércoles 18 de abril de 2007

• Grupos del jueves: antes del jueves 19 de abril de 2007

• Grupos del viernes: antes del viernes 27 de abril de 2007