先読み機能付き左選択肢優先の正規表現用 NFA にプッシュダウン・スタックをつけてリエントラントに書き直し、欲張りマッチングの後戻りバックトラッキングを止めにすると、そのままwikipedia:解析表現文法 (Parsing Expression Grammar, PEG と略す) を解釈できるオートマトンになります。 さて、Perl は 5.8 の頃から既にバックトラック抑制機能をもっており、さらに 5.14 の組み込みエンジンは解析表現埋め込みの Perl 実行文含めてリエントラントに動くように書き直されたものになっています。ということで、Perl-5.14 なら PEG をそのまま正規表現感覚で実行可能になっているというわけです。PEG は正規表現にかなり近い記法ではあるのですけど、それでも慣れ親しんだ正規表現の記法そのままで PEG できるのは素晴らしく、さすがに、まだ CPAN