なつたん

ようやくParsingの章を終了。手を動かす気力が無いので読んだだけです。

8.8 Backtracking Parsers
Perlで自力で継続をしながら、バックトラックをする話。

ソースはこんな感じで
sub lookfor {
　my $wanted = shift;
　my $value = shift || sub { $_[0] };
　my $u = shift;
　$wanted = [$wanted] unless ref $wanted;

　my $parser = parser {
　　my ($input, $continuation) = @_;
　　return unless defined $input;

　　my $next = head($input);
　　for my $i (0 .. $#$wanted) {
　　　next unless defined $wanted->[$i];
　　　return unless $wanted->[$i] eq $next->[$i];
　　}
　　my $wanted_value = $value->($next, $u);

　　# Try continuation
　　if (my ($v) = $continuation->(tail($input))) {
　　　return $wanted_value;
　　} else {
　　　return;
　　}
　};

　$N{$parser} = "[@$wanted]";
　return $parser;
}

SICPの継続の部分に構造は近い。引数に処理すべきリストと継続を渡し、成功／失敗によって自力で継続を呼び出すクロージャを返している。

同様にstreamを使ったparsingも簡単に説明。パースの選択肢がある時に、どちらかを選んで再帰していくのではなく、すべての選択肢を同時に計算していく。ここでStreamを使う。実用性はともかく発想は面白い。

8.9 Overloading
最後は、演算子のオーバーロードを使用してDSLっぽくする話。

この本で、ここまで書いてきたパーサーのソースがこれ。

$factor　　 = alternate(lookfor('INT'),
　　　　　　　T(
　　　　　　　　　　　　 concatenate(lookfor(['OP', '(']),
　　　　　　　　　　　　　　　　　　$Expression,
　　　　　　　　　　　　　　　　　　lookfor(['OP', ')'])),
　　　 　　　　sub {$_[1]})
　　　　　　　);

ちなみにlookforは、引数をパースするだけのクロージャを返し、concatenateは引数のクロージャを連結したクロージャを返す。Tは、クロージャと手続きを引数にして、パースに成功したときにある手続きを読んでから値を返すクロージャを返す。最後にalternateは、複数のクロージャを引数に選択的に実行していくクロージャを返します。もうわけわかんない。

BNFからはほど遠くなっているので、Perlのオーバーロードを使用することで、こんな風に書けます。

$factor = lookfor('INT')
　　　　| lookfor(['OP', '(']) - $Expression, lookfor(['OP', ')']
　　　　　　　　>> sub {$_[1]})
　　　　;

これで確かに読みやすくなる。

こういうのに興味がある人はHigher-Order Perlお勧めですよ。

残りあと一章！