PDF de programación - yacc

YACC



Yacc (Yet Another Compiler Compiler) es un programa que permite construir analizadores gramaticales en C a
partir de una gramática libre al contexto. Junto con Lex permite construir rápidamente las primeras etapas de un
traductor. Tanto Lex como Yacc son herramientas que fueron desarrolladas junto con el sistema UNIX y es posible
encontrar implantaciones de ellas en otras plataformas como PC y Macintosh, al la vez que existen versiones de
dominio público bajo los nombres de Flex y Bison.

Un analizador gramatical construido en Yacc genera una función que realizará el análisis gramatical con el nombre
de yyparse(); esta función solicita un token al analizador de léxico por medio de la función yylex(). La comunicación
que se da entre ambas funciones se muestra en el siguiente diagrama.


Un programa en Yacc tiene tres secciones. Estas secciones están delimitadas por %% como en Lex. La estructura
del programa en Yacc es:



Definición del ambiente del analizador gramatical
%%
Gramática libre al contexto
%%
Procedimientos auxiliares

La sección de definición del ambiente del analizador gramatical posee una sección donde se hacen definiciones
sobre las variables que el analizador empleará. Esta sección esta delimitada por %{ y %} ; en ella se hacen
definiciones en C y se toma literalmente (Yacc no la revisa). En esta primera sección encontramos una serie de
directivas de Yacc que permiten definir:


Los símbolos terminales que la
gramática empleará.
El axioma o símbolo inicial de la
gramática.

Los atributos que los símbolos de la
gramática pueden poseer.

%token

%start
%union
{
tipo1 atributo1;
tipo2 atributo2;
...
tipon atributon;
}

El atributo que cada símbolo posee. %type <atributo>



1

La segunda sección está constituida por la gramática libre al contexto que guiará al analizador gramatical. La
notación empleada es:

noterminal : regla1

| regla2
| regla3
...
| reglan
;

donde regla1 a reglan representan las N producciones que tiene el noterminal en la gramática.

La tercer sección de un programa en Yacc tiene los procedimientos auxiliares que hacen operativo al analizador de
léxico. En lo más simple, posee las funciones main y yyerror. Esta última sirve para especificar la reacción del
analizador gramatical al encontrar un error. main simplemente invoca al analizador gramatical.

Un caso práctico

Supongamos que se quiere construir un analizador gramatical para revisar expresiones aritméticas constituidas por
identificadores, números enteros y los operadores de suma, resta, multiplicación y división. El programa en Yacc
para determinar si una expresión está bien o mal escrita es el siguiente:

%{
%}
%token ID NUM PA PC OPSR OPMD
%start NIVEL2
%%
NIVEL2 : NIVEL2 OPSR SIG_NIVEL

| SIG_NIVEL
;

SIG_NIVEL : SIG_NIVEL OPMD OPERANDO

| OPERANDO
;

OPERANDO : ID

| NUM
| PA NIVEL2 PC
;

%%

main()
{
yyparse();
}

yyerror(char * s)
{
printf("%s \n",s);
}



2

Al procesar este archivo (llamémoslo anagram.y) en Yacc a través de la siguiente orden:


yacc -d anagram.y



se generará el programa anagram.c que contendrá la función yyparse() y el archivo yytab.h (a consecuencia de la
opción -d) que contiene la designación de los valores a los tokens empleados en la gramática (especificados por la
directiva %token). Yacc asigna los valores a los tokens a partir del 257; así que


%token ID NUM PA PC OPSR OPMD


genera en yytab.h las siguientes definiciones:

#define ID 257
#define NUM 258
#define PA 259
#define PC 260
#define OPSR 261
#define OPMD 262

La función yyerror(char * s) espera una secuencia de caracteres que representa el mensaje de error que el
analizador gramatical encuentra; el mecanismo más simple de manejo es desplegar ese error (que es lo que hace
en este caso la función ).

El programa en Lex que realizará el análisis de léxico (analex.l) para devolver el token para cada unidad de léxico
será:

%{
#include "yytab.h"
%}

L [A-Z]
D [0-9]
B [ \t\n]

%%
{L}+ return ID;
{D}+ return NUM;
[\+\-] return OPSR;
[\*\/] return OPMD;
[\(] return PA;
[\)] return PC;
{B}
.
%%

En el programa en Lex incluye al archivo yytab.h para que al reconocer a cada patrón, devuelva el token como está
definido en el programa anagram.y.

Los dos programas generados, anagram.c y analex.c, se unen para formar un solo ejecutable que realizará el
análisis gramatical. Como ya se mencionó, yyparse() ya tiene invocaciones a yylex().

Supongamos ahora que lo que quiere obtener no es solo saber si la expresión aritmética está bien o mal escrita,
sino evaluarla si es correcta gramaticalmente. Se espera tener un valor numérico entero para cada operando en la
expresión y un carácter para saber que operador aplicar (ya que se tienen en las categorías OPSR cuando se es
suma o resta y OPMD cuando es multiplicación o división). En Yacc esto se especifica con %union de la siguiente
manera:



3

%union {

int valor;
char operador;
}

Ahora hay que designar que tipo de atributo se aplicará a cada símbolo en la gramática; un operando puede ser ID,
NUM, OPERANDO, SIG_NIVEL y NIVEL2, por lo que éstos tendrán el atributo valor; mientras que los operadores
OPSR y OPMD, tendrán el atributo operador. En Yacc está asociación se da con la directiva %type <atributo>


%type <valor> ID NUM NIVEL2 SIG_NIVEL OPERANDO
%type <operador> OPSR OPMD


Como los paréntesis no tienen ningún uso al evaluar una expresión, ni PA ni PC tienen asociado atributo alguno.

En Yacc puede asociarse a cada producción una acción codificada en C; si en esa acción se quiere referir a los
atributos que un símbolo de la gramática posee, se hace referencia a él por medio de $$ si es el noterminal que
está definiendo la producción y $1, $2 ... $n para los símbolos gramaticales que se encuentran en el lado derecho
de la producción en el orden 1, 2 ... n. Por ejemplo, si queremos que al encontrar dos elementos que deben
multiplicarse o dividirse al cumplirse la regla:


SIG_NIVEL : SIG_NIVEL OPMD OPERANDO


podemos referir la acción como


$$=opera($2,$1,$3);



suponiendo que la función opera espera en primer lugar un carácter que representa la operación a realizar y los
dos siguientes parámetros sean los valores numéricos de los operandos; el resultado de la operación se asigna a
$$ porque éste será el nuevo valor de SIG_NIVEL después de cumplirse la regla.

La acción por omisión que tiene definida Yacc es $$=$1; por lo que el programa completo para evaluar una
expresión aritmética en Yacc es:


%{

%}

%token ID NUM PA PC OPSR OPMD
%union {

int valor;
char operador;
}

%type <valor> ID NUM NIVEL2 SIG_NIVEL OPERANDO
%type <operador> OPSR OPMD
%start NIVEL2
%%
NIVEL2 : NIVEL2 OPSR SIG_NIVEL {

$$=opera($2,$1,$3);
printf("%d %c %d = %d\n",$1,$2,$3,$$);

}



4

| SIG_NIVEL
;

SIG_NIVEL : SIG_NIVEL OPMD OPERANDO {

$$=opera($2,$1,$3);
printf("%d %c %d = %d\n", $1, $2, $3, $$ );

}

| OPERANDO
;

OPERANDO : ID

| NUM
| PA NIVEL2 PC {$$=$2;}
;

%%

main()
{
yyparse();
}

opera( char a, int b, int c )
{
switch (a)
{

case '+': return (b+c);
case '-': return (b-c);
case '*': return (b*c);
case '/': return (b/c);

}
}

yyerror(char *s)
{
printf ("%s \n",s);
}

Este programa supone que ID y NUM son capaces de obtener un valor al momento que se reconocen por el
analizador de léxico. Esto obliga a modificar el programa en Lex para que esto ocurra. El analizador gramatical en
Yacc crea un espacio para poder asociar un valor a cada símbolo por medio de la variable yylval, que es del tipo
definido por %union. Así que al asociar un valor desde Lex a un terminal, es necesario hacer referencia a la
entidad que representa al atributo. Por ejemplo, si NUM debe asociar un valor entero como atributo, la orden


yylval.valor=atoi(yytext);


hace esta asignación al convertir el lexema de NUM en un entero y asociarlo a yylval.valor. El programa completo
en Lex quedará como sigue:



5

%{
#include "yytab.h"
%}

L [A-Z]
D [0-9]
B [ \t\n]

%%
{L}+ {yylval.valor=*(yytext); return ID;}
{D}+ {yylval.valor=atoi(yytext); return NUM;}
[\+\-] {yylval.operador=*(yytext); return OPSR;}
[\*\/] {yylval.operador=*(yytext); return OPMD;}
[\(] return PA;
[\)] return PC;
{B}
.
%%

Como no se tiene una tabla de símbolos para guarda un valor a cada identificador, se asume que su valor es el
valor ascii del primer carácter de su lexema. Tanto para PA como para PC no hay asignación de yylval ya que
éstos no tienen definido atributo por %type.



6