« [minipy] パーサーを作ってみる その1 | Main | カーニハン先生のありがたいお言葉 »

2008.02.06

[minipy] 繰り返しの実装

日記を書く[・ _ゝ・]はやみずさんから

> 演習の課題提出のあと、春休みに適当に整理してCodeReposにコミットする予定。
これは期待。

なんとか、HOPの作法にのって、catとaltが出来た。
catは、今あるパーサを組み合わせて長いパーサを返す。

eoi = parser.end_of_input() # end of input (EOF) にマッチするパーサ
nl = parser.lookfor('TOK_NEWLINE') # 改行にマッチするパーサ

nl_eoi = parser.cat('nl_eoi', [nl, eoi])
とすると、改行 + EOFにマッチしたとき成功する。

nl_eoi = parser.alt('nl_eoi', [nl, eoi])
とすると、改行もしくは、EOFにマッチしたとき成功する。
基本的には、この連結(cat)と選択(alt)で再帰していけば良いはず。

次の部品が、任意の繰り返しのアスタリスクだ。
#file_input ::= (NEWLINE | statement)* EOF
#a_expr ::= "integer" ( "+" "integer" )*

上は簡単で0回以上の繰り返しの後、EOFが来れば成功だから終了条件が分かる。
下がちょっと難しい、1回でもintegerに入ってしまうと、終わりの条件をどうして良いのか分からない。

HOPの繰り返しの実装star()を見てみて納得。

nothing → トークンを消費せず、何でもマッチし、常に成功を返す。

こういうパーサをつくって、自分自身と nothingの選択にすればよさそう。で自分自身を先にパースしに行って失敗したとき(*が終了するとき)、nothingにマッチしてパースを完了する。このとき、トークンは消費されない。成功したときは、また自分自身を呼び出してパースをするから、繰り返しを実現できる。なるほど。

だんだん、Higher-order Perlが僕のバイブルになってきた。

|

« [minipy] パーサーを作ってみる その1 | Main | カーニハン先生のありがたいお言葉 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/40017430

Listed below are links to weblogs that reference [minipy] 繰り返しの実装:

« [minipy] パーサーを作ってみる その1 | Main | カーニハン先生のありがたいお言葉 »