PEGのボキャブラリー

前回に引き続き、解析表現文法(PEG)を見ていきたいと思います。あいまい性が無かったり、再帰降下型パーサーと相性が良いなどの特徴があるPEGなんですが、どうゆう中身になっているのでしょうか。

PEGは次のような要素で構成されます。各要素の英語名の後にここで使っている表記法を書いておきます:

  • 空文字(empty/()):入力ストリームから一文字も消費することなくパースを成功します。
  • 終端(terminal/小文字英数):物々しい名前がついてますが、要は実際にマッチしたい文字のことです。マッチしたときは対応した入力を消費して成功します。
  • 非終端(non-terminal/大文字英数):これは終端に対応するもので、パースしたいパターンにつけるレーベルのようなものです。
  • 順序(sequence/(e1,e2,e3,e4)):複数の要素を特定の順番にマッチさせるものです。全ての要素がマッチした場合は対応する入力を消費して成功します。そうでなければ一文字も消費せずに失敗します。
  • 選択(ordered choice/(e1/e2/e3/e4)):複数の要素の中から一つマッチするときに全体を成功させます。マッチに対応する入力は消費されます。PEGの選択で特徴的なことは必ず最初の要素から試行されることです。選択内の複数の要素がマッチする可能性があるときは最初のマッチが優先されます。
  • 繰り返し(Greedy Repetition/e*):これは指定された要素の0回以上の繰り返しです。つまりまったく出現しなくても成功することになります。PEGでの定義では繰り返しはマッチする全てを消費するということです。
  • 1回以上の繰り返し(Greedy Positive Repetition/e+):繰り返しとほぼ同じなのですが、最低1回はマッチしないと失敗を返します。sequenceとGreedy Repetitionを組み合わせれば
  • e+ = (e, e*)
  • と書くことができるわけですね。
  • 省略可能(optional/e?):マッチした場合は対応部分を消費して成功、マッチしなかった場合は入力を消費せずに成功します。
  • Followed By/&(e):うまい日本語が思いつかないのですが、後続の要素によってパターン全体を失敗させることができます。成功しても失敗しても入力は先読みされるだけで消費されません。
  • Not Followed By/!(e): これはFollowed Byの否定形ですね。


文献によるとPEGは正規表現の拡張版という位置づけとも捕らえられるようで、繰り返しや選択などは正規表現などにもありますね…しかしながら繰り返しや選択については振る舞いが厳格に定義されています。正規表現に無いものがFollowed ByやNot Followed Byあたりでしょうか…(正規表現をあまりちゃんと知っているわけではないのですが…)
シロート目にはPEGはLL(n)パーサーで解析可能な文法なように見えます。nがいくつかなるかはPEGで定義されている文法に依存しそうです。

試しにPEGで整数をパースするパターンを定義してみると:

NUMBER  =  (0/NONZERO)
NONZERO = (DIGIT, DIGIT0*)
DIGIT = (1/2/3/4/5/6/7/8/9)
DIGIT0 = (0/DIGIT)

といった感じでしょうか。CFGでは普通なようですが、正規表現とは違ってnon-terminalをつかってパターンを分割して定義できるのが便利ですね。

しかしながら、このパターンでは01などの文字列に対して最初の0だけとってパースを終了してしまいます。このような文字列をはじきたい場合はどうしたらよいでしょう?

NUMBER = (ZERO/NONZERO)
ZERO = 0!(DIGIT0)

のようにしてやれば、ZEROは0単独の場合にのみパースを成功するようになります。01などの場合は一文字も消費することなくパースは失敗します。

負の数をパースできるようにするためには、Optionalを使って:
NONZERO=-?(DIGIT,DIGIT0*)
とやってやればオッケイですね…

比較のためにCFGでやってみると:

NUMBER = (ZERO|NONZERO)
ZERO = 0
NONZERO=-,POSITIVE|POSITIVE
POSITIVE=DIGIT, DIGIT0S
DIGIT = 1|2|3|4|5|6|7|8|9
DIGIT0S = DIGIT0|DIGIT0, DIGIT0S
DIGIT0 = 0|DIGIT

特筆べき違いといえば、01をパースするときにCFG版のほうは失敗しないですね…0だけとって終了してしまいます。強制失敗させるような方策も無いので、CFGで01をはじく方法は無いのでしょうか?あとは、CFGがもともと生成文法であることが理由なのか、どこまでパースすれば終了なのかということに関する定義がはっきりしないような気がします。極端な話、1000をパースするのに1だけパースして止まってもCFGの定義からすれば何も契約違反をしていないような気がします。PEGでは文法の定義によって、1000の全ての桁をパースすることが保障されていますね…もっとも、CFGにも追加ルールを付け足して対処することはできそうですが…
もう一つ挙げるとすれば、CFGではパターンの繰り返しは再帰で表現されていますが、これはPEGの*や+と比べると、文法全体の見通しが悪くなるような気がします…再帰はPEGでも使われますが、あまり多用されると読みづらいですね…

次回はもうちょっと踏み込んで整数の四則演算をPEGパターンをやってみたいと思います。

ではでは。