文脈自由文法 CFG
- CFG 実際のプログラム言語では Context-free では
ないが、文法規定の中核として重要。
- 慣用的な数式の構成がCFGに適合する。
- 構文単位の構成の際に内部構造が外部構造と無関係。
- CFG についての処理系による認識など理論・技法が得られている。
CFGとは、次の4つ組
G = < V, Σ, P, S >
である。ここで
- V はGの語彙(vocabulary)と呼ぶ有限集合。
その要素はGの記号(symbol)。
- Σ はV の部分集合で、G の文字集(alphabet)。
- Σの要素
- G の文字 終端記号(terminal symbol)
- V - Σの要素
- 構文単位(syntactic unit) 構文変数(syntactic variable)
非終端記号(nonterminal symbol)という。
- P はG の生成規則集(set of poduction rules)
Gの構文単位A に V 上の記号列α を
対応させる順序対 <A,α>を
- A → α
の形に書いたもの。
- S は構文単位の一つで、G の開始記号(start symbol)
- 連接
- αβ は α と β の連接
- 導出
- σ ⇒ σ′ A の出現に着目し、
αで置き換える操作
- 生成
- σ0 = S からの導出で得られるものの全体 L(G)
- 文法G で生成された言語
例 2進数字`0'と`1'を並べた2進数で、3の倍数になるものを生成するCFG
- Σ = {0,1};
- VN = V - Σ
- = {M, M0, M1, M2 };
- P = {M → 0,
- M → M0, M1 → 1,
- M0 → M11, M0 → M00,
- M1 → M01, M1 → M20,
- M2 → M10, M2 → M21
};
- S = M