文法的化简与改造
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),α不是单个非终结符}
=================================================================
附:源代码,请在此下载