編譯原理期末考試試卷試題及答案

1、得分一 填空題（每空2分，共20分）1. 不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲(chǔ)分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案，而后者又分為（1） 和 （2） 。2. 規(guī)范規(guī)約是最（3）規(guī)約。3. 編譯程序的工作過(guò)程一般劃分為5個(gè)階段：詞法分析、（4） 、語(yǔ)義分析與中間代碼生成，代碼優(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局部?jī)?yōu)化是局限于一個(gè)（10）范

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

3、析法C 遞歸下降分析法 D LL（1）分析法5經(jīng)過(guò)編譯所得到的目標(biāo)程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序6 一個(gè)文法所描述的語(yǔ)言是（ ）；描述一個(gè)語(yǔ)言的文法是（ ）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一個(gè)句子，當(dāng)其滿(mǎn)足下列條件（ ）之一時(shí)，則稱(chēng)該文法是二義文法。A 其最左推導(dǎo)和最右推導(dǎo)相同 B 該句子有兩個(gè)不同的最左推導(dǎo)C 該句子有兩個(gè)不同的最右推導(dǎo) D 該句子有兩棵不同的語(yǔ)法樹(shù)E 該句子對(duì)應(yīng)的語(yǔ)法樹(shù)唯一8 下面（ ）語(yǔ)法制導(dǎo)翻譯中，采用拉鏈回填技術(shù)。A. 賦值語(yǔ)句 B. 布爾表達(dá)式的計(jì)算 C. 條

4、件語(yǔ)句 D. 循環(huán)語(yǔ)句得分三 解答題（共60分）1 （共15分）已知文法GE: EETE|（E）|i T*|+（1） 將文法G改造成LL（1）文法；（5分）（2） 構(gòu)造文法G中每個(gè)非終結(jié)符的FIRST集合及FOLLOW集合；（5分）（3） 構(gòu)造LL（1）分析表。（5分）2 （共12分）給定文法GS：SS(S)|（1） 給出句子()()()()的規(guī)范推導(dǎo)過(guò)程；（4分）（2） 指出每步推導(dǎo)所得句型的句柄；（4分）（3） 畫(huà)出該句子的語(yǔ)法推導(dǎo)樹(shù)。（4分）3 （共8分）在一個(gè)移入-規(guī)約分析過(guò)程中采用以下的語(yǔ)法制導(dǎo)翻譯模式，在按一個(gè)產(chǎn)生式規(guī)約時(shí)，立即執(zhí)行括號(hào)中的動(dòng)作。 AaB print “0”； Ac

5、 print “1”； BAb print “2”；（1） 當(dāng)分析器的輸入為aacbb時(shí)，打印的字符串是什么（3分）（2） 寫(xiě)出分析過(guò)程。（5分）5 （共15分）設(shè)有表格構(gòu)造文法GS： Sa|(T) TT,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分）得分二 單項(xiàng)選擇題（每題2分，共10分）1. 設(shè)有文法GI： II1|I0|Ia|Ic|a|b|c下列符號(hào)串中是該文法句子的有（ ）。 ab0 a0c01 aaa bc10可選項(xiàng)有：A B C D2.程序的基本塊是指（

6、）。A 一個(gè)子程序 B 一個(gè)僅有一個(gè)入口和一個(gè)出口的語(yǔ)句C 一個(gè)沒(méi)有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口3. 高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4經(jīng)過(guò)編譯所得到的目標(biāo)程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序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: SaB

7、c|bABAaAb|bBb|（4） 構(gòu)造其LL（1）分析表；（5） 判斷符號(hào)串baabbb是否為該文法的句子（寫(xiě)出含有符號(hào)棧、輸入串和規(guī)則的分析過(guò)程）。答案：(1) 棧式動(dòng)態(tài)存儲(chǔ)分配(2) 堆式動(dòng)態(tài)存儲(chǔ)分配(3) 左(4) 語(yǔ)法分析(5) 目標(biāo)代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 基本塊一、 選擇題（每問(wèn)2分，共20分）1.C B 2.D 3.B 4.A 5.D 6.A,C7.BCD,選對(duì)一個(gè)得1分且不超過(guò)滿(mǎn)分，選錯(cuò)一個(gè)扣一分，扣完為止。8.BCD，選對(duì)一個(gè)得1分且不超過(guò)滿(mǎn)分，選錯(cuò)一個(gè)扣一分，扣完為止。二、 解答題1（1

8、）文法存在左遞歸，消除左遞歸后的文法為：E(E)E|i E（2分）ETEE| （2分）T*|+ （1分）（2）(5分)沒(méi)考慮#扣0.5分，其它錯(cuò)或少寫(xiě)一個(gè)扣0.5分FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每錯(cuò)一個(gè)扣0.5分，全錯(cuò)或不寫(xiě)不得分，扣完為止，共5分()i*+#EE(E)EEiEEE ETEEE ETEEE E TT*T+2（1）規(guī)范推導(dǎo)過(guò)程如下。寫(xiě)錯(cuò)推導(dǎo)符號(hào)扣0.5分,錯(cuò)寫(xiě)或少寫(xiě)一步推導(dǎo)扣0.5分，扣完為止，最左推導(dǎo)扣2分，共4分。（2）

9、（1）中加下劃線的部分是句柄，標(biāo)識(shí)如（1）。每少寫(xiě)一個(gè)句柄扣0.5分，扣完為止，共4分。（3）每少寫(xiě)步扣0.5分，扣完為止，共4分。SS ( S )S ( S ) ) )S ( S ) )S ( S ) ) S ( S ) )3（1）打印的字符串是：12020（錯(cuò)一個(gè)扣0.5分，共3分）（2）歸約過(guò)程中錯(cuò)一步扣0.5分，扣完為止。（共5分）5（1）少寫(xiě)一個(gè)扣1分，全錯(cuò)或不寫(xiě)不得分，共5分。FIRSTVT(S)=a,(FIRSTVT(T)=, a,(LASTVT(S)= a,)LASTVT(T)= a,), ,三、 單項(xiàng)選擇題（每題2分，共10分）1.B 2.D 3.B 4.D 5.C四、 解答

10、題（共70分）1（1） L(G)=0m1m|M1 共2分，寫(xiě)成扣1分（2） S=>0S1=>00S11=>000111，共3分， =>寫(xiě)成->扣1分（3） 共3分，錯(cuò)處扣0.5分，扣完為止一、判斷題：1.一個(gè)上下文無(wú)關(guān)文法的開(kāi)始符，可以是終結(jié)符或非終結(jié)符。 ( )2.一個(gè)句型的直接短語(yǔ)是唯一的。 ( )3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個(gè)基本塊可用一個(gè)DAG表示。 （ ）5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個(gè)句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 ( )9.采用

11、三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 （ ）10.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( )11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )12.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )13.遞歸下降分析法是一種自下而上分析法。 ( )14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。 ( )15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 ( )16.一個(gè)LL(1)文法一定是無(wú)二義的。 ( )17.逆波蘭法表示的表達(dá)試亦稱(chēng)前綴式。 ( )18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )19.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)

12、文法來(lái)描述。 ( )20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。 ( )二、填空題：1.( )稱(chēng)為規(guī)范推導(dǎo)。2.編譯過(guò)程可分為 （ ） ，（ ），（ ），（ ）和（ ）五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是（ ）。 4.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（ ）語(yǔ)句和（ ）語(yǔ)句兩大類(lèi)。5.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。6.掃描器的任務(wù)是從（ ）中識(shí)別出一個(gè)個(gè)（ ）。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（ ）等等。8.一個(gè)

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

14、態(tài)。18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個(gè)級(jí)別。19.語(yǔ)法分析是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（ ）規(guī)則進(jìn)行的。20.一個(gè)句型的最左直接短語(yǔ)稱(chēng)為句型的（ ）。21.一個(gè)文法G，若它的預(yù)測(cè)分析表M不含多重定義，則該文法是（ ）文法。22.對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN采用( )策略， PASCAL采用( )策略。23.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)， 則稱(chēng)這個(gè)文法是( )。24.最右推導(dǎo)亦稱(chēng)為（ ），由此得到的句型稱(chēng)為（ ）句型。25.語(yǔ)法分析的方法大致可分為兩類(lèi)，一類(lèi)是（ ）分析法，另一類(lèi)是（ ）分析法。26.對(duì)于文

15、法G，僅含終結(jié)符號(hào)的句型稱(chēng)為 ( )。27.所謂自上而下分析法是指（ ）。28.語(yǔ)法分析器的輸入是（ ），其輸出是（ ）。29.局限于基本塊范圍的優(yōu)化稱(chēng)（ ）。30.預(yù)測(cè)分析程序是使用一張（ ）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。31.2型文法又稱(chēng)為（ ）文法；3型文法又稱(chēng)為（ ）文法。32.每條指令的執(zhí)行代價(jià)定義為（ ）。33.算符優(yōu)先分析法每次都是對(duì)（ ）進(jìn)行歸約。三、名詞解釋題：1.局部?jī)?yōu)化2.二義性文法3.DISPLAY表4.詞法分析器5.最左推導(dǎo)6.語(yǔ)法7.文法8.基本塊9.語(yǔ)法制導(dǎo)翻譯10.短語(yǔ)11.待用信息12.規(guī)范句型13.掃描器14.超前搜索15.句柄16.語(yǔ)法制導(dǎo)翻譯17.規(guī)范句型

16、18.素短語(yǔ)19.語(yǔ)法20.待用信息21.語(yǔ)義四、簡(jiǎn)答題：1.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 不以0開(kāi)頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3. 已知文法G(S)SbAaA(B | aBAa)寫(xiě)出句子b(aa)b的規(guī)范歸約過(guò)程。4. 考慮下面的程序：procedure  p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.試問(wèn)，若參數(shù)傳遞的方式分別采

17、用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B的值是什么 5.文法G(S)SdABAaA| aBBb| 描述的語(yǔ)言是什么？6.證明文法G(S) SSaS| 是二義性的。7.已知文法G(S) SBAABS| dBaA| bS | c的預(yù)測(cè)分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過(guò)程。8.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)=albmclanbn| l>=0, m>=1, n>=2 9.已知文法G(S):Sa| (T)TT,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a.>.>(<.&

18、lt;.=.<.)-.>.>,<.<.>.>請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10.何謂優(yōu)化按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化11.目標(biāo)代碼有哪幾種形式生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題12.一字母表=a, b，試寫(xiě)出上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)=abncn| n015.考慮下面的程序：procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print ae

19、nd.試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a的值是什么 16.寫(xiě)出表達(dá)式ab*(c-d)/e的逆波蘭式和三元序列。17.證明文法G(A) AAA | (A)| 是二義性的。25.符號(hào)表的作用是什么符號(hào)表查找和整理技術(shù)有哪幾種五、計(jì)算題：1.設(shè)文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表 3.設(shè)文法G（S）：S(T) | aTT+S | S(1）計(jì)算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 7.已知文法G(S)Sa | | (T)TT,S | S(1) 給出句子(a,(a

20、,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語(yǔ), 直接短語(yǔ)，句柄。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；(2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。 10.設(shè)文法G(S): S(T) | aS | a TT,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.

21、15. 16. 17.× 18. 19. 20.× 21. 22.二、填空題：1.(最右推導(dǎo)）2.(詞法分析），（語(yǔ)法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成）3.(二義性的）4.(執(zhí)行性），（說(shuō)明性）5.(單詞符號(hào)），（語(yǔ)法單位）。6.(源程序），（單詞符號(hào)）7.(類(lèi)型、種屬、所占單元大小、地址）8.(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址)9.(句柄）10.(棧式)，（堆式）11.(類(lèi)型)，（作用域）12.(傳地址），（傳值），（傳名）13.(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）14.(自上而下），（自下而上）15.(分析表），（符號(hào)棧）16.(傳

22、地址），（傳值），（傳名）17.(初），（終）18.(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）19.(語(yǔ)法），（語(yǔ)義）20.(句柄）21.(LL(1) 文法）22.(靜態(tài)），（動(dòng)態(tài)）23.(二義性文法）24.(規(guī)范推導(dǎo)），（規(guī)范）25.(自上而下），（自下而上）26.(句子)27.(從開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）28.(單詞符號(hào)），（語(yǔ)法單位）29.(局部?jī)?yōu)化）30.(分析表），（符號(hào)棧）31.(上下文無(wú)關(guān)文法），（正規(guī)）32.(指令訪問(wèn)主存次數(shù)加1）33.(最左素短語(yǔ)）三、名詞解釋題： 1.局部?jī)?yōu)化-局限于基本塊范圍的優(yōu)化稱(chēng)。2.二義性文法-如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，

23、則稱(chēng)這個(gè)文法是二義性文法。3.DISPLAY表-過(guò)程的嵌套層次顯示表，記錄該過(guò)程的各外層過(guò)程的最新活動(dòng)記錄的起始地址。4.詞法分析器-執(zhí)行詞法分析的程序。5.最左推導(dǎo)-任何一步=>都是對(duì)中的最右非終結(jié)符替換。6.語(yǔ)法-一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法-描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。8.基本塊-指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語(yǔ)句，出口就是其中的最后一個(gè)語(yǔ)句。9.語(yǔ)法制導(dǎo)翻譯-在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法叫做語(yǔ)法制導(dǎo)翻譯。10.短語(yǔ)-令G是一個(gè)文法，S劃文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句型

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

25、何更小的素短語(yǔ)。19.語(yǔ)法-是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。 20.待用信息-如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)有A的其它定值，則稱(chēng)j是四元式i的變量A的待用信息。21.語(yǔ)義-定義程序的意義的一組規(guī)則。四、簡(jiǎn)答題： 1.所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.輸出是42313.句子b(aa)b的規(guī)范歸約過(guò)程：步驟符號(hào)棧輸入串動(dòng)作0#b(aa)b#預(yù)備1#b(aa)b#移進(jìn)2#b(aa)b#移進(jìn)3 #b(a a)b# 移進(jìn)4#b(Aa)b#歸約5 #b(Ma)b#移進(jìn)6#

26、b(Ma)b#移進(jìn)7#b(B b# 歸約8#bAb#歸約9#bAb#移進(jìn)10#S#接受4.傳地址 A=6, B=16傳值 A=2, B=45.L(G)=danbm |n>0, m06.證明： 因?yàn)槲姆℅S存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa7.句子 adccd 的分析過(guò)程：步驟符號(hào)棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd

27、#Ad5#Accd#6#SBccd#ABS7#Scccd# Bc8#S cd# 9#ABcd#Bc10#Acd#11#A d#12#dd#Ad13# 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb9.函數(shù)a(),f4244g552310.優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11.目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。12

28、.正規(guī)式 a ( a | b )*。13.刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫(xiě)傳播和刪除無(wú)用賦值。14.文法GS:SaB | a Bbc |bBc15.傳值 a=2 傳地址 a=1516.逆波蘭式: abcd-*e/+三元序列: op arg1 arg2 (1) - c d (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=>(A)=>()25.作用

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

30、hen BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:=MERG(C.Chain, S(1). Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, aa, ( LASTVT(S)=a, ) LASTVT(T)=+, a, ) (2) a + ( ) a .> .>+ <. .> <. .>( <. <. <. =. ) .> .> >.4. (1) Ffor i:=E(1) to E(2) do SFS(1)(2) Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _,