GNU bison

From האנציקלופדיה היהודית
Jump to: navigation, search

GNU bison היא תוכנה ליצירת נתחים תחביריים (parser) שנכתבה למיזם GNU, וזמינה כמעט לכל מערכות ההפעלה. התוכנה נועדה לעזור למתכנתים ליצור תוכנות המנתחות טקסטים מורכבים בשפות שהוגדרו מראש.

הנתח התחבירי הנוצר על ידי התוכנה עובד בשיטה של זיהוי אסימונים (tokens) שהוגדרו מראש (לרוב נעשה הזיהוי הטקסטואלי של האסימונים בעזרת תוכנת flex) וניתוח משמעותם בשפה שהוגדרה לפי מיקומם בטקסט.

בעת השימוש בתוכנה יש ליצור כללים שיופעלו כאשר הנתח התחבירי ייתקל באסימונים מסוימים.

לאחר הרצת התוכנה על קובץ הגדרת כללי השפה הוא יוצר קוד בשפת C שיקרא את הטקסטים בשפה המוגדרת וידע לפרש אותם בהתאם למיקומם במשפט ובכך לנתח נכון את משמעות המשפט.


דוגמא ל "reentrant parser"[edit | edit source]

הדוגמא להלן מראה כיצד ניצן להשתמש ב 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);
}

ה Tokens שיהיו בשימוש הפארסר של 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;
}

שמות ה Tokens הם בדרך כלל נייטרליים: "TOKEN_PLUS" ו"TOKEN_STAR", ולא "TOKEN_ADD" ו "TOKEN_MULTIPLY". אם היינו מספקים אופרטור אונרי "+" היה לא נכון לקרוא ל "+" הזה בשם "TOKEN_ADD". בשפה כמו C‏ "int *ptr" מגדיר pointer ולא את התוצר.

מאחר וה Tokens ניתנים על ידי flex עלינו לספק אמצעי לקשר בין ה Lexer והפארסר[1] .

הנתונים המשמשים לתקשורת YYSTYPE, נקבעים בעזרת הצהרת %union של Bison.

בדוגמא זו, אנו משתמשים בגרסת reentrant של flex ו yacc ולכן אנו חייבים לספק את הפרמטרים לפונקציית yylex כאשר קוראים לה מ yyparse[1] This is done through Bison %lex-param and %parse-param declarations.[2].

%{

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

לבניית הפרויקט נוכל לכתוב 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

קישורים חיצוניים[edit | edit source]


Crystal Clear app ktalkd.png ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לאנציקלופדיה היהודית ולהרחיב אותו.

ערך זה מוגש באדיבות ויקיפדיה העברית. (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה קטן מערך זה ב -7890 תווים

לעדכון מוויקיפדיה, לחץ כאן.

NivdakVeushar.png