江南大学《编译原理》试卷参考答案(2010A).doc
《江南大学《编译原理》试卷参考答案(2010A).doc》由会员分享，可在线阅读，更多相关《江南大学《编译原理》试卷参考答案(2010A).doc（9页珍藏版）》请在冰点文库上搜索。
江 南 大 学 考
2009―2010第二学期《编译原理》期末考试试卷（A）
使用专业、班级 学号 姓名
题 数
一
二
三
四
五
六
七
总 分
得 分
一、选择填空〖每空1分，共计20分〗
1．编译程序将源程序加工成目标程序是C之间的转换。
A．词法B．语法C．语义D．规则
2．开发一个编译程序应掌握D。
A．源语言B．目标语言C．编译技术D．以上三项都是
3．词法分析器的输出结果是B。
A．单词自身B．单词的机内符
C．单词的词义信息D．单词的词法信息
4．称有限自动机A1和A2等价是指D。
A．A1和A2都是定义在一个字母表Σ上的有限自动机
B．A1和A2状态数和有向边数相等
C．A1和A2状态数或有向边数相等
D．A1和A2所能识别的字符串集合相同
5．同正则表达式（a|b）+等价的正则表达式是B。
A．（a|b）*B．（a|b）（a|b）*
C．（ab）*（ab）D．（a|b）|（a|b）*
6．前后文无关文法G：
S→[S]|[]所产生的语言是D。
A．[m]n（m，n＞0）B．[m]n（m，n>1）
C．[m]m（m≥0）D．[n]n（n≥1）
7．由文法的开始符出发通过若干步（包括0步）推导产生的文法符号序列是B。
A．语言B．句型C．句子D．句柄
8．最左简单子树的叶结点，自左至右排列组成句型的C。
A．短语B．简单短语C．句柄D．素短语
9．简单优先分析法每次都是对D进行归约。
A．短语B．简单短语
C．素短语D．句柄
考试形式开卷（）、闭卷（√），在选项上打（√）
（1）
开课教研室 命题教师 命题时间
试 卷 专 用 纸
10．一个文法G是LL
（1）文法的充要条件是对每一个非终结符A的任意两个不同产生式A→α|β，有C。
A．FIRST（α）∩FIRST（β）=Φ
B．FIRST（α）∩FOLLOW（A）=Φ
C．SELECT（A→α）∩SELECT（A→β）=Φ
D．SELECT（A→α）∩SELECT（A→β）≠Φ
11．一个文法G，若C，则称它是LL
（1）文法。
A．G中不含左递归
B．G无二义性
C．G的LL
（1）分析表不含多重定义
D．G中产生式不含左公因子
12．若a为终结符，则A→α•aβ为A项目。
A．移入B．待约C．归约D．接受
13．设有文法G=（{S}，{a}，{S→SaS|ε}，S），该文法是D。
A．LL
（1）文法B．LR（0）文法
C．简单优先文法D．二义性文法
14．LR分析器核心部分是一张分析表，该表由D组成。
A．ACTION表B．GOTO表
C．LL
（1）分析表D．ACTION表和GOTO表
15．可归前缀是指C。
A．规范句型的前缀B．活前缀
C．含有句柄的活前缀D．句柄
16．编译程序的语法分析器必须输出的信息是A。
A．语法错误信息B．语法规则信息
C．语法分析过程D．语句序列
17．下列错误属于静态语义错误的是C。
A．括弧不配对B．出现非法字符
C．类型不相容D．溢出
18．在语法制导翻译中不采用拉链—回填技术的语句是B。
A．转向语句B．赋值语句
C．条件语句D．循环语句
19．下面逆波兰式（后缀式）中，能正确表示算术表达式a+b+c+d的是D。
A．abcd+++B．abc+d++
C．ab+cd++D．ab+c+d+
20．属于标识符“种属”属性信息的描述是B。
A．整型B．变量C．地址D．指针
使用学期总张数 教研室主任审核签字
江 南 大 学 考
二、文法和语言类型题〖1小题10分，2小题5分，共计15分〗
1．设有文法G[S]：
E→E+T|E-T|T
T→T*F|T/F|F
F→x|y|z|（E）
（1）给出对于句子x+y*x-z的最右推导过程
E=>E-T=>E-F=>E-z=>E+T-z=>E+T*F-z=>>E+T*x-z=>E+F*x-z=>E+y*x-z
=>T+y*x-z=>F+y*x-z=>x+y*x-z
（2）试构造句型（E+T）-（T+F）的语法树
x
F
T
y
x
F
T*F
E
E—T
F
z
E+T
（3）基于上述语法树给出该句型的短语、简单短语和句柄。
短语：
x+y*x-z、x+y*x、y*x、x
（1）、y、x
（2）、z
简单短语：
x
（1）、y、x
（2）、z
句柄：
x
（1）
试 卷 专 用 纸
2．试构造文法G，L（G）={a2mb2n+1|m≥1，n≥0}。
G：
S→AB
A→aaA|aa
B→bbB|b
三、词法分析类题〖每小题5分，共计15分〗
1．令：
L=A|B|…|Z|a|b|…|z
D=0|1|2|3|…|9
试构造描述C语言标识符集的正则表达式。
（L|_）（L|D|_）*
S
1
B
C
A
0
0
D
1
1
1
0
2．设有如下DFA
试构造与之等价的3型文法。
G：
S→1A
A→0B|
B→1B|0C
C→0D
D→1B|0C|ε
江 南 大 学 考
a,b
X
3．设有如下NFA：
试完成下列（右侧）NFA到DFA状态表的构造，将该NFA确定化为DFA
Ia
Ib
-[S]
[AS]
[AS]
[AS]
[XZ]
+[XZ]
[XZ]
[XYZ]
+[XYZ]
[XZ]
[XYZ]
b
Y
b
b
a
A
S
a
Z
b
ε
a,b
四、自上而下语法分析类型题〖每题5分，共计15分〗；
1．对文法G[S]：
S→BA
A→abB|ε
B→Acd|dc|eb
（1）求如下每条产生式的SELECT集合。
SELECT（S→BA）={a,c,d,e}
SELECT（A→abB）={a}
SELECT（A→ε）={c,#}
SELECT（B→Acd）={a,c}
SELECT（B→dc）={d}
SELECT（B→eb）={e}
（2）证明这个文法是否为LL
（1）文法。
由于
SELECT（A→abB）∩SELECT（A→ε）={a}∩{c,#}=Φ
SELECT（B→Acd）∩SELECT（B→dc）∩SELECT（B→eb）={a,c}∩{d}∩{e}=Φ
满足LL
（1）文法条件，所以该文法是LL
（1）文法。
=
试 卷 专 用 纸
（3）无论G[S]是否LL
（1）文法，试完成下列LL
（1）分析表的构造。
VT
VN
a
b
c
d
e
#
S
S→BA
S→BA
S→BA
S→BA
A
A→abB
A→ε
A→ε
B
B→Acd
B→dc
B→eb
#
acc
五、自下而上语法分析类型题〖每题10分，共计20分〗；
1．设有文法G[S]：
S→Aa|bA
A→cd|cAd
（1）完成下列优先关系矩阵的构造
S
A
a
b
c
d
#
S
⋗
A
⋗
a
⋗
b
⋖
c
⋖
d
⋗
⋗
⋗
#
⋖
⋖
⋖
⋖
（2）基于上述优先关系矩阵，按下面要求回答上述文法G[S]是否为简单优先文法并说明其原因
该文法G[S]（是）简单优先文法；
原因是：
优先关系矩阵不存在两个以上关系的元素。
江 南 大 学 考
2.设有如下文法G[S]:
S→EF
E→aE|ab
F→Fb|ba
（1）完成下列LR（0）项目集规范族（可归前缀图）的构造
I8:
E→ab·
b
a
I0:
S→·EF
E→·aE
E→·ab
I1:
E→a·E
E→a·b
E→·aE
E→·ab
a
I2:
E→aE·
E
E
I3:
S→E·F
F→·Fb
F→·ba
I4:
F→b·a
b
a
I5:
F→ba·
F
I7:
F→Fb·
I6:
S→EF·
F→F·b
b
（2）基于该LR（0）可归前缀图，按下面要求回答上述文法G[S]是否为LR（0）文法并说明其原因。
该文法G[S]（不是）LR（0）文法
原因是：
项目集规范族（可归前缀图）中项目集I6存在“移入—归约”项目冲突。
试 卷 专 用 纸
六、代码生成类题〖每题5分，共计15分〗；
1．设有一语法制导翻译算法如下：
S→E{print“E”}
E→E+T{print“+”}
E→T{print“T”}
T→T*F{print“*”}
T→F{print“F”}
F→id{print“id”}
若输入序列为a+b*c，且采用自底向上的分析方法，则给出输出序列。
输出序列：
aFTbF*+E
2．试给出表达式w=x+y-z*（a+b）*c规范和简易的四元式序列。
规范的四元式序列简易的四元式序列
1．（+,x,y,T1）T1:
=x+y
2．（+,a,b,T2）T2:
=a+b
3．（*,z,T2,T3）T3:
=z*T2
4．（*,T3,c,T4）T4:
=T3*c
5．（-,T1,T4,T5）T5:
=T1-T4
6．（:
=,T5,_,w）w:
=T5
3．是给出布尔表达式a四元式序列（序号从100开始）真、假链
100：
ifa101：
goto104
102：
ifc103：
goto104
104：
ife105：
goto106
106：
ifc107：
goto（0）
9
升级会员 