(整理完)编译原理网上作业题参考答案20121101.pdf

东北农业大学网络教育学院 编译原理作业题参考答案 第一章 编译概述 多项选择题： 1. 编译程序各阶段的工作都涉及到（ BC）。（﹡﹡） A. 语法分析 B. 表格管理 C. 出错处理 D. 语义分析 E. 词法分析 2. 编译程序工作时，通常有（ ABCE）阶段。 （﹡） A. 词法分析 B. 语法分析 C. 中间代码生成 D. 语义检查 E. 目标代码生成 填空题： 1．解释程序和编译程序的区别在于（是否生成目标程序）。（﹡） 2．编译过程通常可分为 5 个阶段，分别是（词法分析）、（语法分析）、（中间代码生成）、（代码优 化）和（目标代码）生成。（﹡） 3．编译程序工作过程中，第一段输入是（源程序），最后阶段的输出为（目标代码生成）程序。（﹡） 4 ．编译程序是指将（高级语言编写的）程序翻译成（目标语言）程序的程序。（﹡） 综合题： 1. 画出编译程序的总体结构图，简述各部分的主要功能。（﹡﹡﹡） 解答：编译程序的总体结构如下图所示： 词法分析程序：输入源程序，进行词法分析，输出单词符号。 语法分析程序：在词法分析的基础上，根据语言的语法规则（方法规则）把单词符号串分解成各类语 法单位，并判断输入串是否构成语法上正确的“程序”。 中间代码生成程序：按照语义规则把语法分析程序归约（或推导）出的语法单位翻译成一定形式的中 间代码，比如说四元式。 优化程序：对中间代码进行优化处理。 目标代码生成程序：把中间代码翻译成目标语言程序。 表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段 所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编译过程中都在不断地和表格 打交道。 出错处理程序对出现在源程序中的错误进行处理。此外，编译的各个阶段都可能出现错误。出错处理 程序对发现的错误都及时进行处理。 第二章 文法和语言的基本知识 多项选择题： 1. ABC 2. ACE 3. BCD 4. AC 5. BC 填空题： 1．文法中的终结符和非终结符的交集是（空集）。词法分析器交给语法分析器的文法符号一定是（终结 符），它一定只出现在产生式的（右）部。（﹡） 2．最左推导是指每次都对句型中的（最左）非终结符进行扩展。（﹡） 3．在语法分析中，最常见的两种方法一定是（自上而上）分析法，另一是（自下而上）分析法。（﹡） 4 ．采用（自上而下）语法分析时，必须消除文法的左递归。（﹡） 5．（语法）树代表推导过程，（分析）树代表归约过程。（﹡） 6．自下而上分析法采用（移进）、归约、错误处理、（接受）等四种操作。（﹡﹡） 7．Chomsky把文法分为（ 4）种类型，编译器构造中采用 （2 型） 和（ 3 型）文法，它们分别产生（上下 文无关语言）和（正规语言）语言，并分别用（下推自动机）和（有限）自动机识别所产生的语言。（﹡ ﹡） 判断题： 1．正确 2 ．错误 3 ．错误 4 ．错误 5 ．错误 6． 错误 7 ．正确 8 ．正确 9 ．错误 简答题 1 句柄： （﹡） 解答：一个句型的最左直接短语称为该句型的句柄。 2．素短语： （﹡﹡） 解答：至少含有一个终结符的素短语， 并且除它自身之外不再含任何更小的素短语。 3．语法树： （﹡﹡） 解答：满足下面 4 个条件的树称之为文法 G[S] 的一棵语法树。 ①每一终结均有一标记，此标记为 V N ∪V T 中的一个符号； ②树的根结点以文法 G[S] 的开始符 S 标记； ③若一结点至少有一个直接后继，则此结点上的标记为 V N 中的一个符号； ④若一个以 A 为标记的结点有 K 个直接后继，且按从左至右的顺序，这些结点的标记分别为 X ,X , … ,X ，则 A→X ,X , … ,X ， 必然是 G 的一个产生式。 1 2 k 1 2 k