Notas de Aula - MAC 211 - Laborat�rio de Programa��o

Aula 22 - 28/5/2009

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 oou 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.