CFGの簡略化
CFGでは、文字列の導出にすべての生成規則と記号が必要ない場合があります。その上、いくつかのヌルプロダクションとユニットプロダクションがあるかもしれません。これらの作品やシンボルの排除は、simplification of CFGs。簡略化は、基本的に次の手順で構成されます。
- CFGの削減
- ユニットプロダクションの削除
- ヌルプロダクションの削除
CFGの削減
CFGは2つのフェーズで削減されます-
Phase 1 −同等の文法の導出、 G’、CFGから、 G、各変数が何らかの端末文字列を導出するように。
Derivation Procedure −
ステップ1-すべての記号を含める、 W1、ターミナルを派生させて初期化します i=1。
ステップ2-すべての記号を含める、 Wi+1、派生 Wi。
ステップ3-インクリメント i ステップ2を繰り返します Wi+1 = Wi。
ステップ4-以下のすべてのプロダクションルールを含める Wi 初期化。
Phase 2 −同等の文法の導出、 G”、CFGから、 G’、各記号がセンテンス形式で表示されるようにします。
Derivation Procedure −
ステップ1-開始記号をに含める Y1 初期化して i = 1。
ステップ2-すべての記号を含める、 Yi+1、から派生することができます Yi 適用されたすべてのプロダクションルールを含めます。
ステップ3-インクリメント i ステップ2を繰り返します Yi+1 = Yi。
問題
文法Gに相当する、生成規則P：S→AC |を持つ縮小文法を見つけます。B、A→a、C→c | BC、E→aA | e
解決
Phase 1 −
T = {a、c、e}
W 1 = {A、C、E}ルールA→a、C→cおよびE→aAから
W 2 = {A、C、E} U {S}ルールS→ACから
W 3 = {A、C、E、S}U∅
W 2 = W 3なので、G 'を−として導出できます。
G '= {{A、C、E、S}、{a、c、e}、P、{S}}
ここで、P：S→AC、A→a、C→c、E→aA | e
Phase 2 −
Y 1 = {S}
Y 2 = {S、A、C}ルールS→ACから
Y 3 = {S、A、C、a、c}ルールA→aおよびC→cから
Y 4 = {S、A、C、a、c}
Y 3 = Y 4なので、G”を−として導出できます。
G” = {{A、C、S}、{a、c}、P、{S}}
ここで、P：S→AC、A→a、C→c
ユニットプロダクションの削除
A、B∈非終端記号と呼ばれるA→Bの形式の任意の生成規則 unit production.。
取り外し手順-
Step 1 −削除するには A → B、生産を追加 A → x いつでも文法規則に B → x文法で発生します。[x∈ターミナル、xはNullにすることができます]
Step 2 −削除 A → B 文法から。
Step 3 −すべてのユニット生産が削除されるまで、ステップ1から繰り返します。
Problem
以下からユニット生産を削除します-
S→XY、X→a、Y→Z | b、Z→M、M→N、N→a
Solution −
文法には3つのユニットプロダクションがあります-
Y→Z、Z→M、およびM→N
At first, we will remove M → N.
N→aとして、M→aを追加し、M→Nを削除します。
生産セットは
S→XY、X→a、Y→Z | b、Z→M、M→a、N→a
Now we will remove Z → M.
M→aとして、Z→aを追加し、Z→Mを削除します。
生産セットは
S→XY、X→a、Y→Z | b、Z→a、M→a、N→a
Now we will remove Y → Z.
Z→aとして、Y→aを追加し、Y→Zを削除します。
生産セットは
S→XY、X→a、Y→a | b、Z→a、M→a、N→a
これで、Z、M、およびNに到達できなくなったため、これらを削除できます。
最終的なCFGはユニット生産フリーです-
S→XY、X→a、Y→a | b
ヌルプロダクションの削除
CFGでは、非終端記号 ‘A’ プロダクションがある場合はnull許容変数です A → ε またはで始まる派生があります A そして最後に
ε：A→.......…→ε
取り外し手順
Step 1 −εを導出するnull許容の非終端変数を見つけます。
Step 2 −各プロダクションについて A → a、すべてのプロダクションを構築します A → x どこ x から取得されます ‘a’ 手順1から1つまたは複数の非終端記号を削除します。
Step 3 −元の作品をステップ2の結果と組み合わせて、削除します ε - productions。
Problem
以下からヌルプロダクションを削除します-
S→ASA | aB | b、A→B、B→b | ∈
Solution −
2つのnull許容変数があります- A そして B
At first, we will remove B → ε.
取り外した後 B → ε、プロダクションセットは−になります
S→ASA | aB | b | a、AεB| b | ＆epsilon、B→b
Now we will remove A → ε.
取り外した後 A → ε、プロダクションセットは−になります
S→ASA | aB | b | a | SA | AS | S、A→B | b、B→b
これは、ヌル遷移のない最終的なプロダクションセットです。