小数点的移动-教育调查报告

期末考试试卷
（A）卷
一、
填空题（每小题2分，共20分）

1、字母表∑，用∑ 表示∑上所有有穷长的串集合，∑称为∑的 ① 。
2、设z=abc，则z的固有头是 ① 。
3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫
① 。
4、设＝{a,b}， 上的正规式(a|b)(a|b) 相应的正规集为 ①
5、NFA的映象f是从状态×字映射到状态子集，f为 ① 值函数。
6、LR分析是按规范句型的 ① 为可归约串。
7、结点的 ① 属性值由该结点的兄弟结点和父结点的属性值计算。
8、如果分析树中一结点的属性b依赖于属性c， 那么这个结点的属性b的语义规
则的计算必须在定义属性c的语义规则的计算 ① 。
9、对于栈式符号表，引入一个显示嵌套层次关系表- ① 表，该表总是
指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。
10、任一有向边序列n1 → n2,n2 → n3,„,nk-1 → nk为从结点n1到结点nk
的一条通路。如果n1=nk，则称该通路为 ① 。
二、单项选择（每小题2分，共14分）
1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。其中3型文法也称
为（ ）。
A．上下无关文法 B.正规文法
C．上下文有关文法 D.无限制文法
2、生成非0开头的正偶数集的文法是（ ）。
A． Z::=ABC B. Z::=ABC
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|ε B::=BA|B0|0
A::=1|2|3|„|9 A::=1|2|3|„|9
C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|0 B::=BA|B0|ε
试卷第 1 页 共 11 页
**

A::=1|2|3|„|9 A::=1|2|3|„|9
3、简单优先分析法从左到右扫描输入串,当栈顶出现（ ）时进归约。
A.素短语 B.直接短语 C.句柄 D.最左素短语
4、同心集合并有可能产生新的（ ）冲突。
A.归约 B.移进／移进 C.移进／归约 D.归约／归约
5、在编译中，动态存储分配的含义是（ ）。
A．在运行阶段对源程序中的量进行存储分配
B. 在编译阶段对源程序中的量进行存储分配
C. 在说明阶段对源程序中的量进行存储分配
D. 以上都不正确
6、活动记录中的连接数据不包含（ ）。
A.老SP B.返回地址 C.全局DISPLAY地址 D形式单元
7、有一语法制导翻译如下：
S→bAb {printer(“1”)}
A→(B {printer(“2”)}
A→a {printer(“3”)}
B→Aa) {printer(“4”)}
若输入序列为b(((aa)a)a)b，且采用自下而上的分析法，则输出序列为( )。
A．32224441 B．34242421 C．12424243 D．34442212
三、写出条件语句 IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列（6
分）





四、设有基本块 （8分）

B1： B:=3

D:=A+C

E:=A*C

F:=D+E
G:=B*F
H:=A+C
I:=A*C
J:=H+I
K:=B*5
(1) 画出DAG图；
(2) 假设只有L在基本块后被引用，请写出优
化后的四元序列。

试卷第 2 页 共 11 页

五、将下图DFA最小化，并写出最小化后DFA的正规式。（10分）
c

b
a b

6
1 3
d
c b
5
b
d
b
a a
2 4

7
b

六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。（15分）
S Aa|b
A SB
B ab
七、已知文法:
SS；G|G
GG（T）|H
Ha|(S)
TT+S|S
求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语（12分）
八、【 注意】计算机061062班和计教061062请做第1、2题，计算机063（海外
班）请做第3题 ，做错题得0分。（15分）
【计算机061062班和计教061062班做】
1、给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。（5分）
G[S]为： (1) E E+T (2) E T (3) T T*F
(4) T F (5) F (E) (6) F a
2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。（10分）
G[M]: 1) M →VbA 2) V →d 3) V →ε
试卷第 3 页 共 11 页

4) A →a 5) A →Aba 6) A →ε


0
1
2
3
4
5
6
7
8
ACTION
b
r3

S4
r2
r6
r4
S7

r5
d
S3








a




S5


S8

#

acc


r6
r4
r1

r5
GOTO
M
1








A




6




V
2








【计算机063海外班做】
3、判断下列各题所示是否为LR类文法，若是请说 明是LR(0)，SLR(1)，LALR(1)
或LR(1)的哪一种，并构造相应分析表。（15分 ）
SaAdeBdaBreAr
Aa
Ba











试卷第 4 页 共 11 页

答案：
一、填空题（每空2分，共20分）
1、 闭包 2、 ε， a， ab 3、 语法 4、 ｛aa，bb,ab,ba}
5、 多 6、 句柄 7、 继承 8、 之后
9、 DISPLAY 10、 环路
二、
单项选择（每小题2分，共14分）
题号
答案

1
B
2
D
3
C
4
D
5
A
6
D
7
B
三、写出条件语句 IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列（6分）

解： ① (j>,a ,0 ,③ ) 评分标准：标号对给1分，
② (j, , , ⑥) 四元式格式对给1分，
③ (+,x ,1 ,T1) 每2条四元式序列对给1分。
④ (:= ,T1, , T2 )
⑤ (j , , , ⑨ )
⑥ (- ,x, 1,T3)
⑦ (*,4,T3, T4 )
⑧ (:= ,T4 , , x)
⑨
四、 设有基本块 （8分）
(1) 画出DAG图；
(2) 假设只有L在基本块后被引用，请写出优化后的四元序列。


评分标准：DAG图正确给4分，代码每条1分。
解：（1）对于B1其DAG图：

试卷第 5 页 共 11 页

n9
+
L,M
G
n7
*
n6
+
F,J
n4
D,H
n5
E,I
+
K
n8
15
3
B
n1
A
n2 n3
C
*

若只有L活跃，则代码为
D:=A+C
E:=A*C
F:=D+E
L:=F+15
五、将下图DFA最小化，并写出最小化后DFA的正规式。（10分）
解：P0=({6,7},{1,2,3,4,5})
P0=({6,7},{1,2}，{3,4,5}) 输入b进入不同状态。
P0=({6,7},{1,2}，{3,4},{5}) 3，4对d有定义，5没有定义
最小化DFA如下：
b c
b

a b


1 3
6
d
a
5
正规式为：b*a(c|da)*bb*
评分标准：划分状态集过程给3分，图对得 5分，图部分对根据对的多少给2-4
分，正规上式对给2分。
六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。（15分）
S Aa|b
A SB
B ab
【解法1】 first(S)={b} first(A)={b} first(B)={a}
follow(S)={#,a} follow(A)={a} follow(B)={a}
select(SAS)=first(AS)={b} select(Sb)=first(b)={b}
试卷第 6 页 共 11 页

select(SAS)∩select(Sb)={b}≠φ
所以该文法不是LL（1）文法
改写为： S Aa|b S SBa|b
A SB A SB
B ab B ab
消除左递归： S bS’ 化简得： S b S’
S Ba S’|ε S’ Ba S’|ε
A SB (多余) B ab
B ab
first(S)={b} first(S’)={a,ε} first(B)={a}
follow(S)={#} follow(S’)={#} follow(B)={a}
select(SbS’)=first(bS’) ={b} select(S’BaS’)=first(BaS’)={a}
select(S’ε)=first(ε)Ufollow(S’)={#, ε}
select(S’BaS’)∩select(S’ε)=φ
所以改写后是LL(1)文法。
评分标准：改写前判断LL（1）全对4分，改写正确4分， 改写后判断LL（1）正确得
6分，最后结论1分。
【解法2】

first(S)={b} first(A)={b} first(B)={a}
follow(S)={#,a} follow(A)={a} follow(B)={a}
select(SAS)=first(AS)={b} select(Sb)=first(b)={b}
select(SAS)∩select(Sb)={b}≠φ
所以该文法不是LL（1）文法

用S的产生式右部代替A的产生式右部的S得：
S→Aa|b A→AaB|bB B→ab
消除左递归后文法变为：
0) S→A a 1) S→b 2) A→b B N
3) N→a B N 4) N→ε 5) B→a b
非终结符 FIRST集 FOLLOW集
S {b} {#}
A {b} {a}
B {a} {a}
N {a,ε} {a}
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠φ
SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠φ
所以文法不是LL(1)的。
评分标准：改写前判断LL（1）全对4 分，改写正确4分，改写后判断LL（1）正确得
6分，最后结论1分。
七、已知文法:
SS；G|G
试卷第 7 页 共 11 页

GG（T）|H
Ha|(S)
TT+S|S
求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语（12分）
解：语法图见下图
短语有：
a 相对非终结符 H、G 短语
T+S 相对非终结符 T短语
H 相对非终结符 G短语
(S) 相对非终结符 H、G短语
a(T+S) 相对非终结符 G短语
a(T+S);H 相对非终结符 S短语
a(T+S);H;(S) 相对非终结符 S短语
句柄是 a
素短语 a，T+S，（S）
最左素短语 a

S
S
S ；
；
G
G
H
G
G （ T ）
H （ S ）
H T + S
a
分。

评分标准：语法图正确4分 ，短语正确5分，句柄正确1分，素短语正确1分，最左素短语正确1
八、
1、给出文法G[S ]的LR(1)项目集规范族中I
0
项目集的全体项目。（5分）
G[S]为： (1) E E+T (2) E T (3) T T*F
试卷第 8 页 共 11 页

(4) T F (5) F (E) (6) F a
解：
I0：
S’E ， #
E E+T ， #,+
E T ， #,+
T T*F ， #,+,*
T F ， #,+,*
F  (E) ， #,+,*
F a ， #,+,*

评分标准：前4条项目，每条0.5分，后面3条下面。每条1分

2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。（10分）
G[M]: 1) M →VbA 2) V →d 3) V →ε
4) A →a 5) A →Aba 6) A →ε
解：
对串dbba#的分析过程如下表
对输入串dbba#的分析过程
步骤
1
2
3
4
5
6
7
8
9
状态栈
0
03
02
024
0246
02467
024678
0246
01
文法符号栈 剩余输入符号 动作
# dbba# 移进
#d bba# 用V →d归约
#V bba# 移进
#Vb ba# 用A →ε归约
#VbA ba# 移进
#VbAb a# 移进
#VbAba # 用A →Aba 归约
#VbA # 用M →VbA 归约
#M # 接受
评分标准：每条1分，格式1分。
3、判断下列各题所示是否为LR类文法，若是请说明是L R(0)，SLR(1)，LALR(1)或
LR(1)的哪一种，并构造相应分析表。（15分）
SaAdeBdaBreAr
Aa
Ba
解：LR(0)项目集规范族如图：
试卷第 9 页 共 11 页

I1： I4：
S
I0：
S’·S
S·aAd
S·eBd
S·aBr
S·eAr
S’S·
A
B
SaA·d

I5：
SaB·r
I2：
a
Sa·Ad
Sa·Br
A·a
a
I6：
Aa·
Ba·
e
B·a
I3：
Se·Bd
Se·Ar
A·a
B·a


在状态I6中有“规约-规约”冲突，且Follow(A) =follow(B)={d,r}故不是LR(0)和
SLR(1)。
文法LR(1)项目集规范族如下：
I4：
I1： SaA·d ,#

d
I10：
SaAd· ,#

S
I0：
S’·S ，#
S·aAd ，#
S·eBd ，#
S·aBr ，#
S·eAr ，#
S’S· ，#
I2：
A
B
I5：
SaB·r ,#
I6：
Aa· ,d
r
I11：
SaBr· ,#
a
Sa·Ad ，#
Sa·Br ，#
A·a ，d
a
a
Ba· ,r
I7：
Aa· ,r
Ba· ,d
e
B·a ,r
I3：
Se·Bd ,#
Se·Ar ,#
A·a ,r
B·a ,d
B
A
I8：
SeB·d ,#
I9：
SeA·r ,#
d
I12：
SeBd· ,#
r
I13：
SeAr· ,#

在状态I6、I7中有“规约- 规约”冲突，但归依项目的向前搜索符集不相交，故文
法是LR(1)。
试卷第 10 页 共 11 页

I6，I7是同心集，若合并，则合并后的状态I6，I7有项目：
Aa· ,rd
Ba· ,dr
向前搜索符集相交，故文法不是LALR(1)。
因此，本文法是LR(1)文法。
评分标准：LR（0）和SLR（1）的判断正确给4分，LR（0）和SLR（1）的结论1分，
L R(1)项目集规范族正确的给6分，判断LALR（1）同心集正确给2分，LALR（1）结论
1分 ，LR（1）结论1分。

试卷第 11 页 共 11 页

土家族习俗-浙江国税

怀念父亲的诗-六一黑板报

雷锋的名人名言-保密协议书范本

杨馥伟-人事专员工作职责

说岳全传读后感-太原市卫生局

河南工程学院分数线-会计实习单位鉴定

孝心作文-感动中国文章

我爱你韩文怎么写-幼儿园德育工作总结