《编译原理试题a(含答案)》由会员分享，可在线阅读，更多相关《编译原理试题a(含答案)（6页珍藏版）》请在金锄头文库上搜索。
1、 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 第 1 页 共 页 电子科技大学电子科技大学 2010 2010 - -20112011 学年第学年第 2 2 学期期学期期 末末 考试考试 A A 卷卷 答案及评分细则答案及评分细则 课程名称：_编译原理_ 考试形式： 闭卷 考试日期： 2011 年 6 月 21 日 考试时长：120 分钟 一、选择题（共 10 分，共 10 题，每题 1 分） 1. 编译程序是将高级语言程序翻译成（ D ）程序的翻译程序。 A. 机器语言 B. 汇编语言 C. 中间语言 D. 低级语言 2. 强制式语言的理论基础是（ A ） A.
2、 冯.诺依曼体系结构 B. 数学函数 C. 数理逻辑谓词演算 D. 抽象数据类型 3. C 语言的以下哪种数据类型属于用户定义类型（ C ） A. 整型 B. 实型 C. 数组型 D. 字符型 4. 以下哪种数据类型是抽象数据类型（ D ） A. Pascal 的变体记录 B. C 语言的结构 C. Java 的数组 D. C+的类 5. 从文法开始符推导出的任意符号串是该文法的（ C ） A. 短语 B. 句子 C. 句型 D. 句柄 6. 一个句型对应的语法树中，有且仅有 2 层的子树的边缘，称为该句型的（ A ） A. 直接短语 B. 短语 C. 素短语 D. 活前缀 7. 在自上而下的
3、分析过程中，下列哪种情况不会产生回溯（ C ） A. 公共左因子 B. 左递归 C. 右递归 D. 产生式 8. 下列哪种语法分析法适用于分析 LL(1)文法（ A ） A. 预测分析法 B. LR 分析法 C. 算符优先分析法 D. 递归下降分析法 9. 项目 AB称为（ C ） ，其中 BVN。 A. 移进项目 B. 归约项目 C. 待约项目 D. 接受项目 10. 代码生成时，节省一条指令 MOV Ri, x，节省的执行代价为（ C ） 。 A. 0 B. 1 C. 2 D. 3 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 第 2 页 共 页 二、简答题（共
4、 30 分，共 6 题，每题 5 分） 1. 什么是绑定，静态绑定和动态绑定有什么区别？ 绑定：一个对象（或事物）与其各种属性属性建立起某种联系的过程。 （3 分）分） 静态绑定：凡是在编译时编译时（运行前）能确定的属性称为静态属性。实体与静态属性之间的绑定在编译时 （运行前）完成，运行时不改变，称为静态绑定。 （1 分）分） 动态绑定：凡是在运行时运行时才能确定的属性称为动态属性。实体与动态属性之间的绑定在运行时完成，称 为动态绑定。 （1 分）分） 评分标准：答出关键词属性、编译时、运行时即可得分。评分标准：答出关键词属性、编译时、运行时即可得分。 2. 举例说明用户定义类型的 6 种聚合
5、方法。 笛卡尔积：PASCAL 的记录；C 的结构。 有限映像：数组。 序列：串、顺序文件。 递归：指针。 判定或：PASCAL 的变体记录；C 的联合。 幂集：PASCAL 的集合。 评分标准：评分标准：答出答出 6 种方式种方式可得可得 4 分分；举例酌情给分。；举例酌情给分。 3. 简述编译的 5 大步骤的功能，以及各步骤的输入与输出。 1) 词法分析： 根据词法规则， 进行合法性检查； 从构成源程序的字符串中识别出单词符号。 字符串 单 词符号串（单词串、符号串） 2) 语法分析：根据语法规则，进行合法性检查；将单词符号串组合成各类语法单位，构造语法树。单词 符号串 语法树 3) 语义
6、分析与中间代码生成：根据语义规则，进行合法性检查；进行初步的翻译，生成中间代码。语法 树 中间代码 4) 优化：对中间代码进行等价变换，使代码的效率更高。中间代码 优化后的中间代码 5) 目标代码生成：将中间代码翻译成目标代码（目标程序） 。中间代码 目标程序 评分标准：每个阶段各评分标准：每个阶段各 1 分。分。 4. 若算符文法算符文法 G 的任何两个终结符 a 和 b 没有优先关系，或者至多至多只有=、中的一个优先关系， 则称 G 为算符优先文法。 评分标准：算符文法、至多、评分标准：算符文法、至多、=、各各 1 分。分。 5. 简述循环优化的 3 种方法，各举一个例子。 1) 代码外提
7、：对 x:=op y 或 x:=y op z，如果 y、z 均为循环不变量（常数或定值点在 L 之外） ，则该运算 为循环不变运算，优化时将该运算提到循环入口结点之前所增设的结点中去。 （2 分）分） 2) 强度削弱：基本归纳变量 i 每循环一次增加或减少 c，与 i 同族的归纳变量 j 相应增加或减少 c1*c。计 算 j 的乘法可由加法来代替：j := j + c1*c （c1*c 为常数） 。 （2 分）分） 3) 删除归纳变量：用同族归纳变量作为判断条件，如基本归纳变量别无它用，则可将其删除。 （1 分）分） 例如：j = 10 * i + 5，判断条件为 i 10 ，则 将 i 10
8、 改为 j 105，同时删除 i 相关的语句。 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 第 3 页 共 页 6. 简述存储分配的 3 种方式，各举一个例子。 1) 静态分配： 变量与存储区域的绑定关系在编译时便可建立， 并完成存储分配。 例如： 静态变量的分配。 （2 分）分） 2) 栈式分配：当一个程序单元被激活时, 在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动 记录撤销。例如：半静态变量的分配。 （2 分）分） 3) 堆分配：由于动态变量的首地址、长度、类型等在编译时无法确定，在执行过程中也可能改变，对于 这些变量，必须分配在堆上。例如：C 中通
9、过 malloc 分配的变量；某些语言中的动态变量等。 （1 分）分） 三、已知文法：(共 12 分) E T| E+T | E-T T F| T*F | T/F F (E) | i 1、证明 i+(E-T)*F 是该文法的一个句型； （3 分） 2、给出句型 i+(E-T)*F 的推导树； （3 分） 3、指出该句型的所有短语、直接短语和句柄。 （6 分） 答案答案 1. E = E+T = E+T*F =E+F*F=E+(E)*F= E+(E-T)*F=T+(E-T)*F= F+(E-T)*F= i+(E-T)*F （3 3 分分） 2. （3 3 分分） 3. 短语： i 是关于 F、T
10、、E 的短语； E-T 是关于 E 的短语； （E-T）是关于 F、T 的短语； （E-T）* F 是关于 T 的短语； i +（E-T）* F 是关于 E 的短语。 （3 3 分分） 直接短语： i 是关于 F 的直接短语；E-T 是关于 E 的直接短语。 （2 2 分分） 句柄： i （1 1 分分） E E + T T * F T F i F ( E ) T E _ 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 第 4 页 共 页 四、给出下面语句 WhileWhile ab do ifif a0 thenthen a： a1 elseelse b： b+1；
11、 翻译得到的中间代码序列，地址从 100 开始，一条代码占 1 个字节。(10 分) 答案答案（写成三地址代码也可，错一个扣写成三地址代码也可，错一个扣 1 1 分，直到扣完分，直到扣完） 100: (j, a, b, 102 ) 101: (j, , , 110 ) 102: (j, a, 0, 104 ) 103: (j, , , 107 ) 104: (-, a, 1, t1 ) 105: (:=, t1, , a ) 106： (j, , , 100 ) 107: (+, b, 1, t2 ) 108: (:=, t2, , b ) 109: (j, , , 100 ) 110: 五、
12、给出下述语句（if-then-else 语句）的翻译方案（语义子程序） 。 （共 8 分） Sif B then M S1 else N S2 （3 3 分）分） backpatch(B.T，M.CODE)； backpatch(B.F，N.CODE)； S.CHAIN=merge(S1.CHAIN，N.CHAIN，S2.CHAIN) M （2 分）分） M.CODE =ip N （3 分）分） N.CHAIN=ip； emit(goto 0)； N.CODE=ip 六、已知文法 G(E)： （共 15 分） E （F）| e F FT| f T *ET 1、 消除文法的左递归得文法 G； （
13、1 分） 2、 求 G中各非终结符的的 FIRST 集、FOLLOW 集； （8 分） 3、 构造预测分析表； （4 分） 4、 该文法是不是 LL(1)文法？为什么？（2 分） 答: 1.（1 1 分）分） G（E） ： E（F）| e Ff F FT F| T *ET 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 第 5 页 共 页 2. FIRST 集和 FOLLOW 集（每个集合（每个集合 1 分）分） FIRST FOLLOW E ( , e # , * F f ) F * , ) T * * , ) 3. 预测分析表（每行（每行 1 分）分） e f * ( ) # E Ee E（F） F Ff F F FT F F T T *ET 4. 因为预测分析表无多重定义入口，所以文法 G 是 LL（1）文法。 （2 分）分） 七、设有文法 G(E)： （共 15 分） E(L)|a LL，E|E 1、 列出 G(E)的 LR(0)项目集规范族。 （8 分） 2、构造此相应的 SLR(1)分析表。 （5 分） 3、该文法是否为 SLR(1)文法？为什么（2 分） 答案答案 1、拓广文法（1 分）分） 0.EE 1. E(L) 2. Ea 3. LLbE 4. LE F
