燕山大学软件工程编译原理考试提纲

编译原理考试范围

编译程序构成、编译程序与解释程序区别，词法分析、语法分折、语义分折及其任务，文法，语言，句型，句子，短语，推导，归约，句柄，文法、语言二义性，文法分类，有穷自动机、正则式、正则文法，有穷自动机确定化最小化，词法描述工具，语法分析分类，计算first follow select集，消除左递归，提取左公因子，LL（1）文法（判别、构造预测分折表、句子分析），LR（0）文法（判别、项目集构造、分析表构造、句子分析），SLR（1）文法，冲突，LR（1）文法、LALR（1）（判别、项目集DFA构造、分析表构造、句子分析），可归前缀，活前缀，综合属性，继承属性，符号表作用，静态语义分析任务，属性计算，带标注的语法分析树，S、L属性文法的语义计算，S、L翻译模式语义计算，中间代码形式，赋值语句、布尔表达语句、控制语句翻译，拉链与代码回填，存储策略分类，活动记录，DispIay表

编译原理考试提纲

一、 编译程序概述

1. 编译程序构成
   1. 分析部分（前端）：与源语言相关，包括词法分析、语法分析、语义分析。
   2. 综合部分（后端）：与目标语言相关，包括中间代码生成、代码优化、目标代码生成。
2. 编译程序与解释程序区别
   1. 编译器：将整个源程序翻译为目标程序后执行。
   2. 解释器：边翻译（解释）边执行。

二、 词法分析

1. 任务：读入源程序字符流，识别单词（词素），生成词法单元（Token）。
2. 词法描述工具
   1. 正则表达式（正则式）。
   2. 正则文法（3型文法）。
   3. 有穷自动机（FA）。
3. 有穷自动机（FA）
   1. 非确定有穷自动机（NFA）：定义、表示。
   2. 确定有穷自动机（DFA）：定义、表示。
   3. NFA到DFA的确定化（子集构造法）。
   4. DFA的最小化（状态等价与划分）。
4. 词法分析器实现
   1. 根据正则表达式/正则文法构造NFA。
   2. 将NFA确定化为DFA。
   3. 对DFA进行最小化。
   4. 使用最小化DFA识别单词。
5. 词法错误处理
   1. 错误类型：单词拼写错误、非法字符。
   2. 恐慌模式恢复：从剩余输入中不断删除字符，直到发现一个正确的字符为止。

三、 语法分析

（一） 概述与分类

1. 自顶向下分析：从文法开始符号推导出输入串。
2. 自底向上分析：从输入串归约为文法开始符号。

（二） 自顶向下分析

1. 最左推导：总是选择每个句型的最左非终结符进行替换。
2. 通用形式与问题
   1. 递归下降分析：一组递归过程，可能需要回溯。
   2. 预测分析：递归下降的特例，向前看固定符号（LL(k)），无需回溯。
3. 文法转换（为LL(1)分析做准备）
   1. 消除左递归（直接与间接）。
   2. 提取左公因子。
4. LL(1)文法与分析
   1. 相关集合计算：
      1. FIRST集：文法符号串首终结符集。
      2. FOLLOW集：非终结符后随终结符集。
      3. SELECT集：产生式的可选集。
   2. LL(1)文法判别条件：同一非终结符各产生式的SELECT集互不相交。
   3. 预测分析表构造。
   4. 句子分析过程：
      1. 递归预测分析法：为每个非终结符编写递归函数。
      2. 非递归预测分析法（表驱动）：使用分析栈和预测分析表。

（三） 自底向上分析（移入-归约分析）

1. 基本概念
   1. 句柄：句型的最左直接短语。
   2. 规范归约（最左归约）：每次归约当前句型的句柄。
   3. 活前缀：规范句型的一个前缀，该前缀不包含句柄之后的任何符号。
   4. 可归前缀：包含句柄的活前缀。
2. LR分析家族（核心：构造识别活前缀的DFA——LR自动机）
   1. LR(0)分析
      1. LR(0)项目（项）：右部某位置标有圆点的产生式。
      2. 项目集规范族（DFA）构造（CLOSURE和GOTO函数）。
      3. LR(0)分析表构造（ACTION与GOTO表）。
      4. LR(0)文法判别：分析表中无冲突。
      5. 冲突：移入-归约冲突、归约-归约冲突。
   2. SLR(1)分析
      1. 在LR(0)基础上，用FOLLOW集解决冲突。
      2. SLR(1)分析表构造。
      3. SLR(1)文法判别。
   3. LR(1)分析
      1. LR(1)项目：带**向前看符号（展望符）**的项。
      2. LR(1)项目集规范族构造。
      3. LR(1)分析表构造。
      4. LR(1)文法判别。
   4. LALR(1)分析
      1. 核心思想：合并LR(1)的同心项目集（核心相同，展望符不同）。
      2. LALR(1)分析表构造（合并后可能引入新冲突，但比SLR强）。
      3. LALR(1)文法判别。
   5. 分析能力比较：LR(0) < SLR(1) < LALR(1) < LR(1)。
3. 二义性文法的LR分析
   1. 二义性文法都不是LR的。
   2. 可通过赋予算符优先级和结合性来消解冲突，从而用LR分析。

（四） 语法分析中的错误处理

1. 错误检测时机：
   1. 栈顶终结符与当前输入符号不匹配。
   2. 栈顶状态与当前输入符号在分析表对应项为空。
2. 错误恢复策略：
   1. 恐慌模式：不断丢弃输入符号，直到出现“同步词法单元”（如FOLLOW集中的符号）。
   2. 短语层次恢复：在栈顶进行局部修正（如插入/删除/替换符号）。

四、 语法制导翻译与中间代码生成

（一） 语法制导定义（SDD）与翻译方案（SDT）

1. 属性
   1. 综合属性：自底向上传递信息（子节点 -> 父节点）。
   2. 继承属性：自顶向下或水平传递信息（父节点/兄弟节点 -> 当前节点）。
2. 属性计算
   1. 依赖图：描述分析树中属性间的依赖关系。
   2. 计算顺序：拓扑排序。
3. S属性定义与L属性定义
   1. S属性定义：只包含综合属性。适合自底向上分析。
   2. L属性定义：继承属性仅依赖于父节点或左边兄弟节点的属性。适合自顶向下分析。
4. 翻译模式（SDT）
   1. 语义动作可以嵌入在产生式右部任何位置。
   2. 实现方式：
      1. 基于预测分析的SDT实现（递归下降或非递归）。
      2. 基于LR分析的SDT实现：需要消除嵌入动作（引入标记非终结符），或通过复写规则在栈中模拟继承属性。

（二） 中间代码形式

1. 三地址码：x = y op z 形式。
2. 语法结构树 / 抽象语法树（AST）。
3. 后缀表示等。

（三） 各种语句的翻译（生成三地址码）

1. 声明语句的翻译
   1. 收集标识符属性（种属、类型、宽度、存储偏移量）并填入符号表。
2. 赋值语句的翻译
   1. 简单变量赋值。
   2. 数组引用翻译：计算数组元素地址（行优先存储）。
3. 布尔表达式的翻译
   1. 作为条件控制的布尔表达式翻译。
   2. 拉链与回填技术：
      1. makelist(i)：创建仅包含标号i的列表。
      2. merge(p1, p2)：合并两个标号列表。
      3. backpatch(p, i)：将标号i回填到p所指列表的所有指令中。
4. 控制流语句的翻译（if-then-else, while-do, switch-case等）
   1. 使用继承属性（如.next）和回填技术生成跳转代码。
5. 过程调用语句的翻译
   1. 参数传递（param指令）。
   2. 过程调用（call指令）。

（四） 类型系统与类型检查

1. 类型表达式：基本类型、数组、指针、笛卡尔积、函数、记录等构造符。
2. 类型等价与类型检查规则。

五、 符号表与语义分析

1. 符号表的作用
   1. 收集并维护标识符的属性信息（种属、类型、存储位置、作用域、参数信息等）。
   2. 支持各编译阶段对标识符信息的查询。
2. 静态语义分析的主要任务
   1. 收集信息：填入符号表。
   2. 语义检查：
      1. 变量/过程未经声明就使用。
      2. 重复声明。
      3. 类型不匹配（运算分量、操作符、数组下标、过程参数等）。
      4. 控制流检查。
      5. 唯一性、关联性检查。

六、 运行时存储管理

1. 存储策略分类
   1. 静态存储分配：编译时确定（如全局变量、静态变量）。
   2. 栈式动态存储分配：用于过程/函数活动（活动记录）。
   3. 堆式动态存储分配：用于动态申请的数据（如malloc/new）。
2. 活动记录（Activation Record）
   1. 构成：返回值、实参、控制链（动态链）、访问链（静态链）、保存的机器状态、局部数据、临时变量等。
   2. 过程调用/返回时活动记录的压栈/弹栈。
3. 非局部数据的访问
   1. 静态作用域（词法作用域）：内层过程可以访问外层过程中声明的名字。
   2. 访问链（静态链）：指向定义该过程的外层过程的最新活动记录。
   3. Display表：一个指针数组，指向各嵌套层次过程的最新活动记录。用于高效访问非局部数据。
4. 堆管理
   1. 分配与释放策略（如首次适应、最佳适应等）。
   2. 碎片问题。