Tutorial de Lex & Yacc
Genreración de Parsers de Gramaticas Libres de Contexto.

Regístrate y participa en el foro: http://flex.chocoforum.com
www.medina-web.com

Índice :

Usando Yacc

Conceptos Basicos

En la seccion anterior de este documento, ya repasamos como generar un analizador lexico, un lexer o tokenizer, que puede reconocer patrones de expresiones regulares y en un momento dado determinar que es lo que se esta leyendo, pero para aplicaciones un poco más complejas, tambien puede ser necesario, analizar gramaticalmente la composicion de la entrada para en un momento dado, determinar si la entrada coincide o no con una gramatica definida y resolverla, o darle algun significado un tanto mas complejo.
Es correcto decir que yacc es una herramienta que sirve para generar un programa, capaz de analizar gramaticalmente una entrada dada por lex, a partir de una especificacion. Esta especificacion, debe contener los tokens reconocidos y los tipos de datos de los mismos si es que se ocupan para realizar operaciones sobre ellos, y una especificacion de gramatica en un formato similar a BNF (Backus Naus Form), que va desde el simbolo no terminal más general a cada una de las opciones terminales.
Ejemplo :
<Expresion>
Numero + <Expresion>
Numero - <Expresion>
Numero

En el ejemplo podemos ver que <Expresion> es un simbolo no terminal que esta compuesto por un "Numero" terminal seguido de un simbolo '+' o '-' terminales seguido por un <Expresion> no terminal, que a su vez puede ser otro numero u otra expresion mas compleja.
Es importante notar que esta especificacion es recursiva sobre <Expresion> pero no es ambigua, es decir, siempre se llegara a un terminal.
Una especificación yacc se divide en tres secciones diferentes de manera similar a lex, la de definiciones, la de reglas, y la de subrutinas, que van igualmente separadas por un '%%', mismas que pueden incluir codigo de C encerrado entre un %{ y un %}.

Ejemplo 1.1 (Mini calculadora)

A continuacion, vamos a analizar un ejemplo sencillo de una verdadera especificacion de yacc, que es la gramatica para una calculadora sencilla que permite hacer operaciones como suma, resta, multiplicacion, divición y exponente.
Download ejem1.1.y
Download ejem1.1.l
%{
#include <math.h>
%}

%union{
        double dval;
}

%token  <dval> NUMBER 
%token  PLUS    MINUS   TIMES   DIVIDE  POWER
%token  LEFT_PARENTHESIS        RIGHT_PARENTHESIS
%token  END


%left   PLUS    MINUS
%left   TIMES   DIVIDE
%left   NEG
%right  POWER

%type <dval> Expression
%start Input

%%

Input:	Line
	| Input Line
        ;

Line:	END
        | Expression END                { printf("Result: %f\n",$1); }
        ;

Expression:	NUMBER                        { $$=$1; }

        | Expression PLUS Expression    { $$=$1+$3; }
        | Expression MINUS Expression   { $$=$1-$3; }
        | Expression TIMES Expression   { $$=$1*$3; }
        | Expression DIVIDE Expression  { $$=$1/$3; }
        | MINUS Expression %prec NEG    { $$=-$2; }
        | Expression POWER Expression   { $$=pow($1,$3); }
        | LEFT_PARENTHESIS Expression RIGHT_PARENTHESIS { $$=$2; }
        ;

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

int main(void) {
  yyparse();
}

Definiciones

En esta primera seccion, al igual que en lex, incluimos las librerias que usaremos en el programa, definiciones de los tokens, tipos de datos y precedencia de la gramatica.
%union
Esta definicion, se traduce a una union de C que a su vez dara el tipo de dato a una variable global de nombre yylval que sera de donde yacc tomara los datos a procesar, en la union se definen miembros cuyos correspondientes tipos de datos serán usados para dar el tipo de dato a los tokens como se explicara en la siguiente seccion. %union se traduce de la siguiente forma :
En yacc :

%union{
        double dval;
}

En C :

typedef union
{
        double dval;
} YYSTYPE;

Con esta definicion, yacc declara algunas uniones de este tipo, de las cuales la mas importante es :
YYSTYPE yylval;
que sera usada en la especificacion de lex, del mismo programa para asignarle valor a los tokens que yacc usara para realizar operaciones. Esta estructura puede llegar a ser muy compleja, y para saber de que tipo es cada token devuelto por yylex(), se usan las definiciones %token y %type.
%token y %type
%token sirve para definir los tokens que hay, y si es necesario, el tipo de dato que usan, todos los tokens son tomados como simbolos terminales, lo cual veremos mejor reflejado en la seccion de reglas, estos tambien tienen el objetivo de servir como etiquetas que yylex() regresa a yacc para identificar el token que se ha leido recientemente.
Su uso es como sigue :
%token [<miembro_de_union>] ETIQUETA1 [ETIQUETA2 ... ETIQUETAn]
Donde todo lo que esta entre [ y ] es opcional.
<miembro_de_union> : Indica el miembro al que seran mapeados los tokens en la union yylval dentro de lex.
ETIQUETAS : Estos son los nombres con los que se identificaran los tokens mismos, que serán traducidos en C como numberos en instrucciones #define del preprocesador de C.

%type es analogo a %token, solo que este define el tipo de dato para simbolos no terminales de nuestra gramatica, la unica diferencia es que el tipo de dato a usar es obligatorio.
En nuestro ejemplo :
%token  <dval> NUMBER 
%token  PLUS    MINUS   TIMES   DIVIDE  POWER
%token  LEFT_PARENTHESIS        RIGHT_PARENTHESIS
%token  END

.
.
.

%type <dval> Expression
La primera linea indica que el token NUMERO sera del tipo de miembro de dval, es decir, un double.
Las siguientes tres lineas, son para definir algunos tokens mas que seran usados en la gramatica, pero no necesitan un tipo de dato ni un miembro en yylval asociado.
En la ultima linea definimos el tipo de dato que usara nuestro no terminal Expression.
%left y %right
El siguiente paso, es definir el tipo de precedencia de nuestros tokens operadores, en este punto tenemos dos factores, la precedencia por si misma, y la agrupación de los operadores.
Precedencia
La precedencia es asignada en orden inverso al que aparecen, es decir, el ultimo operador declarado, tiene mayor precedencia que el anterior y asi sucesivamente.
Asociatividad
%left y %right indican si el operador se agrupa a la derecha o a la izquierda, por ejemplo, en el caso de POWER (Exponente) debe asociarse a la derecha, por que buscamos que se resuelva de ese modo, de derecha a izquierda, por ejemplo :
Buscamos que
	4^3^5^2^9
sea evaluado asi :
	4^(3^(5^(2^9)))
Por lo contrario, las sumas y restas queremos resolverlas de izquierda a derecha:
Buscamos que
	4-3+5+2-9
sea evaluado asi :
	(((4-3)+5)+2)-9
Usar este tipo de declaraciones es importante para dismiuir la posibilidad de ambiguedades en el lenguaje generado.
%start
En algunos casos es conveniente indicarle a yacc cual es el simbolo (no terminal) inicial a la hora de hacer el parseo, es decir, el simbolo que se trata de reducir, si esta opcion no es especificada, yacc toma al primer simbolo de la seccion de reglas como simbolo inicial.
En nuestro ejemplo, se presentan ambos casos, nuestro simbolo inicial "Input" se encuentra al inicio del archivo y tambien esta declarado como simbolo inicial.
%start Input

Reglas

En esta parte finalmente llegamos a la definición de la gramatica, aca podemos observar que cada simbolo se define con su nombre, seguido de dos puntos ":" seguidos de varios simbolos que conformaran su composicion gramatical que en caso de tener varias opciones, son separados por "|" (or) indicando que se tienen varias opciones para reducir ese simbolo y para terminar cada regla, un ";".
Ejemplo :
Si tomamos la gramatica que definimos al principio de esta seccion :
<Expresion>
Numero + <Expresion>
Numero - <Expresion>
Numero

Y la transformamos a una regla de yacc, se veria como esto:

Expresion: NUMERO '+' Expresion		{$$ = $1 + $3;}
	| NUMERO '-' Expresion		{$$ = $1 - $3;}
	| NUMERO			{$$ = $1;}
	;

en el ejemplo ya transformado a una regla gramatical de yacc, podemos ver que ya se especifica que hacer con los simbolos de la gramatica una vez que son resueltos en la parte de codigo de C. En este ejemplo, Expresion es el simbolo no terminal que se esta definiendo de manera recursiva, el valor que tomara una vez resuelto es el valor asignado a la variable $$, que traducida a C es una variable mapeada al simbolo no terminal, $1, $2 y $3 son variables que son mapeadas al valor de los simbolos de cada linea de cada regla, estas son numeradas de izquierda a derecha.
Ejemplo :
En este segmento de regla :

Expresion: NUMERO '+' Expresion

Expresion equivale a $$
NUMERO equivale a $1
'+' equivale a $2
y
Expresion (la parte recursiva) equivale a $3

todo esto claro, en la parte de acciones en C para cada linea de la regla en yacc.
En el ejemplo tambien podemos encontrar el uso de %prec que sirve para cambiar la precedencia de un operador dependiendo del contexto en el ejemplo, le estamos dando una más alta precedencia a la operacion "menos" cuando esta en un contexto unario, que a la mayoria de los operadores excepto el POWER (exponente) :
.
.
.
| MINUS Expression %prec NEG    { $$=-$2; }
.
.
.
Reducción
Yacc reduce sus reglas generando un parse tree (no literalmente), y va resolviendo cada regla completa tan pronto como puede, lo cual nos trae un detalle de diseño de gramaticas en yacc, y es la diferencia entre especificar la recursividad por la derecha o por la izquierda, para expresiones muy sencillas que generen un parse tree pequeno no hay ningun problema pero para casos donde la reduccion es compleja, puede desbordar la pila ya que cuando la recursion es derecha, para resolverla, tiene que guardar los datos de la izquierda, y si estos son demaciados, no puede manejarlos.
Por lo contrario, cuando la recursion es izquierda, no tiene que guardar datos que no va a utilizar por que recorre el arbol de izquierda a derecha y resuelve las reglas tan pronto como puede.
En el ejemplo anterior tenemos la recursion por la derecha, un analogo recurrente por la izquierda seri como este :

Expresion: Expresion '+' NUMERO 		{$$ = $1 + $3;}
	| Expresion '-' NUMERO 		{$$ = $1 - $3;}
	| NUMERO			{$$ = $1;}
	;

Especificacion de Lex para el ejemplo1.1
Para que el Ejemplo1.1 pueda funcionar, al igual que cualquier otro programa en yacc, necesita un tokenizer, y a continuacion tenemos su tokenizer correspondiente escrito en lex.

%{
#include "y.tab.h"
#include <stdlib.h>
#include <stdio.h>
%}

white           [ \t]+
digit           [0-9]
integer         {digit}+

%%

{white}         { /* Ignoramos espacios en blanco */ }
"exit"|"quit"|"bye"	{printf("Terminando programa\n");exit(0);}
{integer}	{
                  yylval.dval=atof(yytext);
                  return(NUMBER);
                }

"+"           return(PLUS);
"-"           return(MINUS);
"*"           return(TIMES);
"/"           return(DIVIDE);
"^"           return(POWER);
"("           return(LEFT_PARENTHESIS);
")"           return(RIGHT_PARENTHESIS);
"\n"  return(END);

%%
Acerca de la seccion de definiciones de este lexer, lo unico relevante que podemos mencionar es la linea de C que dice :
#include "y.tab.h"
esta linea incluye al archivo y.tab.h que contiene algunas de las definiciones de yacc que lex necesita para poder interactuar con el, entre las mas importantes se encuentran definidas todas las etiquetas de los tokens, como PLUS, MINUS, NUMBER, etcetera. Estas constantes son los valores que yylex() regresara a yyparse() (la funcion del parser de yacc) para identificar el tipo de token que recien se ha leido.
En la seccion de reglas, en la parte del codigo, podemos ver como al final de cada regla, se hace un return especificando la etiqueta que fue declarada como %token o como %left/%rigth en la especificacion yacc.
Para compilar y correr este ejemplo en sistemas UNIX o similares :
$ lex ejem1.1.l
$ yacc -d ejem1.1.y
$ cc -o ejem1.1 lex.yy.c y.tab.c -ly -ll -lm
$ ejem1.1
25*5-5
Result: 120.000000
5^2*2
Result: 50.000000
5^(2*2)
Result: 625.000000
bye
Terminando programa
$

Subrutinas

En esta ultima seccion, es posible reimplementar, siguiendo la misma idea de lex, algunas funciones que pueden ser utiles en algun momento dado o declarar nuevas funciones para usar dentro de nuestro codigo o nuestras reglas, no hay mucho que reimplementat a este nivel (yacc) a menos que sea con propositos realmente especificos. Las funciones mas comunmente implementadas son main() e yyerror(), la primera se usa para presonalizar el programa con mensajes antes o despues del parser, o para llamarlo varias veces en el codigo y la segunda la ocupa yyparse() cada vez ue encuentra un error de sintaxis, en este ejemplo, se incluyen ambas con su contenido minimo.


Copyright © 2002 Oscar Medina Duarte
Cualquier persona es libre de imprimir y reproducir este documento siempre y cuando esta nota permanezca en el documento.