Aula 13: Ferramentas: Bison/Yacc

Objetivos

  • Dominar o uso do Bison/Yacc.
  • Integrar Lexer (Flex) e Parser (Bison).

Conteúdo

O Bison é um gerador de parsers LALR(1). Ele lê uma especificação gramatical e gera um arquivo C/C++ (.tab.c) contendo a máquina de estados completa.

Estrutura do Arquivo .y

/* DECLARAÇÕES */
%token NUM ID
%left '+' '-'  /* Define precedência e associatividade */
%left '*' '/'

%%
/* GRAMÁTICA */
expr : expr '+' expr  { $$ = $1 + $3; } /* Ações Semânticas em C */
     | expr '*' expr  { $$ = $1 * $3; }
     | NUM            { $$ = $1; }
     ;
%%

Resolução de Conflitos

O Bison é excelente porque permite gramáticas ambíguas, desde que você declare as regras de precedência. - %left '+': Soma associa à esquerda (a+b+c é (a+b)+c). - Como * é declarado depois de +, ele tem maior precedência. Isso reduz drasticamente o tamanho da gramática (não precisa de camadas E, T, F).

Comunicação com Flex

O Bison define os tokens num anenum (header file). O Flex inclui esse header e retorna esses valores. O valor semântico (o número em si, ou a string do ID) é passado via variável global yylval.

Referências

  • Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
  • Cooper, K., & Torczon, L. (2011). Engineering a Compiler.
Back to top