編譯原理期末考試試卷與答案

1、WORD格式.得分一填空題 每空2分，共20分1.不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲(chǔ)分配策略可能不同，但大局部編譯中采用的方案有兩種：靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案，而后者又分為1和2。2.標(biāo)準(zhǔn)規(guī)約是最3規(guī)約。3.編譯程序的工作過程一般劃分為5 個(gè)階段： 詞法分析、 4 、語義分析與中間代碼生成，代碼優(yōu)化及 5 。另外還有 6和出錯(cuò)處理。4表達(dá)式x+y*z/(a+b)的后綴式為7 。5文法符號(hào)的屬性有綜合屬性和8。6假設(shè)二位數(shù)組按行存放，而且每個(gè)元素占用一個(gè)存儲(chǔ)單元，那么數(shù)組a1.15,1.20某個(gè)元素ai ， j 的地址計(jì)算公式為9。7局部優(yōu)化是局限于一個(gè)10X圍內(nèi)的一種優(yōu)化。得二選擇題

2、1-6 為單項(xiàng)選擇題， 7-8 為多項(xiàng)選擇題，每問2 分，共 20 分分1.一個(gè)上下文無關(guān)文法G包括四個(gè)組成局部：一組終結(jié)符，一組非終結(jié)符，一個(gè)，以及一組。A字符串B產(chǎn)生式C開場(chǎng)符號(hào)D文法2. 程序的根本塊是指。A一個(gè)子程序B 一個(gè)僅有一個(gè)入口和一個(gè)出口的語句C一個(gè)沒有嵌套的程序段D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于分析方法。A自左向右B 自頂向下C 自底向上D 自右向左4在通常的語法分析方法中，特別適用于表達(dá)式的分析。A算符優(yōu)先分析法B LR 分析法C遞歸下降分析法D LL 1分析法5經(jīng)過編譯所得到的目標(biāo)程序是。A四元

3、式序列B 間接三元式序列C二元式序列D 機(jī)器語言程序或匯編語言程序6一個(gè)文法所描述的語言是；描述一個(gè)語言的文法是。A唯一的B 不唯一的C 可能唯一，也可能不唯一7如果在文法 G中存在一個(gè)句子，當(dāng)其滿足以下條件之一時(shí)，那么稱該文法是二義文法。A其最左推導(dǎo)和最右推導(dǎo)一樣B 該句子有兩個(gè)不同的最左推導(dǎo)專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.C該句子有兩個(gè)不同的最右推導(dǎo)D 該句子有兩棵不同的語法樹E該句子對(duì)應(yīng)的語法樹唯一8下面語法制導(dǎo)翻譯中，采用拉鏈回填技術(shù)。A.賦值語句B.布爾表達(dá)式的計(jì)算C.條件語句D.循環(huán)語句得分三解答題 共 60 分1共 15 分文法GE:E ETE|E |iT*|

4、+ 1將文法 G改造成 LL1文法；5 分 2構(gòu)造文法G中每個(gè)非終結(jié)符的FIRST 集合及 FOLLOW集合； 5 分 3構(gòu)造 LL1分析表。5 分2共 12 分給定文法GS ： S S(S)| （ 1 給出句子 ()()()()的標(biāo)準(zhǔn)推導(dǎo)過程； 4 分（ 2 指出每步推導(dǎo)所得句型的句柄； 4 分（ 3 畫出該句子的語法推導(dǎo)樹。 4 分3共 8 分在一個(gè)移入 - 規(guī)約分析過程中采用以下的語法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)，立即執(zhí)行括號(hào)中的動(dòng)作。A aBprint“0； A cprint“1； B Abprint“2； 1當(dāng)分析器的輸入為 aacbb 時(shí)，打印的字符串是什么？3 分 2寫出分

5、析過程。 5 分5共 15 分設(shè)有表格構(gòu)造文法GS ：S a| |(T)T T,S|S(1) 計(jì)算文法 GS 的 FIRSTVT集和 LASTVT集。 5 分(2) 構(gòu)造 GS 的優(yōu)先關(guān)系表，并判斷 GS 是否為算符優(yōu)先文法。 5 分(3) 計(jì)算 GS 的優(yōu)先函數(shù)。 5 分專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.得分二單項(xiàng)選擇題 每題 2 分，共 10 分1.設(shè)有文法GI ： I I1|I0|Ia|Ic|a|b|c以下符號(hào)串中是該文法句子的有。 ab0 a0c01 aaa bc10可選項(xiàng)有：A BCD2. 程序的根本塊是指。A一個(gè)子程序B 一個(gè)僅有一個(gè)入口和一個(gè)出口的語句C一個(gè)沒有

6、嵌套的程序段D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于分析方法。A自左向右B 自頂向下C 自底向上D 自右向左4經(jīng)過編譯所得到的目標(biāo)程序是。A四元式序列B 間接三元式序列C二元式序列D 機(jī)器語言程序或匯編語言程序5運(yùn)行階段的存儲(chǔ)組織與管理的目的是。 提高編譯程序的運(yùn)行速度 節(jié)省編譯程序的存儲(chǔ)空間 提高目標(biāo)程序的運(yùn)行速度 為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備可選項(xiàng)有：A.B.C.D.得分2.10 分文法GS:S aBc|bABAaAb|bB b| 4構(gòu)造其 LL1分析表； 5判斷符號(hào)串baabbb 是否為該文法的句子寫出含有符號(hào)棧、輸入串

7、和規(guī)那么的分析過程。答案：(1) 棧式動(dòng)態(tài)存儲(chǔ)分配(2) 堆式動(dòng)態(tài)存儲(chǔ)分配專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.(3) 左(4) 語法分析(5) 目標(biāo)代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 根本塊一、選擇題每問2 分，共 20 分1.CB2.D 3.B4. A5. D6.A,C7. BCD,選對(duì)一個(gè)得1分且不超過總分值，選錯(cuò)一個(gè)扣一分，扣完為止。8. BCD，選對(duì)一個(gè)得1 分且不超過總分值，選錯(cuò)一個(gè)扣一分，扣完為止。二、解答題1 1文法存在左遞歸，消除左遞歸后的文法為：E (E)E |i E 2 分E TEE

8、 | 2 分T *|+1 分2(5分 ) 沒考慮 #扣 0.5 分，其它錯(cuò)或少寫一個(gè)扣0.5分FIRST(E)=(,iFIRST(E )=*,+, FIRST(T)=*,+FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i 3每錯(cuò)一個(gè)扣 0.5分，全錯(cuò)或不寫不得分，扣完為止，共5 分()i*+#EE(E)E E iE EE E TEEE TEEE E E TT *T +2 1標(biāo)準(zhǔn)推導(dǎo)過程如下。寫錯(cuò)推導(dǎo)符號(hào)扣0.5 分, 錯(cuò)寫或少寫一步推導(dǎo)扣0.5分，扣完為止，最左推導(dǎo)扣2分，共4 分。S S(S)S( )S(S)()S( )()S(S)()(

9、)S( S(S)()() S(S()()() S(S(S)()()()S(S( )()()()S()()()()()()()()2 1中加下劃線的局部是句柄，標(biāo)識(shí)如1。每少寫一個(gè)句柄扣0.5分，扣完為止，共4 分。 3每少寫步扣 0.5分，扣完為止，共 4 分。SS( S ).S( S )專業(yè)資料整理WORD格式.S( S )S(S)S( S )3 1打印的字符串是：12021錯(cuò)一個(gè)扣0.5 分， 共 3 分 2歸約過程中錯(cuò)一步扣0.5 分，扣完為止。 共 5 分5 1少寫一個(gè)扣1 分，全錯(cuò)或不寫不得分，共5 分。FIRSTVT(S)=a, ,(FIRSTVT(T)=, a,(LASTVT(S

10、)= a, ,)LASTVT(T)= a, ,), 三、單項(xiàng)選擇題每題2 分，共 10 分1. B2.D 3.B 4.D 5.C四、解答題共70 分1 1 L(G)=0 m1m|M1共 2 分，寫成扣1 分（ 2 S=0S1=00S11=000111，共 3 分， = 寫成 - 扣 1 分（ 3 共 3 分，錯(cuò)處扣 0.5 分，扣完為止一、判斷題：1.一個(gè)上下文無關(guān)文法的開場(chǎng)符，可以是終結(jié)符或非終結(jié)符。()2.一個(gè)句型的直接短語是唯一的。( )3.已經(jīng)證明文法的二義性是可判定的。4.每個(gè)根本塊可用一個(gè)DAG表示。5.每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。6.2 型文法一定是 3 型文法。

11、7.一個(gè)句型一定句子。()8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)展歸約。( )9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)展優(yōu)化。10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。()11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。( )12.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的存放器的問題。( )專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.13.遞歸下降分析法是一種自下而上分析法。()14.并不是每個(gè)文法都能改寫成LL(1) 文法。()15.每個(gè)根本塊只有一個(gè)入口和一個(gè)出口。()16.一個(gè) LL(1) 文法一定是無二義的。( )17.逆波蘭法表示的表達(dá)試亦稱前綴式。()18.

12、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的存放器的問題。( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。( )20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。()21.3 型文法一定是 2 型文法。( )22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，那么文法是二義性的。( )二、填空題：1.()稱為標(biāo)準(zhǔn)推導(dǎo)。2.編譯過程可分為 ，和五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，那么稱這個(gè)文法是。4.從功能上說，程序語言的語句大體可分為語句和語句兩大類。5.語法分析器的輸入是，其輸出是。6.掃描器的任務(wù)是從中識(shí)別出一個(gè)個(gè)。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，

13、如等等。8.一個(gè)過程相應(yīng)的 DISPLAY表的內(nèi)容為。9.一個(gè)句型的最左直接短語稱為句型的。10.常用的兩種動(dòng)態(tài)存貯分配方法是動(dòng)態(tài)分配和動(dòng)態(tài)分配。11.一個(gè)名字的屬性包括 ()和 ()。12.常用的參數(shù)傳遞方式有，和。13.根據(jù)優(yōu)化所涉及的程序X圍，可將優(yōu)化分成為，和三個(gè)級(jí)別。14.語法分析的方法大致可分為兩類，一類是分析法，另一類是分析法。15.預(yù)測(cè)分析程序是使用一X和一個(gè)進(jìn)展聯(lián)合控制的。16.常用的參數(shù)傳遞方式有，和。17.一X轉(zhuǎn)換圖只包含有限個(gè)狀態(tài), 其中有一個(gè)被認(rèn)為是態(tài) ; 而且實(shí)際上至少要有一個(gè)態(tài)。18.根據(jù)優(yōu)化所涉及的程序X圍，可將優(yōu)化分成為，和三個(gè)級(jí)別。19.語法分析是依據(jù)語言的

14、規(guī)那么進(jìn)展。中間代碼產(chǎn)生是依據(jù)語言的規(guī)那么進(jìn)展的。20.一個(gè)句型的最左直接短語稱為句型的。21.一個(gè)文法 G，假設(shè)它的預(yù)測(cè)分析表 M不含多重定義，那么該文法是文法。22.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用 ()策略， PASCAL采用 ()策略。23.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，那么稱這個(gè)文法是 ()。24.最右推導(dǎo)亦稱為，由此得到的句型稱為句型。25.語法分析的方法大致可分為兩類，一類是分析法，另一類是分析法。26.對(duì)于文法 G，僅含終結(jié)符號(hào)的句型稱為()。27.所謂自上而下分析法是指。28.語法分析器的輸入是，其輸出是。29.局限于根本塊X圍的優(yōu)化稱。30.預(yù)測(cè)分

15、析程序是使用一X和一個(gè)進(jìn)展聯(lián)合控制的。31.2 型文法又稱為文法； 3 型文法又稱為文法。32.每條指令的執(zhí)行代價(jià)定義為。33.算符優(yōu)先分析法每次都是對(duì)進(jìn)展歸約。三、名詞解釋題：1. 局部優(yōu)化2. 二義性文法3.DISPLAY 表4. 詞法分析器5. 最左推導(dǎo)6. 語法7. 文法專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.8. 根本塊9. 語法制導(dǎo)翻譯10. 短語11. 待用信息12. 標(biāo)準(zhǔn)句型13. 掃描器14. 超前搜索15. 句柄16. 語法制導(dǎo)翻譯17. 標(biāo)準(zhǔn)句型18. 素短語19. 語法20. 待用信息21. 語義四、簡(jiǎn)答題：1. 寫一個(gè)文法 G, 使其語言為 不以 0 開頭

16、的偶數(shù)集。2. 文法 G(S) 及相應(yīng)翻譯方案S aAb print“1 S aprint“ 2 A ASprint“3 A cprint“ 4 輸入 acab,輸出是什么？3. 文法 G(S) S bAaA (B | aB Aa)寫出句子 b(aa)b的標(biāo)準(zhǔn)歸約過程。4. 考慮下面的程序：procedurep(x, y, z)；beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Bend.試問，假設(shè)參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出A, B的值是什么 5. 文法 G(S) S dAB A aA| aB Bb|

17、描述的語言是什么？6. 證明文法 G(S)S SaS| 是二義性的。7. 文法 G(S) S BAA BS| d專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.B aA| bS | c的預(yù)測(cè)分析表如下abcd#SS BAS BAS BAAA BSA BSA BSA dBB aABbSBc給出句子adccd的分析過程。8. 寫一個(gè)文法G, 使其語言為L(G)=al bmclanbn| l=0, m=1, n=29. 文法G(S):S a| (T)T T,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a-.(.=.,.請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10. 何謂優(yōu)化？按所涉及的程序X圍可分為哪幾

18、級(jí)優(yōu)化？11. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？12. 一字母表 =a, b ，試寫出上所有以 a 為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。13. 根本的優(yōu)化方法有哪幾種？n n14. 寫一個(gè)文法 G, 使其語言為 L(G)=ab c | n 015. 考慮下面的程序：procedure p(x, y, z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b, b, a);print aend.試問，假設(shè)參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a 的值是什么 16. 寫出表達(dá)式a b*(c-d)/e的逆波蘭式和三元序列。

19、17. 證明文法G(A)A AA | (A)|是二義性的。25. 符號(hào)表的作用是什么？符號(hào)表查找和整理技術(shù)有哪幾種？五、計(jì)算題：1. 設(shè)文法 G(S):S | a | (T)T T,S | S 消除左遞歸； 構(gòu)造相應(yīng)的 FIRST 和 FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.3. 設(shè)文法 G S：S (T) | a TT+S | S(1 計(jì)算 FIRSTVT 和 LASTVT；（ 2構(gòu)造優(yōu)先關(guān)系表。7. 文法 G(S) S a | | (T) TT,S | S(1) 給出句子 (a,(a,a) 的最左推導(dǎo)；(2) 給出句型 (T,S),a) 的短語

20、 , 直接短語，句柄。9. 文法 G(S) S aAcBeA Ab| bB d(1) 給出句子 abbcde 的最左推導(dǎo)及畫出語法樹；(2) 給出句型 aAbcde 的短語、素短語。10. 設(shè)文法 G(S):S (T) | aS | aT T,S | S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的 FIRST 和 FOLLOW集合；構(gòu)造預(yù)測(cè)分析表。參考答案一、是非題：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.二、填空題：1.( 最右推導(dǎo)2.( 詞法分析，語法分析，中間代碼生成 ，代碼優(yōu)化，目

21、標(biāo)代碼生成3.( 二義性的4.( 執(zhí)行性，說明性5.( 單詞符號(hào)，語法單位。6.( 源程序，單詞符號(hào)7.( 類型、種屬、所占單元大小、地址8.( 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址)9.( 句柄10.( 棧式 ) ，堆式11.( 類型 ) ，作用域12.( 傳地址，傳值，傳名13.( 局部優(yōu)化，循環(huán)優(yōu)化，全局優(yōu)化14.( 自上而下，自下而上15.( 分析表，符號(hào)棧16.( 傳地址，傳值，傳名17.( 初，終18.( 局部優(yōu)化，循環(huán)優(yōu)化，全局優(yōu)化19.( 語法，語義20.( 句柄21.(LL(1)文法22.( 靜態(tài)，動(dòng)態(tài)23.( 二義性文法專業(yè)資料整理WORD格式.專業(yè)資料整理WORD

22、格式.24.( 標(biāo)準(zhǔn)推導(dǎo)，標(biāo)準(zhǔn)25.( 自上而下，自下而上26.( 句子 )27.( 從開場(chǎng)符號(hào)出發(fā)，向下推導(dǎo)，推出句子28.( 單詞符號(hào)，語法單位29.( 局部優(yōu)化30.( 分析表，符號(hào)棧31.( 上下文無關(guān)文法 ，正規(guī)32.( 指令訪問主存次數(shù)加133.( 最左素短語三、名詞解釋題：1. 局部優(yōu)化 - 局限于根本塊X圍的優(yōu)化稱。2. 二義性文法 - 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，那么稱這個(gè)文法是二義性文法。3.DISPLAY 表 -過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動(dòng)記錄的起始地址。4. 詞法分析器 - 執(zhí)行詞法分析的程序。5. 最左推導(dǎo) - 任何一步=都

23、是對(duì)中的最右非終結(jié)符替換。6. 語法 - 一組規(guī)那么，用它可形成和產(chǎn)生一組合式的程序。7. 文法 - 描述語言的語法構(gòu)造的形式規(guī)那么。8. 根本塊 - 指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。9. 語法制導(dǎo)翻譯 - 在語法分析過程中， 根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序進(jìn)展翻譯的方法叫做語法制導(dǎo)翻譯。10. 短語 -令 G是一個(gè)文法， S 劃文法的開場(chǎng)符號(hào)，假定 是文法 G的一個(gè)句型， 如果有 S A且A ，那么稱是句型 相對(duì)非終結(jié)符 A 的短語。11. 待用信息 -如果在一個(gè)根本塊中，四元式i 對(duì) A 定值，四元式j(luò) 要引

24、用 A 值，而從i 到 j 之間沒有A 的其它定值，那么稱j 是四元式 i 的變量 A 的待用信息。12. 標(biāo)準(zhǔn)句型 - 由標(biāo)準(zhǔn)推導(dǎo)所得到的句型。13. 掃描器 - 執(zhí)行詞法分析的程序。14. 超前搜索 - 在詞法分析過程中，有時(shí)為了確定詞性，需超前掃描假設(shè)干個(gè)字符。15. 句柄 - 一個(gè)句型的最左直接短語。16. 語法制導(dǎo)翻譯 -在語法分析過程中， 根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義程序進(jìn)展翻譯的方法叫做語法制導(dǎo)翻譯。17. 標(biāo)準(zhǔn)句型 - 由標(biāo)準(zhǔn)推導(dǎo)所得到的句型。18. 素短語 - 素短語是指這樣一個(gè)短語， 至少含有一個(gè)終結(jié)符， 并且，除它自身外不再含任何更小的素短語。19. 語法 - 是組規(guī)那么，

25、用它可形成和產(chǎn)生一個(gè)合式的程序。20. 待用信息 -如果在一個(gè)根本塊中，四元式i 對(duì) A 定值，四元式j(luò) 要引用 A 值，而從i 到 j 之間沒有A 的其它定值，那么稱j 是四元式 i 的變量 A 的待用信息。21. 語義 - 定義程序的意義的一組規(guī)那么。四、簡(jiǎn)答題：1. 所求文法是 GS: S AB |B A0 A AD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2. 輸出是 42313. 句子 b(aa)b 的標(biāo)準(zhǔn)歸約過程：步驟符號(hào)棧輸入串動(dòng)作0#b(aa)b#預(yù)備1#b(aa)b#移進(jìn)2#b(aa)b#移進(jìn)專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.專

26、業(yè)資料整理WORD格式4. 傳地址傳值5.L(G)=da3#b(aa)b#移進(jìn)4#b(Aa)b#歸約5#b(Ma)b#移進(jìn)6#b(Ma)b#移進(jìn)7#b(Bb#歸約8#bAb#歸約9#bAb#移進(jìn)10#S#承受A=6, B=16A=2, B=4nbm |n0, m 0專業(yè)資料整理WORD格式6. 證明：因?yàn)槲姆℅S 存在句子aa 有兩個(gè)不同的最左推導(dǎo)，所以文法GS 是是二義性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7. 句子 adccd 的分析過程：步驟符號(hào)棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#S BA2#AAaadccd#B aA

27、3#AAdccd#4#Addccd#A d5#Accd#6#SBccd#A BS7#Scccd#B c8#Scd#9#ABcd#B c10#Acd#11#Ad#12#dd#A d13#8. 所求文法是 GS: S ABA aAc | D D bD | bB aBb | aabb9.函數(shù)a(),f4244g552310. 優(yōu)化：對(duì)程序進(jìn)展各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級(jí)別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11. 目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.應(yīng)著重考慮的問題：(1) 如何使生成

28、的目標(biāo)代碼較短；(2) 如何充分利用存放器，以減少訪問內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點(diǎn)。12. 正規(guī)式 a ( a | b )*。13. 刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并量，復(fù)寫傳播和刪除無用賦值。14. 文法 GS:S aB | aB bc |bBc15. 傳值 a=2 傳地址 a=1516. 逆波蘭式 : abcd-*e/+三元序列 :op arg1 arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)17. 證明：因?yàn)槲姆℅S 存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法GS 是是二義性的。A=AA=(A)A=()A=()A=AA=A=(

29、A)=()25. 作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。主要技術(shù)：線性表，對(duì)折查找，雜奏技術(shù)。五、計(jì)算題：1.(1) 消除左遞，文法變?yōu)?GS ：S | a | (T)TST | ST ,ST | 此文法無左公共左因子。(2) 構(gòu)造相應(yīng)的FIRST 和 FOLLOW集合：FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , (， FOLLOW(T)=FIRST(T )=, ， FOLLOW(F)=)(3) 構(gòu)造預(yù)測(cè)分析表：a(),#SS aS S (T)TT STT STT STTTT,ST 2. (1)C if E the

30、n(1)S CS(2)C if E then BACK(E.TC, NXQ); C.chain:=E.FCS(1)S.chain:=MERG(C.Chain, S(1). Chain) CS3. (1)FIRSTVT(S)=a, ( FIRSTVT(T)=+,aa, (LASTVT(S)=a,) LASTVT(T)=+, a,)(2)a+()專業(yè)資料整理WORD格式.專業(yè)資料整理WORD格式.a.+(.4. (1)F for i:=E(1) to E(2) doS FS(1)(1)to E (2)(2)F for i:=EdoGEN(:=, E(1) .place, _, entry(i);F.place:=entry(i);L