文法的化简与改造
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：
分别置VN1，P1为Φ。
对P中每一个产生式A→δ，若δ∈VT*，则将A放入VN1中。
对P中每一个产生式A→X1 X2……XK，若每一个Xi 都属于VT或VN1，则将A放入VN1中。
重复③直至VN1不增大。
对于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β.
1.分别置VN’、 VT’、P’为φ
算法2:
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），α不是单个非终结符}
=================================================================
附：源代码，请在此下载