tokuhirom's Blog

Perl で簡単にパーザを書く

パーザを書こうという場合、Parse::RecDecsent のようなモジュールを使うのが一般的だが、Perl5 の正規表現は強力すぎるため、そんなものに頼らなくても超絶簡単にパーザを実装することが可能だ。

以下に、四則演算のパーザを示す。

use 5.018000;

package Calc {
    use Carp ();

    sub parse {
        local $_ = $_[1];

        _parse_expr();
    }

    sub err {
        my ($msg) = @_;
        my $ret = join('',
            $_, "\n",
            (" " x pos()) . "^\n",
            $msg, "\n",
        );
        Carp::croak $ret;
    }

    sub _parse_expr {
        my @nodes;
        until (/\G\s*\z/gc) {
            my $m = _parse_add()
                or do {
                err "Syntax error";
            };
            push @nodes, $m;
        }
        return ['expr', @nodes];
    }

    sub _parse_add {
        my $mul = _parse_mul()
            or return undef;
        while (m{\G\s*([+\-])}gc) {
            my $op = $1;
            my $lhs = _parse_mul()
                or die "Cannot parse mul after '$op' : " . pos();
            $mul = [$op, $mul, $lhs];
        }
        return $mul;
    }

    sub _parse_mul {
        my $node = _parse_term()
            or return undef;
        while (m{\G\s*([*/])}gc) {
            my $op = $1;
            my $lhs = _parse_term()
                or die "Cannot parse expr after '$op' : " . pos();
            $node = [$op, $node, $lhs];
        }
        return $node;
    }

    sub _parse_term {
        if (/\G\s*([0-9]+)/gc) {
            return $1;
        } elsif (/\G\s*\(/gc) {
            my $expr = _parse_add();
            /\G\s*\)/gc
                or err "No closing paren after opening paren.";
            return $expr;
        }
        return undef;
    }
}

my $node = Calc->parse('1+2*3-(4+2)*5');
use Data::Dumper; warn Dumper($node);

ポイントは /\G/gc という正規表現と pos() 関数だ。両方とも普段あまり使うことがないツールだが、とても強力である。

//g の g オプションは、みなさんご存知のとおり、マッチするすべてのものにマッチするやつ。//c は、マッチに失敗したときにマッチ位置をリセットしないようにするオプション。

pos() 関数は、//g がどこまでいったかを教えてくれる。これによりエラー報告が用意となる。また、pos() 関数により、マッチ位置を再設定することもできるので、バックトラックも可能だ。

この方法に慣れると、パーザを書くのが超絶楽になるし、Parse::RecDecsent の謎記法やデバッグの困難さに苦しめられたあの日々はいったいなんだったのだろう、という気分になる。

なお、JSON::Tiny がこの方法で実装されているので参考にするとよい。