北方工業(yè)大學(xué)《編譯原理》期中試卷2017

1、北方工業(yè)大學(xué)試卷答案 第 1 頁 共 7 頁 北方工業(yè)大學(xué)北方工業(yè)大學(xué) 編譯原理編譯原理課程課程期中期中試卷試卷答案答案 a 卷卷 2017 年年春春季季學(xué)期學(xué)期 開課學(xué)院：開課學(xué)院： 計(jì)算機(jī)計(jì)算機(jī) 考試方式：閉卷考試方式：閉卷 考試時(shí)間：考試時(shí)間：95 分鐘分鐘 班班級(jí)級(jí) 姓名姓名 學(xué)號(hào)學(xué)號(hào) 題題 號(hào)號(hào) 一一 二二 三三 四四 五五 六六 七七 八八 九九 十十 總總 分分 得得 分分 閱卷人閱卷人 一、一、 判斷題判斷題（每個(gè)小題每個(gè)小題 1 分分，共，共 10 分分） 1. 匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對(duì)象的不同。 （ ） 2. 解釋程序同時(shí)處理源程序和數(shù)據(jù)。 （ ）

2、3. 編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。 （ ） 4. 上下文有關(guān)文法所定義的語法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。 （ ） 5. 喬姆斯基把文法分為 0 型、1 型、2 型和 3 型，0 型文法的描述能力弱于 1型。 （ ） 6. 詞法分析器不斷地從輸入緩沖區(qū)讀入字符串，并進(jìn)行識(shí)別。 （ ） 7. 超前搜索是為了得到某一個(gè)單詞符號(hào)的確切性質(zhì)，需要超前掃描若干個(gè)字符。 （ ） 8. 一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)為初態(tài)，一個(gè)為終態(tài)。 （ ） 9. lr 分析法不是規(guī)范歸約方法。 （ ） 10. 程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義。 （ ） 解： 1. 2. 3.

3、4. 5. 6. 7. 8. 9. 10. 二、二、 選擇題（每個(gè)選擇題（每個(gè)小題小題 1 分，共分，共 20 分）分） 1. 自下而上語法分析的工作原理是_。 a. 移進(jìn)-推導(dǎo)法 b. 最左推導(dǎo)法 c. 移進(jìn)-規(guī)約法 d. 推導(dǎo)-規(guī)約法 2. lr 分析法每次都是對(duì)當(dāng)前句型的_進(jìn)行規(guī)約。 a. 素短語 b. 句柄 c.短語 d. 最左素短語 序號(hào) 訂 線 裝 北方工業(yè)大學(xué)試卷答案 第 2 頁 共 7 頁 3. 如果文法 g 是無二義的，則對(duì)于它的任何句子_。 a. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 b. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 c. 最左推導(dǎo)和最右推導(dǎo)必定相同 d. 可

4、能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 4. 消除間接左遞歸時(shí)，由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是_。 a. 等價(jià)的 b. 不等價(jià)的 c. 形式上不一樣 d. 形式上完全一樣 5. 語法制導(dǎo)翻譯法直觀上說就是為文法中每個(gè)產(chǎn)生式配上一組語義規(guī)則，并且在語法分析的同時(shí)_這些語義規(guī)則。 a. 考慮 b. 不考慮 c. 不執(zhí)行 d. 執(zhí)行 6. 若一個(gè)文法是遞歸的，則它產(chǎn)生的句子個(gè)數(shù)是_。 a. 有限個(gè) b. 無窮個(gè) c. 可能有限個(gè) d. 以上均不對(duì) 7. 下面哪種不是自下而上的語法分析方法_。 a. slr(1) b. lr(1) c. ll

5、(1) d. 算符優(yōu)先分析法 8. 一個(gè)上下文無關(guān)文法消除了左遞歸，提取了公共左因子后是滿足 ll(1) 文法的 _。 a. 沒有關(guān)系 b. 充分必要條件 c. 必要條件 d. 充分條件 9. 正規(guī)式 m1和 m2等價(jià)是指_。 a. m1和 m2的有向邊條數(shù)相等 b. m1和 m2的狀態(tài)數(shù)相等 c. m1和 m2的狀態(tài)數(shù)和有向邊條數(shù)相等 d. m1和 m2所識(shí)別的語言集相等 10. 字母表a,b上以 aa 開頭任何符號(hào)串的集合，可用正規(guī)式表示為_。 a. aa(a*|b*) b. a、b、 c 均不正確 c. aa(a|b)* d. (a|b)*aa 11. 文法 g 所描述的語言是_的集合。

6、 a. 文法 g 的字母表 的閉包 *中的所有符號(hào)串 b. 由文法的開始符號(hào)推出的所有終結(jié)符號(hào)串 c. 由文法的開始符號(hào)推出的所有符號(hào)串 d. 文法 g 的字母表 中所有符號(hào)組成的符號(hào)串 12. 經(jīng)過編譯所得到的目標(biāo)程序是_。 a. 四元式序列 b. 間接三元式序列 c. 三元式序列 d. 機(jī)器語言程序或匯編語言程序 13. _和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。 a語法分析 b中間代碼生成 c詞法分析 d目標(biāo)代碼生成 北方工業(yè)大學(xué)試卷答案 第 3 頁 共 7 頁 14. 不可能是目標(biāo)代碼的是_。 a中間代碼 b可重定位的指令代碼 c絕對(duì)指令代碼 d匯編指令代碼 15. 語言是_。 a句子

7、的集合 b產(chǎn)生式的集合 c符號(hào)串的集合 d句型的集合 16. 一個(gè)句型的最左素短語是指處于句型最左邊的_。 a非終結(jié)符號(hào) b短語 c素短語 d直接短語 17. 自上而下分析法是從文法開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找匹配的 _。 a終結(jié)符號(hào) b規(guī)約 c推導(dǎo) d非終結(jié)符號(hào) 18. 自下而上分析的核心問題是識(shí)別_。 a最左素短語 b可歸約串 c句柄 d非終結(jié)符號(hào) 19. 規(guī)范歸約是一個(gè)_的逆過程。 a規(guī)范句型 b最左歸約 c最左推導(dǎo) d規(guī)范推導(dǎo) 20. 在正規(guī)式中運(yùn)算符的優(yōu)先級(jí)從高到低的順序是_。 a ，*，| b |， ，*， c*， ， | d*，| ， 解： 1. c 2. b 3. a

8、 4. a 5. d 6. b 7. c 8. d 9. d 10. c 11. b 12.d 13.b 14. a 15. a 16. c 17. c 18. b 19. d 20. c 三、三、填填 空題（每空空題（每空 1 分，共分，共 10 分）分） 1. 有些編譯程序?qū)?yōu)化沒有要求， 階段即可省去。 2. 是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。 3. 語法分析的描述工具是 。 4. 自下而上分析法基本思想是從輸入串開始，逐步進(jìn)行 ，直到文法的開始符號(hào)。即從樹末端開始，構(gòu)造語法樹。 5. 消除左遞歸前后，文法的 不變。 6. 由源程序的語法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就是 。 7. 項(xiàng)目 sb.b

9、b 是 。 8. 綜合屬性是 傳遞信息。 9. 僅僅使用綜合屬性的屬性文法稱為 文法。 10. lr(k)分析法中的 r 是指 對(duì)應(yīng)的最左歸約。 解：1. 優(yōu)化 2. 單詞符號(hào) 3. 上下文無關(guān)文法 4. 歸約 5. 開始符號(hào) 6. 語法制導(dǎo)翻譯法 7. 待約項(xiàng)目 8. 自下而上 9. s-屬性 10. 最右推導(dǎo) 四、四、簡(jiǎn)答題（簡(jiǎn)答題（60 分）分） 北方工業(yè)大學(xué)試卷答案 第 4 頁 共 7 頁 1. 請(qǐng)給出一個(gè)上下文無關(guān)文法，使其語言是能被 5 整除且不以 0 開頭的無符號(hào)整數(shù)的集合。 （5 分） 解：文法 gs為： smf| 5 f5 | 0 n1 | 2 | 3 | 4 | 5 | 6

10、 | 7 | 8 | 9 dn | 0 mmd | n 2. 請(qǐng)給出一個(gè)上下文無關(guān)文法 g， 使得 l(g)=anbmcmdn | n0, m1 （3 分） 解：文法 gs為： sasd| a abac | bc 3. 語言 l 是所有由偶數(shù)個(gè) 0 和偶數(shù)個(gè) 1 組成的句子的集合，請(qǐng)給出定義 l 的右線性正規(guī)文法。 （5 分） 解：構(gòu)造狀態(tài)轉(zhuǎn)換圖為： l 的右線性正規(guī)文法為： 4. 請(qǐng)證明下面的文法 ge是二義文法。 eeit | t t t+f | if | f fe* | ( （3 分） 北方工業(yè)大學(xué)試卷答案 第 5 頁 共 7 頁 5. 請(qǐng)構(gòu)造正規(guī)式(a|b)*abb 相應(yīng)的最小化的 d

11、fa。 （12 分） 北方工業(yè)大學(xué)試卷答案 第 6 頁 共 7 頁 6. 對(duì)于文法 gs： ss*atat*at t+at+a （1）請(qǐng)給出句型 a+a*a+at 的最左推導(dǎo)，并給出語法樹； （2）給出上述句型的所有短語、直接短語、句柄和最左素短語。 （10 分） 7. 對(duì)于文法 gs： s iets | ietses | a e b （1）請(qǐng)給出消除 gs的左遞歸和回溯后的文法； （2）計(jì)算消除 gs左遞歸和回溯后文法的每個(gè)非終結(jié)符的 first 和 follow； （3）構(gòu)造它的預(yù)測(cè)分析表；證明這個(gè)文法是否是 ll(1)文法； （4）請(qǐng)改造文法，并為之構(gòu)造滿足 ll(1)文法的 ll(1)

12、分析表。 （12 分） 解：（1）gs不存在左遞歸，存在回溯。提取公共左因子，消除 gs的左遞歸和回溯后的文法 gs : s ietss | a s es | e b （2） 計(jì)算消除 gs左遞歸和回溯后文法 gs的每個(gè)非終結(jié)符的 first 和 follow； first(s)=i, a follow(s)=e, # first(s)=e, follow(s)=e, # first(e)=b follow(e) =t （3）構(gòu)造它的預(yù)測(cè)分析表為： 北方工業(yè)大學(xué)試卷答案 第 7 頁 共 7 頁 a b e i t # s sa sictss s s ses s e eb 由于 first(es)follow(s)=ee, #=e ，所以證明了 gs不是 ll(1)文法。 （4） 根據(jù)最近匹配原則， 在嵌套 if-then-else 語句中， else 和 if 按照最近匹配原則配對(duì)，即相距最近且還沒有配對(duì)的一對(duì) if 和 else 首先配對(duì)。 改造后的文法 gs