《編譯原理》期中及期末習(xí)題

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

1、《編譯原理》期中及期末習(xí)題 第一章高級(jí)語言與編譯程序概述 典型例題: 單項(xiàng)選擇題 1.1.1．將編譯程序分成若干個(gè)“遍”是為了___。 a.提高程序的執(zhí)行效率 b.使程序的結(jié)構(gòu)更加清晰 c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率 1.1.2．構(gòu)造編譯程序應(yīng)掌握____。（陜西省2000年自考題） a.源程序 b.目標(biāo)語言 c.編譯方法 d.以上三項(xiàng)都是 1.1.3．變量應(yīng)當(dāng)＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持有左值也不持有右值 1.1.4．編譯程序絕大多數(shù)時(shí)間花在____上。（

2、陜西省1998年自考題） a.出錯(cuò)處理 b.詞法分析 c.目標(biāo)代碼生成 d.管理表格 1.1.5．____不可能是目標(biāo)代碼。( 陜西省1997年自考題) a.匯編指令代碼 b.可重定位指令代碼 c.絕對(duì)指令代碼 d.中間代碼 1.1.6．?dāng)?shù)組A[1…20,1…10]的首地址偏移量為0，按列存儲(chǔ)，每個(gè)元素占一個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，則A[i,ｊ］的偏移地址為____。 a.(i-1)X10+（j-1） b.(i-1)X20+(j-1) c. (i-1)＋(j-1)X10 d.(i-1)+(j-1)X20 1.1.7.使用____可以定義一個(gè)程序的意義。 a.語義

3、規(guī)則 b.詞法規(guī)則 c.產(chǎn)生規(guī)則 d.左結(jié)合規(guī)則 1.1.8．表達(dá)式X:=5中，變量x____。 a.只有左值 b.只有右值 c.既有左值又有右值 d.沒有左值也沒有右值 1.1.9．詞法分析器的輸入是__。 a.單詞符號(hào) b.源程序 c.語法單位 d.目標(biāo)程序 1.1.10．中間代碼生成時(shí)所遵循的是＿。 a.語法規(guī)則 b.詞法規(guī)則 c.語義規(guī)則 d.等價(jià)變換規(guī)則 1.1.11．編譯程序是對(duì)__。 a.匯編程序的翻譯 b.高級(jí)語言程序的解釋執(zhí)行 c.機(jī)器語言的執(zhí)行 d.高級(jí)語言的翻譯 1.1.12．詞法分析應(yīng)遵循＿。（陜西省2000年自考題）

4、a.語義規(guī)則 b.語法規(guī)則 c.構(gòu)詞規(guī)則 d.等價(jià)變換規(guī)則 多項(xiàng)選擇題： 1.2.1 編譯程序各階段的工作都涉及到___。（陜西省1999年自考題） a.語法分析 b.表格管理 c.出錯(cuò)處理 d.語義分析 e.詞法分析 1.2.2下列各項(xiàng)中，____與數(shù)組元素的地址有關(guān)。（陜西省1999年自考題） a.數(shù)組第一個(gè)元素的存儲(chǔ)地址 b.數(shù)組的存儲(chǔ)方式 c.數(shù)組的維數(shù) d.內(nèi)存的編址方式 e.編譯程序 1.2.3 編譯程序工作時(shí),通常有__階段。（陜西省1998年自考題） a.詞法分析 b.語法分析 c.中間代碼生成 d.語義檢查 e.目標(biāo)代碼生成 1.

5、2.4 過程調(diào)用的參數(shù)傳遞方式有__。 a傳名 b.傳值 c.傳參數(shù) d.傳地址 e.傳結(jié)果 1.2.5 編譯過程中所遵循的規(guī)則有____。 a.等價(jià)變換規(guī)則 b.短語規(guī)則 c.構(gòu)詞規(guī)則 d. 語義規(guī)則 e.語法規(guī)則 填空題： 1.3.1 解釋程序和編譯程序的區(qū)別在于＿。 1.3.2 編譯過程通?？煞譃?個(gè)階段，分別是＿、語法分析、＿、代碼優(yōu)化和目 標(biāo)代碼生成。（陜西省1999年自考題） 1.3.3 編譯程序工作過程中，第一階段輸入是＿，最后階段的輸出為一程序。 （陜西省1997年自考題）1.3.4 靜態(tài)數(shù)組元素地址的計(jì)算公式由兩部分確定，一部分是＿，它在＿時(shí)確定

6、； 另一部分是＿，它在＿時(shí)確定。 1.3.5 把語法范疇翻譯成中間代碼所依據(jù)的是語言的＿。（陜西省2000年自考題） 1.3.6 目標(biāo)代碼可以是＿指令代碼或＿指令代碼或絕對(duì)機(jī)器指令代碼。 （陜西省2000年自考題）1.3.7 編譯程序是指能將____程序翻譯成____程序的程序。 1.3.8 數(shù)組元素的地址由___和___組成，其中＿中的a和c在翻譯數(shù)組說明語句時(shí)填入到數(shù)組的＿中。 1.3.9 過程調(diào)用時(shí)，參數(shù)傳遞的方式有______、______、_____。 1.3.10 詞法分析所遵循的是語言的______，而中間代碼生成所遵循的是語言的_____。 （陜西省1997年自

7、考題）1.3.11 數(shù)組元素的地址計(jì)算與數(shù)組的_____數(shù)及____方式有關(guān)，也與數(shù)組的類型及機(jī)器對(duì)存儲(chǔ)器的編址方式有關(guān)。（陜西省2000年自考題） 判斷題： 1.4.1．賦值號(hào)左邊的變量只持有左值，不持有右值。（） 1.4.2．二維數(shù)組a[3…15,5…20]按行存放，并且每個(gè)元素占用一個(gè)存儲(chǔ)單元，則數(shù)組元素a[i ,j]的地址為base-85+i X 16+j (base是數(shù)組a存放的起始地址）。（） 1.4.3．變量的名字用標(biāo)識(shí)符來表示，同時(shí)名字代表一定的存儲(chǔ)單元，有屬性、值、作用域等特性。（陜西省1997年自考題）（） 1.4.4．指示器變量的右值只持有右值，沒有左值。（陜西

8、省2000年自考題）（） 1.4.5．般而言，中間代碼是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)。（） 綜合題 1.5.1 計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序有哪些途徑？它們之間的主要區(qū)別是什么？ 1.5.2 何謂“標(biāo)識(shí)符”，何謂“名字”，兩者的區(qū)別是什么？ 1.5.3 簡(jiǎn)述在過程調(diào)用中，形參和實(shí)參間常見的各種信息傳遞方式（即形實(shí)結(jié)合方式）的含義。 1.5.4 畫出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。 1.5.5 對(duì)于下面的程序： PROCEDURE P(x,y,z)； BEGIN｛P｝ y：=y+l； Z：=Z+X END；｛P｝ BEGIN { main} A：=2；

9、 B：=3； P（A+B,A,A）； Print A END．{ main} 若參數(shù)傳遞的辦法分別為（1)傳名，(2）傳地址，(3）傳結(jié)果，(4)傳值；試問，程序執(zhí)行時(shí)所輸出的A值分別是什么？ 1.5.6 對(duì)于下面的程序： PROGRAM main； a:integer； PROCEDURE test(x：:integer)； temp:integer； BEGIN {test} x：=a+l； Temp：=a+2 x：=temp END；{ test} BEGIN a:=2； test(a)； print(a) END． 分別給出參數(shù)傳遞為傳地址、傳結(jié)

10、果、傳值和傳名時(shí)a的輸出結(jié)果。 1.5.7 三維數(shù)組a[2:5,-2:2,5:7]首址為100,每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，求數(shù)組元素a[3,1,6] 的地址。 1.5.8 什么叫自展？什么叫交叉編譯？ 1.5.9 試分析編譯程序是否分遍應(yīng)考慮的因素及多遍掃描編譯程序的優(yōu)缺點(diǎn)。 1.5.10 請(qǐng)畫出編譯程序的總框。如果你是一個(gè)編譯程序的總設(shè)計(jì)師，應(yīng)當(dāng)考慮哪些問題？ （國(guó)防科大2000年研究生試題） 1.5.11 對(duì)于下面說明語句所定義的數(shù)組A array A[-2:3,-5:5] 假定數(shù)組按行存放，存儲(chǔ)器按字節(jié)編址，每四個(gè)字節(jié)為一機(jī)器字，令A(yù)的首地址為1000，問A[i+3,

11、j+2]的首地址是什么？（寫出步驟）（同濟(jì)大學(xué)1998年研究生試題） 1.5.12 數(shù)組var a：array[1..5,-3..6] of integer；按列存放，其首址100,每個(gè)整數(shù)占4個(gè)字節(jié)，內(nèi)存按字節(jié)編址，則數(shù)組元素a[4,3]的地址是什么？（上海交大1997年研究生試題） 1.5.13 對(duì)于下面的程序段 … procedure P(x,y,z) begin y：=y*2；; z：=x+z； end； begin a：=5； b：=2； p(a*b,a,a)； print(a) end． 若參數(shù)傳遞的方法分別為（1)傳值、(2)傳地址、(3)傳名，試問

12、程序執(zhí)行所輸出的結(jié) 果分別是什么？ 1.5.14 有一段程序?yàn)椋? PROGRAM sample; x：integer； PROCEDURE sun(m：integer)； BEGIN｛sun｝ M：=11；x：=m+ END；｛sun｝ BEGIN X：=100； sun（x）； write（x） END； 請(qǐng)用（1）傳地址；（2）傳值；（3）傳結(jié)果；(4)傳名的參數(shù)傳遞方式，給出程序的運(yùn)行結(jié)果。 1.5.15有一程序如下： PROGRAM ex； a：integer； PROCEDURE PP(x：integer)； BEGIN｛PP｝ a：=5；x：

13、=a+1 END；｛PP｝ BEGIN a：=2； PP（a）； write（a） END ． 用（1)傳地址；(2)傳值；（3)傳結(jié)果；(4)傳名等4種參數(shù)傳遞方式，；試寫出程序的 運(yùn)行結(jié)果。 第二章詞法分析 典型例題: 單項(xiàng)選擇題 1.1.1．詞法分析所依據(jù)的是____。 a.語義規(guī)則 b.構(gòu)詞規(guī)則 c.語法規(guī)則 d.等價(jià)變換規(guī)則 1.1.2．詞法分析器的輸出結(jié)果是____。 a.單詞的種別編碼 b.單詞在符號(hào)表中的位置 c.單詞的種別編碼和自身值 d.單詞自身值 1.1.3．正規(guī)式MI和M2等價(jià)是指____。 a. MI和M2的狀態(tài)數(shù)相等

14、b.Ml和M2的有向弧條數(shù)相等。 C.M1和M2所識(shí)別的語言集相等 d. Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等 1.1.4．狀態(tài)轉(zhuǎn)換圖（見圖 2.5），接收的字集為： 圖2.5 a.以0開頭的二進(jìn)制數(shù)組成的集合 b.以0結(jié)尾的二進(jìn)制數(shù)組成的集合 c.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 d.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 1.1.5．詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此___。 a.詞法分析器應(yīng)作為獨(dú)立的一遍 b.詞法分析器作為子程序較好 c.詞法分析器分解為多個(gè)過程，由語法分析器選擇使用 d.詞法分析器并不作為一個(gè)獨(dú)立的階段 1.1.6．詞法分析器

15、的輸入是—。 a.單詞符號(hào)串 b.源程序 c.語法單位 d.目標(biāo)程序 1.1.7.如果L(M)=L(M），則M與M__。（陜西省1999年自考題） a. 等價(jià)b．M與M都是二義的 c. M與M都是無二義的 d. 他們的狀態(tài)數(shù)相等 1.1.8．圖 2.56所示的狀態(tài)轉(zhuǎn)換圖接受的字集所對(duì)應(yīng)的正規(guī)式為＿。（陜西省1997年自考題） a. a*b*(aa|bb)a*b* b. (a|b)*(aa|bb)(a|b) c. (a*|b*)(aa|bb)(a*|b*) d. (a*|b*)aa(a*|b*)|(a*|b*)bb(a*|b*) 圖2.56 狀態(tài)轉(zhuǎn)換圖 多項(xiàng)選擇題

16、： 1.2.1在詞法分析中，能識(shí)別出＿。（陜西省1998年自考題） a.基本字 b.四元式 c.運(yùn)算符 d.逆波蘭式 e..常數(shù) 1.2.2令∑={a,b}，則∑上所有以b開頭，后跟若干個(gè)ab的字的全體對(duì)應(yīng)的正規(guī)式為＿。 a．b(ab)* b.b(ab) c.(ba)* b d.(ba)+b e. b(alb)* 1.2.3設(shè)∑={0,1}，則∑上字的全體可用正規(guī)式_____表示。 a.(1|0)* b.(1*|0*)* c.(1|0)+ d.(1*0*)* e.(10)* 填空題： 1.3.1 確定有限自動(dòng)機(jī)DFA是_______的一個(gè)特例。 1.3.2

17、 若二個(gè)正規(guī)式所表示的______相同，則認(rèn)為二者是等價(jià)的。（陜西省1997年自考題）1.3.3 一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由______所______（陜西省1997年自考題） 判斷題： 1.4.1．一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。（） 1.4.2．設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)|L(s) （） 1.4.3．自動(dòng)機(jī)M和M的狀態(tài)數(shù)不同，則二者必不等價(jià)。（）1.4.4．確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（） 1.4.5．對(duì)任意一個(gè)右線性文法G，都存在一個(gè)NFA M，滿足L(G)=L(M)。（）1.4.6 對(duì)任意一個(gè)右線性文法G,都存

18、在一個(gè)DFA M,滿足L(G}=L(M) 。（）1.4.7 對(duì)任何正則表達(dá)式e,都存在一個(gè)NFA M,滿足L(G)=L(e) 。（） 1.4.8 對(duì)任何正則表達(dá)式e,都存在一個(gè)DFA M,滿足L(G)=L(e)。（） 1.4.9 兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。（） 1.4.10 詞法分析作為單獨(dú)的一遍來處理較好。（） 1.4.11 一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（） 綜合題 1.5.1 什么是掃描器？掃描器的功能是什么？ 1.5.2 給出字母表∑上的正規(guī)式及其所描述的正規(guī)集的遞歸定義。 1.5.3 正規(guī)文法、正規(guī)式、確定

19、有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)在接收語言能力上是否相互等價(jià)？ 1.5.4 已知Pascal語言的實(shí)數(shù)表示規(guī)則如下： （1)實(shí)數(shù)十進(jìn)制表示 (a)實(shí)型數(shù)的小數(shù)點(diǎn)前后必須出現(xiàn)數(shù)字： (b）必須出現(xiàn)小數(shù)點(diǎn)。 （2）實(shí)數(shù)科學(xué)表示（指數(shù)形式） (a)字母e表示以十為底的指數(shù)； (b）字母e前必須出現(xiàn)實(shí)數(shù)或者整數(shù)； （c）字母e后必須出現(xiàn)整數(shù)，這個(gè)整數(shù)表示實(shí)型數(shù)的指數(shù)部分。 試畫出該實(shí)數(shù)對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖。 1.5.5 設(shè)M= f(x,a)=｛x,y｝f｛a,b｝=｛Y) f(Y,a)=φf｛y,b｝＝｛x,y｝ 試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M`。 1.5.6 (1）對(duì)給定正規(guī)式b*(

20、d|ad) (b|ab)＋，構(gòu)造其NFA M；（陜西省1997年自考題）（2) 對(duì)給定正規(guī)式(a|b)*a(a|b)，構(gòu)造其DFA M。（中科院計(jì)算所1997年研究生試題） 1.5.7 構(gòu)造一個(gè)DFA,它接收∑=｛a,b｝上的所有滿足下述條件的字符串，即該字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。 1.5.8 有窮狀態(tài)自動(dòng)機(jī)M接受字母表∑＝{0，1｝上所有滿足下述條件的串：串中至少包含兩個(gè)連 續(xù)的0或兩個(gè)連續(xù)的1。 （1)請(qǐng)給出與M等價(jià)的正規(guī)（則）式。 （2）將M最小化。 （3）構(gòu)造與M等價(jià)的正規(guī)文法。 1.5.9 構(gòu)造正規(guī)表達(dá)式((a|b)*|bb)*的ＤＦＡ（要求寫出步驟

21、）。 1.5.10 設(shè)有L(G)={a2n+1b2m a2p+1|n≥0,p≥0,m≥1} （1)給出描述該語言的正規(guī)表達(dá)式。 (2)構(gòu)造識(shí)別該語言的確定的有窮自動(dòng)機(jī)（可直接用狀態(tài)圖形式給出）。 1.5.11 請(qǐng)寫出在∑＝(a,b)上，不是a開頭的，但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)狀態(tài)最少的DFA。 1.5.12 有語言L={w|w∈(0,1）＋，并且w中至少有兩個(gè)1，又在任何兩個(gè)1之間有偶數(shù)個(gè)0，試構(gòu)造接受該語言的確定有限狀態(tài)自動(dòng)機(jī)（DFA）。 1.5.13 已知正規(guī)式(1)((a|b)*|aa)*b和正規(guī)式(2)(a|b)*b。 (1)試用有限自動(dòng)機(jī)的等價(jià)

22、性證明正規(guī)式(1)和(2)是等價(jià)的。 (2）給出相應(yīng)的正規(guī)文法。 1.5.14 某操作系統(tǒng)下合法的文件名為device:name.extension,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，長(zhǎng)度不限，但至少為1，畫出識(shí)別這種文件名的確定有限自動(dòng)機(jī)。 1.5.15 Pascal語言無符號(hào)數(shù)的正規(guī)定義如下： Num→digit+(.digit+)?(E(+|-)?digit+)? 其中digit表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無符號(hào)數(shù)的確定有限自動(dòng)機(jī)。 1.5.16 在C語言中無符號(hào)整數(shù)可用十進(jìn)制（

23、非0打頭）、八進(jìn)制（0打頭）和十六進(jìn)(0X 打頭）表示，試寫出其相應(yīng)的文法和識(shí)別無符號(hào)數(shù)的DFA(假定位數(shù)不限)。 1.5.17 下列程序段若以B表示循環(huán)體，A表示初始化，I表示增量，T表示測(cè)試。 I:=1； while Ibegin sun:=sun+a[I]; I:=I+l End 請(qǐng)用正規(guī)表達(dá)式表示這個(gè)程序段可能的執(zhí)行序列。 1.5.18 在操作系統(tǒng)的進(jìn)程管理中，進(jìn)程的狀態(tài)轉(zhuǎn)換如圖 2.50所示。假設(shè)現(xiàn)有兩個(gè)進(jìn)程Pi 和CPU每次只能運(yùn)行一個(gè)進(jìn)程。當(dāng)P1、P2都處于就緒狀態(tài)時(shí)為初態(tài)，當(dāng)P1、P2都處于睡眠狀態(tài)時(shí)為終態(tài)。請(qǐng)用一個(gè)有限自動(dòng)機(jī)來描述這個(gè)進(jìn)程管理系統(tǒng)。 圖2.

24、50 進(jìn)程狀態(tài)轉(zhuǎn)換圖 1.5.19 有一臺(tái)自動(dòng)售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機(jī)器中 投放≥3分的硬幣，便可得到一塊糖（注意：只給一塊并且不找錢）。 (1)寫出售貨機(jī)售糖的正規(guī)表達(dá)式。 (2)構(gòu)造識(shí)別上述正規(guī)式的最簡(jiǎn)DFA。 1.5.20 證明：一不含無用狀態(tài)的有限自動(dòng)機(jī)M的接收集L(M)是無限集，當(dāng)且僅當(dāng)M相應(yīng)的狀態(tài)轉(zhuǎn)換圖中含有回路。 1.5.21 假定A和B都是正規(guī)集，請(qǐng)用正規(guī)集與有限自動(dòng)機(jī)的等價(jià)性說明A∪B也是正規(guī)的。 1.5.22 下面的正規(guī)式等價(jià)嗎？為什么？ (1)(a|b)* (2) (a*|b*)* (3)((ε|a)b*)* 1.5

25、.23 （電子科大1996年研究生試題） 構(gòu)造識(shí)別下列單詞符號(hào)的狀態(tài)轉(zhuǎn)換圖： begin end標(biāo)識(shí)符正整數(shù)＋－***，．∷＝ 1.5.24 （清華大學(xué)1998年研究生試題） 請(qǐng)將圖2.57所示的有窮自動(dòng)機(jī)M1最小化。 圖2.57 有窮自動(dòng)機(jī)M1 1.5.25 （清華大學(xué)1998年研究生試題） 將有窮自動(dòng)機(jī)M2確定化 M2=({U,V,W,X}，10,1｝,f,{U}，{W}） 其中：f(U,0）＝φf(U,1）＝｛V,X} f(V,0)={V} f(V,l）＝tvlwl f(W,0)={X｝f(W,1)＝{W} f(X,0)={X} f(X,1）＝{X} 1.5.2

26、6 （清華大學(xué)1998年研究生試題） 將圖2.58所示的DFA最小化。 圖2.58 DFA 1.5.27 （中科院計(jì)算所1997年研究生試題） 為正規(guī)式(a|b) *a(a|b)構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)。 1.5.28 （南開大學(xué)1998年研究生試題） 寫出正規(guī)式(alb) *(aa|bb)(a|b)*的DFA。 1.5.29 （復(fù)旦大學(xué)1999年研究生試題） 將圖2.59所示的非確定有限自動(dòng)機(jī)(NFA)變換成等價(jià)的確定有限自動(dòng)機(jī)(DFA)。 圖2.59 NFA 其中，X為初態(tài)，Y為終態(tài)。 1.5.30 （上海交大1997年研究生試題） 請(qǐng)構(gòu)造與正規(guī)式R=(a*|b*)

27、b(ba)*等價(jià)且狀態(tài)最少的DFA。 1.5.31 （國(guó)防科大1999年研究生試題） 構(gòu)造一個(gè)確定的有限自動(dòng)機(jī)DFA,它接受∑＝{0,1}上的所有不帶前導(dǎo)0的二進(jìn)制區(qū)數(shù)。 1.5.32 （國(guó)防科大2000年研究生試題） 已知DFA M如圖2.60所示。 圖2.60 DFA M 請(qǐng)給出M所識(shí)別的字的全體L(M)。 1.5.33 （華中理工2001年研究生試題） 構(gòu)造一個(gè)確定的有窮自動(dòng)機(jī)DFA M,它識(shí)別∑={a,b}上所有滿足如下條件的字符串：字 符串由a, b組成，且其中b的個(gè)數(shù)為3k (k≥0)。 1.5.34 （華中理工2001年研究生試題） 正規(guī)式(ab）*a與正規(guī)

28、式a(ba) *是否等價(jià)？請(qǐng)說明理由。 1.5.35 DFA與NFA有何區(qū)別 5※第三章語法分析 典型例題: 單項(xiàng)選擇題 3.1.1. 文法G: S-xSxly所識(shí)別的語言是_____（陜西省1997年自考題） a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx* 3.1.2. 文法G描述的語言L(G)是指_____。 a. L(G)=｛α|S=>α，α∈VT*｝ b. L(G)={ α|SA=>α,α ∈VT*｝ c．L(G)={ α|S=>α，α∈(VT∪VN)*｝d. L(G)=｛α|S=>α,α∈(VT∪VN)*｝ 3.1.3. 有

29、限狀態(tài)自動(dòng)機(jī)能識(shí)別＿。 a.上下文無關(guān)文法 b.上下文有關(guān)文法 c.正規(guī)文法 d.短語文法 3.1. 4. 設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對(duì)a, b有以下關(guān)系成立____。 a.若f(a)>g(b)，則a>b b.若f(a)c.a~b都不一定成立 d. a~b一定成立 3.1.5．茹果文法G是無二義的，則它的任何句子α_＿。（西電1999年研究生試題） a.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 c.最左推導(dǎo)和最右推導(dǎo)必定相同 d.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 3.1. 6.由文法的開始符經(jīng)。步

30、或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是____。 （陜西省2000年自考題） a．短語 b.句柄 c.句型 d.句子 3.1.7．文法G：E-E+TIT T-T*P|P P-(E)|I 則句型P+T+i的句柄和最左素短語分別為__＿。 a. P+T和i b. P和P+T c. i和P+T+i d. P和P 3.1.8．設(shè)文法為：S--SA|A A→a|b 則對(duì)句子aba，下面____是規(guī)范推導(dǎo)． a. S=>SA=>SAA=>AAA=>aAA=>abA=>aba b. S=>SA=>SAA=>AAA=>AAa=>Aba=>aba c. S=>SA=>SAA=>SAa=>

31、Sba=>Aba=>aba d. S=>SA=>Sa=>Sba=>Aba=>aba 3.1.9.文法G: S→b|∧|(T) T-T,SIS 則FIRSTVT(T)=____。 a.｛b，∧，（｝ b.｛b，∧，）｝ c.｛b,∧，（，,｝ d.{b, ∧，），，｝ 3.1.10．產(chǎn)生正規(guī)語言的文法為____＿。 a. 0型 b. 1型 c. 2型 d. 3型 3.1.11．任何算符優(yōu)先文法—優(yōu)先函數(shù)。 a.有一個(gè) b.沒有 c.有若干個(gè) d.可能有若干個(gè) 3.1.12.采用自上而下分析，必須____＿。 a.消除左遞歸 b.消除右遞歸 c.消除回溯

32、． d.提取公共左因子 3.1.13．設(shè)a, b, c是文法的終結(jié)符，且滿足優(yōu)先關(guān)系a=b和b=c，則_____＿。 a.必有a=ｂb．必有c=a c.必有b=a d. a~c都不一定成立 3.1.1 4.在規(guī)范歸約中，用___＿來刻畫可歸約串。（陜西省1999年自考題） a.直接短語 b.句柄 c.最左素短語 d.素短語 3.1.15.有文法Ｇ：E→E*T|T T→T+i|i 句子1+2*8+6按該文法G歸約，其值為___＿。 a.23 b.42 c.30 d.17 3.1.16.規(guī)范歸約是指________。（陜西省９８年自考題） a.最左推導(dǎo)的逆過

33、程 b.最右推導(dǎo)的逆過程 c.規(guī)范推導(dǎo) d.最左歸約的逆過程 3.1.17.一文法G:S→S+T|T．（陜西省1998年自考題） T→T*P|P P→(S)|i 則句型P+T+i的短語有___＿。 a. i,P+T b. P,P+T,i,P+T+i c. P+T+i d. P,P+T,i 多項(xiàng)選擇題： 3.2.1.下面哪些說法是錯(cuò)誤的___＿。（陜西省1998年自考題） a.有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖 b.狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖 c．狀態(tài)轉(zhuǎn)換圖可以用DFA表示 d. DFA可以用狀態(tài)轉(zhuǎn)換圖表示 e.有向圖是一個(gè)DFA 3.2.2.對(duì)無二義性文法來說，一棵語法樹往

34、往代表了___＿。 a.多種推導(dǎo)過程 b.多種最左推導(dǎo)過程 c.一種最左推導(dǎo)過程 d.僅一種推導(dǎo)過程 e.一種最右推導(dǎo)過程 3.2.3．如果文法G存在一個(gè)句子，滿足下列條件___之一時(shí)，則稱該文法是二義文 法。 a.該句子的最左推導(dǎo)與最右推導(dǎo)相同 b、該句子有兩個(gè)不同的最左推導(dǎo) c.該句子有兩個(gè)不同的最右推導(dǎo) d,該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個(gè) 3.2. 4.語法分析時(shí)通過___＿操作使用符號(hào)棧。（陜西省2000年自考題） a. 移進(jìn) b. 歸約 c. 比較 d. 接受 e. 出錯(cuò)處理 3.2.5.算符優(yōu)先文法與算符優(yōu)先函數(shù)的關(guān)系描

35、述中，下列__＿正確。（陜西省1997 年自考題） a、一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng) b. 一個(gè)算符優(yōu)先文法可能存在多對(duì)算符優(yōu)先函數(shù)與之對(duì)應(yīng) c.一個(gè)算符優(yōu)先文法一定存在多對(duì)算符優(yōu)先函數(shù)與之對(duì)應(yīng) d.一個(gè)算符優(yōu)先文法一定存在算符優(yōu)先函數(shù)與之對(duì)應(yīng) e.一個(gè)算符優(yōu)先文法一定存在有限對(duì)算符優(yōu)先函數(shù)與之對(duì)應(yīng) 3.2.6.有一文法G: S--AB （陜西省1998年自考 題） A--aAb|ε B一cBd|ε 它不產(chǎn)生下面__＿集合。 a. {anbmcndm|n,m≥0} b. {anb"cmdm|n,m>0｝ c. {anbmcmdn|n,m≥0} d

36、. {anbncmdm|n,m≥0} e. {anbncndn|n≥0} 3.2.7．文法的無二義性是指_________。 a.文法中不存在句子有兩個(gè)不同的最左推導(dǎo) b.文法中不存在句子有兩個(gè)不同的最右推導(dǎo) c.文法中不存在句子有不同的推導(dǎo) d.文法中不存在句子有兩裸不同的語法樹 e.文法中不存在句子有不同的最左和最右推導(dǎo) 3.2.8. 文法G：S→aAcB|Bd A→AaB|c B→bScA|b 則句型aAcbBdcc的短語是_______。 a. Bd b. c c. bBdcc d. aAcbBdcc e. cbBd 3.2.9.在自下而上的語法分析中

37、，應(yīng)從_________開始分析。 a.句型 b.句子 c.以單詞為單位的程序 d.文法的開始符 e.句柄 3.2.10.對(duì)正規(guī)文法描述的語言，以下_____＿有能力描述它。 a. 0型文法 b. 1型文法 c.上下文無關(guān)文法 d.右線性文法 e.左線性文法 填空題： 3.3.1．規(guī)范歸約中的可歸約串是指______;算符優(yōu)先分析中的可歸約串是指 ______＿。 3.3.2.文法中的終結(jié)符和非終結(jié)符的交集是______。詞法分析器交給語法分析 器的文法符號(hào)一定是______，它一定只出現(xiàn)在產(chǎn)生式的_____＿部。 3.3.3.在自上而下的語法分析中，應(yīng)先消除

38、文法的_______遞歸，再消除文法的 _____遞歸。 3.3. 4.規(guī)范歸約是指在移進(jìn)過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)_____時(shí)，就用相應(yīng)產(chǎn)生式 的_____符號(hào)進(jìn)行替換。 3.3.5．當(dāng)文法非終結(jié)符的所有_____兩兩___＿時(shí)，該文法對(duì)應(yīng)的句子分析不含 回溯。 3.3.6.最左推導(dǎo)是指每次都對(duì)句型中的____＿非終結(jié)符進(jìn)行擴(kuò)展。（陜西省1998 年自考題） 3.3.7.在語法分析中，最常見的兩種方法一定是_____分析法，另一是______分 析法。（陜西省1998年自考題） 3.3.8.______語法分析的關(guān)鍵問題是精確定義可歸約串的概念。（陜西省2000 年自考題

39、） 3.3.9. Chomsky定義的4種形式語言文法為： ①______文法，又稱______文法；②_____文法，又稱_____文法； ③______文法，又稱______文法；④______文法，又稱_____＿文法。 （中國(guó)科技大學(xué)1999年研究生試題） 3.3.10. LL(K)文法中，第一個(gè)L表示_____＿，第二個(gè)L表示_____＿，K表示 _____，通常情況下K_____。（西安電子科大2000年研究生試題） 3.3.11．采用_______＿語法分析時(shí)，必須消除文法的左遞歸。 3.3.12．_____樹代表推導(dǎo)過程，______＿樹代表歸約過程。 3.3

40、.13.自下而上分析法采用____＿、歸約、錯(cuò)誤處理、_____＿等四種操作。 （陜西省1999年自考題） 3.3.14．設(shè)αβδ是文法G的一個(gè)句型，A是非終結(jié)符，則β是句型αβδ相對(duì)于A的短語，若______＿；β是句型αβδ相對(duì)于A的直接短語，若_____＿；β是句型αβδ的句柄，若_______。（西安電子科大2000年研究生題） 3.3.15．Chomsky把文法分為______＿種類型，編譯器構(gòu)造中采用______和_____＿文法，它們分別產(chǎn)生_____和_____語言，并分別用______和______自動(dòng)機(jī)識(shí)別所產(chǎn)生的語 言。（西安電子科大2000年研究生試題）判斷題：

41、 3.4.1語法分析之所以采用上下文無關(guān)文法是因?yàn)樗拿枋瞿芰ψ顝?qiáng)。 （） 3.4.2欲構(gòu)造行之有效的自上而下分析器，則必須消除左遞歸。（） 3.4.3文法(有圖片)描述的語言是（a|bc）* ( ) 3.4.4 在自下而上的語法分析中，語法樹與分析樹一定相同。（） 3.4.5 二義文法不是上下文無關(guān)文法。（陜西省1999年自考題）（） 3.4.6 每一個(gè)算符優(yōu)先文法，必定能找到一組優(yōu)先函數(shù)與之對(duì)應(yīng)。（陜西省2000年 自考題）（） 3.4.7 語法分析時(shí)必須先消除文法中的左遞歸。（） 3.4.8 規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（） 3.4.9 一個(gè)文法所有句型的集

42、合形成該文法所能接受的語言。（） 3.4.10 LL(1)文法一定不含左遞歸和二義性。（） 綜合題 3.5.1 簡(jiǎn)答題1．句柄 2.素短語3．語法樹 4.歸約 5.推導(dǎo) 3.5.2給出上下文無關(guān)文法的定義。 3.5.3 Chomsky將文法分成四類。指明這四類文法與自動(dòng)機(jī)的對(duì)應(yīng)關(guān)系。指出右線性文法、左線性文法、正規(guī)文法之間的主要區(qū)別。 3.5.4 文法G是LL(1)文法的充分必要條件是什么？ 3.5.5 文法G[S］： S→aSPQ|abQ QP→PQ bP→bb bQ→be cQ→cc （1)它是Chomsky哪一型文法？ （2）它生成的語言是什么？ 3.5

43、.6 指出下述文法的所有類型，并給出所描述的語言。 （1）S→Be （2）A→ε|aB（3）TS→abcA B→eC|Af B→Ab|a S→Aabc A→Ae|e A→ε C→Cf Aa→Sa D→fDA cA→cS 3.5.7 按指定類型，給出語言的文法。 （1）L=｛aidj>i≥l}的上下文無關(guān)文法。 (2)字母表∑={a,b｝上的同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串的集合的正規(guī)文法。 (3）由相同個(gè)數(shù)a和b組成句子的無二義文法。 3.5.8 下面的二義文法描述命題演算公式，為它寫一個(gè)等價(jià)的非二義文法。 S→SandS|S or S|not S|p|q|(S) 3

44、.5.9 有文法G：S→aAcB|Bd A→AaB|c B→bScA|b （1)試求句型aAaBcbbdcc和aAcbBdcc的句柄； (2)寫出句子acabcbbdcc的最左推導(dǎo)過程。 3.5.10對(duì)文法G：E→E+T|T T→T*P|P P→i （1)構(gòu)造該文法的優(yōu)先關(guān)系表（不考慮語句括號(hào)＃），并指出此文法是否為算符優(yōu)先文法； (2）構(gòu)造文法G的優(yōu)先函數(shù) 3.5.11 在上一題中，如果將文法改為E→E+E|E*E|i,在不改動(dòng)文法的情況下是否同樣能構(gòu)造出優(yōu)先關(guān)系表？此外，針對(duì)例3.14中的文法與本例中的文法，對(duì)算符優(yōu)先分析快于規(guī)范歸約進(jìn)行說明。 3.5.12 對(duì)于文法

45、G[S]： S→(L)|aS|a L→L,S|S （1)畫出句型（s，（a））的語法樹。 (2)寫出上述句型的所有短語、直接短語、句柄和素短語。 3.5.13 構(gòu)造算符文法G[H]的算符優(yōu)先關(guān)系（含＃）。 G[H]：H→H;M|M M→d|aHb 3.5.14 設(shè)有文法G[S]為： S→a|b|(A) A→SdA|S （1)完成下列算符優(yōu)先關(guān)系表，見表3.6.并判斷G[S]是否為算符優(yōu)先文法。 (2）給出句型（SdSdS)的短語、簡(jiǎn)單短語、句柄、素短語和最左素短語。 （3)給出輸入串(adb)#的分析過程。 3.5.15 下面映射if語句的文法G[S]是算符優(yōu)先文法

46、嗎？若是，則構(gòu)造其優(yōu)先關(guān)系矩陣。若不是，請(qǐng)按照多數(shù)程序設(shè)計(jì)語言（如Pascal)的習(xí)慣，給出一個(gè)相應(yīng)的算符優(yōu)先文法。 G[S]：S→iBtS|iBtSeS|a B→b 3.5.16 文法G[G[3.5.17 已知文法G[A]為： A→aAB1|a B→Bb|d （I）試給出與G[A]等價(jià)的LL(I）文法G’[A]。 （2)構(gòu)造G’[A］的預(yù)測(cè)分析表。 （3）給出輸入串a(chǎn)adl#分析過程。 3.5.18 將G[V]改造為L(zhǎng)L（1）文法。 G[V]: V→N|N[E] E→V|V+E N→i 3.5.19 有文法G[S]: S-BA A--BS|d B～aA|bS|c

47、 (I）證明文法G是LL(I）文法。 （2）構(gòu)造LL（1）分析表。 (3）寫出句子adccd的分析過程。 3.5.20 考慮文法G[T]： T→T*F|F F→F↑P|P P→(T)|i （1)證明T*P↑(T*F)是該文法的一個(gè)句型，并指出其直接短語和句柄。 (2)構(gòu)造文法G的優(yōu)先關(guān)系表（要求寫出步驟）。 3.5.21 給出算符優(yōu)先文法的分析算法。 3.5.22 文法G的產(chǎn)生式集為：S→S+S|S*S|i|（s），對(duì)于輸入串i+i*i； （1)給出一個(gè)推導(dǎo)； (2）畫出一棵語法樹； （3)文法G是否是二義性的，請(qǐng)證明你的結(jié)論。 3.5.23 已給文法G[E]：

48、 E→EOE|(E)|i 0→+|* 試將其改造為可進(jìn)行不帶回溯的自頂向下分析的文法，并給出其相應(yīng)的LL(1)分析表。 3.5.24 考慮文法G(S)： S→(T)|a+S|a T→T,S|S 消除文法的左遞歸及提取公共左因子，然后，對(duì)每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。 3.5.25 有映射程序設(shè)計(jì)語言if-the-else語句的文法G[S]: S→iEtSeS|EtS|a E→b 其中，else遵從最近匹配原則。 （1)試改造文法，并為之構(gòu)造LL（1）分析表。 (2）利用構(gòu)造的分析表分析句子ibtibtaea,要求給出分析過程中每一步的分析棧和輸入串的變化以及輸出

49、信息。 3.5.26 下述文法描述了C語言整數(shù)變量的聲明語句： D→TL T→int|long|short L→id|L,id （1)改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的。 (2)分別用上述文法和改造文法，為輸入序列int a,b,c構(gòu)造分析樹。 3.5.27 設(shè)有文法G[W]： W→AO A→AO|W1|0 請(qǐng)改寫文法，消除規(guī)則左遞歸和文法左遞歸。 3.5.28 文法G[P]及相應(yīng)翻譯方案為： P→bQb {print:”1”｝ Q→cR {print:”2”｝ Q→a {print:”3”｝ R→Qad (print:”4”｝ （1)該文法

50、是不是算符優(yōu)先文法，請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之。 (2)輸入串為bcccaadadadb時(shí)，該翻譯方案的輸出是什么。 3.5.29 設(shè)有文法G[S]： S→SAS|b A→bSb|b 試構(gòu)造一個(gè)與其等價(jià)的算符文法。 3.5.30 在算符優(yōu)先分析法中，為什么要在找到最左素短語的尾時(shí)，才返回來確定其對(duì)應(yīng)的頭，能否按掃描順序先找到頭后找到對(duì)應(yīng)的尾，為什么？ 3.5.31 試證明在算符文法中，任何句型都不包含兩個(gè)相鄰的非終結(jié)符。 3.5.32假定文法包含產(chǎn)生式A→α，α∈V*（V是文法的詞匯表，由終結(jié)符和非終結(jié)符組成的集合），證明：如果FIRST（α）∩FOLLOW（A）≠φ，則該文法

51、不是LL（1)文法。 3.5.33 給出文法G1： S→aSb|P A→bPc|bQc B→Qa|a （1)它是Chomsky哪一型文法？ （2）它生成的語言是什么？ （3)它是不是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之。 (4)請(qǐng)證實(shí)所有①左遞歸文法②有公共左因子的文法均不是LL（1)文法。 (5)文法G1消除左遞歸、提取公共左因子后是不是LL (1）文法？請(qǐng)證實(shí)。 3.5.34 簡(jiǎn)答題 （1)什么是文法的二義性？二義性問題的不可判定指的是什么？ (2)在規(guī)范句型中，句柄以右的符號(hào)有什么特征？為什么？ 3.5.35 寫正規(guī)文法G,它產(chǎn)生的語言是L(G)={ ani

52、bncp|m,n,p≥0} 3.5.36 語言L是所有由偶數(shù)個(gè)0和偶數(shù)個(gè)1組成的句子的集合，給出定義L的正規(guī)文法。 3.5.37 已知文法G[S］：S→ABS|AB AB→BA A→0 B→1 該文法是幾型的？該文法所產(chǎn)生的語言是什么？（用自然語言描述）寫出與該文法等價(jià)的CFG文法。 3.5.8 寫一個(gè)上下文無關(guān)文法G，使得L(G)={anbmcmdn|n≥0,m≥1｝。 3.5.39 寫一個(gè)文法G，使其語言為L(zhǎng)(G)={ anbm|n≥m≥1｝。 3.5.40 生成語言1={albmclanbn|1>=O,m>=1，n>=2｝的文法是什么？它是Chomsky那一型文法？

53、3.5.41文法G[P]：P→aPQR|abR RQ→QR bQ→bb bR→be cR→cc 它是Chomsky哪一型文法？請(qǐng)證aaabbbccc是G[P]的一個(gè)句子。 3.5.42文法G[S］：S→aSPQ|abQ QP→PQ bP→bb bQ→be cQ→cc （1)它是Chomsky哪一型文法？ （2）它生成的語言是什么？ 3.5.43 給定文法G[S]：S→(S)S|ε，給出句子（（）（））（）（）的規(guī)范推導(dǎo)，并指出每步推導(dǎo)所得句型的句柄，畫出該句子的語法推導(dǎo)樹，指出所有的短語和直接短語。 3.5.44 設(shè)文法G[S]：S→(A)|a A→A+S|S

54、（1）構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合。 （2）構(gòu)造優(yōu)先關(guān)系表。 3.5.45已知文法G[S]：S→dAB A→aA|a B→Bb|ε （1)試問G[S]是否為正規(guī)文法，為什么？ (2）G[S]所產(chǎn)生的語言是什么？ （3) G[S]能否改寫為等價(jià)的正規(guī)文法? 3.5.46 選擇題 有文法G[S]：S→aA|a|bC，A→aS|bB，B→aC|bA|b，C→aB|bS，則____＿為L(zhǎng)(G) 中句子。 a. aloob5oabloo b. alooob5ooaba c. a500b60aab2a d. a l00 b4oab10 aa 3.5.47 對(duì)

55、文法G[S‘］：S‘→#S# S→fstS S→i=E E→E+T|T T→P↑T|P P→(E)|i （1）求各非終結(jié)符的FIRSTVT和LASTVT集合。 (2）構(gòu)造該文法的優(yōu)先關(guān)系表。（請(qǐng)將終結(jié)符以＝＋、↑、（、i, f, t,）、＃的順序構(gòu)造優(yōu)先關(guān)系表） 3.5.48 有文法R::=i|(T)，T::=T，R|R，完成表3.21所示的算符優(yōu)先關(guān)系表（填寫第一、第二行）。 3.5.49 文法G[M]是否LL(1)的，說明理由。 G[M]：M→TB T→Ba|ε B→Db|eT|ε D→d|ε 3.5.50 將文法G[E]改寫為等價(jià)的LL(I)文法，并給出相應(yīng)的

56、預(yù)測(cè)分析表。 G[E]：E→[T T→F]|TE F→i|Fi 3.5.51 已知文法G[S]: S→S*aP|aP|*aP P→+aP|+a （1）將文法G[S]改寫為L(zhǎng)L(1）文法G‘［S］。 (2)寫出文法G [S]的預(yù)測(cè)分析表。 5※第四章語法分析器的自動(dòng)構(gòu)造 典型例題: 單項(xiàng)選擇題 4.1.1.若a為終結(jié)符，則A→aaβ為____＿項(xiàng)目。 a.歸約 b.移進(jìn) c.接受 d.待約 4.1.2.兩個(gè)LR(1)項(xiàng)目集如果除去______后是相同的，則稱這兩個(gè)LR(1)項(xiàng)目同心。 a.項(xiàng)目 b.活前綴 c.搜索符 d.前綴 4.1.3．同心集合并不會(huì)

57、產(chǎn)生—沖突。 a.二義 b.移進(jìn)／移進(jìn) c.移進(jìn)／歸約 d.歸約／歸約 4.1.4．左結(jié)合意味著____＿。 a.打斷聯(lián)系實(shí)行移進(jìn) b.打斷聯(lián)系實(shí)行歸約 c.建立聯(lián)系實(shí)行移進(jìn) d.建立聯(lián)系實(shí)行歸約 4.1. 5.若項(xiàng)目集Ik含有A→a，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)a∈FOLLOW(A) 時(shí)，才采取“A→a”動(dòng)作的一定是_____。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 4.1.6．就文法的描述能力來說，有____＿。 a. SLR(1）cLR(0) b. LR(1）cLR(0) c. SLR(1）cL

58、R(1） d.無二義文法cLR(1） 4.1. 7.在LR(0)的ACTION子表中，如果某一行中存在標(biāo)記為"ri”的欄，則___＿。 a.該行必定填滿ri b.該行未填滿ri c.其他行也有ri d. goto子表中也有ri 4.1.8.一個(gè)____指明了在分析過程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。 a.活前綴 b.前綴 c.項(xiàng)目 d.項(xiàng)目集 4.1.9.若B為非終結(jié)符，則A→aBβ為____項(xiàng)目。 a.接受 b.歸約 c.移進(jìn) d.待約 4.1.10．同心集合并有可能產(chǎn)生新的＿沖突。 a.歸約 b.移進(jìn)／移進(jìn) c.移進(jìn)／歸約 d.歸約／歸約 4

59、.1.11．右結(jié)合意味著＿。 a.打斷聯(lián)系實(shí)行歸約 b.建立聯(lián)系實(shí)行歸約 c.建立聯(lián)系實(shí)行移進(jìn) d.打斷聯(lián)系實(shí)行移進(jìn) 4.1.12.若項(xiàng)目集Ik含有A→a，則在狀態(tài)K時(shí)，無論面臨什么輸入符號(hào)都采取“A→α 歸約”的動(dòng)作一定是＿。 a. LR(1）文法 b. LALR(1)文法 c. LR(0)文法 d. SLR(1）文法 4.1.13．就文法的描述能力來說，有＿。 a.無二義文法cSLR(1） b. LR(0) cLR(1) c.無二義文法cLR(0) d. LR(1) cLR(0) 多項(xiàng)選擇題： 4.2.1．一個(gè)LR分析器包括____。 a.一個(gè)總控程序

60、 b.一個(gè)項(xiàng)目集。 c.一個(gè)活前綴 d.一張分析表 e.一個(gè)分析棧 4.2.2 ．LR分析器核心部分是一張分析表，該表包括_____等子表。 a. LL(1）分析 b.優(yōu)先關(guān)系 c. GOTO d. LR e. ACTION 4.2.3．每一項(xiàng)ACTION[S,a]所規(guī)定的動(dòng)作包括______。 a.移進(jìn) b.比較 c.接受 d.歸約 e.報(bào)錯(cuò) 4.2.4.對(duì)LR分析表的構(gòu)造，有可能存在_____動(dòng)作沖突。 a.移進(jìn) b.歸約 c.移進(jìn)／歸約 d.移進(jìn)／移進(jìn)e .歸約／歸約 4.2.5．就文法的描述能力來說，有____。 a. SLR(1）c LR(

61、1） b. LR(0) c SLR(1） c. LR(0) c LR(1） d. LR(1）c無二義文法 e. SLR(1）c無二義文法 4.2.6．對(duì)LR分析器來說，存在＿_(dá)__等分析表的構(gòu)造方法。 a. LALR b. LR(0) c. SLR(1) d. SLR(0) e. LR(1) 4.2.7.自上而下的語法分析方法有＿_(dá)_。 a.算符優(yōu)先分析法 b. LL(1)分析法 c. SLR(1)分析法 d. LR(0)分析法 e. LALR(1)分析法 填空題： 4.3.1．對(duì)于一個(gè)文法，如果能夠構(gòu)造___，使得它的____均是唯一確定的，則稱該文法

62、為L(zhǎng)R文法。 4.3.2.字的前綴是指該字的＿_(dá)__。 4.3.3．活前綴是指_____的一個(gè)前綴，這種前綴不含____＿之后的任何符號(hào)。 4.3.4.在LR分析過程中，只要＿的已掃描部分保持可歸約成一個(gè)____，則掃描過的 部分正確。 4.3. 5.將識(shí)別＿_(dá)__的NFA確定化，使其成為以＿_(dá)___為狀態(tài)的DFA,這個(gè)DFA就是建 立的基礎(chǔ)。 4.3.6. A→a稱為_____項(xiàng)目；對(duì)文法開始符S，稱S→a為＿_(dá)_項(xiàng)目；若a為 終結(jié)符，則稱A→aaβ為__＿項(xiàng)目；若B為非終結(jié)符，則稱A→aBβ為_____項(xiàng)目。4.3.7. LR(0)分析法的名字中“L”表示，“R”表示，"

63、0”表示______。 4.3.8．一個(gè)LR分析器包括兩部分：________和_______. 4.3.9.兩個(gè)LR(1)項(xiàng)目集如果除去＿_(dá)____后是相同的，則稱這兩個(gè)LR(1)項(xiàng)目集_____。 4.3.10.構(gòu)成識(shí)別一個(gè)文法___＿的DFA的項(xiàng)目集全體，稱為這個(gè)文法的LR(0) _____. 4..3.11.一個(gè)活前綴γ的＿_(dá)__，就是從識(shí)別文法活前綴DFA的初態(tài)出發(fā)，經(jīng)讀出γ后所到達(dá)的那個(gè) 4.3.12．左結(jié)合意味著打斷聯(lián)系實(shí)行___＿，右結(jié)合意味著打斷聯(lián)系實(shí)行____＿。 4.3.13.同心集合并不會(huì)產(chǎn)生—沖突，但可能產(chǎn)生___＿沖突。 判斷題： 4.4.1. LR

64、分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（） 4.4.2.構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。（）4.4.3 .LR文法肯定是無二義的，一個(gè)無二義文法決不會(huì)是LR文法。（）4.4.4.在任何時(shí)候，分析棧的活前綴X1X2...Xm的有效項(xiàng)目集就是棧頂狀態(tài)Sm所在的那個(gè)項(xiàng)目集。（）4.4.5．同心集的合并有可能產(chǎn)生新的“移進(jìn)”／“歸約”沖突。（）4.4.6.由于LR(0)分析表構(gòu)造簡(jiǎn)單，所以它的描述能力強(qiáng)、適用面寬；LR(1)分析表因構(gòu)造復(fù)雜而描述能力弱、適用面窄。（）4.4.7．所有LR分析器的總控程序都是一樣的，只是分析表各有不同。（）4.4.8. LR分析技

65、術(shù)無法適用二義文法。（）4.4.9.項(xiàng)目A→β1β2對(duì)活前綴αβ1是有效的，其條件是存在規(guī)范推導(dǎo)S*=>aAW=> a ββ2ω。（）1 4.4.10. SLR(1)文法的特點(diǎn)是：當(dāng)符號(hào)棧中的符號(hào)串為βα，而面臨的輸入符號(hào)為α則存在把α歸約為A的規(guī)范句型的前綴βAα?xí)r，方可把a(bǔ)歸約為A。（）綜合題 4.5.1請(qǐng)指出圖4.2中的LR分析表（a）、（b）、（c）分屬LR（0）、SLR和LR（1）中的那一種，并說明理由。 4.5.2文法G的產(chǎn)生式如下： S→BB B～aB|b 請(qǐng)分別構(gòu)造該文法的（1) LR (0）分析表；(2）SLR分析表；(3）規(guī)范LR分析表（即LR（1）分析表）；（

66、4）LALR分析表。 4.5.3什么是規(guī)范句型的活前綴？引進(jìn)它的意義何在？ 4.5.4對(duì)于文法G[S］：S→AS|b A→SA|a (1)列出所有LR (0)項(xiàng)目。 (2)根據(jù)列出的項(xiàng)目構(gòu)造識(shí)別文法活前綴的NFA并確定化為DFAo （3)證明DFA的所有狀態(tài)全體構(gòu)成文法LR（0)規(guī)范族。 4.5.5 LR分析器與優(yōu)先關(guān)系分析器在識(shí)別句柄時(shí)的主要異同是什么？ 4.5.6 LR（0）、SLR(1), LR（1)及LALR有何共同特征？它們的本質(zhì)區(qū)別是什么？試論述之。 4.5.7 為二義文法G構(gòu)造一個(gè)LR分析表（詳細(xì)說明構(gòu)造方法）。其中終結(jié)符“，”滿足右結(jié) 合性，終結(jié)符“；”滿足左結(jié)合性，且“，”的優(yōu)先級(jí)高于“；”的優(yōu)先級(jí)。 文法G[T]：T→TAT|bTe｝a A→，|； 4.5.8 二義文法G[S],符的優(yōu)先性和結(jié)合性說明如下： （a）else與最近的if結(jié)合 (b）“；”優(yōu)先性大于if (c）“；”優(yōu)先性大于else (d)“；”服從左結(jié)合 請(qǐng)使用LR分析法的基本思想，憑借上述條件，為G[S]構(gòu)造LR分析表，要求