2007年04月24日 18:00 [Edit]

perl - parser書くならgoto

しかし、本当の本当の本番はこちらだったりする。

camel 404 Blog Not Found:perl - POO と goto
Perl 5のgotoは、仕組みを理解した上で使いどころを誤らなければかのごとく強力なのである。

前回の例では、それでも"One of many ways to do it"で、「知らなくても困らない」レベルのものであった。しかし、今回の例は、gotoがなければ本当にきつい。

以下の例を考えてみよう。

入力:
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))
出力:
[['define',['fact','n'],['if',['=','n','1'],'1',['*','n',['fact',['-','n','1']]]]]]

そう。parserである。ここでは、atomとS式だけを考える。その程度の制約においてすら、こういった括弧が混じったものをparseするのはかなりきつい。

まずは普通に書いてみる。

sub parse_i {
    my $str = shift;
    my $tree = [];
    while (
        $str =~ s{\A             # start of the string
                    \s*          # spaces
                    (  [\(]      # open paren
                     | [^\s\(]+  # or atom
                    )
                   }{}x
      )
    {
        my $token;
        if ( $1 eq '(' ) {
            my $nest = 1;
            my $pos;
            for ( $pos = 0 ; $pos < length($str) ; $pos++ ) {
                my $c = substr( $str, $pos, 1 );
                $nest +=
                    $c eq '(' ? 1
                  : $c eq ')' ? -1
                  :             0;
                last unless $nest;
            }
            my $paren = substr( $str, 0, $pos + 1, '' );
            substr( $paren, -1, 1, '' );
            $token = parse_i($paren);

        }
        else {
            $token = $1;
        }
        push @$tree, $token;
    }
    return $tree;
}

要は頭から文字列を「食べていく」わけだが、括弧の処理が大変なことがわかる。括弧があったら括弧が閉じるまで文字列を呼んで、その部分を再帰的にparseするわけだが、なんともめんどくさく読みにくい。

「それってs///eで」という声が聞こえてきそうだが、ところが本来の正規表現というのは、原理的にネストした括弧のマッチは出来ないのだ。

'(* n (fact (- n 1)))' =~ /\((.*)\)/;  # #1 = '* n (fact (- n 1)))'
'(* n (fact (- n 1)))' =~ /\((.*?)\)/; # $1 = '* n (fact (- n 1)'
                                       # need '* n (fact (- n 1))'

実は、Perl 5では5.6より「正規でない」正規表現で、この括弧のマッチが可能になってはいる。それを使って書き直すと、こうなる。


sub parse_r {
    my $str = shift;
    my $tree = [];
    # see perldoc perlre
    my $re_paren;
    $re_paren = qr{ \(                    
                    (?:
                     (?>[^\(\)]+)
                     | (??{ $re_paren })
                    )*
                    \)
                  }x;
    # or just 
    # use Regexp::Common qw/balanced/; 
    # my $re_paren = $RE{balanced}{-parens=>'()'};
    $str =~ s{( 
               $re_paren     # paren
               | [^\s\(\)]+  # or atom
              )}{
                  my $token = substr($1, 0, 1) eq '('  
                      ? parse_r(substr($1,1,-1)) : $1;
                  push @$tree, $token;
                  ''
              }gex;
    return $tree;
}

たしかにs///eで出来た。が、こういう「非正規表現」は正規表現フェチを自認する私でもちょっとごめんだし、そもそもPerl 5以外でこの正規表現が動くかはあやしい。

ところが、gotoを上手に使うと、コードがこれほどにもすっきりするのだ。

sub _parse_g {
    return $_[1] unless $_[0];
    $_[0] =~ s{\A               # start of the string
               \s*              # spaces
               (  [\(\)]        # paren
                  | [^\s\(\)]+  # or atom
               )
              }{}x;
    return $_[1] if $1 eq ')';
    my $token =
      $1 eq '('
      ? _parse_g( $_[0], [] )
      : $1;
    push @{ $_[1] }, $token;
    goto &_parse_g;
}
sub parse_g{ my $str = shift; _parse_g($str, []) }

みてのとおり、このコードにはループすらない。「頭から文字列を食って消化する」というparserの役割がコードからもきちんと見て取れる。関数の中ではあくまでtokenを一つだけ処理して、文字列が残っていればもう一度自分を呼び、残っていなければ結果を返す。括弧を処理する時にも、単純再帰ではなく$_[0]を渡しているので、文字列は「継続」している。よって不要な後戻りがない。

コードがわかりやすくなっただけでもありがたいのに、処理速度も向上している。ここで例題を解いた場合のbenchmarkを示す。

         Rate   Iter Regexp   Goto
Iter   3664/s     --   -23%   -55%
Regexp 4769/s    30%     --   -42%
Goto   8217/s   124%    72%     --

PerlでParserを書きたいという人は、このテクニックを是非覚えておいてもらいたい。早く書けるだけではなく速く動くのだから。

Dan the Happy-Go-Luck Perl Monger


この記事へのトラックバックURL

この記事へのトラックバック
末尾再帰の速さ. (S式のパースのつづき) トラックバックおくってみたらコメントが続いてるのに気付いてうぐぅ。 で、ついでに末尾再帰でどのくらい変わるのかも試してみました.
http://nikki.hio.jp/?date=20070425【ひおにっき】at 2007年04月25日 19:07
[Program] S式のパース <p> <a href="http://blog.livedoor.jp/dankogai/archives/50816517.html">perl - parser書くならgoto</a> のみて, なんかどれもごちゃっとしてるきがしたので書いてみた. </p> <pre>sub parse_my { my $str = shift; my $tree = []; my @stack ...
http://nikki.hio.jp/?date=20070424【ひおにっき】at 2007年04月25日 15:30
この記事へのコメント
「まずは普通に書いてみる。」の例が恣意的というか、ぜんぜん普通じゃないです。
ループで書くなら、ネストレベルなんてのは状態として持つでしょ。
上の03:06のコメントのコードに一票。

gotoネタを書くために「gotoがなければ本当にきつい」例をでっちあげないといけないとは、アルファブロガーってのは大変ですね…。
Posted by   at 2007年04月26日 15:27
なかにしさん
> goto使えば末尾再帰の最適化ができるよ。ってことでしょうか?
まあ結局のところそういうことですね。
Dan the Tail Recurser
Posted by at 2007年04月25日 13:23
goto使えば末尾再帰の最適化ができるよ。ってことでしょうか?
Posted by なかにし at 2007年04月25日 10:20
おまけで、本当に一度も再帰を使わないコードです。ではまた。
sub parse {
my $str=shift;
my @tree=[];
my $sp=0;
while(
$str=~s{ ^\s* (
[(]|
[)]|
[^\s()]+
)}{}x
){
if($1 eq ')'){ push(@{$tree[--$sp]},pop(@tree)); }
elsif($1 eq '('){ $sp++; }
else{ push(@{$tree[$sp]},$1); }
}
return @tree;
}
Posted by at 2007年04月24日 22:11 at 2007年04月25日 03:06
ついでに、
my $token =
$1 eq '('
? _parse_g( $_[0], [] ) # <---- !?
: $1;
この処理が再帰に見えるのは置いておくとして、そのgotoだとstaticな変数を使った再帰(要はただのループ)と等価ですよね。関数の最初からgotoまでループにすればやっぱりgotoを使用する必要ない気が。
Posted by 2007年04月24日 22:11 at 2007年04月25日 01:23
ついでに、
my $token =
$1 eq '('
? _parse_g( $_[0], [] ) # <---- !?
: $1;
この処理が再帰に見えるのは置いておくとして、そのgotoだとstaticな変数を使った再帰(要はただのループ)と等価ですよね。関数の最初からgotoまでループにすればやっぱりgotoを使用する必要ない気が。
Posted by at 2007年04月24日 22:11 at 2007年04月25日 01:22
言葉が足りなくてすみません、「どうしてスタックじゃないの?」は一番上のソースについてです。で、S式の解析はスタックと再帰を使って、gotoを使わずに
sub parse {
my $str=shift;
my $tree=[];
while(
$$str=~s{ ^\s* (
[(]|
[)]|
[^\s()]+
)}{}x
){
if($1 eq ')'){ return $tree; }
elsif($1 eq '('){ push(@$tree,&parse(\$$str));}
else{ push(@$tree,$1); }
}
return $tree;
}
と書けます。
Posted by 2007年04月24日 22:11 at 2007年04月25日 01:19
""さん、
よく吟味していただければお分かりだと思うのですが、実は、goto版は「再帰しないでスタックする」と等価な構造になっています。
Dan the Parser Generator
Posted by at 2007年04月24日 23:16
S式なら先読みの必要もないから、単に頭から一個ずつトークン切り出してスタックすればわざわざ閉じ括弧まで読んで再帰する必要ない気がするんですが、それじゃだめなんですか?
Posted by   at 2007年04月24日 22:11