人気ブログランキング | 話題のタグを見る

PEG と 文脈自由文法の違い

PEG (Parsing Expression Grammar) も 文脈自由文法もプログラム言語の文法を定義する方法だ。おまけに、どちらも再帰下降構文解析という手法で実装することができるので、一体どこが違うのかが分り難い。

そこで、原点に返って構文解析とはどのようなことをするのかを考えてみよう。プログラムのソースファイルに書き込まれているプログラムは単なる文字コードの並びが延々とづづいているだけだ。アルファベットを延々と書き並べられた紙のテープを渡されて解読しなさいといわれているようなものだ。

これでは取り付く島がないのでどうするかというと、このテープを単語などのまとまりごとに、小さく切っていく。この作業をしても単に単語が順番に並んでいるだけでは、意味不明だ。この単語の並びを関連ある物ごとに並べたり、関連性の階層を調べたりして、単語どうしの関連性の構造を見つけなければならない。この木構造が見つかってはじめて、それをプログラムとして認識できるようになるのだ。

まずはじめに、この単語(トークン)の分析の仕方にもいろいろある。頭から順番にそのトークンが来た場合に次にはどのようなトークンがくる可能性があるのかを次々にしらべて、パターンマッチを行う方法がある。ボトムアップで構文を分析する方法だ。

もうひとつは、プログラムは、複数の文でできており、複数の文は特定の順序に並んだ単語や記号からなっており... というふうに、プログラムの構造は大体決まっているので、それにあわせて予想される単語を探していくという予言的方法だ。これをプログラムに実装すると再帰下降法というプログラムの方法になってくる。この方法では、こうあるべきだというパターンを予想して分析するので、トップダウンの分析法になる。PEGも文脈自由文法もこの再帰下降法でプログラムすることが可能だ。

ただ、PEGの再帰下降法と、文脈自由法の再帰下降法は少し違っている。文脈自由法の場合は、紙テープを一定のルールで先に切っておいてから、その断片についてパターンマッチを行っていく。したがって、与えられた紙テープはまずスキャナというプログラムを使ってトークンに切り分けなければならない。そのときに切り分ける道具となるのが正規表現によるパターンマッチだ。したがって、正規表現であらわせないパターンはトークンにすることができない。

それと違って、PEGの場合は、最初にトークンに分けるようなことをせず、紙テープのまま紙テープの頭の部分から、どのような単語や記号が来るべきなのかを調べる。調べてパターンがマッチしていれば、その部分の文字列は消費されて、紙テープから切り取られてしまう。そうして少し短くなった紙テープについてまた必要な情報を探すという動作をする。したがって、正規表現だけに頼ってトークンに分けるようなことはしないので、正規表現では表現できないパターンも探すことができるのだ。

つまり、PEGと文脈自由法の決定的な違いはスキャナがPEGではいらないし、スキャナの特性による制限を受けないということだ。

また、紙テープの先頭で、あるトークンを認識したとしてもそのトークンがどのような意味を持っているのかは、たとえば変数名なのか関数名なのかなど、次にくる文字情報を先読みしなければ分らない。従来の方法では、すでに、トークンに切り分けられてしまっているので、せいぜいトークンをひとつ先に読んで判断するくらいしか実質的な意味はない。しかし、PEGではトークンに切り分けていないので、先読みする文字やトークンの情報はひとつに限らず、理論上は無限に探索できる。

このパターンの先読みにつかっているのが、PEGの syntactic predicate (述語)だ。これはどういうものかというと、文字のパターン e の先頭につける記号で、& と ! がある。これが、パターン e の先頭について &e となっていると、紙テープの文字列は先頭からパターンマッチが試されるが、マッチした場合にマッチしたという情報を表す真値が返されるものの、マッチした部分の文字列の消費は行われない。つまり先読みして e というパターンがあることを見つけることができるが、文字列そのものには影響しない。!e の場合は紙テープの先頭に e というパターンがないということを知ることができる。

この syntactic predicate がなぜうれしいかというと、たとえば、文字列リテラルのパターンを表記するのに次のように記述することができる。

['] (!['] .)* [']

これはどういうことかというと、先頭にシングルクォートがあり、真ん中にはシングルクォート以外のキャラクタが0回以上あり、末尾にシングルクォートがあるパターンということになる。問題は上の表記で、!['] . がどうしてシングルクォート以外の一文字になるかということだが、!['] は確かにパターンマッチは行うが文字を消費しないので、あらかじめ一文字がシングルクォートではないということだけを検査していることになる。したがって、次の . までは実質的な文字の読み込みは行われていない。そうして、続く . は一文字を消費するので紙テープの端から一文字が切り取られ文字列の分析がひとつ先にすすめられることになる。したがって、シングルクォートではない一文字というパターンが記述できていることになる。

このように、PEGの文脈自由法と異なる第一の点は、先読み情報を文字の順序情報の中に統一的に含ませることができるということだ。

PEGと文脈自由法の違いの第二の点は prioritized choice (優先度のついた選択)だ。文脈自由法では、a b | a と a | a b は同じ意味を持っている。したがって 'abc' という文字列が、ab とマッチしているのか、a とマッチしているのか判別が難しいことがある。いわゆる衝突という状態だ。一方、PEGの場合はこのような選択は優先順位をつけられており、 a b / a の場合、ab のマッチだけが認められ、a とはマッチしない。したがって、曖昧さが発生せず衝突もおこらない。このことによって、文法を実装するときに衝突を回避するための余計なプログラムが必要でなくなるのだ。

したがって、PEGと文脈自由法との違いは、同じ再帰下降構文解析の実装となるものの、

1. スキャナを実装しなくても良い
2. 先読み情報の処理を文法に記述できる。(syntactic predicate)
3. 衝突が発生しない。(prioritized choice)

という3つの点で異なることが分る。

PEGの規則は簡単なのでプログラム言語に実装されていれば、言語設計者だけではなく、ユーザにもメリットがある。たとえば、Rubyなどの言語にPEGが実装されていれば、ユーザが自分のプログラムの中で簡単にミニ言語を設計して利用することができる。また、文字列のパターンマッチの場合も正規表現では不可能だった入れ子構造のパターンなども楽に表現できる。

次期 Ruby の仕様に、ファーストクラスの関数と、リスト構造の組み込みクラスと、PEGが組み込まれたらうれしくなる人は多いのではないだろうか。
by tnomura9 | 2008-04-28 00:50 | Ruby | Comments(0)
<< 原点に帰る 高階関数型 PEG パーサ >>