編譯原理2022年春學(xué)期在線作業(yè)1題目

試卷總分:100  得分:100

一、單選題 (共 20 道試題,共 60 分)

1.在一個NFA中，從某一給定的狀態(tài)q出發(fā)，僅經(jīng)過若干條標(biāo)記為ε的矢線所能達(dá)到的狀態(tài)所組成的集合記為什么()。

A.q-CLOSURE(ε)

B.ε-CLOSURE(q)

C.CLOSURE(ε-q)

D.CLOSURE(q-ε)

2.能將匯編語言翻譯為機(jī)器語言的程序是什么()。

A.匯編程序

B.編譯程序

C.解釋程序

D.語言程序

3.NFA的要素中不包含哪個成分()。

A.有窮字母表

B.初始狀態(tài)集合

C.終止?fàn)顟B(tài)集合

D.有限狀態(tài)集合

4.文法G[N]=（{N,B}，，{N→b│bB，B→bN}，N），該文法所描述的語言是什么()。

A.L(G[N])={bi│i≥0}

B.L(G[N])={b2i│i≥0}

C.L(G[N])={b2i+1│i≥0}

D.L(G[N])={b2i+1│i≥1}

5.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是多少()。

A.無窮多個

B.有窮多個

C.可枚舉的

D.個數(shù)是常量

6.算符優(yōu)先文法的特點是文法的產(chǎn)生式中不含什么()。

A.不含右遞歸

B.不含兩個相鄰的終結(jié)符

C.不含ε-產(chǎn)生式

D.不含左遞歸

7.逆波蘭式ab+c+d*e-所對應(yīng)的表達(dá)式是什么()。

A.(a+b+c)*d-e

B.a+b+c*d-e

C.a+(b+c)*d-e

D.(a-b+c)*d+e

8.賦值語句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是什么()。

A.Xab+cd-/-bc*a+-:=

B.Xab+/cd--bc*a+--:=

C.Xab+-cd-/abc*+-:=

D.Xab+cd-/abc*+--:=

9.兩個有窮自動機(jī)等價是指它們的什么相等()。

A.狀態(tài)數(shù)相等

B.有向弧數(shù)相等

C.所識別的語言相等

D.狀態(tài)數(shù)和有向弧數(shù)相等

10.項目A→α?稱為什么項目，其中A∈VN，A不是開始符()。

A.移進(jìn)

B.歸約

C.待約

D.接受

11.高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于哪一類的分析方法()。

A.自左至右

B.自頂向下

C.自底向上

D.自右向左

12.對于文法S→Ab|c，A→Sa，消除左遞歸性后，與原文法等價的文法是什么()。

A.S→Sab|c

B.S→cS′，S′→abS′|ε

C.S→Sab|c，A→Sa

D.S→cS′，S′→abS′|ε，A→Sa

13.所謂遞歸下降法，是指對文法的每一個什么符號，都根據(jù)相應(yīng)產(chǎn)生式各候選式的結(jié)構(gòu)，為其編寫一個子程序 (或函數(shù))()。

A.終結(jié)符號

B.非終結(jié)符號

C.符號

D.開始符號

14.若文法G定義的語言是無限集，則文法G必然是什么樣的()。

A.遞歸的

B.前后文無關(guān)的

C.二義性的

D.無二義性的

15.一個狀態(tài)轉(zhuǎn)換圖是由一組矢線連接的有限個結(jié)點所組成的什么()。

A.有向圖

B.無向圖

C.無回路有向圖

D.強(qiáng)連通的有向圖

16.一個狀態(tài)轉(zhuǎn)換圖中只能含有一個什么，用來指示分析的開始()。

A.輸入字符

B.矢線

C.終態(tài)

D.初態(tài)

17.巴科斯-諾爾范式(即BNF)是一種廣泛采用的(什么樣的工具()。

A.描述規(guī)則

B.描述語言

C.描述文法

D.描述句子

18.將形如A→αX?β的項目稱為A→α?Xβ的什么項目()。

A.移入

B.后繼

C.接受

D.歸約

19.文法G所描述的語言是什么的集合()。

A.文法G的字匯表V中所有符號組成的符號串

B.文法G的字母表V的閉包V*中的所有符號串

C.由文法的開始符號推出的所有終結(jié)符串

D.由文法的開始符號推出的所有符號串

20.方程X=rX+t的解是什么()。

A.X=rt*

B.X=t*r

C.X=r*t

D.X=tr*

二、判斷題 (共 20 道試題,共 40 分)

21.算符優(yōu)先分析法采用"移近-歸約"技術(shù),其歸約過程是規(guī)范的。

22.多遍掃描的編譯程序優(yōu)于單遍掃描的編譯程序。

23.正規(guī)文法不能產(chǎn)生語言 L＝｛anbn|n≥l｝。

24.逆波蘭表示只能用于表示表達(dá)式，不能用于表示其它的語法結(jié)構(gòu)。

25.逆波蘭表示法表示表達(dá)式時，運(yùn)算對象按實際計算順序從左到右排列。

26.若由文法G所構(gòu)造出的LL(1)分析表中不含有多重定義的元素，則可斷定文法G一定是LL(1)文法。

27.解釋程序與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過程中不產(chǎn)生目標(biāo)程序。

28.文法與語言之間必然存在一一對應(yīng)的關(guān)系。

29.對于文法G[A]： A→aABe|Ba，B→dB|ε，有人說：因為 FIRST（aABe）∩ FOLLOW（A）＝?，F(xiàn)IRST（Ba）∩ FOLLOW（A）≠?，所以，文法G[A]不是LL（l）文法。

30.1型文法常用來描述一個程序設(shè)計語言的單詞結(jié)構(gòu)。

31.若給定文法G，則G是否是LR(1)文法是可判定的。

32.在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。

33.回溯不會降低語法分析的效率，故不需要避免。

34.在一個狀態(tài)轉(zhuǎn)換圖中，規(guī)定從一個結(jié)點只能射出一條矢線。

35.算符優(yōu)先分析法只能識別由算符優(yōu)先文法描述的句子。

36.對于規(guī)模較大的文法，采用手工的方式來計算各個FIRST集和FOLLOW集幾乎是不可能的。

37.文法G[S]：S→aSb|aSa|c是LR（0）文法。

38.一個僅能處理絕對正確源程序的編譯程序才具有實用價值。

39.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中的所有錯誤。

40.如果一個文法含有過多的單產(chǎn)生式，將會增加編譯程序在工作時所需的時間和存儲空間，故在任何情況下都應(yīng)設(shè)法予以消除。