编译原理mooc结课考试及参考答案|镜旅博客

本次考试仅有一次作答机会，共 26 道题，总分 100 分，需要在120分钟内完成。试题均为客观题(判断题、单选题、多选题)。考试截止前，请大家不要在讨论区讨论考试题目。谢谢！

1判断(3分)

在程序中，各种名字是用标识符表示的，所以名字和标识符没有本质区别。

A.√
B.×

2判断(3分)

一个句型的直接短语是唯一的。

A.√
B.×

3判断(3分)

文法的二义性和语言的二义性是两个不同的概念。

A.√
B.×

4判断(3分)

对任何正规集V，都存在一个NFA M，满足L(M)=V。

A.√
B.×

5判断(3分)

对于一个含有左递归的文法，存在与之等价的不含左递归的文法。

A.√
B.×

6判断(3分)

S-属性文法也是L-属性文法。

A.√
B.×

7判断(3分)

数组元素的地址计算代码的翻译与数组的存贮方式有关。

A.√
B.×

8判断(3分)

属性文法描述了语言的语义规则，翻译模式则给出了根据语义规则进行计算的实现细节。

A.√
B.×

9判断(3分)

活动记录的建立和撤销发生在编译阶段。

10判断(3分)

循环中的不变运算在优化时都可以被提到循环之外。

A.√
B.×

11单选(4分)

识别的字集为“包含奇数个1和奇数个0的二进制数串”的DFA是

12单选(4分)

下列文法中，生成的语言是

的是

A.G(S): S → ABCD A → aA | a B → bB |b C → cC |c D → dD | d
B.G(S): S → AC A → aAb | ab C → cCd | cd
C.G(S): S → aSd | A A → bAc | bc
D.G(S): S → aSb | A A → cAd | cd

13单选(4分)

对于文法G(S)：

S → BA

A → BS | d

B → aA | bS | c

该文法非终结符A的 FIRST集合是

A.FIRST(A) = { d }
B.FIRST(A) = { c，d }
C.FIRST(A) = { b，c，d }
D.FIRST(A) = { a，b，c，d }

14单选(4分)

对于文法G(S)：

S → BA

A → BS | d

B → aA | bS | c

该文法对应的预测分析表是

A. abcd#S A A → d BB → aAB → bSB → c
B. abcd#S S→ BA A A→ BSA → d BB → aAB → bSB → c
C. abcd#S S → BAS→ BA A A → BSA→ BSA → d BB → aAB → bSB → c
D. abcd#SS → BAS → BAS→ BA AA → BSA → BSA→ BSA → d BB → aAB → bSB → c

15单选(4分)

文法G(S)：

S → aTb | ,

T → R

R → R/S | S

的句型aR/aSb/aTb/,b 的最左素短语是

A.aTb
B.aSb
C.S
D.,

16单选(4分)

对于文法G(S’)：

(0) S’ → S

(1) S → aS

(2) S → bS

(3) S → a

该文法的LR分析表如下：

下面是输入串aba#的LR分析过程的0~4步的格局，第5步的格局是

步骤	状态栈	符号栈	输入串
0	0	#	aba#
1	01	#a	ba#
2	012	#ab	a#
3	0121	#aba	#
4	0125	#abS	#
5

17单选(4分)

考虑下面的属性文法G(S)：

对于输入字符串aabbbc进行语法分析和属性计算，输出结果是

A.1 2 3
B.3 2 1
C.2 3 1
D.2 1 3

18单选(4分)

将语句

while (A>B) Ú (B<C) do

if (D>0) then B:=C+D

else B:=C+1;

翻译成下面的四元式序列

100 (j>， A， B， 104)

101 (j， -， -， 102)

102 (j<， B， C， 104)

103 (j， -， -， 112)

104

105 (j， -， -， 109)

106 (+， C， D， T1)

107 (:=， T1， -， B)

108 (j， -， -， 100)

109 (+， C， 1， T2)

110 (:=， T2， -， B)

111 (j， -， -， 100)

112

其中空白处应该填写：

A.(j>， D， 0， 102)
B.(j>， D， 0， 106)
C.(j>， D， 0， 108)
D.(j>， D， 0， 111)

19单选(4分)

考虑下面的类PASCAL的嵌套过程语言程序，对于过程调用序列 S →Q→E→P 的情况，过程P的活动记录中的 Display 表为：

Program S(input,output);

var a,x:integer;

Procedure E;

Function P: integer;

var i,j:integer;

begin …

…

end{P};

begin

…

end {E};

Procedure Q;

var k, v:integer;

begin

…

end{Q};

begin …

…

end{S}.

20单选(4分)

假设H是基本块出口的活跃变量， R0和R1是可用寄存器，对下列四元式组成基本块：

A:=B*C

D:=E+A

G:=B+C

H:=G/D

生成目标代码如下：

LD R0 B

MUL R0 C

LD R1 E

ADD R1 R0

LD R0 B

ADD R0 C

ST R0 H

其中空白处的代码为

A.DIV R1 R0
B.DIV R0 R1
C.DIV R1 D
D.DIV R0 D

21多选(5分)

下面哪些文法是无二义文法

A.LL(1)文法
B.算符文法
C.算符优先文法
D.LR文法

22多选(5分)

对于文法G(S’)，该文法识别活前缀的DFA如下图，状态I2包含的项目有

G(S’)：

(0) S’ → S

(1) S → Pa

(2) S → Pb

(3) S → c

(4) P → Pd

(5) P → Se

(6) P → f

A.S → Pa
B.S → Pb
C.S → Pc
D.S → Pd

23多选(5分)

一个目标程序运行所需的存储空间包括

A.存放目标代码的空间
B.存放数据项目的空间
C.存放程序运行的控制或连接数据的空间
D.存放程序运行时动态申请的存储空间

24多选(5分)

对于下面程序段

program test (input, output) ;

var i, j: integer;

procedure calculate(x, y: integer);

begin

y:=y*y; x:=x-y; y:=y-x

end;

begin

i:=2; j:=3; calculate(i, j)

writeln(j)

end.

若程序执行的输出结果为16，能够产生该结果的参数传递方法有

A.传值
B.传地址
C.得结果
D.传名

25多选(5分)

设有基本块如下：

T1:=A+B

T2:=3

M:=T2*4

T3:=C-D

T4:=M+T3

N:= C-D;

L:=T1*T3

T4:=A+B

N:=T4

假设L、M和N 是出基本块后的活跃变量，对于上述程序可以采取的局部优化措施有

A.删除公共子表达式
B.删除无用赋值
C.合并已知量
D.代码外提

26多选(5分)

对以下四元式程序，对其中循环进行优化，可采取的循环优化措施有

S := 0

K := 1

L1: A := J+100

C := A * K

S := S + C

if K = 100 goto L2

K := K + 1

goto L1

L2: …

A.合并已知量
B.代码外提
C.强度消弱
D.删除归纳变量

答案PDF文件查看:

文章版权归作者所有，未经允许请勿转载。

THE END

编译原理编译原理
# 文法 # 判断 # 考试

喜欢就支持以下吧

点赞1 赞赏

请登录后发表评论