編譯原理期末考試復(fù)習(xí)題

1、編譯原理參考題目第一套一、判斷題1用高級(jí)語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。( N)2若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( N)3一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 (Y )4在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 ( N)5僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 (Y )6削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 (Y )7在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 (N )8算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 ( N)9數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 (N

2、)10編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。 (N )參考答案：1、2、3、4、5、6、7、8、9、10、二、選擇題1 通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括_。A模擬執(zhí)行器 B解釋器 C表格處理和出錯(cuò)處理 D符號(hào)執(zhí)行器2 文法 GN= （ b ， N ， B ， N ， NbbB ， BbN ），該文法所描述的語言是 A L(GN)=bii0 B L(GN)=b2ii0 C L(GN)=b2i+1i0 D L(GN)=b2i+1i13 一個(gè)句型中的最左_稱為該句型的句柄。 A短語 B簡單短語 C素短語 D終結(jié)符號(hào) 4 設(shè)

3、 G 是一個(gè)給定的文法， S 是文法的開始符號(hào)，如果 S-x( 其中 xV*), 則稱 x 是文法 G 的一個(gè)_。 A候選式 B句型 C單詞 D產(chǎn)生式 5 文法 GE ： ETE T TFT F Fa （ E ） 該文法句型 E F (E T) 的簡單短語是下列符號(hào)串中的_。 （ E T ） E T F F (E T) A 和 B 和 C 和 D 6 若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子_。A( ) 是無窮多個(gè) B( ) 是有窮多個(gè) C( ) 是可枚舉的 D( ) 個(gè)數(shù)是常量 7 詞法分析器用于識(shí)別_。 A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式 8 在語法分析處理

4、中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_。 A. ( ) 非終極符集 B( ) 終極符集 C( ) 字母表 D. ( ) 狀態(tài)集 9 在自底向上的語法分析方法中，分析的關(guān)鍵是_。 A.( ) 尋找句柄 B.( ) 尋找句型 C.( ) 消除遞歸 D.( ) 選擇候選式 10 在 LR 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型_的 DFA 狀態(tài)。 A.( )句柄 B.( ) 前綴 C.( )活前綴 D.( ) LR(0) 項(xiàng)目參考答案：1、C2、C3、B4、B5、B6、A7、C8、B9、D10、C三、填空題1設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S-x(

5、 其中 xVT*), 則稱 x是文法的一個(gè)_句子_。 2遞歸下降法不允許任一非終極符是直接 左 遞歸的。3自頂向下的語法分析方法的基本思想是：從文法的_開始符號(hào)_開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)出文法的_句子_，使之與給定的輸入串_匹配_。 4自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接規(guī)約_ ，力求 歸約到文法的_開始符號(hào)_。 5常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 6在使用高級(jí)語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯(cuò)誤和語義部分錯(cuò)誤。參考答案：1句子2左3開始符號(hào) 直接推導(dǎo)

6、 句子 匹配4直接歸約 開始符號(hào)5傳地址6語法四、簡答題1. 已知文法 GS 為： SdAB AaA|a BBb| GS 產(chǎn)生的語言是什么？ 參考答案：答：GS產(chǎn)生的語言是L(GS)=danbmn1,m0。 2. 簡述 DFA 與 NFA 有何區(qū)別 ? 參考答案：答：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以若干個(gè)開始狀態(tài)，而DFA僅只一個(gè)開始狀態(tài)。 另一方面，DFA的映象M是從K到K，而NFA的映象M是從K到K的子集， 即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。 5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？參考答案：(1)優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變

7、換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。 (2) 三種級(jí)別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五.計(jì)算題（10分） 對(duì)下面的文法 G ： E-TE E-+E| T-FT T -T| F- PF F- *F| P-(E)|a|b| (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。參考答案：解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T)=FIRST(

8、T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含F(xiàn)OLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含F(xiàn)OLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;FOLL

9、OW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含(2)證明這個(gè)方法是LL(1)的。各產(chǎn)生式的SELECT集合有： SELECT(E-TE)=FIRST(T)=(,a,b,;SELECT(E-+E)=+;SELECT(E-)=FOLLOW(E/)=),#SELECT(T-FT)=FIRST(F)=(,a,b,;SELECT(T-T)=FIRST(T)=(,a,b,;SELECT(T-)=FOLLOW(T/)=+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,; SELECT(F-*F)=*;SELECT(F-)=FOLLOW(F)=(,a,b

10、,+,),#; SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-)=可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3)構(gòu)造它的預(yù)測分析表。文法GE的預(yù)測分析表如下：第二套一、判斷題1對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。( N)2甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。( N)3遞歸下降分析法是自頂向上分析方法。( Y)4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 (N )5LR 法是自頂向下語法分析方法。 (Y )6在 SLR （ 1 ）分析法

11、的名稱中，S的含義是簡單的。(Y )7綜合屬性是用于 “ 自上而下 ” 傳遞信息。(N )8符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 (N )9程序語言的語言處理程序是一種應(yīng)用軟件。 ( N)10解釋程序適用于 COBOL 和 FORTRAN 語言。 ( N)二、選擇題1 文法 G 產(chǎn)生的_的全體是該文法描述的語言。 A( ) 句型 B( ) 終結(jié)符集 C( ) 非終結(jié)符集 D( ) 句子2 若文法 G 定義的語言是無限集，則文法必然是 _。 A( ) 遞歸的 B( ) 前后文無關(guān)的C( ) 二義性的 D( ) 無二義性的3 四種形式語

12、言文法中，1型文法又稱為 _文法。 A( ) 短語結(jié)構(gòu)文法 B( ) 前后文無關(guān)文法 C( ) 前后文有關(guān)文法 D( ) 正規(guī)文法 4 一個(gè)文法所描述的語言是_。 A( ) 唯一的 B( ) 不唯一的 C( ) 可能唯一，好可能不唯一 D( ) 都不對(duì)5 _和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。 A( ) 語法分析 B( ) 中間代碼生成 C( ) 詞法分析 D( ) 目標(biāo)代碼生成 6_是兩類程序語言處理程序。 A( ) 高級(jí)語言程序和低級(jí)語言程序 B( ) 解釋程序和編譯程序 C( ) 編譯程序和操作系統(tǒng) D( ) 系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_的信息。 A.

13、( ) 維數(shù) B( ) 類型 C( ) 維上下界 D( ) 各維的界差 8. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _。 A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_。 A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關(guān)文法D( ) 上下文無關(guān)文法10文法 G 所描述的語言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串 B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串 C( ) 由文法的開始

14、符號(hào)推出的所有終極符串 D. ( ) 由文法的開始符號(hào)推出的所有符號(hào)串參考答案：1、D2、A3、C4、A5、B6、B7、A8、D9、D10、C三、填空題1一個(gè)句型中的最左簡單短語稱為該句型的_句柄_。 2對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語義規(guī)則_ 。3一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。 6 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。

15、參考答案：1句柄2語義規(guī)則3詞法分析 語法分析 中間代碼生成4執(zhí)行性 說明性5源程序 單詞符號(hào)6語法范疇四、簡答題1. 寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。 參考答案：解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D五、計(jì)算題已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(z,1)=y, 構(gòu)造相應(yīng)的DFA并最小化。 參考答案：解：根據(jù)題意有NFA圖: 下表由子集法將NFA轉(zhuǎn)換為DFA：下面將該DFA最小化： (1)

16、 首先將它的狀態(tài)集分成兩個(gè)子集：P1=A,D,E,P2=B,C,F (2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價(jià)（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。 (3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所

17、以最小化的DFA如下：第三套一、判斷題1一個(gè) LL(l)文法一定是無二義的。 ( N)2正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( N)3一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。 ( Y)4目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( N)5逆波蘭法表示的表達(dá)式亦稱前綴式 。 (Y )6如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。 (Y )7LR 法是自頂向下語法分析方法。 ( N)8數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。( N)9算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 (N )10對(duì)于數(shù)據(jù)空間的存貯分配， F

18、ORTRAN 采用動(dòng)態(tài)貯存分配策略。 (N )參考答案：1、2、3、4、5、6、7、8、9、10、二、選擇題1詞法分析器用于識(shí)別_。 A( ) 字符串 B( )語句 C( )單詞 D( )標(biāo)識(shí)符2文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_。 A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關(guān)文法D( ) 上下文無關(guān)文法3一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _。 A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產(chǎn)生式4_是一種典型的解釋型語言。 A( ) BASIC B( ) C C(

19、) FORTRAN D( ) PASCAL5與編譯系統(tǒng)相比，解釋系統(tǒng)_。 A( ) 比較簡單 , 可移植性好 , 執(zhí)行速度快 B( ) 比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 C( ) 比較簡單 , 可移植性差 , 執(zhí)行速度慢 D( ) 比較簡單 , 可移植性好 , 執(zhí)行速度慢 6用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_。 A( ) 源程序 B( ) 目標(biāo)程序 C( ) 連接程序 D( ) 解釋程序7詞法分析器用于識(shí)別_。 A. ( ) 字符串 B( ) 語句 C( ) 單詞 D( ) 標(biāo)識(shí)符 8編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后 , 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過_這幾步: (1) 編輯

20、(2) 編譯 (3) 連接 (4) 運(yùn)行 A. ( ) (1)(2)(3)(4) B( ) (1)(2)(3) C( ) (1)(3) D( ) (1)(4)9把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_完成的。 A( ) 編譯器 B( ) 匯編器 C( ) 解釋器 D( ) 預(yù)處理器10文法 G 所描述的語言是_的集合。 A. ( ) 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串 B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串 C( ) 由文法的開始符號(hào)推出的所有終極符串 D. ( ) 由文法的開始符號(hào)推出的所有符號(hào)串參考答案：1、C2、A3、D4、A5、D6、B7

21、、C8、B9、B10、C三、填空題1語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。2語法分析器的輸入是單詞符號(hào)串_，其輸出是_語法單位_。3一個(gè)名字的屬性包括_類型_和_作用域_。4產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。5逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為 (a+b+c)*d-e _ 。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 參考答案：1語法 語義 2單詞符號(hào)串 語法單位 3類型 作用域4語法成分5(a+b+c)*d-e6自上而下 自下而上四、簡答題1. 寫出下列表達(dá)式的三地址形式的中間表示。(1) 5+6 *(

22、a + b); (2)for j:=1 to 10 do aj + j:=0。參考答案：答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1 101: if j10 goto NEXT 102: i:=j+j 103: ai:=0 3. 寫出表達(dá)式(a+b)/(a-b)-(a+b*c)的三元序列及四元序列。參考答案：解：（1）三元式： （，a，b） （，a，b） （/，） （*，b，c） （，a，） （，） （2）四元式： （，a，b，T1） （，a，b，T2） （/，T1，T2，T3） （*，b，c，T4） （，a，T4，T5

23、） （，T3，T5，T6） 4. 寫一個(gè)文法使其語言為偶數(shù)集，且每個(gè)偶數(shù)不以0開頭。 參考答案：解：文法G（S）： SAB|B|A0 AAD|C B2|4|6|8 C1|3|5|7|9|B D0|C 5. 設(shè)文法 G （ S ）： SS aF|aF| aF F*aF|*a （1）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。參考答案：（1） S-aFS|aFS S-aFS| F-*aF F-F| （2） FIRST（S）a，+ FOLLOW（S） FIRST（S）+， FOLLOW（S） FIRST（F）* FOLLoW（F）（+， FIRST（F）*， FOLLOW

24、（+，第四套一、判斷題1編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。( N)2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。( N)3一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( Y)4語法分析時(shí)必須先消除文法中的左遞歸 。 (N )5LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 (Y )6逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。 (Y )7靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 (X )8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。 (X )9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 ( Y)10一個(gè)語義子程序描述了一個(gè)文法所對(duì)

25、應(yīng)的翻譯工作。 ( X)參考答案：1、2、3、4、5、6、7、8、9、10、二、選擇題1詞法分析器的輸出結(jié)果是_。 A( ) 單詞的種別編碼 B( ) 單詞在符號(hào)表中的位置 C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_。 A( ) M1和M2的狀態(tài)數(shù)相等 B( ) M1和M2的有向邊條數(shù)相等 C( ) M1和M2所識(shí)別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語言是_。 A( ) xyx B( ) (xyx)* C( ) xnyxn(n0) D( ) x*yx* 4如果文法G是無二義的，則它的任

26、何句子_。 A( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同 D( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_。 A( )源程序 B( ) 目標(biāo)語言 C( ) 編譯方法 D( ) 以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過_實(shí)現(xiàn)的。 A( ) 指示器 B( ) 臨時(shí)變量 C( ) 符號(hào)表 D( ) 程序變量 7表達(dá)式(AB)(CD)的逆波蘭表示為_。 A. ( ) ABCD B( ) ABCD C( ) ABCD D( ) ABCD 8. 優(yōu)化可生成_的目標(biāo)代碼。 A( ) 運(yùn)行

27、時(shí)間較短 B( ) 占用存儲(chǔ)空間較小 C( ) 運(yùn)行時(shí)間短但占用內(nèi)存空間大 D( ) 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. ( ) 強(qiáng)度削弱 B( ) 刪除歸納變量 C( ) 刪除多余運(yùn)算 D( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識(shí)符的作用域。 A. ( ) 說明標(biāo)識(shí)符的過程或函數(shù)名 B( ) 說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次 C( ) 說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D. ( ) 標(biāo)識(shí)符的行號(hào)參考答案：1、C2、C3、C4、A5、D6、B7、B8、D9、C10、B三、填空題1計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_

28、詞法分析器 _，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5后綴式abc-/所代表的表達(dá)式是_ a/(b-c)_。 6局部優(yōu)化是在基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。參考答案：1解釋 編譯2詞法分析器 源程序 詞法分析3移進(jìn) 接受4一張分析表5a/(b-c)6基本塊四、簡答題1. 簡要說明語義分析的基本功能。參考答案：答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文

29、法 GS: S (T) | a+S | aT T,S | S消除文法的左遞歸及提取公共左因子。參考答案：解：消除文法GS的左遞歸：S(T) | a+S | aTSTT,ST| 提取公共左因子：S(T) | aSS+S | TSTT,ST| 3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。參考答案：解： w a b + c d e 10 - / + 8 + * +第五套一、判斷題1設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。(N )2確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。(Y )3詞法分析作為單獨(dú)的一遍來處理較好。 (N )4構(gòu)造

30、LR分析器的任務(wù)就是產(chǎn)生LR分析表。 (Y )5規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 (N )6同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突。 (N )7LR分析技術(shù)無法適用二義文法。 (N )8樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 ( N)9程序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。 (Y )10對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。 (N )參考答案：1、2、3、4、5、6、7、8、9、10、二、選擇題1編譯程序絕大多數(shù)時(shí)間花在_ 上。 A( ) 出錯(cuò)處理 B( ) 詞法分析 C( ) 目標(biāo)代碼生成 D( ) 表格管理2 編譯程序是對(duì)_。 A( ) 匯編程序的

31、翻譯 B( ) 高級(jí)語言程序的解釋執(zhí)行C( ) 機(jī)器語言的執(zhí)行 D( ) 高級(jí)語言的翻譯 3 采用自上而下分析，必須_。 A( ) 消除左遞歸 B( ) 消除右遞歸C( ) 消除回溯 D( ) 提取公共左因子 4在規(guī)范歸約中，用_來刻畫可歸約串。 A( )直接短語 B( )句柄 C( )最左素短語 D( )素短語 5 若a為終結(jié)符，則A- a為_項(xiàng)目。 A( )歸約 B( ) 移進(jìn) C( ) 接受 D( ) 待約 6間接三元式表示法的優(yōu)點(diǎn)為_。 A( ) 采用間接碼表，便于優(yōu)化處理 B( ) 節(jié)省存儲(chǔ)空間，不便于表的修改 C( ) 便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D( ) 節(jié)省存儲(chǔ)空間，不便于優(yōu)化

32、處理 7基本塊內(nèi)的優(yōu)化為_。 A. ( ) 代碼外提，刪除歸納變量 B( ) 刪除多余運(yùn)算，刪除無用賦值 C( ) 強(qiáng)度削弱，代碼外提 D( ) 循環(huán)展開，循環(huán)合并 8. 在目標(biāo)代碼生成階段，符號(hào)表用_。 A( ) 目標(biāo)代碼生成 B( ) 語義檢查 C( ) 語法檢查 D( ) 地址分配9若項(xiàng)目集Ik含有A- ，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aFOLLOW(A)時(shí)，才采取“A- ”動(dòng)作的一定是_。 A. ( ) LALR文法 B( ) LR(0)文法 C( ) LR(1)文法D( ) SLR(1)文法10堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_原則。 A. ( ) 先請(qǐng)先放 B( ) 先請(qǐng)后放 C( ) 后請(qǐng)先放 D. ( ) 任意參考答案