1、習(xí)題1 1.1解釋名詞：源語(yǔ)言、目標(biāo)語(yǔ)言、翻譯器、編譯器和解釋器。答：源語(yǔ)言是指待翻譯的語(yǔ)言，和目標(biāo)語(yǔ)言相對(duì)。目標(biāo)語(yǔ)言是指被翻譯的語(yǔ)言，與源語(yǔ)言相對(duì)。能夠完成從一種語(yǔ)言到另一種語(yǔ)言的變換的軟件稱為翻譯器，這兩種語(yǔ)言分別叫做該翻譯器的源語(yǔ)言和目標(biāo)語(yǔ)言。編譯器是一種特殊的翻譯器，它進(jìn)行語(yǔ)言變換的特點(diǎn)是目標(biāo)語(yǔ)言比源語(yǔ)言低級(jí)。解釋器是不同于編譯器的另一類語(yǔ)言處理器。它不像編譯器那樣通過翻譯來生成目標(biāo)程序，而是直接執(zhí)行源程序所指定的運(yùn)算。它的執(zhí)行方式是一邊翻譯一邊執(zhí)行，因此其執(zhí)行效率一般偏低。1.2典型的編譯器可以劃分成幾個(gè)主要的邏輯階段？各階段的主要功能是什么？答：典型的編譯器可以劃分成七個(gè)主要的邏輯

2、階段，分別是詞法分析器、語(yǔ)法分析器、語(yǔ)義分析器、中間代碼生成器、獨(dú)立于機(jī)器的代碼優(yōu)化器、代碼生成器、依賴于機(jī)器的代碼優(yōu)化器。各階段的主要功能：（1）詞法分析器：詞法分析閱讀構(gòu)成源程序的字符流，按編程語(yǔ)言的詞法規(guī)則把它們組成詞法記號(hào)流。（2）語(yǔ)法分析器：按編程語(yǔ)言的語(yǔ)法規(guī)則檢查詞法分析輸出的記號(hào)流是否符合這些規(guī)則，并依據(jù)這些規(guī)則所體現(xiàn)出的該語(yǔ)言的各種語(yǔ)言構(gòu)造的層次性，用各記號(hào)的第一元建成一種樹形的中間表示，這個(gè)中間表示用抽象語(yǔ)法的方式描繪了該記號(hào)流的語(yǔ)法情況。（3）語(yǔ)義分析器：使用語(yǔ)法樹和符號(hào)表中的信息，依據(jù)語(yǔ)言定義來檢查源程序的語(yǔ)義一致性，以保證程序各部分能有意義地結(jié)合在一起。它還收集類型信息

3、，把它們保存在符號(hào)表或語(yǔ)法樹中。（4）中間代碼生成器:為源程序產(chǎn)生更低級(jí)的顯示中間表示，可以認(rèn)為這種中間表示是一種抽象機(jī)的程序。（5）獨(dú)立于機(jī)器的代碼優(yōu)化器：試圖改進(jìn)中間代碼，以便產(chǎn)生較好的目標(biāo)代碼。通常，較好是指執(zhí)行較快，但也可能是其他目標(biāo)，如目標(biāo)代碼較短或目標(biāo)代碼執(zhí)行時(shí)能耗較低。（6）代碼生成器：取源程序的一種中間表示作為輸入并把它映射到一種目標(biāo)語(yǔ)言。如果目標(biāo)語(yǔ)言是機(jī)器代碼，則需要為源程序所用的變量選擇寄存器或內(nèi)存單元，然后把中間指令序列翻譯為完成同樣任務(wù)的機(jī)器指令序列。（7）依賴于機(jī)器的代碼優(yōu)化器：試圖改進(jìn)目標(biāo)機(jī)器代碼，以便產(chǎn)生較好的目標(biāo)機(jī)器代碼。第二章2.解：由題目分析可知，一個(gè)符號(hào)串

4、由0和1組成，則0和1的個(gè)數(shù)只能有四種情況：偶數(shù)個(gè)0和偶數(shù)個(gè)1（用狀態(tài)0表示）；偶數(shù)個(gè)0和奇數(shù)個(gè)1（用狀態(tài)1表示）；奇數(shù)個(gè)0和偶數(shù)個(gè)1（用狀態(tài)2表示）；奇數(shù)個(gè)0和奇數(shù)個(gè)1（用狀態(tài)3表示）。所以，狀態(tài)0（偶數(shù)個(gè)0和偶數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0 和奇數(shù)個(gè)1（狀態(tài)1）； 狀態(tài)0（偶數(shù)個(gè)0和偶數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0 和偶數(shù)個(gè)1（狀態(tài)2）；狀態(tài)1（偶數(shù)個(gè)0和奇數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0 和偶數(shù)個(gè)1（狀態(tài)0）；狀態(tài)1（偶數(shù)個(gè)0和奇數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0 和奇數(shù)個(gè)1（狀態(tài)3）；狀態(tài)2（奇數(shù)個(gè)0和偶數(shù)個(gè)1）讀入1，則0和1的數(shù)目變

5、為：奇數(shù)個(gè)0 和奇數(shù)個(gè)1（狀態(tài)3）； 狀態(tài)2（奇數(shù)個(gè)0和偶數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0和偶數(shù)個(gè)1（狀態(tài)0）；狀態(tài)3（奇數(shù)個(gè)0和奇數(shù)個(gè)1）讀入1，則0和1的數(shù)目變?yōu)椋浩鏀?shù)個(gè)0 和偶數(shù)個(gè)1（狀態(tài)2）；狀態(tài)3（奇數(shù)個(gè)0和奇數(shù)個(gè)1）讀入0，則0和1的數(shù)目變?yōu)椋号紨?shù)個(gè)0 和奇數(shù)個(gè)1（狀態(tài)1）。因?yàn)?，所求為由偶?shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串，故狀態(tài)0既為初始狀態(tài)，又為終結(jié)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖如下面的圖1所示：200011111300start圖11.解：由狀態(tài)轉(zhuǎn)換圖可以寫出其正規(guī)文法為：S01S1|0S2|S11S0|0S3|1S21S3|0S0|0S31S2|0S1在不考慮S0產(chǎn)生式

6、的情況下，可以將文法變形為：S0=1S1+0S2S1=1S0+0S3+1 S2=1S3+0S0+0S3=1S2+0S1所以S0=(00|11)S0+(01|10)S3+11+00(1) S3=(00|11)S3+(01|10)S0+01+10 (2)解(2)式得：S3=(00|11)*(01|10)S0+(01|10)代入(1)式得：S0=(00|11)S0+(01|10)(00|11)*(01|10)S0+(01|10)+(00|11)=S0=(00|11)S0+(01|10)(00|11)*(01|10)S0+(01|10)(00|11)*(01|10)+(00|11)=S0=(00|11

7、)+(01|10)(00|11)*(01|10)S0+(01|10)(00|11)*(01|10)+(00|11)=S0=(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*(01|10)+(00|11)=S0=(00|11)|(01|10)(00|11)*(01|10)*(00|11)+(01|10)(00|11)*(01|10)=S0=(00|11)|(01|10)(00|11)*(01|10)*(00|11)|(01|10)(00|11)*(01|10)=S0=(00|11)|(01|10)(00|11)*(01|10)+=S0=(00|11|(0

8、1|10)(00|11)*(01|10)+因?yàn)镾0所以由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的01串的正規(guī)式為：S0(00|11|(01|10)(00|11)*(01|10)*由正規(guī)式(00|11|(01|10)(00|11)*(01|10)*畫其NFA答：先畫正規(guī)式分析樹如圖 1所示。圖 1NFA如圖 2所示。圖 2由上面的NFA轉(zhuǎn)換圖得：-closure(1)=1,2,36,3,27,4,7,28,31=A-closure(move(A,1)= -closure(8,32)=8,32=B-closure(move(A,0)= -closure(5,29)=5,29=C-closure(move(B,1)

9、= -closure(33)=33,34,35,36,2,3,27,4,7,28,31=D-closure(move(B,0)= -closure(9)=9,10,11,19,12,15,20,23=E-closure(move(C,1)= -closure(6)=6,10,11,19,12,15,20,23=F-closure(move(C,0)= -closure(30)=30,34,35,36,2,3,27,4,7,28,31=G-closure(move(D,1)= -closure(8,32)=B-closure(move(D,0)= -closure(5,29)=C-closure

10、(move(E,1)= -closure(16,24)=16,24=H-closure(move(E,0)= -closure(13,21)=13,21=I-closure(move(F,1)= -closure(16,24)=16,24=H-closure(move(F,0)= -closure(13,21)=13,21=I-closure(move(G,1)= -closure(8,32)=8,32=B-closure(move(G,0)= -closure(5,29)=5,29=C-closure(move(H,1)= -closure(17)=17,18,11,19,12,15,20,

11、23=J-closure(move(H,0)= -closure(25)=25,26,35,36,2,3,27,4,7,28,31=k-closure(move(I,1)= -closure(22)=22,26,35,36,2,3,27,4,7,28,31=L-closure(move(I,0)= -closure(14)=14,18,11,19,12,15,20,23=M-closure(move(J,1)= -closure(16,24)=16,24=H-closure(move(J,0)= -closure(13,21)=13,21=I-closure(move(K,1)= -closu

12、re(8,32)=8,32=B-closure(move(K,0)= -closure(5,29)=5,29=C-closure(move(L,1)= -closure(8,32)=8,32=B-closure(move(L,0)= -closure(5,29)=5,29=C-closure(move(M,1)= -closure(16,24)=16,24=H-closure(move(M,0)= -closure(13,21)=13,21=IDFA的轉(zhuǎn)換表如下。狀態(tài)輸入符號(hào)10ABCBDECFGDBCEHIFHIGBCHJKILMJHIKBCLBCMHI這個(gè)DFA的轉(zhuǎn)換圖如下。0=B,C,E

13、,F,H,I,J,M,A,D,G,K,L1= E,F,J,M,A,D,G,K,L,B,C,H,I2= E,F,J,M,A,D,G,K,L,B,I,C,H最簡(jiǎn)DFA的轉(zhuǎn)換表如下。狀態(tài)輸入符號(hào)10ABCBAECEAECB極小化DFA的轉(zhuǎn)換圖如下。matched_stmt-if expr then matched_stmt else matched_stmt | other unmatched_stmt-if expr then matched_stmt | if expr then matched_stmt else unmatched_stmt ifexprthenmatched_stmtels

14、ematched_stmt ifexprthenmatched_stmtelseunmatched_stmt ifexprthenunmatched_stmtelsematched_stmt ifexprthenunmatched_stmtelseunmatched_stmt （3） 漏掉了還是包含在里面？（4） 能否由推出？若不能推出，會(huì)不會(huì)造成結(jié)構(gòu)性缺失？解：(1) 漏掉了。(2) 不能由推出，并且不會(huì)造成結(jié)構(gòu)性缺失。會(huì)使文法具有二義性。3.10構(gòu)造下面文法的LL（1）分析表。DTLTint | realLid RR,id R |解：DTL FIRST(D)=FIRST(TL)=FIRST

15、(T)= int, real Tint FIRST (int)= int T real FIRST (real)= real FIRST(T)= int，realLid R FIRST (L)=FIRST (id R)= id R，id R FIRST (，id R)= ，R FIRST ()= FIRST (R)=，, FOLLOW(R)= FOLLOW(L)=FOLLOW(D)=$由此得出上述文法的LL（1）分析表如下表所示。文法的LL（1）分析表intrealid,$DDTLDTLTTintT realLLid R RR,id RR非遞歸的預(yù)測(cè)分析對(duì)題3.10的預(yù)測(cè)分析器接受輸入分別為i

16、nt id，id id，id:real時(shí)的動(dòng)作根據(jù)上題中得出的分析表（表格 1）可得三列表分別為表格 2、表格 3。表格 1intrealid,$DDTLDTLTTintT realLLid R RR，id RR表格 2棧輸入輸出$Dint id，id$LTint id，id$DTL$L intint id，id$Tint$L id，id$Rid id，id$Lid R $R，id$ Rid， ，id$R，id R$ Ridid$ R$R表格 3棧輸入輸出$Did，id:real$因?yàn)镸D,id沒有產(chǎn)生式，出錯(cuò)，所以直接退出。3.18 求下面文法中非終結(jié)符的FIRST、FOLLOW集?！咀ⅲ何?/p>

17、法分析中不能判斷閉包、加號(hào)、乘號(hào)等符號(hào)，均視為終結(jié)符】EE+T|TTTF|FFF*|a|b解：F a FIRST(a)=a F b FIRST(b)=bFIRST(F)= FIRST(F*)FIRST(a)FIRST(b)=a,bFIRST(T)= FIRST(TF)FIRST(F) = FIRST(T)FIRST(F)= FIRST(F) =a,bFIRST(E)= FIRST(E+T)FIRST(T)= FIRST(E)FIRST(T) = FIRST(T)= a,b即FIRST(E)= FIRST(T)= FIRST(F)= a,bE為開始符號(hào)，F(xiàn)OLLOW(E)=+,$FOLLOW(T

18、)=FIRST(F)FOLLOW(E)=a,b+,$=a,b,+,$FOLLOW(F)=*,$FOLLOW(T)=*,$a,b,+,$=*,a,b,+,$即FOLLOW(E)=+,$FOLLOW(T) =a,b,+, $FOLLOW(F)=*,a,b,+, $一、解：LR分析器對(duì)于輸入id +id *id的格局變化和相應(yīng)動(dòng)作棧輸入動(dòng)作0id +id *id$移進(jìn)0 id 5+id *id$按Fid歸約0 F 3+id *id$按TF歸約0 T 2+id *id$按ET歸約0 E 1+id *id$移進(jìn)0 E 1 + 6id *id$移進(jìn)0 E 1 + 6 id 5*id$按Fid歸約0 E 1

19、 + 6 F 3*id$按TF歸約0 E 1 + 6 T 9*id$移進(jìn)0 E 1 + 6 T 9 * 7id$移進(jìn)0 E 1 + 6 T 9 * 7 id 5$按Fid歸約0 E 1 + 6 T 9 * 7 F 10$按TT*F歸約0 E 1 + 6 T 9 $按EE+T歸約0 E 1 $接受二、3.18 求下面文法EE+T|TTTF|FFF*|a|b解：拓廣文法：EEEE+T|TTTF|FFF*|a|bLR(0)項(xiàng)目集規(guī)范族(DFA構(gòu)造過程)：I0：EEEE+TETTTFTFFF*FaFbI1：EEEE+T I2：ETTTFFF*FaFbI3：TFFF* I4：FaI5：FbI6：EE+T

20、 TTFTFFF*FaFbI7：TTFFF*I8 ：FF*I9：EE+T TTF FF*FaFbEEEE+T ETTTFTFFF*FaFbFIRST(E)=FIRST(T)=FIRST(F)=a,bFOLLOW(E)=+,$FOLLOW(T)=a,b,+, $FOLLOW(F)=*,a,b,+, $表達(dá)式文法的分析表狀態(tài)動(dòng)作轉(zhuǎn)移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5r5r5r5r59r1s4s5r173.18 為下面文法構(gòu)造LR(1)分析表和LALR分析表EE+

21、T|TTTF|FFF*|a|b解：拓廣文法：EEEE+T|TTTF|FFF*|a|bFIRST(E)=FIRST(T)=FIRST(F)=a,bLR(1)項(xiàng)目集族(DFA構(gòu)造過程)： I0：EE，$EE+T，$/+ET，$/+TTF，$/+/a/bTF，$/+/a/bFF*，$/+/a/b/*Fa，$/+/a/b/*Fb，$/+/a/b/*I1：EE，$EE+T，$/+I2：ET，$/+TTF，$/+/a/bFF*，$/+/a/b/*Fa，$/+/a/b/*Fb，$/+/a/b/*I3：TF，$/+/a/bFF*，$/+/a/b/* I4：Fa，$/+/a/b/*I5：Fb，$/+/a/b/*

22、I6：EE+T，$/+TTF，$/+/a/bTF，$/+/a/bFF*，$/+/a/b/*Fa，$/+/a/b/*Fb，$/+/a/b/*I7：TTF，$/+/a/bFF*，$/+/a/b/*I8 ：FF*，$/+/a/b/*I9：EE+T，$/+TTF，$/+/a/b FF*，$/+/a/b/*Fa，$/+/a/b/*Fb，$/+/a/b/*EEEE+T ETTTFTFFF*FaFb表達(dá)式文法的LR(1)分析表狀態(tài)動(dòng)作轉(zhuǎn)移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5

23、r5r5r5r59r1s4s5r17考慮LR(1)項(xiàng)目集族沒有同心的項(xiàng)目集。所以LALR分析表同LR(1)分析表。表達(dá)式文法的LALR分析表 狀態(tài)動(dòng)作轉(zhuǎn)移+*ab$ETF0s4s51231s6acc2r2s4s5r273r4s8r4r4r44r6r6r6r6r65r7r7r7r7r76s4s5937r3s8r3r3r38r5r5r5r5r59r1s4s5r173.23 證明下面的文法SAa|bAc|Bc|bBaAdBd是LR(1)文法，但不是LALR(1)文法。解：拓廣文法：SSSAaSbAcSBcSbBaAdBdLR(1)項(xiàng)目集族(DFA構(gòu)造過程)： I0：SS，$SAa，$SbAc，$SB

24、c，$SbBa，$Ad，aBd，cI1：SS，$I2：SAa，$I3：SbAc，$SbBa，$Ad，cBd，aI4：SBc，$I5：Ad，aBd，cI6：SAa，$I7：SbAc，$I8 ：SbBa，$I9：Ad，cBd，aI10：SBc，$I11：SbAc，$I12：SbBa，$接受活前綴的DFA轉(zhuǎn)換圖： SSSAaSbAcSBcSbBaAdBd表達(dá)式文法的LR(1)分析表狀態(tài)動(dòng)作轉(zhuǎn)移abcd$SAB0s3s51241acc2s63s9784s105r5r66r17s118s129r6r510r311r212r4考慮LR(1)項(xiàng)目集族有1對(duì)同心的項(xiàng)目集。I5和I9合并成：I59：Ad，a/c

25、Bd，c/a所以LALR(1)分析表如下所示。表達(dá)式文法的LALR(1)分析表 狀態(tài)動(dòng)作轉(zhuǎn)移abcd$SAB0s3s591241acc2s63s59784s1059r5 r6r6 r56r17s118s1210r311r212r4因?yàn)長(zhǎng)R(1)分析表中無分析沖突，而LALR(1)分析表中存在2處歸約-歸約沖突，故所給文法是LR(1)文法，但不是LALR(1)文法。3.29 下面兩個(gè)文法中哪一個(gè)不是LR(1)文法?對(duì)非LR(1)的那個(gè)文法，給出那個(gè)有移進(jìn)-歸約沖突的規(guī)范的LR(1)項(xiàng)目集。SaAcAAbb|bSaAcAbAb|b解：文法SaAcAbAb|b不是LR(1)文法。拓廣文法：SSSaA

26、cAbAbAbLR(1)項(xiàng)目集規(guī)范族：I0：SS，$ SaAc，$I1：SS，$I2：SaAc，$AbAb，cAb，cI3：SaAc，$I4：AbAb，cAb，cAbAb，bAb，bI5：SaAc，$I6：AbAb，cI7：AbAb，bAb，bAbAb，bAb，bI8：AbAb，cI9：AbAb，bI10：AbAb，bSSSaAcAbAbAb 狀態(tài)動(dòng)作轉(zhuǎn)移abc$SA0s211acc2s433s54s7r365r16s87s7 r398s29s1010r2有移進(jìn)-歸約沖突的規(guī)范的LR(1)項(xiàng)目集是I7：AbAb，bAb，bAbAb，bAb，b3.29 對(duì)是LR(1)的那個(gè)文法SaAcAAbb|

27、b解：拓廣文法：SSSaAcAAbbAbSSSaAcAAbbAb狀態(tài)動(dòng)作轉(zhuǎn)移abc$SA0s211acc2s433s6s54r3r35r16s77r2r24.7 用S的綜合屬性val給出下面文法中s產(chǎn)生的二進(jìn)制數(shù)的值。例如：輸入101.101時(shí)，S.val=5.625。SL.L|LLLB|BB0|1(a)僅用綜合屬性決定S.val。(b)用L屬性定義決定S.val。在該定義中，B的唯一綜合屬性是c（還需要繼承屬性），它給出由B產(chǎn)生的位對(duì)最終值的貢獻(xiàn)。例如，101.101的最前一位和最后一位對(duì)值5.625的貢獻(xiàn)分別是4和0.125。解：(a):產(chǎn)生式語(yǔ)義規(guī)則SL1.L2S.val=L1.val+

28、L2.val/pow(2,L2.length)SLS.val=L.valLL1 BL.val=L1.val*2+B.valL.length=L1.length+1LBL.val=B.valLSL.val=S.val L.length=1B0B.val=0B1B.val=1/pow(a,b)為a的b次方。(b):先將文法改寫為：SL.R|LLBL|BRRB|BB0|1然后有：/其中i是B的繼承屬性，val和c是綜合屬性產(chǎn)生式語(yǔ)義規(guī)則SL.RS.val=L.val+R.valSLS.val=L.valLBL1B.i=L1.c*2L.c=L1.c*2L.val=L1.val+B.cLBB.i=1L.

29、c=1L.val=B.cRR1 BB.i=R1.c/2R.c=R1.c/2 R.val=R1.val+B.cRBB.i=0.5R.c=0.5R.val=B.cB0B.c=0B1B.c=14.10 文法如下：S(L)|aLL,S|S(a)寫一個(gè)翻譯方案，它輸出每個(gè)a的嵌套深度。例如，對(duì)于句子(a,(a,a)，輸出的結(jié)果是122。(b)寫一個(gè)翻譯方案，它打印出每個(gè)a在句子中是第幾個(gè)字符。例如，當(dāng)句子是(a,(a,(a,a),(a)時(shí)，打印的結(jié)果是2581014。解：(a):SS.depth=0SSL.depth=S.depth+1 (L)Saprint(S.depth)LL1.depth=L.de

30、pthL1,S.depth=L.depthSLS.depth=L.depthS(b):SS.in=0SSL.in=S.in+1(L)S.out=L.out+1Sa S.out=S.in+1；print(S.out)LL1.in=L.inL1，S.in=L1.out+1SL.out=S.outLS.in=L.inSL.out=S.out4.3為文法S(L)|aLL,S|S(a)寫一個(gè)語(yǔ)法制導(dǎo)定義，它輸出括號(hào)的對(duì)數(shù)。并畫出(a),(a)的注釋分析樹。(b)寫一個(gè)語(yǔ)法制導(dǎo)定義，它輸出括號(hào)嵌套的最大深度。并畫出(a),(a)的注釋分析樹。解：(a):注意：用下標(biāo)加以區(qū)分。構(gòu)造表達(dá)式語(yǔ)法樹的語(yǔ)法制導(dǎo)定義

31、產(chǎn)生式語(yǔ)義規(guī)則SSnprint(S.val)S(L)S.val = L.val + 1SaS.val = 0LL1,SL.val = L1.val + S.valLSL.val = S.valSnS.val=4()L.val=3L.val=2，S.val=1()L.val=0S.val=2()L.val=1S.val=1()L.val=0S.val=0aS.val=0a(b): 注意：用下標(biāo)加以區(qū)分。構(gòu)造表達(dá)式語(yǔ)法樹的語(yǔ)法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(guī)則SSnprint(S.val)S(L)S.val = L.val + 1SaS.val = 0LL1,SL.val=max(L1.val,S.val)L

32、SL.val = S.valSnS.val=3()L.val=2L.val=2，S.val=1()L.val=0S.val=2()L.val=1S.val=1()L.val=0S.val=0aS.val=0a4.7 用S的綜合屬性val給出下面文法中s產(chǎn)生的二進(jìn)制數(shù)的值。例如：輸入101.101時(shí)，S.val=5.625。SL.L|LLLB|BB0|1(a)僅用綜合屬性決定S.val。(b)用L屬性定義決定S.val。在該定義中，B的唯一綜合屬性是c（還需要繼承屬性），它給出由B產(chǎn)生的位對(duì)最終值的貢獻(xiàn)。例如，101.101的最前一位和最后一位對(duì)值5.625的貢獻(xiàn)分別是4和0.125。解：(a)

33、:產(chǎn)生式語(yǔ)義規(guī)則SL1.L2S.val=L1.val+L2.val/pow(2,L2.length)SLS.val=L.valLL1 BL.val=L1.val*2+B.valL.length=L1.length+1LBL.val=B.valLSL.val=S.val L.length=1B0B.val=0B1B.val=1/pow(a,b)為a的b次方。(b):先將文法改寫為：SL.R|LLBL|BRRB|BB0|1然后有：/其中i是B的繼承屬性，val和c是綜合屬性產(chǎn)生式語(yǔ)義規(guī)則SL.RS.val=L.val+R.valSLS.val=L.valLBL1B.i=L1.c*2L.c=L1.c*2L