武汉理工大学编译技术期末复习题

编译技术复习题

复制题日后，按住Ctrl+F键查找相应题目答案

一、多选（共计25分，每题2.5分，每题答案完全一样得满分，少选、多选、错选均不得分。）

1、自下而上的语法分析中，应从一开始分析。

A.句型

B.句子

C.以单词为单位的程序

D.文法的开始符

错误：【B;D】

2、词法分析器的输出结果包括

A.单词的种别编码

B.单词在符号表中的位置

C.单词名

D.单词自身值

错误：【AD】

3、对无二义性文法来说，一棵语法树往往代表了_____

A.多种推导过程

B.多种最左推导过程

C.仅一种推导过程

D.一种最左推导过程

错误：【A;D】

4、在词法分析中，能识别出_____

A.保留字

B.运算符

C.逆波兰式

D.常数

错误：【A;B;D】

5、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标

代码生成等五个部分，还应包括_。

A.模拟执行器

B.解释器

C.表格处理

D.出错处理

错误：[C;D]

6、编译程序的输出结果可以是_____

A.源代码

B.汇编语言代码

C.中间代码

D.可重定位代码

错误：【B;D】

7、对于文法G[E]:⑴E-E+T⑵E-T(3)T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短语是一。

A.a

B.T

C.a+T

D.T*F

错误：【A;D】

8、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面说法中—正确。

A.是左递归文法

B.含有左公因子

C,是算符文法

D.是2型文法

错误：[A;B;C;D]

9、每一项ACTIONS,a]所规定的动作包括。

A.编辑

B.编译

C.连接

D.运行

错误:【A;B;C】

10、源程序中的错误一般有______

A.词法错误

B.语法错误

C.编译错误

D.语义错误

错误：[A;B;D]

二、判断（共计25分，每题2.5分）

11、确定的自动机以及襁定的自动机都能正确地识别正规集。

A.正确

B.错误

错误：【A】

12、递归下降语法分析时必须先消除文法中的左递归。

A.正确

B.错误

错误：【A】

13、对任意文法G,都存在相应的正规式与之等价.

A.正确

B.错误

错误：【A】

14、LR分析技术无法适用二义文法。

A.正确

B.错误

错误：⑻

15、自下而上语法制导翻译法的特点是语法分析栈与语义分析栈不需要同步操作。

A.正确

B.错误

错误：[B]

16、若一个语言是无穷集合，则定义该语言的文法一定是递归的。

A.正确

B.错误

错误：【A】

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

A.正确

B.错误

错误：【A】

18、对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存

器的利用效率。

A.正确

B.错误

错误：[A]

19、某赋值语句为y:=a+(b*c),其中a,b,c均为单词。

A.正确

B.错误

错误：⑻

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

A.正确

B.错误

错误：⑻

三、单选(共计50分，每题2.5分)

21、一个确定的有穷自动机DFA是一个

A.五元组(K£f,SZ)

B.四元组(VN,VT,P,S)

C.四元组(K,Z,f,S)

D.三元组(VN,VT,P)

错误：【A】

22、在产生式中，符号"一"("::=")表示

A.等于

B.恒等于

C.取决于

D.定义为

错误：【D】

23、中缀表达式a+b*(c+d)的逆波兰表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

错误：【A】

24、一文法不是LL⑴的。

A.递归

B.右递归

C.2型

D.含有公共左因子的

错误：【D】

25、设有如图所示的有穷自动机。其中状态①为初态，状态⑤为终态，假设digit代表数字

。到9。则下述实数中—可被该有穷自动机接受。

A.+123

B.-1.

C.6

D.-11.47

错误：[D]

26、若a为终结符,则A-coap是一项目。

A.归约

B.移进

C.接收

D,待约

错误：⑻

27、无符号常数的识别与拼数工作通常在一阶段完成。

A.语法分析

B.语义分析

C.词法分析

D.代码优化

错误：【O

28、递归下降分析法和预测分析法要求描述语言的文法是

A.正规文法

B.LR（O文法）

c.LL(1)文法

D.右线性文法

错误：⑹

29、有文法G及其语法制导翻译的属性文法如下所示(语义规则中的*和+分别是常规意义

,­,E-*-E,A,T,{E.val,=,E.val-*-T.val}^

••・EfT............{E.val,=,T.val}.

••,TfTftn',•,{T.val-=,T'.val-+*n.val,}p

•••T-*,-n............{T.val-=*n.val}♦J

下的算术运算符)：则分析句子1。八，2・八・3・#-4其值为........

A.10

B.34

C.14

D.54

错误：【C】

30、一不可能是目标代码。

A.汇编指令代码

B.可重定位指令代码

C.绝对指令代码

D.中间代码

错误：【D】

31、不能被如下状态转换图识别的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

错误：[D]

32、下列符号串不可以由符号集S={a,b}上的正闭包运算产生的是:

A.£

B.a

C.aa

D.ab

错误：【A】

33、在编译过程中，如果遇到错误应该

A.把错误理解成局部的错误

B.对错误在局部范围内进行纠正，继续向下分析

C.当发现错误时，跳过错误所在的语法单位继续分析下去

D.当发现错误时立即停止编译，待用户改正错误后再继续编译

错误：[C]

34、若源程序是用高级语言编写的程序，目标程序是_,则其翻译程序称为编译程序。

A.汇编语言程序或高级语言程序

B.高级语言程序或机器语言程序

C.汇编语言程序或机器语言程序

D.连接程序或运行程序

错误：⑹

•S-->.xxW......................print­•“1”一

•s.f.y.........................print-“2”♦

35、已知属性文法G【S】：,-->・敏.............Print-"3”.则若输入“xxxxyzz”，

文法将输出一O

A.11233

B.23131

C.11231

D.33211

错误：⑻

36、编译程序的语法分析器接受以—为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式

B.产生式

C.单词

D.语句

错误：【。

37、在状态转换图中，结点代表—,用圆圈表示。

A.输入缓冲区

B.向前搜索

C.字符串

D.状态

错误：【D】

38、文法G所描述的语言是一的集合。

A.文法G的字母表V中所有符号组成的符号串

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

C.由文法的开始符号推出的所有终结符串

D.由文法的开始符号推出的所有符号串

错误：⑹

39、已知文法G[S]为:S->a|A|(T)T->3sls则G[S]的FIRSTVT(S)为

A.{aA(}

B.{aA)}

C.{aA(,)

D.{aA)J

错误：【A】

40、如果文法G是无二义的，则它的得可句子a—o

A.最左推导和最右推导对应的语法树必定相同

B.最左推导和最右推导对应的语法树可能不同

C.最左推导和最右推导必定相同

D.可能存在两个不同的最左推导，但它们对应的语法树相同

错误：[A]

一、多选(共计25分，每题2.5分，每题答案完全一样得满分，少选、多选、错选均不得分。)

1、设有文法G⑸为：S-a|b|(A)A-SdA|S则LASTVT(S)包含的终结符有：

A.a

B.b

C.)

D.(

错误:【A;B;C】

2、词法分析器的输出结果包括一。

A.单词的种别编码

B.单词在符号表中的位置

C.单词名

D.单词自身值

错误：[A;D]

3、编译程序的输出结果可以是_____

A.源代码

B.汇编语言代码

C.中间代码

D.可重定位代码

错误：【B;D】

4、在词法分析中，能识别出一

A.保留字

B.运算符

C.逆波兰式

D.常数

错误：[A;B;D]

5、自下而上的语法分析中，应从开始分析。

A.句型

B.句子

C.以单词为单位的程序

D.文法的开始符

错误：[B;D]

6、源程序中的错误有______

A.词法错误

B.语法错误

C.编译错误

D.语义错误

错误：【A;B;D】

7、对于文法G[E]:(1)E-E+T⑵E-T⑶T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短语是一。

A.a

B.T

C.a+T

D.T*F

错误：[A;D]

8、算符优先文法G[E]:EE+T,T(E”i,则关于优先级的判断正确的是

A.+•>(

B.+•>+

C.+•>)

D.(•>)

错误：【B;C】

9、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标

代码生成等五个部分，还应包括

A.模拟执行器

B.解释器

C.表格处理

D.出错处理

错误：【C;D】

10、每一项ACTION[S,a]所规定的动作包括。

A.编辑

B.编译

C.连接

D.运行

错误:【A;B;C】

二、判断供计25分，每题2.5分）

11、逆波兰法表示的表达式亦称前缀式。

A.正确

B.错误

错误：⑻

12、每一个NFA都对应有唯一的一个最小化的DFA。

A.正确

B.错误

错误：⑻

13、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

A.正确

B.错误

错误：【A】

14、递归下降分析法是自顶向下分析方法。

A.正确

B.错误

错误:[A]

15、设有一个LR(O)项目集I={X-aBB，A-a},该项目集含有“归约-归约"冲突。

A.正确

B.错误

错误：⑻

16、编译程序与解释程序的区别在于编译程序对源程序进行了翻译，而解释程序则没有。

A.正确

B.错误

错误：⑻

17、自动机M和M'的状态数不同，则二者必不等价。

A.正确

B.错误

错误：⑻

18、使用语法制导翻译法的编译程序能够同时进行语法分析和语义分析。

A.正确

B.错误

错误：⑻

19、进行代码优化时应着重考虑循环的代码优化，颜寸提高目标代码的效率将起更大作用。

A.正确

B.错误

错误：【A】

20、包含左递归的文法也能直接用LL(1)分析法来分析。

A.正确

B.错误

错误：[B]

三、单选(共计50分，每题2.5分)

21、同正规式(a|b)*等价的正规式为

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

错误：【B】

22、文法G所描述的语言是一的集合。

A.文法G的字母表V中所有符号组成的符号串

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

C.由文法的开始符号推出的所有终结符串

D.由文法的开始符号推出的所有符号串

错误：[C]

23、编译程序的语法分析器接受以—为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式

B.产生式

C.单词

D.语句

错误：【O

24、LR语法分析栈中存放的状态是识别文法规范句型—的DFA状态。

A.前缀

B.活前缀

C.句柄

D.LR(0)项目

错误：⑻

25、编译程序前三个阶段完成的工作是^一。

A.词法分析、语法分析和代码优化

B.代码生成、代码优化和词法分析

C.词法分析、语法分析、语义分析和中间代码生成

D.词法分析、语法分析和代码生成

错误：[C]

•S-->.xxW.....................print*•“1”3

•S>—>.y........................print-,"2”♦

26、已知属性文法G【S】：WT•累..............「日出一“3”•则若输入“xxxxyzz",

文法将输出____

A.11233

B.23131

C.11231

D.33211

错误：⑻

27、中缀表达式a+b*(c+d)的逆波兰表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

错误：【A】

28、无符号常数的识别与拼数工作通常在一阶段完成。

A.语法分析

B.语义分析

C.词法分析

D.代码优化

错误：[C]

29、递归下降分析法和预测分析法要求描述语言的文法是

A.正规文法

B.LR(O文法)

C.LL(1)文法

D.右线性文法

错误：【C】

30、一不可能是目标代码。

A.汇编指令代码

B.可重定位指令代码

C.绝对指令代码

D.中间代码

错误：[D]

31、有文法G及其语法制导翻译的属性文法如下所示（语义规则中的*和+分别是常规意义

••・EfE1,AeT,{E.val,=•£.val,*,T.val}^

••・EfT............{E.val,=,T.val}^

•一TfTftn,,,•{T.val,=•71.val-+-n.val」。

••,T-*,n............{T.val,="n.val}y

下的算术运算符）,则分析句子1・八・2・/V3・#・4其值为........。,

A.10

B.34

C.14

D.54

错误：【C】

32、在编译过程中，如果遇到错误应该

A.把错误理解成局部的错误

B.对错误在局部范围内进行纠正，继续向下分析

C.当发现错误时,跳过错误所在的语法单位继续分析下去

D.当发现错误时立即停止编译，待用户改正错误后再继续编译

错误：⑹

33、已知文法G[S]为:S->a|A|（T）T->3sls则G[S]的FIRSTVT（S）为

A.”（}

B.{a八）}

C.{a八（,}

D.{a»}

错误：[A]

34、若源程序是用高级语言编写的程序，目标程序是_,则其翻译程序称为编译程序。

A.汇编语言程序或高级语言程序

B.高级语言程序或机器语言程序

C.汇编语言程序或机器语言程序

D.连接程序或运行程序

错误：⑹

35、自底向上语法分析法的原理是

A."移进~~推导法"

B."最蟠导法"

C."移进一归约法"

D."推导——归约法”

错误：⑹

36、下列符号串不可以由符号集S={a,b}上的正闭包运算产生的是：

A.E

B.a

C.aa

D.ab

错误：【A】

37、若a为终结符，则ATocaB是一项目。

A.归约

B.移进

C.接收

D.待约

错误：⑻

38、设有文法G[S]为：S-a|b|(A)AfSdA|S则FIRSTVT(S)=

A.{a,b,(}

B.{a,b,)}

C.{a,b,(,)}

D.{a,b,d}

错误：【A】

39、编译过程中，词法分析阶段的任务是_____

A.识别表达式

B.识别语言单词

C.识别语句

D.识别程序

错误：[B]

40、一文法不是LL(1)的。

A.递归

B.右递归

C.2型

D.含有公共左因子的

错误：【D】

一、多选(共计25分，每题2.5分海题答案完全一样得满分，少选、多选、错选均不得分。)

L对于文法G[E]:(1)E-E+T⑵E-T⑶T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短语是一。

A.a

B.T

C.a+T

D.T*F

错误：【A;D】

2、源程序中的错误T§有______

A.词法错误

B.语法错误

C.编译错误

D.语义错误

错误:[A;B;D]

3、自下而上的语法分析中，应从一开始分析。

A.句型

B.句子

C.以单词为单位的程序

D.文法的开始符

错误：【B;D】

4、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标

代码生成等五个部分，还应包括一O

A.模拟执行器

B.解释器

C.表格处理

D.出错处理

错误：【C;D】

5、编译程序的输出结果可以是_____

A.源代码

B.汇编语言代码

C.中间代码

D.可重定位代码

错误：【B;D】

6、在词法分析中，能识别出.

A.保留字

B.运算符

C.逆波兰式

D.常数

错误：[A;B;D]

7、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面说法中—正确。

A.是左递归文法

B.含有左公因子

C,是算符文法

D.是2型文法

错误：[A;B;C;D]

8、设有文法G⑸为：S-a|b|(A)A-SdA|S则LASTVT(S)包含的终结符有：

A.a

B.b

C.)

D.(

错误：【A;B;C】

9、下列优化中，属于循环优化的有

A.强度削弱

B.合并已知量

C.删除归纳变量

D.代码外提

错误：【A;C;D】

10、算符优先文法G【E】：EE+T,T(E)儿则关于优先级的判断正确的是

A.+•>(

B.+•>+

€.+•>)

D.(・>)

错误：【B;C】

二、判断供计25分，每题2.5分)

11、一个有限状态自动机中，有且仅有一个唯一终态。

A.正确

B.错误

错误：[B]

12、若一个语言是无穷集合，则定义该语言的文法一定是递归的。

A.正确

B.错误

错误：【A】

13、包含左递归的文法也能直接用LL(1)分析法来分析。

A.正确

B.错误

错误：⑻

14、LR分析技术无法适用二义文法。

A.正确

B.错误

错误:[B]

15、递归下降语法分析时必须先消除文法中的左递归。

A.正确

B.错误

错误：【A】

16、产生式是用于定义词法成分的一种书写规则。

A.正确

B.错误

错误：⑻

17、设有一个LR(O)项目集I={X-aBB，A-a},该项目集含有“归约-归约"冲突。

A.正确

B.错误

错误：⑻

18、每一个NFA都对应有唯一的一个最小化的DFA。

A.正确

B.错误

错误：⑻

19、紧跟在条件转移语句后面的语句是基本块的入口语句。

A.正确

B.错误

错误：【A】

20、对任意文法G,都存在相应的正规式与之等价.

A.正确

B.错误

错误：【A】

三、单选（共计50分，每题2.5分）

21、递归下降分析法和预测分析法要求描述语言的文法是

A.正规文法

B.LR（0文法）

C.LL（1）文法

D.右线性文法

错误：

22、无符号常数的识别与拼数工作通常在一阶段完成。

A.语法分析

B.语义分析

C.词法分析

D.代码优化

错误：[C]

23、自底向上语法分析法的原理是

A."移0~导法"

B."最磁导法”

C.”移进一归约法”

D."推导一归约法”

错误：【C】

24、用高级语言编写的程序经编译后产生的程序叫

A.源程序

B.目标程

C.连接程序

D.解释程序

错误：⑻

25、—不可能是目标代码。

A.汇编指令代码

B.可重定位指令代码

C.绝对指令代码

D.中间代码

错误：[D]

26、设有如图所示的有穷自动机。其中状态①为初态，状态⑤为终态，假设digit代表数字

0到9。则下述实数中—可被该有穷自动机接受。

A.+123

B.-1.

C.6

D.-11.47

错误：[D]

27、如果文法G是无二义的，则它的任何句子a

A.最左推导和最右推导对应的语法树必定相同

B.最左推导和最右推导对应的语法树可能不同

C.最左推导和最右推导必定相同

D.可能存在两个不同的最左推导，但它们对应的语法树相同

错误：【A】

28、有文法G及其语法制导翻译的属性文法如下所示（语义规则中的*和+分别是常规意义

••・EfE1,AeT,{E.val,=•£.val,*,T.val}^

••・EfT............{E.val,=,T.val}^

•一TfTftn,,,•{T.val,=•71.val-+-n.val」。

••,T-*,n............{T.val,="n.val}y

下的算术运算符）,则分析句子1・八・2・/V3・#・4其值为........。,

A.10

B.34

C.14

D.54

错误：⑹

29、在编译过程中，如果遇到错误应该

A.把错误理解成局部的错误

B.对错误在局部范围内进行纠正，继续向下分析

C.当发现错误时,跳过错误所在的语法单位继续分析下去

D.当发现错误时立即停止编译，待用户改正错误后再继续编译

错误：⑹

30、一文法不是山1）的。

A.递归

B.右递归

C.2型

D.含有公共左因子的

错误：【D】

31、文法G[S]:S-ab|aSb,该文法所描述的语言

A.L(G[S])={anbn|n>0}

B.L(G[S])={ambn|m,n>0}

C.L(G[S])={anbn|n>l}

D.L(G[S])={ambn|m,n>l}

错误：【C】

32、同正规式(a|b)*等价的正规式为

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

错误：【B】

33、一个确定的有穷自动机DFA是一个一。

A.五元组(KEf,S,Z)

B.四元组(VN,VT,P,S)

C.四元组(KZf,S)

D.三元组(VN,VT,P)

错误：【A】

34、设有文法G⑸为:STa|b|(A)A—SdA|S则FIRSTVT⑸=

A.{ab(}

B.{a,b,))

C.{a,b,(,))

D.{a,b,d}

错误：【A】

35、编译过程中，词法分析阶段的任务是_____

A.识别表达式

B.识别语言单词

C.识别语句

D.识别程序

错误：[B]

36、中缀表达式a+b*(c+d)的逆波兰表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

错误：【A】

37、文法G所描述的语言是一的集合。

A.文法G的字母表V中所有符号组成的符号串

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

C.由文法的开始符号推出的所有终结符串

D.由文法的开始符号推出的所有符号串

错误：⑹

38、不能被如下状态转换图识别的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

错误：【D】

39、在状态转换图中，结点代表一,用圆圈表示。

A.输入缓冲区

B.向前搜索

C.字符串

D.状态

错误：【D】

40、编译程序的语法分析器接受以—为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式

B.产生式

C.单词

D.语句

错误：［C］

一、多选（共计25分，每题2.5分，每题答案完全一样得满分，少选、多选、错选均不得分。）

1、每一项ACTIONS,a］所规定的动作包括。

A.编辑

B.编译

C.连接

D.运行

错误:【A;B;C】

2、对无二义性文法来说，一棵语法树往往代表了_____

A.多种推导过程

B.多种最左推导过程

C.仅一种推导过程

D.一种最左推导过程

错误：［A;D］

3、源程序中的错误有______

A.词法错误

B.语法错误

C.编译错误

D.语义错误

错误：[A;B;D]

4、通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标

代码生成等五个部分，还应包括一O

A.模拟执行器

B.解释器

C.表格处理

D.出错处理

错误：【C;D】

5、在词法分析中，能识别出_____

A.保留字

B.运算符

C.逆波兰式

D.常数

错误：[A;B;D]

6、设有文法G[S]为：S-a|b|(A)ATSdA|S则LASTVT(S)包含的终结符有：

A.a

B.b

C.)

D.(

错误：[A;B;C]

7、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面说法中—正确。

A.是左递归文法

B.含有左公因子

C,是算符文法

D.是2型文法

错误：[A;B;C;D]

8、算符优先文法G[E]:EE+T,T(E)|i,则关于优先级的判断正确的是一。

A.+•>(

B.+•>+

€.+•>)

D.(>>)

错误：[B;C]

9、对于文法G[E]:(1)E—E+T⑵E-T⑶Tf*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短语是一。

A.a

B.T

Ca+T

D.T*F

错误：【A;D】

10、词法分析器的输出结果包括

A.单词的种别编码

B.单词在符号表中的位置

C.单词名

D.单词自身值

错误：[A;D]

二、判断（共计25分，每题2.5分）

11、对任意文法G,都存在相应的正规式与之等价.

A.正确

B.错误

错误：【A】

12、每一个NFA都对应有唯一的一个最小化的DFA。

A.正确

B.错误

错误：[B]

13、包含左递归的文法也能直接用LL(1)分析法来分析。

A.正确

B.错误

错误：⑻

14、逆波兰法表示的表达式亦称前缀式。

A.正确

B.错误

错误：⑻

15、一个有限状态自动机中，有且仅有一个唯一终态。

A.正确

B.错误

错误：[B]

16、递归下降语法分析时必须先消除文法中的左递归。

A.正确

B.错误

错误：【A】

17、每个句子都有规范推导；每个句型都有规范推导。

A.正确

B.错误

错误：【A】

18、自下而上语法制导翻译法的特点是语法分析栈与语义分析栈不需要同步操作。

A.正确

B.错误

错误：[B]

19、进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

A.正确

B.错误

错误：【A】

20、对任何一个编译程序来说，产生中间代码是不可缺少的。

A.正确

B.错误

错误：⑻

三、单选（共计50分，每题2.5分）

21、同正规式（a|b）*等价的正规式为

A.（a|b）+

B.a*|b*

C.(ab)*

D.(a*|b*)+

错误：⑻

22、若源程序是用高级语言编写的程序，目标程序是—，则其翻译程序称为编译程序。

A.汇编语言程序或高级语言程序

B.高级语言程序或机器语言程序

C.汇编语言程序或机器语言程序

D.连接程序或运行9

错误：⑹

23、—不可能是目标代码。

A.汇编指令代码

B.可重定位指令代码

C.绝对指令代码

D.中间代码

错误:【D】

24、无符号常数的识别与拼数工作通常在一阶段完成。

A.语法分析

B.语义分析

C.词法分析

D.代码优化

错误：[C]

25、编译程序前三个阶段完成的工作是一0

A.词法分析、语法分析和代码优化

B.代码生成、代码优化和词法分析

C.词法分析、语法分析、语义分析和中间代码生成

D.词法分析、语法分析和代码生成

错误：⑹

26、在状态转换图中，结点代表一，用圆圈表示。

A.输入缓冲区

B.向前搜索

C.字符串

D.状态

错误：【D】

27、在产生式中，符号）表示

A.等于

B.恒等于

C.取决于

D.定义为

错误：【D】

28、递归下降分析法和预测分析法要求描述语言的文法是

A.正规文法

B.LR(O文法)

C.LL(1)文法

D.右线性文法

错误：[C]

29、编译过程中,词法分析阶段的任务是_____

A.识别表达式

B.识别语言单词

C.识别语句

D.识别程序

错误：⑻

30、设有如图所示的有穷自动机。其中状态①为初态，状态⑤为终态，假设digit代表数字

0到9。则下述实数中—可被该有穷自动机接受。

digitdigit

ca

A.+123

B.一1.

C.6

D.-11.47

错误：【D】

31、不能被如下状态转换图识别的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

错误：[D]

32、LR语法分析栈中存放的状态是识别文法规范句型—的DFA状态。

A.前缀

B.活前缀

C.句柄

D.LR(0)项目

错误：⑻

33、如果文法G是无二义的，则它的任何句子a

A.最左推导和最右推导对应的语法树必定相同

B.最左推导和最右推导对应的语法树可能不同

C.最左推导和最右推导必定相同

D.可能存在两个不同的最左推导，但它们对应的语法树相同

错误：［A］

34、设有文法G［法为:S-a|b|(A)AfSdA|S则FIRSTVT(S)=

A.{a,b,(}

B.{a,b,))

C.{a,b,(,)}

D.{a,b,d}

错误：【A】

35、若a为终结符,则A-ocaB是一项目。

A.归约

B.移进

C.接收

D.待约

错误：【B】

36、中缀表达式a+b*(c+d)的逆波兰表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

错误：【A】

37、用高级语言编写的程序经编译后产生的程序叫一o

A.源程序

B.目标程J?

C.连接程序

D.解释程序

错误：⑻

38、一个确定的有穷自动机DFA是一个

A.五元组(KZf,S,Z)

B.四元组(VN,VLP5)

C.四元组(K,Z,f,S)

D.三元组(VN,VT,P)

错误：【A】

39、在编译过程中，如果遇到错误应该

A.把错误理解成局部的错误

B.对错误在局部范围内进行纠正，继续向下分析

C.当发现错误时，跳过错误所在的语法单位继续分析下去

D.当发现错误时立即停止编译，待用户改正错误后再继续编译

错误：【O

40、编译程序的语法分析器接受以—为单位的输入，并产生有关信息供以后各阶段使用。

A.表达式

B.产生式

C.单词

D.语句

错误：⑹

一、简答(每题参考分值5分)

1、设M=({x,y},{a,b},f,x,{y})为一非确定的有限自动机,其中f定义如

f(xsa)={xsy}f{x,b}={y}

f{y5b}={x,y}

下：试构造相应的确定有限自动机M‘(即：DFAM')。

正确答案:解:对照自动机的定义M=(S,2,f,So,Z),由f的定义可知f(x,a)、

f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出NFAM相应的

状态图，如下图所示。

(正确得2分)

用于集法构造状态转换矩阵，如下表所示。(下面正确得6分)

ILh

{X}{x,y}{y}

{y}—{x,y)

{x，a{x,y}{x»y)

将转换矩阵中的所有子集重新命名，形成下表所示的状态转换矩阵，即得到

(注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。)

2、对于文法G[S]：S-(L)|aS|aL-L,S|S写出上述句型的所有短语、直接

短语、句柄和素短语。

G*一语:S、a、(a)、S,(a)%(S,(a))j(2分)”

如直施语：a、…(1分)/

6句标S3・•(1分)d

正确答案：6素短语…・・(1分八

3、将赋值语句X=a*b+c*(d+e*f/g)*h翻译为相应的四元式。

正确答案：四元式：(1)(*,a,b,tl)(2)(*,e,f,t2)⑶(/,t2,

g,t3)(4)(+,d,t3,t4)(5)(*,c,t4,t5)(6)(*,t5,h,t6)(7)

(十,tl,t5,t6)(8)(=,t6,,x)

4、设有基本块：Tl:=A+BT2:=5M:=T2*4T3:=C-DT4:=M+T3L:=T1*T3T4:=A+BN:=T4

画出DAG图；假设只有L,M,N在基本块后面还要被引用，请写出优化后的代码

序列。

正确答案：DAG(6分，每个父节点1分,合并节点1分)：

优化后的四元

式为:(4分，每个1分)N:=A+B;M:=20;T3:=C-D;L:=N*T3

5、设有以下文法：G[S]：S-aAbDe|dA->BSD|eB^SAc|cD|eD-*Se|e求出

该文法的每一个非终结符的FOLLOW集。

正确答案：FOLLOW(S)=FIRST(D)UFIRST(Ac)UFIRST(e)

U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e#}FOLLOW(A)=FIRST(bDe)

UFIRST(c)={b,c}FOLLOW(B)=FIRST(SD)={a,d}FOLLOW(D)=FIRST

(e)UFOLLOW(A)UFOLLOW(B)={e}U{b,c}U{a,d}={a,b,c,d,e}

6、对于文法G[S]：S-Sa|aTfT-fSd|f|fSa构造识别其规范句

型所有活前缀的DFA；说明该文法是何种LR文法,并给出其相应的LR分析表。

正确答案：将文法拓广为：G'[S']：(0)S'fS(l)S->Sa(2)S-aTf

(3)T->fSd(4)T->f(5)T-fSaDFA：

因为上述DFA的I、•r、I态集中有移进-归约冲突和归约-归约冲突，所以该文法不是

LR(O)文法。L

对于I中：,归约项目宓・移进项目S—S.aw

而：{a}-n・FOLLOY(交.,)=•{a}-C・{#}・=g

对于I中：,归约项自T-*f-移进项自S->.aI*

而：{a}・C・FOLLOWT)=・{a}・C・{f}・=W

对于［中：•归约项目T-*fSa--归约项目S-*Sa.

而：FOLLOV(T-Cl-FOLLOW(S)=-{f}-A•{#,a<!•}♦=6

所以可用SLR(l)方法解决L、•1、工的冲突。所以该文法是SLR⑴文法。・・(2分).

ACTION^GOM

状心*丸g

0/皿

Id83P^£r'd

2ddSsv4〃

3-okod

跖1do

5-s2~7

6/w丁

13Sgdd

8-y♦Jd

9-

SLR(l)分析表:ri"*

7、已知文法G：S-*(LaLS,L|)判断是不是LL(1)文法，如

果是请构造文法G的预测分析表，如果不是请说明理由。

正确答案：【解】1)求各非终结符的FISRT集和FOLLOW集：(正确得4

First(S)={(,a}

FIRST(L)={)FIRST(S)={(,),a}

FOLLOW(S)={,#}

FOLLOW(L)=FOLLOW⑸={,#}

FIRST((L)G{a}二6

FIRST(S,L)A{)}=<P

分)所以是LL(1)文法(正确得2分)

2)预测分析表：(正确得4分)

}#

(a9

SS-*(LSfa

LLfS,LLfS,LLf)

L(G)={ab1|j>i>l)

8、给出下面语言的上下文无关文法。

正确答案：上下文无关文法G[S]为：G[S]：S-aSb|Sb|b

9、基本块的DAG右图所示。若b在该基本块出口处活跃，请给出下列代码经过

优化之后的代码：(1)a=b+c(2)b=a-d(3)c=b+c(4)d=a-d

正确答案：当b在出口活跃时，生成优化后的代码为a=bO+cOb=a-dOd=b

c=d+cO

10、设文法G(S)：S-(L)|aS|aL-L,S|S消除左递归和

提取左公因子；

S->(L)|aS'

S'—S|£

L—SL'

正确答案：(消除左递归正确得3分,提取左公因子正确得2分)L--SL'|E

二、单选(每题参考分值2.5分)

11、递归下降分析法和预测分析法要求描述语言的文法是__o

A.正规文法

B.LR(O文法)

C.LL(1)文法

D.右线性文法

错误：【C】

12、文法G所描述的语言是的集合。

A

文法G的字母表V中所有符号组成的符号串

B

文法G的字母表V的闭包V*中的所有符号串

c

由文法的开始符号推出的所有终结符串

D

由文法的开始符号推出的所有符号串

错误：【C】

13、一个确定的有穷自动机DFA是一个

A.五元组(K,2,f,S,Z)

B.四元组(VN,VT,P,S)

C.四元组(K,S,f,S)

D.三元组(VN,VT,P)

错误：【A】

14、若a为终结符，则A-a・aB是—项目。

归约

A.移进

BC.

收

接

约

D.待

错误：【B】

15、设有如图所示的有穷自动机。其中状态①为初态，状态⑤为终态。假设digit

代表数字0到9。则下述实数中可被该有穷自动机接受。

ea

A.+123

B.一1.

C.6

D.一11.47

错误：【D】

16、设有文法G[S]为：Sfa|b|(A)AfSdA|S则FIRSTVT(S)二

A.{a,b,()

B.{a,b,))

C.{a,b,(,)}

D.{a,b,d)

错误：【A】

17、有文法G及其语法制导翻译的属性文法如下所示(语义规则中的*和+分别是

••・EfE'A{E.val,=,E.val•♦,T.val}一

・•・EfT.............{E.val,=,T.val}.

••T#•!!••••{T.val,=,T1.val-+-n.val,}

,•,T~~*,,n.............{T.val,=,n.val}y

常规意义下的算术运算符)：则分析句子1.八.2・八・3嘛・4其值为.......--

A.10

B.34

C.14

D.54

错误：【C】

18、用高级语言编写的程序经编译后产生的程序叫

A.源程序

B.目标程序

C.连接程序

D.解释程序

错误：【B】

19、在编译过程中，如果遇到错误应该

A

把错误理解成局部的错误

B

对错误在局部范围内进行纠正，继续向下分析

c

当发现错误时，跳过错误所在的语法单位继续分析下去

D

当发现错误时立即停止编译，待用户改正错误后再继续编译

错误：【C】

20、编译程序前三个阶段完成的工作是

A

词法分析、语法分析和代码优化

B

代码生成、代码优化和词法分析

c

诃法分析、语法分析、语义分析和中间代码生成

D

词法分析、语法分析和代码生成

错误：【c】

21、编译过程中，词法分析阶段的任务是

A.识别表达式

B.识别语言单词

C.识别语句

D.识别程序

错误：【B】

22、文法G[S]：S->ab|aSb,该文法所描述的语言

A.L(G[S])={anbn|n^O]

B.L(G[S])={ambn|m,n20}

C.L(G[S])={anbn|n'l}

D.L(G[S])={ambn|田，n21}

错误：【c】

23、LR语法分析栈中存放的状态是识别文法规范句型___的DFA状态。

前缀

AR.

活前

缀

C句柄

D.

24、文法不是LL(1)的。

A.递归

B.右递归

C.2型

D.含有公共左因子的

错误：【D】

25、中缀表达式a+b*(c+d)的逆波兰表示是

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

错误：【A】

26、下列符号串不可以由符号集S={a,b}上的正闭包运算产生的是:

A.£

B.a

C.aa

D.ab

错误：【A】

27、无符号常数的识别与拼数工作通常在一阶段完成。

A.语法分析

B.语义分析

C.词法分析

D.代码优化

错误：【口

•S-->.xxW......................print-"1”，

•s.T.y.........................print--"2”♦

28、已知属性文法G[S]:•敦...........PHnt・,”3〃♦则若输入

“xxxxyzz”,文法将输出___o

A.11233

B.23131

C.11231

D.33211

错误：【B】

29、不可能是目标代码。

A

汇编指令代码

B

可重定位指令代码

c

绝对指令代码

D

中间代码

错误：【D】

30、已知文法G[S]为：S->a己知T)T->T,S|S则G[S]的FIRSTVT(S)为

A.{a-(}

B.{「)}

C.(a〜(,}

D.{a'),1

错误：【A】

31、在产生式中，符号“一”（"：：=”）表示

A.等于

B.恒等于

C.取决于

D.定义为

错误：【D】

32、若源程序是用高级语言编写的程序，目标程序是—,则其翻译程序称为编

译程序。

A.汇编语言程序或高级语言程序

B.高级语言程序或机器语言程序

C.汇编语言程序或机器语言程序

D.连接程序或运行程序

错误：【C】

33、自底向上语法分析法的原理是

A.“移进一一推导法”

B.“最左推导法”

C.“移进一一归约法”

D.“推导一一归约法”

错误：【c】

34、在状态转换图中，结点代表,用圆圈表示。

A.输入缓冲区

B.向前搜索

C.字符串

D.状态

错误：【D】

35、不能被如下状态转换图识别的句子是

A

aOb

B

alOlOb

c

bOOb

D

ab

错误：【D】

36、同正规式(a|b)*等价的正规式为

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

错误：【B】

37、如果文法G是无二义的，则它的任何句子Q

A

最左推导和最右推导对应的语法树必定相同

B

最左推导和最右推导对应的语法树可能不同

c

最左推导和最右推导必定相同

D

可能存在两个不同的最左推导，但它们对应的语法树相同

错误：【A】

38、编译程序的语法分析器接受以—为单位的输入，并产生有关信息供以后各

阶段使用。

表达式

九

式

产生

BC.

单词

D.语句

错误：【C】

39、正规式M1和M2等价是指—

A.Ml和M2的状态数相等

B.Ml和M2的有向边条数相等

C.Ml和M2所识别的语言集相等

D.Ml和M2状态数和有向边条数相等

错误：【C】

40、Chomsky把文法分成四种类型，即0型、1型、2型和3型。1型文法也称为

A

上下文无关文法

B

上下文有关文法

c

正规文法

D

短语文法

错误：【B】

41、正规式的运算符“*”读作

A.或

B.连接

C.闭包

D.乘

错误：【C】

42、设有文法G［法:S-Sl|S0|Sa|Sc|a|b|c,下列符号串中是该文法的句子有

A

abO

B

aOcOl

c

aaab

D

bcblO

错误：【B】

43、词法分析器的输出结果是一

A.单词的种别码

B,单词组符号表中的位置

C.单词的种别码和单词的巨身值

D.单词的自身值

错误：【C】

44、在规范归约中，用来刻划可归约串。

A.直接短语

B.句柄

C.最左素短语

D.素短语

错误：【B】

45、文法G所描述的语言是的集合。

A.文法G的字汇表V中所有符号组成的符号串

B.文法G的字汇表V的闭包组成的所有符号串

C.由文法的识别符号推出的所有符号串

D.由文法的识别符号推出的所有终结符号串

错误：【D】

46、设G是一个给定的文法，S是文法的开始符号，如果S3x（其中xWV）,则称x

是文法G的一个—o

候选

式

A.

R句型

C产生

式

单词

D.

错误:[B]

47、在目标代码生成阶段，符号表用于

A.词法检查

B.语义检查

C.语法检查

D.地址分配

错误：【D】

48

、是一种典型的解释型语言。

A.BASIC

BC.C

FORTRAN

D.PASCAL

错误：【A】

49、若状态k含有项目“Afa.”,对任意非终结符a,都用规则“A-Q”归

约的语法分析方法是o

A.LALR分析法

B.L