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

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

3、如A的產生式之外，的產生式之外，對于對于 P，均有，均有|，并且，并且V成立。成立。 關鍵：對于關鍵：對于 AV，如果，如果AP，則無，則無論論A出現在句型的任何位置，我們都可以將出現在句型的任何位置，我們都可以將A替換成替換成，而不考慮，而不考慮A的上下文。的上下文。 2021-12-1256.1.1 上下文無關文法的派生樹上下文無關文法的派生樹 算術表達式的文法算術表達式的文法 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 上下文無關文法的派生樹上下文無關

4、文法的派生樹 算術表達式算術表達式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 上下文無關文法的派生樹上下文無關文法的派生樹 文法文法

5、Gexp1句子句子x+x/y22的結構。的結構。 86.1.1 上下文無關文法的派生樹上下文無關文法的派生樹S - SS | (S) | () ()()SSSS)()()96.1.1 上下文無關文法的派生樹上下文無關文法的派生樹 派生樹派生樹(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 上下文無關文法的派生樹上下文無關文法的派生樹 別稱別稱 生成樹生成樹 分析樹分析樹(parse tree) 語法樹語法樹(syntax tree) 順序順序 v1，v2是派生樹是派生樹T的兩個不同頂點，如果存在頂的兩個不同頂點，如果存在頂點點v，v至少有兩個兒子，使得至少有兩個兒子，使得v1是是v的較左兒子的較左兒子的后代，的后代，v2是是v

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

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

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

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

11、2186.1.1 上下文無關文法的派生樹上下文無關文法的派生樹 必要性必要性設設A An n，現施歸納于派生步數，現施歸納于派生步數n n，證明存在結果為，證明存在結果為的的A-A-子樹。子樹。設設n nk(kk(k1)1)時結論成立，往證當時結論成立，往證當n=k+1n=k+1時結論也成立：令時結論也成立：令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 上下文無關文法的派生樹上下文無關文法的派生樹2021-12-12206.1.1

12、 上下文無關文法的派生樹上下文無關文法的派生樹 例例6-1設設Gbra：SS(S)|，()()和和(S)(S)的派生樹。的派生樹。2021-12-12216.1.1 上下文無關文法的派生樹上下文無關文法的派生樹 關于標記關于標記的結點的結點x+x/y222021-12-12226.1.1 上下文無關文法的派生樹上下文無關文法的派生樹 最左派生最左派生(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 上下文無關文法的派生樹上下文無關文法的派生樹 最右派生最右派生(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 上下文無關文法的派生樹上下文無關文法的派生樹 規范派生規范派生(normal derivation)最右派生。最右派生。 規范句型規范句型(normal sentencial form)規范派生產生的句型。規范派

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

16、m *12Xm *12mA左左X1X2Xm *左左1X2Xm *左左12Xm *左左12m 同理可證，句型同理可證，句型有最右派生。有最右派生。 2021-12-12276.1.1 上下文無關文法的派生樹上下文無關文法的派生樹定理定理6-3 如果如果是是CFG G的一個句型，的一個句型，的的派生樹與最左派生和最右派生是一一對應派生樹與最左派生和最右派生是一一對應的，但是，這棵派生樹可以對應多個不同的，但是，這棵派生樹可以對應多個不同的派生。的派生。2021-12-12286.1.2 二義性二義性 簡單算術表達式的二義性文法簡單算術表達式的二義性文法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對應對應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 設設Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法產生語言可以用如下文法產生語言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 自頂向下的分析和自底向自頂向下的分析和自底向上的分析上的分析 自底向上自底向上的分析方法的分析方法 通過考察是否可以將一個符號串歸約為通過考察是否可以將一個符號串歸約為給定文法的開始符號，完成判定一個符給定文法的開始符號，完成判定一個符號串是否為該文法的句子的任務。號串是否為該文法的句子的任務。 和歸約與派生是互逆過程相對應，自頂向和歸約與派生是互逆過程相對應，自頂向下的分析與自底向上的分析互逆的分析過下的分析與自底向上的分析互逆的分析過程。程。2021-12-1238aabd

22、abb的派生樹的自底向上的的派生樹的自底向上的“生長生長”過程過程 2021-12-12396.2 上下文無關文法的化簡上下文無關文法的化簡 如下文法如下文法含有無含有無用的用的“東西東西”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 上下文無關文法的化簡上下文無關文法的化簡 去掉產生式去掉產生式A后后的的文法文法G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C 去掉產生式去掉產生式AB后

23、的后的文法文法G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C 可以去掉文法中的無用符號、可以去掉文法中的無用符號、 產生式和產生式和單一產生式。單一產生式。2021-12-12416.2.1 去無用符號去無用符號 無用符號無用符號(useless symbol) 對于任意對于任意XVT，如果存在，如果存在wL(G)，X出現在出現在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都是有窮的。從而我們有都是有窮的。從而我們有可能構造出有效的算法，來完成消除文可能構造出有效的算法，來完成消除文法的無用符號的工作。法的無

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: 對產生式 A - w, 如果 w 是終結符號行, 那么 A 能派生出終結符號行. Induction: 對產

26、生式 A - , 如果 只包含終結符號或者能派生出終結符號行的變量, 那么 A 能派生出終結符號行. 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進行迭代更新。進行迭代更新。第一次循環將那些恰經過兩步可以派生出終第

27、一次循環將那些恰經過兩步可以派生出終極符號行的變量放入極符號行的變量放入NEWV；第二次循環將；第二次循環將那些恰經過三步和某些至少經過三步可以派那些恰經過三步和某些至少經過三步可以派生出終極符號行的變量放入生出終極符號行的變量放入NEWV；，第第n次循環將那些恰經過次循環將那些恰經過n步和某些至少經過步和某些至少經過n+1步可以派生出終極符號行的變量放入步可以派生出終極符號行的變量放入NEWV。這個循環一直進行下去，直到所給。這個循環一直進行下去，直到所給文法文法G中的所有可以派生出終極符號行的變中的所有可以派生出終極符號行的變量都被放入量都被放入NEWV中。中。 2021-12-12476

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

29、析，同時考慮算法材所給的證明進行分析，同時考慮算法6-1的實際運行，可以證明，的實際運行，可以證明，A是在第是在第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 刪除不出現在任何句型中的語法符號。刪除不出現在任何句型中的語法符號。 輸入：輸入：CFG G=(V，T，P，S)。 輸出：輸出：CFG G=(V，T，P，S)，VT中的中的符號必在符號必在G的某個句型中出現，并且有的某個句型中出現，并且有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) 施歸納于派生步數施歸納于派生步數n，證明如果，證明如果Sn X，則當，則當XV時，時，X在算法中被語句在算法中被語句(3)或者語句或者語句(8)放入放入NEWV；當；當XT時，它在算法中被語句時，它在算法中被語句(4)或者或者語句語句(9)放入放入NEWT。(2) 對循環次數對循環次數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 設有如下文法設有如下文法 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后, 所有剩下的變量都能推導出終結字符串. 算法6-2后, 所有剩下的變量都能從S出發派生到. 另外, 剩下的變量仍然保證能派生出終結字符串, 因為派生終結字符串所用到的后續符號都能從S出發到達，所以不會被6-2刪掉. 反之則不然2021-12-12586.2.2 去去-產生式產生式 -產生式

35、（產生式（-production） 形如形如A的產生式叫做的產生式叫做-產生式。產生式。 -產生式產生式又稱為又稱為空產生式（空產生式（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 去去-產生式產生式 算法算法6-3 求求CFG G的可空變量集的可空變量集U。 輸入：輸入：CFG G=(V，T，P，S)。 輸出：輸出：G的可空變量集的可空變量集U。 主要步驟：主要步驟：(1) OLDU=;(2) NEWU=A| AP;2021-12-12616.2.2 去去-產生式產生式 (3) while NEWUOLDU do begin(4) OLDU = NEWU;(5) NEWU= OLDU A|AP并且并且OLDU* end(6) U=NE

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

38、36.2.2 去去-產生式產生式 定理定理 6-7 對于任意對于任意CFG G，存在不含，存在不含-產產生式的生式的CFG G使得使得L(G)=L(G)-。證明：證明： (1) 構造構造 設設CFG G=(V，T，P，S) ， 用用算法算法6-3求出求出G的可空變量集的可空變量集U， 構造構造P。 2021-12-12646.2.2 去去-產生式產生式 對于對于 AX1X2XmP 將將A12m放入放入P，其中，其中 if XiU then i=Xi或者或者i=； if Xi U then i=Xi 要求：在同一產生式中，要求：在同一產生式中，1，2，m不不能同時為能同時為。 2021-12-1

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

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

41、立。成立。2021-12-12696.2.2 去去-產生式產生式充分性：設充分性：設AmG w，施歸納于，施歸納于m，證明，證明AnG w成立。成立。當當m=1時，由時，由AG w知，知，AwP，按照定，按照定理所給的構造理所給的構造G的方法，必定有的方法，必定有AP。Aw是通過刪除產生式是通過刪除產生式A右部中的可空右部中的可空變量而構造出來的，所以，變量而構造出來的，所以，AG *G w 成立。成立。 2021-12-12706.2.2 去去-產生式產生式設設nk時結論成立時結論成立(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 去去-產生式產生式表明表明A XiXjXkP。按照。按照G的構造方法，的構造方法，必定存在必定存在A X1X2XmP，而且，而且Xi，Xj，Xk X1，X2，XmX1，X2，Xm-Xi，Xj，Xk U從而，從而，AG X1X2Xm *G XiXjXk2021-12-12726.2.2 去去-產生式產生式再根據再根據Xi*G wi，Xj*G wj，Xk*G wk和歸納和歸納假設，有假設，有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 去去-產生式產生式表明表明結論對結論對m=k+1成立。由歸納法原理，結成立。由歸納法原理，結論對任意論對任意m成立。成立。注意到注意到A 的任意性，當的任意性，當S=A時結論成立。即：時結論成立。即：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 去單一產生式去單一產生式 文法文法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 去單一產生式去單一產生式 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 去單一產生式去單一產生式 單一產生式單一產生式(unit production) 形如形如AB的產生式稱為的產生式稱為單一產生式。單一產生式。 定理定理 6-8對于任意對于任意CFG G， L(G)，存在，存在等價的等價的CFG G1，G1不含無用符號、不含無用符號、-產生產生式和單一產生式

46、。式和單一產生式。 滿足本定理的滿足本定理的CFG為為化簡過的文法。化簡過的文法。 已有去無用符號和去已有去無用符號和去-產生式的結論，所以產生式的結論，所以只討論去單一產生式的問題。只討論去單一產生式的問題。 2021-12-12786.2.3 去單一產生式去單一產生式 證明要點：證明要點： （1）構造）構造G2，滿足，滿足L(G2)=L(G)，并且，并且G2中中不含單一產生式。不含單一產生式。用非單一產生式用非單一產生式A1取代取代A1*G An用到用到的產生式系列的產生式系列 A1A2，A2A3，An-1An，An。其中，。其中，A1A2，A2A3，An-1An都是單一產生式。都是單一產

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

48、刪除G2中的無用符號。中的無用符號。由于在刪除單一產生式后，文法中可能出由于在刪除單一產生式后，文法中可能出現新的無用符號，因此，我們還需要再次現新的無用符號，因此，我們還需要再次刪除新出現的無用符號。刪除新出現的無用符號。 此外，在去此外，在去-產生式后可能會產生新的單一產生式后可能會產生新的單一產生式，也可能會引進新的無用符號。這產生式，也可能會引進新的無用符號。這是值得注意的。是值得注意的。 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)中的產生式形式：中的產生式形式：ABC，Aa其中，其中，A、B、CV，aT。 CNF中，不允許有中，不允許有-產生式、單一產生式。產生式、單一產生式。 2021-12-12836.3 喬姆斯基范式喬姆斯基范式 例例 6-3-1 試將文法試將文法Gexp4轉換成等價的轉換成等價的 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、. 構造構造CNF按照上述例子所描述的轉換方法，在構造給定按照上述例子所描述的轉換方法，在構造給定CFG的的CNF時，可以分兩步走。時，可以分兩步走。 假設假設G為化簡過的文法為化簡過的文法 構造構造G1=(V1，T，P1，S) G1中的產生式都是形如中的產生式都是形如AB1B2Bm和和Aa的產生式，其中，的產生式，其中，A，B1，B2，BmV1，aT，m2 2021-12-12876.3 喬姆斯基范式喬姆斯基范式 構造構造CNF G2=(V2，T，P2，S)。 m3時，引入新變量：時，引入新變量：B1、B2、Bm-2，將將G1的形如的形如AA1A2Am的產生式替換成的產生式替換成AA1B1B

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

54、先引入變量先引入變量Ba，Bb和產生式和產生式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 喬姆斯基范式喬姆斯基范式 不能因為原來有產生式不能因為原來有產生式A a和和B b而放而放棄引進變量棄引進變量Ba 、Bb和產生式和產生式Baa 、Bbb。 L(A

55、)=x | xa，b+ & x中中a的個數比的個數比b的個的個數恰多數恰多1個個。 L(B)=x | xa，b+ & x中中b的個數比的個數比a的個的個數恰多數恰多1個個。 L(Ba)= a 。 L(Bb)= b 。 2021-12-12936.4 格雷巴赫范式格雷巴赫范式格雷巴赫范式文法格雷巴赫范式文法(Greibach normal form ,GNF)簡稱為簡稱為Greibach文法文法，或，或Greibach范式。范式。Aa 其中，其中，AV，aT，V* 。在在GNF中，有如下兩種形式的產生式中，有如下兩種形式的產生式AaAaA1A2Am(m1) 2021-12-129

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

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

58、量的產生式是變量A的的直接遞歸直接遞歸的的(directly recursive)產生式。產生式。2021-12-12986.4 格雷巴赫范式格雷巴赫范式 當當n2時，稱該派生是關于變量時，稱該派生是關于變量A的的間接遞間接遞歸歸(indirectly recursive)派派生。簡稱為間接生。簡稱為間接遞歸派生。遞歸派生。 當當=時，稱相應的時，稱相應的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)左遞歸左遞歸(left-recursive)； 當當=時，稱相應的時，稱相應的(直接直接/間接間接)遞歸為遞歸為(直接直接/間接間接)右遞歸右遞歸(right-recursive)。2021-12-12996.4 格雷巴赫范式格雷巴赫范式 引理引理 6-2 對于任意的對于任意的CFG G=(V，T，P，S)，G中所有中所有A的產生式的產生式 A1 |2 |mA1B |2 B |m BB1 |2 |nB1B |2 B |n B 可以被等價地替換為產生式組可以被等價地替換為產生式組AA1 |A2 |AnA1 |2 |m2021-12-121006.4 格雷巴赫范式格雷巴赫范式 證明要點：證明要點： 用直接右遞歸取代原來的直接左