足し算、引き算ができるようにする
まずは単純に数値の足し算、引き算ができるようにしてみましょう
仕組み
パーサが処理すべき式はたぶん次のような形式になっているでしょう
完結式 ::= 部分式 部分式 ::= 数値 演算子 部分式 演算子 ::= ＋ あるいは − 数値 ::= 16進数 あるいは 8進数 あるいは 10進数 16進数 ::= 0x[0-9a-fA-F]+ 8進数 ::= 0[0-7]* 10進数 ::= [1-9][0-9]*
「部分式」のところに注目してください
「部分式」の定義に「部分式」自身が含まれていますね
つまり定義が再帰的になっているわけです
そしてこの定義を上から下へと順番に降りながら解析するので、この手法を「再帰下降型」と呼んでいます
このように定義が固まれば後は特に何も考えずにこれをそのまま C++ のコードとして実装すればいいだけです
- まずパーサに指定されるのは「完結式」の文字列ですから「完結式」のところに注目します
つまり「完結式」用の関数 full_expression を呼び出します- 「完結式」に注目すると「部分式」とありますから
full_expression では「部分式」用の関数 operator_add_sub を呼び出します - 次に「部分式」に注目すると「部分式」は「数値」「演算子」「部分式」の順番に出現すると書いてあるので、operator_add_sub ではまず「数値」用の関数 constant を呼び出します
- 数値用の関数である constant では数値を評価するわけですが、これはとりあえず strtol でも使っておくことにしましょう
- 「数値」の処理が終わって operator_add_sub に戻ると「数値」の次には「演算子」があると書いてあるので、operator_add_sub では次に１文字を得て + か - だったら「部分式」用の関数 operator_add_sub を呼び出し、その結果を先ほど得た「数値」に足すか引くかします
- operator_add_sub のやることはそれだけです
- full_expression のやることはそれだけです
- 「完結式」に注目すると「部分式」とありますから
パーサのやるべきことはたったこれだけです
簡単ですね
では実装してみましょう
実装
class string_calc : protected istringstream<char> { bool skipspace(); bool operator_new_number( any_value_t* presult ); bool constant( any_value_t* presult ); bool operator_add_sub( any_value_t* presult ); bool full_expression( any_value_t* presult ); void error_illegal_character( char c ); void error_unexpected_eof(); // とりあえず代入は無効 string_calc& operator=( const string_calc& rhs ); string_calc( const string_calc& rhs ); public: bool eval( const std::string& s, any_value_t* presult ); string_calc(); ~string_calc(); }; string_calc::string_calc(): istringstream<char>() { } string_calc::~string_calc(){ } void string_calc::error_illegal_character( char c ){ // 変な文字だからお終い OutputDebugString( stringprintf( "error: illegal caracter '%c'.\n", c )); } void string_calc::error_unexpected_eof(){ // 予期せぬ EOF OutputDebugString( "error: unexpected EOF.\n" ); } bool string_calc::skipspace(){ while( !eof()){ char c = getch(); if( _ismbblead(( unsigned int )( unsigned char )c ) || !isspace(( unsigned char )c )){ ungetch( c ); break; } } return !eof(); } bool string_calc::operator_new_number( any_value_t* presult ){ bool success = true; if( !skipspace()){ error_unexpected_eof(); success = false; } else{ const char* s = getp(); char* endp = const_cast<char*>(s); strtol( s, &endp, 0 ); size_type cch = endp - s; std::string value = gets( cch ); if( presult ){ presult->assign( TYPEOF_INTEGER, value ); } } return success; } bool string_calc::constant( any_value_t* presult ){ bool success = true; if( !skipspace()){ error_unexpected_eof(); success = false; } else{ char c = at( 0, SEEK_CUR ); if( isdigit( c )){ success = operator_new_number( presult ); } else{ error_illegal_character( c ); success = false; } } return success; } bool string_calc::operator_add_sub( any_value_t* presult ){ bool success = constant( presult ); if( success && skipspace()){ char c = at( 0, SEEK_CUR ); if( c == '+' ){ seek( 1, SEEK_CUR ); any_value_t rhs; success = operator_add_sub( &rhs ); if( success && presult ){ presult->operator_assign_add( rhs ); } } else if( c == '-' ){ seek( 1, SEEK_CUR ); any_value_t rhs; success = operator_add_sub( &rhs ); if( success && presult ){ presult->operator_assign_sub( rhs ); } } } return success; } bool string_calc::full_expression( any_value_t* presult ){ return operator_add_sub( presult ); } bool string_calc::eval( const std::string& s, any_value_t* presult ){ assign( s ); return full_expression( presult ); }
左再帰
もう一度定義を見てみましょう
完結式 ::= 部分式
部分式 ::= 数値 演算子 部分式
演算子 ::= ＋ あるいは −
数値 ::= 16進数 あるいは 8進数 あるいは 10進数
16進数 ::= 0x[0-9a-fA-F]+
8進数 ::= 0[0-7]*
10進数 ::= [1-9][0-9]*
ここで「部分式」の定義が「部分式 ::= 部分式 演算子 数値」ではなく「部分式 ::= 数値 演算子 部分式」となっていることには意味があります
もし「部分式」の定義が「部分式 ::= 部分式 演算子 数値」になっていたとするとどうでしょうか
上記の実装では「部分式」用の関数 operator_add_sub でまず最初に constant を呼んでいますが、ここで operator_add_sub を呼ぶことになりますね
しかし operator_add_sub から何の条件も無く operator_add_sub を呼び出せば、その呼び出された operator_add_sub でもまた無条件に operator_add_sub を呼び出すことになるので無限に呼び出し続ける羽目に陥ってしまいます
「部分式 ::= 部分式 演算子 数値」のように演算子の左側に自分自身を持つ定義を「左再帰（left recursion）」と言います
再帰下降型のパーサでは「左再帰」は上記のように無限に呼び出しが続くことになってしまうので定義から排除する必要があることに気をつけてください
また「部分式」の定義が「部分式 ::= 部分式 演算子 数値」か「部分式 ::= 数値 演算子 部分式」かの違いは、具体的な式で示すと「1 + 2 + 3」とあったときに「( 1 + 2 ) + 3」と計算するのか「1 + ( 2 + 3 )」と計算するのかの違いになります
つまり「左再帰」には左結合性があり、右再帰には右結合性があるということです
これは、どちらが正しい、どちらが間違っている、というものではなく、どのような言語設計にするかの問題です
どちらでもいいのなら左再帰を右再帰に置き換えるのが簡単ではありますが、それは文法自体に影響を与えるということにも気をつけてください
普通の感覚では例えば「1 - 2 - 3」が「-4」であることを考えてみると明らかなように演算子は左結合性が期待されます
上記の実装では演算子は右結合性で実装されているので「1 - 2 - 3」は「1 - ( 2 - 3 )」と解釈されてしまっています
「1 - ( 2 - 3 )」は「2」ですから「1 - 2 - 3」の答えとしては間違っていますね
左結合性を持ちながら「左再帰」の問題を回避するには「部分式」の定義を「数値」と「演算子 部分式」の２つの部分に分けて「演算子 部分式」の部分を新しく「部分式2」として独立させることで実現できます
正しい定義は次のようになります
完結式 ::= 部分式1
部分式1 ::= 数値 部分式2
部分式2 ::= 演算子 数値 部分式2
演算子 ::= ＋ あるいは −
数値 ::= 16進数 あるいは 8進数 あるいは 10進数
16進数 ::= 0x[0-9a-fA-F]+
8進数 ::= 0[0-7]*
10進数 ::= [1-9][0-9]*
これでもいいのですが、「部分式1」「部分式2」という名前だとぱっと見てなんだかわからないので別の適当な名前に変えましょう
完結式 ::= 部分式_add_sub
部分式_add_sub ::= 数値 部分式_add_sub_
部分式_add_sub_ ::= 演算子 数値 部分式_add_sub_
演算子 ::= ＋ あるいは −
数値 ::= 16進数 あるいは 8進数 あるいは 10進数
16進数 ::= 0x[0-9a-fA-F]+
8進数 ::= 0[0-7]*
10進数 ::= [1-9][0-9]*
この方が分りやすいですね
ではこの新しい定義を実装してみましょう
正しい実装
class string_calc : protected istringstream<char> { . . . bool operator_add_sub_( any_value_t* presult ); . . . }; bool string_calc::operator_add_sub_( any_value_t* presult ){ bool success = true; if( skipspace()){ char c = at( 0, SEEK_CUR ); if( c == '+' ){ seek( 1, SEEK_CUR ); any_value_t rhs; success = constant( &rhs ); if( success && presult ){ presult->operator_assign_add( rhs ); } if( success ){ success = operator_add_sub_( presult ); } } else if( c == '-' ){ seek( 1, SEEK_CUR ); any_value_t rhs; success = constant( &rhs ); if( success && presult ){ presult->operator_assign_sub( rhs ); } if( success ){ success = operator_add_sub_( presult ); } } } return success; } bool string_calc::operator_add_sub( any_value_t* presult ){ bool success = constant( presult ); if( success ){ success = operator_add_sub_( presult ); } return success; }
本来は
ところで最初に戻って「数値の足し算と引き算だけができる式」の形というものを考えてみると、それは次のような形であることがわかりますね
数値 数値 ± 数値 数値 ± 数値 ± 数値 数値 ± 数値 ± 数値 ± 数値...
最初がいきりなり ＋ や − で始まることはありませんし、最後が ＋ や − で終わっていることもありませんし、数値が２つ続くこともありませんし、＋ や − が連続することもありません
つまり次のようになっていることがわかります
数値 (演算子 数値)*
これは「式」は「数値」と「演算子 数値」の繰り返しの２つの部分からできているということですね
これを素直に定義に直すと、次のように正しい定義と同じになります
完結式 ::= 部分式_add_sub 部分式_add_sub ::= 数値 部分式_add_sub_ 部分式_add_sub_ ::= 演算子 数値 部分式_add_sub_ 演算子 ::= ＋ あるいは − 数値 ::= 16進数 あるいは 8進数 あるいは 10進数 16進数 ::= 0x[0-9a-fA-F]+ 8進数 ::= 0[0-7]* 10進数 ::= [1-9][0-9]*
本来はこのように最初から正しい定義にたどり着けるはずなのですが、説明の都合上おかしな定義から始めました
