書ける気がするけれども、実際のところはどうなのだろう。
PEGの定義と正規表現の機能
文脈自由文法（CFG）は、純粋な正規表現では表せない入れ子構造の文字列を表すことができる。だが正規表現の実装によっては、再帰が可能で入れ子構造に対応できるものがある。
CFGと似た感じのParsing Expression Grammar（PEG）についても、定義を見ていたら全て正規表現の機能で再現できるのではないかと思った。
| PEG | 正規表現 (Ruby) |
|---|---|
| 終端記号 | 1文字 |
| 非終端記号 | 利用のみ： /\g'expr'/定義： /(?'expr'expression)/
|
| 空文字列 | // |
| 連接 $e_1 e_2$ | /\g'e1'\g'e2'/ |
| 選択 $e_1 / e_2$ | /(?>\g'e1'|\g'e2')/ |
| 0回以上 $e*$ | /\g'expr'*+/ |
| 1回以上 $e+$ | /\g'expr'++/ |
| 省略可能 $e?$ | /\g'expr'?+/ |
| 肯定先読み $\&e$ | /(?=\g'expr')/ |
| 否定先読み $!e$ | /(?!\g'expr')/ |
PEGの特徴のひとつは「選択は最初にマッチしたものを結果とする」「繰り返しは常に貪欲」というバックトラック軽減なので、アトミックグループや絶対最大量指定子を使えば正規表現でも再現できるはず。先読みも正規表現にあるし、部分式呼び出し（再帰）でバッカス・ナウア記法みたいな書き方ができる。
非終端記号の定義の書き方
非終端記号の定義 /(?'expr'expression)/ は必ず同じ正規表現のどこかに書いておかなければならない。ただしこれもマッチの対象になってしまうため、本文のマッチを邪魔しない書き方が必要になる。それには以下のような方法がある。
-
/本文(?'expr1'expression1){0}(?'expr2'expression2){0}.../という風に空文字列化して連結しておく。（空文字列を表すパターンは必ずマッチが成功する） -
/本文|(?!)(?'expr1'expression1)(?'expr2'expression2).../という風に絶対にマッチしない選択を作ってその中に書く。 - 本文中に各定義が1回だけ現れるよう埋め込む。上のどちらかを作ってから変換すると楽。
例
文脈自由言語でない例としてよく出る $a^n b^n c^n$（$n \ge 1$）。
\begin{align}
S &\gets \&(A \:\: !b) \:\: a\!\!+ B \:\: !. \\
A &\gets a \:\: A? \:\: b \\
B &\gets b \:\: B? \:\: c
\end{align}
ほぼそのまま正規表現で表すことができる。空白を入れられるモードにして書くと読みやすい。
anbncn_regexp.rb
# 3つの正規表現は「非終端記号の定義の書き方」が異なるだけで同じ文字列にマッチする
regexp1 = /
\A (?= \g'A' (?! b)) a++ \g'B' \z
(?'A' a \g'A'?+ b){0}
(?'B' b \g'B'?+ c){0}
/x
regexp2 = /
\A (?= \g'A' (?! b)) a++ \g'B' \z
|(?!)
(?'A' a \g'A'?+ b)
(?'B' b \g'B'?+ c)
/x
regexp3 = /
\A (?= (?'A' a \g'A'?+ b) (?! b)) a++ (?'B' b \g'B'?+ c) \z
/x
# 1行入力するたびにマッチするかどうかを出力
while (str = gets)
str.chomp! # 末尾に改行文字があるとマッチしないので削除
p [regexp1 === str, regexp2 === str, regexp3 === str]
end
選択の動作が重要になるマッチに関してはいい例が出てこなかった。アトミックグループによってマッチしなくなる簡単な例を挙げておく。
ordered_choice.rb
p "abc".match(/(?:ab|a)c/) #=> #<MatchData "abc">
p "abc".match(/(?>ab|a)c/) #=> #<MatchData "abc">
p "abc".match(/(?:a|ab)c/) #=> #<MatchData "abc">
p "abc".match(/(?>a|ab)c/) #=> nil
使い道
PEGを使うべきところを無理に正規表現で代用するのは損するだけだが、正規表現のバックトラック抑制のヒントにはなると思う。
参考
- Parsing Expression Grammar - Wikipedia
- PEG基礎文法最速マスター - kmizuの日記
- 正規表現 (Ruby 2.0.0)
- 正規表現技術入門 最新エンジン実装と理論的背景