《编译原理》复习题
则中的*和+分别是常规意义下的算术运算符）： 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．自上而下语法分析中分析器的动作有___匹配终结符____、__展开非终结符_、__分析成功、报错__。