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