گنو بایسون

بایسون گنو (به انگلیسی: GNU bison) بخشی از پروژه گنو است که مسئولیت تجزیه زبان‌های مستقل از متن را بر عهده دارد. بایسون مشخصه‌های یک زبان مستقل از متن را خوانده، هر جا که با ابهام در تجزیه روبرو شود، هشداری را صادر کرده، سپس یک تجزیه‌گر واژگانی را تولید می‌کند (برای زبان‌های سی، سی++ یا جاوا) که این تجزیه‌گر، خود می‌تواند دنباله‌ای از توکن‌ها را بخواند و تصمیم بگیرد که آیا این دنباله، با ساختار دستوری که توسط گرامر اولیه مشخص شده، همخوانی دارد یا نه. بایسون به صورت پیشفرض تجزیه‌گرهای نوع LALR تولید می‌کند، اما قادر به تولید کردن تجزیه‌گرهای GLR هم است.

گنو بایسون

توسعه‌دهنده(ها)	رابرت کوروت، پروژه گنو
مخزن	git.savannah.gnu.org/cgit/bison.git
سیستم‌عامل	چندسکویی
نوع	ایجاد تجزیه کننده
مجوز	GPL (نرم‌افزار آزاد
وبگاه	www.gnu.org/software/bison

در حالت POSIX بایسون با Yacc سازگار است ولی می تواند با برنامه های قدیمی تر نیز کار کند. از جمله :

• ردیابی مکانی (مانند فایل، خط و ستون)
• پیام های خطای دارای توضیحات در پارسر های تولید شده
• پارسر های بازورود (reentrant)
• پارسر های pull
• پشتیبانی از مراجع نامگذاری شده
• چندین نوع گزارش (گرافیکی ، XML ) بر پارسر تولیدی
• پشتیبانی از چندین زبان برنامه نویسی
• و غیره

FLEX که یک آنالیز کننده ی کلمه ای خودکار است، معمولا به همراه بایسون استفاده می شود. تا داده های ورودی را توکن بندی کند و توکن ها را در اختیار بایسون قرار دهد.

بایسون ابتدا در سال 1985 توسط رابرت کوربت نوشته شد. بعدها در سال 1989 او یک تولید کننده ی پارسر دیگر به نام Berkeley Yacc ایجاد کرد. بایسون و Yacc توسط ریچارد استالمن با یکدیگر سازگار شدند.

بایسون یک نرم افزار رایگان است و تحت GNU General Public License قرار دارد. با یک استثنا ( که در زیر مورد بحث قرار گرفته است) که به کد تولیدی اجازه می دهد بدون عبور از حقوق کپی رایت مورد استفاده قرار بگیرد.

یک نمونه ی پارسر بازورود کامل

---

مثال زیر چگونگی استفاده از بایسون و فلکس در راستای ایجاد یک برنامه ی ماشین حساب ساده را نشان می دهد (فقط جمع و ضرب) و یک برنامه نیز برای ایجاد یک Abstract syntax tree نشان می دهد. دو فایل بعدی تعریف و پیاده سازی کارکرد های درخت را نشان می دهد :

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

توکن های مورد نیاز پارسر بایسون توسط 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" بگذاریم.

از آنجایی که توکن ها توسط فلکس در اختیار قرار می گیرند باید راهی برای ایجاد ارتباط بین Parser و Lexer ایجاد کنیم. نوع داده ی استفاده شده برای ارتباط، YYSTYPE است.

از آنجا که در این مثال از مدل بازورود فلکس و yacc استفاده می شود باید پارامتر هایی برای تابع yylex در زمانی که از yyparse فراخوانی می شود تعریف کنیم. این کار با تعریف های 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); }
    ;

%%

کد مورد نیاز برای بدست آوردن درخت سینتکس که از پارسر تولید شده توسط بایسون و اسکنر تولید شده توسط فلکس بدست می آید بصورت زیر است :

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

یک makefile ساده برای تولید پروژه ی بالا بصورت زیر است :

# 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

بازورود

---

بازورود یک ویژگی جدید است که در بایسون وجود دارد ولی در Yacc وجود ندارد.

به‌طور معمول، بایسون پارسری تولید می کند که بازورود نیست. برای حصول این ویژگی باید از تعریف define api.pure% استفاده کرد. ویژگی های بیشتر درمورد بازورود بایسون را می توان در راهنمای بایسون یافت.

استفاده از بایسون با زبان های دیگر

---

بایسون فقط می تواند در زبان های C , ++C , جاوا کد تولید نماید. برای استفاده از بایسون در زبان های دیگر باید از ابزار های Language binding مانند SWIG استفاده شود.

مجوز و توزیع کد تولیدی

---

به علت آنکه بایسون کدی تولید می کند که به کد منبع پروژه های دیگر اضافه می شود مسائلی از جهت کپی رایت ایجاد می کند.

یک مجوز GPL-compatible لازم نیست

کد تولید شده توسط بایسون شامل مقادیر زیادی از کد حاصل از خود پروژه ی بایسون است. بسته ی بایسون تحت مجوز (GNU General Public License (GPL قرار دارد ولی یک استثنا در آن قرار داده شده است تا GPL به خروجی اعمال نشود.

نسخه های اولیه ی بایسون نشان از قرار داشتن خروجی تحت GPL داشتند. زیرا در آنها تابع yyparse خود در کد حاصل خروجی وجود داشت.

توزیع بسته ها با بایسون

پروژه های نرم افزاری رایگان که از بایسون استفاده می کنند می توانند انتخاب کنند که کد پروژه شان به بایسون ارجاع کند و یا توسط بایسون خروجی بدهد. هر دو روش برای کامپایل کد پروژه کافیست. البته توزیع صرفا ورودی دارای این مساله است که دریافت کنندگان باید یک نمونه ی سازگار بایسون داشته باشند تا بتوانند کد C لازم را هنگام کامپایل پروژه تولید کنند. و توزیع صرفا خروجی این مشکل را دارد که ویرایش پارسر مشکل می شود زیرا کد آن نه توسط انسان نوشته شده است و نه برای انسان ها- هدف آن صرفا دخول به کامپایلر C است.

این مسائل را می توان با توزیع هر دو فایل ورودی و خروجی در کد تولیدی حل کرد. اکثر افراد با کد تولیدی کامپایل خواهند کرد ولی هر کس بخواهد بخش پارسر را ویرایش کند می تواند ابتدا ورودی ها را ویرایش کرده و قبل از کامپایل آنها را بازتولید کند.

پروژه های دارای هردو توزیع معمولا در سیستم های Revision Control کد های تولیدی را ندارند. و فایل ها فقط موقع تولید خروجی تولید می شوند.

برخی مجوز ها از جمله GPL نیازمند این هستند که کد مرجع در حالت ترجیح داده شده ی کاری برای ویرایش قرار داشته باشند. بنابرین پروژه های GPL استفاده کننده از بایسون باید فایل های ورودی بایسون را توزیع کنند.

استفاده

---

به علت آنکه بایسون به عنوان یک جایگزین برای yacc نوشته شده است و تا حد زیادی سازگار است، کد های پروژه های زیادی را می توان به yacc داد. این کار تشخیص اینکه پروژه از کد صرفا-بایسون استفاده می کند یا نه را دشوار می کند. در موارد زیادی، "استفاده" از بایسون می تواند با yacc و یا مشتقات آن جایگزین شود.

بایسون دارای ویژگی هایی است که در yacc یافت نمی شود. بنابرین برخی پروژه ها حقیقتا از بایسون استفاده می کنند. زیرا yacc کافی نخواهد بود.

لیست زیر از پروژه هایی است که از بایسون استفاده می کنند. یعنی نرم افزار های توسعه ای هستند که به قصد ورود به بایسون و یا یک بسته ی سازگار با بایسون ساخته شده اند :

• زبان برنامه نویسی (Ruby (YARV
• زبان برنامه نویسی PHP
• GCC در ابتدا از بایسون استفاده می کرد که در سال 2004 به یک پارسر بازگشتی تغییر داد
• زبان برنامه نویسی GO
• شل BASH
• LilyPond
• PostGreSQL
• MYSQL
• GNU octave
• Perl 5

---

منابع

مشارکت‌کنندگان ویکی‌پدیا. «GNU bison». در دانشنامهٔ ویکی‌پدیای انگلیسی.