PEG覚え書き
PEG? Parsing Expression Grammerの略 Contest Free Grammerと同等レベルの表現能力 曖昧さを許さない文法 Parsing Expression Grammars:A Recognition-Based Syntactic Foundation by Bryan Ford Page 2
PEGの活用 PEGは正規表現の強力版 Perl6にもPEGが GaucheにもPEGが Haskell, Pappy, Frisby OCaml, aurochs Page 3
PEG定義 「非終端記号 ← parsing expression」の集合(ただし、非終端記号はユニーク) ε(空文字) 終端記号 非終端記号 e1 e2(並び) e1 / e2(選択) e*(0個以上) !e (入力を消費しない存在確認) オプショナル e? = e/ ε e+ = e e* &e = ! !e Page 4
例:足し算とかけ算 PEG CFG V ← (0/1/2/3/4/5/6/7/8/9)+/”(“ E “)” %left “+” exp : exp “+” exp | exp “*” exp PEG V ← (0/1/2/3/4/5/6/7/8/9)+/”(“ E “)” P ← V (“*” V)* S ← P (“+” P)* E ← S Page 5