Parsing Expression Grammar
形式的には、PEGは次の要素からなる。
非終端記号の有限集合 N
終端記号の有限集合 Σ(Nとは交わらない)
規則の有限集合 P
P に含まれる各規則は、A ← e という形式であり、A は非終端記号、e は、次のように構築される記号およびメタ記号の列である。前述のように、文脈自由文法における「どれかを選択」という意味の「 | 」の代わりに、「順番に試す」という意味の「 / 」を使うことが特徴である。
「atomic parsing expression」は次のいずれかである。 任意の終端記号 任意の非終端記号 空文字列 ε
任意の既存のparsing expressionを e, e1, e2 としたとき、以下のように構築されるものもparsing expressionである。 並び: e1 e2 選択: e1 / e2 ゼロ個以上: e* 1個以上: e+ 省略可能: e? AND predicate: &e NOT predicate: !e
文脈自由文法や他の生成文法とは異なり、PEGでは、ある非終端記号が左辺にくる規則は常に1つしか存在しない。すなわち、規則群は「定義」であり、各非終端記号には1つしか定義が存在しない。