PEG
PEG(Parsing Expression Grammar)
解析表現文法（英: Parsing Expression Grammar; PEG）
2004年にB.Fordが提案した文法
古来からある文脈自由文法(Context Free Grammar: CFG)や正規表現(Regular Expression)と同じ文法の仲間 特徴
字句解析器がいらない
CFGとは違う言語クラスが定義できる
曖昧さがない
非終端記号の有限集合$ N
終端記号の有限集合 $ Σ （Nとは交わらない）
規則の有限集合$ P
ex1のようにPEGの構文ルールは構文名<-構文内容で定義
右辺を非終端記号
左辺をParsing Expression
IF文、while文、単項演算、代入文など欲しい構文ルールを作っていくと、プログラミング言語を作ることが出来る
構文ルールの集まりが文法
code:memo
add <- Integer "+" Integer
# ↓展開後
「atomic parsing expression」は次のいずれかである。
任意の終端記号
任意の非終端記号
空文字列 ε
任意の既存のparsing expressionを e, e1, e2 としたとき、以下のように構築されるものもparsing expressionである。
並び: e1 e2
選択: e1 / e2
ゼロ個以上: e*
1個以上: e+
省略可能: e?
AND predicate: &e
NOT predicate: !e
CFGでのLL(1)構文解析は行う前に字句解析が必要
code:memo
add <- Integer "+" Integer
構文名<-構文内容の形式で記述
右辺を非終端記号
左辺をParsing Expression
code:memo
e := a \\ 終端記号
A \\ 非終端記号
ε \\ 空文字列
e' e'' \\ 連接
e' * \\ 0以上の繰り返し
e' / e'' \\ 優先度付き選択
! e' \\ 否定先読み
e' + \\ 1以上の繰り返し
e' ? \\ 省略可能
& e' \\ 肯定先読み
. \\任意の一文字
終端記号
構文ルールに出てくる文字列のことです。大抵の場合は構文ルール中に"+"や"("のように現れます。
終端記号: [0-9], "+"
非終端記号: add, Integer
文法制作者にとって直感的でない振る舞いをすること
工夫をしないと遅いこと
関連
確認用
Q. PEG
Q. PEGのメリット
Q. PEGのデメリット
参考