FLEX e BYACC – Revista PROGRAMAR

Ao longo desta série de artigos, temos vindo a ver como utilizar as ferramentas FLEX e BYACC para escrever uma calculadora simples. No primeiro artigo vimos como escrever o scanner da nossa calculadora usando FLEX e no segundo como escrever o parser usando BYACC. Neste artigo veremos o que nos falta para conseguir criar o executável da nossa calculadora, e como lhe adicionar funcionalidade eficientemente.

O ficheiro do parser que vimos no artigo anterior estaria completo, mas como o código do scanner é C e o do parser é C++, precisamos de dar uma ajuda ao BYACC.

#include <cstdlib>
 
extern "C"
{
        int yyparse(void);
        int yylex(void);  
        int yywrap()
        {
                return 1;
        }
        void yyerror(char *);
 
}

Declaramos as funções do scanner que o parser usa como funções C no bloco dos #includes do parser e resolvemos o problema. Para concluir o exemplo vejamos como expandir a nossa calculadora, adicionando-lhe variáveis por exemplo. Introduzir variáveis implica alterar o parser e o scanner simultaneamente. Começando pelo parser, vejamos do que precisamos para ter variáveis. Sendo uma calculadora simples as nossas variáveis vão conter sempre doubles, e são identificadas por uma string, portanto podemos usar um map para as guardar. Também vamos necessitar dum novo token que nos indique uma variável, e de outro token que sirva como operador de atribuição. Vejamos a nova primeira secção do parser:

%{
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
 
extern "C"
{
        int yyparse(void);
        int yylex(void);  
        int yywrap()
        {
                return 1;
        }
        void yyerror(char *);
 
}
 
std::map<std::string, double> varMap;
 
%}
 
%union {
  double d;
  char * s;
};
 
%token<d> NUMBER
%token<s> VARIABLE
%token NL
 
%right '='
%left '+' '-'
%left '*' '/'
%right '^'    
%nonassoc UMINUS
 
%type<d> expr

Temos o mapa onde guardamos as variáveis, varMap, um novo tipo na %union, char * para o novo token VARIABLE, e um operador de atribuição =, associativo à direita e com a menor precedência de todos os operadores. A segunda secção do parser segue-se:

%%
 
expr_list   : expr NL            { std::cout << $1 << std::endl; }
            | expr_list expr NL  { std::cout << $2 << std::endl; }
            ;            
 
 
expr : NUMBER                    { $$ = $1; }
     | VARIABLE                 
     {
       std::string key($1);
       $$ = (varMap.find(key) != varMap.end())? varMap[key] : 0;
     }
     | '-' expr %prec UMINUS     { $$ = -$2; }
     | expr '+' expr             { $$ = $1+$3; }
     | expr '-' expr             { $$ = $1-$3; }
     | expr '*' expr             { $$ = $1*$3; }
     | expr '/' expr             { $$ = $1/$3; }
     | expr '^' expr             { $$ = pow($1, $3); }
     | VARIABLE '=' expr        
     {
       std::string key($1);
       varMap[key] = $3;
       $$ = varMap[key];
     }
     | '(' expr ')'              { $$ = $2; }
     ;
 
 
%%

A gramática mantém-se praticamente inalterada, só adicionámos duas novas produções, uma para indicar que uma expressão pode ser uma variável e a outra para indicar que uma expressão pode ser uma atribuição. Ambas têm acções associadas, a primeira verifica se a variável se encontra no mapa, se sim atribui à cabeça o valor da variável no mapa, se não atribui zero. A segunda atribui ao valor da variável no mapa o valor da expressão, e à cabeça o valor da variável no mapa, ou seja é possível escrever (f = 3) + 5 e obter 8 mas sendo atribuído 3 a f. A terceira secção mantém-se inalterada portanto com isto concluímos o parser.

O novo scanner necessita de ainda menos alterações que o parser, basta enviarmos os novos tokens VARIABLE e =. Para o token VARIABLE adicionamos a seguinte expressão regular na primeira secção:

    IDENTIFIER  [A-Za-z_][A-Za-z0-9_]*

e a seguinte regra na segunda secção:

    {IDENTIFIER}     { yylval.s = strdup(yytext); return VARIABLE; }

Para adicionar o token = só necessitamos de alterar a regra,

[-+*/^()]        return *yytext;

para:

[-+*/=^()]       return *yytext;

Os ficheiros finais do scanner e do parser encontram-se abaixo.

%option outfile="CalculatorScanner.c"

%{
#include "CalculatorParser.tab.h"


void yyerror(char * err_msg)
{
    printf("%s\n", err_msg);
    exit(1);
}

%}

IDENTIFIER  [A-Za-z_][A-Za-z0-9_]*
WS          [ \t]
NL          "\n"|"\r"|"\r\n"
DIG         [0-9]
 
 
MANTISSA    ({DIG}*\.{DIG}+)|({DIG}+\.)
EXPONENT    [eE][-+]?{DIG}+
 
INT         (0|[1-9]{DIG}*)
DOUBLE      {MANTISSA}{EXPONENT}?
 
%%
 
 
{IDENTIFIER}     { yylval.s = strdup(yytext); return VARIABLE; }
{INT}|{DOUBLE}   { yylval.d = strtod(yytext, NULL); return NUMBER; }
 
 
[-+*/=^()]       return *yytext;
 
{NL}             return NL;
{WS}             ; /* ignore whitespace */
 
.                yyerror("Unknown character");
 
%%

%{
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <string>
 
extern "C"
{
        int yyparse(void);
        int yylex(void);  
        int yywrap()
        {
                return 1;
        }
        void yyerror(char *);
 
}
 
std::map<std::string, double> varMap;
 
%}
 
%union {
  double d;
  char * s;
};
 
%token<d> NUMBER
%token<s> VARIABLE
%token NL
 
%right '='
%left '+' '-'
%left '*' '/'
%right '^'    
%nonassoc UMINUS
 
%type<d> expr
 
%%

expr_list   : expr NL            { std::cout << $1 << std::endl; }
            | expr_list expr NL  { std::cout << $2 << std::endl; }
            ;            


expr : NUMBER                    { $$ = $1; }
     | VARIABLE                 
     {
       std::string key($1);
       $$ = (varMap.find(key) != varMap.end())? varMap[key] : 0;
     }
     | '-' expr %prec UMINUS     { $$ = -$2; }
     | expr '+' expr             { $$ = $1+$3; }
     | expr '-' expr             { $$ = $1-$3; }
     | expr '*' expr             { $$ = $1*$3; }
     | expr '/' expr             { $$ = $1/$3; }
     | expr '^' expr             { $$ = pow($1, $3); }
     | VARIABLE '=' expr        
     {
       std::string key($1);
       varMap[key] = $3;
       $$ = varMap[key];
     }
     | '(' expr ')'              { $$ = $2; }
     ;
 
 
%%
 
int main()
{
    yyparse();
}

Tendo dado ao scanner o nome de CalculatorScanner.l e ao parser o nome de CalculatorParser.y, basta correr os seguintes comandos na shell para criar o executável calculator.

flex CalculatorScanner.l
byacc -dtv -b CalculatorParser CalculatorParser.y
gcc -c CalculatorScanner.c
g++ -c CalculatorParser.tab.c
g++ -o calculator CalculatorParser.tab.o CalculatorScanner.o

Esta série de artigos pretende-se apenas como uma introdução a estas ferramentas e como tal não cobre muitos dos aspectos do FLEX e do BYACC. Compreender o uso de estados num analisador lexical é fundamental em aplicações mais sofisticadas, e a introdução às gramáticas aqui feita é ténue e não aborda os conceitos com exactidão, tendendo a focar-se em explicações mais intuitivas. Para usar estas ferramentas com proficiência, é necessário mais estudo, para o qual pode consultar: http://dinosaur.compilertools.net/

E ler os seguintes livros:

lex & yacc, 2nd edition, John R. Levine, Tony Mason, Doug Brown, 1995, ISBN 10: 1-56592-000-7, ISBN 13: 9781565920002, O’Reilly & Associates
Compilers: Principles, Techniques, & Tools (2nd Edition), Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, 2006, ISBN-10: 0321486811, ISBN-13: 978-0321486813, Addison-Wesley Professional

Revista PROGRAMAR

A revista portuguesa de programação