GNU Bison - GNU Bison
 | |
| Autor (es) original (is) | Robert Corbett |
|---|---|
| Desenvolvedor (s) | O Projeto GNU |
| lançamento inicial | Junho de 1985 |
| Versão estável | 3.8.1 / 11 de setembro de 2021
|
| Repositório | |
| Escrito em | C e m4 |
| Sistema operacional | Tipo Unix |
| Modelo | Gerador de analisador |
| Licença | GPL |
| Local na rede Internet |
www 
|
GNU Bison , comumente conhecido como Bison , é um gerador de analisador que faz parte do Projeto GNU . Bison lê uma especificação de uma linguagem livre de contexto , avisa sobre quaisquer ambiguidades de análise e gera um analisador que lê sequências de tokens e decide se a sequência está em conformidade com a sintaxe especificada pela gramática. Os analisadores gerados são portáteis: eles não requerem nenhum compilador específico. Bison por padrão gera analisadores LALR (1), mas também pode gerar analisadores LR , IELR (1) e GLR canônicos .
No modo POSIX , Bison é compatível com Yacc , mas também tem várias extensões sobre este programa anterior, incluindo
- Geração de contra-exemplos para conflitos
- Rastreamento de localização (por exemplo, arquivo, linha, coluna)
- Mensagens de erro de sintaxe rica e internacionalizável nos analisadores gerados
- Geração de erro de sintaxe personalizável,
- Analisadores reentrantes
- Analisadores push, com preenchimento automático
- Suporte para referências nomeadas
- Vários tipos de relatórios (gráficos, XML) no analisador gerado
- Suporte para várias linguagens de programação ( C , C ++ , D ou Java )
Flex , um analisador léxico automático , é frequentemente usado com o Bison, para tokenizar dados de entrada e fornecer tokens ao Bison.
Bison foi originalmente escrito por Robert Corbett em 1985. Mais tarde, em 1989, Robert Corbett lançou outro gerador de parser chamado Berkeley Yacc . Bison tornou-se compatível com o Yacc por Richard Stallman .
Bison é um software livre e está disponível sob a GNU General Public License , com uma exceção (discutida abaixo) permitindo que seu código gerado seja usado sem acionar os requisitos de copyleft da licença.
Recursos
Geração de contra-exemplo
Um problema delicado com geradores de analisador LR é a resolução de conflitos (mudar / reduzir e reduzir / reduzir conflitos). A resolução de conflitos geralmente requer a análise do autômato do analisador conforme descrito nos relatórios e algum conhecimento do usuário. Os contra-exemplos ajudam a compreender rapidamente alguns conflitos e podem até mesmo provar que o problema é que a gramática é realmente ambígua.
Por exemplo, em uma gramática que sofre do infame problema de dangling else , Bison relata
doc / if-then-else.y: aviso : deslocar / reduzir o conflito no token "else" [- Wcounterexamples ] Exemplo: "if" expr "then" "if" expr "then" stmt • "else" stmt Derivação de deslocamento if_stmt ↳ "if" expr "then" stmt ↳ if_stmt ↳ "if" expr "then" stmt • "else" stmt Exemplo: "if" expr "then" "if" expr "then" stmt • "else" stmt Reduzir derivação if_stmt ↳ "if" expr "then" stmt "else" stmt ↳ if_stmt ↳ "if" expr "then" stmt •
Reentrada
Reentrância é um recurso que foi adicionado ao Bison e não existe no Yacc.
Normalmente, o Bison gera um analisador que não é reentrante . Para conseguir a reentrada, a declaração %define api.puredeve ser usada. Mais detalhes sobre a reentrada do Bison podem ser encontrados no manual do Bison.
Idiomas de saída
O Bison pode gerar código para C , C ++ , D e Java .
Para usar o analisador gerado pelo Bison de outras linguagens, uma ferramenta de vinculação de linguagem , como SWIG, pode ser usada.
Licença e distribuição do código gerado
Como o Bison gera código-fonte que, por sua vez, é adicionado ao código-fonte de outros projetos de software, ele levanta algumas questões de direitos autorais simples, mas interessantes.
Uma licença compatível com GPL não é necessária
O código gerado pelo Bison inclui quantidades significativas de código do próprio projeto Bison. O pacote Bison é distribuído sob os termos da GNU General Public License (GPL), mas uma exceção foi adicionada para que a GPL não se aplique à saída.
Versões anteriores do Bison estipulavam que partes de sua saída também eram licenciadas sob a GPL, devido à inclusão da função yyparse () do código-fonte original na saída.
Distribuição de pacotes usando Bison
Os projetos de software livre que usam o Bison podem ter a escolha de distribuir o código-fonte que seu projeto alimenta no Bison ou o código C resultante produzido pelo Bison. Ambos são suficientes para que um destinatário possa compilar o código-fonte do projeto. No entanto, distribuir apenas a entrada traz o pequeno inconveniente de que os destinatários devem ter uma cópia compatível do Bison instalada para que possam gerar o código C necessário ao compilar o projeto. E distribuir apenas o código C na saída cria o problema de tornar muito difícil para os destinatários modificar o analisador, uma vez que esse código não foi escrito por um ser humano nem para humanos - seu propósito é ser alimentado diretamente em um compilador C.
Esses problemas podem ser evitados com a distribuição dos arquivos de entrada e do código gerado. A maioria das pessoas compilará usando o código gerado, não diferente de qualquer outro pacote de software, mas qualquer pessoa que quiser modificar o componente do analisador pode modificar os arquivos de entrada primeiro e regenerar os arquivos gerados antes de compilar. Projetos que distribuem ambos geralmente não possuem os arquivos gerados em seus sistemas de controle de revisão . Os arquivos são gerados apenas ao fazer um lançamento.
Algumas licenças, como a GPL , exigem que o código-fonte esteja na " forma preferida de trabalho para fazer modificações ". Os projetos GPL usando o Bison devem, portanto, distribuir os arquivos que são a entrada para o Bison. Claro, eles também podem incluir os arquivos gerados.
Usar
Como o Bison foi escrito como um substituto para o Yacc e é amplamente compatível, o código de muitos projetos que usam o Bison também pode ser alimentado no Yacc. Isso torna difícil determinar se um projeto "usa" código-fonte específico do Bison ou não. Em muitos casos, o "uso" de Bison poderia ser substituído trivialmente pelo uso equivalente de Yacc ou um de seus outros derivados.
Bison tem recursos não encontrados no Yacc, portanto, pode-se dizer que alguns projetos "usam" Bison, já que Yacc não seria suficiente.
A lista a seguir é de projetos que são conhecidos por "usar" o Bison no sentido mais amplo, que usam ferramentas de desenvolvimento de software livre e distribuem código que se destina a ser alimentado no Bison ou em um pacote compatível com o Bison.
- O shell Bash usa uma gramática yacc para analisar a entrada do comando.
- O próprio analisador gramatical do Bison é gerado pelo Bison.
- CMake usa várias gramáticas Bison.
- O GCC começou usando Bison, mas mudou para um analisador descendente recursivo escrito à mão para C ++ em 2004 (versão 3.4) e para C e Objective-C em 2006 (versão 4.1)
- A linguagem de programação Go (GC) usava Bison, mas mudou para um scanner e analisador escrito à mão na versão 1.5.
- LilyPond requer Bison para gerar seu analisador.
- MySQL
- GNU Octave usa um analisador gerado pelo Bison.
- O Perl 5 usa um analisador gerado pelo Bison a partir de 5.10.
- A linguagem de programação PHP (Zend Parser).
- PostgreSQL
- Ruby MRI , a implementação de referência da linguagem de programação Ruby , depende da gramática Bison.
- syslog-ng usa várias gramáticas Bison reunidas.
Um exemplo completo de analisador reentrante
O exemplo a seguir mostra como usar Bison e flex para escrever um programa de calculadora simples (apenas adição e multiplicação) e um programa para criar uma árvore de sintaxe abstrata . Os próximos dois arquivos fornecem definição e implementação das funções da árvore de sintaxe.
/*
* Expression.h
* Definition of the structure used to build the syntax tree.
*/
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__
/**
* @brief The operation type
*/
typedef enum tagEOperationType
{
eVALUE,
eMULTIPLY,
eADD
} EOperationType;
/**
* @brief The expression structure
*/
typedef struct tagSExpression
{
EOperationType type; /* /< type of operation */
int value; /* /< valid only when type is eVALUE */
struct tagSExpression *left; /* /< left side of the tree */
struct tagSExpression *right; /* /< right side of the tree */
} SExpression;
/**
* @brief It creates an identifier
* @param value The number value
* @return The expression or NULL in case of no memory
*/
SExpression *createNumber(int value);
/**
* @brief It creates an operation
* @param type The operation type
* @param left The left operand
* @param right The right operand
* @return The expression or NULL in case of no memory
*/
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right);
/**
* @brief Deletes a expression
* @param b The expression
*/
void deleteExpression(SExpression *b);
#endif /* __EXPRESSION_H__ */
/*
* Expression.c
* Implementation of functions used to build the syntax tree.
*/
#include "Expression.h"
#include <stdlib.h>
/**
* @brief Allocates space for expression
* @return The expression or NULL if not enough memory
*/
static SExpression *allocateExpression()
{
SExpression *b = (SExpression *)malloc(sizeof(SExpression));
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = 0;
b->left = NULL;
b->right = NULL;
return b;
}
SExpression *createNumber(int value)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = eVALUE;
b->value = value;
return b;
}
SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right)
{
SExpression *b = allocateExpression();
if (b == NULL)
return NULL;
b->type = type;
b->left = left;
b->right = right;
return b;
}
void deleteExpression(SExpression *b)
{
if (b == NULL)
return;
deleteExpression(b->left);
deleteExpression(b->right);
free(b);
}
Os tokens necessários para o analisador Bison serão gerados usando flex.
%{
/*
* Lexer.l file
* To generate the lexical analyzer run: "flex Lexer.l"
*/
#include "Expression.h"
#include "Parser.h"
#include <stdio.h>
%}
%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
%%
[ \r\n\t]* { continue; /* Skip blanks. */ }
[0-9]+ { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }
"*" { return TOKEN_STAR; }
"+" { return TOKEN_PLUS; }
"(" { return TOKEN_LPAREN; }
")" { return TOKEN_RPAREN; }
. { continue; /* Ignore unexpected characters. */}
%%
int yyerror(const char *msg) {
fprintf(stderr, "Error: %s\n", msg);
return 0;
}
Os nomes dos tokens são normalmente neutros: "TOKEN_PLUS" e "TOKEN_STAR", não "TOKEN_ADD" e "TOKEN_MULTIPLY". Por exemplo, se fôssemos apoiar o unário "+" (como em "+1"), seria errado nomear este "+" "TOKEN_ADD". Em uma linguagem como C, "int * ptr" denota a definição de um ponteiro, não de um produto: seria errado nomear isso "*" "TOKEN_MULTIPLY".
Como os tokens são fornecidos pelo flex, devemos fornecer os meios de comunicação entre o analisador e o lexer . O tipo de dados usado para comunicação, YYSTYPE , é definido usando a declaração Bison % Union .
Como neste exemplo usamos a versão reentrante de flex e yacc, somos forçados a fornecer parâmetros para a função yylex , quando chamada de yyparse . Isso é feito por meio das declarações Bison % lex-param e % parse-param .
%{
/*
* Parser.y file
* To generate the parser run: "bison Parser.y"
*/
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
int yyerror(SExpression **expression, yyscan_t scanner, const char *msg) {
/* Add error handling routine as needed */
}
%}
%code requires {
typedef void* yyscan_t;
}
%output "Parser.c"
%defines "Parser.h"
%define api.pure
%lex-param { yyscan_t scanner }
%parse-param { SExpression **expression }
%parse-param { yyscan_t scanner }
%union {
int value;
SExpression *expression;
}
%token TOKEN_LPAREN "("
%token TOKEN_RPAREN ")"
%token TOKEN_PLUS "+"
%token TOKEN_STAR "*"
%token <value> TOKEN_NUMBER "number"
%type <expression> expr
/* Precedence (increasing) and associativity:
a+b+c is (a+b)+c: left associativity
a+b*c is a+(b*c): the precedence of "*" is higher than that of "+". */
%left "+"
%left "*"
%%
input
: expr { *expression = $1; }
;
expr
: expr[L] "+" expr[R] { $$ = createOperation( eADD, $L, $R ); }
| expr[L] "*" expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
| "(" expr[E] ")" { $$ = $E; }
| "number" { $$ = createNumber($1); }
;
%%
O código necessário para obter a árvore de sintaxe usando o analisador gerado pelo Bison e o scanner gerado pelo flex é o seguinte.
/*
* main.c file
*/
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
#include <stdio.h>
int yyparse(SExpression **expression, yyscan_t scanner);
SExpression *getAST(const char *expr)
{
SExpression *expression;
yyscan_t scanner;
YY_BUFFER_STATE state;
if (yylex_init(&scanner)) {
/* could not initialize */
return NULL;
}
state = yy_scan_string(expr, scanner);
if (yyparse(&expression, scanner)) {
/* error parsing */
return NULL;
}
yy_delete_buffer(state, scanner);
yylex_destroy(scanner);
return expression;
}
int evaluate(SExpression *e)
{
switch (e->type) {
case eVALUE:
return e->value;
case eMULTIPLY:
return evaluate(e->left) * evaluate(e->right);
case eADD:
return evaluate(e->left) + evaluate(e->right);
default:
/* should not be here */
return 0;
}
}
int main(void)
{
char test[] = " 4 + 2*10 + 3*( 5 + 1 )";
SExpression *e = getAST(test);
int result = evaluate(e);
printf("Result of '%s' is %d\n", test, result);
deleteExpression(e);
return 0;
}
Um makefile simples para construir o projeto é o seguinte.
# Makefile
FILES = Lexer.c Parser.c Expression.c main.c
CC = g++
CFLAGS = -g -ansi
test: $(FILES)
$(CC) $(CFLAGS) $(FILES) -o test
Lexer.c: Lexer.l
flex Lexer.l
Parser.c: Parser.y Lexer.c
bison Parser.y
clean:
rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h test
Veja também
- Berkeley Yacc (byacc) - outro substituto de software livre Yacc compartilhando o mesmo autor que GNU Bison
- ANTLR outra ferramenta para reconhecimento de linguagem, outro gerador de analisador de código aberto
Referências
Leitura adicional
- Levine, John (agosto de 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1.