编译原理复习题-给学生(简) 下载本文

《编译原理》复习题

则中的*和+分别是常规意义下的算术运算符): 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.自上而下语法分析中分析器的动作有___匹配终结符____、__展开非终结符_、__分析成功、报错__。