編譯原理試卷2

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