《华东交通大学编译原理试题库试卷八》由会员分享，可在线阅读，更多相关《华东交通大学编译原理试题库试卷八（6页珍藏版）》请在金锄头文库上搜索。
1、一、填空题(每题 2 分，共 20 分) 1、从功能上说，程序语言的语句大体可分为 语句和 语句两大类。 2、扫描器的任务是从 中识别出一个个 。 3、所谓最右推导是指： 。 4、语法分析最常用的两类方法是 和 分析法。 5、一个上下文无关文法所含四个组成部分是 。 6、所谓语法制导翻译方法是 。 7、符号表中的信息栏中登记了每个名字的有关的性质，如 等等。 8、一个过程相应的 DISPLAY 表的内容为 。 9、常用的两种动态存贮分配办法是 动态分配和 动态分配。 10、产生式是用于定义 的一种书写规则。二、名词解释(每题 2 分，共 10 分)1、遍2、无环路有向图(DAG)3、语法分析4
2、、短语5、后缀式三、简述题(每题 4 分，共 24 分)1、考虑下面程序Var a：integer；Procedure S(X)；Var X：integer；Begina：a1；X：aXEnd；Begina：5；S(a)；Print(a)End试问：若参数传递方式分别采取传名和传值时，程序执行后输出 a 的值是什么？2、画出 Pascal 中实数(不带正负号，可带指数部分)的状态转换图。3、写出表达式(ab*c)/(ab)d 的逆波兰表示及三元式序列。4、已知文法 G(S)Sa|(T)TT，S|S写出句子(a，a)，a)的规范归约过程及每一步的句柄。5、何谓优化？按所涉及的程序范围可分为哪几级
3、优化？6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？四、计算题(共 41 分)1、写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。(5 分)2、设文法 G(S)：S(L)|a S|aLL，S|S(1)消除左递归和回溯；(2)计算每个非终结符的 FIRST 和 FOLLOW；(3)构造预测分析表。3、While a0 b0 do BeginX：X1；if a0 then a：a1else b：b1End；翻译成四元式序列。(7 分)4、已知文法 G(E)ET|ETTF|T *FF(E)|i(1)给出句型(T *Fi)的最右推导及画出语法树；(2)给出句型(T *Fi)的短
4、语、素短语。(7 分)5、设布尔表达式的文法为E E(1)E(2)E E(1)E(2)E i假定它们将用于条件控制语句中，请(1)改写文法，使之适合进行语法制导翻译和实现回填；(2)写出改写后的短个产生式的语义动作。(6 分)6、设有基本块T1：2T2：10/TT3：SRT4：SRA：T2 *T4B：AT5：SRT6：T3 *T5B：T6(1)画出 DAG 图；(2)假设基本块出口时只有 A，B 还被引用，请写出优化后的四元序列。(6 分)参考答案： 一、填空题 1、执行性、说明性 2、源程序、单词符号 3、任何一步 都是对 中最右非终结符进行替换的 4、自上而下、自下而上5、一组终结符号，一
5、组非终结符号、一个开始符号、一组产生式 6、为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序 7、类型、种属、所占单元大小、地址 8、现行活动记录地址和所有外层最新活动记录的地址 9、栈式、堆式 10、语法范畴二、名词解释1遍指编译程序对源程序或中间代码程序从头到尾扫描一次。 2无环路有向图(DAG)如果有向图中任一通路都不是环路，则称庐有向图为无环路有 向图，简称 DAG。 3语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。4短语令 G 是一个文法。S 划文法的开始符号，假定 是文法 G 的一个句型，如 果有 SA 且 AB，则称 是句型 相对非终结符 A 的
6、短语。 5后缀式一种把运算量写在前面，把算符写在后面的表示表达式的方法。三、简述题1、考虑下面程序 Var a：integer； Procedure S(X)； Var X：integer； Begin a：a1； X：aX End； Begin a：5； S(a)； Print(a) End 试问：若参数传递方式分别采取传名和传值时，程序执行后输出 a 的值是什么？ 答：传名：a12 (2 分) 传值：a6 (2 分) 3、写出表达式(ab*c)/(ab)d 的逆波兰表示及三元式序列。 逆波兰表示： abc*ab/d (2 分) 三元式序列： (*，b，c) (，a，) (，a，b) (/，
7、) (，d) (2 分) 4、已知文法 G(S) Sa|(T) TT，S|S 写出句子(a，a)，a)的规范归约过程及每一步的句柄。 句型 归约规则 句柄 (a，a)，a) Sa a (S，a)，a) TS S (T，a)，a) Sa a (T，S)，a) TT，S T，S (S)，a) TS S (T)，a) SS(T) (T) (S，a) TS S (T，a) Sa a (T，S) TT，S T，S (T) S(T) (T) S (4 分) 5、何谓优化？按所涉及的程序范围可分为哪几级优化？ 答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目 标代码。 (2 分)
8、三种级别：局部优化、循环优化、全局优化。 (2 分) 6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ 答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2 分) 应着重考虑的问题： (1)如何使生成的目标代码较短； (2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指仅系统的的特点。 (2 分)四、计算题 1、写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。(5 分) 解：文法 G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D (5 分) 2、设文法 G(S)： S(L)|a S|a LL，S
9、|S (1) 消除左递归和回溯； (2) 计算每个非终结符的 FIRST 和 FOLLOW； (3) 构造预测分析表。 解： (1) S(L)|aS SS| LSL LSL| 评分细则：消除左递归 2 分，提公共因子 2 分。 (2) FIRST)S)(，a FOLLOW(S)#， ， ，) FIRST(S)，a, FOLLOW(S)#， ， ，) FIRST(L)(，a FOLLOW(L) ) FIRST(L)， ， FOLLOW(L ) 3、While a0 b0 do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列。(7 分) 解：
10、 (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15) 评分细则：控制结构 4 分，其它 3 分。 4、已知文法 G(E) ET|ET TF|T * F F(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树； (2) 给出句型(T * Fi)的短语、素短语。(7 分) 解
11、：(1) 最右推导： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短语：(T*Fi)，T*Fi，T*F，i (2 分) 素短语：T*F,i (1 分) 5、设布尔表达式的文法为 E E(1)E(2) E E(1) E(2) E i 假定它们将用于条件控制语句中，请 (1) 改写文法，使之适合进行语法制导翻译和实现回填； (2) 写出改写后的短个产生式的语义动作。(6 分) 解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei (3 分) (2) EE(1) BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TC EE0E(2) EF
12、C：E(2)FC； ETC：MERG(E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC) Ei ETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0) (3 分) 6、设有基本块 T1：2 T2：10/T T3：SR T4：SR A：T2 * T4 B：A T5：SR T6：T3 * T5 B：T6 (1) 画出 DAG 图； (2) 假设基本块出口时只有 A，B 还被引用，请写出优化后的四元序列。(6 分) 解：(1)DAG： (2) 优化后的四元式 T3：SR T4：SR A：5*T4 B：T3T4 (3 分)
