編譯原理課后習(xí)題答案

1、第一章1解答：程序設(shè)計語言：程序設(shè)計語言是遵守一定規(guī)范的、描述“計算”（Computing）過程的形式語言。一般可以劃分為低級語言和高級語言兩大類。低級語言是面向機(jī)器的語言，它是為特定的計算機(jī)系統(tǒng)設(shè)計的語言，機(jī)器指令、匯編語言是低級語言。高級語言是與具體計算機(jī)無關(guān)的“通用”語言，它更接近于人類的自然語言和數(shù)學(xué)表示，例如FORTRAN、Pascal、C等等我們熟悉的語言是高級語言。語言處理程序：由于目前的計算機(jī)只能理解和執(zhí)行機(jī)器語言，因此必須有一個程序?qū)⒂贸绦蛟O(shè)計語言書寫的程序等價（執(zhí)行效果完全一致）地轉(zhuǎn)換為計算機(jī)能直接執(zhí)行的形式，完成這一工作的程序稱為“語言處理程序”。它一般可分為解釋程序和翻

2、譯程序兩大類。翻譯程序： 翻譯程序(Translator)是一種語言處理程序，它將輸入的用程序設(shè)計語言書寫的程序（稱為源程序）轉(zhuǎn)換為等價的用另一種語言書寫的程序（稱為目標(biāo)程序）。若源語言是匯編語言，目標(biāo)程序是機(jī)器語言，稱這種翻譯程序為匯編程序。若源語言是高級語言，目標(biāo)程序是低級語言，稱這種翻譯程序為編譯程序。解釋程序：解釋程序（Interpreter）是一種語言處理程序，它對源程序逐個語句地進(jìn)行分析，根據(jù)每個語句的含義執(zhí)行語句指定的功能。2解答：編譯程序的總框圖見圖1.2。其中詞法分析器，又稱掃描器，它接受輸入的源程序，對源程序進(jìn)行詞法分析，識別出一個個的單詞符號，其輸出結(jié)果是單詞符

3、號。 語法分析器，對單詞符號串進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或歸約），識別出程序中的各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。 語義分析及中間代碼產(chǎn)生器，按照語義規(guī)則對語法分析器歸約出（或推導(dǎo)出）的語法單位進(jìn)行語義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒有中間代碼形式，而直接生成目標(biāo)代碼。 優(yōu)化器對中間代碼進(jìn)行優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代碼的優(yōu)化，其過程實際上是對中間代碼進(jìn)行等價替換，使程序在執(zhí)行時能更快，并占用更小的空間。 目標(biāo)代碼生成器把中間代碼翻譯成目標(biāo)程序。中間代碼

4、一般是一種機(jī)器無關(guān)的表示形式，只有把它再翻譯成與機(jī)器硬件直接相關(guān)的機(jī)器能識別的語言，即目標(biāo)程序，才能在機(jī)器上運(yùn)行。 表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個編譯過程都在不斷地和表格打交道。出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進(jìn)行處理。如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報告給用戶。編譯程序的各個階段都有可能發(fā)現(xiàn)錯誤，出錯處理程序要對發(fā)現(xiàn)的錯誤進(jìn)行處理、記錄，并反映給用戶 Chapter 21 試寫出VT0，1上下述集合的正則表達(dá)式： 所有以1開始和結(jié)束的符號串

5、。 恰含有3個1的所有符號所組成的集合。 集合01，1。 所有以111結(jié)束的符號串。解答： 1(0|1)*1|1 0*10*10*10* 01|1 (0|1)*1112 試寫出非負(fù)整數(shù)集的正則表達(dá)式。 試寫出以非5數(shù)字為頭的所有非負(fù)整數(shù)集的正則表達(dá)式。解答： 0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 3試將2.8中所示的有限狀態(tài)自動機(jī)M最小化。分析：只能對確定的有限狀態(tài)自動機(jī)進(jìn)行最小化，本題的自動機(jī)已經(jīng)是確定的。最小化采用狀態(tài)分離法，具體做法如下： 進(jìn)行0等價類的劃

6、分：Q劃分為Qf與QQf 若已進(jìn)行了k等價劃分，即Q已被劃分成（Q1，Q2，Qn），再進(jìn)行k1劃分，對Qi（i1n），若q、qÎQi，使得對某一個aÎVT，d（q，a）ÎQj和d（q，a）ÎQl，jl或d（q，a）存在而d（q，a）不存在或反之。則將Qi劃分為二個子集Qi1，Qi2，使qÎQi1，q ÎQi2。 重復(fù)直至無法進(jìn)一步劃分為止。對最后劃分得到的狀態(tài)子集中每一個子集，選擇該子集中任何一個狀態(tài)作為該狀態(tài)子集的代表，然后修改原來的有限狀態(tài)自動機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)d，凡在d作用下轉(zhuǎn)向某狀態(tài)子集中任何一個狀態(tài)的一律改成轉(zhuǎn)向該狀態(tài)子集的代

7、表。若一個狀態(tài)子集中某一狀態(tài)是原來的開始狀態(tài)，則該狀態(tài)子集的代表就是新的有限狀態(tài)自動機(jī)的開始狀態(tài)。同理，若一個狀態(tài)子集中的狀態(tài)均是最終狀態(tài)，則該狀態(tài)子集的代表就是新的有限狀態(tài)自動機(jī)的最終狀態(tài)。 抹去可能存在的無用狀態(tài)與不可及狀態(tài)。解答：此有限狀態(tài)自動機(jī)的狀態(tài)轉(zhuǎn)換表如表3.1所示：表2.1 M的狀態(tài)轉(zhuǎn)換表 abABC BDC CBE DDFAcceptEGEAcceptFGEAcceptGDFAccept由此看出：此有限狀態(tài)自動機(jī)是確定的。最小化：初始劃分由2個子集組成，即：（A,B,C,D,E,F,G）集合D,E,F,G不需要進(jìn)一步劃分，考察子集A,B,

8、C。由于d（B,a）=DÎD,E,F,G，而d（A,a）d（C,a）BÎA,BC，因此Q可進(jìn)一步劃分為：（A,C,B,D,E,F,G）。由于d（A,b）CÎA,C，而d（C，b）EÎD,E,F,G。因此Q可進(jìn)一步劃分為：（A,C,B,D,E,F,G）。這時不能再劃分了，得到的最小化的有限狀態(tài)自動機(jī)如表3.2所示：表2.2 最小化的有限狀態(tài)自動機(jī) abABC CBE BDC DDDAccept4某程序語言的無（正負(fù)）符號常數(shù)可以用下面正則表達(dá)式R來表示：  （D+E|D+.D+E|E|.D+E）(

9、+|-)D|D)D*|D+|D*.D+ 試把它轉(zhuǎn)換成確定性有限狀態(tài)自動機(jī)。 把上述有限狀態(tài)自動機(jī)最小化。 在上述有限狀態(tài)自動機(jī)中添加相應(yīng)動作，取出無（正負(fù)）符號常數(shù)。分析：從正則表達(dá)式構(gòu)造有限狀態(tài)自動機(jī)可以分兩步進(jìn)行。 畫一條從結(jié)點X到結(jié)點Y的有向弧，有向弧上標(biāo)以正則表達(dá)式R。結(jié)點X為標(biāo)以“”的初始狀態(tài)，結(jié)點Y為標(biāo)以“”的最終狀態(tài)。從這一有向圖出發(fā)反復(fù)應(yīng)用圖3.2所示的替代規(guī)則，直至所有有向弧都以VT中的符號或標(biāo)記e為止。  圖2.2 3條替代規(guī)則 消除應(yīng)用所得到的傳遞圖中的弧，可以分為兩步：首先消除環(huán)路，其次消除其他弧。a) 環(huán)路的消除方法：i將環(huán)路的諸項合并為一個頂點。ii修改各

10、個相關(guān)的有向弧。iii若環(huán)路中某一狀態(tài)是最終（或初始）狀態(tài)，則新頂點是最終（或初始）狀態(tài)。b)其它弧的消除有兩種方法：1）子集法：即計算-Closure（T），其表示從狀態(tài)集T中任何一狀態(tài)沿弧可以到達(dá)的狀態(tài)全體。其要點是：從初始狀態(tài)q0的X=-Closure（q0）開始，按如下方法構(gòu)造狀態(tài)集：i令SetX；ii若Set中還有未考察過的狀態(tài)子集Xi，則對于每一輸入符號aÎVT，求T=-Closure（move（Xi,a），Set=SetT（其中move(Xi,a)=q|qÎ(p,a),pÎXi）。重復(fù)執(zhí)行（2），直至不存在這樣的Xi。這樣得到的Set即為消除弧后的確

11、定的有限狀態(tài)機(jī)（DFA）。DFA的初始狀態(tài)就是-Closure（q0），最終狀態(tài)由那些至少含有一個最終狀態(tài)的狀態(tài)子集組成。2）逐步消除法：其要點是找到類似于圖2.3所示，但從B再無弧引出的弧。圖2.3 逐步消除法刪除狀態(tài)A到狀態(tài)B的弧，對每一條從狀態(tài)B到狀態(tài)C標(biāo)記為ai的弧，增加1條從狀態(tài)A到狀態(tài)C標(biāo)記為ai的弧。若B是最終狀態(tài)，則讓A為最終狀態(tài)。重復(fù)上述過程直至消除全部的弧，這樣得到的一般是不確定的有限狀態(tài)自動機(jī)（NFA）。解答： 圖3.4給出了從正則表達(dá)式R構(gòu)造有限狀態(tài)自動機(jī)M的過程。圖2.4替代規(guī)則的應(yīng)用過程應(yīng)用子集法消除??。?Closure（x）=x,2，令A(yù)1x,2，計算：-Clo

12、sure（move（A1，D）-Closure（7,10,2,1）=7,10,2,1,y-Closure（move（A1，·）=-Closure（5,3）=5,3-Closure（move（A1，E）-Closure（4）=4令A(yù)27,10,2,1,y，A35,3，A44，計算：-Closure（move（A2，D）7,10,2,1,y-Closure（move（A2，·）8,3-Closure（move（A2，E）4-Closure（move（A3，D）5,6,3,y-Closure（move（A4，D）12,y-Closure（move（A4，）11-Closure（m

13、ove（A4，）11令A(yù)58,3，A65,6,3,y，A7=12,y，A811，計算：-Closure（move（A5，D）8,9,3,y-Closure（move（A6，D）5,6,3,y-Closure（move（A6，E）4-Closure（move（A7，D）12,y-Closure（move（A8，D）12,y令A(yù)98,9,3,y，計算：-Closure（move（A9，D）8,9,3,y-Closure（move（A9，E）4得到的DFA M的初始狀態(tài)是A1，最終狀態(tài)集由A2，A6，A7，A9組成。圖2.5是M的狀態(tài)轉(zhuǎn)換圖，M的狀態(tài)轉(zhuǎn)換表如表2.3所示。表2.3 M的狀態(tài)轉(zhuǎn)換表&#

14、160;DE·+-A1A2A4A3   A2A2A4A5  AcceptA3A6     A4A7  A8A8 A5A9     A6A6A4   AcceptA7A7    AcceptA8A7     A9A9A4   Accept圖2.5 M的狀態(tài)轉(zhuǎn)換圖

15、采用狀態(tài)分離法：  初始時分成2個子集，即：(A1,A3,A4,A5,A8,A2,A6,A7,A9)  考察子集 A2,A6,A7,A9，它進(jìn)一步可分成：（A6,A9,A2,A7）  考察子集 A1,A3,A4,A5,A8，它進(jìn)一步分成：（A4,A1,A8,A3,A5）  不能再進(jìn)一步劃分了，得到的最小化的有限狀態(tài)自動機(jī)如圖2.6所示：圖2.6 最小化的有限狀態(tài)自動機(jī)由于數(shù)的表示和具體的機(jī)器有著內(nèi)在聯(lián)系，這里僅將此無（正負(fù)）符號常數(shù)的十進(jìn)制數(shù)部分和指數(shù)部分分別存入2個工作單元。設(shè)立下述工作單元：此常數(shù)的十進(jìn)制數(shù)部分

16、      number此常數(shù)的指數(shù)部分          exp小數(shù)點位數(shù)                n此常數(shù)指數(shù)部分正負(fù)號      expsign這4個工作單元進(jìn)入有限狀態(tài)自動機(jī)的模擬程序時被初始化為0。函數(shù)過程getchar，其功能是讀入下一個字符

17、到工作單元char中。函數(shù)過程value，其功能是求出存放在工作單元char中數(shù)字字符的值。經(jīng)過加工后的狀態(tài)矩陣如表2.4所示：表2.4 加工后的狀態(tài)矩陣D·E+-A1#1,A2#2,A3#2,A4   A2#3,A2#2,A3#2,A4  #10,AcceptA3#4,A6     A4#5,A7  #6,A8#7,A8 A6#4,A6 #2,A4  #11,AcceptA7#8,A7   &#

18、160;#12,AcceptA8#9,A7     矩陣中元素A1，A2，.，A7表示應(yīng)該轉(zhuǎn)換的下一個狀態(tài)。1，2，.，12表示應(yīng)該執(zhí)行的語義子程序。各語義子程序的代碼歸結(jié)如下：1：number:=value（char）;getchar;2：getchar;3：number:=number*10+value（char）;getchar;4：n:=n+1; number:=number*10+value（char）;getchar;5：expsign:=1;exp:=value（char）;getchar;6：expsign:=1;getchar

19、;7：expsign=-1;getchar;8：exp:=exp*10+value（char）;getchar;9：exp:=value（char）;getchar;10：按硬件要求構(gòu)造無（正負(fù)）符號數(shù)；11：exp:=-n; 按硬件要求構(gòu)造無（正負(fù)）符號數(shù)；12：if expsign=-1 then exp:=-exp;exp=exp-n; 按硬件要求構(gòu)造無（正負(fù)）符號數(shù)；5.設(shè)要識別的單詞有限集是STEP,SWITCH,STRING，相應(yīng)正則表達(dá)式是STEP|SWITCH|STRING，試把它轉(zhuǎn)換成確定性有限狀態(tài)自動機(jī)。解答：6設(shè)VTa,b，試構(gòu)造下述正則表達(dá)式的確定性有限狀態(tài)自動機(jī)： a

20、(a|b)*baa (a|b)*bbb*  解答： 由此正則表達(dá)式構(gòu)造的有限狀態(tài)自動機(jī)M1的狀態(tài)轉(zhuǎn)換圖如圖2.7所示：圖2.7 有限狀態(tài)自動機(jī)M1的轉(zhuǎn)換圖確定化（表3.5）：表3.5 M1的確定化Qdadb12  222,3 2,32,42,3 2,42,52,3 2,522,3A對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖3.8所示：圖2.8 DFA M1的狀態(tài)轉(zhuǎn)換圖 由正則表達(dá)式構(gòu)造的有限狀態(tài)自動機(jī)M2的狀態(tài)轉(zhuǎn)換圖如圖2.9所示：圖2.9 M2的狀態(tài)圖確定化（表2.6）：表2.6 M2的確定化Qdadb111,2 1,211,2,3&

21、#160;1,2,311,2,3 對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.10所示：圖2.10 DFA M2的狀態(tài)轉(zhuǎn)換圖9對于下列的狀態(tài)轉(zhuǎn)換矩陣： abSAS AAB BBBZ abSAS ABAZBBB  分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖。 用自然語言分別描述它們所識別的輸入串的特征。解答： 表1所對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.11所示：圖2.11 表3.6對應(yīng)的狀態(tài)轉(zhuǎn)換圖表2所對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.12所示：圖2.12 表3.7對應(yīng)的狀態(tài)轉(zhuǎn)換圖 表1所識別的輸入串是：以b*aa*b開頭的后接任意多個a或b的a,b上的字符串。  

22、 表2所識別的輸入串是：僅含有一個a的a,b上的字符串。10. 將習(xí)題圖2.1所示的非確定的有限狀態(tài)自動機(jī)確定化和最小化。習(xí)題圖2.1 非確定的有限狀態(tài)自動機(jī)M解答：確定化（表2.8）：表2.8 M的確定化abSA  AB,CA B,CA Z令BB,C對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖2.14所示：圖2.14 DFA M的狀態(tài)轉(zhuǎn)換圖確定化的M已是最小化的。11.消除傳遞圖T（習(xí)題圖2.2）中的 e 弧。習(xí)題圖2.2傳遞圖T解答：i）先消除e環(huán)路，合并狀態(tài)2和3，得到的傳遞圖T如圖3.16所示：圖2.16 消除?環(huán)路的傳遞圖Tii）采用逐步消除法去除其他e弧，

23、最終得到的傳遞圖T如圖2.17所示：圖2.17 消除所有e弧的傳遞圖Chapter 32設(shè)有文法G1<S>：<S><N><N><D>|<N><D><D0|1|2|9試寫出028和4321的最左推導(dǎo)和最右推導(dǎo)過程。分析：在每一步的推導(dǎo)中，都是對最左的那個非終結(jié)符用相應(yīng)的產(chǎn)生式的右部來替換，這樣的推導(dǎo)稱為最左推導(dǎo)。類似地，如果每一步的推導(dǎo)中都是對最右的那個非終結(jié)符用相應(yīng)的產(chǎn)生式的右部來替換，這樣的推導(dǎo)稱為最右推導(dǎo)，最右推導(dǎo)又稱規(guī)范推導(dǎo)。解答：028的最左推導(dǎo)：<S>Þ<N>&

24、#222;<N><D>Þ<N><D><D>Þ<D><D><D>Þ0<D><D>Þ02<D>Þ028028的最右推導(dǎo)：<S>Þ<N>Þ<N><D>Þ<N>8Þ<N><D>8Þ<N>28Þ<D>28Þ0284321的最左推導(dǎo)：<S>

25、Þ<N>Þ<N><D>Þ<N><D><D>Þ<N><D><D><D>Þ<D><D><D><D>Þ4<D><D><D>Þ43<D><D>Þ432<D>Þ43214321的最右推導(dǎo)：<S>Þ<N>Þ<N><D&g

26、t;Þ<N>1Þ<N><D>1Þ<N>21Þ<N><D>21Þ<N>321Þ<D>321Þ43213證明文法G<S>是二義性文法：<S>if<E>then<S>else<S>|if<E>then<S>|s<E>0|1分析：只要找出該文法的一個二義性句子即可證明。解答：句子if 0 then if 1 then s else s 對應(yīng)如下

27、兩棵不同的推導(dǎo)樹：圖3.1 句子if 0 then if 1 then s else s的推導(dǎo)樹（1）圖3.1 句子if 0 then if 1 then s else s的推導(dǎo)樹（2）4設(shè)有文法G<E>：<E><E>-<T>|<T><T><T>/<F>|<F><F>i|(<E>) 試寫出i/(i-i-i)的推導(dǎo)樹。 試寫出（<F>-i）/<F>的短語、簡單短語和句柄。分析：只要給出句型（句子）對應(yīng)的推導(dǎo)樹就容易求出短語、簡單短語和句柄。解

28、答： i/(i-i-i)的推導(dǎo)樹如下：圖3.3 句子i/(i-i-i)的推導(dǎo)樹（<F>-i）/<F>的推導(dǎo)樹如下：圖3.4 句子（<F>-i）/<F>的推導(dǎo)樹短語：<F>，i，<F>-i，（<F>-i），（<F>-i）/<F>簡單短語：<F>，i句柄：<F>5對布爾矩陣求B+。解答：利用Warshall算法求解的結(jié)果如下：7對表結(jié)構(gòu)語言G<S>：<S>a|Ù|(<T>)<T><T>,<S&

29、gt;|<S> 試給出(a,(a,a)的最左和最右推導(dǎo)。 指出(a,a),Ù,(a),a)的最右推導(dǎo)，以及規(guī)約的每一步的句柄。 給出(a,a),Ù,(a),a)的推導(dǎo)樹自下而上的構(gòu)造過程。分析：本題是要讓讀者明確，自下而上構(gòu)造推導(dǎo)樹的過程是最右推導(dǎo)(規(guī)范推導(dǎo))的逆過程，這一過程正是自底向上句法分析的過程，其要點是找句柄、歸約。解答： 句子(a,(a,a)的最左推導(dǎo)為： <S>Þ(<T>)Þ(<T>,<S>)Þ(<S>,<S>)Þ(a,<

30、S>)Þ(a,(<T>)Þ(a,(<T>,<S>)Þ(a,(<S>,<S>)Þ(a,(a ,<S>)Þ(a,(a,a)最右推導(dǎo)為：<S>Þ(<T>)Þ(<T>,<S>)Þ(<T>,(<T>)Þ(<T>,(<T>,<S>)Þ(<T>,(<T>,a)Þ(<T>,(<

31、S>,a)Þ(<T>, (a,a)Þ(<S>,(a,a)Þ(a,(a,a) 句子(a,a),Ù,(a),a)的最右推導(dǎo)及歸約的每一步句柄如表3.1所示：表3.1 句子(a,a),Ù,(a),a)的最右推導(dǎo)過程最右推導(dǎo)每一步歸約時的句柄<S>(<T>)(<T>) (<T>,<S>)<T>,<S> (<T>,a)a (<S>,a) <S> (<T>)

32、,a)(<T>) (<T>,<S>),a)<T>,<S> (<T>,(<T>),a)(<T>) (<T>,(<S>),a)<S> (<T>,(a),a)a (<T>,<S>,(a),a)<T>,<S> (<T>,Ù,(a),a)Ù (<S>,Ù,(a),a)<S>

33、0;(<T>),Ù,(a),a)(<T>) (<T>,<S>),Ù,(a),a)<T>,<S> (<T>,a),Ù,(a),a)a (<S>,a),Ù,(a),a)<S> (a,a),Ù,(a),a)a 句子(a,a),Ù,(a),a)的推導(dǎo)樹如圖3.5所示:圖3.5 句子(a,a),Ù,(a),a)的推導(dǎo)樹構(gòu)造過程如圖3.6所示:圖3.6 句子(a,a),Ù,(a),

34、a)的推導(dǎo)樹自下而上的構(gòu)造過程Chapter 4（略）Chapter 51. 考察算術(shù)表達(dá)式翻譯文法T1：T1=(+,*,(,),C,<E>,<T>,<P>,C,ADD,MUL,R,<E>)其中R由下面規(guī)則組成：<E><E>+<T>,<E><T>ADD<E><T>,<T><T><T>*<P>,<T><P>MUL<T><P>,<P><P>(<

35、E>),<E><P>C,C其相應(yīng)輸入文法是LR(1)。試對該輸入文法的下推自動機(jī)控制表作適當(dāng)改動，構(gòu)造翻譯下推自動機(jī)的控制表，使該翻譯下推自動機(jī)把任何一個由C,+,*組成的中綴表達(dá)式翻譯成后綴表達(dá)式。分析：設(shè)翻譯文法中的翻譯規(guī)則形如：<A>x，y把自底向上的下推自動機(jī)改造成相應(yīng)的下推翻譯自動機(jī)的方法很簡單：只需規(guī)定，當(dāng)下推自動機(jī)應(yīng)用產(chǎn)生式i進(jìn)行規(guī)約的同時，輸出y中的輸出符號。解答：輸入文法的LR(1)狀態(tài)集如表5.1。表5.1 輸入文法的LR(1)狀態(tài)集狀態(tài)T項目集文法符號BGOTO（T，B）0*<E>·<E>, &#

36、217;<E>1<E>·<E>+<T>, /+<E>1<E>·<T>, /+<T>2<T>·<T>*<P>, /+/*<T>2<T>·<P>, /+/*<P>3<P>·(<E>), /+/*(4<P>·C, /+/*C51*<E><E>·Accept*<E><E>&

37、#183;+<T>, /+62*<E><T>·, /+/+#2*<T><T>·*<P>, /+/*73*<T><P>·, /+/*/+/*#44*<P>(·<E>), /+/*<E>8<E>·<E>+<T>, )/+<E>8<E>·<T>, )/+<T>9<T>·<T>*<P>

38、, )/+/*<T>9<T>·<P>, )/+/*<P>10<P>·(<E>), )/+/*(11<P>·C, )/+/*C125*<P>C·, /+/*/+/*#66*<E><E>+·<T>, /+<T>13<T>·<T>*<P>, /+/*<T>13<T>·<P>, /+/*<P>3<P&g

39、t;·(<E>), /+/*(4<P>·C, /+/*C57*<T><T>*·<P>, /+/*<P>14<P>·(<E>), /+/*(4<P>·C, /+/*C58*<P>(<E>·), /+/*)15*<E><E>·+<T>, )/+169*<E><T>·, )/+)/+#2*<T><T>

40、3;*<P>, )/+/*1710*<T><P>·, )/+/*)/+/*#411*<P>(·<E>), )/+/*<E>18<E>·<E>+<T>, )/+<E>18<E>·<T>, )/+<T>9<T>·<T>*<P>, )/+/*<T>9<T>·<P>, )/+/*<P>10<P>

41、·(<E>), )/+/*(11<P>·C, )/+/*C1212*<P>C·, )/+/*)/+/*#613*<E><E>+<T>·, /+/+#1*<T><T>·*<P>, /+/*714*<T><T>*<P>·, /+/*/+/*#315*<P>(<E>)·, /+/*/+/*#516*<E><E>+·<T>

42、, )/+<T>19<T>·<T>*<P>, )/+/*<T>19<T>·<P>, )/+/*<P>10<P>·(<E>), )/+/*(11<P>·C, )/+/*C1217*<T><T>*·<P>, )/+/*<P>20<P>·(<E>), )/+/*(11<P>·C, )/+/*C1218*<P>

43、;(<E>·), )/+/*)21*<E><E>·+<T>, )/+1619*<E><E>+<T>·, )/+)/+#1*<T><T>·*<P>, )/+/*1720*<T><T>*<P>·, )/+/*)/+/*#321*<P>(<E>)·, )/+/*)/+/*#5翻譯下推自動機(jī)的控制表如表5.2所示：表5.2 翻譯下推自動機(jī)的控制表狀態(tài)T動作表（Act

44、ion）轉(zhuǎn)向表（Goto）+*()C<E><T><P>0  S4 S5 1231S6    Acc   2R#2S7   R#2   3R#4R#4   R#4   4  S11 S12 89105R#6, GEN(C)R#6, GEN(C)   R#6,GEN(

45、C)   6  S4 S5  1337  S4 S5   148S16  S15     9R#2S17 R#2     10R#4R#4 R#4     11  S11 S12 1891012R#6, GEN(C)R#6, GE

46、N(C) R#6, GEN(C)     13R#1,GEN(ADD)S7   R#1,GEN(ADD)   14R#3,GEN(MUL)R#3,GEN(MUL)   R#3,GEN(MUL)   15R#5R#5   R#5   16  S11 S12  191017  S11 

47、;S12   2018S16  S21     19R#1,GEN(ADD)S17 R#1,GEN(ADD)     20R#3,GEN(MUL)R#3,GEN(MUL) R#3,GEN(MUL)     21R#5R#5 R#5     2. 考察下述文法G<S>：<S>i:=<E>

48、;<E><E1>+<E2><E><E1>*<E2><E>(<E1>)<E>i試寫出各產(chǎn)生式的語義子程序。解答：讓非終結(jié)符<E>帶有屬性<E>.type指出數(shù)據(jù)類型，屬性<E>.val存放運(yùn)算結(jié)果。 <S>i:=<E>if i.type=<E>.type then   GEN(:=,<E>.val,i.val); else if i.type=real AND <E>

49、;.type=int then   begin       T:=NEWTEMP;       GEN(float,<E>.val,T);       GEN(:=,T,i.val);   end. else if i.type=int AND <E>.type=real then   begin  &#

50、160;    T:=NEWTEMP;       GEN(int,<E>.val,T);       GEN(:=,T,i.val);   end.else error.       <E>E1>+<E2><E>.val:=NEWTEMP; if <E1>.type=int AND <

51、E2>.type=int then    begin        <E>.type:=int;        GEN(int+,<E1>.val, <E2>.val,<E>.val);    end. else if <E1>.type=real AND <E2>.type=real then &#

52、160;  begin        <E>.type:=real;        GEN(real+,<E1>.val, <E2>.val,<E>.val);    end. else if <E1>.type=int AND <E2>.type=real then    begin  

53、;      <E>.type:=real;        T:=NEWTEMP;        GEN(float, <E1>.val,T);        GEN(real+,T, <E2>.val,<E>.val);    end. else i

54、f <E1>.type=real AND <E2>.type=int then    begin        <E>.type:=real;        T:=NEWTEMP;        GEN(float, <E2>.val,T);      

55、;  GEN(real+, <E1>.val,T,<E>.val);    end. else error.<E><E1>*<E2><E>.val:=NEWTEMP; if <E1>.type=int AND <E2>.type=int then    begin        <E>.type:=int;  

56、      GEN(int*,<E1>.val, <E2>.val,<E>.val);    end. else if <E1>.type=real AND <E2>.type=real then    begin        <E>.type:=real;      

57、60; GEN(real*,<E1>.val, <E2>.val,<E>.val);    end. else if <E1>.type=int AND <E2>.type=real then    begin        <E>.type:=real;        T:=NEWTEMP;  

58、      GEN(float, <E1>.val,T);        GEN(real*,T, <E2>.val,<E>.val);    end. else if <E1>.type=real AND <E2>.type=int then    begin        &

59、lt;E>.type:=real;        T:=NEWTEMP;        GEN(float, <E2>.val,T);        GEN(real*, <E1>.val,T,<E>.val);    end. else error.<E>(<E1>)<E&g

60、t;.val:= <E1>.val; <E>.type:= <E1>.type;<E>i<E>.val:= i.val; <E>.type:=i.type;Chapter 6（略）Chapter 71.考察下面程序段：procedure p(x,y,z)  begin    y:=y+1;    z:=z+x;  end;begin  a:=2; 

61、0;b:=3;  p(a+b,a,a);  write(a);end;若參數(shù)通信分別是： 按名 按值方式，上述程序執(zhí)行后，輸出a的值分別是多少？解答：按名調(diào)用的特點是：在被調(diào)用過程執(zhí)行時，用實參替換形參，然后執(zhí)行替換后的程序，因此本程序相當(dāng)于執(zhí)行如下程序段：  a:=2；  b:=3；  a:=a+1；  a:=a+a+b；輸出a的值是9。按值調(diào)用的特點是：傳送的是實在參數(shù)的當(dāng)時值，該值成為形參的初值，是一種單向的行為，它并不改變實參的值。所以a的值不變，仍是2。  

62、; 2. 考察下面C程序：main()  int ;P1()       P2()；        P2()       P3()；        P3()   P1()；試說明，該程序執(zhí)行時，運(yùn)行棧中調(diào)用記錄的變化情況。解答：程序流進(jìn)入過程P1時，?？臻g中各調(diào)用記錄的布局如圖7

63、.2所示。 圖7.2 程序流進(jìn)入過程P1時各調(diào)用記錄的布局程序流進(jìn)入過程P2時，棧空間中各調(diào)用記錄的布局如圖7.3所示。圖7.3 程序流進(jìn)入過程P2時各調(diào)用記錄的布局程序流進(jìn)入過程P3時，?？臻g中各調(diào)用記錄的布局如圖7.4所示。圖7.4 程序流進(jìn)入過程P3時各調(diào)用記錄的布局3.下標(biāo)變量地址計算可以采用另一種方法：直接生成計算下標(biāo)變量地址的中間代碼?？疾煜率龊拖聵?biāo)變量有關(guān)的產(chǎn)生式： <SUB_V>i<E> <SUB_V><SUB_V>1,<E> <V><SUB_V>試寫出相應(yīng)求下標(biāo)變量地址的語義子程序。

64、解答：由于在處理數(shù)組定義時，已經(jīng)將數(shù)組的維數(shù)n，每一維的上下界Ui、Li，長度di以及數(shù)組元素存貯首地址stp，address(a0,0)均存放在數(shù)組的信息向量表中。為得到這些數(shù)據(jù)，用屬性id.dim表示數(shù)組的維數(shù)，函數(shù)limit(id,j)返回dj，函數(shù)getaddr(id)返回假頭地址address(a0,0)，過程Mark_indirect(T)表示在T中添加間址標(biāo)記。各產(chǎn)生式的語義子程序為： <SUB_V>i<E><SUB_V>.dim:=1；<SUB_V>.array:=i.array；/* i.array表示數(shù)組名*/<SUB_

65、V>.val:=<E>.val；<SUB_V><SUB_V>1,<E><SUB_V>.dim:= <SUB_V>1.dim+1；D:=Newtemp；GEN(*,<SUB_V>1.val,limit(<SUB_V>.array,<SUB_V >.dim),D)；GEN(+,D,<E>.val,D)；<E_list>.val:=D；<SUB_V>.array:= <SUB_V>1.array;<V><SUB_V>

66、Checkdim(<SUB_V>.dim,<SUB_V>.array.dim)； /*檢查維數(shù)的正確性*/L:=Newtemp；GEN(+,getaddr(<SUB_V>.array),<SUB_V>.val,L)；Mark_indirect(L)；<V>.val:=L；4.過程語句： <S>call i(<E_list>) <E_list><E_list>1,<E> <E_list><E>的中間代碼采用下面形式：（call,i.VAL,<E1&

67、gt;.VAL,<En>.VAL）試寫出生成上述形式的中間代碼的語義子程序。解答：讓<E_list>帶有屬性：<E_list>.que（隊頭）和<E_list>.tail（隊尾）。1的語義子程序為：fetch(<E_list>.que, <E_list>.tail);Gen(call,i.VAL,<E1>.VAL,<En>.VAL);2的語義子程序為：<E_list>.que= <E_list>1.que;<E_list>.tail= <E_list>

68、1.tail;Append(<E_list>.tail,<E>.val);3的語義子程序為：MakeQueue(<E_list>.que, <E_list>.tail);Append(<E_list>.tail,<E>.val);  5. 考察下面Pascal程序：Program P(input,output);  var a,b:integer；      c1:array110 of real；  Proced

69、ure f1(x,y:integer)；    var d,e:integer；        c2:array120 of real；    Procedure f2；      var u,v:real；      begin       

70、60;      end；    begin            f2；   end；  Procedure f3；    var h1,h2:integer；    begin      

71、;      f1(h1,h2)；    end；begin   f3；end. 給出程序流進(jìn)入過程f1和f2時區(qū)頭地址表的內(nèi)容。 給出程序流進(jìn)入f2時運(yùn)行棧中的主要內(nèi)容。解答：本題中過程的嵌套和調(diào)用關(guān)系可示意性地由圖7.5表示。 圖7.5 過程的嵌套和調(diào)用關(guān)系 當(dāng)程序流進(jìn)入f1時，區(qū)頭地址表的內(nèi)容有以下兩項：過程f1的調(diào)用記錄首址P過程的調(diào)用記錄首址當(dāng)程序流進(jìn)入f2時，區(qū)頭地址表的內(nèi)容有以下三項：過程f2的調(diào)用記錄首址過程f1的調(diào)用記錄首址P過程的調(diào)用記錄首址(2

72、)程序流進(jìn)入f2時，運(yùn)行棧的主要內(nèi)容如圖7.6所示。圖7.6 程序流進(jìn)入f2時運(yùn)行棧的情形Chapter 81.考察下述文法G<S>：<S>i:=<E><E><E1>+<E2><E><E1>*<E2><E>(<E1>)<E>i試寫出各產(chǎn)生式的語義子程序。解答：讓非終結(jié)符<E>帶有屬性<E>.type指出數(shù)據(jù)類型，屬性<E>.val存放運(yùn)算結(jié)果。 <S>i:=<E>if i.type=<E

73、>.type then   GEN(:=,<E>.val,i.val); else if i.type=real AND <E>.type=int then   begin       T:=NEWTEMP;       GEN(float,<E>.val,T);       GEN(:=,T,i.val); 

74、60; end. else if i.type=int AND <E>.type=real then   begin       T:=NEWTEMP;       GEN(int,<E>.val,T);       GEN(:=,T,i.val);   end.else error.     

75、  <E>E1>+<E2><E>.val:=NEWTEMP; if <E1>.type=int AND <E2>.type=int then    begin        <E>.type:=int;        GEN(int+,<E1>.val, <E2>.val,<E>.val);&#

76、160;   end. else if <E1>.type=real AND <E2>.type=real then    begin        <E>.type:=real;        GEN(real+,<E1>.val, <E2>.val,<E>.val);    end. 

77、;else if <E1>.type=int AND <E2>.type=real then    begin        <E>.type:=real;        T:=NEWTEMP;        GEN(float, <E1>.val,T);        GEN(real+,T, <E2>.val,<E>.val);    end. else if <E1>.type=real AND <E2>.type=int then