形式語言與自動(dòng)機(jī)理論電子教案06

1、第6章 上下文無關(guān)語言 Gbra：SS(S)| L(Gbra)不是RL,是CFL高級(jí)程序設(shè)計(jì)語言的絕大多數(shù)語法結(jié)構(gòu)都可以用上下文無關(guān)文法(CFG)描述。BNF(巴科斯范式：Backus normal form，又叫Backus-naur form)。2022/10/11第6章 上下文無關(guān)語言 主要內(nèi)容關(guān)于CFL的分析派生和歸約、派生樹CFG的化簡 無用符、單一產(chǎn)生式、空產(chǎn)生式CFG的范式 CNFGNFCFG的自嵌套特性 2022/10/12第6章 上下文無關(guān)語言 重點(diǎn)CFG的化簡。CFG到GNF的轉(zhuǎn)換。 難點(diǎn)CFG到GNF的轉(zhuǎn)換，特別是其中的用右遞歸替換左遞歸的問題。2022/10/136.1

2、 上下文無關(guān)語言 文法G=(V，T，P，S)被稱為是上下文無關(guān)的。 如果除了形如A的產(chǎn)生式之外，對(duì)于P，均有|，并且V成立。關(guān)鍵：對(duì)于AV，如果AP，則無論A出現(xiàn)在句型的任何位置，我們都可以將A替換成，而不考慮A的上下文。 2022/10/146.1.1 上下文無關(guān)文法的派生樹 算術(shù)表達(dá)式的文法 Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2022/10/156.1.1 上下文無關(guān)文法的派生樹 算術(shù)表達(dá)式x+x/y2的不同派生 EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx

3、+x/Fx+x/FPx+x/PPx+x/yPx+x/y2 EE+TE+T/FE+T/FPE+T/F2E+T/P2E+T/y2 E+F/y2 E+P/y2 E+x/y2 T+x/y2 F+x/y2 P+x/y2x+x/y2 EE+TT+TT+T/FF+T/FF+T/FPP+T/FPx+T/FPx+F/FPx+F/F2x+F/P2x+P/P2x+P/y2x+x/y2 2022/10/166.1.1 上下文無關(guān)文法的派生樹文法Gexp1句子x+x/y2的結(jié)構(gòu)。 2022/10/176.1.1 上下文無關(guān)文法的派生樹派生樹(derivation tree) 一棵(有序)樹(ordered tree)

4、樹的每個(gè)頂點(diǎn)有一個(gè)標(biāo)記X，且XVT 樹根的標(biāo)記為S； 如果非葉子頂點(diǎn)v標(biāo)記為A，v的兒子從左到右依次為v1，v2，vn，并且它們分別標(biāo)記為X1，X2，Xn，則AX1X2XnP；如果X是一個(gè)非葉子頂點(diǎn)的標(biāo)記，則XV；如果頂點(diǎn)v標(biāo)記為，則v是該樹的葉子，并且v是其父頂點(diǎn)的惟一兒子。 2022/10/186.1.1 上下文無關(guān)文法的派生樹別稱生成樹分析樹(parse tree)語法樹(syntax tree) 順序v1，v2是派生樹T的兩個(gè)不同頂點(diǎn)，如果存在頂點(diǎn)v，v至少有兩個(gè)兒子，使得v1是v的較左兒子的后代，v2是v的較右兒子的后代，則稱頂點(diǎn)v1在頂點(diǎn)v2的左邊，頂點(diǎn)v2在頂點(diǎn)v1的右邊。 20

5、22/10/196.1.1 上下文無關(guān)文法的派生樹結(jié)果(yield) 派生樹T的所有葉子頂點(diǎn)從左到右依次標(biāo)記為X1，X2，Xn，則稱符號(hào)串X1X2Xn是T的結(jié)果。 一個(gè)文法可以有多棵派生樹，它們可以有不同的結(jié)果。句型的派生樹：“G的結(jié)果為的派生樹”。2022/10/1106.1.1 上下文無關(guān)文法的派生樹派生子樹(subtree) 滿足派生樹定義中除了對(duì)跟結(jié)點(diǎn)的標(biāo)記的要求以外各條的樹叫派生子樹(subtree)。如果這個(gè)子樹的根標(biāo)記為A，則稱之為A子樹。 惟一差別是根結(jié)點(diǎn)可以標(biāo)記非開始符號(hào)。2022/10/1116.1.1 上下文無關(guān)文法的派生樹定理6-1 設(shè)CFG G=(V，T，P，S)，S

6、*的充分必要條件為G有一棵結(jié)果為的派生樹。證明：證一個(gè)更為一般的結(jié)論：對(duì)于任意AV，A*的充分必要條件為G有一棵結(jié)果為的A-子樹。 充分性：設(shè)G有一棵結(jié)果為的A-子樹，非葉子頂點(diǎn)的個(gè)數(shù)n施歸納，證明A*成立。 2022/10/1126.1.1 上下文無關(guān)文法的派生樹設(shè)A-子樹有k+1個(gè)非葉子頂點(diǎn)，根頂點(diǎn)A的兒子從左到右依次為v1，v2，vm，并且它們分別標(biāo)記為X1，X2，Xm 。 AX1X2XmP 。 以X1，X2，Xm為根的子樹的結(jié)果依次為1，2，m 。 X1，X2，Xm為根的子樹的非葉子頂點(diǎn)的個(gè)數(shù)均不大于k。 2022/10/1136.1.1 上下文無關(guān)文法的派生樹 X1*1X2*2Xm*

7、m而且=12m2022/10/1146.1.1 上下文無關(guān)文法的派生樹AX1X2Xm *1X2Xm *12Xm *12m2022/10/1156.1.1 上下文無關(guān)文法的派生樹2022/10/1166.1.1 上下文無關(guān)文法的派生樹必要性設(shè)An，現(xiàn)施歸納于派生步數(shù)n，證明存在結(jié)果為的A-子樹。設(shè)nk(k1)時(shí)結(jié)論成立，往證當(dāng)n=k+1時(shí)結(jié)論也成立：令A(yù)k+1，則有：AX1X2Xm *1X2Xm *12Xm *12m 2022/10/1176.1.1 上下文無關(guān)文法的派生樹2022/10/1186.1.1 上下文無關(guān)文法的派生樹例6-1設(shè)Gbra：SS(S)|，()()和(S)(S)的派生樹。2

8、022/10/1196.1.1 上下文無關(guān)文法的派生樹關(guān)于標(biāo)記的結(jié)點(diǎn)2022/10/1206.1.1 上下文無關(guān)文法的派生樹最左派生(leftmost derivation) 的派生過程中，每一步都是對(duì)當(dāng)前句型的最左變量進(jìn)行替換。左句型(left sentencial form)最左派生得到的句型可叫做左句型。最右歸約(rightmost reduction)與最左派生對(duì)相的歸約叫做最有歸約。2022/10/1216.1.1 上下文無關(guān)文法的派生樹最右派生(rightmost derivation) 的派生過程中，每一步都是對(duì)當(dāng)前句型的最右變量進(jìn)行替換。右句型(right sentencial

9、 form)最右派生得到的句型可叫做右句型。最左歸約(leftmost reduction)與最左派生對(duì)相的歸約叫做最右歸約。2022/10/1226.1.1 上下文無關(guān)文法的派生樹規(guī)范派生(normal derivation)最右派生。規(guī)范句型(normal sentencial form)規(guī)范派生產(chǎn)生的句型。規(guī)范歸約(normal reduction)最左歸約。2022/10/1236.1.1 上下文無關(guān)文法的派生樹定理6-2 如果是CFG G的一個(gè)句型，則G中存在的最左派生和最右派生。證明：基本思路：對(duì)派生的步數(shù)n施歸納，證明對(duì)于任意AV，如果An，在G中，存在對(duì)應(yīng)的從A到的最左派生：A

10、n左。 2022/10/1246.1.1 上下文無關(guān)文法的派生樹AX1X2Xm *1X2Xm *12Xm *12mA左X1X2Xm *左1X2Xm *左12Xm *左12m 同理可證，句型有最右派生。 2022/10/1256.1.1 上下文無關(guān)文法的派生樹定理6-3 如果是CFG G的一個(gè)句型，的派生樹與最左派生和最右派生是一一對(duì)應(yīng)的，但是，這棵派生樹可以對(duì)應(yīng)多個(gè)不同的派生。2022/10/1266.1.2 二義性 簡單算術(shù)表達(dá)式的二義性文法Gexp2：EE+E|E-E|E/E|E*EE EE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2022/10

11、/1276.1.2 二義性 E E+E x+E x+E/E x+x/E x+x/EEx+x/yEx+x/y2句子x+x/y2在文法中的三個(gè)不同的最左派生 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+x/EE x+x/yE x+x/y2 2022/10/1286.1.2 二義性 對(duì)應(yīng)3個(gè)不同的語法樹2022/10/1296.1.2 二義性 二義性(ambiguity) CFG G=(V，T，P，S)，如果存在wL(G)，w至少有兩棵不同的派生樹，則稱G是二義性的。否則，G為非二義性的。二義性的問題是

12、不可解的(unsolvable)問題。 2022/10/1306.1.2 二義性 例6-2 用其他方法消除二義性。Gifa：Sif E then S else S | if E then SGifm：SU|MUif E then SUif E then M else UMif E then M else M|SGifh：STS|CSCif E thenT CS else 2022/10/1316.1.2 二義性 例 6-3 設(shè)Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法產(chǎn)生語言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C

13、3|12|1D2D12|1D2 語言Lambiguity不存在非二義性的文法。 2022/10/1326.1.2 二義性 固有二義性的(inherent ambiguity) 如果語言L不存在非二義性文法，則稱L是固有二義性的，又稱L是先天二義性的。文法可以是二義性的。語言可以是固有二義性的。 2022/10/1336.1.3 自頂向下的分析和自底向上的分析 自頂向下的分析方法通過考察是否可以從給定文法的開始符號(hào)派生出一個(gè)符號(hào)串，可以判定一個(gè)符號(hào)串是否為該文法的句子。例SaAb|bBaAaAb|bBaBd 2022/10/134aabdabb的派生樹的自頂向下的“生長”過程 2022/10/1

14、356.1.3 自頂向下的分析和自底向上的分析 自底向上的分析方法通過考察是否可以將一個(gè)符號(hào)串歸約為給定文法的開始符號(hào)，完成判定一個(gè)符號(hào)串是否為該文法的句子的任務(wù)。和歸約與派生是互逆過程相對(duì)應(yīng)，自頂向下的分析與自底向上的分析互逆的分析過程。2022/10/136aabdabb的派生樹的自底向上的“生長”過程 2022/10/1376.2 上下文無關(guān)文法的化簡 如下文法含有無用的“東西”G1：S0|0A|EA|0A|1A|BB_CC0|1|0C|1CD1|1D|2DE0E2|E02 去掉無用“東西”后的文法G2：S0|0AA|0A|1A|BB_CC0|1|0C|1C 2022/10/1386.2

15、 上下文無關(guān)文法的化簡去掉產(chǎn)生式A后的文法G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C 去掉產(chǎn)生式AB后的文法G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C 可以去掉文法中的無用符號(hào)、 產(chǎn)生式和單一產(chǎn)生式。2022/10/1396.2.1 去無用符號(hào) 無用符號(hào)(useless symbol) 對(duì)于任意XVT，如果存在wL(G)，X出現(xiàn)在w的派生過程中，即存在，(VT)*，使得S*X*w，則稱X是有用的，否則，稱X是無用符號(hào)。對(duì)CFG G=(V，T，P，S) G中的符號(hào)X既可能是有用的，也可能是無用的。當(dāng)X是無用的時(shí)候，它既可能是終極符號(hào)，也可能是語法變量

16、。2022/10/1406.2.1 去無用符號(hào) 對(duì)于任意XVT，如果X是有用的，它必須同時(shí)滿足如下兩個(gè)條件： 存在wT*，使得X*w； ，(VT)*，使得S*X。 注意到文法是語言的有窮描述，所以，集合V，T，P都是有窮的。從而我們有可能構(gòu)造出有效的算法，來完成消除文法的無用符號(hào)的工作。 2022/10/1416.2.1 去無用符號(hào) 算法 6-1 刪除派生不出終極符號(hào)行的變量。輸入：CFG G=(V，T，P，S)。輸出：CFG G=(V，T，P，S)，V中不含派生不出終極符號(hào)行的變量，并且L(G)=L(G)。 主要步驟： 2022/10/1426.2.1 去無用符號(hào) (1) OLDV=;(2)

17、 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)*2022/10/1436.2.1 去無用符號(hào) 第(3)條語句控制對(duì)NEWV進(jìn)行迭代更新。第一次循環(huán)將那些恰經(jīng)過兩步可以派生出終極符號(hào)行的變量放入NEWV；第二次循環(huán)將那些恰經(jīng)過三步和某些至少經(jīng)過三步可以派生出終極符號(hào)行的變量放入NEWV；，第n次循環(huán)將那些恰經(jīng)過n步和某些至少經(jīng)過n+1步可以派生出終極符號(hào)行的變量放入NEWV。這個(gè)循環(huán)一直進(jìn)行下去，直到所給文法

18、G中的所有可以派生出終極符號(hào)行的變量都被放入NEWV中。 2022/10/1446.2.1去無用符號(hào) 定理 6-4 算法6-1是正確的。 證明要點(diǎn)：首先證明對(duì)于任意AV，A被放入V中的充要條件是存在wT，An w。再證所構(gòu)造出的文法是等價(jià)的。(1)對(duì)A被放入NEWV的循環(huán)次數(shù)n施歸納，證明必存在wT，滿足A w。2022/10/1456.2.1去無用符號(hào) (2)施歸納于派生步數(shù)n，證明如果An w，則A被算法放入到NEWV中。實(shí)際上，對(duì)原教材所給的證明進(jìn)行分析，同時(shí)考慮算法6-1的實(shí)際運(yùn)行，可以證明，A是在第n次循環(huán)前被放入到NEWV中的。(3)證明L(G)=L(G) 。顯然有L(G) L(G

19、)，所以只需證明L(G)。 2022/10/1466.2.1 去無用符號(hào) 算法 6-2 刪除不出現(xiàn)在任何句型中的語法符號(hào)。輸入：CFG G=(V，T，P，S)。輸出：CFG G=(V，T，P，S)，VT中的符號(hào)必在G的某個(gè)句型中出現(xiàn)，并且有L(G)=L(G)。主要步驟： 2022/10/1476.2.1 去無用符號(hào) 主要步驟：(1) OLDV=;(2) OLDT=;(3) NEWV=SA|SAP;(4) NEWT=a|SaP;2022/10/1486.2.1去無用符號(hào) (5) while OLDVNEWV 或者OLDTNEWT do begin(6) OLDV=NEWV;(7) OLDT=NE

20、WT;(8) NEWV=OLDVB| AOLDV且 ABP 且BV;(9) NEWT=OLDTa| AOLDV且 AaP 且aT; end2022/10/1496.2.1去無用符號(hào) (10) V=NEWV;(11) T=NEWT;(12) P= A| AP且 AV且(TV)*。2022/10/1506.2.1去無用符號(hào)定理 6-5 算法6-2是正確的。證明要點(diǎn)：(1)施歸納于派生步數(shù)n，證明如果Sn X，則當(dāng)XV時(shí)，X在算法中被語句(3)或者語句(8)放入NEWV；當(dāng)XT時(shí)，它在算法中被語句(4)或者語句(9)放入NEWT。(2)對(duì)循環(huán)次數(shù)n施歸納，證明如果X被放入NEWT或者NEWV中，則必

21、定存在，(NEWVNEWT)*，使得Sn X。(3) 證明L(G)=L(G) 。2022/10/1516.2.1去無用符號(hào)定理6-6 對(duì)于任意CFL L，L，則存在不含無用符號(hào)的CFG G，使得L(G)=L。證明要點(diǎn)：依次用算法6-1和算法6-2對(duì)文法進(jìn)行處理，可以得到等價(jià)的不含無用符號(hào)的文法。 不可先用算法6-2后用算法6-1。2022/10/1526.2.1去無用符號(hào)例 6-2-1 設(shè)有如下文法 SAB|a|BB，Aa，Cb|ABa先用算法6-2，文法被化簡成： SAB|a|BB，Aa再用算法6-1，可得到文法： S a，Aa顯然，該文法中的變量A是新的無用變量。2022/10/1536.

22、2.2 去-產(chǎn)生式 -產(chǎn)生式（-production） 形如A的產(chǎn)生式叫做-產(chǎn)生式。 -產(chǎn)生式又稱為空產(chǎn)生式（null production。 可空(nullable)變量對(duì)于文法G=(V，T，P，S)中的任意變量A，如果A+，則稱A為可空變量。 2022/10/1546.2.2 去-產(chǎn)生式 對(duì)形如AX1X2Xm的產(chǎn)生式進(jìn)行考察，找出文法的可空變量集U，然后對(duì)于HU，從產(chǎn)生式AX1X2Xm中刪除H中的變量。對(duì)于不同的H，得到不同的A產(chǎn)生式，用這組A產(chǎn)生式替代產(chǎn)生式AX1X2Xm。必須避免在這個(gè)過程中產(chǎn)生新的-產(chǎn)生式：當(dāng) X1，X2，XmU時(shí)，不可將X1，X2，Xm同時(shí)從產(chǎn)生式AX1X2Xm中刪

23、除。 2022/10/1556.2.2 去-產(chǎn)生式 算法6-3 求CFG G的可空變量集U。輸入：CFG G=(V，T，P，S)。輸出：G的可空變量集U。主要步驟：(1)OLDU=;(2) NEWU=A| AP;2022/10/1566.2.2 去-產(chǎn)生式 (3)while NEWUOLDU do begin(4)OLDU = NEWU;(5) NEWU= OLDU A|AP并且OLDU* end(6)U=NEWU2022/10/1576.2.2 去-產(chǎn)生式 定理 6-7 對(duì)于任意CFG G，存在不含-產(chǎn)生式的CFG G使得L(G)=L(G)-。證明： (1) 構(gòu)造設(shè)CFG G=(V，T，P，

24、S) ，用算法6-3求出G的可空變量集U，構(gòu)造P。 2022/10/1586.2.2 去-產(chǎn)生式 對(duì)于 AX1X2XmP 將A12m放入P，其中if XiU then i=Xi或者i=；if XiU then i=Xi要求：在同一產(chǎn)生式中，1，2，m不能同時(shí)為。 2022/10/1596.2.2 去-產(chǎn)生式 證明對(duì)于任意wT+，AnG w的充分必要條件是A。必要性：設(shè)AnG w，施歸納于n，證明AmG w成立。 當(dāng)n=1時(shí)，由AG w知，AwP，按照定理所給的構(gòu)造G的方法，必定有AwP。所以，AG w成立。 2022/10/1606.2.2 去-產(chǎn)生式 設(shè)nk時(shí)結(jié)論成立(k1)，當(dāng)n=k+1時(shí)

25、AX1X2Xm *G w1X2Xm *G w1w2Xm *G w1w2wm其中w1w2wm=w，且w1，w2，wmT*。 2022/10/1616.2.2 去-產(chǎn)生式 注意到w，必存在1im，wi，設(shè)i，j，k是w1，w2，wm中所有非空串的下標(biāo)，并且1ijkm，即： w= wiwjwk按照G的構(gòu)造方法，A XiXjXkP 再由歸納假設(shè)，Xi*G wi，Xj*G wj，Xk*G wk。2022/10/1626.2.2 去-產(chǎn)生式 A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk所以，結(jié)論對(duì)n=k+1成立。由歸納法原理，結(jié)論對(duì)所有的n成立。2022/10/1636

26、.2.2 去-產(chǎn)生式充分性：設(shè)AmG w，施歸納于m，證明AnG w成立。當(dāng)m=1時(shí)，由AG w知，AwP，按照定理所給的構(gòu)造G的方法，必定有AP。Aw是通過刪除產(chǎn)生式A右部中的可空變量而構(gòu)造出來的，所以，AG *G w 成立。 2022/10/1646.2.2 去-產(chǎn)生式設(shè)nk時(shí)結(jié)論成立(k1)，當(dāng)m=k+1時(shí)A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w其中Xi*G wi，Xj*G wj，Xk*G wk 。2022/10/1656.2.2 去-產(chǎn)生式表明A XiXjXkP。按照G的構(gòu)造方法，必定存在A X1X2XmP，而且Xi，Xj，XkX1，X2，X

27、mX1，X2，Xm-Xi，Xj，XkU從而，AG X1X2Xm *G XiXjXk2022/10/1666.2.2 去-產(chǎn)生式再根據(jù)Xi*G wi，Xj*G wj，Xk*G wk和歸納假設(shè)，有Xi*G wi，Xj*G wj，Xk*G wk。這表明，如下派生成立： AG X1X2Xm *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w2022/10/1676.2.2 去-產(chǎn)生式表明結(jié)論對(duì)m=k+1成立。由歸納法原理，結(jié)論對(duì)任意m成立。注意到A 的任意性，當(dāng)S=A時(shí)結(jié)論成立。即：S*G w 的充分必要條件是S*G w亦即：L(G)=L(G)-。定理得證。 2022/

28、10/1686.2.3 去單一產(chǎn)生式 文法Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E存在派生：ETFPid2022/10/1696.2.3 去單一產(chǎn)生式 Gexp3：EE+T|E-T|T*F|T/F|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該文法中不存在類似的派生。2022/10/1706.2.3 去單一產(chǎn)生式 單一產(chǎn)生式(unit pro

29、duction) 形如AB的產(chǎn)生式稱為單一產(chǎn)生式。 定理 6-8對(duì)于任意CFG G，L(G)，存在等價(jià)的CFG G1，G1不含無用符號(hào)、-產(chǎn)生式和單一產(chǎn)生式。 滿足本定理的CFG為化簡過的文法。已有去無用符號(hào)和去-產(chǎn)生式的結(jié)論，所以只討論去單一產(chǎn)生式的問題。 2022/10/1716.2.3 去單一產(chǎn)生式 證明要點(diǎn)： （1）構(gòu)造G2，滿足L(G2)=L(G)，并且G2中不含單一產(chǎn)生式。用非單一產(chǎn)生式A1取代A1*G An用到的產(chǎn)生式系列 A1A2，A2A3，An-1An，An。其中，A1A2，A2A3，An-1An都是單一產(chǎn)生式。（n1） 2022/10/1726.2.3 去單一產(chǎn)生式 （2）

30、 證明L(G2)=L(G)。 用A1所完成的派生A1與產(chǎn)生式系列A1A2，A2A3，An-1An，An所完成的派生A1*G An相對(duì)應(yīng)。在原文法中可能會(huì)出現(xiàn)一個(gè)變量在派生過程中循環(huán)出現(xiàn)的情況，在wL(G) 證明w L(G2)的過程中，要取w在G中的一個(gè)最短的最左派生。S=0G1G2GGn=w2022/10/1736.2.3 去單一產(chǎn)生式 （3）刪除G2中的無用符號(hào)。由于在刪除單一產(chǎn)生式后，文法中可能出現(xiàn)新的無用符號(hào)，因此，我們還需要再次刪除新出現(xiàn)的無用符號(hào)。 此外，在去-產(chǎn)生式后可能會(huì)產(chǎn)生新的單一產(chǎn)生式，也可能會(huì)引進(jìn)新的無用符號(hào)。這是值得注意的。 2022/10/1746.3 喬姆斯基范式 喬

31、姆斯基范式文法(Chomsky normal form ，CNF)簡稱為Chomsky文法，或Chomsky范式。CFG G=(V，T，P，S)中的產(chǎn)生式形式：ABC，Aa其中，A、B、CV，aT。CNF中，不允許有-產(chǎn)生式、單一產(chǎn)生式。 2022/10/1756.3 喬姆斯基范式例 6-3-1 試將文法Gexp4轉(zhuǎn)換成等價(jià)的 GNF。Gexp4：EE+T| T*F|FP| (E)| idTT*F| FP| (E) |idFFP| (E) |idP(E) |id 可以分兩步走變成A a和A A1A2An的形式。變成CNF。2022/10/176第一步EEA+T| T A*F|F AP| A(E

32、A5| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+A*AA(A) 2022/10/177第二步 GexpCNF：EEA1| TA2E FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+A*AA(A)A1A+T A2A*FA3APA4EA) 2022/10/1786.3 喬姆斯基范式定理6-9 對(duì)于任意CFG G，L(G)，存在等價(jià)的 CNF G2 。 證明要點(diǎn)：1. 構(gòu)造CNF按照上述例子所描述的轉(zhuǎn)換方法，在構(gòu)造給定CFG的CNF時(shí)，可以分兩步走。假設(shè)G為化簡過的文法構(gòu)造G1=

33、(V1，T，P1，S) G1中的產(chǎn)生式都是形如AB1B2Bm和Aa的產(chǎn)生式，其中，A，B1，B2，BmV1，aT，m2 2022/10/1796.3 喬姆斯基范式構(gòu)造CNF G2=(V2，T，P2，S)。 m3時(shí)，引入新變量：B1、B2、Bm-2，將G1的形如AA1A2Am的產(chǎn)生式替換成AA1B1B1A2B2Bm-2Am-1Am2022/10/1806.3 喬姆斯基范式2. 構(gòu)造的正確性證明。按照上述構(gòu)造，證明被替換的產(chǎn)生式是等價(jià)的。例如：在第二步中A A1B1， B1A2B2 ， ， Bm-2Am-1Am與AA1A2Am等價(jià)。2022/10/1816.3 喬姆斯基范式例 6-6 試將下列文法

34、轉(zhuǎn)換成等價(jià)的 CNF。 SbA | aB AbAA | aS | a BaBB | bS | b 2022/10/1826.3 喬姆斯基范式先引入變量Ba，Bb和產(chǎn)生式Baa，Bbb ，完成第一步變換。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb2022/10/1836.3 喬姆斯基范式引入新變量B1、B2 SBbA | BaBABbB1 | BaS | aBBaB2 | BbS | b Baa Bbb B1AA B2BB2022/10/1846.3 喬姆斯基范式不能因?yàn)樵瓉碛挟a(chǎn)生式A a和B b而放棄引進(jìn)變量Ba 、Bb和產(chǎn)生式Baa

35、 、Bbb。L(A)=x | xa，b+ & x中a的個(gè)數(shù)比b的個(gè)數(shù)恰多1個(gè)。L(B)=x | xa，b+ & x中b的個(gè)數(shù)比a的個(gè)數(shù)恰多1個(gè)。L(Ba)= a 。L(Bb)= b 。 2022/10/1856.4 格雷巴赫范式格雷巴赫范式文法(Greibach normal form ,GNF)簡稱為Greibach文法，或Greibach范式。Aa 其中，AV，aT，V* 。在GNF中，有如下兩種形式的產(chǎn)生式AaAaA1A2Am(m1) 2022/10/1866.4 格雷巴赫范式右線性文法是一種特殊的GNF。 由于GNF中不存-產(chǎn)生式，所以對(duì)任意的GNF G，L(G)。當(dāng)L(G)時(shí)，能夠找

36、到一個(gè)GNF G，使得 L(G)=L(G) 。經(jīng)過化簡的CFG，都有一個(gè)等價(jià)的GNF。 2022/10/1876.4 格雷巴赫范式引理 6-1 對(duì)于任意的CFG G=(V，T，P，S)，ABP，且G中所有的B產(chǎn)生式為 B1 |2 |n 取G1=( V，T，P1，S)P1=(P-AB)A1，A2，An則，L(G1)=L(G)。 2022/10/1886.4 格雷巴赫范式證明 以下兩組產(chǎn)生式等價(jià)AB ；B1 |2 |n A1，A2，An 2022/10/1896.4 格雷巴赫范式遞歸(recursive) 如果G中存在形如AnA的派生，則稱該派生是關(guān)于變量A遞歸的，簡稱為遞歸派生。當(dāng)n=1時(shí)，稱該

37、派生關(guān)于變量A直接遞歸(directly recursive)，簡稱為直接遞歸派生。形如AA的產(chǎn)生式是變量A的直接遞歸的(directly recursive)產(chǎn)生式。2022/10/1906.4 格雷巴赫范式當(dāng)n2時(shí)，稱該派生是關(guān)于變量A的間接遞歸(indirectly recursive)派生。簡稱為間接遞歸派生。當(dāng)=時(shí)，稱相應(yīng)的(直接/間接)遞歸為(直接/間接)左遞歸(left-recursive)；當(dāng)=時(shí)，稱相應(yīng)的(直接/間接)遞歸為(直接/間接)右遞歸(right-recursive)。2022/10/1916.4 格雷巴赫范式引理 6-2 對(duì)于任意的CFG G=(V，T，P，S)，G中所有A的產(chǎn)生式 A1 |2 |mA1B |2 B |m BB1 |2 |nB1B |2 B |n B 可以被等價(jià)地替換為產(chǎn)生式組AA1 |A2 |AnA1 |2 |m2022/10/1926.4 格雷巴赫范式證明要點(diǎn)： 用直接右遞歸取代原來的直接左