فلکس :

 فلکس (Flex) یک نرم افزار متن باز و رایگان است که می توان بجای lex استفاده کرد. Lex برنامه کامپیوتری است که برای تحلیل واژگانی استفاده می شود. فلکس بیشتر به عنوان پیاده سازی lex همراه با تولیدکننده پارسر Yacc بر روی سیستم عامل های مشتق شده از BSD و یا همراه با گنو بایسون در پورت های BSD و توزیع های گنو لینوکس استفاده می شوند. برخلاف بایسون، فلکس بخشی از پروژه گنو نیست وتحت لیسانس GPL منتشر نشده است.

فلکس توسط ورن پاکسون در سال 1987 با زبان C نوشته شد. وی در حال ترجمه یک تولیدکننده Ratfor بود که توسط جف پسکانزر هدایت میشود

مثالی از تحلیل کننده های واژگانی

این در واقع مثالی از یک اسکنر فلکس برای زبان برنامه نویسی دستوری PL/0است. توکن های تشخیص داده شده :+ , - , * , / , = , ( , ), , , ; , . , := , < , > , <> , >=، اعداد 0 تا 9، حروف a تا z و کلمات کلیدی begin ، call، const، do، end، if، odd، procedure، then، var، while می باشد.

%{
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%
int yywrap(void){return 1;}

پیچیدگی زمانی

یک تحلیل کننده واژگانی فلکس معمولا دارای پیچیدگی زمانی (On) است که یعنی به طول ورودی هم بستگی دارد. در واقع آن تعداد ثابتی از عملیات را برای هر سمبل ورودی اجرا می کند. این ثابت بسیار کم است: GCC، 12 دستور را برای حلقه DFA تولید می کند. توجه داشته باشید که این ثابت وابسته به طول توکن ها، طول عبارت ثابت و اندازه DFA می باشد.

بازگشتی

به صورت پیشفرض، اسکنر تولید شده توسط فلکس بازگشتی نیست. این امر می تواند منجر به مشکلاتی جدی برای برنامه هایی شود که از اسکنر تولید شده از نخ های مختلف استفاده می کنند. برای غلبه بر این موضوع، گزینه هایی وجود دارد که فلکس به منظور رسیدن به بازگشت پذیری فراهم می کند. یک موضوع جزئی از این گزینه های می تواند در راهنمای فلکس یافت شود.

استفاده تحت محیط غیر یونیکسی

به صورت نرمال، اسکنر تولید شده شامل ارجاعاتی به هدرفایل unistd.h می شود که خاص یونیکس است. برای پرهیز از تولید کد که شامل unistd.h می شود، باید از %option استفاده کرد. موضوع دیگر، فراخوانی isatty است که در کد تولید شده یافت می شود.

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

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

بایسون :  

گنو بایسون که با نام بایسون شناخته می شود، یک تولیدکننده پارسر است که بخشی از پروژه گنو محسوب می شود. بایسون ویژگی های یک زبان مستقل از متن را می خواند، ابهامات پیمایشی آن را می گیرد و یک پارسر یا پیمایش کننده به C، C++ یا جاوا تولید می کند که رشته ای از توکن ها را گرفته و تشخیص می دهد که آیا این رشته با گرامر مربوطه مطابقت دارد یا نه. بایسون به صورت پیشفرض، پارسرهای LALR تولید می کند ولی پارسرهای GLR هم می تواند بسازد.

در حالت Posix، بایسون یک تولیدکننده پارسر سازگار با yacc است ولی اصلاحاتی را نسبت به آن داشته است. فلکس، یک تحلیل کننده واژگانی خودکار است که اغلب با بایسون استفاده می شود تا بایسون را با توکن ها در کنار هم آورد

.

بایسون در ابتدا توسط روبرت کربت در سال 1988 نوشته شد. بعدها در سال 1990، روبرت کربت تولیدکننده پارسر دیگری به نام Berkeley Yacc نوشت. بایسون توسط ریچارد استالمن با Yacc سازگار شد. بایسون یک نرم افزار آزاد است و هم اکنون تحت مجوز عمومی گنو در دسترس می باشد.

یک مثال کامل از پارسر بازگشتی

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

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

توکن های تولید شده توسط پارسر بایسون از فلکس استفاده می کنند.

%{
/*
* Lexer.l file
* To generate the lexical analyzer run: "flex Lexer.l"
*/
#include "Expression.h"
#include "Parser.h"
#include 
%}
%option outfile="Lexer.c" header-file="Lexer.h"
%option warn nodefault
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
LPAREN "("
RPAREN ")"
PLUS "+"
MULTIPLY "*"
NUMBER [0-9]+
WS [ \r\n\t]*
%%
{WS} { /* Skip blanks. */ }
{NUMBER} { sscanf(yytext, "%d", &yylval->value); return TOKEN_NUMBER; }
{MULTIPLY} { return TOKEN_MULTIPLY; }
{PLUS} { return TOKEN_PLUS; }
{LPAREN} { return TOKEN_LPAREN; }
{RPAREN} { return TOKEN_RPAREN; }
. { }
%%
int yyerror(const char *msg) {
fprintf(stderr,"Error:%s\n",msg); return 0;
}

از آنجاییکه توکن ها توسط فلکس تولید می شوند، باید ابزاری برای ارتباط بین پارسر و تحلیل های واژگانی فراهم کرد. از انواع داده ای که برای ارتباط استفاده می شود، YYSTYPE است که استفاده می شود تا %union را اعلان کند.

از آنجایی که در این نمونه از نسخه بازگشتی فلکس و 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 {
#ifndef YY_TYPEDEF_YY_SCANNER_T
#define YY_TYPEDEF_YY_SCANNER_T
typedef void* yyscan_t;
#endif

}
%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;
}
%left '+' TOKEN_PLUS
%left '*' TOKEN_MULTIPLY
%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_PLUS
%token TOKEN_MULTIPLY
%token  TOKEN_NUMBER
%type  expr
%%
input
: expr { *expression = $1; }
;
expr
: expr[L] TOKEN_PLUS expr[R] { $$ = createOperation( ePLUS, $L, $R ); }
| expr[L] TOKEN_MULTIPLY expr[R] { $$ = createOperation( eMULTIPLY, $L, $R ); }
| TOKEN_LPAREN expr[E] TOKEN_RPAREN { $$ = $E; }
| TOKEN_NUMBER { $$ = createNumber($1); }
;
%%

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

/*
* main.c file
*/
#include "Expression.h"
#include "Parser.h"
#include "Lexer.h"
#include 
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)) {
// couldn't 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 ePLUS:
return evaluate(e->left) + evaluate(e->right);
default:
// shouldn't be here
return 0;
}
}
int main(void)
{
SExpression *e = NULL;
char test[]=" 4 + 2*10 + 3*( 5 + 1 )";
int result = 0;
e = getAST(test);
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++ و جاوا تولید کند. برای استفاده از پارسر تولید شده بایسون از دیگر زبان ها، به یک ابزار انقیاد زبان مانند SWIG نیاز است که می تواند استفاده شود.

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

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

عدم نیاز به مجوز سازگار با GPL

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

استفاده

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

بایسون ویژگی هایی دارد که در Yacc استفاده نمی شود، بنابراین می توان صادقانه گفت بسیاری از پروژه هایی که توسط بایسون استفاده می شوند، Yacc نمی تواند اجرا کند.

در زیر، لیستی از پروژه هایی است که از بایسون استفاده می کند و یا با بسته های بایسون سازگار هستند.

• زبان برنامه نویسی روبی (YARV)

• زبان برنامه نویسی PHP

• GCC با بایسون کار خود را شروع کرد ولی بعدها به پارسر دست نویس دیگر سوئیچ کرد.

• زبان برنامه نویسی GoGC

• پوسته shell که از گرامر yacc برای پیمایش ورودی های یک دستور استفاده می کند.

• LilyPond

• PostgreSQL

• MySQL