编译原理——文法的化简与改造(附源代码)

时间:2022-05-10 14:39:56

文法的化简与改造

1、无用符号及无用产生式的删除

无用符号:设有一文法G[S]= VNVTPS),说G中的一个符号XV是有用的是指X至少出现在一个句子的推导过程中,即满足:

存在α,β∈V*,有S=*>αXβ

存在ω∈VT*,αXβ=*>ω

否则X为无用符号

 

设有文法G[S]= VNVTPS),首先用算法2.1改造该文法的到G1[S]= VN1VTP1S),使得对于每一个XVN1,都有ω∈VT*X=*>ω

 

算法1

分别置VN1P1为Φ。

P中每一个产生式A→δ,若δ∈VT*,则将A放入VN1中。

P中每一个产生式AX1 X2……XK,若每一个Xi 都属于VTVN1,则将A放入VN1中。

重复③直至VN1不增大。

对于P中的每一个产生式BY1 Y2……Yn,若B及每一个Yi,都属于VN1VT  ,则将BY1 Y2……Yn,放入P1中。

其次,对以给文法G[S],若执行算法2.2可得到一等价文法G’=VN VTP’S)使得对任一XVN VT都存在α,β∈(VN VT)有S=*>αXβ.

 1.分别置VN VTP’为φ

 

算法2:

 

2.S 放入VN中。

3.对于G中任何型如A→α1|……|αm的产生式,若AVN则将α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+K1}

  WK+1是一个有限集,设最后的WK+1W

SW时,ε∈LG[S])。

 

设有一文法G[S]= VNVTPS),当ε不属于该文法所描述的语言时,可构造文法:

G’=VNVTP’S),使得LG’=LG),G’不含有ε产生式:

算法4:

1.利用WVN分为两个子集WVN -W

2.AX1 X2……XKP,按下面规则将所有型如AY1 Y2……YK的产生式放入P’中,对于一切1ik

  a.若Xi不属于W,则取Yi = Xi

b.  XiW,则分别取YiXi与ε,但是若所有Xi均属于W,却不能把所有Yi取为ε。

 

设有一文法G[S]= VNVTPS),当ε属于该文法所描述的语言时,可构造文法:

G1=VN1VTP1S’),使得LG1=LG),P1中除S’→ε外不再含有其它ε产生式,并且S’不出现在任何产生式的右边。

 

 

算法5

S不出现在任何产生式的右部,则可直接用算法2.4消除ε产生式,再加入S→ε,否则:

  1.引入新的非终结符S’ VN1= VN{ S’}

  2.构造P’ =P{ S’→α| S→α∈P}

  3.对文法G1=VN1VTP1S’),执行算法4,再加入S’→ε。

 

3、单产生式的消除

ABA,BVN此类产生式被称为单产生式。

假定文法中不含有ε产生式。

 

算法6

VN ={ A1 ...... AN } 对每一个Ai1in)构造集合序列

W1(Ai={Ai}

WK+1Ai= WKAi)∪{D|CDPCWKAi),DVN }

K1,该集合序列存在一个j,有

WjAi= Wj+1Ai......

Wi= WjAi

Wi={B| Ai =>BBVN }

构造P’={ Ai→α|B→α∈PBWi),α不是单个非终结符}

 

=================================================================

附:源代码,请在此下载

http://d.download.csdn.net/down/309862/njdragonfly