señor

1.- OBJETIVOS
El objetivo de esta práctica es realizar un analizador sintáctico descendente recursivo en C,
para el lenguaje planteado durante el curso. El analizador sintáctico a generar se apoyará en el
analizador léxico desarrollado en la práctica 2.
2.- ANÁLISIS SINTÁCTICO DESCENDENTE RECURSIVO
2.1 Características generales
Un analizador sintáctico es una aplicación que recibe comoentrada un flujo de componentes
léxicos (tokens) y verifica que dicha secuencia es válida para una cierta gramática libre de contexto.
Dada una gramática, existen diferentes formas de construir un analizador sintáctico que
la reconozca. En la práctica anterior se presentó una herramienta, llamada Bison, que desarrolla
de manera automática un analizador basado en un algoritmo de análisis sintácticoascendente
(Bison utiliza el algoritmo de análisis LALR). En esta práctica el analizador sintáctico se debe
construir de forma manual siguiendo un algoritmo de análisis descendente.
El desarrollo del analizador sintáctico se va a traducir en un la programación de un fichero
en C, que llamaremos Anasint.c, que contiene un conjunto de funciones dedicadas a analizar
la gramática deseada. Elpunto de entrada del analizador va a ser una función que vamos a llamar
yyparse() (por mantener el mismo nombre que el utilizado por la herramienta Bison). La función
yyparse() debe devolver un valor entero. Si el fichero de entrada analizado es correcto, es decir,
si corresponde a la gramática deseada, la función yyparse() debe devolver 0. Si, por el contrario,
el fichero de entrada esincorrecto, es decir, si no corresponde a la gramática deseada, la función
yyparse() devolverá el valor 1.
Internamente, las funciones del analizador sintáctico van a llamar a la función yylex(), que
desarrolla el análisis léxico. El analizador léxico es el único módulo que lee realmente el contenido
del fichero de entrada. Cada llamada al método yylex() devuelve el código del último
componente léxicoleído. El valor de dicho componente léxico se debe almacenar en la variable
yylval. En el desarrollo de esta práctica se hará uso del analizador léxico desarrollado en la segunda
práctica de la asignatura.
2.2 Algoritmo de análisis sintáctico descendente recursivo
Los analizadores sintácticos descendentes recursivos son una forma sencilla de programación
“a mano” de analizadores sintácticos.Sin embargo, esta técnica no puede emplearse
Analizador Léxico fentrada int yylex()
Analizador Sintáctico
int yyparse() caracteres
yylex()
tokenTeoría de Autómatas y Lenguajes Formales 2
Ciencias de la Computación e Inteligencia Artificial 2010-2011
sobre cualquier gramática libre de contexto, sino sólo sobre el conjunto de gramáticas denominadas
LL(1). La idea básica de este tipo deanálisis consiste en asociar una función a cada símbolo
no terminal de la gramática. El objetivo de esta función es reconocer sintácticamente ese
símbolo. De esta manera, la ejecución de una regla formada por los símbolos A, B y C consiste
en ejecutar las funciones asociadas a esos simbolos, es decir, “ A( ); B( ); C( ); ”. Para describir
el código de un analizador sintáctico descendente recursivovamos a explicar el código asociado
a la siguiente gramática:
Esta gramática corresponde a un lenguaje formado por listas de identificadores o números
separados por coma. A continuación se muestra el código C que desarrolla un analizador sintáctico
descendente recursivo para esta gramática.
Lista ::= Elemento SigueLista
SigueLista ::= ‘,’ Elemento SigueLista
| λ
Elemento ::= ID
| NUMERO#include
#include “analex.h”
#include “anasint.h”
extern int yylex(); /* Esta es la función que desarrolla el análisis léxico */
extern void yyerror(const char* s); /* Esta es la función de error sintáctico */
int nextToken; /* Token de preanálisis */
int yyparse()
{
nextToken = yylex();
if( parseLista() != 0 ) { yyerror(“Fichero INCORRECTO”); return 1; }
if( nextToken != EOF) {...