Basic implementation for PEG

[nagisc007]

PEG (Parsing Expression Grammar) の基本についてまとめておきます。

[nagisc007]

基本定義

要素

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

規則

規則Pとは「A　←　ｅ」であり、Aは非終端記号、ｅは記号、またはメタ記号の列である

atomic parsing expression

• 任意の終端記号
• 任意の非終端記号
• 空文字列 ε

another parsing expression

• 並び: e1 e2
• 選択: e1 / e2
• ゼロ個以上: e*
• 1個以上: e+
• 省略可能: e?
• AND predicate: &e
• NOT predicate: !e

解釈

非終端記号は、再帰下降構文解析における構文解析関数を表現しており、parsing expression は関数とみなせる。各関数は引数として「入力文字列」をとり、次のいずれかの結果を返す

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

[nagisc007]

並び

e1、e2の並びでは、まずe1が評価され、成功なら、文字列を消費して、次にe2で評価する。e1かe2のいずれかが失敗した場合は「全体が失敗」とみなす。

[nagisc007]

選択

e1／e2では、まずe1で評価し、成功ならただちにその結果が返される（e2は評価しない）。e1が失敗の場合は、e1で文字列を消費しない状態にバックトラックし、e2で評価する。