《編譯原理》第三版期末復習.doc

《《編譯原理》第三版期末復習.doc》由會員分享，可在線閱讀，更多相關《《編譯原理》第三版期末復習.doc（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

期末復習總結《編譯原理》 第一章：緒論 一、填空問題 ①由于計算機只能認識機器語言，所以需要翻譯程序?qū)⒏呒壵Z言翻譯成計算機可以識別的機器語言。 ②編譯程序的工作過程一般主要劃分為詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等幾個基本階段，同時還會伴有表格管理和出錯處理。 ③如果編譯程序生成的目標程序是機器代碼程序，則源程序的執(zhí)行分為兩個階段：編譯階段和運行階段。如果編譯程序生成的目標程序是匯編語言的程序，則源程序的執(zhí)行分為三個階段：編譯階段，匯編階段和運行階段。 1-02.若源程序是用高級語言編寫的,目標程序是 機器語言程序或匯編程序 ,則其翻譯程序稱為編譯程序. 1-03.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標代碼 . 1-05.對編譯程序而言,輸入數(shù)據(jù)是 源程序 ,輸出結果是 目標程序 . 1-10.一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生 成等五個部分，還應包括 (1)c .其中, (2)b 和代碼優(yōu)化部分不是每個編譯程序都必需的. 詞法分析器用于識別 (3)c ,語法分析器則可以發(fā)現(xiàn)源程序中的 (4)d . (1) a.模擬執(zhí)行器 b.解釋器 c.表格處理和出錯處理 d.符號執(zhí)行器 (2) a.語法分析 b.中間代碼生成 c.詞法分析 d.目標代碼生成 (3) a.字符串 b.語句 c.單詞 d.標識符 (4) a.語義錯誤 b.語法和語義錯誤 c.錯誤并校正 d.語法錯誤 1-11.程序語言的語言處理程序是一種 (1)a . (2)b 是兩類程序語言處理程序,他們的主要區(qū)別在于 (3)d . (1) a.系統(tǒng)軟件 b.應用軟件 c.實時系統(tǒng) d.分布式系統(tǒng) (2) a.高級語言程序和低級語言程序 b.解釋程序和編譯程序 c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應用程序 (3) a.單用戶與多用戶的差別b.對用戶程序的查錯能力 c.機器執(zhí)行效率 d.是否生成目標代碼 1-12.匯編程序是將 a 翻譯成 b ,編譯程序是將 c 翻譯成 d . a.匯編語言程序 b.機器語言程序 c.高級語言程序 d. a 或者 b e. a 或者 c f. b 或者 c 1-13.下面關于解釋程序的描述正確的是 b . (1) 解釋程序的特點是處理程序時不產(chǎn)生目標代碼 (2) 解釋程序適用于COBOL 和 FORTRAN 語言 (3) 解釋程序是為打開編譯程序技術的僵局而開發(fā)的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3) 1-14.高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個階段，而解釋程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后階段產(chǎn)生的目標代碼更為高效. 與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d .解釋程序處理語言時,大多數(shù)采用的是 (3)b 方法. (1): a. 中間代碼生成 b.目標代碼生成 c.詞法分析 d.語法分析 e.代碼優(yōu)化 (2): a.比較簡單,可移植性好,執(zhí)行速度快 b.比較復雜,可移植性好,執(zhí)行速度快 c.比較簡單,可移植性差,執(zhí)行速度慢 d.比較簡單,可移植性好,執(zhí)行速度慢 (3): a.源程序命令被逐個直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為之間代碼,再解釋執(zhí)行 c.先將源程序解釋轉(zhuǎn)化為目標程序,在執(zhí)行 d.以上方法都可以 1-15.用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b .用不同語言編寫的程序產(chǎn)生 a 后,可用 g 連接在一起生成機器可執(zhí)行的程序.在機器中真正執(zhí)行的是 e . a. 源程序 b. 目標程序 c. 函數(shù) d. 過程 e. 機器指令代碼 f. 模塊 g. 連接程序 h.程序庫 1-16.要在某一臺機器上為某種語言構造一個編譯程序,必須掌握下述三方面的內(nèi)容: c , d , f . a. 匯編語言 b. 高級語言 c. 源語言 d. 目標語言 e. 程序設計方法 f. 編譯方法 g. 測試方法 h. 機器語言 1-17.由于受到具體機器主存容量的限制,編譯程序幾個不同階段的工作往往被組合成 (1)d , 諸階段的工作往往是 (2)d 進行的. (1) a. 過程 b. 程序 c. 批量 d.遍 (2) a. 順序 b. 并行 c. 成批 d.穿插 1-18.編譯程序與具體的機器 a , 與具體的語言 a . a. 有關 b.無關 1-19.使用解釋程序時,在程序未執(zhí)行完的情況下， a 重新執(zhí)行已執(zhí)行過的部分. a. 也能 b.不可能 1-20.編譯過程中,語法分析器的任務就是 b . (1) 分析單詞是怎樣構成的 (2)分析單詞串是如何構成語句和說明的 (3) 分析語句和說明是如何構成程序的 (4) 分析程序的結構 a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4) 1-21.編譯程序是一種常用的 b 軟件. a. 應用 b. 系統(tǒng) 1-22.編寫一個計算機高級語言的源程序后,到正式上機運行之前，一般要經(jīng)過 b 這幾步. (1) 編輯 (2) 編譯 (3) 連接 (4) 運行 a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4) 1-23.編譯程序必須完成的工作有 a . (1) 詞法分析 (2) 語法分析 (3) 語義分析 (4) 代碼生成 (5) 之間代碼生成 (6) 代碼優(yōu)化 a. (1)(2)(3)(4) b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6) d. (1)(2)(3)(4)(6) e. (1)(2)(3)(5)(6) 1-24.“用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標代碼后才能投入運行”這種說法 a . a. 不正確 b.正確 1-25.把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由 b 完成的. a. 編譯器 b. 匯編器 c. 解釋器 d. 預處理器 1-26.編譯程序生成的目標程序 b 是機器語言的程序. a. 一定 b. 不一定 1-27.編譯程序生成的目標程序 b 是可執(zhí)行的程序. a. 一定 b. 不一定 1-28．編譯程序是一種 B 。 A. 匯編程序 B. 翻譯程序 C. 解釋程序 D. 目標程序 1-29．按邏輯上劃分，編譯程序第二步工作是 C 。 A. 語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化 1-30．通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應包括 C 。 A.模擬執(zhí)行器 B.解釋器 C.表格處理和出錯處理 D.符號執(zhí)行器 1) 把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由什么完成的？ 解答: 由匯編器（匯編程序）完成的。 19）編譯程序是一種解釋程序嗎？還是什么程序？ 解答:編譯程序是一種翻譯程序。 二、判斷問題 ①高級語言程序必須經(jīng)過編譯程序的翻譯才被計算機識別和執(zhí)行。（錯） 答：對高級語言的翻譯，還有解釋程序。 ②編譯程序的輸入是高級語言，輸出是機器語言程序。（錯） 答：輸出還有匯編語言程序。 ③具有優(yōu)化功能的編譯程序的工作效率高。（錯） 答：優(yōu)化是編譯程序的的一部分，優(yōu)化的目的，是提高目標程序的質(zhì)量和運行效率。 ④有的編譯程序可以沒有目標代碼生成部分。（錯） 答：編譯程序必須生成目標代碼，所以目標代碼生成部分是不可缺少的。 1-31.計算機高級語言翻譯成低級語言只有解釋一種方式。 （） 1-32.在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。 （） 第二章：詞法分析 一、填空題 1、編譯過程中掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位—單詞。 2、高級程序設計語言的單詞通常分為五類，它們是關鍵字、標識符、常數(shù)、運算符以及界限符。 3、確定的有限自動機是一個五元組，通常表示為DFAM=（S，S，d，S0，F(xiàn)）。 4、詞法分析的任務是輸入源程序，輸出單詞符號。 5、確定有限自動機DFA是NFA的一種特例。 6、若二個正規(guī)式所表示的正規(guī)集相同，則認為二者是等價的。 8-01.符號表中的信息欄中登記了每個名字的 屬性和特征等有關信息 ，如類型、種屬、所占單元大小、地址等等。 6-04.終結符只有 綜合屬性 ，它們由詞法分析器提供。 二、判斷題 1、一些語言，它們能被確定的有限自動機識別，但不能用正規(guī)表達式表示。（錯）答：用正規(guī)式表示的語言，都能被確定的有限自動機識別。 2、每一個NFAM都對應有唯一的一個最小化的DFAM。（對） 答：每一個NFAM都可以構造一個DFAM，而DFAM又可以構造一個最小化的DFAM。 3、 一個有限自動機，僅有一個唯一的終態(tài)。（錯） 答：有限自動機的終態(tài)可以有多個。 4、 確定的有限自動機以及不確定的有限自動機都能正確識別正規(guī)集。（對） 答：一個有限自動機能識別該正規(guī)式，所描述的語言（正規(guī)集）。 5、 對任意一個正規(guī)文法G，都存在一個DFAM，滿足L（G）=L（M）。（對） 答：對每一個正規(guī)文法G，都存在一個DFAM，使得L（G）=L（M）。 1、正規(guī)文法一定不是二義性的。（錯） 答：文法的二義性問題是不可避免和不可判定的，正規(guī)文法也可能存在二義性的問題。 2、文法的二義性和語言的二義性是兩個不同的概念。（對） 答：可能有兩個不同的文法G和G`，其中G是二義性的，但是卻有L（G）=L（G`）。 3、一個句型對應的一棵語法樹，包括了該句型的所有推導。（錯） 答：一棵語法樹，只能對應一個推導，所以不能包括該句型的所有推導。 三、選擇題 1、在詞法分析中能識別出a，c，e。 a、關鍵字b、四元式c、運算符d、逆波蘭式e、常數(shù) 2、令Σ={a，b}，則Σ上所有以b開頭，后跟若干個ab的字的全體對應的正規(guī)式b，d。 a、b（ab）*b、b（ab）+c、（ba）*bd、（ba）+be、b（ba）* 3、詞法分析所依據(jù)的是b。 a、語義規(guī)則b、詞法規(guī)則c、語法規(guī)則d、等價變換規(guī)則 4、正規(guī)式V1和V2等價是指c。 a、V1和V2的狀態(tài)數(shù)相等b、V1和V2的有向弧條數(shù)相等 c、V1和V2所識別的語言集相等d、V1和V2狀態(tài)數(shù)和有向弧條數(shù)相等 5、 令Σ={a，b}，正規(guī)式abc代表的正規(guī)集b。 a、{ａ}b、｛ａ，ｂ，ｃ｝c、｛ａｂｃ｝d、｛ｂ，ｃ｝ 6、有限狀態(tài)自動機能識別 正規(guī)文法 。 三、簡答題 1、什么是掃描器？掃描器的功能是什么？掃描器就是詞法分析器，它接受輸入的源程序，對源程序進行詞法分析并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析使用。 2) DFA與NFA有何區(qū)別 ? 解答:DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以有若干個開始狀態(tài)，而DFA僅只有一個開始狀態(tài)。另一方面，DFA的映象M是從K∑到K，而NFA的映象M是從K∑到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。 3) 詞法分析器是用于做什么的？ 解答:詞法分析器是用于識別單詞的。 15)詞法分析的主要任務是什么？ 解答:詞法分析器的任務是對構成源程序的字符串從左到右逐個字符逐個字符地進行掃描，依次把它們識別為一個一個具有獨立意義的單詞，并確定其屬性，再轉(zhuǎn)換為長度統(tǒng)一的屬性字并輸出。 第3章 ：語法分析 6)句柄 答：句柄——給定句型中的最左簡單短語就是句柄。 7)句型 答：句型——設G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈V*),則稱x是文法的一個句型。 * 8)句子 答：句子——設G是一個給定的文法，S是文法的開始符號，如果S x（其中x∈VT*），則稱x是文法的一個句子。 9)非終結符 答：非終結符—出現(xiàn)在文法產(chǎn)生式的左部且能派生出符號或符號串的那些符號稱為非終結符號。 10)終結符 答：終結符——出現(xiàn)在文法產(chǎn)生式的右部且不能派生出符號或符號串的那些符號稱為終結符號。 11）屬性文法 答：一個屬性文法形式的定義為一個三元組AG，AG=（G，V，E）。 其中G為一個上下文無關文法；V為屬性的有窮集；E為一組語義規(guī)則。 二．簡答題： 1) 什么是句子？ 什么是語言? * 解答：句子——設G是一個給定的文法，S是文法的開始符號，如果S x（其中x∈VT*），則稱x是文法的一個句子。 語言——語言是句子的集合。 或——設G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)＝{x│Sx,x∈VT*} 。 2) 自頂向下的語法分析方法的基本思想是什么? 解答:從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導，試圖推導出文法的句子，使之與給定的輸入串匹配。 3) 自底向上的語法分析方法的基本思想是什么? 解答:從給定的輸入串（終結符串）開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的開始符號。 4) 一個上下文無關文法G包括哪四個組成部分？ 解答:一組非終結符號，一組終結符號，一個開始符號，以及一組產(chǎn)生式。 5) 在自底向上的語法分析方法中，分析的關鍵是什么？ 解答:關鍵是尋找句柄。 6) 在自頂向下的語法分析方法中，分析的關鍵是什么？ 解答:關鍵是選擇候選式。 7) 若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是可枚舉的嗎？ 解答: 它所產(chǎn)生的語言的句子不是可枚舉的，而是無窮多個。 17）文法G所描述的語言是什么的集合？ 解答:是由文法的開始符號推出的所有終結符串的集合?；蛘f是句子的集合。 18）喬姆斯基把文法分為四種類型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文無關文法。 25）語法分析的任務是什么？ 解答:語法分析的任務是識別給定的終結符串是否為給定文法的句子。 37）寫一個文法，使其語言是無符號二進制實數(shù)（不含指數(shù)）。 解答:文法G(N)： 　　　　　 　N→L.L|L 　　　　　 　L→LB|B 　　　　　 　B→0|1 28）在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是什么集合？ 解答: 均是終結符集。 34）說明下面文法G[S]是二義性文法：S→SaS|SbS|cSd|eS|f 解答:fafbf是文法G[S]的一個句子，并且有兩個不同的最右推導。 （1）S => SaS => SaSbS => SaSbf=> Safbf=> fafbf （2）S => SbS => Sbf=> SaSbf => Safbf=> fafbf 因此說明此文法有二義性。 27）文法等價的定義是什么？ 解答: 設G1和G2是給定的文法，如果有L（G1）= L（G2），則稱G1與G2等價。 5-19.自底向上分析法的原理是什么？ 答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復查找當前句型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把句柄歸約成相應的非終極符來一步步地進行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。 5-20.簡單優(yōu)先方法基本思想是什么？ 答：簡單優(yōu)先方法基本思想是首先規(guī)定文法符號之間的優(yōu)先關系和結合性質(zhì)，然后在利用這種關系，通過比較兩個相鄰的符號之間的優(yōu)先順序來確定句型的“句柄”并進行歸約。 5-21.三種優(yōu)先關系的定義是什么？ 答：三種優(yōu)先關系的定義是： 1. si（1）sisj sj 當且僅當存在形如下面的產(chǎn)生式U→…SiSj… 2. sisj 當且僅當存在形如下面的產(chǎn)生式U→…SiW…的生產(chǎn)式，且有 WSj 3. sisj 當且僅當存在形如下面的產(chǎn)生式U→…VW…的生產(chǎn)式,且有 VSi和WSj 5-22.如何確定簡單優(yōu)先文法的句柄？ 答：設S1S2…Sn是簡單優(yōu)先文法的規(guī)范句型，其子串SiSi+1…Sj是滿足下列條件的最左子串： Si-1 Si Si Si+1…… Sj-1 Sj Sj Sj+1 則SiSi+1…Sj定是S1S2…Sn的句柄。 2-01.所謂最右推導是指： 任何一步αβ都是對α中最右非終結符進行替換的 。 2-02.一個上下文無關文法所含四個組成部分是 一組終結符號、一組非終結符號、一個開始符號、一組產(chǎn)生式 。 2-03.產(chǎn)生式是用于定義 語法成分 的一種書寫規(guī)則。 2-04.設G[S]是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)＝{x│Sx,x∈VT*} 。 2-05.設G是一個給定的文法，S是文法的開始符號，如果Sx（其中x∈V*），則稱x是文法的一個句型 。 2-06.設G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈VT*),則稱x是文法的一個句子。 1、自上而下語法分析方法的基本思想是：從文法的開始符號出發(fā)。不斷建立直接推導，試圖構造一個推導序列，最終由它推導出與輸入符號串相同的符號串。 2、自上而下語法分析方法會遇到的主要問題有回溯和左遞歸。 3、在自上而下語法分析中，應先消除文法的間接左遞歸，再消除文法的直接左遞歸。 4、在語法分析中，最常見的兩種方法是自上而下分析法，另一種是自下而上分析法。 4-01.語法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。 4-02.語法分析的任務是識別給定的終極符串是否為給定文法的句子。 4-03.遞歸下降法不允許任一非終極符是直接 左 遞歸的。 4-04.自頂向下的語法分析方法的關鍵是 如何選擇候選式 的問題。 4-05.遞歸下降分析法是自頂向上 分析方法。 4-06.自頂向下的語法分析方法的基本思想是：從文法的 開始符號 開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導，試圖推導出文法的 句子 ，使之與給定的輸入串匹配。 5-01.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的 開始符號 。 5-03.簡單優(yōu)先方法每次歸約當前句型的 句柄 ，算符優(yōu)先方法每次歸約當前句型的 最左素短語 ，二者都是不斷移進輸入符號，直到符號棧頂出現(xiàn) 可歸約串 的尾，再向前找到 可歸約串 的頭，然后歸約。 5-04.在LR（0）分析法的名稱中，L的含義是 自左向右的掃描輸入串 ，R的含義是 最左歸約 ，0 的含義是 每步最多向前檢查0個輸入符號 。 5-05.在SLR（1）分析法的名稱中，S的含義是 簡單的 。 ⑴對于一文法，如果能夠構造一張分析表，使得它的每一個入口均是唯一確定的，則稱該文法為LR文法。 ⑵自下而上語法分析法的基本思想是：從待輸入的符號串開始，利用文法的產(chǎn)生式步步向上進行直接歸約，試圖歸約到文法的開始符號（識別符號）。 ⑶字的活前綴是指該字的任意首部。 ⑷活前綴是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何句型。 ⑶對LR分析表的構造，有可能存在C、E動作沖突。 A、歸約B、移進C、移進-歸約D、移進-移進E、歸約-歸約 ⑷自上而下的語法分析方法A、C、D、E有。 A、算符優(yōu)先分析法B、LL（1）分析法C、LR（0）分析法D、SLR（1）分析法E、LALR（1）分析法 ⑸每一項ACTION[s，a]所規(guī)定的動作包括A、C、D、E。 A、歸約B、比較C、移進D、接受E、報錯 2-07．文法G所描述的語言是 C 的集合。 A.文法G的字母表V中所有符號組成的符號串 B.文法G的字母表V的閉包V*中的所有符號串 C.由文法的開始符號推出的所有終極符串 D.由文法的開始符號推出的所有符號串 2-08．喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B 。 A. 短語文法（0型） B.正則文法 C.上下文有關文法（1型） D.上下文無關文法（2型） 5-06．在自底向上的語法分析方法中，分析的關鍵是 D 。 A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式 5-07. 在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。 A.句柄 B. 前綴 C. 活前綴 D. LR(0)項目 2-10．一個句型中的最左 B 稱為該句型的句柄。 可選項有： A. 短語 B. 簡單短語 C. 素短語 D. 終結符號 2-11．設G是一個給定的文法，S是文法的開始符號，如果Sx(其中x∈V*),則稱x是文法G的一個 B 。 A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式 2-15．文法的二義性和語言的二義性是兩個 A 的概念。 A 不同 B 相同 C 無法判斷 D 不存在 3-02．詞法分析器用于識別 C 。 A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式 4-07.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。 A. 非終極符集 B.終極符集 C. 字母表 D. 狀態(tài)集 4-08.編譯程序中語法分析器接收以 A 為單位的輸入。 A. 單詞 B. 表達式 C. 產(chǎn)生式 D. 句子 2-13.文法G[E]： E→T∣E＋T T→F∣T﹡F F→a∣（E） 該文法句型E＋F﹡(E＋T)的簡單短語是下列符號串中的 B 。 ①（E＋T） ②E＋T ③F ④ F﹡(E＋T) 可選項有： A) ①和③ B) ②和③ C) ③和④ D) ③ 2-14．若一個文法是遞歸的，則它所產(chǎn)生的語言的句子 A 。 A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量 2-15.正則文法其產(chǎn)生式為Aa，ABb, A,B∈VN，a、b∈VT。 √） 4-09.每個文法都能改寫為LL(1)文法。 （） 4-10.遞歸下降法允許任一非終極符是直接左遞歸的。（√） 5-08.算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。（√） 5-12.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（） 5-13.一個句型的句柄一定是文法某產(chǎn)生式的右部。（√） 5-09.自底而上語法分析方法的主要問題是候選式的選擇。（） 5-10.LR法是自頂向下語法分析方法。（） 5-11.簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 （） 三．應用題 1）消除下列文法G[A]的左遞歸。 E→E-T∣T T→T/F∣F F→( E )∣i 解答：消除文法G[E]的左遞歸后得到： E→TE′ E’→-T E′∣ε T→FT′ T’→/FT′∣ε F→( E )∣i 2） 消除下列文法G[A]的左遞歸。 A→AaB∣B B→BbC∣C C→eD∣D D→(A)∣d 解答：消除文法G[A]的左遞歸后得到： A →BAˊ Aˊ→aBAˊ∣ε B →CBˊ Bˊ→bcBˊ∣ε C→eD∣D D→(A)∣d 四．設計題 （1）給定文法G[S′] 及相應翻譯方案為：1．S→S {print:“a”} 2．S→r D {print:“b”} 3．D→D，i {print:“c”} 4．D→i {print:“d”} a. 按chomsky分類法，文法G屬于哪一型文法？ b. 符號串ri,i,i是不是該文法的一個句型，請證實。 c. 若是句型，寫出該句型的所有短語、簡單短語，以及句柄。 解答： a．文法G屬于2型(上下文無關)文法。 b．符號串r i,i,i是該文法的一個句型。 證：SSrDrD，i rD，i，i r i，i，i，得證。 或證：構造語法樹見圖4，可知符號串r i,i,i是該文法的一個句型。 c．句型r i,i,i的短語有：①r i,i,i；② i,i,i；③i,i；④ 第一個i 簡單短語有：第一個i 句柄有：第一個i 2-20.已知文法G[E]為： E→T|E+T|E-T T→F|T*F|T/F F→（E）|i ① 該文法的開始符號（識別符號）是什么？ ②請給出該文法的終結符號集合VT和非終結符號集合VN。 ③ 找出句型T+T*F+i的所有短語、簡單短語和句柄。 解：① 該文法的開始符號（識別符號）是E。 ②該文法的終結符號集合VT={+、-、*、/、（、）、i}。 非終結符號集合VN={E、T、F}。 ③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i; 簡單短語為i、T*F、第一個T;句柄為第一個T。 4-14.在LL(1)分析法中,LL分別代表什么含義? 答:第一個L代表從左到右的掃描，第二個L代表每次進行最左推導。 4-15.自頂向下分析思想是什么？ 答：從開始符出發(fā)導出句型并一個符號一個符號地與給定終結符串進行匹配。如果全部匹配成功，則表示開始符號可推導出給定的終結符串。因此判定給定終結符號串是正確句子。 4-16.自頂向下的缺點是什么？ 答：在推導過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點是不斷地回溯，大大影響速度。 4-17.LL（1）文法的定義是什么？ 答：一個上下文無關文法是LL(1)文法的充分必要條件是每個非終結符A的兩個不同產(chǎn)生式，A→α,A→β；滿足SELECT(A →α)∩SELECT(A →β)=Ф。其中，α、β不能同時ε。 4-18.什么是文法的左遞歸？ 答：一個文法含有下列形式的產(chǎn)生式之一時： 1)A→Aβ，A∈VN，β∈V* 2)A→Bβ，B→Aα，A、B∈VN，α、β∈V* 則稱該文法是左遞歸的。 4-19.遞歸下降法的主要思想是什么？ 答：對每個非終結符按其產(chǎn)生式結構寫出相應語法分析子程序。因為文法遞歸相應子程序也遞歸，子程序的結構與產(chǎn)生式結構幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。