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の終端に達した時に呼び出される関数である */
/* 常に１を返すよう再定義 */
#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