Parsing Expression Grammar

ウィキペディア

Parsing Expression Grammar

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/18 08:11 UTC 版)

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

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

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

定義

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

• 非終端記号の有限集合 N
• 終端記号の有限集合 Σ（Nとは交わらない）
• 規則の有限集合 P

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

1. 「atomic parsing expression」は次のいずれかである。
   • 任意の終端記号
   • 任意の非終端記号
   • 空文字列 ε

1. 任意の既存のparsing expressionを e, e₁, e₂ としたとき、以下のように構築されるものもparsing expressionである。
   • 並び: e₁ e₂
   • 選択: e₁ / e₂
   • ゼロ個以上: 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 の再帰呼び出しを表している。

並び 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である。

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 は単純な文脈自由マッチング言語 ${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$