编译原理练习题.docx
- 文档编号:18616361
- 上传时间:2023-08-20
- 格式:DOCX
- 页数:21
- 大小:185.72KB
编译原理练习题.docx
《编译原理练习题.docx》由会员分享,可在线阅读,更多相关《编译原理练习题.docx(21页珍藏版)》请在冰点文库上搜索。
编译原理练习题
“编译原理”练习题
一、选择题
1、汇编程序是将a翻译成b,编译程序是将c翻译成d.
a.汇编语言程序b.机器语言程序c.高级语言程序
d.a或者be.a或者cf.b或者c
2、下面关于解释程序的描述正确的是b.
(1)解释程序的特点是处理程序时不产生目标代码
(2)解释程序适用于COBOL和FORTRAN语言
(3)解释程序是为打开编译程序技术的僵局而开发的
a.
(1)
(2) b.
(1) c.
(1)
(2)(3) d.
(2)(3)
3、高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段,而解释程序通常缺少
(1)e和
(1)b.其中,
(1)e的目的是使最后阶段产生的目标代码更为高效.与编译系统相比,解释系统
(2)d.解释程序处理语言时,大多数采用的是(3)b方法.(4)a就是一种典型的解释型语言.
(1):
a.中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化
(2):
a.比较简单,可移植性好,执行速度快
b.比较复杂,可移植性好,执行速度快
c.比较简单,可移植性差,执行速度慢
d.比较简单,可移植性好,执行速度慢
(3):
a.源程序命令被逐个直接解释执行b.先将源程序转化为之间代码,再解释执行
c.先将源程序解释转化为目标程序,在执行d.以上方法都可以
(4):
a.BASICb.Cc.FORTRANd.PASCAL
4、用高级语言编写的程序经编译后产生的程序叫b.用不同语言编写的程序产生b后,可用g连接在一起生成机器可执行的程序.在机器中真正执行的是e.
a.源程序 b.目标程序 c.函数 d.过程
e.机器指令代码 f.模块 g.连接程序 h.程序库
5、要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容:
c,d,f.
a.汇编语言 b.高级语言 c.源语言 d.目标语言
e.程序设计方法 f.编译方法 g.测试方法 h.机器语言
6、由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成
(1)d,
诸阶段的工作往往是
(2)d进行的.
(1)a.过程 b.程序 c.批量 d.遍
(2)a.顺序 b.并行 c.成批 d.穿插
7、编译过程中,语法分析器的任务就是b.
(1)分析单词是怎样构成的
(2) 分析单词串是如何构成语句和说明的
(3)分析语句和说明是如何构成程序的 (4)分析程序的结构
8、编写一个计算机高级语言的源程序后,到正式上机运行之前,一般要经过b这几步.
(1)编辑
(2)编译 (3)连接 (4)运行
9、编译程序必须完成的工作有a.
(1)词法分析
(2)语法分析 (3)语义分析
(4)代码生成 (5)之间代码生成 (6)代码优化
a.
(1)
(2)(3)(4) b.
(1)
(2)(3)(4)(5) c.
(1)
(2)(3)(4)(5)(6)
d.
(1)
(2)(3)(4)(6) e.
(1)
(2)(3)(5)(6)
10、编译程序是一种B。
A.汇编程序B.翻译程序C.解释程序D.目标程序
11、按逻辑上划分,编译程序第二步工作是C。
A.语义分析B.词法分析C.语法分析D.代码优化
12、通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括C。
A.模拟执行器 B.解释器 C.表格处理和出错处理 D.符号执行器
13、文法G所描述的语言是C的集合。
A.文法G的字母表V中所有符号组成的符号串
B.文法G的字母表V的闭包V*中的所有符号串
C.由文法的开始符号推出的所有终极符串
D.由文法的开始符号推出的所有符号串
14、乔姆斯基(Chomsky)把文法分为四种类型,即0型、1型、2型、3型。
其中3型文法是B。
A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法
15、文法G[N]=({b},{N,B},N,{N→b│bB,B→bN}),该文法所描述的语言是
C。
A.L(G[N])={bi│i≥0}B.L(G[N])={b2i│i≥0}
C.L(G[N])={b2i+1│i≥0}D.L(G[N])={b2i+1│i≥1}
16、一个句型中的最左B称为该句型的句柄。
可选项有:
A.短语B.简单短语C.素短语D.终结符号
17、设G是一个给定的文法,S是文法的开始符号,如果S
x(其中x∈V*),则称x是文法G的一个B。
A.候选式B.句型C.单词D.产生式
18、一个上下文无关文法G包括四个组成部分,它们是:
一组非终结符号,一组终结符号,一个开始符号,以及一组D。
A.句子B.句型C.单词D.产生式
19、文法G[E]:
E→T∣E+T
T→F∣T﹡F
F→a∣(E)
该文法句型E+F﹡(E+T)的简单短语是下列符号串中的B。
①(E+T)②E+T③F④F﹡(E+T)
可选项有:
A)①和③B)②和③C)③和④D)③
20、若一个文法是递归的,则它所产生的语言的句子A。
A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量
21、词法分析器用于识别C。
A.句子B.句型C.单词D.产生式
22、在语法分析处理中,FIRST集合、FOLLOW集合、SELECT集合均是B。
A.非终极符集B.终极符集C.字母表D.状态集
23、编译程序中语法分析器接收以A为单位的输入。
A.单词B.表达式C.产生式D.句子
24、在自底向上的语法分析方法中,分析的关键是A。
A.寻找句柄B.寻找句型C.消除递归D.选择候选式
25、在LR分析法中,分析栈中存放的状态是识别规范句型C的DFA状态。
A.句柄B.前缀C.活前缀D.LR(0)项目
26、词法分析的任务是(A)
A.识别单词 B.分析句子的含义 C.识别句子 D.生成目代码
27、代码优分的目的是(C)
A.节省时间 B.节省空间 C.节省时间和空间 D.把编译程序进行等价交换
28、代码生成阶段的主要任务是(C)
A.把高级语言翻译成汇编语言
B.把高级语言翻译成机器语言
C.把中间代码变换成依赖具体机器的目标代码
D.把汇编语言翻译成机器语言
29、在LR分析法中,分析栈中存放的状态是识别规范句型C的DFA状态。
A.句柄B.前缀C.活前缀D.LR(0)项目
30、一个上下文无关文法G包括四个组成部分,它们是:
一组非终结符号,一组终结符号,一个开始符号,以及一组D。
A.句子B.句型C.单词D.产生式
二、是非判断题
1、正规文法产生的语言都可以用上下文无关文法来描述。
(×)
2、如果一个文法是递归的,则其产生的语言的句子是无穷个。
(√)
3、文法的二义性和语言的二义性是两个不同的概念。
(√)
4、一个LL(l)文法一定是无二义的。
(√)
5、在规范规约中用最左素短语来刻划可归约串。
(×)
6、目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。
(√)
7、编译程序是对汇编程序的翻译。
(×)
8、计算机高级语言翻译成低级语言只有解释一种方式。
(×)
9、在编译中进行语法检查的目的是为了发现程序中所有错误。
(×)10、甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
(×)
11、正则文法其产生式为Aa,ABb,A,B∈VN,a、b∈VT。
(√)
12、每个文法都能改写为LL
(1)文法。
(×)
13、递归下降法允许任一非终极符是直接左递归的。
(×)
14、算符优先关系表不一定存在对应的优先函数。
(√)
15、自底而上语法分析方法的主要问题是候选式的选择。
(×)
16、LR法是自顶向下语法分析方法。
(×)
18、若一个句型中出现了某产生式的右部,则此右部一定是该句型的句柄。
(×)
19、一个句型的句柄一定是文法某产生式的右部。
(√)
20、在程序中标识符的出现仅为使用性的。
(×)
21、在程序中标识符的出现仅为使用性的。
(×)
三、名词解释题
1、简单短语:
设G[Z]是给定文法,w=xuy∈V+,为该文法的句型,如果满足下面两个条件:
①Z
xUy;
②Uu;
则称句型xuy中的子串u是句型xuy的简单短语(或直接短语)。
2、句柄:
一个句型中的最左简单短语称为该句型的句柄。
3、活前缀:
若S′
αAωαβω是文法G′中的一个规范推导,G′是G的拓广文法,符号串γ是αβ的前缀,则称γ是G的,也是G′的一个活前缀。
其中S'为文法开始符号。
或:
可归前缀的任意首部。
4、LR(0)项目:
把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。
5、语义规则:
对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则。
6、LL
(1)文法的定义
答:
一个上下文无关文法是LL
(1)文法的充分必要条件是每个非终结符A的两个不同产生式,A→α,A→β;满足SELECT(A→α)∩SELECT(A→β)=Ф。
其中,α、β不能同时
ε。
7、活动记录:
为了管理过程在一次执行中所需要的信息,使用一个连续的存储块,这样一个连续的存储块称为活动记录。
8、递归下降法
答:
对每个非终结符按其产生式结构写出相应语法分析子程序。
因为文法递归相应子程序也递归,子程序的结构与产生式结构几乎一致。
所以称此种方法称为递归子程序法或递归下降法。
9、基本块的DAG:
一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。
(1)图的叶结点(没有后继的结点)以一标识符(变量名)或常数作为标记,表示该结点代表该变量或常数的值。
如果叶结点用来代表某变量A的地址,则用addr(A)作为该结点的标记。
通常把叶结点上作为标记的标识符加上下标0,以表示它是该变量的初值。
(2)图的内部结点(有后继的结点)以一运算符作为标记,表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
(3)图中各个结点上可能附加一个或多个标识符,表示这些变量具有该结点所代表的值。
10、自底向上分析法的原理
答:
在采用自左向右扫描,自底向上分析的前提下,该类分析方法是从输入符号串入手,通过反复查找当前句型的句柄(最左简单短语),并使用文法的产生式把句柄归约成相应的非终极符来一步步地进行分析的。
最终把输入串归约成文法的开始符号,表明分析成功。
11、L-属性文法:
L-属性文法要求对于每个产生式AX1X2…Xn,其每个语义规则中的每个属性或者是综合属性,或者是Xj的一个继承属性,且该属性仅依赖于:
(1)产生式Xj的左边符号X1,X2…Xj-1的属性;
(2)A的继承属性。
12、文法的左递归?
答:
一个文法含有下列形式的产生式之一时:
1)A→Aβ,A∈VN,β∈V*
2)A→Bβ,B→Aα,A、B∈VN,α、β∈V*
则称该文法是左递归的。
13、在一个属性文法中,对应于每个产生式A→a都有一套与之相关联的语义规则,每条规则的形式为
b:
=f(c1,c2…,ck),其中对于b的要求是什么?
答:
语义规则中的左部属性变量b被规定为只能是下述两种变量:
1对应产生式左部符号的综合属性变量;
2对应产生式右部符号的继承属性变量。
四、简答计算题
1、已知文法G[E]为:
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
①该文法的开始符号(识别符号)是什么?
②请给出该文法的终结符号集合VT和非终结符号集合VN。
③找出句型T+T*F+i的所有短语、简单短语和句柄。
答:
①该文法的开始符号(识别符号)是E。
②该文法的终结符号集合VT={+、-、*、/、(、)、i}。
非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;
简单短语为i、T*F、第一个T;句柄为第一个T。
2、已知文法G[S]为:
S→dAB
A→aA|a
B→Bb|ε
①G[S]产生的语言是什么?
②G[S]能否改写为等价的正规文法?
答:
①G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。
②G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为:
Sˊ→dA
A→aA|aB|a
B→bB|b
3、为正规式(a|b)*a(a|b)构造一个等价的确定的有限自动机。
答:
4、给定下列自动机,将其转换为确定的自动机。
答:
(1)消除ε边,得到NFA:
(2)确定化,得到DFA:
+
―
D
·
+
―
d
·
S
A
B
C
D
E
G
H
A
A
BCE
BCE
B
C
D
E
H
H
G
D
G
+[SA]
[A]
[BCE]
[G]
[DG]
[H]
[DH]
[A]
[A]
[BCE]
[BCE]
[BCE]
[H]
[DH]
[H]
[DH]
[G]
[G]
[DG]
5、消除下列文法G[E]的左递归。
E→E-T∣T
T→T/F∣F
F→(E)∣i
答:
消除文法G[E]的左递归后得到:
E→TE’
E’→-TE’∣ε
T→FT’
T’→/FT’∣ε
F→(E)∣i
6、给定文法G[Z]:
a)构造此文法的LR(0)项目集规范族,并给出识别活前缀的DFA。
b)构造其SLR
(1)分析表。
答:
1.首先拓广文法:
在G中加入产生式0.Z′→Z,然后得到新的文法G′,再求G′的识别全部活前缀的DFA:
2.Follow(Z)={#}
Follow(C)={i}
Follow(S)={#}
Follow(E)={#,∨,then}
Follow(A)={=,#,∨,then}
则可构造SLR
(1)分析表为:
ACTION
GOTO
0
if
then
=
∨
i
#
Z
C
S
E
A
0
S3
1
2
1
OK
2
S6
4
5
3
S6
7
8
4
r1
5
S9
6
r6
r6
r6
r6
7
S10
S11
8
r5
r5
r5
9
S6
12
8
10
r2
11
S6
13
12
S11
r3
13
r4
r4
r4
7、设有文法G[S]:
S→aA
A→Ab
A→b
求识别该文法所有活前缀的DFA。
答:
(1).首先拓广文法:
在G中加入产生式0.S′→S,然后得到新的文法G′:
0.S′→S
1.S→aA
2.A→Ab
3.A→b
(2).再求G′的识别全部活前缀的DFA:
8、对于文法G(E):
ET|E+T
TF|T*F
F(E)|i
1)写出句型(T*F+i)的最右推导并画出语法树。
2)写出上述句型的短语,直接短语和句柄。
答:
1.)
ETF(E)(E+T)(E+F)
(E+i)(T+i)(T*F+i)
2)
短语:
(T*F+i),T*F+i,T*F,i
直接短语:
T*F,i
句柄:
T*F
9、构造下面文法的LL
(1)分析表。
SaBS|bAS|
AbAA|a
BaBB|b
答:
开始符号集合和后继符号集合LL
(1)分析表
First
Follow
S
a,b,
$
A
a,b
a,b,$
B
a,b
a,b,$
a
b
$
S
SaBS
SbAS
S
A
Aa
AbAA
B
BaBB
Bb
五、综合题
1、通过构造识别活前缀的DFA和构造分析表,来证明文法EE+id|id是SLR
(1)文法。
答:
先给出接受该文法活前缀的DFA如下:
再构造SLR分析表如下:
动作
转移
id+$
E
0
s2
1
1
s3acc
2
r2r2
3
s4
4
r1r1
表中没有多重定义的条目,因此该文法是SLR
(1)的。
2、为下面文法构造规范LR
(1)分析表,画出像教材上图3.20这样的状态转换图就可以了。
SV=E|E
VE|id
EV
(2)上述状态转换图有同心项目集吗?
若有,合并同心项目集后是否会出现动作冲突?
答:
(1)状态转换图如下:
(2)合并同心项目集(I4和I11,I5和I12,I7和I13,I8和I10)后没有动作冲突。
3、给定文法:
EE+id|id
要求:
(a)构造识别活前缀的DFA;
(b)构造分析表,并说明该文法是否为SLR
(1)文法;
(c)假定输入串为id+id+id,请给出分析过程。
答:
先给出接受该文法活前缀的DFA如下:
(a):
(b):
构造SLR分析表如下:
动作
转移
id+$
E
0
s2
1
1
s3acc
2
r2r2
3
s4
4
r1r1
表中没有多重定义的条目,因此该文法是SLR
(1)的。
(c):
假定输入串为id+id+id,请给出分析过程。
栈
输入
动作
0
id+id+id$
移进
0id2
+id+id$
按Eid归约
0E1
+id+id$
移进
0E1+3
id+id$
移进
0E1+3id4
+id$
按EE+id归约
0E1
+id$
移进
0E1+3
id$
移进
0E1+3id4
$
按EE+id归约
0E1
接收
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 练习题