1、系別_ 專業(yè)_年級(jí)_姓名_學(xué)號(hào) 密封線 計(jì)科專業(yè)編譯原理 課題 號(hào)一二三四五總 分總分人復(fù)核人分 數(shù)一、分?jǐn)?shù)評(píng)卷人選擇題：（每小題2分，共20分，請(qǐng)將答案寫在下面的答題欄中，否則答案無(wú)效）123456789101. 一個(gè)文法所描述的語(yǔ)言是 ；描述一個(gè)語(yǔ)言的文法是 。A 唯一的；唯一的 B 唯一的；不唯一的C 不唯一的；不唯一的 D 不唯一的；唯一的2. 若文法 G 定義的語(yǔ)言是無(wú)限集，則文法必然是 。A 遞歸的 B上下文無(wú)關(guān)的C二義性的 D無(wú)二義性的3. 文法 G 產(chǎn)生的 的全體是該文法描述的語(yǔ)言。A 句型 B 終結(jié)符號(hào)集 C 非終結(jié)符號(hào)集 D 句子4 下面狀態(tài)轉(zhuǎn)換圖接受的字集為 。 A.以0

2、開(kāi)頭的二進(jìn)制數(shù)組成的集合 B.以0結(jié)尾的二進(jìn)制數(shù)組成的集合C. 含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 D.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合5 在下述的編譯方法中，簡(jiǎn)單優(yōu)先分析 算符優(yōu)先分析 遞歸下降分析 預(yù)測(cè)分析技術(shù) LR(k)分析 SLR分析 LL(k)分析 LALR(k)分析自底向上的方法有 。A B C D 6自頂向下的分析方法有 。A B C D 7 Chomsky 定義的四種形式語(yǔ)言文法中，0 型文法又稱為 文法；A 短語(yǔ)文法 B上下文無(wú)關(guān)文法 C上下文有關(guān)文法 D正規(guī)文法8 1 型文法又稱為 文法；A 短語(yǔ)文法 B上下文無(wú)關(guān)文法 C上下文有關(guān)文法 D正規(guī)文法9 3型文法可以由 準(zhǔn)確的識(shí)別A

3、圖靈機(jī) B下推自動(dòng)機(jī) C有限自動(dòng)機(jī) D以上皆不對(duì)10詞法分析器的輸出結(jié)果是 。A、單詞自身值B、單詞在符號(hào)表中的位置C、單詞的種別編碼D、單詞的種別編碼和自身值二、分?jǐn)?shù)評(píng)卷人簡(jiǎn)答題：（每題10分，共20分）1簡(jiǎn)述編譯過(guò)程的五個(gè)階段及各個(gè)階段的任務(wù)。2簡(jiǎn)述自下而上語(yǔ)法分析方法基本思想及其中心問(wèn)題是什么？三、分?jǐn)?shù)評(píng)卷人推導(dǎo)計(jì)算題：（共60分）1(10分)給出下面語(yǔ)言的相應(yīng)文法L(G)=anbnci| n1，i0。2(10分)構(gòu)造正規(guī)式(a|b) * (aa|bb)(a|b)*的DFA （寫出步驟）。3 (20分)對(duì)文法G(S)：S a | | (T)T T，S | S(1) 構(gòu)造各非終結(jié)符的FIR

4、STVT和LASTVT集合；(2) 構(gòu)造算符優(yōu)先表，該文法是算符優(yōu)先文法嗎?(3) 給出輸入串（a，（a，a）的算法分析過(guò)程?（注：答案格式為：步驟 棧 關(guān)系 輸入符 剩余輸入符 動(dòng)作）4(20分)考慮文法 EaAbB AcAd BcBd (1) 列出這個(gè)文法的所有LR(0)項(xiàng)目。(2) 構(gòu)造這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族及識(shí)別活前綴的DFA。(3) 這個(gè)文法是SLR文法嗎？給出原因。第 5 頁(yè) 共 頁(yè)計(jì)科專業(yè)編譯原理 課參考答案及評(píng)分標(biāo)準(zhǔn)一、選擇題（每小題2分，共20分） 1-5 BADDC 6-10 AABCD 二、簡(jiǎn)答題（每題10分，共20分）1（1）詞法分析，任務(wù): 輸入源程序，對(duì)構(gòu)

5、成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)。（2）語(yǔ)法分析，任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則把單詞符號(hào)串分解成各類語(yǔ)法單位。（3）中間代碼生成，任務(wù):對(duì)各類不同語(yǔ)法范疇按語(yǔ)言的語(yǔ)義進(jìn)行初步翻譯。（4）優(yōu)化，任務(wù)：對(duì)于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。（5）目標(biāo)代碼生成，任務(wù): 把中間代碼變換成特定機(jī)器上的目標(biāo)代碼。評(píng)分標(biāo)準(zhǔn)：每條2分。2基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直到文法的開(kāi)始符號(hào)。即從樹(shù)末端開(kāi)始，構(gòu)造語(yǔ)法樹(shù)。（4分）中心問(wèn)題：怎樣判斷棧頂符號(hào)串的可歸約性，以及如何歸約。即識(shí)別可歸約串。（6分）三、推導(dǎo)計(jì)算題：（共60分）1. SAC （2分） AaAbab （4分） CcCb （4分）2XY(a|b)*(aa|bb)(a|b)*XYe514236abeeeababab3. (1) (5分) (2) (5分)a(),a>>>>(<<<=<)>>,<<<>>是算符優(yōu)先文法，因?yàn)槿魏蝺蓚€(gè)終結(jié)符之間至多只有一種優(yōu)