BYACC

No artigo anterior adquirimos algumas noções sobre FLEX e vimos como implementar um scanner simples. Relembrando, o FLEX é um gerador de analisadores lexicais ou scanners, e o BYACC é um gerador de parsers. Usados em conjunto permitem escrever aplicações bastante sofisticadas, mas no nosso artigo limitamo-nos a considerar uma calculadora simples, servindo como exemplo introdutório. Agora que temos o scanner para a nossa calculadora escrito podemos começar a considerar o parser.

Um ficheiro BYACC tem a mesma estrutura que o FLEX, já que o analisador lexical em que o FLEX se baseia, o LEX, copiou a sua estrutura do YACC, o gerador de parsers em que o BYACC se baseia. Como tal o nosso ficheiro BYACC vai ser algo deste género:

definições

%%

gramática

%%

int main()
{
    yyparse();
}

Comecemos por considerar como é que o parser e o scanner funcionam em conjunto. Um parser recebe tokens e verifica se esses tokens estão a seguir uma gramática. O que nós estávamos a retornar no scanner, o NUMBER e o NL são esses tokens. Os tokens podem ter um valor associado ou não. O que o parser faz é ver se eles seguem a gramática que ele define. Se o objectivo do parser for só verificar que um certo ficheiro, por exemplo um ficheiro XML, segue a especificação da linguagem, podemos não ter interesse nenhum em saber o valor de qualquer token. A nossa calculadora no entanto, precisa de produzir resultados, portanto necessita de saber o valor de cada token NUMBER que recebe. O parser define os tokens e o tipo de valores que lhes podem estar associados na zona das definições, sempre que precisa de um token novo ele chama o scanner com o resto do input que falta analisar. Vejamos a definição dos tokens para a nossa calculadora:

%union {
    double d;
};

%token<d> NUMBER
%token NL

%left '+' '-'
%left '*' '/'
%right '^'    
%nonassoc UMINUS


%%

...

%%

int main()
{
    yyparse();
}

A primeira coisa que encontramos é uma %union, seguida da declaração de dois tokens, NUMBER e NL. A %union serve para indicar tipos que queiramos associar a tokens e eventualmente a elementos da gramática. Ao escrevermos %token<d> NUMBER estamos a indicar que para além de NUMBER ser um token, tem um valor associado do tipo d, neste caso double. Isto vai ser importante quando passarmos para a gramática e é por esta razão que no scanner passávamos o número que tínhamos lido ao yylval.d antes de retornarmos o token. A informação da union e dos tokens que escrevermos nesta secção vai servir para o BYACC gerar o header ao qual o nosso scanner fez #include e que permite ao scanner e ao parser comunicarem entre si. O +, -, *, /, ^UMINUS também são tokens mas aqui para além de indicarmos que são tokens estamos a indicar a associatividade dos operadores, um conceito que o leitor deverá conhecer, mas que abordaremos com maior profundidade na gramática.

%{
#include <iostream>
#include <cmath>
%}

%union {
    double d;
};

%token<d> NUMBER
%token NL

%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; }
     | '-' 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); }
     | '(' expr ')'              { $$ = $2; }
     ;


%%

int main()
{
    yyparse();
}

Esta versão do parser introduz a gramática, mas comecemos por observar as diferenças na secção das definições. Podemos ver primeiro que a introdução de código C/C++ se processa da mesma forma que no scanner. Em seguida temos a instrução, %type<d> exprexpr não é um token, é outro símbolo da gramática mas ainda assim tem um tipo, portanto temos que o indicar.

Uma gramática, tal como a gramática da língua portuguesa, serve para nos indicar a estrutura da linguagem, quais as composições de elementos que são válidas ou não de acordo com a linguagem. É fácil de ver como isto é útil para um compilador. A nossa calculadora tem uma gramática muito simples, mas ainda assim tem-la, portanto temos que compreender alguns princípios sobre gramáticas. As gramáticas são um conjunto de regras, às quais chamamos produções, constituídas por uma cabeça e um corpo. Por exemplo:

    stmt : WHILE expression stmt;

é uma produção, com cabeça stmt e corpo WHILE expression stmt. A cabeça indica-nos uma construção da gramática e o corpo como ela é composta. Os elementos duma gramática dividem-se em símbolos terminais e não terminais, sendo os terminais, para efeitos deste artigo, os tokens que o scanner envia e os não-terminais as cabeças de produções, ou seja símbolos que podem ser produzidos através doutros símbolos.

Por clareza, usamos maiúsculas para representar terminais e minúsculas para não terminais, logo, no exemplo acima, stmt e expression são símbolos não terminais enquanto que o WHILE é terminal. Um símbolo terminal não pode ser obtido através da junção de outros símbolos, portanto só pode aparecer em corpos de produções. Um não terminal por outro lado pode ser derivado de terminais e outros não terminais, logo pode aparecer tanto na cabeça como no corpo duma produção.

Um símbolo não terminal pode, e habitualmente, tem várias definições. Pegando no exemplo anterior e expandindo, obtemos,

stmt : WHILE expression stmt;     
stmt : IF expression stmt;  
stmt : IF expression stmt ELSE stmt;
stmt : block;
...

faz sentido criar várias produções para um stmt, já que um stmt pode ser várias coisas. Neste caso, um while, um if, um bloco, e continuando teríamos um for, um switch, um do while, etc. Sendo usual a existência de várias produções com a mesma cabeça, o BYACC permite usar a seguinte sintaxe, com significado equivalente, para aumentar a legibilidade:

stmt : WHILE expression stmt    
     | IF expression stmt 
     | IF expression stmt ELSE stmt
     | block
...
     ;

Se quiséssemos escrever um parser para uma linguagem de programação, tínhamos de ter uma forma de relacionar as várias regras, por outras palavras uma gramática necessita de uma estrutura. A forma de criar essa estrutura é criando um símbolo não terminal inicial ao qual todos os outros estão subordinados. Pode ajudar pensar na estrutura da gramática como uma árvore na qual o símbolo não terminal inicial é a raiz, os outros não terminais são nós e os terminais são as folhas.

%%

program : list    
        ;

list    : statement
        | list statement
        ;

statement : declaration
          | function
          ;

declaration : type identifier
            | type identifier '=' expression
            ;

type : INT
     | DOUBLE
     | CHAR
     ;

function : type identifier '(' arg_list ')' block
         ;

block : '{' stmt_list '}'
      ;

stmt_list : stmt
          | stmt_list stmt
          ;
...

%%

Acima temos um esqueleto de uma linguagem muito simplificada, ainda com vários não terminais sem produções associadas, mas basta para termos uma noção da estrutura duma gramática. Qualquer que seja o programa escrito para esta linguagem, se ele estiver sintacticamente correcto deve ser possível partir de program e derivar todos os elementos que o compõem. Neste caso program é o símbolo inicial da gramática, e indicamos isso ao BYACC colocando-o como a primeira produção do ficheiro.