Aula 13: Ferramentas: Bison/Yacc

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

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

Motivação prática

Assim como o Flex automatiza a implementação de scanners, o Bison/Yacc automatiza a implementação de parsers LR.

Para Engenharia de Computação, essa dupla é importante porque:

  • Permite construir rapidamente compiladores, montadores, analisadores de logs e DSLs confiáveis.
  • Garante parsers eficientes e bem comportados, baseados em algoritmos clássicos de parsing LR/LALR.
  • Facilita a experimentação com diferentes gramáticas para a mesma linguagem, sem reescrever código de parsing manual.

Conteúdo

O Bison (e o Yacc) é um gerador de parsers LALR(1). Ele lê uma especificação gramatical (arquivo .y) e gera código C/C++ com a tabela de parsing e o loop shift-reduce.

flowchart LR
  Arquivo[Arquivo .y] --> Bison[Bison]
  Bison --> Tab[.tab.c]
  Tab --> Comp[Compilação]
  Flex[Flex lex.yy.c] --> Comp
  Comp --> Parser[Parser completo]

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 gera um header com os códigos dos tokens (enum). O Flex inclui esse header e retorna esses valores em yylex(). O valor semântico (número, string do ID, etc.) é passado pela variável global yylval. O parser chama yylex() sempre que precisa do próximo token.

Conexões com o projeto Mini-Pascal

  • Embora o projeto utilize ANTLR4 em vez de Bison/Yacc, os conceitos são análogos:
    • Uma gramática de alto nível é traduzida em código de parser eficiente.
    • As ações semânticas associadas às regras constroem a AST e/ou já executam verificações.
  • Entender Bison/Yacc ajuda a interpretar ferramentas e documentação clássicas de compiladores, além de conectar com ambientes de desenvolvimento de sistemas em C/C++.

Resumo

  • Bison lê .y (declarações, gramática com ações em C) e gera o parser LALR(1). Precedência e associatividade (%left, %right) resolvem conflitos sem reescrever a gramática.
  • Flex + Bison: tokens e yylval definidos pelo Bison; o scanner (Flex) retorna os códigos e preenche yylval; o parser chama yylex().

Materiais da aula

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 4.
  • Cooper & Torczon (2011). Engineering a Compiler.

Última atualização: 08/03/2026

De volta ao topo