Notas de Aula - MAC 211 - Laboratório de Programação

Aula 22 - 25/5/2010 - YACC e GNU Bison

O UNIX original tinha como um de seus componentes, o YACC - Yet Another Compiler Compiler.
Ele gera um analisador sintático (que é parte do compilador) a partir de uma especificação formal de uma gramática.
O GNU Bison é a implementação da FSF desta ferramenta e é completamente compatível com o yacc, mas ele inclui coisas a mais.
Usando o bison, é possível desde criar simples programas interativos, como calculadores, até analisadores de linguagens de programação bem complexas.
Mais especificamente, o bison recebe como entrada uma gramática livre de contexto e gera um analisador sintático LALR(1) ou GLR.

A definição formal do que é uma gramática livre de contexto e o que são analisadores sintáticos LALR(1) ou GLR são tópicos da disciplina MAC 414 Linguagens Formais e Autômatos.

A forma mais conhecida para se representar uma gramática é aquela criada para a linguagem Algol-60 na década de 1960 e se chama Backus-Naur Form ou simplesmente “BNF”.
O bison recebe como entrada uma especificação BNF (adaptada para os caracteres comumente encontrados nos teclados modernos).
Ao definirmos uma gramática para uma linguagem, cada tipo de unidade sintática ou agrupamento é associado a um símbolo.
Símbolos que são definidos a partir do agrupamento de símbolos menores são chamados de não-terminais.
Símbolos que não podem ser subdivididos são chamados de símbolos terminais.

Símbolos não-terminais: expressão, sentença (statement), declaração e definição de função.
Símbolos terminais: identificador, número, string, if, while, do, for, continue, break, return, cont, static, int, char, float, double, +, -, *, /, %, &, &&, =, ==, {, }, [, ], ", ', etc...

O prólogo contém definições iniciais em C que são jogadas diretamente para o arquivo de saída do bison, antes da definição da função yyparse que é o analisador sintático em si.
Na parte das declarações do Bison são definidos símbolos terminais e não-terminais e relações de precedência. Em gramáticas simples, pode ser deixado vazio.
A seção de regras gramaticais é o coração do arquivo. É obrigatório ter pelo menos 1 regra gramatical.
O epílogo é copiado ipsis literis para o arquivo de saída.

Especifique a gramática em um arquivo .y e para cada regra gramatical, descreva a ação a ser tomada quando uma instância daquela regra é detectada.
Escreva um analisador léxico para fornecer os itens para o bison (pode ser manualmente ou via flex).
Escreva uma função (p.ex., main) para chamar a função yyparse gerada pelo bison.
Escreva, opcionalmente, funções de relatos de erros.

Os arquivos com gramáticas do bison (*.y) são processados pelo bison e geram *.tab.c
Os *.tab.c são compilados pelo gcc para gerar um executável, p.ex., a.out
O a.out processa um arquivo de entrada (escrito na linguagem dada), gera a árvore sintática do programa e executa os comandos definidos pelo programador, associados à gramática.

Para ser útil, um programa tem que fazer algo mais do que simplesmente analisar a sintaxe da entrada, ele tem que gerar alguma saída.
Para gerar a saída, ele precisa definir a semântica (o significado) daquilo que ele está processando.
No caso de um compilador, a saída é um programa numa outra linguagem (p.ex., linguagem de montagem).
No caso de uma calculadora, a saída é o resultado do cálculo.

Portanto, cada regra é seguida de uma ação que define o que deve ser feito quando a regra é detectada.
Por exemplo:

expr: expr '+' expr { $$ = $1 + $3; }
define que o valor semântico de expr quando esta regra é detectada é a soma das duas sub-expressões.