Parsing Expression Grammar
PEGにおける各非終端記号は、ある意味で再帰下降構文解析における構文解析関数を表現しており、それに対応するparsing expressionはその関数のコードであると解釈できる。各構文解析関数は、引数として入力文字列をとり、以下のいずれかの結果を返す。
「成功」- 引数として与えられた文字列からいくつかの文字を「消費」するなどした場合
「失敗」- 入力を全く消費できなかった場合
非終端記号は入力を全く消費しなくとも成功と見なされる場合があり、単に返される結果だけで失敗と区別される。
1つの終端記号からなるatomic parsing expressionは、入力文字列の先頭の文字と一致した場合に成功し、その入力文字を消費する。さもなくば、そのparsing expressionは失敗の結果を返す。空文字列だけからなるatomic parsing expressionは、入力を消費せずに常に成功と見なされる。非終端記号 A からなるatomic parsing expressionは、非終端関数 A の再帰呼び出しを表している。
並び e1 e2 は、まず e1 を呼び出し、e1 が成功なら続いて e2 を e1 が消費した文字列を除いた入力文字列を引数として呼び出し、その結果を全体の結果として返す。e1 か e2 のいずれかが失敗した場合、並び e1 e2 全体が失敗となる。
選択 e1 / e2 は、まず e1 を呼び出し、e1 が成功ならそれを結果として即座に返す。あるいは e1 が失敗なら入力文字列を e1 を呼び出す前の元の位置にバックトラッキングして e2 を呼び出し、e2 の結果を返す。
ゼロ個以上、1個以上、省略可能の場合、それぞれゼロ個以上、1個以上、ゼロ個または1個の e が続くものとして入力を消費する。PEGにおける繰り返しは常に貪欲でありマッチし続ける限り入力を消費するが、それだけではなく、正規表現とは異なりバックトラックしない(正規表現では貪欲にマッチするものの、失敗するともっと短いマッチを試すためにバックトラックする)。例えば、a* という表現は 'a' が連続する限り入力文字列を消費し、(a* a) という表現は最初の (a*) が全ての 'a' の並びを消費してしまうため、最後の (a) にマッチする 'a' がなくなるので、常に失敗する。
AND predicateとNOT predicateはsyntactic predicateである。&e という表現は e をまず呼び出して、それが成功した場合には成功し、失敗した場合には失敗する。しかし、どちらの場合も「入力文字列を消費しない」。逆に !e という表現は e が失敗した場合には成功し、成功した場合には失敗する。こちらも入力文字列は消費しない。e には任意の複雑な表現が当てはまるので、これらは強力な先読み機能となる。
↑ "Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking" §3.1.1 pp.32〜33
↑ Ford, Bryan (2002年9月). “Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking”. Massachusetts Institute of Technology. 2007年7月27日閲覧。