Parsing Expression Grammar
Parsing Expression Grammar (PEG, Parsing Expression Grammar) は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。
PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。
このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、一方、自然言語の多義性を、そのまま複数の構文木が可能である、という形で形式化するのには向かない。
形式的には、PEGは次の要素からなる。
"P" に含まれる各規則は、"A" ← "e" という形式であり、"A" は非終端記号、"e" は、次のように構築される記号およびメタ記号の列である。前述のように、文脈自由文法における「どれかを選択」という意味の「 | 」の代わりに、「順番に試す」という意味の「 / 」を使うことが特徴である。
文脈自由文法や他の生成文法とは異なり、PEGでは、ある非終端記号が左辺にくる規則は常に1つしか存在しない。すなわち、規則群は「定義」であり、各非終端記号には1つしか定義が存在しない。
PEGにおける各非終端記号は、ある意味で再帰下降構文解析における構文解析関数を表現しており、それに対応するparsing expressionはその関数のコードであると解釈できる。各構文解析関数は、引数として入力文字列をとり、以下のいずれかの結果を返す。非終端記号は入力を全く消費しなくとも成功と見なされる場合があり、単に返される結果だけで失敗と区別される。
1つの終端記号からなるatomic parsing expressionは、入力文字列の先頭の文字と一致した場合に成功し、その入力文字を消費する。さもなくば、そのparsing expressionは失敗の結果を返す。空文字列だけからなるatomic parsing expressionは、入力を消費せずに常に成功と見なされる。非終端記号 "A" からなるatomic parsing expressionは、非終端関数 "A" の再帰呼び出しを表している。
並び "e" "e" は、まず "e" を呼び出し、"e" が成功なら続いて "e" を "e" が消費した文字列を除いた入力文字列を引数として呼び出し、その結果を全体の結果として返す。"e" か "e" のいずれかが失敗した場合、並び "e" "e" 全体が失敗となる。
選択 "e" / "e" は、まず "e" を呼び出し、"e" が成功ならそれを結果として即座に返す。あるいは "e" が失敗なら入力文字列を "e" を呼び出す前の元の位置にバックトラッキングして "e" を呼び出し、"e" の結果を返す。
ゼロ個以上、1個以上、省略可能の場合、それぞれゼロ個以上、1個以上、ゼロ個または1個の "e" が続くものとして入力を消費する。しかし、文脈自由文法や正規表現とは異なり、PEGにおける繰り返しは常に貪欲であり、マッチし続ける限り入力を消費し、バックトラックしない。正規表現では貪欲にマッチするものの、失敗するともっと短いマッチを試すためにバックトラックする。例えば、a* という表現は 'a' が連続する限り入力文字列を消費し、(a* a) という表現は最初の (a*) が全ての 'a' の並びを消費してしまうため、最後の (a) にマッチする 'a' がなくなるので、常に失敗する。
AND predicateとNOT predicateはsyntactic predicateである。&"e" という表現は "e" をまず呼び出して、それが成功した場合には成功し、失敗した場合には失敗する。しかし、どちらの場合も「入力文字列を消費しない」。逆に !"e" という表現は "e" が失敗した場合には成功し、成功した場合には失敗する。こちらも入力文字列は消費しない。"e" には任意の複雑な表現が当てはまるので、これらは強力な先読み機能となる。
以下は、非負整数についての四則演算を行う数式を認識するPEGである。
この例では、終端記号は文字であり、シングルクオートで囲んで codice_1 や codice_2 のように表されている。範囲 codice_3 も10種類の数字 0 から 9 を表している。このような範囲表現は正規表現でも用いられている。非終端記号は各規則の左辺に現れている "Value", "Product", "Sum", "Expr" である。
次の例ではシングルクオートを省略して読みやすくしている。小文字は終端記号、大文字のイタリック体が非終端記号である。実際のPEGパーサでは、小文字で表される終端記号は引用記号で囲む必要がある。
parsing expression (a/b)* は任意の長さの a および b の並びにマッチする。規則 "S" ← a "S"? b は単純な文脈自由マッチング言語 formula_1 を表している。以下のPEGは文脈自由でない言語 formula_2 を表している。
次の例は、再帰的規則でC言語風の if/then/else 文にマッチするものである。"else" 節は省略可能で、'/' オペレータの暗黙の優先順位付けによって常に最も内側の "if" と対応付けられる。文脈自由文法では、else の対応関係は曖昧となる。
foo &(bar) というparsing expressionは、"bar" というテキストが後に続く場合のみ "foo" というテキストにマッチし消費する。foo !(bar) というparsing expressionは、"bar" というテキストが後に続かない場合のみ "foo" というテキストにマッチし消費する。!(a+ b) a という表現は、'a' の任意の長さの並びに 'b' が続く形式でない場合のみ 'a' にマッチする。
以下の再帰的規則はPascal風の (* このように (* 入れ子に *) できる *) コメントの構文にマッチするものである。コメント記号はPEGのオペレータと区別するためにダブルクオートで囲んでいる。
PEGはそのまま再帰下降構文解析器に変換可能である。先読みが無制限に可能であるため、最悪の場合指数関数時間かかる。
解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにすると、任意のPEGを Packrat Parser に変換でき、メモリ領域を余分に必要とするものの、常に線形時間で動作する。
Packrat Parser は再帰下降構文解析器と構造的にはよく似た構文解析器である。ただし、Packrat Parser は相互再帰構文解析関数を呼び出す度に途中結果をメモ化する。このメモ化によって Packrat Parser は、多くの文脈自由文法と任意のPEG（文脈自由でない場合も含む）を線形時間で構文解析できるようになっている。
PEGは正規表現より強力であり、よい代替手法となる。例えば、正規表現は再帰的ではないため本質的に括弧の対応付けができないが、PEGでは可能である。
PEGは上述のように Packrat Parser を使えば線形時間で構文解析可能である。
文脈自由文法で表される言語の構文解析器（例えばLR法）は、事前に入力を字句解析しておく必要がある。字句解析は線形時間内で先読みしつつ構文解析するにあたって必要となるものである。しかしPEGは事前に字句解析する必要はなく、字句解析規則を他の構文規則と同じように記述できる。
文脈自由文法は多くの場合本質的に曖昧であり、曖昧でない言語を記述する場合でもそのようになる傾向がある。C、C++、Javaにおける else の曖昧さの問題はその例である。通常、このような曖昧さは文法以外の規則を適用することで解決される。PEGでは、優先順位が厳密に決まるため、そのような曖昧さは発生しない。
PEGは、文字列上で位置を変更せずにある規則が自分自身を呼び出すという左再帰規則を表現できない。例えば、上述の数式の文法では、次のような規則としたほうが自然である。
この場合、Expr とマッチするかを判定するには、まず Product とマッチするかを判定する必要があり、Product とマッチするかを判定するには、Expr とマッチするかを判定しなければならない。これは不可能である（循環定義になっていて完了しない）。
しかし、左再帰規則は常に左再帰を使わない形式で書き換え可能である。例えば、左再帰規則で任意長の繰り返しを表すと（文脈自由文法では）次のようになる。
PEGではこれを + オペレータを使って書き換え可能である。
PEGパーサ（多くはPackratパーサ）を生成するパーサジェネレータやパーサコンビネータライブラリなどを以下に示す。