編譯原理試卷2

北京工業(yè)大學(xué)2088-2089學(xué)年第一學(xué)期試卷考試課程：編譯原理考試日期：年月日學(xué)院：專(zhuān)業(yè)：學(xué)號(hào)：姓名：成績(jī)：題號(hào)一二三四總分成績(jī)閱卷教師一、選擇題（16分）1、描述高級(jí)語(yǔ)言詞法的最簡(jiǎn)單模型是(D)。A、上下文無(wú)關(guān)文法B、圖靈機(jī)C、下推自動(dòng)機(jī)D、有窮狀態(tài)自動(dòng)機(jī)2、自頂向下的語(yǔ)法分析在于尋找輸入串的(A)。A、推導(dǎo)（派生）B、歸約C、回溯D、推導(dǎo)（派生）或者歸約3、通常編譯程序是把高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序翻譯為(D)程序。A、BASIC語(yǔ)言B、中間語(yǔ)言C、另一種高級(jí)語(yǔ)言D、等價(jià)的機(jī)器/匯編語(yǔ)言4、代碼優(yōu)化的目的是加快(B)的執(zhí)行速度。A、編譯程序B、目標(biāo)程序C、源程序D、編譯程序和目標(biāo)程序5、符號(hào)表存取方法影響(A)的效率。A、編譯程序B、目標(biāo)程序C、解釋程序D、編譯程序和目標(biāo)程序6、設(shè)有文法G[E]：EE+E|E*E|（E）|i。在下述文法類(lèi)中，文法G[E]屬于(A)、(B)和(D)。A、算符文法B、上下文無(wú)關(guān)文法C、正規(guī)文法D、二義文法二、簡(jiǎn)答題（18分）1、簡(jiǎn)要解釋編譯程序中的遍（趟）的含義。2、何為“標(biāo)識(shí)符”？何為“名字”？?jī)烧叩膮^(qū)別是什么？在程序設(shè)計(jì)語(yǔ)言中，標(biāo)識(shí)符是一個(gè)最基本的概念，其定義為：凡以字母開(kāi)頭的字母數(shù)字序列(有限個(gè)字符)都是標(biāo)識(shí)符。當(dāng)給予某標(biāo)識(shí)符以確切的含義時(shí)，這個(gè)標(biāo)識(shí)符就叫做名字。程序語(yǔ)言中各種名字都是用標(biāo)識(shí)符表示的，只是標(biāo)識(shí)符是一個(gè)沒(méi)有意義的字符序列，而名字卻有著確切的意義和屬性。3、簡(jiǎn)述為什么自頂向下的語(yǔ)法分析技術(shù)不能處理具有左遞歸的文法？這是由于在自頂向下的語(yǔ)法分析技術(shù)中，要解決的問(wèn)題是根據(jù)當(dāng)前輸入符號(hào)判斷將棧頂（最左）的非終結(jié)符號(hào)替換成哪條規(guī)則的右部，若文法具有左遞歸，則在分析過(guò)程中，無(wú)法判斷出替換的規(guī)則，造成無(wú)窮遞歸求解的過(guò)程。三、文法設(shè)計(jì)（22分）1、已知語(yǔ)言L={anbm|m≥n≥0}對(duì)應(yīng)的上下文無(wú)關(guān)文法為S→aSb|Sb|ε（1）試說(shuō)明該文法是二義文法；（本小題4分）（2）試給出該語(yǔ)言一個(gè)等價(jià)的無(wú)二義性的上下文無(wú)關(guān)文法。（本小題6分）S->aSb|bS’|εS’->bS’|ε2、設(shè)計(jì)上下文無(wú)關(guān)文法G，使得abcdba∈L(G),且G中至少含有三個(gè)語(yǔ)法變量（非終結(jié)符）。（本小題12分）（1）給出設(shè)計(jì)的文法；（2）畫(huà)出該句子的語(yǔ)法分析樹(shù)；（3）寫(xiě)出該句子的最右推導(dǎo)中的任意一個(gè)句型，并指出該句型中的句柄。四、語(yǔ)法分析（44分）1、考慮文法G[S]：S→(T)|a+S|aT→T,S|S試消去該文法的左遞歸并提取左因子；（本題8分）2、寫(xiě)出下面文法中各候選式的FIRST集和各非終結(jié)符的FOLLOW集,構(gòu)造該文法的LL（1）分析表，并說(shuō)明它是否為L(zhǎng)L（1）文法；（本題16分）S→aA|BAA→cB|B→bB|解：各候選式的FIRST集FIRST（aA）={a}FIRST（BA）={b，c，}FIRST（cB）={c}FIRST（）={}FIRST（bB）=FIRST（）={}各非終結(jié)符的FOLLOW集FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(B)={c，#}LL（1）分析表abc#SS→aAS→BAS→BAS→BAAA→cBA→BB→bBB→B→說(shuō)明它是否為L(zhǎng)L（1）文法(2分)判斷1分，理由1分因?yàn)長(zhǎng)L（1）分析表無(wú)沖突，所以該文法是LL（1）文法。3、考慮文法G