《編譯原理》第三版期末復(fù)習(xí).doc

《《編譯原理》第三版期末復(fù)習(xí).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《編譯原理》第三版期末復(fù)習(xí).doc（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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