編譯原理2022年春學(xué)期在線作業(yè)2題目
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 60 分)
1.正則式的“·”讀作什么()。
A.并且
B.或者
C.連接
D.閉包
2.巴科斯-諾爾范式(即BNF)是一種廣泛采用的(什么樣的工具()。
A.描述規(guī)則
B.描述語(yǔ)言
C.描述文法
D.描述句子
3.設(shè)有文法G［S］:S→aAc|b，A→cAS|ε，則文法G是哪一類文法()。
A.LL(1)文法
B.非LL(1)文法
C.二義性文法
D.無(wú)法判斷
4.如果一個(gè)產(chǎn)生式的左部或右部含有無(wú)用符號(hào)，則此產(chǎn)生式稱為()產(chǎn)生式。
A.非法
B.多余
C.非確定
D.無(wú)用
5.DFA中定義了一個(gè)從K×Σ到K的單值映射f，指明若當(dāng)前的狀態(tài)為P，而輸入字符為a時(shí)，則下一個(gè)狀態(tài)是Q,f記為什么()。
A.f(P,Q)=a
B.f(P,a)=Q
C.f(Q,a)=P
D.f(a,P)=Q
6.規(guī)范推導(dǎo)的每一步總是用產(chǎn)生式右邊符號(hào)串替換句型中什么位置的非終結(jié)符號(hào)()。
A.最左
B.最右
C.最中
D.任意
7.自底向上分析時(shí)，若分析成功，則分析棧中只剩下什么()。
A.界符#及開始符號(hào)S
B.開始符號(hào)S
C.界符#號(hào)
D.當(dāng)前的輸入符號(hào)
8.設(shè)G是一右線性文法，并設(shè)G中的非終結(jié)符號(hào)的個(gè)數(shù)為k，則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有幾個(gè)結(jié)點(diǎn)()。
A.k-1
B.k
C.k+1
D.k+2
9.設(shè)有文法G[S]：S→11S|00S|0C|1C|ε，C→1S|0S|00C|11C，下列符號(hào)串中哪個(gè)是該文法的句子()。
A.00011
B.01011
C.001101
D.0110
10.假設(shè)某程序語(yǔ)言的文法如下：S→a|b|(T)，T→TdS|S，考察該文法的句型(Sd(T)db)，其中：素短語(yǔ)是哪個(gè)()。
A.S
B.b
C.(T)
D.Sd(T)
11.LL(1)分析表可用一個(gè)二維數(shù)組表示，它的每一行與文法的一個(gè)什么符號(hào)相關(guān)聯(lián)()。
A.非終結(jié)符號(hào)
B.終結(jié)符號(hào)
C.界符#號(hào)
D.開始符號(hào)
12.對(duì)一個(gè)什么文法G構(gòu)造相應(yīng)的優(yōu)先矩陣，若此矩陣中無(wú)多重定義的元素，則可確認(rèn)G為一算符優(yōu)先文法()。
A.LL(1)
B.LR(1)
C.簡(jiǎn)單優(yōu)先
D.算符
13.文法G的一棵語(yǔ)法樹葉結(jié)點(diǎn)的自左至右排列是G的一個(gè)什么()。
A.短語(yǔ)
B.句型
C.句柄
D.素短語(yǔ)
14.代碼優(yōu)化的主要目標(biāo)是什么()。
A.如何提高目標(biāo)程序的運(yùn)行速度
B.如何減少目標(biāo)程序運(yùn)行所需的空間
C.如何協(xié)調(diào)A和B
D.如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短。
15.生成中間代碼時(shí)所依據(jù)的是什么()。
A.語(yǔ)法規(guī)則
B.詞法規(guī)則
C.語(yǔ)義規(guī)則
D.等價(jià)變換規(guī)則
16.有下列文法：S→Pa|Pb|c，P→Pd|Se|f，該文法是哪一類文法()。
A.LL(1)文法
B.SLR(1)文法
C.A和B
D.都不是
17.所謂NFA的確定化，是指對(duì)任給的NFA，都能相應(yīng)地構(gòu)造一DFA，使它們有相同的什么()。
A.狀態(tài)集
B.符號(hào)集
C.接受集
D.結(jié)點(diǎn)集
18.設(shè)有文法G［S］:S→Ac，A→Sb|a，則利用文法G進(jìn)行自頂向下的語(yǔ)法分析時(shí)會(huì)怎樣()。
A.不會(huì)出現(xiàn)回溯
B.會(huì)出現(xiàn)回溯
C.不會(huì)出現(xiàn)死循環(huán)
D.會(huì)出現(xiàn)死循環(huán)
19.產(chǎn)生式是用于定義什么的一種書寫規(guī)則()。
A.語(yǔ)法范疇
B.推導(dǎo)
C.句柄
D.短語(yǔ)
20.通常把構(gòu)成各個(gè)單詞的字符串稱為該單詞的什么()。
A.編碼
B.類別
C.詞文
D.內(nèi)部表示
二、判斷題 (共 20 道試題,共 40 分)
21.編譯程序的特點(diǎn)是先將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程序，即先翻譯、后執(zhí)行。
22.若在一個(gè)右線性文法中含有多個(gè)右部相同的產(chǎn)生式，則由該文法構(gòu)造的狀態(tài)轉(zhuǎn)換圖一定是NFA。
23.對(duì)任何正規(guī)表達(dá)式e，都存在一個(gè)NFA M，滿足L(M)=L(e)。
24.對(duì)一個(gè)布爾表達(dá)式而言，它必須至少有一個(gè)真出口，但可以沒有假出口。
25.循環(huán)的入口結(jié)點(diǎn)是循環(huán)中每一結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)。
26.一個(gè)BASIC解釋程序和編譯程序的不同在于,解釋程序由語(yǔ)法制導(dǎo)翻譯成目標(biāo)代碼并立即執(zhí)行之,而編譯程序需產(chǎn)生中間代碼及優(yōu)化。
27.程序中的任何控制轉(zhuǎn)移四元式（條件轉(zhuǎn)移、無(wú)條件轉(zhuǎn)移、停機(jī)等）都是某基本塊的出口。
28.解釋程序與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過(guò)程中不產(chǎn)生目標(biāo)程序。
29.若給定文法G和某個(gè)固定的k，則G是否是LR(k)文法是可判定的。
30.逆波蘭表示法表示表達(dá)式時(shí)，運(yùn)算對(duì)象按實(shí)際計(jì)算順序從左到右排列。
31.布爾表達(dá)式有兩個(gè)基本的作用：一是在某些控制語(yǔ)句中作為實(shí)現(xiàn)控制轉(zhuǎn)移的條件；二是用于計(jì)算邏輯值本身。
32.在流程圖中的一組結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)時(shí)，可以有若干個(gè)入口結(jié)點(diǎn)，但出口結(jié)點(diǎn)必須是惟一的。
33.LR法是自頂向下語(yǔ)法分析方法。
34.構(gòu)造句型的語(yǔ)法樹時(shí)，要從樹的根結(jié)點(diǎn)出發(fā)，逐步向下構(gòu)造，而不能從句型出發(fā)向上構(gòu)造。
35.字母表A的自反傳遞閉包就是A上所有符號(hào)串所組成的集合。
36.空符號(hào)串ε與任何符號(hào)串x的連接還是x本身。
37.在一個(gè)控制結(jié)點(diǎn)樹中，一個(gè)結(jié)點(diǎn)n的全部子孫就組成了這個(gè)結(jié)點(diǎn)的必經(jīng)結(jié)點(diǎn)集D(n)。
38.每個(gè)文法都能改寫為L(zhǎng)L(1)文法。
39.若文法中含有形如A→A的產(chǎn)生式，可使含有非終結(jié)符號(hào)A的同一句型具有不同的語(yǔ)法樹，從而引起二義性。
40.存在既不是左句型也不是右句型的句型。
