《编译原理》复习题

则中的*和+分别是常规意义下的算术运算符）： E→E(1) ∧ T {E.val = E(1).val * T.val} E→T {E.val = T.val}

T→T(1)# n {T.val = T(1).val + n.val } T→ n {T.val = n.val}

则分析句子3 ∧ 3 # 4其值为（ B ）。 A. 10 B. 21 C. 14 D. 24

61．表达式a+b+c的逆波兰表示为（ B ）。 A．a+bc+ B．ab+c+ C．+abc+ D．abc++ 62. 文法G[S]及其语法制导翻译定义如下： 产生式 语义动作

S’ → S print(S.num) S → (L) S.num = L.num +1

S → a

S.num = 0

L →L(1), S L.num = L(1).num + S.num

L →S L.num =

S.num

若输入为(a, a)，且采用自底向上的分析方法，则输出为（ B ）。 A．0 B．1 C．2 D．4

63. 在SLR（1）的Action表中，如果某行中存在标记为“rj”的栏，则：（ B ）

A. 该行必定填满“rj” B. 该行未必填满“rj” C. 其他行可能也有“rj” D. goto表中也可能有“rj” 64. 一个（ D ）指明了在LR分析过程中的某个时刻所能看到产生式多大一部分。

A. 活前缀 B. 前缀 C. 归约活前缀 D. 项目 65.文法G：S → xS | y 所识别的语言是（ D ）。 A．xy* B．(xy)* C．xx*yx D．x*y 66.若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是（ D ）。

A．LALR分析法 B．LR(0)分析法 C．LR(1)分析法 D．SLR(1)分析法 67．设有文法G[T]: T→T*F|F F→F↑P|P P→(T)|a

该文法句型T*P↑(T*F)的句柄是下列符号串（ C ）

A.（T*F） B. T*F C. P D. P↑(T*F)

5

68．LR分析表中的转移表（goto）是以（ B ）作为列标题的。

A．终结符 B．非终结符 C．终结符或非终结符 D．表示状态的整形数

69．编译程序的语法分析器必须输出的信息是（ A ）

A．语法错误信息 B．语法规则信息 C．语法分析过程 D．语句序列

70．下列项目中为可移进项目的是（ C ）。

A．E′→E . B．L→. C．L→-.L D．F→L*F.

71．有一语法指导定义如下： S→bAb print “1” A→（B print “2” A→a print “3” B→aA) print “4” 若输入序列为b（a（a（aa）））b，且采用自底向上的分析方法，则输出序列为（ B ） A．32224441 B．34242421 C．12424243 D．34442212

72．同正规式（a|b）*等价的正规式为（ D ） A．(a|b)+ B．a*|b* C．(ab)* D．(a*|b*)+

73．词法分析器的加工对象是（ C ） A．中间代码 B．单词 C．源程序 D．元程序

74．在自下而上的语法分析中，应从（ B ）开始分析。

A．句型 B．句子 C．文法开始符号 D．句柄

75．赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示是（ C ） A. Xab+cd-/-bc*a+-:= B. Xab+/cd-bc*a+--:= C. Xab+-cd-/ a bc* +-:= D. Xab+cd-/abc* +--:= 76．设有文法G[T]: T→T*F|F F→F↑P|P P→(T)|a

该文法句型T*F↑(T*F)的句柄是下列符号串（ B ）

A.（T*F） B. T*F C. P D. P↑(T*F)

77．LR分析表中的动作表（action）是以（ D ）作为列标题的。

《编译原理》复习题

A．终结符 B．非终结符 C．终结符或C．该行一定填满rj D．该非终结符 D．终结符和结束符$

行未填满rj

78．下列项目中为可归约项目的是（ B ）。

A．E′→.E B．L→. C．L→-.L 86．同正规式（a|b）+等价的正规式是D．F→L*.F

_________B________________。 79．有一语法指导定义如下，其中+表示符号连接

运算： A．（a|b）* B．（a|b）（a|b）* C．（ab）S→B print B.vers

*（ab） D．（a|b）|（a|b）* B→a B.vers=a

B→b B.vers=b 87.在规范归约中，用______B______来刻画可归B→Ba B.vers=a+B.vers

约串。 B→Bb B.vers=b+B.vers

A．直接短语 B．句柄 C．素短语 若输入序列为abab，且采用自底向上的分析方法，

D．短语 则输出序列为（ D ）

A．aabb B．abab C．bbaa 88．若a为终结符，则A→α·aβ为 D．baba

_______B______项目。 80．同正规式（a|b）*等价的正规式为（ D ）

A．(a|b)+ B．a*|b* C．(ab)* A．归约 B．移进 C．接受 D．待 D．(a*|b*)+

约 共 4 页 第 1 页

81．词法分析器的加工对象是（ C ） 89．一个文法G，若________C____________，

A．中间代码 B．单词 C．源程序

则称它是LL（1）文法。 D．元程序

82．在自上而下的语法分析中，应从（ C ）A．G中不含左递归 开始分析。

B．G无二义性 A．句型 B．句子 C．文法开始符号

D．句柄 C．G的LL（1）分析表中不含多重定义的条目 83．赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示

D．G中产生式不含左公因子 是（ C ）

E. Xab+cd-/-bc*a+-:= 90．LR分析器的核心部分是一张分析表，该表F. Xab+/cd-bc*a+--:=

由_______D___________组成。 G. Xab+-cd-/ a bc* +-:=

H. Xab+cd-/abc* +--:= A．ACTION表 B．GOTO表 C．预84．编译程序不能检查、处理的错误是程序中的_______B_________。

测分析表 D．ACTION表和GOTO表 91．构造编译程序应该掌握

A．静态语义检查 B．动态语义检查

_______D__________。

C．语法错误 D．词法错误

A．源程序 B．目标语言 C．编译方

85．在LR（0）的ACTION子表中，如果某一

法 D．以上三项都是

行中有标记为“rj”的栏，则_______C__________。

92．在递归子程序方法中，若文法存在左递归，

A．该行既有rj又有Sj B．其它

则会使分析过程产生___D__________。

行也有rj

A．回溯 B．非法调用 C．有限次

6

《编译原理》复习题

调用 D．无限循环

93．最左简单子树的叶结点，自左至右排列组成句型的________C____________。

C．确定使用哪一个产生式进行展开 D．确定是否推导

100．称正规式R1和R2 等价是指

A．短语 B．句型 C．句柄 __________C_______________ 。 D．间接短语

94．如果一个正规式所代表的集合是无穷的，则它必含有的运算是__________C___________。 A．连接运算“· ” B．或运算“|” C．闭包运算“* ” D．括号“（”和“）” 95．同正规式

a*b*等价的文法是

二、填空题 概述部分：

1．编译程序的开发常常采用自编译、 交叉编96．由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为______B________。

A．语言 B．句型 C．句子 D．句

程序 。

柄

97．四元式之间的联系是通过 _______B____________实现的。

3．如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为3个阶段： 编译阶段 、 汇译 、 自展 和移植等技术实现。

2．解释程序和编译程序的区别在于 是否生成目标A．R1和R2都是定义在同一个字母表上的正规式

B．R1和R2使用的运算符相同 C．R1和R2代表同一个正规集 D．R1和R2代表不同的正规集

________C___________。

A．G1：S→aS|bS|ε B．G2：S→aSb|ε C．G3：S→ aS|Sb|ε D．G4： S→ abS|ε

A．指示器 B．临时变量 C．符号表

编阶段 和 运行阶段 。

D．程序变量

98．编译程序的语法分析器必须输出的信息是________A____________。

4．编译程序工作过程中，第一阶段输入是 源程序 ，最后阶段的输出为 目标程序 。

A．语法错误信息 B．语法规则信息

5．编译过程通常可分为5个阶段 词法分析阶段 、

C．语法分析过程 D．语句序列

99．LL（1）分析法中“1”的含义是在输入串中查看一个输入符号，其目的是_______C___________。

6．如果编译阶段生成的目标程序是某特定计算机

A．确定最左推导 B．确定句柄

7

语法分析阶段 、 语义分析和中间代码生成阶段 、优化阶段和目标代码生成阶段。

系统的机器代码程序，则源程序的执行分为两大阶

《编译原理》复习题

段： 编译阶段 和 运行阶段 。

7．对编译程序而言，输入数据是 源程序 ，输出结果是 目标程序 。

8．NFA和DFA的区别主要有两点：其一是 NFA可以有若干个初始状态，而DFA仅有一个初始状态 ；其二是 NFA的状态转换函数f不是单值函

8．贯穿于编译程始终的工作有 符号表处理 和出错处理。

词法分析部分：

1．词法分析的工作是将源程序中的 字符串 变换成 单词符号流 的过程，所遵循的是语言的 构词规则 。

2．若两个正规式所表示的 正规集 相同，则认为二者是等价的。

3．若两个正规式所表示的正规集相同，则认为二

4．规范归约是 最右推导 的逆过程。

者是 等价 的。

5．自下而上语法分析中分析器的动作有_移4．正规式R1和R2等价是指_______表示相同的正规集 。

5．词法分析器的输入是源程序字符串，输出结构是 二元式（单词种别， 单词自身的值） 。词法分析所遵循的是语言的 构词 规则。

7．常用的自上而下语法分析方法有递归下降子程6．确定的有限自动机是一个五元组，包含的五个

序方法和预测分析表方法（LL（1）方法）。

元分别是：状态集合、 字母表、初态、终态集、

8．常用的自下而上语法分析方法有算符优先分析

状态转换函数集合 。

法和LR分析法。

7．有限自动机是更一般化的状态转换图，它分为

9．一个LL(1)分析器由 一张LL(1)分析表（预测确定的有限自动机DFA 和 非确定的有限自动

分析表） 、 一个先进后出分析栈 和一个

机NFA 两种。

控制程序（表驱动程序）组成。

8

数，而是一个多值函数 。

语法分析部分：（基本概念、LL（1）、LR（0）、SLR（1）、递归下降子程序）

1． 语法分析的方法通常分为两类： 自上而下分析方法 和 自下而上分析方法 。 2．文法中的终结符集和非终结符集的交集是 空集 。

3．一个句型的最左直接短语称为该句型的___句柄________________。

进 、____归约 、__接受_ 、__报错 __。 6．自上而下语法分析中分析器的动作有___匹配终结符____、__展开非终结符_、__分析成功、报错__。