形式語言 第6章 上下文無關(guān)語言ppt課件

1、第第6章章 上下文無關(guān)言語上下文無關(guān)言語 主要內(nèi)容主要內(nèi)容 關(guān)于關(guān)于CFLCFL的分析的分析 派生和歸約、派生樹派生和歸約、派生樹 CFGCFG的化簡的化簡 無用符、單一產(chǎn)生式、空產(chǎn)生式無用符、單一產(chǎn)生式、空產(chǎn)生式 CFGCFG的范式的范式 CNFCNF GNFGNF CFGCFG的自嵌套特性的自嵌套特性 第第6章章 上下文無關(guān)言語上下文無關(guān)言語 重點重點 CFGCFG的化簡。的化簡。 CFGCFG到到GNFGNF的轉(zhuǎn)換。的轉(zhuǎn)換。 難點難點 CFGCFG到到GNFGNF的轉(zhuǎn)換，特別是其中的用右遞歸的轉(zhuǎn)換，特別是其中的用右遞歸交換左遞歸的問題。交換左遞歸的問題。6.1 上下文無關(guān)言語上下文無關(guān)言

2、語 文法文法G=(VG=(V，T T，P P，S)S)被稱為是上下文無關(guān)被稱為是上下文無關(guān)的。的。 假設(shè)除了形如假設(shè)除了形如A A的產(chǎn)生式之外，的產(chǎn)生式之外，對于對于PP，均有，均有|，并且，并且VV成立。成立。 關(guān)鍵：對于關(guān)鍵：對于AVAV，假設(shè)，假設(shè)A APP，那么，那么無論無論A A出如今句型的任何位置，我們都可以出如今句型的任何位置，我們都可以將將A A交換成交換成，而不思索，而不思索A A的上下文。的上下文。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 算術(shù)表達式的文法算術(shù)表達式的文法 Gexp1Gexp1：E EE+T|E-T|TE+T|E-T|TT TT T* *F

3、|T/F|FF|T/F|FF FFP|PFP|PP P(E)|N(L)|id(E)|N(L)|idN Nsin|cos|exp|abs|log|intsin|cos|exp|abs|log|intL LL,E|E L,E|E 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 算術(shù)表達式算術(shù)表達式x+x/y2x+x/y2的不同派生的不同派生 E EE+TE+TT+TT+TF+TF+TP+TP+Tx+Tx+Tx+T/Fx+T/Fx+F/Fx+F/Fx+P/Fx+P/Fx+x/Fx+x/Fx+x/FPx+x/FPx+x/PPx+x/PPx+x/yPx+x/yPx+x/y2 x+x/y2 E

4、EE+TE+TE+T/FE+T/FE+T/FPE+T/FPE+T/F2E+T/F2E+T/P2E+T/P2E+T/y2E+T/y2 E+F/y2 E+F/y2 E+P/y2 E+P/y2 E+x/y2 E+x/y2 T+x/y2 T+x/y2 F+x/y2 F+x/y2 P+x/y2 P+x/y2x+x/y2 x+x/y2 E EE+TE+TT+TT+TT+T/FT+T/FF+T/FF+T/FF+T/FPF+T/FPP+T/FPP+T/FPx+T/FPx+T/FPx+F/FPx+F/FPx+F/F2x+F/F2x+F/P2x+F/P2x+P/P2x+P/P2x+P/y2x+P/y2x+x/y2

5、 x+x/y2 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 文法文法Gexp1Gexp1句子句子x+x/y2x+x/y2的構(gòu)造。的構(gòu)造。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 派生樹派生樹(derivation tree) (derivation tree) 一棵一棵( (有序有序) )樹樹(ordered tree) (ordered tree) 樹的每個頂點有一個標(biāo)志樹的每個頂點有一個標(biāo)志X X，且，且XVT XVT 樹根的標(biāo)志為樹根的標(biāo)志為S S； 假設(shè)非葉子頂點假設(shè)非葉子頂點v v標(biāo)志為標(biāo)志為A A，v v的兒子從左到的兒子從左到右依次為右依次為v1v

6、1，v2v2，vnvn，并且它們分別，并且它們分別標(biāo)志為標(biāo)志為X1X1，X2X2，XnXn，那么，那么A AX1X2XnPX1X2XnP； 假設(shè)假設(shè)X X是一個非葉子頂點的標(biāo)志，那么是一個非葉子頂點的標(biāo)志，那么XVXV； 假設(shè)頂點假設(shè)頂點v v標(biāo)志為標(biāo)志為，那么，那么v v是該樹的葉子是該樹的葉子，并且，并且v v是其父頂點的獨一兒子。是其父頂點的獨一兒子。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 別稱別稱 生成樹生成樹 分析樹分析樹(parse tree)(parse tree) 語法樹語法樹(syntax tree) (syntax tree) 順序順序 v1v1，v2v

7、2是派生樹是派生樹T T的兩個不同頂點，假設(shè)存的兩個不同頂點，假設(shè)存在頂點在頂點v v，v v至少有兩個兒子，使得至少有兩個兒子，使得v1v1是是v v的的較左兒子的后代，較左兒子的后代，v2v2是是v v的較右兒子的后代的較右兒子的后代，那么稱頂點，那么稱頂點v1v1在頂點在頂點v2v2的左邊，頂點的左邊，頂點v2v2在頂點在頂點v1v1的右邊。的右邊。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 結(jié)果結(jié)果(yield) (yield) 派生樹派生樹T T的一切葉子頂點從左到右依次標(biāo)志的一切葉子頂點從左到右依次標(biāo)志為為X1X1，X2X2，XnXn，那么稱符號串，那么稱符號串X1

8、X2XnX1X2Xn是是T T的結(jié)果。的結(jié)果。 一個文法可以有多棵派生樹，它們可以有一個文法可以有多棵派生樹，它們可以有不同的結(jié)果。不同的結(jié)果。 句型句型的派生樹：的派生樹：“G“G的結(jié)果為的結(jié)果為的派生樹的派生樹。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 派生子樹派生子樹(subtree) (subtree) 滿足派生樹定義中除了對跟結(jié)點的標(biāo)志的滿足派生樹定義中除了對跟結(jié)點的標(biāo)志的要求以外各條的樹叫派生子樹要求以外各條的樹叫派生子樹(subtree)(subtree)。 假設(shè)這個子樹的根標(biāo)志為假設(shè)這個子樹的根標(biāo)志為A A，那么稱之為，那么稱之為A A子樹。子樹。 獨一差別是根

9、結(jié)點可以標(biāo)志非開場符號。獨一差別是根結(jié)點可以標(biāo)志非開場符號。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-1 6-1 設(shè)設(shè)CFG G=(VCFG G=(V，T T，P P，S)S)，S S* *的的充分必要條件為充分必要條件為G G有一棵結(jié)果為有一棵結(jié)果為的派生樹的派生樹。證明：證明：證一個更為普通的結(jié)論：對于恣意證一個更為普通的結(jié)論：對于恣意AVAV，A A* *的充分必要條件為的充分必要條件為G G有一棵結(jié)果為有一棵結(jié)果為的的A-A-子樹。子樹。 充分性：設(shè)充分性：設(shè)G G有一棵結(jié)果為有一棵結(jié)果為的的A-A-子樹，非葉子樹，非葉子頂點的個數(shù)子頂點的個數(shù)n n施歸納，證

10、明施歸納，證明A A* *成立。成立。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 設(shè)設(shè)A-A-子樹有子樹有k+1k+1個非葉子頂點，根頂點個非葉子頂點，根頂點A A的的兒子從左到右依次為兒子從左到右依次為v1v1，v2v2，vmvm，并，并且它們分別標(biāo)志為且它們分別標(biāo)志為X1X1，X2X2，Xm Xm 。 A AX1X2XmP X1X2XmP 。 以以X1X1，X2X2，XmXm為根的子樹的結(jié)果依次為根的子樹的結(jié)果依次為為11，22，m m 。 X1X1，X2X2，XmXm為根的子樹的非葉子頂點為根的子樹的非葉子頂點的個數(shù)均不大于的個數(shù)均不大于k k。 6.1.1 上下文無關(guān)文

11、法的派生樹上下文無關(guān)文法的派生樹 X1*1X2*2Xm*m而且而且=12m6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹AX1X2Xm *1X2Xm *12Xm *12m6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 必要性必要性 設(shè)設(shè)A Ann，現(xiàn)施歸納于派生步數(shù)，現(xiàn)施歸納于派生步數(shù)n n，證明存在結(jié)果，證明存在結(jié)果為為的的A-A-子樹。子樹。 設(shè)設(shè)nk(k1)nk(k1)時結(jié)論成立，往證當(dāng)時結(jié)論成立，往證當(dāng)n=k+1n=k+1時結(jié)論也時結(jié)論也成立：令成立：令A(yù) Ak+1k+1，那么有：，那么有：A AX1X2XmX

12、1X2Xm * *1X2Xm1X2Xm * *12Xm12Xm * *12m 12m 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 例例6-16-1設(shè)設(shè)GbraGbra：S SS(S)|S(S)|，()()()()和和(S)(S)(S)(S)的派生樹。的派生樹。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 關(guān)于標(biāo)志關(guān)于標(biāo)志的結(jié)點的結(jié)點6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 最左派生最左派生(leftmost derivation) (leftmost derivation) 的派生過程中，每一步都

13、是對當(dāng)前句型的派生過程中，每一步都是對當(dāng)前句型的最左變量進展交換。的最左變量進展交換。 左句型左句型(left sentencial form)(left sentencial form) 最左派生得到的句型可叫做左句型。最左派生得到的句型可叫做左句型。 最右歸約最右歸約(rightmost reduction)(rightmost reduction) 與最左派生對相的歸約叫做最有歸約。與最左派生對相的歸約叫做最有歸約。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 最右派生最右派生(rightmost derivation) (rightmost derivation) 的派生過

14、程中，每一步都是對當(dāng)前句型的派生過程中，每一步都是對當(dāng)前句型的最右變量進展交換。的最右變量進展交換。 右句型右句型(right sentencial form)(right sentencial form) 最右派生得到的句型可叫做右句型。最右派生得到的句型可叫做右句型。 最左歸約最左歸約(leftmost reduction)(leftmost reduction) 與最左派生對相的歸約叫做最右歸約。與最左派生對相的歸約叫做最右歸約。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 規(guī)范派生規(guī)范派生(normal derivation)(normal derivation) 最右派生

15、。最右派生。 規(guī)范句型規(guī)范句型(normal sentencial form)(normal sentencial form) 規(guī)范派消費生的句型。規(guī)范派消費生的句型。 規(guī)范歸約規(guī)范歸約(normal reduction)(normal reduction) 最左歸約。最左歸約。6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-2 6-2 假設(shè)假設(shè)是是CFG GCFG G的一個句型，那么的一個句型，那么G G中存在中存在的最左派生和最右派生。的最左派生和最右派生。證明：證明：根本思緒：對派生的步數(shù)根本思緒：對派生的步數(shù)n n施歸納，證明對于施歸納，證明對于恣意恣意AVAV，假

16、設(shè)，假設(shè)A Ann，在，在G G中，存在對應(yīng)中，存在對應(yīng)的從的從A A到到的最左派生：的最左派生：A An n左左。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹AX1X2Xm *1X2Xm *12Xm *12mA左左X1X2Xm *左左1X2Xm *左左12Xm *左左12m 同理可證，句型同理可證，句型有最右派生。有最右派生。 6.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-3 6-3 假設(shè)假設(shè)是是CFG GCFG G的一個句型，的一個句型，的派的派生樹與最左派生和最右派生是一一對應(yīng)的生樹與最左派生和最右派生是一一對應(yīng)的，但是，這棵派生樹可以對應(yīng)多個不同的，

17、但是，這棵派生樹可以對應(yīng)多個不同的派生。派生。6.1.2 二義性二義性 簡單算術(shù)表達式的二義性文法簡單算術(shù)表達式的二義性文法 Gexp2：EE+E|E-E|E/E|E*EE EE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 6.1.2 二義性二義性 E E+E x+E x+E/E x+x/E x+x/EEx+x/yEx+x/y2句子句子x+x/y2x+x/y2在文法中的三個不同的最左派生在文法中的三個不同的最左派生 E E/E E+E/E x+E/E x+x/E x+x/EE x+x/yE x+x/y2 E EE E/EE E+E/EE x+E/EE x

18、+x/EE x+x/yE x+x/y2 6.1.2 二義性二義性 對應(yīng)對應(yīng)3 3個不同個不同的語法的語法樹樹6.1.2 二義性二義性 二義性二義性(ambiguity) (ambiguity) CFG G=(VCFG G=(V，T T，P P，S)S)，假設(shè)存在，假設(shè)存在wL(G)wL(G)，w w至少有兩棵不同的派生樹，那么稱至少有兩棵不同的派生樹，那么稱G G是二是二義性的。否那么，義性的。否那么，G G為非二義性的。為非二義性的。 二義性的問題是不可解的二義性的問題是不可解的(unsolvable)(unsolvable)問問題。題。 6.1.2 二義性二義性 例例6-2 6-2 用其他

19、方法消除二義性。用其他方法消除二義性。 GifaGifa：S Sif E then S else S | if E then Sif E then S else S | if E then S GifmGifm：SU|MSU|MUif E then SUif E then SUif E then M else UUif E then M else UMif E then M else M|SMif E then M else M|S GifhGifh：STS|CSSTS|CSCif E thenCif E thenT CS else T CS else 6.1.2 二義性二義性 例例 6-3

20、設(shè)設(shè)Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法產(chǎn)生言語可以用如下文法產(chǎn)生言語Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 言語言語Lambiguity不存在非二義性的文法。不存在非二義性的文法。 6.1.2 二義性二義性 固有二義性的固有二義性的(inherent ambiguity) (inherent ambiguity) 假設(shè)言語假設(shè)言語L L不存在非二義性文法，那么稱不存在非二義性文法，那么稱L L是固有二義性的，又稱是固有二義性的，又稱L L是先天二義性的。是先天二義性的。 文法

21、可以是二義性的。文法可以是二義性的。 言語可以是固有二義性的。言語可以是固有二義性的。 6.1.3 自頂向下的分析和自底向上自頂向下的分析和自底向上的分析的分析 自頂向下的分析方法自頂向下的分析方法 經(jīng)過調(diào)查能否可以從給定文法的開場符號經(jīng)過調(diào)查能否可以從給定文法的開場符號派生出一個符號串，可以斷定一個符號串派生出一個符號串，可以斷定一個符號串能否為該文法的句子。能否為該文法的句子。 例例 SaAb|bBa AaAb|bBa Bd aabdabb的派生樹的自頂向下的的派生樹的自頂向下的“生長過程生長過程 6.1.3 自頂向下的分析和自底向上自頂向下的分析和自底向上的分析的分析 自底向上的分析方法

22、自底向上的分析方法 經(jīng)過調(diào)查能否可以將一個符號串歸約為給經(jīng)過調(diào)查能否可以將一個符號串歸約為給定文法的開場符號，完成斷定一個符號串定文法的開場符號，完成斷定一個符號串能否為該文法的句子的義務(wù)。能否為該文法的句子的義務(wù)。 和歸約與派生是互逆過程相對應(yīng)，自頂向和歸約與派生是互逆過程相對應(yīng)，自頂向下的分析與自底向上的分析互逆的分析過下的分析與自底向上的分析互逆的分析過程。程。aabdabb的派生樹的自底向上的的派生樹的自底向上的“生長過程生長過程 6.2 上下文無關(guān)文法的化簡上下文無關(guān)文法的化簡 如下文法含有無如下文法含有無用的用的“東西東西 G1：S0|0A|EA|0A|1A|BB_CC0|1|0C

23、|1CD1|1D|2DE0E2|E02 去掉無用去掉無用“東西東西后的文法后的文法 G2：S0|0AA|0A|1A|BB_CC0|1|0C|1C 6.2 上下文無關(guān)文法的化簡上下文無關(guān)文法的化簡 去掉產(chǎn)生式去掉產(chǎn)生式A后后的文法的文法 G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C 去掉產(chǎn)生式去掉產(chǎn)生式AB后的后的文法文法 G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C 可以去掉文法中的無用符號、可以去掉文法中的無用符號、 產(chǎn)生式和產(chǎn)生式和單一產(chǎn)生式。單一產(chǎn)生式。6.2.1 去無用符號去無用符號 無用符號無用符號(useless symbol) (usel

24、ess symbol) 對于恣意對于恣意XVTXVT，假設(shè)存在，假設(shè)存在wL(G)wL(G)，X X出出如今如今w w的派生過程中，即存在的派生過程中，即存在，(VT)(VT)* *，使得，使得S S* *XX* *w w，那么稱，那么稱X X是有用的，否那么，稱是有用的，否那么，稱X X是無用符號。是無用符號。 對對CFG G=(VCFG G=(V，T T，P P，S) S) G G中的符號中的符號X X既能夠是有用的，也能夠是既能夠是有用的，也能夠是無用的。當(dāng)無用的。當(dāng)X X是無用的時候，它既能夠是終是無用的時候，它既能夠是終極符號，也能夠是語法變量。極符號，也能夠是語法變量。6.2.1

25、去無用符號去無用符號 對于恣意對于恣意XVT，假設(shè)，假設(shè)X是有用的，它是有用的，它必需同時滿足如下兩個條件：必需同時滿足如下兩個條件： 存在存在wT*，使得，使得X*w； ，(VT)*，使得，使得S*X。 留意到文法是言語的有窮描畫，所以，留意到文法是言語的有窮描畫，所以，集合集合V，T，P都是有窮的。從而我們有能都是有窮的。從而我們有能夠構(gòu)造出有效的算法，來完成消除文法夠構(gòu)造出有效的算法，來完成消除文法的無用符號的任務(wù)。的無用符號的任務(wù)。 6.2.1 去無用符號去無用符號 算法算法 6-1 6-1 刪除派生不出終極符號行的變量。刪除派生不出終極符號行的變量。輸入：輸入：CFG G=(VCFG

26、 G=(V，T T，P P，S)S)。輸出：輸出：CFG G=(VCFG G=(V，T T，PP，S)S)，VV中不中不含派生不出終極符號行的變量，并且含派生不出終極符號行的變量，并且L(G)=L(G)L(G)=L(G)。 主要步驟：主要步驟： 6.2.1 去無用符號去無用符號 (1) OLDV=;(2) NEWV=A|AwP且且wT*；(3) while OLDVNEWV dobegin(4) OLDV=NEWV；(5) NEWV=OLDVA|AP且且(TOLDV) *end(6) V=NEWV；(7) P= A| AP且且 AV且且(TV)*6.2.1 去無用符號去無用符號 第第(3)條語

27、句控制對條語句控制對NEWV進展迭代更新。進展迭代更新。第一次循環(huán)將那些恰經(jīng)過兩步可以派生出終第一次循環(huán)將那些恰經(jīng)過兩步可以派生出終極符號行的變量放入極符號行的變量放入NEWV；第二次循環(huán)將；第二次循環(huán)將那些恰經(jīng)過三步和某些至少經(jīng)過三步可以派那些恰經(jīng)過三步和某些至少經(jīng)過三步可以派生出終極符號行的變量放入生出終極符號行的變量放入NEWV；，第第n次循環(huán)將那些恰經(jīng)過次循環(huán)將那些恰經(jīng)過n步和某些至少經(jīng)過步和某些至少經(jīng)過n+1步可以派生出終極符號行的變量放入步可以派生出終極符號行的變量放入NEWV。這個循環(huán)不斷進展下去，直到所給。這個循環(huán)不斷進展下去，直到所給文法文法G中的一切可以派生出終極符號行的變

28、中的一切可以派生出終極符號行的變量都被放入量都被放入NEWV中。中。 6.2.1去無用符號去無用符號 定理定理 6-4 6-4 算法算法6-16-1是正確的。是正確的。 證明要點：首先證明對于恣意證明要點：首先證明對于恣意AVAV，A A被被放入放入VV中的充要條件是存在中的充要條件是存在wTwT，A An wn w。再證所構(gòu)造出的文法是等價。再證所構(gòu)造出的文法是等價的。的。(1)(1)對對A A被放入被放入NEWVNEWV的循環(huán)次數(shù)的循環(huán)次數(shù)n n施歸納，施歸納，證明必存在證明必存在wTwT，滿足，滿足A A w w。6.2.1去無用符號去無用符號 (2)施歸納于派生步數(shù)施歸納于派生步數(shù)n，

29、證明假設(shè)，證明假設(shè)An w，那么那么A被算法放入到被算法放入到NEWV中。實踐上，對中。實踐上，對原教材所給的證明進展分析，同時思索算原教材所給的證明進展分析，同時思索算法法6-1的實踐運轉(zhuǎn)，可以證明，的實踐運轉(zhuǎn)，可以證明，A是在第是在第n次次循環(huán)前被放入到循環(huán)前被放入到NEWV中的。中的。(3)證明證明L(G)=L(G) 。顯然有。顯然有L(G) L(G)，所以只需證明所以只需證明L(G)。 6.2.1 去無用符號去無用符號 算法算法 6-2 刪除不出如今任何句型中的語法符號刪除不出如今任何句型中的語法符號。輸入：輸入：CFG G=(V，T，P，S)。輸出：輸出：CFG G=(V，T，P，S

30、)，VT中的中的符號必在符號必在G的某個句型中出現(xiàn)，并且有的某個句型中出現(xiàn)，并且有L(G)=L(G)。主要步驟：主要步驟： 6.2.1 去無用符號去無用符號 主要步驟：主要步驟： (1) OLDV=;(1) OLDV=; (2) OLDT=;(2) OLDT=; (3) NEWV=SA|S(3) NEWV=SA|SAP;AP; (4) NEWT=a|S(4) NEWT=a|SaP;aP;6.2.1去無用符號去無用符號 (5) while OLDVNEWV 或者或者OLDTNEWT do begin(6) OLDV=NEWV;(7) OLDT=NEWT;(8) NEWV=OLDVB| AOLDV

31、且且 ABP 且且BV;(9) NEWT=OLDTa| AOLDV且且 AaP 且且aT; end6.2.1去無用符號去無用符號 (10) V=NEWV;(11) T=NEWT;(12) P= A| AP且且 AV且且(TV)*。6.2.1去無用符號去無用符號定理定理 6-5 算法算法6-2是正確的。是正確的。證明要點：證明要點：(1) 施歸納于派生步數(shù)施歸納于派生步數(shù)n，證明假設(shè)，證明假設(shè)Sn X，那么當(dāng)，那么當(dāng)XV時，時，X在算法中被語句在算法中被語句(3)或或者語句者語句(8)放入放入NEWV；當(dāng)；當(dāng)XT時，它在算時，它在算法中被語句法中被語句(4)或者語句或者語句(9)放入放入NEWT

32、。(2) 對循環(huán)次數(shù)對循環(huán)次數(shù)n施歸納，證明假設(shè)施歸納，證明假設(shè)X被放入被放入NEWT或者或者NEWV中，那么必定存在中，那么必定存在，(NEWVNEWT)*，使得，使得Sn X。(3) 證明證明L(G)=L(G) 。6.2.1去無用符號去無用符號定理定理6-6 對于恣意對于恣意CFL L，L，那么存在不，那么存在不含無用符號的含無用符號的CFG G，使得，使得L(G)=L。證明要點：證明要點：依次用算法依次用算法6-1和算法和算法6-2對文法進展處置，可對文法進展處置，可以得到等價的不含無用符號的文法。以得到等價的不含無用符號的文法。 不可先用算法不可先用算法6-2后用算法后用算法6-1。6

33、.2.1去無用符號去無用符號 例例 6-2-1 設(shè)有如下文法設(shè)有如下文法 SAB|a|BB，Aa，Cb|ABa 先用算法先用算法6-2，文法被化簡成：，文法被化簡成： SAB|a|BB，Aa 再用算法再用算法6-1，可得到文法：，可得到文法： S a，Aa 顯然，該文法中的變量顯然，該文法中的變量A是新的無用變量。是新的無用變量。6.2.2 去去-產(chǎn)生式產(chǎn)生式 -產(chǎn)生式產(chǎn)生式-production 形如形如A的產(chǎn)生式叫做的產(chǎn)生式叫做-產(chǎn)生式。產(chǎn)生式。 -產(chǎn)生式又稱為空產(chǎn)生式產(chǎn)生式又稱為空產(chǎn)生式null production。 可空可空(nullable)變量變量 對于文法對于文法G=(V，T，

34、P，S)中的恣意變量中的恣意變量A，假設(shè)假設(shè)A+，那么稱，那么稱A為可空變量。為可空變量。 6.2.2 去去-產(chǎn)生式產(chǎn)生式 對形如對形如AX1X2Xm的產(chǎn)生式進展調(diào)查，的產(chǎn)生式進展調(diào)查，找 出 文 法 的 可 空 變 量 集找 出 文 法 的 可 空 變 量 集 U ， 然 后 對 于， 然 后 對 于HU，從產(chǎn)生式，從產(chǎn)生式AX1X2Xm中刪除中刪除H中的變量。對于不同的中的變量。對于不同的H，得到不同的，得到不同的A產(chǎn) 生 式 ， 用 這 組產(chǎn) 生 式 ， 用 這 組 A 產(chǎn) 生 式 替 代 產(chǎn) 生 式產(chǎn) 生 式 替 代 產(chǎn) 生 式AX1X2Xm。 必需防止在這個過程中產(chǎn)生新的必需防止在這

35、個過程中產(chǎn)生新的-產(chǎn)生式：產(chǎn)生式：當(dāng)當(dāng) X1，X2，XmU時，不可將時，不可將X1， X 2 ， ， X m 同 時 從 產(chǎn) 生 式同 時 從 產(chǎn) 生 式AX1X2Xm中刪除。中刪除。 6.2.2 去去-產(chǎn)生式產(chǎn)生式 算法算法6-3 求求CFG G的可空變量集的可空變量集U。輸入：輸入：CFG G=(V，T，P，S)。輸出：輸出：G的可空變量集的可空變量集U。主要步驟：主要步驟：(1) OLDU=;(2) NEWU=A| AP;6.2.2 去去-產(chǎn)生式產(chǎn)生式 (3) while NEWUOLDU do begin(4) OLDU = NEWU;(5) NEWU= OLDU A|AP并且并且OL

36、DU* end(6) U=NEWU6.2.2 去去-產(chǎn)生式產(chǎn)生式 定理定理 6-7 對于恣意對于恣意CFG G，存在不含，存在不含-產(chǎn)產(chǎn)生式的生式的CFG G使得使得L(G)=L(G)-。證明：證明： (1) 構(gòu)造構(gòu)造設(shè)設(shè)CFG G=(V，T，P，S) ，用算法用算法6-3求出求出G的可空變量集的可空變量集U，構(gòu)造構(gòu)造P。 6.2.2 去去-產(chǎn)生式產(chǎn)生式 對于對于 AX1X2XmP 將將A12m放入放入P，其中，其中 if XiU then i=Xi或者或者i=； if XiU then i=Xi 要求：在同一產(chǎn)生式中，要求：在同一產(chǎn)生式中，1，2，m不能同時為不能同時為。 6.2.2 去去-

37、產(chǎn)生式產(chǎn)生式 證明對于恣意證明對于恣意wT+，AnG w的充分必要的充分必要條件是條件是A。 必要性：設(shè)必要性：設(shè)AnG w，施歸納于，施歸納于n，證明，證明AmG w成立。成立。 當(dāng)當(dāng)n=1時，由時，由AG w知，知，AwP，按照，按照定理所給的構(gòu)造定理所給的構(gòu)造G的方法，必定有的方法，必定有AwP。所以，。所以，AG w成立。成立。 6.2.2 去去-產(chǎn)生式產(chǎn)生式 設(shè)設(shè)nk時結(jié)論成立時結(jié)論成立(k1)，當(dāng)，當(dāng)n=k+1時時 AX1X2Xm *G w1X2Xm *G w1w2Xm *G w1w2wm 其中其中w1w2wm=w，且，且w1，w2，wmT*。 6.2.2 去去-產(chǎn)生式產(chǎn)生式 留意

38、到留意到w，必存在，必存在1im，wi，設(shè)，設(shè)i，j，k是是w1，w2，wm中一切非空串的中一切非空串的下標(biāo)，并且下標(biāo)，并且1ijkm，即：，即： w= wiwjwk按照按照G的構(gòu)造方法，的構(gòu)造方法，A XiXjXkP 再由歸納假設(shè)，再由歸納假設(shè)，Xi*G wi，Xj*G wj，Xk*G wk。6.2.2 去去-產(chǎn)生式產(chǎn)生式 A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk所以，結(jié)論對所以，結(jié)論對n=k+1成立。由歸納法原理，成立。由歸納法原理，結(jié)論對一切的結(jié)論對一切的n成立。成立。6.2.2 去去-產(chǎn)生式產(chǎn)生式充分性：設(shè)充分性：設(shè)AmG w，施歸納于，施歸納于

39、m，證明，證明AnG w成立。成立。當(dāng)當(dāng)m=1時，由時，由AG w知，知，AwP，按照，按照定理所給的構(gòu)造定理所給的構(gòu)造G的方法，必定有的方法，必定有AP。Aw是經(jīng)過刪除產(chǎn)生式是經(jīng)過刪除產(chǎn)生式A右部中的可右部中的可空變量而構(gòu)造出來的，所以，空變量而構(gòu)造出來的，所以，AG *G w 成立。成立。 6.2.2 去去-產(chǎn)生式產(chǎn)生式設(shè)設(shè)nk時結(jié)論成立時結(jié)論成立(k1)，當(dāng)，當(dāng)m=k+1時時A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w其中其中Xi*G wi，Xj*G wj，Xk*G wk 。6.2.2 去去-產(chǎn)生式產(chǎn)生式闡明闡明A XiXjXkP。按照。按照G的構(gòu)

40、造方法的構(gòu)造方法，必定存在，必定存在A X1X2XmP，而且，而且Xi，Xj，XkX1，X2，XmX1，X2，Xm-Xi，Xj，XkU從而，從而，AG X1X2Xm *G XiXjXk6.2.2 去去-產(chǎn)生式產(chǎn)生式再根據(jù)再根據(jù)Xi*G wi，Xj*G wj，Xk*G wk和歸納假設(shè)，有和歸納假設(shè)，有Xi*G wi，Xj*G wj，Xk*G wk。這闡明，如下派生成立：這闡明，如下派生成立： AG X1X2Xm *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w6.2.2 去去-產(chǎn)生式產(chǎn)生式闡明結(jié)論對闡明結(jié)論對m=k+1m=k+1成立。由歸納法原理，結(jié)論成立。由歸

41、納法原理，結(jié)論對恣意對恣意m m成立。成立。留意到留意到A A 的恣意性，當(dāng)?shù)捻б庑?，?dāng)S=AS=A時結(jié)論成立。即：時結(jié)論成立。即：S S* *G w G w 的充分必要條件是的充分必要條件是S S* *G wG w亦即：亦即：L(G)=L(G)-L(G)=L(G)-。定理得證。定理得證。 6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 文法文法Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E存在派生：存在派生：ETFPid6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 Gexp3：EE+T|E-T|T*F|T/F|

42、FP|(E)|N(L)|idTT*F|T/F| FP| (E)|N(L)|idFFP| (E)|N(L)|idP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E該文法中不存在類似的派生。該文法中不存在類似的派生。6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 單一產(chǎn)生式單一產(chǎn)生式(unit production) (unit production) 形如形如A AB B的產(chǎn)生式稱為單一產(chǎn)生式。的產(chǎn)生式稱為單一產(chǎn)生式。 定理定理 6-8 6-8對于恣意對于恣意CFG GCFG G，L(G)L(G)，存在，存在等價的等價的CFG G1CFG G1，G1G1不含無用符號、不含

43、無用符號、-產(chǎn)生產(chǎn)生式和單一產(chǎn)生式。式和單一產(chǎn)生式。 滿足本定理的滿足本定理的CFGCFG為化簡過的文法。為化簡過的文法。 已有去無用符號和去已有去無用符號和去-產(chǎn)生式的結(jié)論，所產(chǎn)生式的結(jié)論，所以只討論去單一產(chǎn)生式的問題。以只討論去單一產(chǎn)生式的問題。 6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 證明要點：證明要點： 1構(gòu)造構(gòu)造G2，滿足，滿足L(G2)=L(G)，并且，并且G2中不含單一產(chǎn)生式。中不含單一產(chǎn)生式。 用非單一產(chǎn)生式用非單一產(chǎn)生式A1取代取代A1*G An用到的產(chǎn)生式系列用到的產(chǎn)生式系列 A1A2，A2A3，An-1An，An。其中，。其中，A1A2，A2A3，An-1An都是單一產(chǎn)生式

44、。都是單一產(chǎn)生式。n1 6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 2 2 證明證明L(G2)=L(G)L(G2)=L(G)。 用用A1A1所完成的派生所完成的派生A1A1與產(chǎn)生式系列與產(chǎn)生式系列A1A1A2A2，A2A2A3A3，An-1An-1AnAn，AnAn所所完成的派生完成的派生A1A1* *G AnG An相對應(yīng)。相對應(yīng)。在原文法中能夠會出現(xiàn)一個變量在派生過程中在原文法中能夠會出現(xiàn)一個變量在派生過程中循環(huán)出現(xiàn)的情況，在循環(huán)出現(xiàn)的情況，在wL(G) wL(G) 證明證明w L(G2)w L(G2)的過程中，要取的過程中，要取w w在在G G中的一個最短的最左派中的一個最短的最左派生。生。S

45、=0S=0G1G1G2G2GGGn=wGn=w6.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 3 3刪除刪除G2G2中的無用符號。中的無用符號。由于在刪除單一產(chǎn)生式后，文法中能夠出由于在刪除單一產(chǎn)生式后，文法中能夠出現(xiàn)新的無用符號，因此，我們還需求再次現(xiàn)新的無用符號，因此，我們還需求再次刪除新出現(xiàn)的無用符號。刪除新出現(xiàn)的無用符號。 此外，在去此外，在去-產(chǎn)生式后能夠會產(chǎn)生新的單產(chǎn)生式后能夠會產(chǎn)生新的單一產(chǎn)生式，也能夠會引進新的無用符號。一產(chǎn)生式，也能夠會引進新的無用符號。這是值得留意的。這是值得留意的。 6.3 喬姆斯基范式喬姆斯基范式 喬姆斯基范式文法喬姆斯基范式文法(Chomsky normal f

46、orm (Chomsky normal form ，CNF)CNF)簡稱為簡稱為ChomskyChomsky文法，或文法，或ChomskyChomsky范范式。式。 CFG G=(VCFG G=(V，T T，P P，S)S)中的產(chǎn)生式方式：中的產(chǎn)生式方式： A ABCBC，A Aa a 其中，其中，A A、B B、CVCV，aTaT。 CNFCNF中，不允許有中，不允許有-產(chǎn)生式、單一產(chǎn)生式產(chǎn)生式、單一產(chǎn)生式。 6.3 喬姆斯基范式喬姆斯基范式 例例 6-3-1 試將文法試將文法Gexp4轉(zhuǎn)換成等價的轉(zhuǎn)換成等價的 GNF。 Gexp4：EE+T| T*F|FP| (E)| idTT*F| FP

47、| (E) |idFFP| (E) |idP(E) |id 可以分兩步走可以分兩步走 變成變成A a和和A A1A2An的方式。的方式。 變成變成CNF。第一步第一步EEA+T| T A*F|F AP| A(EA5| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+A*AA(A) 第二步第二步 GexpCNF：EEA1| TA2E FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+A*AA(A)A1A+T A2A*FA3APA4EA) 6.3 喬姆斯基范式喬姆斯基范式定理定理6-9

48、6-9 對于恣意對于恣意CFG GCFG G，L(G)L(G)，存在等，存在等價的價的 CNF G2 CNF G2 。 證明要點：證明要點：1. 1. 構(gòu)造構(gòu)造CNFCNF按照上述例子所描畫的轉(zhuǎn)換方法，在構(gòu)造給按照上述例子所描畫的轉(zhuǎn)換方法，在構(gòu)造給定定CFGCFG的的CNFCNF時，可以分兩步走。時，可以分兩步走。假設(shè)假設(shè)G G為化簡過的文法為化簡過的文法構(gòu)造構(gòu)造G1=(V1G1=(V1，T T，P1P1，S) G1S) G1中的產(chǎn)生式都是中的產(chǎn)生式都是形如形如A AB1B2BmB1B2Bm和和A Aa a的產(chǎn)生式，其中，的產(chǎn)生式，其中，A A，B1B1，B2B2，BmV1BmV1，aTaT，

49、m2 m2 6.3 喬姆斯基范式喬姆斯基范式 構(gòu)造構(gòu)造CNF G2=(V2，T，P2，S)。 m3時，引入新變量：時，引入新變量：B1、B2、Bm-2，將，將G1的形如的形如AA1A2Am的產(chǎn)生式交換的產(chǎn)生式交換成成 AA1B1 B1A2B2 Bm-2Am-1Am6.3 喬姆斯基范式喬姆斯基范式2. 構(gòu)造的正確性證明。構(gòu)造的正確性證明。按照上述構(gòu)造，證明被交換的產(chǎn)生式是等價按照上述構(gòu)造，證明被交換的產(chǎn)生式是等價的。的。例如：在第二步中例如：在第二步中A A1B1， B1A2B2 ， ， Bm-2Am-1Am與與AA1A2Am等價。等價。6.3 喬姆斯基范式喬姆斯基范式 例例 6-6 6-6 試

50、將以下文法轉(zhuǎn)換成等價的試將以下文法轉(zhuǎn)換成等價的 CNF CNF。 S SbA | aBbA | aB A AbAA | aS | abAA | aS | a B BaBB | bS | b aBB | bS | b 6.3 喬姆斯基范式喬姆斯基范式 先引入變量先引入變量Ba，Bb和產(chǎn)生式和產(chǎn)生式Baa，Bbb ，完成第一步變換。，完成第一步變換。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb6.3 喬姆斯基范式喬姆斯基范式 引入新變量引入新變量B1、B2 SBbA | BaBABbB1 | BaS | aBBaB2 | BbS | b B

51、aa Bbb B1AA B2BB6.3 喬姆斯基范式喬姆斯基范式 不能由于原來有產(chǎn)生式不能由于原來有產(chǎn)生式A a和和B b而放棄而放棄引進變量引進變量Ba 、Bb和產(chǎn)生式和產(chǎn)生式Baa 、Bbb。 L(A)=x | xa，b+ & x中中a的個數(shù)比的個數(shù)比b的的個數(shù)恰多個數(shù)恰多1個個。 L(B)=x | xa，b+ & x中中b的個數(shù)比的個數(shù)比a的的個數(shù)恰多個數(shù)恰多1個個。 L(Ba)= a 。 L(Bb)= b 。 6.4 格雷巴赫范式格雷巴赫范式格雷巴赫范式文法格雷巴赫范式文法(Greibach normal (Greibach normal form ,GNF)form

52、,GNF)簡稱為簡稱為GreibachGreibach文法，或文法，或GreibachGreibach范式。范式。A Aa a 其中，其中，AVAV，aTaT，VV* * 。在在GNFGNF中，有如下兩種方式的產(chǎn)生式中，有如下兩種方式的產(chǎn)生式A Aa aA AaA1A2AmaA1A2Am(m1) (m1) 6.4 格雷巴赫范式格雷巴赫范式 右線性文法是一種特殊的右線性文法是一種特殊的GNF。 由于由于GNF中不存中不存-產(chǎn)生式，所以對恣意的產(chǎn)生式，所以對恣意的GNF G，L(G)。 當(dāng)當(dāng)L(G)時，可以找到一個時，可以找到一個GNF G，使，使得得 L(G)=L(G) 。 經(jīng)過化簡的經(jīng)過化簡的

53、CFG，都有一個等價的，都有一個等價的GNF。 6.4 格雷巴赫范式格雷巴赫范式引理引理 6-1 6-1 對于恣意的對于恣意的CFG G=(VCFG G=(V，T T，P P，S)S)，A ABPBP，且，且G G中一切的中一切的B B產(chǎn)生式為產(chǎn)生式為 B B1 |2 |n 1 |2 |n 取取G1=( VG1=( V，T T，P1P1，S)S)P1=(P-AP1=(P-AB)AB)A11，A A22，A Ann那么，那么，L(G1)=L(G)L(G1)=L(G)。 6.4 格雷巴赫范式格雷巴赫范式 證明證明 以下兩組產(chǎn)生式等價以下兩組產(chǎn)生式等價 AB ；B1 |2 |n A1，A2，An 6

54、.4 格雷巴赫范式格雷巴赫范式 遞歸遞歸(recursive) (recursive) 假設(shè)假設(shè)G G中存在形如中存在形如A AnAnA的派生，那么的派生，那么稱該派生是關(guān)于變量稱該派生是關(guān)于變量A A遞歸的，簡稱為遞歸遞歸的，簡稱為遞歸派生。派生。 當(dāng)當(dāng)n=1n=1時，稱該派生關(guān)于變量時，稱該派生關(guān)于變量A A直接遞歸直接遞歸(directly recursive)(directly recursive)，簡稱為直接遞歸，簡稱為直接遞歸派生。派生。 形如形如A AAA的產(chǎn)生式是變量的產(chǎn)生式是變量A A的直接遞歸的直接遞歸的的(directly recursive)(directly recu

55、rsive)產(chǎn)生式。產(chǎn)生式。6.4 格雷巴赫范式格雷巴赫范式 當(dāng)當(dāng)n2時，稱該派生是關(guān)于變量時，稱該派生是關(guān)于變量A的間接遞的間接遞歸歸(indirectly recursive)派生。簡稱為間接派生。簡稱為間接遞歸派生。遞歸派生。 當(dāng)當(dāng)=時，稱相應(yīng)的時，稱相應(yīng)的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)左遞歸左遞歸(left-recursive)； 當(dāng)當(dāng)=時，稱相應(yīng)的時，稱相應(yīng)的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)右遞歸右遞歸(right-recursive)。6.4 格雷巴赫范式格雷巴赫范式 引理引理 6-2 6-2 對于恣意的對于恣意的CFG G=(VC

56、FG G=(V，T T，P P，S)S)，G G中一切中一切A A的產(chǎn)生式的產(chǎn)生式 A1 |2 |mA1B |2 B |m BB1 |2 |nB1B |2 B |n B 可以被等價地交換為產(chǎn)生式組可以被等價地交換為產(chǎn)生式組AA1 |A2 |AnA1 |2 |m6.4 格雷巴赫范式格雷巴赫范式 證明要點：證明要點： 用直接右遞歸取代原來的直接左遞歸。用直接右遞歸取代原來的直接左遞歸。 兩組產(chǎn)生式產(chǎn)生的符號串都是兩組產(chǎn)生式產(chǎn)生的符號串都是 121.hhhhkqq 前者是先產(chǎn)生前者是先產(chǎn)生 然后產(chǎn)生然后產(chǎn)生k 。 121.hhhhqq6.4 格雷巴赫范式格雷巴赫范式 后者先產(chǎn)生后者先產(chǎn)生k 。 然后產(chǎn)生然后產(chǎn)生121.hhhhqq6.4 格雷巴赫范式格雷巴赫范式121211.