古いネタをひっぱりだすシリーズその１

http://kentn.at.infoseek.co.jp/cpp/parser.htmlから移動。
この当時はまだSpiritを知らなかった頃です。たぶん２年かそこら前じゃないかと。
今はどうなってるんでしょうね？

はじめに

ここではメジャーなパーサジェネレータflex & bisonをC++から使う方法を考えてみます。この二つのジェネレータはどちらももともとC言語用に開発されましたが、再入可能性などはあまり深く考えられていませんでした。また、C++から利用する場合にはいくつか不便なところがありました。

ここではよりC++と親和性の高いflex & bisonの使い方を考えます。最終的にはヘッダーファイル一つといくつかの手順を守ることで、手軽にパーサクラスを作成できるようになりました。
とりあえずflexとbisonについて

flexとbisonはどちらもGNUの開発しているユーティリティで、それぞれレキサ（トークナイザ：字句解析器）とパーサ（構文解析器）を生成するジェネレータです。

これらは元々AT&Tで開発されたlexとyaccを元にしており、それぞれの仕様に従った文法で定義を書いていけば、最終的にC言語のプログラムをはき出してくれます。

たとえば、以下はflexで数値と文字列を切り出すプログラムです。

%{
#include 
%}
%%
[0-9][0-9]* { printf("number:%d\n", atoi(yytext)); }
[a-zA-Z][0-9a-zA-Z]* { printf("string:%s\n", yytext); }
%%
int main()
{
  yylex();
  return 0;
}

このように、正規表現を使ってトークン（字句）を定義すれば、それが現れた時に該当する処理を起動させることができます。このファイルを"hoge.l"として保存すると、

flex hoge.l
cc lex.yy.c

のようにしてコンパイルできます。

同様に、簡単なbisonのプログラムを示すと、

%{
#include 
%}
%union {
  double number_;
}
%token  NUMBER
%type  expr, additive_expr, multiplicative_expr, primary
%%
answer
  : expr
  { printf("answer=%f\n", $1); }
  ;
expr
  : additive_expr
  ;
additive_expr
  : multiplicative_expr
  | additive_expr '+' multiplicative_expr
  { $$ = $1 + $3; }
  | additive_expr '-' multiplicative_expr
  { $$ = $1 - $3; }
  ;
multiplicative_expr
  : primary
  | multiplicative_expr '*' primary
  { $$ = $1 * $3; }
  | multiplicative_expr '/' primary
  { $$ = $1 / $3; }
  ;
primary
  : NUMBER
  | '(' expr ')'
  { $$ = $2; }
  ;
%%
int yywrap() { return 0; }
int main() { yyparse(); return 0; }

これは四則演算をするbisonプログラムです。末尾に見慣れたmain関数がありますが、その中で読んでいるyyparse関数というものこそ、bisonが生成する構文解析器の本体です。

flexとC++

さて上で見たように、flexとbisonの基本動作は、指定されたタイミングで与えられたC言語のコード断片を実行するものです。この断片をC++で記述することもできます。やってみましょう。

%{
#include 
%}
%%
[0-9][0-9]* { std::cout << "number:" <%lt; atoi(yytext) << std::endl; }
[a-zA-Z][0-9a-zA-Z]* { std::cout << "string:" <%lt; yytext << std::endl; }
%%
int main()
{
  yylex();
  return 0;
}

flex hoge.l
c++ lex.yy.c

これはこれで良いのですが、実はflexにはC++サポートが備わっています（ずーっと『実験的なもの』とされ続けていますが）ので、これを利用してみます。

やり方はコマンドラインで引数-+を与えるか、%option c++を追加するだけです。ここでは後者を用いています。

ちなみに環境によってはflex++というコマンドが用意されている場合もあります。これはflexを-+オプションつきで呼び出したのと同じ動きをします。

%{
#include 
%}
%option c++
%%
[0-9][0-9]* { std::cout << "number:" <%lt; atoi(yytext) << std::endl; }
[a-zA-Z][0-9a-zA-Z]* { std::cout << "string:" <%lt; yytext << std::endl; }
%%
int main()
{
  FlexLexer* lexer = new yyFlexLexer();
  lexer->parse();
  return 0;
}

呼び出し側のコードを多少書き換える必要がありますが、まあほとんど変えていません。

flexのC++対応で何がうれしいかというと、iostreamを使えるようになる点が上げられます。

従来のflexでは、データの入出力はC言語のファイル操作関数を用いていました。yyin/yyoutというFILE*型の広域変数が用意されており、これに任意のファイルハンドルを代入させることで、入力を切り替える事ができました。

int main()
{
  FILE* fp = fopen("hoge.input", "rb");
  yyin = fp;
  yylex();
  close(fp);
  return 0;
}

…が、C++版では以下のようになります。

int main()
{
  FlexLexer* lexer = new yyFlexLexer();
  std::ifstream in("hoge.input" std::ios::binary);
  lexer->switch_stream(&in);  
  lexer->parse();
  return 0;
}

iostreamでさえあれば、その先が何であっても同様に渡すことができます。std::fstream/std::stringstreamはもちろん、自作のストリームも渡すことができます。

bisonとC++

flexがC++をサポートしたとなれば、そのflexを利用するbisonもC++サポートがついて当然。flexがflex++なら、bisonはbison++だ！…と考えるのは自然です。

ところが、どうも話はそう簡単ではないのです。

まず、bisonに埋め込むコード断片は、C++で記述することができます。これはflexの時と同様です。しかし、bisonにはflexでいう-+オプションや%option c++といった命令は用意されていません。

最も痛いのは、bisonがflexが出力したC++コードを標準でサポートしていない点です。これは、ラッパ関数を用意することで切り抜けられます。

inline int yylex() {
	return yyFlexLexer().yylex();
}

が、試してみると分かりますが、これでは上手く行きません。なぜなら、yyFlexLexerのオブジェクトをyylex関数の呼び出しごとに生成するため、yyFlexLexerが内部で持っている先読み情報が失われてしまうからです。正しくスキャンするためには、一つのyyFlexLexerインスタンスを使い回す必要があります。

たとえば広域変数を一つ用いることで、上手く回避できます。

%{
#include 
#include 

FlexLexer* lexer = NULL;
inline int yylex() { return ((FlexLexer*)lexer)->yylex(); }
%}
%union {
  double number_;
}
%token  NUMBER
%type  expr, additive_expr, multiplicative_expr, primary
%%
answer
  : expr
  { printf("answer=%f\n", $1); }
  ;
expr
  : additive_expr
  ;
additive_expr
  : multiplicative_expr
  | additive_expr '+' multiplicative_expr
  { $$ = $1 + $3; }
  | additive_expr '-' multiplicative_expr
  { $$ = $1 - $3; }
  ;
multiplicative_expr
  : primary
  | multiplicative_expr '*' primary
  { $$ = $1 * $3; }
  | multiplicative_expr '/' primary
  { $$ = $1 / $3; }
  ;
primary
  : NUMBER
  | '(' expr ')'
  { $$ = $2; }
  ;
%%
int yywrap() { return 0; }
int main() { lexer = new yyFlexLexer(); yyparse(); return 0; }

再入可能なパーサとFlexLexerの拡張

><

（予定）

BisonParser.h

ということで、こういうヘッダを用意してみました。これをflexとbisonの両方のソースファイルからインクルードすると、Parserクラスができあがります。

最終的には以下のように使えるものになりました：

%{
#include 
#include 
%}
%option c++
%%
[0-9][0-9]* { std::cout << "number:" <%lt; atoi(yytext) << std::endl; return NUMBER; }
[a-zA-Z][0-9a-zA-Z]* { std::cout << "string:" <%lt; yytext << std::endl; }
%%


%{
#include 
#include 
%}
%union {
  double number_;
}
%token  NUMBER
%type  expr, additive_expr, multiplicative_expr, primary
%%
answer
  : expr
  { printf("answer=%f\n", $1); }
  ;
expr
  : additive_expr
  ;
additive_expr
  : multiplicative_expr
  | additive_expr '+' multiplicative_expr
  { $$ = $1 + $3; }
  | additive_expr '-' multiplicative_expr
  { $$ = $1 - $3; }
  ;
multiplicative_expr
  : primary
  | multiplicative_expr '*' primary
  { $$ = $1 * $3; }
  | multiplicative_expr '/' primary
  { $$ = $1 / $3; }
  ;
primary
  : NUMBER
  | '(' expr ')'
  { $$ = $2; }
  ;
%%
int yywrap() { return 0; }
int main() { Parser parser; parser.parse(); return 0; }

以下がその実装です。

/*
 * BisonParser.h --- a C++ parser class for bison & flex++
 *
 *    Copyright (C) Kent.N, 2002  All rights reserved.
 *
 *  Feel FREE to use/distribute/modify this codes. Enjoy!
 *
 */

#if defined(__cplusplus)

#if !defined(__PARSER_DECLARED__)
#define __PARSER_DECLARED__

class MyLexer;

class Parser {
public:
	MyLexer* lexer_;
	int parse();
};

#endif /* __PARSER_DECLARED__ */

#if defined(YYBISON)

#define YYPARSE_PARAM parser
#define YYLEX_PARAM parser

extern "C" int yylex(YYSTYPE* yylval, void* parser);

#endif /* YYBISON */

#if defined(FLEX_SCANNER)

class MyLexer : public yyFlexLexer {
public:
	YYSTYPE yylval;
	int yylex();
};

inline int yyFlexLexer::yylex() { return 0; }
#define YY_DECL int MyLexer::yylex()

extern int yyparse(void*);

int Parser::parse() {
	lexer_ = new MyLexer();
	return yyparse(this);
}

extern "C" int yylex(YYSTYPE* yylval, void* parser) {
	MyLexer* lexer = static_cast(parser)->lexer_;
	int r = lexer->yylex();
	*yylval = lexer->yylval;
	return r;
}

#endif /* FLEX_SCANNER */

#endif /* __cplusplus */

オチ

…ただし、これはバグがあって上手く動かなかった気がする。
何せ昔のことなのでよく覚えてないけれど…(^^;