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 +, -, *, /, ^ e 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> expr, expr 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.
Já vimos nos exemplos anteriores que as produções podem ser recursivas, o corpo duma produção pode conter o mesmo não terminal que é a cabeça. A recursividade é necessária e algo que o BYACC processa muito eficientemente, mas usada sem cuidado é uma das coisas que introduz conflitos na gramática. Um conflito surge quando o parser não sabe que regra usar para uma determinada sequência de tokens. Um exemplo segue-se:
s : x | y ; x : A B C ; y : A B C ;
Este caso é óbvio, temos duas produções diferentes com o mesmo corpo, o parser não sabe qual deve usar quando recebe os três tokens. O mesmo se passa nos casos seguintes.
s : x | y ; x : A B C ; y : A z C ; z : B ;
s : x | y ; x : A B C ; y : z C ; z : A B ;
O BYACC só tem um token de lookahead, ou seja, no caso abaixo ele não consegue decidir se o que recebeu foi o x ou o y porque no momento de escolher a produção ele só sabe que o se segue é o token C. Como existem dois casos com o token C, ele não sabe o que fazer. Isto não é um problema com a gramática, é uma limitação do BYACC.
s : x C D | y C F ; x : A B; y : A B;
O mesmo não ocorre no caso seguinte. Nesta situação ele consegue saber que produção usar vendo se o lookahead é D ou F.
s : x D | y F ; x : A B; y : A B;
A existência de conflitos na gramática não impede o parser de ser gerado, já que o BYACC tem comportamentos default quando não sabe que produção usar, mas claro que o comportamento default pode não ser o que o programador tinha em mente quando escreveu a gramática portanto convém eliminar os conflitos antes de gerar o parser.
Os conflitos são introduzidos na escrita da gramática e podem sempre ser eliminados reescrevendo-a, mas por vezes é preferível eliminá-los usando precedências. Tomemos o seguinte exemplo clássico, o “dangling else”:
stmt : IF expression stmt
| IF expression stmt ELSE stmt
;Para o seguinte input:
if(a) if(b) c = a + b; else c = a;
O problema que nos surge é que o parser não sabe se o que ele tem é um IF expression stmt com expression igual a (a) e o stmt igual a if(b) c = a + b; else c = a; ou se em vez disso tem um IF expression stmt ELSE stmt com expression também igual a (a), o primeiro stmt igual a if(b) c = a + b; e o segundo stmt igual a c = a;. O que queremos que o parser faça? Associe o else ao primeiro if ou ao segundo? O comportamento que esperamos é que associe ao segundo, portanto para o conseguir vamos usar precedências.
%nonassoc IFX
%token ELSE
...
%%
...
stmt : IF expression stmt %prec IFX
| IF expression stmt ELSE stmt
;
...
%%Introduzimos o token IFX – o token ELSE já tem de estar definido, tal como o IF se o estamos a usar na gramática – que não é retornado pelo scanner. O IFX só existe dentro do parser e serve apenas para indicar o nível de precedência de uma produção. Indicamos ao BYACC o nível de precedência dos tokens pela ordem em que os declaramos, tendo os últimos maior precedência que os primeiros. A precedência de um token determina a precedência da produção em que ele se encontra, numa situação em que duas produções são viáveis como no exemplo anterior a produção com maior precedência é usada. Se quisermos modificar a precedência de uma produção sem afectar a precedência de nenhum dos seus tokens, podemos, como mencionado previamente, criar um token “falso” como o IFX e escrever %prec IFX no fim da produção para o conseguir. Usando o token IFX no primeiro IF estamos a dizer que aquele tipo de if tem menos precedência que o segundo IF, já que o token IFX é declarado antes do token ELSE, portanto quando existem as duas hipóteses o parser escolhe sempre a segunda, o que é o comportamento que desejávamos.
expr : expr '*' expr
| NUMBER
;Neste caso para o input NUMBER * NUMBER * NUMBER por exemplo, o parser não sabe se há-de fazer (NUMBER * NUMBER) * NUMBER ou NUMBER * (NUMBER * NUMBER). Para resolver este problema precisamos de indicar a associatividade do operador binário * ao BYACC. Um operador com associatividade à esquerda para o input NUMBER * NUMBER * NUMBER * NUMBER faz ((NUMBER * NUMBER) * NUMBER) * NUMBER, um operador com associatividade à direita faz NUMBER * (NUMBER * (NUMBER * NUMBER)) para o mesmo input. A forma de indicar a associatividade de um token ao BYACC é escrever %left ou %right em vez de %token quando o declaramos. Para declarar um operador unário não associativo (ou seja um operador que não se pode encadear) escrevemos %nonassoc em vez de %token.
Entendendo associatividade e precedências podemos começar a compreender a gramática da nossa calculadora.
%token NUMBER
%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS
%%
expr : NUMBER
| '-' expr %prec UMINUS
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| expr '^' expr
| '(' expr ')'
;
%%Dizemos que os operadores binários + e - são associativos à esquerda e têm a mesma precedência. Os operadores * e / funcionam de forma idêntica mas têm maior precedência. O operador de potência ^ é associativo à direita e tem a maior precedência de todos os operadores binários. O UMINUS indica que uma expressão negada tem a maior precedência e que não se pode negar uma negação. Os parênteses forçam a avaliação de qualquer que seja a expressão que estiver dentro deles, contornando as precedências caso seja necessário. Para o input, -1^2 + 5 + 3 - 2 * 3 ^ 4 ^ 5 / -6 / 2 - 5 a nossa gramática vai fazer (((((-1)^2) + 5) + 3) - (((2 * (3 ^ (4 ^ 5))) / (-6)) / 2)) - 5 como seria de esperar.
Podemos associar acções a cada produção, para serem executadas quando o parser acaba de processar o corpo de uma produção e o substitui pela cabeça. As acções indicam-se da mesma forma que no scanner, e é possível usar elementos da produção dentro delas desde que eles tenham valores associados. Para indicar o valor da cabeça usamos $$, para os membros do corpo usamos $1, $2, …, $n de acordo com a ordem em que eles aparecem. Um não terminal tem por default associado um int. Se quisermos associar um tipo diferente declaramos %type<tipo-do-valor-associado> nome-do-símbolo-não-terminal na primeira secção do ficheiro.
Vejamos então o ficheiro inteiro:
%{
#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();
}O ficheiro começa com os #includes de C++ que precisamos, seguidos da %union com o único tipo que a nossa calculadora necessita, um double. Lemos a declaração dos tokens, com os tipos associados, associatividade e precedência. Concluímos a primeira secção com a declaração que o símbolo não terminal expr tem um valor associado do tipo double. Isto é essencial porque as nossas operações não estão a receber tokens NUMBER como argumentos mas sim não terminais expr. O símbolo inicial da nossa gramática é expr_list e está definido como uma sequência de um ou mais não terminais expr, separados por mudanças de linha. Associamos a cada produção de expr_list a acção da impressão do valor de expr. As produções com cabeça expr tem associadas as acções que realizam os cálculos, guardando os valores na cabeça. Na terceira secção temos um main que chama o yyparse().
Neste momento temos um parser e um scanner para a nossa calculadora, no próximo artigo veremos como ligá-los e como modificar o scanner e o parser em conjunto de forma a adicionar mais funcionalidades à calculadora.