Jump to content

ГНУ Бизон

ГНУ Бизон
Оригинальный автор(ы) Роберт Корбетт
Разработчик(и) Проект GNU
Первоначальный выпуск июнь 1985 г .; 39 лет назад ( 1985-06 ) [1]
Стабильная версия
3.8.2 [2]  Отредактируйте это в Викиданных / 25 сентября 2021 г.
Репозиторий
Написано в С и м4
Операционная система Unix-подобный
Тип Генератор парсера
Лицензия лицензия GPL
Веб-сайт www .gnu .org /программное обеспечение /бизон /  Edit this on Wikidata

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

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

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

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

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

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

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. [7]

Языки вывода

[ редактировать ]

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

В более ранних версиях 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.

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

[ редактировать ]

В следующем примере показано, как использовать 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, мы должны предоставить средства для связи между синтаксическим анализатором и лексером . [23] Тип данных, используемый для связи, YYSTYPE , устанавливается с помощью объявления Bison %union .

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

%{

/*
 * 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, еще один генератор парсеров с открытым исходным кодом.
  1. ^ Jump up to: а б Корбетт, Роберт Пол (июнь 1985 г.). Статическая семантика и восстановление ошибок компилятора (доктор философии). Калифорнийский университет в Беркли . ДТИК ADA611756 .
  2. ^ Аким Демайль (25 сентября 2021 г.). «Бизон 3.8.2» .
  3. ^ «Язык и грамматика (Бизон 3.8.1)» . www.gnu.org . Проверено 26 декабря 2021 г.
  4. ^ Руководство по бизонам: Введение.
  5. ^ Левин, Джон (август 2009 г.). флекс и бизон . О'Рейли Медиа. ISBN  978-0-596-15597-1 .
  6. ^ «АВТОРЫ» . bison.git. ГНУ Саванна . Проверено 26 августа 2017 г.
  7. ^ Руководство Bison: Чистый (реентерабельный) парсер
  8. ^ Руководство Bison: Краткое изложение декларации Bison
  9. ^ Руководство Bison: Условия использования Bison
  10. ^ Файл исходного кода parse-gram.c, который содержит исключение
  11. ^ "parse-gram.y" . bison.git. ГНУ Саванна . Проверено 29 июля 2020 г.
  12. ^ «ЛексерПарсер в CMake» . github.com .
  13. ^ Изменения, новые функции и исправления серии выпусков GCC 3.4.
  14. ^ Изменения, новые функции и исправления серии выпусков GCC 4.1.
  15. ^ Определение грамматики Голанга
  16. ^ «Parser.yy — репозиторий GNU LilyPond Git» . git.savannah.gnu.org .
  17. ^ «4. Парсинг SQL — flex & bison [Книга]» .
  18. ^ «GNU Octave: исходный файл Libinterp/Parse-tree/Oct-parse.cc» .
  19. ^ «Что нового в Perl 5.10.0?» . perl.org.
  20. ^ «Этап парсера» . postgresql.org. 30 сентября 2021 г.
  21. ^ «Рубиновый МРТ-парсер» . github.com .
  22. ^ «Парсер XML syslog-ng» . github.com . 14 октября 2021 г.
  23. ^ Jump up to: а б Руководство Flex: Сканеры C с парсерами Bison. Архивировано 17 декабря 2010 г. на Wayback Machine.
  24. ^ Руководство Bison: Соглашения о вызовах для чистых парсеров

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f4e8bdf571af7832d49d425a506b9643__1717003620
URL1:https://arc.ask3.ru/arc/aa/f4/43/f4e8bdf571af7832d49d425a506b9643.html
Заголовок, (Title) документа по адресу, URL1:
GNU Bison - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)