raccのparser.rbへのとりあえずのパッチ作成

racc 1.2.6のcparseで無限ループ発生せずで、parser.rbとcparseの参照するテーブルの内容が異なるのではないかという予想を立てていましたが、またしてもこの予想は外れていました.
cparseはC言語によるrubyの拡張ライブラリとして実装されてており、参照するテーブルは同一でした.
拡張ライブラリ側で参照する際に、参照する位置がずれたりしないかとも考えましたが、拡張ライブラリのデバッグ用出力を有効にして、parse.rbとcparser.cの両者の出力内容を比較した結果、文法エラーになるトークンを読み込んで、エラーと判定し、エラー回復モードに入るまではまったく同じでした。
違いは、cparse.cがエラー処理として、(仮想的な)エラートークンをシフトするのに対し、parser.rbは文法エラーになるトークンをそのままシフトすることでした。

振り出しに戻ってしまったのですが、よくよくcparse.cを調べてみると、エラー回復モード中に、エラートークンを読み込む処理をする処理がか書かれていました。
それに対して、parser.rbには、該当する処理が存在しませんでした.

そこで、parser.rbに必要な処理を追加すのが、以下に示すパッチです.

ただし、cparse.cでは、(エラー回復モード中のエラー処理には)goto文で飛んできて、(エラー処理が終われば)goto文で(飛んできた所の次の行に)戻っているため、parser.rbにどう書くのが適切かは自信がないです。
また、tecsgenに同梱されているテストケースを実行すると、@racc_state(パーサ内部の状態遷移を管理する配列)がnilになる場合があり、とりあえず動作させるために、@racc_stateがnliの場合には、処理を打ちきるという修正を加えました.

上記の事情を踏まえた上での、ruby 1.8.7に同梱されたraccのparser.rbに対するパッチを以下に示します.

これにより、cparseでなくparser.rbで実行した時でも、テストケースを全て実行できました。
すくなくとも無限ループにはなりませんでした。
#Linuxのruby1.8.7での実行結果です.
#もともとの発端になったJRubyではまだ試していません.

Index: parser.rb
===================================================================
--- parser.rb   (リビジョン 23907)
+++ parser.rb   (作業コピー)
@@ -115,6 +115,10 @@
 
       catch(:racc_end_parse) {
         while true
+#addeb by komianmi
+          break unless @racc_state[-1]
+          break if @racc_state.length < 1
+#end
           if i = action_pointer[@racc_state[-1]]
             if @racc_read_next
               if @racc_t != 0   # not EOF
@@ -294,6 +298,47 @@
             racc_e_pop @racc_state, @racc_tstack, @racc_vstack
           end
         end
+#added by kominami
+        # shiftreduce error token 
+        if act > 0 and act < shift_n
+          #
+          # shift
+          #
+          @racc_vstack.push @racc_val
+          @racc_state.push act
+          @racc_read_next = true
+          if @yydebug
+            @racc_tstack.push @racc_t
+            racc_shift 1, @racc_tstack, @racc_vstack
+          end
+        elsif (act < 0 && act > -(reduce_n)) 
+          #
+          # reduce
+          #
+          code = catch(:racc_jump) {
+            @racc_state.push _racc_do_reduce(arg, act)
+            false
+          }
+          if code
+            case code
+            when 1 # yyerror
+              @racc_user_yyerror = true   # user_yyerror
+              return -reduce_n
+            when 2 # yyaccept
+              return shift_n
+            else
+            raise '[Racc Bug] unknown jump code'
+            end
+          end
+
+        elsif (act == shift_n)
+          racc_accept if yydebug
+          return vstack[0]
+
+        else 
+            rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
+        end
+#end
         return act
 
       else

racc 1.2.6のcparseで無限ループ発生せず

<a href=”http://www.northern-cross.info/wordpress/index.php/archives/26″>racc 1.3のcparseで無限ループ発生</a>で、cparseでもエラー回復モードからエラー回復できず、無限ループに陥ったことを報告しました。

1.3.0以外の(別のことが原因で実行できなかった1.3.1, 1.3.を除いて)1.3.*では無限ループになりませんでした.

また、1.3.0の一つ前のバージョンの、1.2.6では無限ループが発生しませんでした.

1.3.0と1.2.6は構造体のメンバに直接アクセスするか、構造体へのポインタを介してアクセスすか程度の違いしかなく、無限ループになるかならないかは、参照するテーブルの違いの可能性が大きいです。

より具体的に言えば、テーブルを作成するメソッドの違いではないかということです。

複数のテーブル間の参照がからんでくるので、テーブルの内容の一がずれていたり指している先がどこか一ヶ所でもずれてたら、その後の参照内容が間違ってしまいます。

実際、1.3.0では、文法エラーとなるトークンを読み込んだとき、文法エラーであるとは判定しています。

しかし、それに対するアクションが定義済みと判断し、エラーとなるトークンをそのままシフト、還元して、最終的に無限ループになってしまいます。

もしアクションを示すテーブルの一つ前の要素をさしていたら、アクションは未定義と判定され、状態を一つ前に戻し、$endを読みこむことになり、エラー回復につながるのですが。

次は、テーブル作成の部分を調べてみます。

racc 1.3のcparseで無限ループ発生

raccのparser.rbとcparseの実装上の違いで、「振る舞いが異なる原因となるところを見つけました」と書きました.
その後、この予想を確かめるべくraccのリポジトリから、どの時点でcparseとparser.rbの処理が異なるようになったか、を

調べたのはhttp://i.loveruby.net/svn/public/racc/trunkです。
以前はcvsのリポジトリを使っていたようでしたが、現在はCVSのリポジトリにはアクセスで来ませんでした。
SVNのリポジトリでは、以下が最も古いログです。
r1611 | 1999-06-30 11:52:10 +0900 (水, 30 6月 1999) | 1 line

ただし、ディレクトリ構成も過去からずいぶん変更されているようで、あるリビジョン以前では、目的とするcparse.cの過去のリビジョンとのdiffをとるのが面倒になりました。

結局、raccの過去のアーカイブから調べたいバージョンを取ってきて、ローカルで展開して比較することにしました。
ログを元に推測が出来る分、当てずっぽうよりはずいぶんマシです.

さて私の予想で、今回も外れた部分があります。
私が注目していたのは、エラー回復モードに入ってから、エラーとなった場合のトークンに、対応するアクションが存在するかしないかを、いろいろ調べて、なければラベルerror_popに飛んでいたところでした。

しかし、racc 1.4まで遡っても、cparse.cでは無限ループになりませんでした.

racc1.4は、エラー判定はするものの、それ以降のバージョンのコードと比較して、判定方法はとてもあっさりしていました。

私としては、あんなにしつこくチェックしているから、エラーの判定漏れがないのかなと思っていましたが、文法エラーの時に、(エラー時のアクションが定義されていなければ)ひとつ前の状態にもどるという方針が(今回のようなエラーに対しては)有効のようです。

バージョンを遡って試してみたところ、racc1.3になってやっとcparseでもエラーになることを発見しました.

ただし、1.3といっても1.3.*すべてを試したわけではないので、もっと絞り込む必要があります.

raccのparser.rbとcparseの実装上の違い

raccのparser.rbとcparseの違いでは、入力に対する振る舞いの違いについてのべました。
その後、両者を比較して、振る舞いが異なる原因となるところを見つけました.

ソースは、ruby 1.8.7のsvnのtrunkの最新版です。

パス: .
URL: http://svn.ruby-lang.org/repos/ruby/branches/ruby_1_8
リポジトリのルート: http://svn.ruby-lang.org/repos/ruby
リポジトリ UUID: b2dd03c8-39d4-4d8f-98ff-823fe69b080e
リビジョン: 23875
ノード種別: ディレクトリ
準備中の処理: 特になし
最終変更者: svn
最終変更リビジョン: 23875
最終変更日時: 2009-06-28 05:11:49 +0900 (日, 28 6月 2009)

なお以下から入手したracc 1.4.6でもparser.rbの該当個所は変更されていませんでした.
http://rubyforge.org/projects/racc/

違いはcparse.cの452行目から始まる以下の関数内での処理にあります。

   452	static void
   453	parse_main(struct cparse_params *v, VALUE tok, VALUE val, int resume)

  (略)

(ここに来るまでに、エラー回復モードになっています)

   591	    /* check if we can shift/reduce error token */
   592	    D_printf("(err) k1=%ld\n", v->curstate);
   593	    D_printf("(err) k2=%d (error)\n", ERROR_TOKEN);
   594	    while (1) {
   595	        tmp = AREF(v->action_pointer, v->curstate);
   596	        if (NIL_P(tmp)) goto error_pop;
   597	        D_puts("(err) pointer[k1] ok");
   598	
   599	        i = NUM2LONG(tmp) + ERROR_TOKEN;
   600	        D_printf("(err) i=%ld\n", i);
   601	        if (i < 0) goto error_pop;
   602	
   603	        act_value = AREF(v->action_table, i);
   604	        if (NIL_P(act_value)) {
   605	            D_puts("(err) table[i] == nil");
   606	            goto error_pop;
   607	        }
   608	        act = NUM2LONG(act_value);
   609	        D_printf("(err) table[i]=%ld\n", act);
   610	
   611	        tmp = AREF(v->action_check, i);
   612	        if (NIL_P(tmp)) {
   613	            D_puts("(err) check[i] == nil");
   614	            goto error_pop;
   615	        }
   616	        if (NUM2LONG(tmp) != v->curstate) {
   617	            D_puts("(err) check[i] != k1");
   618	            goto error_pop;
   619	        }
   620	
   621	        D_puts("(err) found: can handle error token");
   622	        break;
   623	          
   624	      error_pop:
   625	        D_puts("(err) act not found: can't handle error token; pop");
   626	
   627	        if (RARRAY(v->state)->len < = 1) {
   628	            v->retval = Qnil;
   629	            v->fin = CP_FIN_CANTPOP;
   630	            return;
   631	        }
   632	        POP(v->state);
   633	        POP(v->vstack);
   634	        v->curstate = num_to_long(LAST_I(v->state));
   635	        if (v->debug) {
   636	            POP(v->tstack);
   637	            rb_funcall(v->parser, id_d_e_pop,
   638	                       3, v->state, v->tstack, v->vstack);
   639	        }
   640	    }

この中で、ラベルerror_popを指定したgoto文がありますが、これに該当する処理がparser.rbには存在しません。
ラベルerror_popでは、エラーとなったトークンにに対するアクションが見つからない場合、そのエラートークンを読み込まなかったことにして(スタックからpopして)います。

parser.rbではこの処理に飛ぶかどうかの判定をするところがありません。
また、判定できるように参照するテーブルなどがつくられているかどうかも、不明です。
#まだそこまで調べれていません。
#今回の調査のきっかけとなったケースでは、はエラートークンに対するアクションが得られるのですが、そのアクションをとると、最終的に無限ループにおちいってしまいました。

raccのparser.rbとcparseの違い

さらに引き続き(raccのエラー回復モードは頑張りすぎ?tecsgen の Exerb版, Jruby 版の障害について)、raccのparser.rbとcparseの動作の違いを調べています.

昨日は、parser.rbがエラー回復モードで、定義された文法を満たすトークンの並びを得ようとして、(入力が終わっているのに)延々と次のトークンを得ようとして、無限ループに陥っているようだと書きました。
このことを指して「頑張りすぎ」と評していました。

そして、同じ不完全な内容の入力(不完全故に文法エラーになる)に対して、正常終了して文法エラーを報告するcparseは「頑張らない」ようにしているのではないかと予想していました.

今回、cparseを用いて、同じくtecsgen -yを指定してデバッグ表示させて見たところ、以外な結果になりました。

celltype tTaskMain {};

に対して、’}’を読み込むと文法エラーになります。
そしてエラー回復モードに入ります。

ここでcparseの場合、いったん読み込んだトークンを
捨てて、$endというトークンを読み込みます。
その次のトークンとして「}」を読み込みます。
後は、入力の通りにトークンを読み込みます。

エラー回復モードに入ったときに(入力には存在しない)仮想的なトークンを読み込んでいます。

この影響で、必要なトークンが不足しているために発生した文法エラーから回復することができていました。

先日以下の入力なら、parser.rbでも無限ループにはいらないと書きました.

celltype tTaskMain {}};

cparseの場合、エラー回復モード時に、あたかも上記のような入力がされていたかのように振る舞います。

$endが追加されるのは、他の文法エラーになる入力でも確かめてみました。

最初の私の予想(入力の終わりを特別扱いして、頑張らない)は外れていました。
cparseが採用しているエラー回復処理の方針は、どこかで聞いた覚えがあるのですが、思い出せません。またちょっとググってみても分かりませんでした。

(追記)
上の書き方ですと、parser.rbとcparse.soがまるっきりエラー回復モードのやりかたが違っているように受け取られるかも知れません。
しかし、rubyとC言語の違いはありますが、アルゴリズムとしては、(私が今まで調べて、理解した範囲では)どちらも同じに見えます。
動作の違いは、微妙な判定条件の違いとか、参照するテール(テーブルはそれぞれ用に作成されます)の内容の違いによるのではないかと感じています。

Reblog this post [with Zemanta]

raccのエラー回復モードは頑張りすぎ?

昨日の続きで、TECSジェネレータでの文法定義と、CDLファイルでのエラーになる書き方を調べています。

今回も途中報告です。

前回に書いたerror-7.cdlは、以下の文法の記述に誤りがある場合のテスト-ケースでした.

文法定義

celltype
: CELLTYPE celltype_name ‘{‘ celltype_statement_list ‘}’ ‘;’

error-7.cdlの内容

celltype TaskMain {
/* attributeの定義が空でならsyntax error */
/*    attr {

x = 0;

};
*/
};

これはコメントを無視すると、以下と同等です。

celltyope TaskMain {};

文法定義と比較すると、celltype_statement_listという要素が不足しているため、文法エラーとなります。

実際、raccの生成したパーザはこの文法エラーを認識して、on_error()を呼び出しています.

ここで、on_error()とは、raccを用いてパーザを作成する人が、エラー処理を行うために自由に定義できるメソッドです。

on_error()でパース自体を中止することもできます。

また中止せずに、raccが生成したパーザにエラー回復モードで処理を続行させることができます。

エラー回復モードは、文法エラーが見つかった箇所を、エラーだとは認識しつつも、そこに正しい記述があったものとみなして、パース処理をつづけることです。

今回の文法定義の場合を例にとると、celltype_statement_listが存在するべきところに、「}」があったため、エラーとなります.

この後エラー回復モードで処理を続けようとして、「}」をcelltype_statement_listだとみなします。

文法では、この後に「}」と「;」がこの順番に記述されていなければなりません。

しかし、入力としては「;」しか存在しません。

raccは入力の終わりを$endというトークンとして扱います。

しかし、これが来ても、文法エラーが解消されません.パーザは次の入力を求めますが、実際の入力は終わっているので、$endしか渡してもらえません.

結局ここで無限ループが発生してしまいます。

実は、同じエラー内容でも以下の場合は、パーザは文法エラーを報告し、正常に終了します.

(文法としてはエラーになるが、正常終了する場合の記述)

celltyope TaskMain {}};

最初の「}」が来た時点でエラーと判断されますが、エラー回復モードになっても「}」、「;」と続くため、celltypeの文法定義に合致し、エラー回復モードは終了します。その後入力の終わり$endが来て、パーザは正常終了します。

エラー回復モードが(期待するより)頑張りすぎているのかもしれません.

ただし、入力の終わりがきたら必ず打ち切るようにするには、入力の終わりを特別扱いし、どんな状態であっても終了するルーチンをつくるか、どの状態からでも入力の終わりが来たら終了する状態遷移テーブルを作成する必要があると思います。

後、raccが手本にしたyaccの仕様がどうだったのか、確認したほうがいいかな。

raccの動作が、yaccの仕様の通りであれば、on_error()で対処するのがbetterだと思います.

tecsgen の Exerb版, Jruby 版の障害について

TECS 開発ブログの記事「tecsgen の Exerb版, Jruby 版の障害 (06/21)」、「tecsgen の Exerb版, Jruby 版の障害(続き) (06/24) 」 において、TECSジェネレータの障害が報告されています.

TECSジェネレータとは、TECSにおいてコンポーネントの定義、組み合わせを指定したファイルであるCDLファイル(拡張子が「.cdl」であるテキストファイル)から、コンポーネントを実現する部分のCソースコードを自動生成します.また、コンポーネントが提供する機能(これは個々のコンポーネントの作成者がコーディングする必要があります)のCソースの雛形も生成します.

このTECSジェネレータは、Rubyで書かれています。

より具体的に言うと、CDL(Component Description Language)という言語をパースするためにRubyでかかれたパーザジェネレータRaccを用いています.

これがJavaで実装されたRuby、JRubyで期待した動作をしない(Out Of Memoryが発生する)という報告があったことが発端でした。

この問題に対して、私も調べて見ました。

今回は、Linux(Fedora 7)で行いました。

1.まず、問題を再現させるために、Rubyの標準ライブラリのRaccそのままではなく、一部手を加えたものを用いま す。

cp /usr/lib/ruby/1.8/racc/parser.rb ~/lib/ruby/racc

export RUBYLIB=~/lib/ruby/racc:$RUBYLIB

~/lib/ruby/racc/parser.rbの40行め、モジュールRaccの中のクラスParserに対する機能追加の部分で、以下が四杯するように変更する

require ‘racc/cparse’ -> require ‘xracc/cparse’

2.Raccのデバッグ機能を用いるため、デバッグ用の出力を行う、デバッグ用パーザを生成します。

TECSジェネレータのMakefileにはデバッグ用パーザを生成する定義がありますが、通常のターゲットでは生成されません。そのため、以下のようにターゲットを指定します。

make yydebug

3.問題が発生するテストケースのCDLファイルが存在するディレクトリに移動し、TECSジェネレータ(tecsgen)のオプション-yを指定して実行する。

tecsgen -y error-7.idl  2>&1 | tee  error-7-2.txt

オプション-yはTECSジェネレータにRaccのデバッグ用パーザを読み込むことを指定します。

また、デバッグがしやすいように、~/lib/ruby/racc/parser.rbにデバッグ用出力を追加しておきます.

このようしてTECSジェネレータを実行させて見ました.

結果は以下のとおりです.

1) tok=CELLTYPE
[ 0 45 ]
2) tok=IDENTIFIER
[ 0 45 101 ]
reduce  IDENTIFIER(2) –> celltype_name(214)
[ 0 45 102 ]
3) tok={
[ 0 45 102 149 ]
4) tok=}
[ 0 45 102 149 214 ]
reduce  “}”(76) –> celltype_statement(219)
[ 0 45 102 149 229 ]
reduce  celltype_statement(219) –> specified_celltype_statement(218)
[ 0 45 102 149 228 ]
reduce  specified_celltype_statement(218) –> celltype_statement_list(215)
[ 0 45 102 149 223 ]
6) tok=;
[ 0 45 102 149 223 214 ]
7) tok=nil
[ 0 45 102 149 223 214 ]

(これ以降、以下の部分の繰り返し)

reduce  $end(0) –> celltype_statement(219)
[ 0 45 102 149 223 229 ]
reduce  celltype_statement(219) –> specified_celltype_statement(218)
[ 0 45 102 149 223 347 ]
reduce  celltype_statement_list(215) specified_celltype_statement(218) –> celltype_statement_list(215)
[ 0 45 102 149 223 ]
shift   $end
[ 0 45 102 149 223 214 ]
error-7.cdlは文法エラーの場合のテストケースです。

本来トークン3とトークン4の間にセルタイプの定義が存在すべきですが、それがない場合のテストをするものです。

ですから、トークン3の次にトークン4が来た時点で構文エラーになるべきはずです。

しかし、逆にトークン4をセルタイプの定義と(パーザが)判断しているため、その後のトークン(また、ファイルの終わりに到達しても)が来ても無限ルールに陥ってしまっているのではないでしょうか。

racc/parserとrac/cparseの違いは、まだ調べていません。

同じ文法テーブルを使用しているなら、racc/cparseでも無限ルールに陥っても不思議ではありません.

現段階の仮説の一つは、racc/cparseが(パーザの)入力の終わりを特別扱いして、処理を打ちきっているのではないかいうことです。

でもこの仮説が真の場合でも、racc/cparseの方がが予期せぬ入力に対して柔軟な対応をしてくれるということでしかありません。

私の見る限り、racc/parserは、文法テーブルの指定通りに動作してると思います。