ГНУ Бизон

ГНУ Бизон

Оригинальный автор(ы)	Роберт Корбетт
Разработчик(и)	Проект GNU
Первоначальный выпуск	июнь 1985 г ( 1985-06 )
Стабильная версия	3.8.2   / 25 сентября 2021 г.
Репозиторий	мерзавец .саванна .gnu .org /cgit /бизон .git
Написано в	С и м4
Операционная система	Unix-подобный
Тип	Генератор парсера
Лицензия	лицензия GPL
Веб-сайт	www .gnu .org /программное обеспечение /бизон /

GNU Bison , широко известный как Bison , представляет собой генератор синтаксического анализатора , являющийся частью проекта GNU . Bison читает спецификацию синтаксиса Bison (описываемого как «машиночитаемый BNF »). ), предупреждает о любых неоднозначностях синтаксического анализа и генерирует синтаксический анализатор, который считывает последовательности токенов и решает, соответствует ли последовательность синтаксису, указанному в грамматике.

Сгенерированные парсеры портативны: они не требуют каких-либо специальных компиляторов. Bison по умолчанию генерирует парсеры LALR(1), но он также может генерировать LR , IELR(1) и GLR . канонические парсеры

В режиме POSIX Bison совместим с Yacc , но также имеет несколько расширений по сравнению с этой более ранней программой, включая

• Генерация контрпримеров для конфликтов
• Отслеживание местоположения (например, файл, строка, столбец)
• Богатые и интернационализируемые сообщения о синтаксических ошибках в сгенерированных анализаторах.
• Настраиваемая генерация синтаксических ошибок,
• Реентерабельные парсеры
• Push-парсеры с автозаполнением
• Поддержка именованных ссылок
• Несколько типов отчетов (графические, XML) на формируемом парсере
• Поддержка нескольких языков программирования ( C , C++ , D или Java )

Flex , автоматический лексический анализатор , часто используется с Bison для токенизации входных данных и предоставления Bison токенов.

«Бизон» был первоначально написан Робертом Корбеттом в 1985 году. Позже, в 1989 году, Роберт Корбетт выпустил ещё один генератор парсеров под названием Berkeley Yacc . Bison был сделан Yacc-совместимым Ричардом Столлманом .

Bison является свободным программным обеспечением и доступен под лицензией GNU General Public License , за исключением (обсуждаемым ниже), позволяющим использовать сгенерированный код без применения требований авторского лева лицензии.

Функции

Генерация контрпримера

Одной из деликатных проблем с генераторами анализаторов LR является разрешение конфликтов (конфликты сдвига/сокращения и сокращения/сокращения). Во многих генераторах синтаксических анализаторов LR разрешение конфликтов требует анализа автомата синтаксического анализатора, что требует от пользователя определенных знаний.

Чтобы помочь пользователю более интуитивно понимать конфликты, Bison вместо этого может автоматически генерировать противоположные примеры. Для неоднозначных грамматик Bison часто даже может привести контрпримеры, показывающие, что грамматика неоднозначна.

Например, о грамматике, страдающей от пресловутой проблемы с висячим else , сообщает Bison.

doc/if-then-else.y: warning: shift/reduce conflict on token "else" [-Wcounterexamples]
  Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
  Shift derivation
    if_stmt
    ↳ "if" expr "then" stmt
                        ↳ if_stmt
                           ↳ "if" expr "then" stmt • "else" stmt
  Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
  Reduce derivation
    if_stmt
    ↳ "if" expr "then" stmt                        "else" stmt
                        ↳ if_stmt
                           ↳ "if" expr "then" stmt •

Реентерабельность

Повторный вход — это функция, которая была добавлена ​​в Bison и не существует в Yacc.

парсер Обычно Bison генерирует нереентерабельный . Чтобы добиться реентерабельности, декларация %define api.pure необходимо использовать. Более подробную информацию о реентерабельности Bison можно найти в руководстве Bison.

Языки вывода

Bison может генерировать код для C , C++ , D и Java .

Для использования синтаксического анализатора, созданного Bison, с других языков инструмент привязки языка, такой как SWIG можно использовать .

Лицензия и распространение сгенерированного кода

Поскольку Bison генерирует исходный код, который, в свою очередь, добавляется к исходному коду других программных проектов, возникает несколько простых, но интересных вопросов об авторских правах.

Лицензия, совместимая с GPL, не требуется.

Код, сгенерированный Bison, включает значительные объемы кода из самого проекта Bison. Пакет Bison распространяется на условиях GNU General Public License (GPL), но было добавлено исключение, согласно которому GPL не применяется к выходным данным.

В более ранних версиях Bison оговаривалось, что часть его результатов также лицензируется по лицензии GPL из-за включения в выходные данные функции yyparse() из исходного исходного кода.

Распространение пакетов с помощью Bison

Проекты бесплатного программного обеспечения, использующие Bison, могут иметь выбор: распространять ли исходный код, который их проект передает в Bison, или полученный код C, выводимый Bison. И того, и другого достаточно, чтобы получатель смог скомпилировать исходный код проекта. Однако распространение только входных данных несет в себе небольшое неудобство: у получателей должна быть установлена ​​совместимая копия Bison, чтобы они могли генерировать необходимый код C при компиляции проекта. А распространение на выходе только кода C создает проблему, заключающуюся в том, что получателям очень сложно модифицировать синтаксический анализатор, поскольку этот код не был написан ни человеком , ни для людей - его цель - передать непосредственно в компилятор C.

Этих проблем можно избежать, распространяя как входные файлы, так и сгенерированный код. Большинство людей будут компилировать с использованием сгенерированного кода, ничем не отличающегося от любого другого программного пакета, но любой, кто хочет изменить компонент синтаксического анализатора, может сначала изменить входные файлы и повторно сгенерировать сгенерированные файлы перед компиляцией. Проекты, распространяющие оба варианта, обычно не имеют сгенерированных файлов в своих системах контроля версий . Файлы генерируются только при выпуске релиза.

Некоторые лицензии, такие как GPL , требуют, чтобы исходный код находился в « предпочтительной форме произведения для внесения в него изменений ». Таким образом, проекты под лицензией GPL, использующие Bison, должны распространять файлы, которые являются входными данными для Bison. Конечно, они также могут включать сгенерированные файлы.

Использовать

Поскольку Bison был написан как замена Yacc и в значительной степени совместим, код из многих проектов, использующих Bison, также можно было бы передать в Yacc. Из-за этого сложно определить, «использует» ли проект исходный код, специфичный для Bison, или нет. Во многих случаях «использование» Bison можно тривиально заменить эквивалентным использованием Yacc или одной из его других производных.

Bison имеет функции, отсутствующие в Yacc, поэтому можно сказать, что некоторые проекты действительно «используют» Bison, поскольку Yacc будет недостаточно.

В следующем списке представлены проекты, которые, как известно, «используют» Bison в более широком смысле: они используют бесплатные инструменты разработки программного обеспечения и распространяют код, предназначенный для загрузки в Bison или пакет, совместимый с Bison.

• Оболочка Bash использует грамматику yacc для анализа ввода команды.
• Собственный анализатор грамматики Bison создается Bison.
• CMake использует несколько грамматик Bison.
• GCC начал использовать Bison, но в 2004 году перешёл на рукописный парсер рекурсивного спуска для C++ (версия 3.4). и для C и Objective-C в 2006 г. (версия 4.1)
• В языке программирования Go (GC) использовался Bison, но в версии 1.5 он перешёл на рукописный сканер и парсер.
• LilyPond требует, чтобы Bison сгенерировал свой парсер.
• MySQL
• GNU Octave использует парсер, сгенерированный Bison.
• Perl 5 использует синтаксический анализатор, сгенерированный Bison, начиная с версии 5.10.
• Язык программирования PHP (Zend Parser).
• PostgreSQL
• Ruby MRI , эталонная реализация языка программирования Ruby , опирается на грамматику Bison.
• syslog-ng использует несколько грамматик Bison, собранных вместе.

Полный пример реентерабельного парсера

В следующем примере показано, как использовать Bison и flex для написания простой программы-калькулятора (только сложение и умножение) и программы для создания абстрактного синтаксического дерева . Следующие два файла содержат определение и реализацию функций синтаксического дерева.

/*
 * 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);
}

Токены, необходимые парсеру Bison, будут сгенерированы с использованием 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(SExpression **expression, yyscan_t scanner, const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    return 0;
}

Имена токенов обычно нейтральны: «TOKEN_PLUS» и «TOKEN_STAR», а не «TOKEN_ADD» и «TOKEN_MULTIPLY». Например, если бы мы поддерживали унарный «+» (как в «+1»), было бы неправильно называть этот «+» «TOKEN_ADD». В таком языке, как C, «int *ptr» обозначает определение указателя, а не произведения: было бы неправильно называть этот «*» «TOKEN_MULTIPLY».

Поскольку токены предоставляются flex, мы должны предоставить средства для связи между синтаксическим анализатором и лексером . Тип данных, используемый для связи, YYSTYPE , устанавливается с помощью объявления Bison %union .

Поскольку в этом примере мы используем реентерабельную версию как flex, так и yacc, мы вынуждены предоставлять параметры для функции yylex при вызове из yyparse . Это делается с помощью объявлений Bison %lex-param и %parse-param .

%{

/*
 * Parser.y file
 * To generate the parser run: "bison Parser.y"
 */

#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"

// reference the implementation provided in Lexer.l
int yyerror(SExpression **expression, yyscan_t scanner, const char *msg);

%}

%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); }
    ;

%%

Код, необходимый для получения синтаксического дерева с использованием синтаксического анализатора, созданного Bison, и сканера, созданного flex, следующий.

/*
 * 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;
}

Ниже приведен простой make-файл для сборки проекта.

# 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

См. также

• Berkeley Yacc (byacc) — еще одна бесплатная замена Yacc, имеющая того же автора, что и GNU Bison.
• ANTLR ANother Tool for Language Recognition, еще один генератор парсеров с открытым исходным кодом.

Дальнейшее чтение

• Левин, Джон (август 2009 г.). флекс и бизон . О'Рейли Медиа. ISBN  978-0-596-15597-1 .

Внешние ссылки

• Веб-сайт в проекте GNU
  • Руководство
• Проект Bison в GNU Savannah
• Запись в каталоге свободного программного обеспечения
• Внутреннее устройство парсеров C, созданных GNU Bison
• Как загрузить и установить Bison (GNU Parser Generator) в Linux
• Двоичные файлы Win32 от GnuWin32 (версия 2.4.1)