文法的化簡與改造
1、無用符號及無用產生式的刪除
無用符號：設有一文法G[S]= （VN ，VT ，P，S），說G中的一個符號X∈V是有用的是指X至少出現在一個句子的推導過程中，即滿足：
存在α，β∈V*，有S=*>αXβ
存在ω∈VT* ，αXβ=*>ω
否則X為無用符號
設有文法G[S]= （VN ，VT ，P，S），首先用算法2.1改造該文法的到G1[S]= （VN1 ，VT ，P1，S），使得對于每一個X∈VN1，都有ω∈VT*，X=*>ω
算法1：
(1) 分別置VN1，P1為Φ。
(2) 對P中每一個產生式A→δ，若δ∈VT*，則將A放入VN1中。
(3) 對P中每一個產生式A→X1 X2……XK，若每一個Xi 都屬于VT或VN1，則將A放入VN1中。
(4) 重復③直至VN1不增大。
(5) 對于P中的每一個產生式B→Y1 Y2……Yn ，若B及每一個Yi ，都屬于VN1∪VT ，則將B→Y1 Y2……Yn，放入P1中。
其次，對以給文法G[S]，若執行算法2.2可得到一等價文法G’=（VN’， VT’ ，P’，S）使得對任一X∈VN’∪ VT’都存在α，β∈（VN’∪ VT’）有S=*>αXβ.
算法2:
1.分別置VN’、 VT’、P’為φ
2.將S 放入VN’中。
3.對于G中任何型如A→α1|……|αm的產生式，若A∈VN’則將α1……αm 中的全部非終結符放入VN’中，終結符放入VT’中。
4.重復③直至VN’、 VT’不增大為止。
5.將P中左右部僅含VN’∪ VT’中符號的所有產生式放入P’ 中。
2、ε—產生式的消除
有的分析方法要求文法中不能含有ε—產生式，因此需要改造文法使之不含ε—產生式。
如果語言不含有ε句子，則可有辦法消除文法中的全部ε—產生式，否則不可能全部消除，但我們希望只有在空句子的推導中用到ε—產生式，其他語句的推導過程中不會使用ε—產生式。故對含有空句子的文法，我們希望只有文法開始符S→ε這樣一個產生式并且S不出現在其它任何產生式的右部。
算法3：
找出所有能導出ε的非終結符。
1.構造W1={A|產生式A→ε∈P}
2.構造集合序列WK+1= WK∪{B|B→β∈P，且β∈WK，K≥1}
WK+1是一個有限集，設最后的WK+1為W。
當S∈W時，ε∈L（G[S]）。
設有一文法G[S]= （VN ，VT ，P，S），當ε不屬于該文法所描述的語言時，可構造文法：
G’=（VN，VT，P’，S），使得L（G’）=L（G），G’不含有ε產生式：
算法4:
1.利用W將VN 分為兩個子集W及VN -W。
2.設A→X1 X2……XK∈P，按下面規則將所有型如A→Y1 Y2……YK 的產生式放入P’中，對于一切1≤i≤k：
a．若Xi 不屬于W，則取Yi = Xi
b．若Xi ∈W，則分別取Yi 為Xi與ε，但是若所有Xi均屬于W，卻不能把所有Yi 取為ε。
設有一文法G[S]= （VN ，VT ，P，S），當ε屬于該文法所描述的語言時，可構造文法：
G1=（VN1 ，VT ，P1，S’），使得L（G1）=L（G），P1中除S’→ε外不再含有其它ε產生式，并且S’不出現在任何產生式的右邊。
算法5：
若S不出現在任何產生式的右部，則可直接用算法2.4消除ε產生式，再加入S→ε，否則：
1．引入新的非終結符S’， VN1= VN ∪{ S’}
2．構造P’ =P∪{ S’→α| S→α∈P}
3．對文法G1=（VN1 ，VT ，P1，S’），執行算法4，再加入S’→ε。
3、單產生式的消除
A→B，A,B∈VN 此類產生式被稱為單產生式。
假定文法中不含有ε產生式。
算法6：
設VN ={ A1 ...... AN } 對每一個Ai （1≤i≤n）構造集合序列
W1( Ai）={Ai}，
WK+1（Ai ）= WK（Ai ）∪{D|C→D∈P，C∈WK（Ai ），D∈VN }
K≥1，該集合序列存在一個j，有
Wj（Ai ）= Wj+1（Ai ）......
令W（i）= Wj（Ai ）
W（i）={B| Ai =>B，B∈VN }
構造P’={ Ai →α|B→α∈P，B∈W（i），α不是單個非終結符}(對于A1到An的U操作),此時P′中已不含任何單產生式。
</script>