2023年12月20日发(作者：)
一、画图( 每题参考分值5分 )
1、设有布尔表达式文法G【B】： B→B or T | T
T→T and F | F
F→not F | （B） | true | false
给出句型 true and not false or F的语法树，以及所有直接短语、句柄。
正确答案：
直接短语：true
false
F
句 柄 ：true
2、设有基本块： t1＝3*A
t2＝2*C
t3＝t1＋t2
t4＝t3十5
t5＝2*C
t6＝3*A
t7＝t6＋t5
M＝t7－1
N＝t4－M
1．画出DAG图；
2．假设只有M，N在基本块后面还要被引用，请写出优化后的代码序列。
正确答案：
答：
DAG：
优化后的代码
1． t1＝3*A
2． t2＝2*C
3． t3＝t1＋t2
4． t4＝t3＋5
5． M＝t3－1
6． N＝t4－M
3、设有布尔表达式文法G【B】： B→B or T | T
T→T and F | F
F→not F | （B） | true | false
给出句子 （ true or false）and not false的推导和语法树。
正确答案：
解：
B T T and F F and F （B）and F （B or T）and F
（T or T）and F
（true or F）and F
（F or T）and F （true or T）and F
（true or false ）and F
（ true or false）and not false （true or false ）and not F
4、将赋值语句x=a * b＋c *（d＋e * f / g）*h 翻译为相应的逆波兰式和四元式
正确答案：
答：
逆波兰式： x a b * c d e f * g / ＋ * h * ＋ ＝
四元式：⑴ （*，a， b，t1）
⑵ （*，e， f，t2）
⑶（/，t2， g，t3）
⑷（＋，d， t3，t4）
⑸（*，c，t4，t5）
⑹（*，t5，h， t6）
⑺（＋，t1， t5， t6）
(8)（＝，t6， ，x）
5、构造下面文法的预测分析表（LL（1）分析表）
G【
X →d ; X | s Y
Y →; s Y |
正确答案：
答：
分析表（每个2分，共10分）
begin
P
d
s
；
end
#
P begin
d
；X end
X
X
X
Y
YsY
6、将语句 if x > 2 and x < 20 then y = x * 10 else y = x + 6 表示为相应的四元式。
d
；XsY
；Ye
正确答案：
⑴ （j>，x，2， ⑶ ）
⑵ （j， _， _，⑻ ）
⑶ （j<，x，20，⑸ ）
⑷ （j， _， _，⑻ ）
⑸ （*， x， 10，t1 ）
四元式：
⑹（=， t1， _，y ）
⑺（j， _， _，⑽ ）
⑻（＋， x， 6，t2 ）
⑼（=， t2， _， y ）
⑽ …
7、设有文法G【S】：S aBc|bAB A aAb|b B b|ε
构造其LL(1)分析表。
正确答案：
答：
因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}
分析表
S
A
B
8、对于下述文法G【A】： A→cAb | cAd | ε
1.构造识别其规范句型所有活前缀的DFA；
2.说明该文法是何种LR文法，并给出其相应的LR分析表。
a
SaBc
AaAb
b
S bAB
Ab
Bb
Bε
c
Bε
#
正确答案：
解：将文法拓广为:
G’[A’]： (0) A’ →A (1) A→cAb (2) A→cAd (3)A→ε
DFA
因为上述DFA的I0、I2状态集中有移进-归约冲突，
所以该文法不是LR(0)文法。
对于I0、I2中：
归约项目A→• 移进项目A→• cAb和A→• cAd
而：{ c} ∩ FOLLOW(A)= {c} ∩ { b，d，＃} ＝Φ
所以可用SLR(1)方法解决I0、I2的冲突。
所以该文法是SLR(1)文法。
分析表（6分,每行1分）
ACTION
b
c
d
#
GOTO
A
1
0
r3
S2
r3
r3
1
acc
3
2
r3
S2
r3
r3
3
S4
4
r1
5
r2
S5
r1
r1
r2
r2
9、将语句if x > y then x:=10 else x:= x + y 翻译为相应四元式。
正确答案：
解：四元式:
⑴ （j>，x， y，⑶ ）
⑵ （j， _， _，⑸ ）
⑶ （:=，10，_， x ）
⑷ （j， _， _，⑺ ）
⑸（＋， x， y，t1 ）
⑹（:=， t1， _，x ）
10、设文法G【S】： S→a | b |(T)
T→T,S | S
1. 改写文法，消除其文法中的直接左递归；
2．证明改写后的文法是LL（1）文法，并且构造其预测分析表。
正确答案：
答：
改写文法： S→a | b |(T)
T→S T’ S→，ST’| ε
分析表
a
S
T
T’
b
，
(
)
#
a
ST’
b
ST’
（T）
ST’
，ST’
e
二、单选( 每题参考分值2.5分 )
11、编译过程中，词法分析阶段的任务是 。
A.
识别表达式
B.
识别语言单词
C.
识别语句
D.
识别程序
错误:【B】
12、一个文法G是四元组，分别是：非终结符，终结符，开始符号，以及 。
A.
句子
B.
句型
C.
单词
D.
产生式
错误:【D】
13、LR语法分析栈中存放的状态是识别文法规范句型 的DFA状态。
A.
前缀
B.
活前缀
C.
句柄
D.
LR（0）项目
错误:【B】
14、堆式动态分配申请和释放存储空间遵守
原则。
A.
先申请先释放
B.
先申请后释放
C.
后申请先释放
D.
任意申请和释放
错误:【D】
15、循环优化是指对 中的代码进行优化。
A.
循环
B.
函数
C.
基本块
D.
整个程序
错误:【A】
16、过程的DISPLAY表中记录了 。
A.
过程的嵌套层次
B.
过程的连接数据
C.
过程的返回地址
D.
过程的入口地址
错误:【A】
17、有文法G[S]：S→aA|a|bB A→aS B→aB|bS 则____为L(G)中的句子。
A.
abab
B.
aababab
C.
abaa
D.
baaba
错误:【A】
18、无符号常数的识别与拼数工作通常在 阶段完成。
A.
语法分析
B.
语义分析
C.
词法分析
D.
代码优化
错误:【C】
19、正规表达式最适合描述 。
A.
语法
B.
语义
C.
词法
D.
程序变换
错误:【C】
20、中缀表达式a＋b*（c＋d）的逆波兰表示是____。
A.
abcd+*+
B.
ab+cd*+
C.
abc+*d+
D.
a+bc*d+
错误:【A】
21、对应Chomsky四种文法的四种语言之间的关系是 。
A.
L0L1L2L3
B.
L3L2L1L0
C.
L3=L2L1L0
D.
L0L1L2=L3
错误:【B】
22、词法分析器的输出结果是 。
A.
单词的种别码
B.
单词组符号表中的位置
C.
单词的种别码和单词的自身值
D.
单词的自身值
错误:【C】
23、____文法不是LL(1)的。
A.
递归
B.
右递归
C.
2型
D.
含有公共左因子的
错误:【D】
24、有文法G=({S}，{a}，{ S→SaS，S→ }，S)，该文法是____。
A.
LL(1)文法
B.
二义性文法
C.
算符优先文法
D.
SLR(1)文法
错误:【B】
25、自底向上语法分析法的原理是____。
A.
“移进——推导法”
B.
“最左推导法”
C.
“移进——归约法”
D.
“推导——归约法”
错误:【C】
26、设有如图所示的有穷自动机。其中状态①为初态，状态⑤为终态。假设digit代表数字0到9。则下述实数中 可被该有穷自动机接受。
A.
＋123
B.
一1．
C.
6
D.
一11．47
错误:【D】
27、在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 。
A.
终结符集
B.
非终结符集
C.
字母表
D.
状态集
错误:【A】
28、设G是一个给定的文法，S是文法的开始符号，如果S法G的一个____。
x(其中x∈V*),则称x是文A.
候选式
B.
句型
C.
产生式
D.
单词
错误:【B】
29、编译程序的语法分析器接受以____为单位的输入，并产生有关信息供以后各阶段使用。
A.
表达式
B.
产生式
C.
单词
D.
语句
错误:【C】
30、语言是 。
A.
句子的集合
B.
产生式的集合
C.
符号串的集合
D.
句型的集合
错误:【A】
31、在规范归约中，用 来刻划可归约串。
A.
直接短语
B.
句柄
C.
最左素短语
D.
素短语
错误:【B】
32、文法G【S】=（{b}，{S，B}，S，{S→b│bB，B→bS}），该文法所描述的语言____。
A.
L(G[S])={b2i+1│i≥0}
B.
L(G[S])={b2i+1│i≥1}
C.
L(G[S])={bi│i≥0}
D.
L(G[S])={b2i│i≥0}
错误:【A】
33、在产生式中，符号“→”（“::＝”）表示 。
A.
等于
B.
恒等于
C.
取决于
D.
定义为
错误:【D】
34、一个句型最左边的 称为该句型的句柄。
A.
短语
B.
素短语
C.
规范短语
D.
直接短语
错误:【D】
35、在编译程序常用的语法分析方法中，算符优先分析法属于 分析方法。
A.
自左至右
B.
自上而下
C.
自下而上
D.
自右向左
错误:【C】
36、四元式之间的联系是通过 实现的。
A.
指示器
B.
临时变量
C.
符号表
D.
程序变量
错误:【B】
37、程序基本块是指____。
A.
一个子程序
B.
一个仅有一个入口和一个出口的语句
C.
一个没有嵌套的程序段
D.
一组顺序执行的程序段，仅有一个入口和一个出口
错误:【D】
38、 算符优先文法G【S】: EE+T，T(E)|i 则关于优先级的判断正确的是____。
A.
+ •＞ (
B.
( •＞ (
C.
+ •＞ )
D.
( •＞ )
错误:【C】
39、不能被如下状态转换图识别的句子是 。
A.
a0b
B.
a1010b
C.
b00b
D.
ab
错误:【D】
40、代码优化时所依据的是 。
A.
等价变换规则
B.
词法规则
C.
语法规则
D.
语义规则
错误:【A】
41、FORTRAN语言中的存储分配策略是 。
A.
时钟分配策略
B.
最佳分配策略
C.
静态存储分配策略
D.
动态存储分配策略
错误:【C】
42、若a为终结符，则A→α·aβ是 项目。
A.
归约
B.
移进
C.
接收
D.
待约
错误:【B】
43、如果在文法G中存在一个句子，当其满足下列条件____时，则称该文法是二义性文法。
A.
该句子的最右推导唯一
B.
该句子有两个不同的最左推导
C.
该句子对应的语法树唯一
D.
该句子的最左推导和最右推导相同
错误:【B】
44、在状态转换图中，结点代表____，用圆圈表示。
A.
输入缓冲区
B.
向前搜索
C.
字符串
D.
状态
错误:【D】
45、算符优先分析法从左到右扫描输入串，当栈顶出现 时进行归约。
A.
素短语
B.
直接短语
C.
句柄
D.
最左素短语
错误:【D】
46、一个确定的有穷自动机DFA是一个 。
A.
五元组（K,Σ,f,S,Z）
B.
四元组（VN, VT,P,S）
C.
四元组（K,Σ,f,S）
D.
三元组（VN, VT,P）
错误:【A】
47、编译程序使用 区别标识符的作用域。
A.
说明标识符的过程或函数名
B.
说明标识符的过程或函数的静态层次
C.
说明标识符的过程或函数的动态层次
D.
标识符的行数
错误:【B】
48、活动记录中的连接数据不包含____。
A.
老SP
B.
返回地址
C.
形式单元
D.
全局DISPLAY地址
错误:【C】
49、基本块内的优化为_____。
A.
代码外提，删除归纳变量
B.
删除多余运算，删除无用赋值
C.
强度削弱，代码外提
D.
循环展开，循环合并
错误:【B】
50、文法G[S]：S→ab│aSb ，该文法所描述的语言____。
A.
L(G[S])={ anbn
│n≥0}
B.
L(G[S])={ ambn│m，n≥0}
C.
L(G[S])={ anbn│n≥1}
D.
L(G[S])={ ambn│m，n≥1}
错误:【C】
发布评论