GNU Bison - GNU Bison

GNU Bison
Heckert GNU white.svg
Автор (ы) оригинала Роберт Корбетт
Разработчики) Проект GNU
Первый выпуск Июнь 1985 г . ; 36 лет назад ( 1985-06 )
Стабильный выпуск
3.8.1 / 11 сентября 2021 г . ; 36 дней назад ( 2021-09-11 )
Репозиторий
Написано в C и m4
Операционная система Unix-подобный
Тип Генератор парсеров
Лицензия GPL
Веб-сайт www .gnu .org / software / bison / Отредактируйте это в Викиданных

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

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

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

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

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

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

Функции

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

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

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

doc / if-then-else.y: предупреждение : конфликт сдвига / уменьшения на токене "else" [- Wcounterexamples ]
  Пример: "if" expr "then"  "if" expr "then" stmt  •  "else" stmt
  Вывод сдвига
    if_stmt 
    ↳ "if" expr "then"  stmt 
                        ↳  if_stmt 
                           ↳ "if" expr "then" stmt  •  "else" stmt 
  Пример: "if" expr "then"  "if" expr "then" stmt  •  "else" stmt
  Уменьшить вывод
    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, но перешел на рукописный синтаксический анализатор с рекурсивным спуском для C ++ в 2004 году (версия 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(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"

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

%%

Код, необходимый для получения синтаксического дерева с использованием синтаксического анализатора, созданного 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 Другой инструмент для распознавания языков, еще один генератор парсеров с открытым исходным кодом.

использованная литература

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

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