Parsing Expression Grammar

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: 案内、 検索

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

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

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

目次

定義 [編集]

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

P に含まれる各解析規則は、A ← e という形式であり、A は非終端記号、e は「解析表現; parsing expression」である。解析表現は正規表現に似た階層型の数式であり、次のように構築される。

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

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

解析表現の解釈 [編集]

PEG における各非終端記号は、ある意味で再帰下降構文解析における構文解析関数を表現しており、それに対応する解析表現はその関数のコードを表現している。各構文解析関数は、引数として入力文字列をとり、以下のいずれかの結果を返す。

  • 「成功」- 引数として与えられた文字列からいくつかの文字を「消費」するなどした場合
  • 「失敗」- 入力を全く消費できなかった場合

非終端記号は入力を全く消費しなくとも成功と見なされる場合があり、単に返される結果だけで失敗と区別される。

1つの終端記号からなる原子解析表現は、入力文字列の先頭の文字と一致した場合に成功し、その入力文字を消費する。さもなくば、その解析表現は失敗の結果を返す。空文字列だけからなる原子解析表現は、入力を消費せずに常に成功と見なされる。非終端記号 A からなる原子解析表現は、非終端関数 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述語とNOT述語は統語的述語（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パーサでは、小文字で表される終端記号は引用記号で囲む必要がある。

解析表現 (a/b)* は任意の長さの a および b の並びにマッチする。規則 S ← a S? b は単純な文脈自由マッチング言語 \{ a^n b^n : n \ge 1 \} を表している。以下の PEG は文脈自由でない言語 \{ a^n b^n c^n : n \ge 1 \} を表している。

S ← &(A !b) a+ B !c
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) という解析表現は、"bar" というテキストが後に続く場合のみ "foo" というテキストにマッチし消費する。foo !(bar) という解析表現は、"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]。先読みが無制限に可能であるため、最悪の場合指数関数時間かかる。

解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにすると、任意の PEG を Packrat Parser に変換でき、メモリ領域を余分に必要とするものの、常に線形時間で動作する。

Packrat Parser[2] は再帰下降構文解析器と構造的にはよく似た構文解析器である。ただし、Packrat Parser は相互再帰構文解析関数を呼び出す度に途中結果をメモ化する。このメモ化によって Packrat Parser は、多くの文脈自由文法と任意のPEG（文脈自由でない場合も含む）を線形時間で構文解析できるようになっている。

PEG から LL法やLR法のパーサを構築することも可能だが、その場合、無限の先読みが可能という特徴が失われてしまう。

利点 [編集]

PEG は正規表現より強力であり、よい代替手法となる。例えば、正規表現は再帰的ではないため本質的に括弧の対応付けができないが、PEG では可能である。

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

文脈自由文法で表される言語の構文解析器（例えばLR法）は、事前に入力を字句解析しておく必要がある。字句解析は線形時間内で先読みしつつ構文解析するにあたって必要となるものである。しかし PEG は事前に字句解析する必要はなく、字句解析規則を他の構文規則と同じように記述できる。

文脈自由文法は多くの場合本質的に曖昧であり、曖昧でない言語を記述する場合でもそのようになる傾向がある。C、C++、Java における else の曖昧さの問題はその例である。通常、このような曖昧さは文法以外の規則を適用することで解決される。PEG では、優先順位が厳密に決まるため、そのような曖昧さは発生しない。

欠点 [編集]

PEG は新しく、実装例が少ない。対照的に文脈自由文法と正規表現は数十年の歴史があり、実装に関しても最適化が行われ、多くのプログラマが使い方を知っているという利点がある。

PEG は、文字列上で位置を変更せずにある規則が自分自身を呼び出すという左再帰規則を表現できない。例えば、上述の数式の文法では、次のような規則としたほうが自然である。

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

この場合、Expr とマッチするかを判定するには、まず Product とマッチするかを判定する必要があり、Product とマッチするかを判定するには、Expr とマッチするかを判定しなければならない。これは不可能である（循環定義になっていて完了しない）。

しかし、左再帰規則は常に左再帰を使わない形式で書き換え可能である。例えば、左再帰規則で任意長の繰り返しを表すと（文脈自由文法では）次のようになる。

string-of-a ← string-of-a 'a' | 'a'

PEG ではこれを + オペレータを使って書き換え可能である。

string-of-a ← 'a'+

PEGパーサ生成器ほか [編集]

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

関連項目 [編集]

参考文献 [編集]

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

外部リンク [編集]

「http://ja.wikipedia.org/w/index.php?title=Parsing_Expression_Grammar&oldid=47465812」から取得