计算机应用技术【专】-编译原理-2016-3-14 10-15-8试卷

武汉理工大学网络学院试卷

课程名称：编译原理专业班级：计算机应用技术【专】

备注: 学生不得在试题纸上答题(含填空题、选择题等客观题)

一、单项选择题（本题共10道小题，每小题2分，共20分）

1、程序基本块是指（）。

A．一个子程序

B．一个仅有一个入口和一个出口的语句

C．一个没有嵌套的程序段

D．一组顺序执行的程序段，仅有一个入口和一个出口

2、在产生式中，符号“→”（“::＝”）表示（）。

A. 等于

B. 恒等于

C. 取决于

D. 定义为

3、编译程序是对（）程序进行翻译。

A. 汇编语言

B.机器语言

C.自然语言

D. 高级语言

4、设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*),则称x是文法G 的一个（）。

A. 候选式

B. 句型

C. 产生式

D. 单词

5、文法G所描述的语言是（）的集合。

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

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

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

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

6、词法分析器的输出结果是（）。

A．单词的种别码B．单词组符号表中的位置

C．单词的种别码和单词的自身值D．单词的自身值

7、在状态转换图中，结点代表（），用圆圈表示。

A．输入缓冲区B．向前搜索C．字符串D．状态

8、编译程序前三个阶段完成的工作是（）。

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

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

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

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

9、如果在文法G中存在一个句子，当其满足下列条件（）时，则称该文法是二义性文法。

A．该句子的最右推导唯一B．该句子有两个不同的最左推导

C．该句子对应的语法树唯一D．该句子的最左推导和最右推导相同

10、已知属性文法G【S】：S →xxW print “1”

S →y print “2”

W →Sz print “3”

则若输入“xxxxyzz”，文法将输出（）。

A．11233 B．23131 C．11231 D．33211

二、判断题（本题共10道小题，每小题2分，共20分）正确的画“√”，错误的画“X”

1、( ) 如果a?＞b,b?＞c,则a?＞c。

2、( ) 对任意文法G，都存在相应的正规式与之等价。

3、( ) 程序中的表达式语句在语义翻译时不需要回填技术。

4、( ) 含有优化部分的编译程序的执行效率高。

5、( ) 语法分析时必须先消除文法中的左递归。

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

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

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

9、( ) 每个文法都能改写为LL(1)文法。

10、( ) 终态和非终态是可区别的。

三、应用（本题共4道小题，每小题10分，共40分）

1、设有布尔表达式文法G【B】： B→B or T | T

T→T and F | F

F→not F | （B） | true | false

给出句子（true or false）and not false的推导和语法树。

2、对于文法G【S】： S→（L）| aS| a

L→L, S|S

画出句型（S,（a））的语法树，写出上述句型的所有短语、直接短语、句柄。

3、设有布尔表达式文法G【B】： B→B or T | T

T→T and F | F

F→not F | （B） | true | false

给出句型true and not false or F的语法树，以及所有直接短语、句柄。

4、设文法G【S】： S→a | b |(T)

T→T,S | S

（1）改写文法，消除其文法中的直接左递归；

（2）证明改写后的文法是LL（1）文法，并且构造其预测分析表。

四、综合题（本题共1道小题，每小题20分，共20分）

1、对于文法G【E】： E → E(E) | e

（1）构造识别其规范句型所有活前缀的DFA；

（2）说明该文法是何种LR文法,并给出其相应的LR分析表。