编译原理期末A试卷答案.doc

《编译原理期末A试卷答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、黄冈师范学院2012—2013学年度第一学期期末试卷参考答案考试课程：编译原理考核类型：考试A卷考试形式：闭卷出卷教师：牛冀平考试专业：计算机科学与技术，软件工程考试班级：计科201001班，软件201001班一、填空（每空0.5分，共10分）1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。另外还有表格管理和（出错处理）。3、一个上下文无关文法所含四个组成部分是  一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）  。4、设G是一个给定的文法

2、，S是文法的开始符号，如果S=> x（其中x∈V*），则称x是文法的一个（句型 ）。5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）7、语法分析最常用的两类方法是（ 自上而下 ）和  （自下而上）  分析法。8、表达式（a+b)*c的后缀表达式为（ab+c*）。9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）10、代码优化的目的是（减少代码的时空开销）

3、。11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。二、选择题（每题1分，共10分）1、文法的开始符号经多步推导产生的文法符号序列(仅包含终结符)是文法的（D）。A.短语B.句柄C.句型D.句子2、构造编译程序应掌握（D）。A.源程序B.目标语言C.编译方法D.以上三项都是3、不属于循环优化的主要方法的是（B）。A.强度削弱B.删除无用赋值C.删除归纳变量D.代码外提4、使用（A）可以定义一个程序的含义。A.语义规则B.词法规则C.产生规则D.左结合规则5、优化可生成（D）的目标代码。A．运行时

4、间较短B．占用存储空间较小C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小6、有文法G：E→E*T

5、T，T→T+i

6、i,则输入串1+2*8+6按该文法G归约,其值为（B）。A.23B.42C.30D.177、编译技术中描述单词符号的形成规则的常用工具有（D）。A．正规文法B．正规式C．有穷自动机D．以上都是8、编译技术中常用（B）描述程序语言的语法。A．正规文法B．上下文无法文法C．属性文法D．上下文有关文法9、词法分析器的输出结果是(C)。A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值10、以下(B)不是DFA的组成部分。A．有穷字母表B

7、．初始状态集合C．终止状态集合　D．有限状态集合　三、简答题（每题10分，共50分）1、有文法G[S]：S→SA

8、AA→a

9、b写出句子aba的最左推导和最右推导。解：句子aba的最左推导为：S=>SA=>SAA=>AAA=>aAA=>abA=>aba（5分）句子aba的最右推导为：S=>SA=>Sa=>SAa=>Sba=>Aba=>aba（5分）2、一正规表达式为：b（b

10、a）

11、a（b

12、a（b

13、a）），写出上述正规式对应的DFA和状态装换矩阵。解答：正规式对应的DFA为：（5分）YX123aaabbbbaDFA状态矩阵为：（5分）状态字符abX1312Y2YY3YYY--3、设G[E]

14、:E->T

15、E+T

16、E-T,T->F

17、T*F

18、T/F,F->(E)

19、i证明E+T*i*i+i是该文法的句型解答：E=>E+T=>E+T+T=>E+T*F+T=>E+T*F*F+T=>E+T*i*F+T=>E+T*i*i+T=>E+T*i*i+F=>E+T*F*i+i（5分）或E=>E+T=>E+F=>E+i=>E+T+i=>E+T*F+i=>E+T*i+i=>E+T*F*i+i=>E+T*i*i+i（5分）即，E=>*E+T*i*i+i，所以是该文法的句型。4、下面的文法是否是左递归的？如果是，该如何消除？E→E+T

20、TT→T*F

21、FF→(E)

22、id解答：ET存在左递归，可以用以下等价文

23、法消除左递归E→TE’（2分）E’→+TE’

24、ε（2分）T→FT’（2分）T’→*FT’

25、ε（2分）F→(E)

26、id（2分）5、设有文法G[S]：S→S/S

27、S-S

28、(S)

29、a，该文法是否有二义性？为什么？解答：有.该文法存在句子:a/a-a。（5分）该句子存在两颗不同的语法树，如图：（5分）四、解答题（共30分）1、对于下面的程序：Programmainprocedurep(x,y,z)beginy:=y+1;z:=z+x;end