編譯原理習(xí)題.ppt

1、習(xí)題1 6試用各種不同的形式表示法描述1的一切精度 的近似值集合。 解：省略表示法 1.3,1.33,1.333, 描述表示法 1.3i|i1或1.3i|i=1 錯誤： x| x=1+310-i|i=1, 因為形式表示不應(yīng)涉及任何含義。 錯誤：GN: N:=1.M M:=M3 M:=3, 因為文法僅一組重寫規(guī)則，不是語言。 若給出答案：L(GN)，正確，但不簡潔,7. 設(shè)字母表x=0,1,2,3,4,5,6,7,X+與X*各是什么？ 各舉出4個不同長度的符號串作為例子。 解：X是字母表x的正閉包，X*是字母表的閉包， X*=X+ X+=0,1,00,01,123,345,1234,2345，

2、因此是一切可能帶前導(dǎo)0的八進(jìn)制數(shù)的集合 X*=,0,1,00,01,12,345,3456, X+ :0,1,00,123 X* :, 1,00,123,習(xí)題2 2設(shè)文法G的規(guī)則是: :=a|b|c|a|c|0|1 試寫出VT與VN, 并對下列符號串a(chǎn)、ab0、a0c01、0a、 11與aaa給出可能的推導(dǎo)。 解：VT=a,b,c,0,1 VN= a: = a ab0: = 0 不能直接推導(dǎo)出 b0 , 因此不能直接推導(dǎo)出ab0 (不能寫: =0=b0 不能推導(dǎo)出ab0) a0c01: =1=01=c01 =0c01 = a0c01 0a: = a 不能直接推導(dǎo)出0a (不能寫: =a = 0

3、a 不能推導(dǎo)出0a） 11: = 1 不能直接推導(dǎo)出11 (不能寫： = 1= 11 不能推導(dǎo)出11) aaa: = a = aa = aaa,3設(shè)GE: E:=T|E+T|E-T T:=F|T*F|T/F F:=(E)|i 1) 試給出關(guān)于(i)、i*i-i與(i+i)/i的推導(dǎo)。 2) 證明E+T*F*i+I 是該文法的句型，然后列出它的一切短語與簡單短語。 解：1）給出推導(dǎo) E = T = F = (E) = (T) = (F) = (i) 不能寫：E = T = F = (E) = (i) 可以寫: E = T = F = (E) = + (i) E = E-T = T-T = T*F

4、-T = F*F-T = i*F-T = i*i-T = i*i-F = i*i-i (最左推導(dǎo)) 或 E = E-T = E-F = E-i =T-i = T*F-i = T*i-i = F*i-i =i*i-i (最右推導(dǎo)),E = T = T/F = F/F = (E)/F = (E+T)/F = (T+T)/F = (F+T)/F = (i+T)/F = (i+F)/F = (i+i)/F = (i+i)/i (最左推導(dǎo)) 或 E = T = T/F = T/i = F/i = (E)/i = (E+T)/i = (E+F)/i = (E+i)/i = (T+i)/i =(F+i)/i

5、 = (i+i)/i ( 最右推導(dǎo)),2) 證明E+T*F*i+i是該文法的句型： E = E+T = E+T+T = E+T*F+T = E+T*F*F+T = E+T*F*i+T = E+T*F*i+F = E+T*F*i+i 或E = E+T = E+F = E+i =E+T+i= E+T*F+i = E+T*i+i = E+T*F*i+i 即，E=* E+T*F*i+i，所以是該文法的句型。 因為 E=* E E=+ E+T*F*i+i E=* E+i E=+ E+T*F*i E=* E+T+i T=+ T*F*i E=* E+T*F*i+T T=+ i E=* E+T*i+i T=

6、T*F E=* E+T*F*F+F F= i (=+ 包括=) 所以 句型E+T*F*i+i中 相對于E的短語有 E+T*F*i+i和E+T*F*i 相對于T的短語有T*F*i、T*F和i 相對于F的短語有i 所以 句型E+T*F*i+i中 相對于T的簡單短語有T*F 相對于F的簡單短語有i,不能用畫語法分析樹的方法來尋找短語，因按教學(xué)進(jìn)度，還未講到語法分析樹。 簡單短語可如下尋找：首先尋找與規(guī)則右部相同的子符號串，把它歸約成相應(yīng)的非終結(jié)符號后,看是否是句型, 如果仍是，則此子符號串是簡單短語，否則不是。例如，子符號串E+T, 可歸約成E,但歸約后成為E*F*i+i, 顯然不是句型，所以，E+

7、T不是簡單短語。 對于短語，類似地尋找，即，先找子符號串,看它能否歸約到某個非終結(jié)符號, 再看歸約后得到的新符號串是否是句型，是，則是短語，否則，不是短語。 當(dāng)在學(xué)習(xí)了語法分析樹之后，可以也應(yīng)該使用語法分析樹來尋找短語與簡單短語。,2) ambn|nm0 解：可把ambn(nm0)寫成ambmbn-m。 易見可有文法GS： S:=Sb| Ab A:=ab|aAb 也可以寫出下列文法：GS： S:=ab2|Sb|aSb 或GS： S:=aSbaBb B:=Bbb 可見給定一個語言，可以為它構(gòu)成若干個不同的文法。,習(xí)題3 4通常程序設(shè)計語言包含一些嵌套結(jié)構(gòu)，例如，平衡的括號對，以及對應(yīng)的if與el

8、se等。試簡要說明為什么這些結(jié)構(gòu)不能用正則文法描述。 答：通常程序設(shè)計語言必定包含一些嵌套結(jié)構(gòu), 例如，平衡的括號對，以及對應(yīng)的if與else等。它們的存在必定因下列規(guī)則的必定存在： E:=E+T|T T:=T*F|F F:=(E)|i 以及 S:=if(E)S else S 因此，E=* xEy x, y 與 S=* uSv u, v, 即, E與S等必定是具有自嵌套特性的非終結(jié)符號。因此通常的程序設(shè)計語言的文法必具有自嵌套特性的非終結(jié)符號，也就是說不可能是正則文法。,5下列文法中哪一個是自嵌套的，請說明理由。 對于非自嵌套文法給出等價的正則文法。 G1=(A,B,C,a,b,P1,A) P

9、1： A:=CB|b B:=CA C:=AB|a 答：因存在自嵌套的非終結(jié)符號B： B=CA=ABA 即，B=* ABA，A, 所以文法G1是自嵌套的。 G2=(A,B,C,a,b,P2,A) P2： A:=CB|Ca B:=bC C:=aB|b 答：因不可能得到推導(dǎo)：A=* xAy, 其中 ，對于B與C，情況類似，所以A、B與C都不是自嵌套的非終結(jié)符號，文法G2是非自嵌套的文法。 為構(gòu)造等價的正則文法，首先確定相應(yīng)語言。,C=aB=abC=abaB=ababC=(ab)iC =(ab)ib， 即，C=* (ab)ib B=bC=baB=(ba)iB=(ba)ibC =* (ba)ib(ab)

10、jb 即，B=* (ba)ib(ab)jb A=CB=* (ab)ib (ba)jb(ab)kb 又，A=Ca=(ab)iba 即, A=* (ab)iba, 所以, L(G2)=(ab) ib (ba) jb(ab)kb|i,j,k0(ab)i ba|i0 對于文法G2,可以采用圖示法給出相應(yīng)的正則文法 a b a bab b a 可給出如下的規(guī)則： A A:=a A:=Ba B:=Ab B C:=Bb S:=Ca A B C S,顯然，S=Ca=Bba=Abba=Babba=Ababba =Bababba=B(ab)i-1ba=(ab)iba 即， S=* (ab)iba (i=1)。 為

11、使i=0,讓C:=b，因此，對于(ab)iba|i=0有下列規(guī)則： S:=Ca C:=Bb|b B:=Ab A:=Ba|a 對于(ab)ib(ba)jb(ab)kb|i,j,k=0可類似地給出一組規(guī)則，這里不擬詳細(xì)給出。只是請注意：可利用前面的規(guī)則以減少規(guī)則的個數(shù)。,習(xí)題4 4試用不同的方法消去文法G：I:=Ia|Ib|c 的 規(guī)則左遞歸。 解: 步驟1 判定文法是規(guī)則左遞歸 步驟2 消去規(guī)左遞歸。 步驟3 方法1 改寫規(guī)則左遞歸成右遞歸。 等價文法G為： I:=cI I:=(a|b)I| 方法2 改寫成擴充BNF表示法. 應(yīng)用規(guī)則1提因子有：I:=I(a|b)|c， 應(yīng)用規(guī)則2有I:=ca|

12、b 等價文法G 為：I:=ca|b,5試消去文法GW：W:=A0 A:=A0|W1|0 的 文法左遞歸與規(guī)則左遞歸。 解: 步驟1 判定文法是文法左遞歸還是規(guī)則左遞歸 步驟2 判定文法是文法左遞歸，所以按相應(yīng)算 法消去文法左遞歸如下。 步驟2.1：把終結(jié)符排序成U1=W, U2=A(n=2) 步驟2.2：執(zhí)行循環(huán) i=1 j=1:ji 1 不執(zhí)行關(guān)于j的循環(huán)， 且關(guān)于U1=W 不存在規(guī)則左遞歸。 i=2 j=1,有規(guī)則 A:=W1|A0|0形如U2:=U1,把U1:=r1， 即，把W:=A0代入得：A:=A01|A0|0 即， A:=A(01|0)|0 j=2, ji-1 消去關(guān)于U2=A的規(guī)

13、則左遞歸有 A:=0A, A:=(01|0)A|,步驟3 最后得到消去左遞歸的等價文法GW： W:=A0 A:=0A A:= (01|1)A| 說明：如果在第二步中，把原文法等價變換成擴充表示法，則最終的等價文法是 GW: W:=A0 A:=001|0,6試消去文法GS： S:=Qc|Rd|c Q:=Rb|Se|b R:=Sa|Qf|a 解: 步驟1 首先判定是文法左遞歸還是規(guī)則左遞歸 步驟2 是文法左遞歸，按相應(yīng)算法處理如下。 步驟2.1 把非終結(jié)符號排序成 U1=S U2=Q U3=R (n=3) 步驟2.2 執(zhí)行循環(huán)： i=1 j=1: ji 1，不執(zhí)行關(guān)于j的循環(huán), 且關(guān)于U1=S 不

14、存在規(guī)則左遞歸。 i=2 j=1,有規(guī)則Q:=Se|Rb|b,形如U2:=U1,把U1:=r1即，把S:=Qc|Rd|c 代入，得：Q:= (Qc|Rd|c)e| Rb|b，整理后 Q:= Qce|Rde| Rb|ce|b j=2, ji-1 對U2其消去規(guī)則左遞歸，得 Q:=(R(de|b)|ce|b)Q Q:=ceQ|,(按擴充表示法，有 Q:=（Rb|Rde|ce|b）ce ) i=3 j=1,有規(guī)則R:=Sa|Qf|a，形如U3:=U1形，把U1:=r1, 即，S:=Qc|Rd|c代入: R:=(Qc|Rd|c)a|Qf|a，整理后，R:= Rda| Qca| Qf| ca|a 注意:

15、 j循環(huán)還未結(jié)束,不能消去Ui=R的規(guī)則左遞歸! j=2,有規(guī)則R:= Rda| Qca| Qf| ca|a，形如U3:=U2， 把 U2:=r2,即，把Q:=(R(b|de)|ce|b)Q 代入， (按擴充表示法代入的是 Q:=(Rb|Rde|ce|b)ce) ) 所以 R:=Rda| (R(b|de)|ce|b)Q(ca|f)| ca|a， 整理:R:=R(b|de)Q(ca|f)|da)|(ce|b)Q(ca|f)|ca|a j=3, ji-1 消去關(guān)于U3=R的規(guī)則左遞歸,得： R:= (ce|b)Q(ca|f)|ca|a)R R:=(b|de)Q(ca|f)|da)R| (當(dāng)按擴充表

16、示法時是:R:=(ce|b)Q(ca|f)|ca|a)(b|de)Q(ca|f)|da ),步驟3 最后消去了左遞歸的等價文法GS： S:=Qc|Rd|c Q:=(R(b|de)|ce|b)Q Q:=ceQ| R:= (b|ce)Q(ca|f)|ca|a)R R:=(b|de)Q(ca|f)|da）R| (按擴充表示法時是GS: S:=Qc|Rd|c Q:=(Rb|Rde|ce|b)ce R:= (ce|b)Q(ca|f)|ca|a)(b|de)Q(ca|f)|da ),習(xí)題5 1. 設(shè)有文法GS： S:=aAcB|BdS B:=aScA|cAB|b A:=BaB|aBc|a 試對下列符號串：

17、1）aabcccab 2) ababccbb 進(jìn)行句型分析，識別是否是文法GS的句子。當(dāng)是句子時，給出 最左推導(dǎo)、最右推導(dǎo)與相應(yīng)的語法分析樹。 解：1）建立最左推導(dǎo)如下： S= aAcB = aaBccB=aabccB =aabcccAB =aabcccaB=aabcccab 即,S=* aabcccab 因此，aabcccab是該文法的句子。最右推導(dǎo)如下: S=aAcB=aAccAB=aAccAb=aAccab =aaBcccab= aabcccab 語法分析樹：,畫語法分析樹并不一定要先寫出推導(dǎo)，事實上，根據(jù)所給符號串的形式來選擇合適的規(guī)則便可。例如，輸入符號串是（i），不包含if，自然選

18、擇 I:=E，之后，因有(與)，自然選E:=(E)，等等。 對于輸入符號串if i then i else (i)，自然選擇I:=if B T。 其他情況類似。,3.為題2中的狀態(tài)轉(zhuǎn)換圖寫出相應(yīng)的有窮狀態(tài)自動 機。它能接受字符串0011011嗎？ 解：這是一個確定有窮狀態(tài)自動機，因此可寫出DFA D如下： DFA D=(K,0,1,M,A,E,F) 其中 K=A,B,C,D,E,F M：M(A,0)=B M(B,0)=D M(B,1)=C M(C,0)=A M(C,1)=F M(D,0)=A M(D,1)=C M(E,0)=D M(E,1)=C M(F,0)=E M(F,1)=A,M：M(A,

19、0)=B M(B,0)=D M(B,1)=C M(C,0)=A M(C,1)=F M(D,0)=A M(D,1)=C M(E,0)=D M(E,1)=C M(F,0)=E M(F,1)=A 對輸入字符串0011011運行該DFA： M(A,0011011) =M(M(A,0),011011) =M(M(B,0),11011) =M(M(D,1),1011) =M(M(C,1),011) =M(M(F,0),11) =M(M(E,1),1) =M(C,1)=F 因為FE,F, 所以字符串0011011可以被該DFA所接受。 注意，在一般情況下，必須首先判別是確定的FA，還是非確定的FA，然后再寫

20、出相應(yīng)的FA。,6. 設(shè)有NFA，其狀態(tài)轉(zhuǎn)換圖如圖所示，試為其構(gòu)造DFA。 解：步驟1 首先寫出NFA，然后再確定化。 NFA N (S,V,M,U,Z,0,1,M,S,Z） 其中: M : M(S,0)=V,M M(S,1)=M,U M(V,0) =Z M(V,1)= M(M,0)=V,M M(M,1)=M,U M(U,0)= M(U,1)=Z M(Z,0) =Z M(Z,1)=Z,步驟3 構(gòu)造DFA如下： DFA N=(K,0,1, M, S, F) 其中：K= S, MV,MU, MUZ, MVZ M:M(S,0) =VM M(S,1) =MU M(MV,0) = MVZ M(MV,1)

21、 =MU M(MU,0) = MV M(MU,1) =MUZ M(MVZ,0)= MVZ M(MVZ,1) =MUZ M(MUZ,0)= MVZ M(MUZ,1) =MUZ F= MVZ, MUZ,注意： 1. DFA N的狀態(tài)名必須用方括號對與括住，且狀態(tài)名中所包含的字母必須按字典順序排列（數(shù)字也一樣）。 2. 終止?fàn)顟B(tài)之名則必須包含原NFA中終止?fàn)顟B(tài)名，如，新終止?fàn)顟B(tài)名MVZ中包含了原終止?fàn)顟B(tài)名Z。,7. 設(shè)有NFA A=(q0,q1,q2, a,b,M,q0,q1), 其中M為: M(q0,a)=q1,q2 M(q0,b)=q0 M(q1,a)=q0,q1 M(q1,b)= M(q2,a

22、)=q0,q2 M(q2,b)=q 試為其構(gòu)造DFA, 它能接受bababab與abababb嗎？ 解：首先寫出狀態(tài)轉(zhuǎn)換矩陣如下。 a b q0 q1,q2 q0 q1,q2 q0,q1,q2 q1 q0,q1,q2 q0,q1,q2 q0q1 q1 q0q1 q0,q1 q0,q1,q2 q0,所以 DFA A=(K,a,b,M,q0,F) 其中：K=q0,q1, q0q1, q1q2, q0q1q2 M: M(q0,a) =q1q2 M(q0,b)=q0 M(q1q2,a) =q0q1q2 M(q1q2,b)=q1 M(q0q1q2,a)= q0q1q2 M(q0q1q2,b)=q0q1

23、M(q1,a) =q0q1 M(q0q1,a) = q0q1q2 M(q0q1,b)=q0 F=q1,q1q2,q0q1,q0q1q2,運行DFA A： 輸入字符串bababab M(q0, bababab) =M(M(q0,b), ababab) =M(M(q0, a), babab)=M(M(q1q2,b), abab) =M(M(q1,a), bab) =M(M(q0q1,b), ab) =M(M(q0, a), b) =M(q1q2, b)=q1 因為q1F, 所以，輸入字符串bababab可為該DFA A所接受。,輸入字符串a(chǎn)bababb M(q0, abababb)=M(M(q0,

24、a), bababb) =M(M(q1q2, b), ababb) =M(M(q1,a), babb)= M(M(q0q1,b), abb) = M(M(q0,a), bb) =M(M(q1q2, b),b)=M(q1, b) 因為M(q1, b)不存在，所以，輸入字符串a(chǎn)bababb不可為DFA A所接受。 運行狀態(tài)轉(zhuǎn)換圖時請注意： 1必須說明最終的狀態(tài)屬于終止?fàn)顟B(tài)集，才說可接受。 2不要寫成：M (q1,b)=，只能寫成：M(q1,b)不存在（因而不可接受）。,習(xí)題7 7. 試為文法GS： S:=SaB|bB A:=S|a B:=Ac 構(gòu)造預(yù)測分析表，并識別輸入符號串bacaac是否該文法

25、的句子。 解：首先判別文法是否滿足兩個先決條件。 因為不滿足，進(jìn)行文法等價變換，消去左遞歸 ，得到等價文法如下： S:=bBS S:=aBS| A:=S|a B:=Ac 為其構(gòu)造預(yù)測分析表，現(xiàn)構(gòu)造如下。 a b c # S S:=bBS S S:=aBS S:= S:= A A:=a A:=S B B:=Ac B:=Ac,a b c # S S:=bBS S S:=aBS S:= S:= A A:=a A:=S B B:=Ac B:=Ac,所以輸入符號串bacaac 是該文法的句子 。,習(xí)題8 1. 根據(jù)下列語法分析樹，確定全部簡單優(yōu)先關(guān)系（以矩陣形式給出)。 解： E 簡單優(yōu)先矩陣如下： E

26、 T F i * ( ) E T E T F T T * F i F F ( E ) i i T * F ( I ) ,習(xí)題10 3試為文法GZ：Z:=A() A:=( |Ai|B) B:=i 構(gòu)造算符優(yōu)先關(guān)系。 解：易見 () 構(gòu)造優(yōu)先關(guān)系 , 尋找規(guī)則 U:=VT的規(guī)則, 由規(guī)則Z:=A(), 因A=* ( , A=* i 以及A=* ), 所以, ( (, i ( , ) ( 。類似地, 由A:=Ai以及A:=B), 有: ( i, ( ) i i i , ) i, ( (, i ( , ( = ) ( , 以及 i ) ) 算符優(yōu)先矩陣如右所示。 i 當(dāng)然，也可以利用語法分析樹尋找優(yōu)先

27、關(guān)系。,習(xí)題11 4. 試?yán)帽?-10中的分析表識別符號串(i+i)*i+i是否是文法G5.5的句子。給出識別過程。注意，請指出每步動作。 解：題目要求指明每個分析步的動作，因此以表的形式給出分析過程。 文法G5.5E： 1：E:=E+T 2：E:=T 3：T:=T*F 4：T:=F 5：F:=(E) 6：F:=i 分析過程見下面。最終結(jié)果表明，輸入符號串(i+i)*i+i是文法G5.5的句子。,分析表,所以輸入符號串(i+i)*i+i是該文法的句子。,習(xí)題12 1. 根據(jù)例6.2中所給語法制導(dǎo)定義，關(guān)于輸入符號串int i, j 構(gòu)造注釋分析數(shù)。 解：語法制到定義如下：,可畫出注釋分析樹如

28、下。,習(xí)題13 1. 為下列類型寫出類型表達(dá)式： （1）指向?qū)嵭蛿?shù)據(jù)的指針數(shù)組，該數(shù)組的上下界分別為100與1。 （2）一個函數(shù)，實參為一個整型數(shù)，返回值為一個指針，它指向由一個整型數(shù)和一個字符組成的結(jié)構(gòu)體。 解：(1) 按約定，相應(yīng)的類型表達(dá)式是： array(1.100, pointer(real) (2) 按約定，相應(yīng)的類型表達(dá)式是： integerpointer(record(iinteger)(cchar),2. 設(shè)有C語言程序片段如下： struct cell int a; int b; ; typedef struct cell * pcell; cell Buf200; pce

29、ll handle(int x, cell y) 試給出標(biāo)識符Buf與Handle所關(guān)聯(lián)的類型表達(dá)式。 解：Buf所關(guān)聯(lián)的類型表達(dá)式是： array(0.199, cell) 其中cell所關(guān)聯(lián)的類型表達(dá)式是： record(ainteger)(binteger) Handle所關(guān)聯(lián)的類型表達(dá)式是：integercellPcell 其中Pcell所關(guān)聯(lián)的類型表達(dá)式是： pointer(cell),習(xí)題14 1. 試為下列賦值語句 x=a/(b+c)-d*(e+f)生成目標(biāo)代碼，其中用變量名表示存儲地址，且假定有三個寄存器可用。 解：目標(biāo)代碼如下。 MOV b, r1 ADD c, r1 MOV

30、 a, r2 DIV r1, r2 MOV e, r1 ADD f, r1 MOV d, r3 DIV r1, r3 SUB r3, r2 MOV r2, x,3. 試應(yīng)用6.3.3.2節(jié)中關(guān)于條件語句的翻譯方案， 給出下列條件語句的目標(biāo)代碼： if(a0) x=b-a; else x=a-b; 解： MOV a, t2 MOV a, t4 CMP t5, #1 CMP t2, b CMP t4, #0 CJ= l1 CJ *+8 GOTO L2 GOTO *+12 GOTO *+12 L1: MOV b, t6 MOV #1, t1 MOV #1, t3 SUB a, t6 GOTO *+8

31、 GOTO *+8 MOV t6, x MOV #0, t1 MOV #0, t3 GOTO L3 MOV t1, t5 L2: MOV a, t7 AND t3, t5 SUB b, t7 MOV t7, x L3:,5. 試給出賦值語句序列： n=1; while(2*n-1)*(2*n-1)!=399) n=n+1; 的目標(biāo)代碼。 解：L1：MOV #2， t1 L2：MOV n， t4 MPY n， t1 ADD #1， t4 SUB #1， t1 MOV t4， n MOV #2， t2 GOTO L1 MPY n， t2 L0： ADD #1， t2 MPY t2， t1 MOV

32、t1， t3 CMP t3， #399 CJ L2 GOTO L0,習(xí)題15 2. 試把表達(dá)式（a+b)*(c-d)-(a*b+c)翻譯成： （1）逆波蘭表示 （2） 四元式序列 （3） 三元式序列 解：(1) 逆波蘭表示： ab+cd-*ab*c+- (2) 四元式序列 (3) 三元式序列 + a b t1 + a b - c d t2 - c d * t1 t2 t3 * * a b t4 * a b + t4 c t5 + c - t3 t5 t6 -,3. 試把逆波蘭表示 abc*-de+/f- 還原成中綴表達(dá)式 解：還原成：(a-b*c)/(d+e)-f 6. 試寫出題4中程序片段的四元式表示。 解:positive=0; negative=0; 先展開循環(huán)如下。 zero=0; i=1; for(i=1; i100) goto FINISH; if(Ai0) if(Ai0) positive=positive+1; positive=positive+1; else if(Ai=0) else if(Ai=0) zero=zero+1; zero=zero+1; else else negative=negative+1; negative=ne