自動機與形式語言_第六章

1、2021-12-121第第6章章 上下文無關(guān)語言上下文無關(guān)語言 Gbra：SS(S)| L(Gbra)不是不是RL,是是CFLhhnnnnnn10.10102211高級程序設(shè)計語言的絕大多數(shù)語法結(jié)構(gòu)都高級程序設(shè)計語言的絕大多數(shù)語法結(jié)構(gòu)都可以用上下文無關(guān)文法可以用上下文無關(guān)文法(CFG)(CFG)描述。描述。BNF(BNF(巴科斯范式：巴科斯范式：Backus normal formBackus normal form，又叫又叫Backus-naur form)Backus-naur form)。2021-12-122第第6章章 上下文無關(guān)語言上下文無關(guān)語言 主要內(nèi)容主要內(nèi)容關(guān)于關(guān)于CFL的分析

2、的分析 派生和歸約、派生樹派生和歸約、派生樹 CFG的化簡的化簡 無用符、單一產(chǎn)生式、空產(chǎn)生式無用符、單一產(chǎn)生式、空產(chǎn)生式 CFG的范式的范式 CNF GNF CFG的自嵌套特性的自嵌套特性 2021-12-123第第6章章 上下文無關(guān)語言上下文無關(guān)語言 重點重點 CFG的化簡。的化簡。 CFG到到GNF的轉(zhuǎn)換。的轉(zhuǎn)換。 難點難點 CFG到到GNF的轉(zhuǎn)換，特別是其中的用右遞歸替的轉(zhuǎn)換，特別是其中的用右遞歸替換左遞歸的問題。換左遞歸的問題。2021-12-1246.1 上下文無關(guān)語言上下文無關(guān)語言 文法文法G=(V，T，P，S)被稱為是上下文無關(guān)被稱為是上下文無關(guān)的。的。 如果除了形如如果除了形

3、如A的產(chǎn)生式之外，的產(chǎn)生式之外，對于對于 P，均有，均有|，并且，并且V成立。成立。 關(guān)鍵：對于關(guān)鍵：對于 AV，如果，如果AP，則無，則無論論A出現(xiàn)在句型的任何位置，我們都可以將出現(xiàn)在句型的任何位置，我們都可以將A替換成替換成，而不考慮，而不考慮A的上下文。的上下文。 2021-12-1256.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 算術(shù)表達式的文法算術(shù)表達式的文法 Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2021-12-1266.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)

4、文法的派生樹 算術(shù)表達式算術(shù)表達式x+x/y22的不同派生的不同派生 E EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x/Fx+x/FPx+x/PPx+x/yPx+x/y2 E 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 E 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 2021-12-1276.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 文法文法

5、Gexp1句子句子x+x/y22的結(jié)構(gòu)。的結(jié)構(gòu)。 86.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹S - SS | (S) | () ()()SSSS)()()96.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 派生樹派生樹(derivation tree) 一棵一棵(有序有序)樹樹(ordered tree) 樹的每個頂點有一個標記樹的每個頂點有一個標記X， 且且XVT 樹根的標記為樹根的標記為S； 如果非葉子頂點如果非葉子頂點v標記為標記為A，v的兒子從左到右的兒子從左到右依次為依次為v1，v2，vn，并且它們分別標記為，并且它們分別標記為X1，X2，Xn，則，則AX1X

6、2XnP；如果如果X是一個非葉子頂點的標記，則是一個非葉子頂點的標記，則XV；如果頂點如果頂點v標記為標記為，則，則v是該樹的葉子，并且是該樹的葉子，并且v是其父頂點的惟一兒子。是其父頂點的惟一兒子。 SSSS)()()2021-12-12106.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 別稱別稱 生成樹生成樹 分析樹分析樹(parse tree) 語法樹語法樹(syntax tree) 順序順序 v1，v2是派生樹是派生樹T的兩個不同頂點，如果存在頂?shù)膬蓚€不同頂點，如果存在頂點點v，v至少有兩個兒子，使得至少有兩個兒子，使得v1是是v的較左兒子的較左兒子的后代，的后代，v2是是v

7、的較右兒子的后代，則稱頂點的較右兒子的后代，則稱頂點v1在頂點在頂點v2的左邊，頂點的左邊，頂點v2在頂點在頂點v1的右邊。的右邊。 SSSS)()()2021-12-12116.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 結(jié)果結(jié)果(yield) 派生樹派生樹T的所有葉子頂點從左到右依次標記的所有葉子頂點從左到右依次標記為為X1 1，X2，Xn，則稱符號串，則稱符號串X1X2Xn是是T的的結(jié)果。結(jié)果。 一個文法可以有多棵派生樹，它們可以有一個文法可以有多棵派生樹，它們可以有不同的結(jié)果。不同的結(jié)果。 句型句型的派生樹：的派生樹：“G G的結(jié)果為的結(jié)果為的派生的派生樹樹”。SSSS)()

8、()2021-12-12126.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 派生子樹派生子樹(subtree) 滿足派生樹定義中除了對根結(jié)滿足派生樹定義中除了對根結(jié)點的標記的點的標記的要求以外各條的樹叫要求以外各條的樹叫派生子樹派生子樹(subtree)。 如果這個子樹的根標記為如果這個子樹的根標記為A，則稱之為，則稱之為A子子樹。樹。 惟一差別是根結(jié)點可以標記非開始符號。惟一差別是根結(jié)點可以標記非開始符號。SSSS)()()2021-12-12136.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-1 設(shè)設(shè)CFG G=(V，T，P，S)，S*的的充分必要條件為充分必

9、要條件為G有一棵結(jié)果為有一棵結(jié)果為的派生的派生樹樹。證明：證明： 證一個更為一般的結(jié)論：對于任意證一個更為一般的結(jié)論：對于任意AV，A*的充分必要條件為的充分必要條件為G有一棵結(jié)果為有一棵結(jié)果為的的A-子樹。子樹。 充分性：設(shè)充分性：設(shè)G有一棵結(jié)果為有一棵結(jié)果為的的A-子樹，非葉子子樹，非葉子頂點的個數(shù)頂點的個數(shù)n施歸納，證明施歸納，證明A*成立。成立。 2021-12-12146.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 設(shè)設(shè)A-子樹有子樹有k+1個非葉子頂點，根頂點個非葉子頂點，根頂點A的的兒子從左到右依次為兒子從左到右依次為v1，v2，vm，并且，并且它們分別標記為它們分別標

10、記為X1，X2，Xm 。 AX1X2XmP 。 以以X1，X2，Xm為根的子樹的結(jié)果依次為根的子樹的結(jié)果依次為為1，2，m 。 X1，X2，Xm為根的子樹的非葉子頂點為根的子樹的非葉子頂點的個數(shù)均不大于的個數(shù)均不大于k。 2021-12-12156.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 X1*1X X2 2*2X Xm m*m而且而且=1 12 2m m2021-12-12166.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹AX1X2Xm *1X2Xm *12Xm *12m2021-12-12176.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹2021-12-1

11、2186.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 必要性必要性設(shè)設(shè)A An n，現(xiàn)施歸納于派生步數(shù)，現(xiàn)施歸納于派生步數(shù)n n，證明存在結(jié)果為，證明存在結(jié)果為的的A-A-子樹。子樹。設(shè)設(shè)n nk(kk(k1)1)時結(jié)論成立，往證當時結(jié)論成立，往證當n=k+1n=k+1時結(jié)論也成立：令時結(jié)論也成立：令A Ak+1k+1，則有：，則有：A AX X1 1X X2 2X Xm m * *1 1X X2 2X Xm m * *1 12 2X Xm m * *1 12 2m m 2021-12-12196.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹2021-12-12206.1.1

12、 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 例例6-1設(shè)設(shè)Gbra：SS(S)|，()()和和(S)(S)的派生樹。的派生樹。2021-12-12216.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 關(guān)于標記關(guān)于標記的結(jié)點的結(jié)點x+x/y222021-12-12226.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 最左派生最左派生(leftmost derivation) 的派生過程中，每一步都是對當前句型的最的派生過程中，每一步都是對當前句型的最左變量進行替換。左變量進行替換。 左句型左句型(left sentencial form)最左派生得到的句型可叫做左句型。最左派

13、生得到的句型可叫做左句型。 最右歸約最右歸約(rightmost reduction)(rightmost reduction)與最左派生對相的歸約叫做最有歸約。與最左派生對相的歸約叫做最有歸約。Grammmar:S - SS | (S) | () S =lm SS =lm (S)S =lm ()S =lm ()()2021-12-12236.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 最右派生最右派生(rightmost derivation) 的派生過程中，每一步都是對當前句型的最的派生過程中，每一步都是對當前句型的最右變量進行替換。右變量進行替換。 右句型右句型(right s

14、entencial form)最右派生得到的句型可叫做右句型。最右派生得到的句型可叫做右句型。 最左歸約最左歸約( (leftmost reduction) )與最左派生對相的歸約叫做最右歸約。與最左派生對相的歸約叫做最右歸約。Grammmar:S - SS | (S) | () S =rm SS =rm S() =rm (S)() =rm ()()2021-12-12246.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹 規(guī)范派生規(guī)范派生(normal derivation)最右派生。最右派生。 規(guī)范句型規(guī)范句型(normal sentencial form)規(guī)范派生產(chǎn)生的句型。規(guī)范派

15、生產(chǎn)生的句型。 規(guī)范歸約規(guī)范歸約(normal reduction)最左歸約。最左歸約。2021-12-12256.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-2 如果如果是是CFG G的一個句型，則的一個句型，則G中中存在存在的最左派生和最右派生。的最左派生和最右派生。證明：證明：基本思路：基本思路：對派生的步數(shù)對派生的步數(shù)n施歸納，證明對于施歸納，證明對于任意任意AV，如果，如果An，在，在G中，存在對中，存在對應(yīng)的從應(yīng)的從A到到的最左派生：的最左派生：An左左。 2021-12-12266.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹AX1X2Xm *1X2X

16、m *12Xm *12mA左左X1X2Xm *左左1X2Xm *左左12Xm *左左12m 同理可證，句型同理可證，句型有最右派生。有最右派生。 2021-12-12276.1.1 上下文無關(guān)文法的派生樹上下文無關(guān)文法的派生樹定理定理6-3 如果如果是是CFG G的一個句型，的一個句型，的的派生樹與最左派生和最右派生是一一對應(yīng)派生樹與最左派生和最右派生是一一對應(yīng)的，但是，這棵派生樹可以對應(yīng)多個不同的，但是，這棵派生樹可以對應(yīng)多個不同的派生。的派生。2021-12-12286.1.2 二義性二義性 簡單算術(shù)表達式的二義性文法簡單算術(shù)表達式的二義性文法Gexp2：EE+E|E-E|E/E|E*EE

17、 EE|(E)|N(L)|idE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E 2021-12-12296.1.2 二義性二義性 E E+E x+E x+E/E x+x/E x+x/EEEx+x/yEEx+x/y22句子句子x+x/y22在文法中的三個不同的最左派生在文法中的三個不同的最左派生 E E/E E+E/E x+E/E x+x/E x+x/EEE x+x/yEE x+x/y22 E EE E/EE E+E/EE x+E/EE x+x/EE x+x/yE x+x/y2 2021-12-12306.1.2 二義性二義性 x+x/y22對應(yīng)對應(yīng)3個不個

18、不同的語法同的語法樹樹2021-12-12316.1.2 二義性二義性 二義性二義性(ambiguity) CFG G=(V，T，P，S)，如果存在wL(G)，w至少有兩棵不同的派生樹，則稱G是二義二義性的性的。否則，G為非二義性的。 二義性的問題是不可解的不可解的(unsolvable)(unsolvable)問問題。題。 2021-12-12326.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

19、 then M else M|SGifh：STS|CSCif E thenT CS else 2021-12-12336.1.2 二義性二義性 例例 6-3 設(shè)設(shè)Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法產(chǎn)生語言可以用如下文法產(chǎn)生語言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 語言語言Lambiguity不存在非二義性的文法。不存在非二義性的文法。 2021-12-12346.1.2 二義性二義性 固有二義性的固有二義性的(inherent ambiguity) 如果語言如果語言L不存在

20、非二義性文法，則稱不存在非二義性文法，則稱L是是固有二義性的固有二義性的，又稱，又稱L是是先天二義性的。先天二義性的。 文法可以是二義性的。文法可以是二義性的。 語言可以是固有二義性的。語言可以是固有二義性的。 2021-12-12356.1.3 自頂向下的分析和自底向自頂向下的分析和自底向上的分析上的分析 自頂向下的分析方法自頂向下的分析方法 通過考察是否可以從給定文法的開始符號派生通過考察是否可以從給定文法的開始符號派生出一個符號串，可以判定一個符號串是否為該出一個符號串，可以判定一個符號串是否為該文法的句子。文法的句子。 例例 SaAb|bBa AaAb|bBa Bd 2021-12-1

21、236aabdabb的派生樹的自頂向下的的派生樹的自頂向下的“生長生長”過程過程 2021-12-12376.1.3 自頂向下的分析和自底向自頂向下的分析和自底向上的分析上的分析 自底向上自底向上的分析方法的分析方法 通過考察是否可以將一個符號串歸約為通過考察是否可以將一個符號串歸約為給定文法的開始符號，完成判定一個符給定文法的開始符號，完成判定一個符號串是否為該文法的句子的任務(wù)。號串是否為該文法的句子的任務(wù)。 和歸約與派生是互逆過程相對應(yīng)，自頂向和歸約與派生是互逆過程相對應(yīng)，自頂向下的分析與自底向上的分析互逆的分析過下的分析與自底向上的分析互逆的分析過程。程。2021-12-1238aabd

22、abb的派生樹的自底向上的的派生樹的自底向上的“生長生長”過程過程 2021-12-12396.2 上下文無關(guān)文法的化簡上下文無關(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 2021-12-12406.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后

23、的后的文法文法G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C 可以去掉文法中的無用符號、可以去掉文法中的無用符號、 產(chǎn)生式和產(chǎn)生式和單一產(chǎn)生式。單一產(chǎn)生式。2021-12-12416.2.1 去無用符號去無用符號 無用符號無用符號(useless symbol) 對于任意對于任意XVT，如果存在，如果存在wL(G)，X出現(xiàn)在出現(xiàn)在w的派生過程中，即存在的派生過程中，即存在，(VT)*，使得，使得S*X*w，則稱，則稱X是有用的，否則，稱是有用的，否則，稱X是是無用符號。無用符號。 對對CFG G=(V，T，P，S) G中的符號中的符號X既可能是有用的，也可能既可能是有用的，也

24、可能是無用的。當是無用的。當X是無用的時候，它既可能是無用的時候，它既可能是終極符號，也可能是語法變量。是終極符號，也可能是語法變量。2021-12-12426.2.1 去無用符號去無用符號 對于任意對于任意XVT，如果，如果X是有用的，是有用的，它必須同時滿足如下兩個條件：它必須同時滿足如下兩個條件： 存在存在wT*，使得，使得X*w； ，(VT)*，使得，使得S*X。 注意到文法是語言的有窮描述，所以，注意到文法是語言的有窮描述，所以，集合集合V，T，P都是有窮的。從而我們有都是有窮的。從而我們有可能構(gòu)造出有效的算法，來完成消除文可能構(gòu)造出有效的算法，來完成消除文法的無用符號的工作。法的無

25、用符號的工作。 2021-12-12436.2.1 去無用符號去無用符號 算法算法 6-1 刪除派生不出終極符號行的變量。刪除派生不出終極符號行的變量。 輸入：輸入：CFG G=(V，T，P，S)。 輸出：輸出：CFG G=(V，T，P，S)，V中不含中不含派生不出終極符號行的變量，并且派生不出終極符號行的變量，并且L(G)=L(G)。 主要步驟：主要步驟： 44Testing Whether a Variable Derives Some Terminal String Basis: 對產(chǎn)生式 A - w, 如果 w 是終結(jié)符號行, 那么 A 能派生出終結(jié)符號行. Induction: 對產(chǎn)

26、生式 A - , 如果 只包含終結(jié)符號或者能派生出終結(jié)符號行的變量, 那么 A 能派生出終結(jié)符號行. 2021-12-12456.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)*2021-12-12466.2.1 去無用符號去無用符號 第第(3)條語句控制對條語句控制對NEWV進行迭代更新。進行迭代更新。第一次循環(huán)將那些恰經(jīng)過兩步可以派生出終第

27、一次循環(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中的所有可以派生出終極符號行的變中的所有可以派生出終極符號行的變量都被放入量都被放入NEWV中。中。 2021-12-12476

28、.2.1去無用符號去無用符號 定理定理 6-4 算法算法6-1是正確的。是正確的。 證明要點：首先證明對于任意證明要點：首先證明對于任意AV，A被放被放入入V中的充要條件是存在中的充要條件是存在wT，An w。再證所構(gòu)造出的文法是等價的。再證所構(gòu)造出的文法是等價的。(1)對對A被放入被放入NEWV的循環(huán)次數(shù)的循環(huán)次數(shù)n施歸納，證施歸納，證明必存在明必存在wT，滿足，滿足A w。2021-12-12486.2.1去無用符號去無用符號 (2)施歸納于派生步數(shù)施歸納于派生步數(shù)n，證明如果，證明如果An w，則，則A被算法放入到被算法放入到NEWV中。實際上，對原教中。實際上，對原教材所給的證明進行分

29、析，同時考慮算法材所給的證明進行分析，同時考慮算法6-1的實際運行，可以證明，的實際運行，可以證明，A是在第是在第n次循環(huán)次循環(huán)前被放入到前被放入到NEWV中的。中的。(3)證明證明L(G)=L(G) 。顯然有顯然有L(G) L(G)，所以只需證明所以只需證明L(G)。 49Example: Eliminate VariablesS - AB | C, A - aA | a, B - bB, C - cBasis: A and C are identified because of A - a and C - c.Induction: S is identified because of S

30、- C.Nothing else can be identified.Result: S - C, A - aA | a, C - c2021-12-12506.2.1 去無用符號去無用符號 算法算法 6-2 刪除不出現(xiàn)在任何句型中的語法符號。刪除不出現(xiàn)在任何句型中的語法符號。 輸入：輸入：CFG G=(V，T，P，S)。 輸出：輸出：CFG G=(V，T，P，S)，VT中的中的符號必在符號必在G的某個句型中出現(xiàn)，并且有的某個句型中出現(xiàn)，并且有L(G)=L(G)。 主要步驟：主要步驟： 2021-12-12516.2.1 去無用符號去無用符號 主要步驟：主要步驟：(1) OLDV=;(2) O

31、LDT=;(3) NEWV=SA|SAP;(4) NEWT=a|SaP;2021-12-12526.2.1去無用符號去無用符號 (5) while OLDVNEWV 或者或者OLDTNEWT do begin(6) OLDV=NEWV;(7) OLDT=NEWT;(8) NEWV=OLDVB| AOLDV且且 ABP 且且BV;(9) NEWT=OLDTa| AOLDV且且 AaP 且且aT; end2021-12-12536.2.1去無用符號去無用符號 (10) V=NEWV;(11) T=NEWT;(12) P= A| AP且且 AV且且(TV)*。2021-12-12546.2.1去無用

32、符號去無用符號定理定理 6-5 算法算法6-2是正確的。是正確的。證明要點：證明要點：(1) 施歸納于派生步數(shù)施歸納于派生步數(shù)n，證明如果，證明如果Sn X，則當，則當XV時，時，X在算法中被語句在算法中被語句(3)或者語句或者語句(8)放入放入NEWV；當；當XT時，它在算法中被語句時，它在算法中被語句(4)或者或者語句語句(9)放入放入NEWT。(2) 對循環(huán)次數(shù)對循環(huán)次數(shù)n施歸納，證明如果施歸納，證明如果X被放入被放入NEWT或 者或 者 N E W V 中 ， 則 必 定 存 在中 ， 則 必 定 存 在 ，(NEWVNEWT)*，使得，使得Sn X。(3) 證明證明L(G)=L(G)

33、 。2021-12-12556.2.1去無用符號去無用符號定理定理6-6 對于任意對于任意CFL L，L，則存在不含，則存在不含無用符號的無用符號的CFG G，使得，使得L(G)=L。 證明要點：證明要點： 依次用算法依次用算法6-1和算法和算法6-2對文法進行處理，對文法進行處理，可以得到等價的不含無用符號的文法。可以得到等價的不含無用符號的文法。 不可先用算法不可先用算法6-2后用算法后用算法6-1。2021-12-12566.2.1去無用符號去無用符號 例例 6-2-1 設(shè)有如下文法設(shè)有如下文法 SAB|a|BB，Aa，Cb|ABa 先用算法先用算法6-2，文法被化簡成：，文法被化簡成：

34、 SAB|a|BB，Aa 再用算法再用算法6-1，可得到文法：，可得到文法： S a，Aa 顯然，該文法中的變量顯然，該文法中的變量A是新的無用變量是新的無用變量。 若先用若先用6-1，得到，得到Sa, Aa, Cb, 再用再用6-2，則得到正確的則得到正確的S a57Why It Works 算法6-1后, 所有剩下的變量都能推導出終結(jié)字符串. 算法6-2后, 所有剩下的變量都能從S出發(fā)派生到. 另外, 剩下的變量仍然保證能派生出終結(jié)字符串, 因為派生終結(jié)字符串所用到的后續(xù)符號都能從S出發(fā)到達，所以不會被6-2刪掉. 反之則不然2021-12-12586.2.2 去去-產(chǎn)生式產(chǎn)生式 -產(chǎn)生式

35、（產(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，P，S)中的任意變量中的任意變量A，如，如果果A+，則稱，則稱A為為可空變量?？煽兆兞俊?59Example: Nullable SymbolsS - AB, A - aA | , B - bB | A Basis: A is nullable because of A - . Induction: B is nullable because of B - A

36、. Then, S is nullable because of S - AB. 可空變量集S,A,B2021-12-12606.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;2021-12-12616.2.2 去去-產(chǎn)生式產(chǎn)生式 (3) while NEWUOLDU do begin(4) OLDU = NEWU;(5) NEWU= OLDU A|AP并且并且OLDU* end(6) U=NE

37、WU2021-12-12626.2.2 去去-產(chǎn)生式產(chǎn)生式 對形如對形如AX1X2Xm的產(chǎn)生式進行考察，的產(chǎn)生式進行考察，找出文法的可空變量集找出文法的可空變量集U，然后對于，然后對于 H U，從產(chǎn)生式從產(chǎn)生式AX1X2Xm中刪除中刪除H中的變量。中的變量。對于不同的對于不同的H，得到不同的，得到不同的A產(chǎn)生式，用這產(chǎn)生式，用這組組A產(chǎn)生式替代產(chǎn)生式產(chǎn)生式替代產(chǎn)生式AX1X2Xm。 必須避免在這個過程中產(chǎn)生新的必須避免在這個過程中產(chǎn)生新的-產(chǎn)生式：產(chǎn)生式：當當 X1，X2，Xm U時，不可將時，不可將X1，X2，Xm同時從產(chǎn)生式同時從產(chǎn)生式AX1X2Xm中中刪除。刪除。 2021-12-126

38、36.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。 2021-12-12646.2.2 去去-產(chǎn)生式產(chǎn)生式 對于對于 AX1X2XmP 將將A12m放入放入P，其中，其中 if XiU then i=Xi或者或者i=； if Xi U then i=Xi 要求：在同一產(chǎn)生式中，要求：在同一產(chǎn)生式中，1，2，m不不能同時為能同時為。 2021-12-1

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

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

41、立。成立。2021-12-12696.2.2 去去-產(chǎn)生式產(chǎn)生式充分性：設(shè)充分性：設(shè)AmG w，施歸納于，施歸納于m，證明，證明AnG w成立。成立。當當m=1時，由時，由AG w知，知，AwP，按照定，按照定理所給的構(gòu)造理所給的構(gòu)造G的方法，必定有的方法，必定有AP。Aw是通過刪除產(chǎn)生式是通過刪除產(chǎn)生式A右部中的可空右部中的可空變量而構(gòu)造出來的，所以，變量而構(gòu)造出來的，所以，AG *G w 成立。成立。 2021-12-12706.2.2 去去-產(chǎn)生式產(chǎn)生式設(shè)設(shè)nk時結(jié)論成立時結(jié)論成立(k1)，當，當m=k+1時時A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjw

42、k=w其中其中Xi*G wi，Xj*G wj，Xk*G wk 。2021-12-12716.2.2 去去-產(chǎn)生式產(chǎn)生式表明表明A XiXjXkP。按照。按照G的構(gòu)造方法，的構(gòu)造方法，必定存在必定存在A X1X2XmP，而且，而且Xi，Xj，Xk X1，X2，XmX1，X2，Xm-Xi，Xj，Xk U從而，從而，AG X1X2Xm *G XiXjXk2021-12-12726.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 X1X2X

43、m *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w2021-12-12736.2.2 去去-產(chǎn)生式產(chǎn)生式表明表明結(jié)論對結(jié)論對m=k+1成立。由歸納法原理，結(jié)成立。由歸納法原理，結(jié)論對任意論對任意m成立。成立。注意到注意到A 的任意性，當?shù)娜我庑?，當S=A時結(jié)論成立。即：時結(jié)論成立。即：S*G w 的充分必要條件是的充分必要條件是S*G w亦即：亦即：L(G)=L(G)-。定理得證。定理得證。 74Example: Eliminating -ProductionsS - ABC, A - aA | , B - bB | , C - A, B, C, and S

44、 are all nullable. New grammar:S - ABC | AB | AC | BC | A | B | CA - aA | aB - bB | bNote: C is now useless.Eliminate its productions.2021-12-12756.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存在派生：存在派生：ETFPid2021-12-12766.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 Gexp3：EE+T|

45、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 該文法中不存在類似的派生。該文法中不存在類似的派生。2021-12-12776.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 單一產(chǎn)生式單一產(chǎn)生式(unit production) 形如形如AB的產(chǎn)生式稱為的產(chǎn)生式稱為單一產(chǎn)生式。單一產(chǎn)生式。 定理定理 6-8對于任意對于任意CFG G， L(G)，存在，存在等價的等價的CFG G1，G1不含無用符號、不含無用符號、-產(chǎn)生產(chǎn)生式和單一產(chǎn)生式

46、。式和單一產(chǎn)生式。 滿足本定理的滿足本定理的CFG為為化簡過的文法。化簡過的文法。 已有去無用符號和去已有去無用符號和去-產(chǎn)生式的結(jié)論，所以產(chǎn)生式的結(jié)論，所以只討論去單一產(chǎn)生式的問題。只討論去單一產(chǎn)生式的問題。 2021-12-12786.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)生式。都是單一產(chǎn)

47、生式。（n1） 2021-12-12796.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 （2） 證明證明L(G2)=L(G)。 用用A1所完成的派生所完成的派生A1與產(chǎn)生式系列與產(chǎn)生式系列A1A2，A2A3，An-1An，An所所完成的派生完成的派生A1*G An相對應(yīng)。相對應(yīng)。在原文法中可能會出現(xiàn)一個變量在派生過程中在原文法中可能會出現(xiàn)一個變量在派生過程中循環(huán)出現(xiàn)的情況，在循環(huán)出現(xiàn)的情況，在wL(G) 證明證明w L(G2)的過程中，要取的過程中，要取w在在G中的一個最短的最左派中的一個最短的最左派生。生。S=0G1G2GGn=w2021-12-12806.2.3 去單一產(chǎn)生式去單一產(chǎn)生式 （3）刪除

48、刪除G2中的無用符號。中的無用符號。由于在刪除單一產(chǎn)生式后，文法中可能出由于在刪除單一產(chǎn)生式后，文法中可能出現(xiàn)新的無用符號，因此，我們還需要再次現(xiàn)新的無用符號，因此，我們還需要再次刪除新出現(xiàn)的無用符號。刪除新出現(xiàn)的無用符號。 此外，在去此外，在去-產(chǎn)生式后可能會產(chǎn)生新的單一產(chǎn)生式后可能會產(chǎn)生新的單一產(chǎn)生式，也可能會引進新的無用符號。這產(chǎn)生式，也可能會引進新的無用符號。這是值得注意的。是值得注意的。 81Cleaning Up (2)Proof: Start with a CFG for L.Perform the following steps in order:1. Eliminate -p

49、roductions.2. Eliminate unit productions.3. Eliminate variables that derive no terminal string.4. Eliminate variables not reached from the start symbol.Must be first. Can createunit productions or uselessvariables.2021-12-12826.3 喬姆斯基范式喬姆斯基范式 喬姆斯基范式文法喬姆斯基范式文法(Chomsky normal form ，CNF)簡稱為簡稱為Chomsky文法

50、文法，或，或Chomsky范式。范式。CFG G=(V，T，P，S)中的產(chǎn)生式形式：中的產(chǎn)生式形式：ABC，Aa其中，其中，A、B、CV，aT。 CNF中，不允許有中，不允許有-產(chǎn)生式、單一產(chǎn)生式。產(chǎn)生式、單一產(chǎn)生式。 2021-12-12836.3 喬姆斯基范式喬姆斯基范式 例例 6-3-1 試將文法試將文法Gexp4轉(zhuǎn)換成等價的轉(zhuǎn)換成等價的 CNF。Gexp4：EE+T| T*F|FP| (E)| idTT*F| FP| (E) |idFFP| (E) |idP(E) |id 可以分兩步走可以分兩步走 變成變成A a和和A A1A2An的形式。的形式。 變成變成CNF。2021-12-12

51、84第一步第一步EEA+T| T A*F|F AP| A(EA5| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+A*AA(A) 2021-12-1285第二步第二步GexpCNF：EEA1| TA2E FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+A*AA(A)A1A+T A2A*FA3APA4EA) 2021-12-12866.3 喬姆斯基范式喬姆斯基范式定理定理6-9 對于任意對于任意CFG G， L(G)，存在等，存在等價的價的 CNF G2 。 證明要點：證明要點：1

52、. 構(gòu)造構(gòu)造CNF按照上述例子所描述的轉(zhuǎn)換方法，在構(gòu)造給定按照上述例子所描述的轉(zhuǎn)換方法，在構(gòu)造給定CFG的的CNF時，可以分兩步走。時，可以分兩步走。 假設(shè)假設(shè)G為化簡過的文法為化簡過的文法 構(gòu)造構(gòu)造G1=(V1，T，P1，S) G1中的產(chǎn)生式都是形如中的產(chǎn)生式都是形如AB1B2Bm和和Aa的產(chǎn)生式，其中，的產(chǎn)生式，其中，A，B1，B2，BmV1，aT，m2 2021-12-12876.3 喬姆斯基范式喬姆斯基范式 構(gòu)造構(gòu)造CNF G2=(V2，T，P2，S)。 m3時，引入新變量：時，引入新變量：B1、B2、Bm-2，將將G1的形如的形如AA1A2Am的產(chǎn)生式替換成的產(chǎn)生式替換成AA1B1B

53、1A2B2Bm-2Am-1Am2021-12-12886.3 喬姆斯基范式喬姆斯基范式2. 構(gòu)造的正確性證明。構(gòu)造的正確性證明。 按照上述構(gòu)造，證明被替換的產(chǎn)生式是等按照上述構(gòu)造，證明被替換的產(chǎn)生式是等價的。價的。 例如：在第二步中例如：在第二步中A A1B1， B1A2B2 ， ， Bm-2Am-1Am與與AA1A2Am等價。等價。2021-12-12896.3 喬姆斯基范式喬姆斯基范式 例例 6-6 試將下列文法轉(zhuǎn)換成等價的試將下列文法轉(zhuǎn)換成等價的 CNF。 SbA | aB AbAA | aS | a BaBB | bS | b 2021-12-12906.3 喬姆斯基范式喬姆斯基范式

54、先引入變量先引入變量Ba，Bb和產(chǎn)生式和產(chǎn)生式Baa，Bbb ，完成第一步變換。完成第一步變換。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb2021-12-12916.3 喬姆斯基范式喬姆斯基范式 引入新變量引入新變量B1、B2 SBbA | BaBABbB1 | BaS | aBBaB2 | BbS | b Baa Bbb B1AA B2BB2021-12-12926.3 喬姆斯基范式喬姆斯基范式 不能因為原來有產(chǎn)生式不能因為原來有產(chǎn)生式A a和和B b而放而放棄引進變量棄引進變量Ba 、Bb和產(chǎn)生式和產(chǎn)生式Baa 、Bbb。 L(A

55、)=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 。 2021-12-12936.4 格雷巴赫范式格雷巴赫范式格雷巴赫范式文法格雷巴赫范式文法(Greibach normal form ,GNF)簡稱為簡稱為Greibach文法文法，或，或Greibach范式。范式。Aa 其中，其中，AV，aT，V* 。在在GNF中，有如下兩種形式的產(chǎn)生式中，有如下兩種形式的產(chǎn)生式AaAaA1A2Am(m1) 2021-12-129

56、46.4 格雷巴赫范式格雷巴赫范式 右線性文法是一種特殊的右線性文法是一種特殊的GNF。 由于由于GNF中不存中不存-產(chǎn)生式，所以對任意的產(chǎn)生式，所以對任意的GNF G， L(G)。 當當 L(G)時，能夠找到一個時，能夠找到一個GNF G，使得，使得 L(G)=L(G) 。 經(jīng)過化簡的經(jīng)過化簡的CFG，都有一個等價的，都有一個等價的GNF。 2021-12-12956.4 格雷巴赫范式格雷巴赫范式引理引理 6-1 對于任意的對于任意的CFG G=(V，T，P，S)，ABP，且，且G中所有的中所有的B產(chǎn)生式為產(chǎn)生式為 B1 |2 |n 取取G1=( V，T，P1，S)P1=(P-AB)A1，A

57、2，An則，則，L(G1)=L(G)。 2021-12-12966.4 格雷巴赫范式格雷巴赫范式 證明證明 以下兩組產(chǎn)生式等價以下兩組產(chǎn)生式等價 AB ；B1 |2 |n A1，A2，An 2021-12-12976.4 格雷巴赫范式格雷巴赫范式 遞歸遞歸(recursive) 如果如果G中存在形如中存在形如AnA的派生，則稱該的派生，則稱該派生是關(guān)于變量派生是關(guān)于變量A遞歸的，遞歸的，簡稱為遞歸派生。簡稱為遞歸派生。 當當n=1時，稱該派生關(guān)于變量時，稱該派生關(guān)于變量A直接遞歸直接遞歸(directly recursive)，簡稱為直接遞歸派簡稱為直接遞歸派生。生。 形如形如AA的產(chǎn)生式是變

58、量的產(chǎn)生式是變量A的的直接遞歸直接遞歸的的(directly recursive)產(chǎn)生式。產(chǎn)生式。2021-12-12986.4 格雷巴赫范式格雷巴赫范式 當當n2時，稱該派生是關(guān)于變量時，稱該派生是關(guān)于變量A的的間接遞間接遞歸歸(indirectly recursive)派派生。簡稱為間接生。簡稱為間接遞歸派生。遞歸派生。 當當=時，稱相應(yīng)的時，稱相應(yīng)的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)左遞歸左遞歸(left-recursive)； 當當=時，稱相應(yīng)的時，稱相應(yīng)的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)右遞歸右遞歸(right-recursive)。2021-12-12996.4 格雷巴赫范式格雷巴赫范式 引理引理 6-2 對于任意的對于任意的CFG G=(V，T，P，S)，G中所有中所有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 |m2021-12-121006.4 格雷巴赫范式格雷巴赫范式 證明要點：證明要點： 用直接右遞歸取代原來的直接左