2010年7月25日日曜日

flex / bison 使い方メモ


flex と bison の使い、簡単な計算機を作成してみる。


◆ main 関数(C++ を利用する)
.ccファイル名 : calc-main.cc
#include <iostream>
#include "calc-driver.h"

int main(int argc, char **argv)
{
calc_driver driver;
driver.calc(*++argv);
return 0;
}



◆ parser呼び出し関数を実装しているクラス
.ccファイル名 : calc-driver.cc
#include <iostream>
#include <iomanip>
#include "calc-driver.h"


// コンストラクタ
calc_driver::calc_driver()
{
}


// デストラクタ
calc_driver::~calc_driver()
{
}


// calcメソッドはcalc.cc内、main関数から呼ばれる
// 引数に参照を使うため、&を付与
bool calc_driver::calc(const std::string &f)
{
// fileはcalc-driver.h内で定義済みのフィールド
file = f;

// calc-scanner.ll内で実装している本クラスのメソッドを呼ぶ
// メソッド内でyyin変数を使う(flexファイル内で実装されている)
scan_begin();

// 名前空間yyで定義されるcalc_parserクラスのオブジェクト(bisonが生成)を作る
// コンストラクタに本オブジェクトを渡す(ポインタ経由ではなく参照渡し)
// bison定義ファイルの%~-paramで指定したパーサとスキャナの連携用オブジェクトを参照
yy::calc_parser parser(*this);

// 作成したparserオブジェクトからparse関数を呼ぶ
// parse関数が呼ばれると、bisonが生成するyylex関数から
// tokenがひとつづつ読みこまれ、構文解析が行われる
int result = parser.parse();

// calc-scanner.ll内で実装している本クラスのメソッドを呼ぶ
scan_end();

if (result != 0)
return false;
return true;
}

std::string &calc_driver::get_filename()
{
return file;
}

// 仮引数がなぜポインタかというと、flex側で文字列の受け取り時に、
// new std::string(yytext)しているからである
int calc_driver::value(std::string *name)
{
return values[*name];
}


void calc_driver::assign(std::string *value, cnode *node)
{
values[*value] = node->expr(this);
delete value;
delete node;
}


void calc_driver::print(cnode *node)
{
std::cout << node->expr(this) << std::endl;
delete node;
}


struct list_action {
void operator()(const std::pair &it)
{
std::cout << it.first << " = " << it.second << std::endl;
}
} ;


void calc_driver::list()
{
std::for_each(values.begin(), values.end(), list_action());
}


void calc_driver::error(const std::string& m)
{
std::cerr << m << std::endl;
}



◆ 先にコード例を上げた calc-driver.cc用ヘッダファイル
.hファイル名 : calc-driver.h
#ifndef __CALC_DRIVER_H__
#define __CALC_DRIVER_H__

#include "calc-parser.hh"
#include "calc-node.h"

// token_typeを返すyylex関数を定義している
// 本来であれば字句解析用の関数"int yylex(YYSTYPE *yylval)"をbisonが自動で定義する
// 関数内の、YYSTYPEというのは、スキャナとパーサが利用する変数のための共用体のタグ名である
// しかし、今回はbisonの雛形としてlalr1.ccを用いているので変更を加える必要がある
// また、ここで関数の定義をしているのは、calc-driver.ccが本ヘッダファイルをincludeし、
// そのファイル内でparse関数、そしてそこからyylex呼ぶためである
#define YY_DECL \
yy::calc_parser::token_type yylex( \
yy::calc_parser::semantic_type* yylval, \
calc_driver& driver)
// 第1引数 : 変数を授受する共用体の変数ポインタ
// 第2引数 : bison定義ファイルの%*-paramで指定したパーサとスキャナの連携用オブジェクト

YY_DECL;

class calc_driver {
private:
// 変数とそこに代入される値は連想配列で管理
std::map values;
std::string file;

private:
void scan_begin();
void scan_end();

public:
calc_driver();
virtual ~calc_driver();

bool calc(const std::string &f);
std::string &get_filename();
int value(std::string *name);
void assign(std::string *value, cnode *node);
void print(cnode *node);
void list();
void error(const std::string& m);
} ;

#endif



◆ bison 用設定ファイル
ファイル名 : calc-parser.yy
// 雛形の設定
// 雛形の形式の指定。c++のソースコードに展開されるようにlalr1.ccにする
%skeleton "lalr1.cc"
// bisonが生成するパーサ用のクラス名を指定する
%define "parser_class_name" "calc_parser"


// C宣言部
// bisonが生成するC++ヘッダファイルに書き込まれる(bisonは利用しない)
%{
#include <string>
// flexがincludeするヘッダファイル内に下記ヘッダファイルの情報が必要
#include "calc-node.h"
%}


// 引数の設定
// パーサから呼び出すスキャナと引数を使って連携を取れる
// 参照渡しをすることでリエントラント(再入可能)な構文解析器の生成が可能となる
// 引数を使わない場合は、外部変数や外部関数を使うことになる
%parse-param { calc_driver& driver }
%lex-param { calc_driver& driver }

// デバッグ用
%error-verbose


// 記号の設定
// スキャナから値を受け取る場合と、パーサ内部で使われる変数の型を指定する
// bisonが生成するヘッダファイル内で、unionのタグ名をYYSTYPEに、
// 変数名をyyvalとしして定義される
%union
{
int ival;
std::string *sval;
cnode *expr;
}


// C宣言部
// bisonが生成するソースファイルに書き込まれる(bisonが利用する)
// 文字規則部にて下記ヘッダ内で定義しているクラスを使う
%{
#include "calc-driver.h"
%}


// 終端記号設定(<>部は型)
// TK_EOFは明示的に0を返したいため0という別名をつけておく
%token TK_EOF 0
%token <ival> TK_IVAL
%token <sval> TK_IDENTIFIER
%token TK_PRINT
%token TK_LIST


// 非終端記号の設定(<>部は型)
%type <expr> expr


// svalメンバ変数はスキャナ側で"new std::string(yytext)"して作られるため
%destructor { delete $$; } TK_IDENTIFIER

// 非終端記号であるexprはパーサ側で"new cnode(・・・)"して作られるため
// ただし、文法規則部の$1などの変数は引数としてCコード中で利用されるため、
// そこでdeleteしてやる必要がある
%destructor { delete $$; } expr

// 下にいくほど優先度が高い
// leftは右から左へ評価順序を指定するためのものである
%left '+' '-';
%left '*' '/';
%left NEG;

// 文法規則部
%%
%start unit;

unit : state
| unit state
;

state : TK_IDENTIFIER '=' expr '\n' { driver.assign($1, $3); }
| TK_PRINT expr '\n' { driver.print($2); }
| TK_LIST '\n' { driver.list(); }
;

expr : expr '-' expr { $$ = new cnode(OP_MINUS, $1, $3); }
| expr '+' expr { $$ = new cnode(OP_PLUS, $1, $3); }
| expr '*' expr { $$ = new cnode(OP_TIMES, $1, $3); }
| expr '/' expr { $$ = new cnode(OP_DIVIDE, $1, $3); }
| '-' expr %prec NEG { $$ = new cnode(OP_NEG, $2, 0); }
| '(' expr ')' { $$ = $2; }
| TK_IDENTIFIER { $$ = new cnode(OP_VALUE, $1); }
| TK_IVAL { $$ = new cnode(OP_CONST, $1); }
;

/* %prec NEG の説明 */
/* '-' は'-' トークンではなく、NEGの'-'を使うという意味である */

%%

// Cプログラム部
// bisonが生成するソースファイルに埋め込まれる
void yy::calc_parser::error(const yy::calc_parser::location_type&, const std::string& m)
{
driver.error(m);
}



◆ flex 用設定ファイル
ファイル名 :calc-scanner.ll
/* Cコード部 */
/* 生成されるソースコードに展開される */
%{
#include <cstdlib>
#include <cerrno>
#include <climits>
#include <string>
/* 字句定義部にて下記ヘッダ内で定義しているクラスを使う */
#include "calc-driver.h"
/* bisonが生成するヘッダファイルは必須 */
#include "calc-parser.hh"


/* yyinの終端に達した時に呼び出される関数である */
/* 常に1を返すよう再定義 */
#undef yywrap
#define yywrap() 1

/* アクションの中で呼び出されるとスキャナの実行を終了する */
#define yyterminate() return token::TK_EOF
%}


/* flaxのオプションの記載 */
/* 不要な関数を組み込まない */
%option noyywrap nounput batch
%option never-interactive
%option noyy_scan_buffer
%option noyy_scan_bytes
%option noyy_scan_string
%option nounistd


/* %% %{ %} %% という構造になっている*/
/* %{%} 内にflexから生成されたソースコード中に展開させるコードを記載する
/* その次に字句定義を行う*/
%%
%{
/* 名前空間yy内、calc_parserクラス内のtoken構造体の定義 */
typedef yy::calc_parser::token token;

std::string string_buffer;
%}


"list" return token::TK_LIST;

"print" return token::TK_PRINT;

[-+*/=()\n] return yy::calc_parser::token_type(yytext[0]);

[ \t]+ ;

[1-9][0-9]* {
errno = 0;
long n = strtol(yytext, NULL, 10);
if (n < LONG_MIN || n > LONG_MAX || errno == ERANGE)
driver.error("整数が範囲外です。");
yylval->ival = n;
return token::TK_IVAL;
}

"0" {
yylval->ival = 0;
return token::TK_IVAL;
}

[a-zA-Z_][a-zA-Z_0-9]* {
yylval->sval = new std::string(yytext);
return token::TK_IDENTIFIER;
}

. driver.error("この文字を識別子で使用することはできません。");

%%


/* Cコード部 */
/* flexから生成されたソースコード末尾に展開させる関数を記載する */
void calc_driver::scan_begin()
{
if ((yyin = fopen(file.c_str(), "r")) == 0)
error(file + " がオープンできません。");
}

void calc_driver::scan_end()
{
fclose(yyin);
yylex_destroy();
}



◆ ノードクラスコード
ファイル名 : calc-node.cc
#include "calc-node.h"
#include "calc-driver.h"

int cnode::op()
{
return op_;
}

int cnode::value()
{
return value_;
}

std::string &cnode::string()
{
return *string_;
}

cnode *cnode::left()
{
return left_;
}

cnode *cnode::right()
{
return right_;
}

cnode::cnode(int op, cnode *left, cnode *right)
: op_(op), left_(left), right_(right), value_(NULL), string_(NULL)
{
}

cnode::cnode(int op, int value)

: op_(op), left_(NULL), right_(NULL), value_(value), string_(NULL)
{
}

cnode::cnode(int op, std::string *str)

: op_(op), left_(NULL), right_(NULL), value_(NULL), string_(str)
{
}

int cnode::expr(calc_driver *driver)
{
switch (op_) {
case OP_PLUS:
return left_->expr(driver) + right_->expr(driver);

case OP_MINUS:
return left_->expr(driver) - right_->expr(driver);

case OP_TIMES:
return left_->expr(driver) * right_->expr(driver);

case OP_DIVIDE:
return left_->expr(driver) / right_->expr(driver);

case OP_CONST:
return value_;

case OP_VALUE:
return driver->value(string_);

case OP_NEG:
return -left_->expr(driver);

default:
return 0;
}
}



◆ 先にコード例を上げた calc-node.cc 用ヘッダファイル
ファイル名 : calc-node.h
#ifndef __NODE_H__
#define __NODE_H__

#include <string>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>

enum {
OP_NEG,
OP_PLUS,
OP_MINUS,
OP_TIMES,
OP_DIVIDE,
OP_VALUE,
OP_CONST,
} ;

class calc_driver;

class cnode {
private:
int op_;
int value_;
std::string *string_;
cnode *left_;
cnode *right_;

public:
cnode(int op, cnode *left, cnode *right);
cnode(int op, int value);
cnode(int op, std::string *str);
virtual ~cnode()
{
delete left_;
delete right_;
delete string_;
}

int expr(calc_driver *driver);
int op();
int value();
std::string &string();
cnode *left();
cnode *right();
} ;

#endif



◆ make 用ファイルの準備
ファイル名 : Makefile
CC = gcc
OBJ = calc-main.o calc-node.o calc-driver.o calc-parser.o calc-scanner.o
BISON_OUTPUT = calc-parser.cc calc-parser.hh location.hh position.hh stack.hh
FLEX_OUTPUT = calc-scanner.cc

CFLAGS = -Wall


calc: $(OBJ)
$(CC) $(CFLAGS) -o $@ $(OBJ) -lstdc++

.cc.o:
$(CC) -c $(CFLAGS) -o $@ $<

$(BISON_OUTPUT): calc-parser.yy
bison -d -ra -ocalc-parser.cc calc-parser.yy

$(FLEX_OUTPUT): calc-scanner.ll
flex -8 -ocalc-scanner.cc calc-scanner.ll

calc-parser.o: $(BISON_OUTPUT)
calc-scanner.o: $(FLEX_OUTPUT)


calc-main.o : calc-driver.h calc-driver.cc
calc-node.o : calc-node.h calc-driver.h calc-node.cc
calc-driver.o : calc-driver.h calc-driver.cc

calc-parser.o : calc-node.h calc-driver.h calc-parser.hh stack.hh location.hh position.hh
calc-scanner.o : calc-driver.h calc-parser.hh stack.hh location.hh position.hh



◆ ビルドする
$ make


◆ 実行する
$ vi file
a=3+5*2
b=10-8/(4-2)
list
print a+b

$ ./calc file
a = 13
b = 6
19



0 件のコメント:

コメントを投稿