bison

Bison

Bison é um gerador de analise sintático que trabalha com gramaticas LALR e é também compatível com o YACC. Esse analisador sintático é gerado em C e trabalha com o Win32, Linux entre outros sistemas operacionais.
Quando se fala em ambiguidade e conflitos, o analisador verifica o proximo token para se decidir se a ação deve carregar ou reduzir o token por alguma regra. Se o Bison não pode decidir qual regra deve ser escolhida, então ocorre conflitos empilhar/reduzir ou reduzir/reduzir.
Se ocorrer um conflito empilhar/reduzi, o Bison irá compara a precedência do token a ser deslocado com a precedência da regra a ser reduzida. Já o conflito reduzir/reduzir se escolhe a regra que aparece primeiro na gramatica.

Segundo Mason, Levine e Brown (1995), o Flex e o Bison podem ajudar na escrita de programas que transformam uma entrada estruturada. Isso inclui uma gama grande de aplicações, desde um simples programa que procura por padrões em um arquivo texto de entrada até um compilador C que transforma um programa fonte em um código objeto otimizado.
O Bison utiliza uma descrição concisa de uma gramatica e produz uma rotina em C, chamada parser. O parser detecta automaticamente se uma sequência de tokens entrada combina com uma das regras da gramatica e também detecta erros de sintaxe caso a entrada não combine com nenhuma das regras.

A análise sintática foi implementada com o auxílio do gerador de analisadores sintáticos bison , que faz parte do conjunto de ferramentas GNU. O bison recebe como entrada um arquivo contendo a gramática da linguagem, juntamente com um conjunto de ações específicas, denominadas ações embutidas, a serem executadas em certos pontos da análise sintática.
O bison gera analisadores sintáticos ascendentes LALR. Uma peculiaridade dos analisadores ascendentes é existência de uma pilha de valores que é mantida conforme a análise sintática progride. Cada símbolo gramatical do lado direito das produções possui uma variável nessa pilha,