Tociyuki::Diary

■[Perl][PEG]Perl-5.14 で解析表現文法

先読み機能付き左選択肢優先の正規表現用 NFA にプッシュダウン・スタックをつけてリエントラントに書き直し、欲張りマッチングの後戻りバックトラッキングを止めにすると、そのままwikipedia:解析表現文法 (Parsing Expression Grammar, PEG と略す) を解釈できるオートマトンになります。

さて、Perl は 5.8 の頃から既にバックトラック抑制機能をもっており、さらに 5.14 の組み込みエンジンは解析表現埋め込みの Perl 実行文含めてリエントラントに動くように書き直されたものになっています。ということで、Perl-5.14 なら PEG をそのまま正規表現感覚で実行可能になっているというわけです。PEG は正規表現にかなり近い記法ではあるのですけど、それでも慣れ親しんだ正規表現の記法そのままで PEG できるのは素晴らしく、さすがに、まだ CPAN モジュールには投入するのは避けていますけど、私の個人用途のスクリプトで使いまくっています。

一つだけ、気をつけないといけないのは、PEG の S* 等はすべて後戻りバックトラックなしの欲張りマッチングなので、Perl-5.14 以降で PEG するには (?>S*) のようにバックトラックを明示的に抑制する必要があります。フラグで一律抑制できるようになると便利でしょうに。また、今のところ、解析表現中の実行文で使う変数は our にしておいた方が無難であるとドキュメントに記載があるので、従っておいた方が良いみたいです。

⇒ `perldoc perlre`

"(?{ code })"
   WARNING: Use of lexical ("my") variables in these blocks is
   broken. The result is unpredictable and will make perl
   unstable. The workaround is to use global ("our") variables.

実例として、中置記法の四則演算を逆ポーランド記法に変換する Perl スクリプトを書いてみます。構文中のコメントには PEG を書いておきました。PEG をそのまま正規表現の構文に置き換えていくだけです。

use 5.014;

our $rpn = [];
my $expr = qr{
    (?&additive)
    (?(DEFINE)
        # additive <- multitive ([+-] multitive)*
        (?<additive>
            (?>(?&multitive) (?:([+-]) (?&multitive) (?{ push $rpn, $^N }))*) )
        # multitive <- primary ([*/] primary)*
        (?<multitive>
            (?>(?&primary) (?:([*/]) (?&primary)     (?{ push $rpn, $^N }))*) )
        # primary <- [0-9]+ / [(] additive [)]
        (?<primary>
            (?>([0-9]+)(?{ push $rpn, $^N }) | [(] (?&additive) [)]) )
    )
}msx;

my $src = '2*(3+4*(5+6))+7';
if ($src =~ m/\A($expr)\z/msx) {
    say $1, ' -> ', join q( ), @{$rpn}; #=> '2*(3+4*(5+6))+7 -> 2 3 4 5 6 + * + * 7 +'
}

(はてなダイアリーのシンタックス・ハイライトは Perl の拡張解析表現未対応で奇妙な配色になり読みにくくなっていたので、手打ちで修正しておきました)

Permalink | コメント(0) | トラックバック(0) | 23:02