Parsing Expression Grammar

Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。

PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。

このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析に向いており、一方、自然言語の多義性を、そのまま複数の構文木が可能である、という形で形式化するのには向かない。

定義

形式的には、PEGは次の要素からなる。

P に含まれる各規則は、A ← e という形式であり、A は非終端記号、e は、次のように構築される記号およびメタ記号の列である。前述のように、文脈自由文法における「どれかを選択」という意味の「 | 」の代わりに、「順番に試す」という意味の「 / 」を使うことが特徴である。

  1. 「atomic parsing expression」は次のいずれかである。
    • 任意の終端記号
    • 任意の非終端記号
    • 空文字列 ε
  1. 任意の既存のparsing expressionを e, e1, e2 としたとき、以下のように構築されるものもparsing expressionである。
    • 並び: e1 e2
    • 選択: e1 / e2
    • ゼロ個以上: e*
    • 1個以上: e+
    • 省略可能: e?
    • AND predicate: &e
    • NOT predicate: !e

文脈自由文法や他の生成文法とは異なり、PEGでは、ある非終端記号が左辺にくる規則は常に1つしか存在しない。すなわち、規則群は「定義」であり、各非終端記号には1つしか定義が存在しない。

解釈

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 には任意の複雑な表現が当てはまるので、これらは強力な先読み機能となる。

例

以下は、非負整数についての四則演算を行う数式を認識するPEGである。

Value ← [0-9]+ / '(' Expr ')'
Product ← Value (('*' / '/') Value)*
Sum ← Product (('+' / '-') Product)*
Expr ← Sum

この例では、終端記号は文字であり、シングルクオートで囲んで '(' や ')' のように表されている。範囲 [0-9] も10種類の数字 0 から 9 を表している。このような範囲表現は正規表現でも用いられている。非終端記号は各規則の左辺に現れている Value, Product, Sum, Expr である。

次の例ではシングルクオートを省略して読みやすくしている。小文字は終端記号、大文字のイタリック体が非終端記号である。実際のPEGパーサでは、小文字で表される終端記号は引用記号で囲む必要がある。

parsing expression (a/b)* は任意の長さの a および b の並びにマッチする。規則 S ← a S? b は単純な文脈自由マッチング言語 を表している。以下のPEGは文脈自由でない言語 を表している。

S ← &(A !b) a+ B !.
A ← a A? b
B ← b B? c

次の例は、再帰的規則でC言語風の if/then/else 文にマッチするものである。"else" 節は省略可能で、'/' オペレータの暗黙の優先順位付けによって常に最も内側の "if" と対応付けられる。文脈自由文法では、else の対応関係は曖昧となる。

S ← if C then S else S / if C then S

foo &(bar) というparsing expressionは、"bar" というテキストが後に続く場合のみ "foo" というテキストにマッチし消費する。foo !(bar) というparsing expressionは、"bar" というテキストが後に続かない場合のみ "foo" というテキストにマッチし消費する。!(a+ b) a という表現は、'a' の任意の長さの並びに 'b' が続く形式でない場合のみ 'a' にマッチする。

以下の再帰的規則はPascal風の (* このように (* 入れ子に *) できる *) コメントの構文にマッチするものである。コメント記号はPEGのオペレータと区別するためにダブルクオートで囲んでいる。

Begin ← "(*"
End ← "*)"
C ← Begin N* End
N ← C / (!Begin !End Z)
Z ← any single character

PEGに基づいた構文解析器の実装

PEGはそのまま再帰下降構文解析の構文解析器に変換可能である[1]。ただしそれをナイーブに実装すると最悪の場合、最後まで先読みして失敗し、また最初から繰返すことにより指数時間かかる可能性がある構文解析器になってしまう。

しかし、PEGが21世紀に入って以降に見直される傾向となったのは、再帰下降構文解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにするPackrat Parser[2]の実用性が確認されたためである。メモ化のためにメモリ領域を必要とすることと引き換えに、理論的には常に線形時間で動作する。遅延評価の言語では自然に実装できることもこれを後押しした。

ただし実際のプログラミング言語などでは、典型的にはC言語においてtypedefで「型の名前」として扱われるべき名前が追加されることによる大域的な文脈依存性などで、再度の解析が必要となる場合があるが、そういったものも含め、たいていは実用的な範疇である。

利点

上述のように Packrat Parser を使えば線形時間で構文解析可能である。

文脈自由文法とほぼ同程度の利点がある。すなわち、正規表現より強力でありよい代替手法となる、等である。

C言語のような典型的なプログラミング言語の文法では、既存のよく使われている手法、たとえばyaccのLALR(1)文法では、先読みの制限により、広義の構文解析について前段となる字句解析を分離し、いわゆる「トークン」を終端記号にしなければならない。これは局所的には任意の文字数を先読みする必要があるためである。PEGにはこの制限が無いため、字句解析の段階に相当する規則も構文規則として統合的に扱うことができる。

en:Dangling else のような多義性（曖昧な文法の記事を参照）について、文脈自由文法ではそれが「曖昧な文法」であり、yaccなどではそれがコンフリクトとその解決として明示的に多義的でなくなる。一方PEGでは、最初に解析に成功した結果が、そもそも文法が意図していたものだとされる。このどちらが良いかは目的にもより、見方によってはPEGの欠点である。

欠点

左再帰の問題（詳細は「左再帰」の記事を参照）は、ナイーブな再帰下降構文解析の場合と全く同様に、PEGでも問題となる。

PEGパーサ生成器ほか

PEGパーサ（多くはPackratパーサ）を生成するパーサジェネレータやパーサコンビネータライブラリなどを以下に示す。

注

  1. ^ "Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking" §3.1.1 pp.32〜33
  2. ^ Ford, Bryan (September 2002). “Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking”. Massachusetts Institute of Technology. 2007年7月27日閲覧。

外部リンク