編譯原理-2016-2017學(xué)年第二學(xué)期期末考試(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 2016-2017年廣東海洋大學(xué)編譯原理試卷 注：文檔及答案由Adao完善上傳提供，如有疑問或不妥之處，請自行解決。一、填空題1、編譯程序的基本任務(wù)是將 源 程序翻譯成等價的 目標(biāo) 程序。編譯器的各個階段的工作都涉及表格處理和 出錯處理 。2、將非LL（1）文法轉(zhuǎn)換為等價的LL（1）文法的兩種方法是 消除左遞歸 和 提取左公共因子 。3、編譯和解釋程序的根本區(qū)別是 是否生成目標(biāo)代碼 。4、文法G產(chǎn)生的 句子 的全體是該文法描述的語言。5、文法G定義為四元組（Vn，Vt，P，S），其中，Vn為 非終結(jié)符集 ，Vt為 終結(jié)符集 ，P為 產(chǎn)生式集合 ，S稱作 開始符號 。

2、6、2型文法又稱為 上下文無關(guān) 文法，3型文法又稱為 正規(guī) 文法。 3型 文法可用作詞法分析， 2型 文法可用作語法分析。7、通常用于描述詞法規(guī)則的工具有四種， NFA ， DFA ， 正規(guī)文法 ， 正規(guī)式 。8、假設(shè)GS是一個文法，如有S=>x，則稱x是該文法G的 句型 。2、 判斷題如：3型文法一定是2型文法。 ( ) 三、問答題1、 畫出編譯程序的結(jié)構(gòu)框圖。 2、對下圖中的DFA，要求：（1）寫出對應(yīng)的五元組表示形式。（2）求與該DFA等價的正規(guī)式。答：（1）DFA M=（S，U，V，Q，a，b，c，d，f，S，Q）其中：f（S，a）=U f（S，c）

3、=Vf（U，a）=V f（U，b）=Qf（V，b）=U f（V，a）=Qf（Q，c）=Q f（Q，d）=Q（2）等價正規(guī)式：(a|c)(ab)*(a|b)(c|d)*3、將下圖所示NFA轉(zhuǎn)換為等價的DFA并最小化。答：4、給定文法GS：S->AB A->aB|bS|c B->AS|d（1）給出每一個產(chǎn)生式右部的First集；（2）給出每一個非終結(jié)符號的Follow集；（3）給出每一個產(chǎn)生式的Select集；（4）判斷該文法是否為LL（1）文法？若是，給出該文法的預(yù)測分析表。答：5、已知文法GS：S->BA A->Bs|d B->aA|bS|c的預(yù)測分析表如下

4、：abcd#SABS->BAA->BSB->aAS->BAA->BSB->bSS->BAA->BSB->cA->d（1）根據(jù)預(yù)測分析法，給出輸入串a(chǎn)dccd的分析過程步驟分析棧剩余輸出串推導(dǎo)用到的產(chǎn)生式或匹配1#Sadccd# S->BA2#ABadccd# B->aA3#AAaadccd#“a”匹配4#AAdccd#A->d5#Addccd#“d”匹配6#Accd#A->BS7#SBccd#B->c8#Scccd#“c”匹配9#Scd# S->BA10#ABcd#B->c11#Accd#“c”匹配12#Ad#A->d1