ＰＥＧ覚え書き
PEG？
 Parsing Expression Grammerの略
 Contest Free Grammerと同等レベルの表現能力
 パース手法の一つである再帰下降法と相性がいい。O(n)
 曖昧さを許さない文法
 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」の集合（ただし、非終端記号はユニーク）
parsing expression定義
1.
2.
3.
4.
5.
6.
7.
Page 4
ε(空文字)
オプショナル
終端記号
e? = e/ ε
非終端記号
e+ = e e*
e1 e2(並び)
&e = ! !e
e1 / e2(選択)
e*(0個以上)
!e （入力を消費しない存在確認)
例:足し算とかけ算
CFG
%left “+”
%left “*”
exp : exp “+” exp
| exp “*” exp
Page 5
PEG
V ← (0/1/2/3/4/5/6/7/8/9)+/”(“ E “)”
P ← V (“*” V)*
S ← P (“+” P)*
E←S

スライド 1

Document

pwlc week at a glance v1