« 今日の日記 | Main | myminicity »

2007.12.15

[HOP]Parsingの章終了

ようやく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お勧めですよ。

残りあと一章!

|

« 今日の日記 | Main | myminicity »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

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

Listed below are links to weblogs that reference [HOP]Parsingの章終了:

« 今日の日記 | Main | myminicity »