上海大学编译原理试卷2013-2014春(附答案).doc
- 文档编号:4896027
- 上传时间:2023-05-07
- 格式:DOC
- 页数:6
- 大小:141.50KB
上海大学编译原理试卷2013-2014春(附答案).doc
《上海大学编译原理试卷2013-2014春(附答案).doc》由会员分享,可在线阅读,更多相关《上海大学编译原理试卷2013-2014春(附答案).doc(6页珍藏版)》请在冰点文库上搜索。
试卷序号:
第1页(共8页)
上海大学2013~2014学年春季学期试卷A
课程名:
编译原理课程号:
08305013学分:
5
参考答案
题号
一(10)
二(10)
三(10)
四(15)
五(12)
六(15)
七(12)
八(16)
得分
一、判断题(本大题共10小题,每小题1分,共10分)
判断下列各题正误,正确者在括号内打“√”,错误者在括号内打“×”。
1.对中间代码的优化不依赖于具体的计算机。
(√)
2.程序流图中的每条回边对应于一个循环。
(√)
3.自底向上语法分析时必须先消除文法中的左公共因子。
(×)
4.使用逆波兰式描述表达式时无须使用括号。
(√)
5.编译程序是对高级语言程序的解释执行。
(×)
6.符号表内容的一个重要作用是作为上下文语义合法性检查的依据。
(√)
7.状态中含有冲突的文法有可能是一个SLR
(1)文法。
(√)
8.语义处理中“拉链”的作用是使“回填”更为有效。
(√)
9.算符优先分析法是一种自下而上的语法分析方法。
(√)
10.编译程序能找出源程序中所有错误。
(×)
成
绩
得分
阅卷人
二、选择题(本大题共10小题,每小题1分,共10分)
在每小题列出的备选项中只有一个是符合题目要求的,请将其代码填写在题中的空格内。
错选、多选或未选均无分。
1.以下优化技术除b外,都是针对循环优化进行的。
a)强度削弱b)删除多余运算c)变换控制条件d)代码外提
2.下列d工作不属于编译阶段的前端。
a)语法分析b)词法分析c)中间代码生成d)目标代码生成
3表达式(a+b)*c/d对应的逆波兰式是a。
a)ab+c*d/b)abc+/*dc)ab*c+/dd)abc*/d+
4.一个句型中称为句柄的是该句型中最左的d。
a)非终结符b)句子c)短语d)直接短语
5.以下c函数是PL/0编译程序中的词法分析器。
a)termb)expressionc)getsymd)factor
6.PL/0编译程序的语法分析采用的是b。
a)LR分析法b)递归子程序法c)算符优先分析法d)预测分析法
7.程序所需的数据空间在程序运行前就可确定,称为d方法。
a)动态分配b)堆式分配c)栈式分配d)静态分配
8.下列语句中,c语句不是基本块的入口语句。
a)程序的首条b)被转向的目标c)停止d)条件转移的下一条
9.给定文法A→bAa|a|b,下列符号串中语法正确的是a。
a)bbaaab)babbac)abaabd)aabab
10.c和代码优化部分不是每个编译程序都必需的。
a)目标代码生成b)词法分析c)中间代码生成d)语法分析
第2页(共8页)
第3页(共8页)
三、设计题(本大题共2小题,每小题5分,共10分)
1.定义一个上下文无关文法G[S],生成下述语言L:
L={andmbn|n,m≥1}
答G[A]:
A→aAb|aBb
B→dB|d
2.证明下列文法G[A]是一个二义文法:
A→B+B|B
B→B*B|A|a
答:
∵对于句子a+a*a存在两个不同的最左推导:
1:
A=>B+B=>a+B=>a+B*B=>a+a*B=>a+a*a
2:
A=>B=>B*B=>A*B=>B+B*B=>a+B*B=>a+a*B=>a+a*a
∴G[A]是一个二义文法
四、设计题(本大题共3小题,每小题5分,共15分)
设有正规式r=(a|ab)(a|b)*b
1.构造一个NFAM,接受L(r)。
2.把上述NFAM转化为等价的DFAM。
3.给出DFAM所对应的正规文法。
G[S]:
S→aAA→aB|bC
B→aB|bCC→aB|bC|ε
五、设计题(本大题共2小题,第1题7分,第2题5分,共12分)
对下列基本块B应用DAG进行优化,设只有S、W在基本块后面还要继续引用。
B:
T1:
=a+b
T2:
=3.14
S:
=T1*T2
T3:
=a+b
T4:
=2.56
T5:
=T2+T4
W:
=T5*T1
S:
=T5*T3
1.基本块B的DAG
答:
2.优化后的基本块B’
答:
T1:
=a+b
T5:
=5.70
W:
=T5*T1
S:
=W
第4页(共8页)
第5页(共8页)
六、分析题(本大题共2小题,第1题5分,第2题10分,共15分)
1.对下列属性文法中的语义处理功能作简略说明:
E→id1ropid2{E.true:
=nextstat;
E.false:
=nextstat+1;
E.Codebegin:
=nextstat;
emit(‘if’id1.place‘rop’id2.place‘goto’–);
emit(‘goto’-)}
答:
E.true:
E的真出口链
E.false:
E的假出口链
E.Codebegin:
E的代码开始地址
Nextstat:
下一条代码地址
emit:
生成一条四元式
2.在下划线处填写正确内容,完成下列源语句通过语法制导翻译后生成的四元式序列。
源语句:
while(s<100)and((a
begin
a:
=a+1;
if(a
=s+a;
end;
四元式序列:
1)ifs<100goto(3)
2)goto(14)
3)ifa 4)goto(5) 5)ifa=bgoto(7) 6)goto(14) 7)t1: =a+1 8)a: =t1 9)ifa 10)goto (1) 11)t2: =s+a 12)s: =t2 13)goto (1) 14) 七、证明题(本大题共3小题,每题4分,共12分) 设有文法G[S]: S→BA A→AB|Aa|a B→ba|bB 1)证明G[S]是一个非LL (1)文法。 答: ∵A含左递归(以及A、B含公共左因子)∴G[S]非LL (1)文法。 2)把G[S]等价改写为LL (1)文法G1[S]。 答: G1[S]: S→BA A→aA’ A’→BA’|aA’|ε B→bB’ B’→a|B 3)证明G1[S]为LL (1)文法。 答: 对于S,A,B: 仅有一个候选,选择唯一; 对于A’: Select(A’→BA’)={b} Select(A’→aA’’)={a} Select(A’→ε)={#} {a}∩{b}=Æ且{a}∩{#}=Æ且{b}∩{#}=Æ 选择唯一 对于B’: Select(B’→a)={a} Select(B’→B)={b} {a}∩{b}=Æ 选择唯一 ∴G1[S]为LL (1)文法。 第6页(共8页)八、综合题(本大题共3小题,第1题6分,第2,3题各5分共16分) 设有文法G[S’]: (0)S’→E (1)E→E+T (2)E→T (3)T→n (4)T→r 1.证明G[S]是SLR (1)文法,构造G[S]的SLR (1)分析表。 答: LR(0)项目集规范族: ∵状态I1含有移进-归约冲突∴G[S]是非LR(0)文法 ∵follow(S’)={#}∩{+}=Æ∴G[S]是SLR (1)文法 SLR (1)分析表: 状态 ACTION GOTO +nr# ET 0 1 2 3 4 5 6 s3s4 s5acc r2r2 r3r3 r4r4 s3s4 r1r1 12 6 第7页(共8页) 第8页(共8页) 2.对输入串n+r+n#给出分析过程: 步骤 状态符号 输入串 动作 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 0# 03#n 02#T 01#E 015#E+ 0154#E+r 0156#E+T 01#E 015#E+ 0153#E+n 0156#E+T 01#E n+r+n# +r+n# +r+n# +r+n# r+n# +n# +n# +n# n# # # # s3 r3 r2 s5 s4 r4 r1 s5 s3 r3 r1 acc 3.将文法G[S’]扩充为属性文法: (0)S’→E{} (1)E→E+T{print(“+”)} (2)E→T{} (3)T→n{print(“n”)} (4)T→r{print(“r”)} 写出对输入串n+r+n#进行语法制导翻译分析后,输出的符号串。 答: 输出的符号串: nr+n+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上海 大学 编译 原理 试卷 2013 2014 答案