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

### 编译原理知识点解析 #### 一、填空题解析 1. **不同编译程序的数据空间存储分配策略** - **静态存储分配方案**：指在编译阶段就确定了变量的存储位置，不会随着程序运行时的变化而变化。 - **动态存储分配方案**：指在程序运行期间根据需要动态地分配存储空间，进一步可以分为两种子类型： - **栈式分配**：主要用来管理函数调用时的局部变量，遵循先进后出的原则。 - **堆式分配**：用于管理动态创建的对象或者较大的数据结构，空间分配和释放时间较为灵活。 2. **规范规约** - 规范规约是最**左**规约。它是一种特殊的LR分析法，确保每次规约都是以最左边的直接短语进行规约，从而保证规约过程的一致性和简洁性。 3. **编译程序工作过程划分** - 词法分析：将源代码转换成一个个有意义的记号（token）。 - **语法分析**：基于语言的语法规则检查这些记号是否构成合法的程序结构。 - 语义分析与中间代码生成：检查程序逻辑是否正确，并将其转换为一种更接近于目标代码的形式。 - **目标代码生成**：将中间代码转换为目标机器的指令集。 - **错误处理**：在整个编译过程中检测并报告可能出现的语法和语义错误。 - **代码优化**：改进中间代码或目标代码，提高程序的运行效率。 4. **表达式的后缀式表示** - 后缀式（逆波兰表示法）是一种无需括号来表示运算优先级的表达式表示法。 - **x+y*z/(a+b)** 的后缀式为 **xyza+b/*+**。其中，“/”、“*”、“+”等操作符紧跟它们的操作数之后。 5. **文法符号的属性分类** - 综合属性：依赖于该符号后面符号的属性。 - **继承属性**：依赖于该符号前面符号的属性。 6. **数组元素地址计算** - 对于按行存放的二维数组 a[1..15,1..20]，某个元素 a[i,j]的地址计算公式为 **base + (i-1)*cols + (j-1)**，其中 base 是数组起始地址，cols 是列数。 7. **局部优化概念** - 局部优化是局限于一个基本块内的优化，如循环展开、常量传播等。 #### 二、选择题解析 1. **上下文无关文法的组成** - 正确答案是 **C. 开始符号** 和 **B. 产生式**。 - 上下文无关文法由终结符、非终结符、开始符号和一系列产生式构成。 2. **程序基本块定义** - 正确答案是 **D. 一组顺序执行的程序段，仅有一个入口和一个出口**。 - 基本块是一段代码，其中的语句顺序执行且只有一个入口和一个出口。 3. **高级语言编译语法分析方法** - 递归下降分析法属于 **B. 自顶向下** 分析方法。 - 这种方法从文法的根节点开始，逐步向下解析输入串，适用于简单文法。 4. **适用于表达式分析的语法分析方法** - **A. 算符优先分析法** 特别适用于表达式的分析。 - 它利用了算符之间的优先关系来进行分析。 5. **编译后目标程序形式** - 正确答案是 **D. 机器语言程序或汇编语言程序**。 - 目标程序通常是机器可以直接执行的指令序列。 6. **文法所描述的语言特性** - 一个文法所描述的语言是 **A. 唯一的**。 - 描述一个语言的文法是 **B. 不唯一的**。 7. **二义文法判定条件** - 正确选项包括 **B. 该句子有两个不同的最左推导**、**C. 该句子有两个不同的最右推导** 和 **D. 该句子有两棵不同的语法树**。 - 二义文法指的是一个句子可以有不同的推导方式或语法树。 8. **语法制导翻译中的拉链-回填技术** - 正确选项包括 **B. 布尔表达式的计算** 和 **D. 循环语句**。 - 拉链-回填技术常用于条件语句和循环语句的翻译中，以处理跳转指令。 #### 三、解答题解析 1. **LL(1)文法构造** - 对于给定的文法 G[E]，通过消除左递归和公共前缀等方法可以构造出LL(1)文法。 - 构造 FIRST 集合和 FOLLOW 集合是确定LL(1)分析表的基础。 - LL(1)分析表用于指导自顶向下的解析过程。 2. **规范推导过程解析** - 规范推导是指按照文法的产生式规则对一个句子进行推导的过程。 - 句柄是在某一步推导过程中被规约的最左直接短语。 3. **移入-规约分析过程** - 移入-规约分析是一种自底向上的分析方法，其中“移入”是指将输入串中的符号移动到分析栈中，“规约”是指用产生式规约分析栈中的符号。 4. **表格构造文法解析** - 计算 FIRSTVT 集和 LASTVT 集是构造优先关系表的前提。 - 优先关系表用于判断文法是否为算符优先文法。 - 优先函数可以帮助确定何时进行规约。 以上是对给定试卷内容中的关键知识点的详细解释。这些知识点涵盖了编译原理课程的核心内容，对于理解编译过程的不同阶段、语法分析方法以及优化技术等方面具有重要意义。