编译原理期末A试卷答案

黄冈师范学院20122013学年度第一学期期末试卷参考答案 考试课程：编译原理 考核类型：考试A卷考试形式：闭卷 出卷教师：牛冀平 考试专业：计算机科学与技术，软件工程 考试班级：计科201001班，软件201001班 一、填空（每空0.5分，共 10分）1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成 。另外还有表格管理和（出错处理）。3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。 4、设G是一个给定的文法，S是文法的开始符号，如果S=x（其中xV*），则称x是文法的一个（句型）。 5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语） 。6、在编译过程中,可采用的中间代码形式有（ ）、（ ）、（ ）等。（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。8、表达式（a+b)*c的后缀表达式为（ab+c*）。9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。 分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）10、代码优化的目的是（减少代码的时空开销）。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运行时间较短 B占用存储空间较小 C运行时间短但占用内存空间大 D运行时间短且占用存储空间小6、有文法G：EE*T|T， TT+i|i ,则输入串1+2*8+6按该文法G归约,其值为（B）。 A.23 B.42 C.30 D.17 7、编译技术中描述单词符号的形成规则的常用工具有（ D ）。 A正规文法 B正规式 C有穷自动机 D以上都是8、编译技术中常用（ B ）描述程序语言的语法。 A正规文法 B上下文无法文法 C属性文法 D上下文有关文法9、词法分析器的输出结果是( C )。 A单词的种别编码 B单词在符号表中的位置 C单词的种别编码和自身值 D单词自身值10、以下( B )不是DFA的组成部分。 A有穷字母表 B初始状态集合 C终止状态集合D有限状态集合 三、简答题（每题10分，共50分）1、有文法GS：SSA|A Aa|b 写出句子aba的最左推导和最右推导。解： 句子aba的最左推导为：S=SA=SAA=AAA=aAA=abA=aba （5分）句子aba的最右推导为：S=SA=Sa=SAa=Sba=Aba=aba （5分）2、 一正规表达式为：b（b|a）| a（b|a（b|a） ，写出上述正规式对应的DFA和状态装换矩阵。解答：正规式对应的DFA为： （5分）YX123aaabbbbaDFA 状态矩阵为： （5分）状态字符abX1312Y2YY3YYY-3、设GE: E-T|E+T|E-T, T-F|T*F|T/F , F-(E)|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、下面的文法是否是左递归的？如果是，该如何消除？EE+T|TTT*F|FF(E)|id解答：E T 存在左递归， 可以用以下等价文法消除左递归 ETE （2分） E+TE| （2分） TFT （2分） T*FT| （2分） F(E)|id （2分） 5、设有文法GS：SS/S|S-S|(S)|a，该文法是否有二义性？为什么？ 解答： 有. 该文法存在句子: a/a-a。（5分） 该句子存在两颗不同的语法树，如图：（5分）四、解答题（共30分）1、对于下面的程序：Program main procedure p(x,y,z) begin y:=y+1; z:=z+x; end;begin a:=2; b:=3; p(a+b,a,a); write(a);end. 请分别按照（1）传值 (call by value)（2）传地址(call by reference) （3）传名（call by name）(4)传结果(call by result)的参数传递方式给出程序执行时的输出结果。解：（1）传名（call by name）输出结果为：2 （5分） （2）传地址(call by reference) 输出结果为：8 （5分） （3）传值 (call by value) 输出结果为：9 （5分）(4) 传结果(call by result) 输出结果为：7 （5分）2、 对于文法G(S):S-bMbM-（L|aL-Ma)SbM(TMabL)1. 写出句型b(Ma)b的最右推导并画出语法树。2. 写出上述句型的短语，直接短语和句柄。答：1. (5分) 2. (5分)短语: Ma)， (Ma)， b(Ma)b直接短语: Ma)句柄: Ma)