考研复试6 编译原理

第一章 编译器简介

1. 编译器的核心功能

把源代码翻译成目标代码

2. 编译器设计两个原则：

语义相同；以某种可察觉的方式改进输入程序

3. 编译器内部结构

1. 前端：依赖于源语言，与目标机器无关。将输入的代码映射到 IR。包括分析部分(词法、语法、语义分析)、中间代码生成与优化以及这部分的符号表管理错误处理。
2. 后端：依赖于目标机器，与源语言无关；将 IR 映射到目标机的指令集和有限资源上，处理前端生成的 IR。包括目标代码生成、与目标机有关的优化以及这部分的符号表管理和错误处理工作。

4. 编译器的什么性质最重要：

1. 编译的效率，即编译一个程序的速度和代价
2. 编译生成代码的效率，即编译器生成的可执行程序的运行效率
3. 编译生成代码的质量，即和源代码语义等价性

5. 编译程序的主要构成成分有

词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序、出错处理程序。

6. 编译程序与解释程序区别

前者生成目标代码，而后者不生成；前者产生的目标代码的执行速度比解释程序的执行速度要快；后者人机交互好，适于初学者使用。

7. 图灵机

1. 一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。
2. 它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

第二章 文法

1. 文法：

语言结构的定义和描述，是有穷非空的产生式集合，由终结符、非终结符、产生式、开始符号四部分组成。

2. 终结符和非终结符

终结符：是文法所定义的语言的基本符号，可称为单词、token

非终结符：是用来表示语法成分的符号，称为语法变量

3. 0型文法、1型文法、2型文法、3型文法区别

0型文法 包含 1型文法 包含 2型文法 包含 3型文法

（1）0型文法：对于推导式 α→β，α属于非终结符和终结符并集的正闭包，且α至少含有一个非终结符，并且 β 属于非终结符和终结符的闭包。它可由图灵机识别。

（2）1型文法：上下文有关文法。它可由线性线界自动机识别。

1. 左式可以有多个字符但是必须有一个非终结符；
2. 右式可以有多个字符，可以是终结符或非终结符，但是必须是有限个字符；
3. 左式长度必须不大于右式（除了右式为空）。

（3）2型文法：上下文无关文法。它可由下推自动机识别。2型文法(即上下文无关文法)是描述程序设计语言语法的形式化工具

1. 左式只能有一个字符，而且必须是非终结符；
2. 右式可以有多个字符，可以是终结符或非终结符，但是必须是有限个字符

（4）3型文法：正规文法，包括左线性文法和右线性文法。它可由有限自动机识别。3型文法是是描述程序设计语言词法的形式化工具

1. 左式只能有一个字符且必须是非终结符
2. 右式至多有两个字符，如果有两个字符则必须是一个终结符和一个非终结符；如果有一个字符则必须是终结符。
3. 右式如果是终结符+非终结符，则为右线性文法；如果是非终结符+终结符，则为左线性文法。

4. 二义性文法

二义性文法：一个文法存在某个句子对应两棵不同的语法树。或者说一个文法存在某个句子有不同的最左（最右）推导。

二义性文法存在问题：同一个程序有不同的含义；程序运行的结果不是唯一的。

二义性文法解决方案：文法的重写

5. 最左推导

在推导的任何一步 α → β，都是对 α 中的最左非终结符进行替换。

第三章 词法分析

词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用于语法分析。执行词法分析的程序称为词法分析程序或扫描程序。

词法分析器实现方法：手工编码实现法、根据正则表达式画DNF

正则表达式

1. 正则表达式与正规文法等价：对任意一个正规文法，存在一个定义同一个语言的正则表达式；对每个正则表达式，存在一个生成同一个语言的正规文法；两者可相互转化。
2. 正规式和有限自动机之间可以相互转换，它们之间存在着等价性。

状态自动机：

（1）DNF

1. 有限状态自动机：字母表，状态集、初始状态、终结状态集、转移函数
2. 非确定的有限状态自动机（NFA）：状态转移函数是不确定的，即对于任意字符有多于一个状态可以转移
3. 确定的有限状态自动机（DFA）：每次接受字符走到的状态是确定的，即对于任意字符最多有一个状态可以转移
4. NFA和DFA在表达力上是等价的；任何DFA是某个NFA的一个特例，任何NFA可以通过一个DFA模拟

（2）RE转化为NFA：Thompson算法；

（3）NFA转为DFA：子集构造算法；

（4）DFA转化为词法分析器代码：Hopcroft最小化算法；

第四章 语法分析

需要掌握的：LL(1)，LR(0)，SLR，LR(1)，LALR

1. 语法分析：

1. 概念：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。这种语法短语也成为语法单位，可以表示成语法树。
2. 步骤：
   1. 对程序设计语言的语法规则进行形式化描述（用2型文法）
   2. 根据语言的语法描述形式，定义各种基本语法结构的抽象语法树
   3. 选择一种合适的语法分析算法，并在分析程序中插入动作

2. 自顶向下和自底向上：

（1）自顶向下的分析方法（LL）

1. 概念：也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的单词符号相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。

（2）自底向上的分析算法（LR）

1. 从输入串开始，逐步进行“归约”，直至归约到文法的 开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。
2. 应用面广：能够通过LR分析程序识别所有采用上下文无关文法描述的程序设计语言的语法结构
3. 能有效实现：是无回溯的移进—归约方法
4. 容易查错：LR分析器能够及时发现语法错误和准确指出错误位置

3. 分析树

推导可以表达成树状结构，和推导所用的顺序无关（最左、最右、其他），树中的每个内部节点代表非终结符，每个叶子节点代表终结符，每一步推导代表如何从双亲节点生成它的孩子节点

4. 递归下降分析

递归下降分析方法是一种自上而下的语法分析方法，该方法执行一组递归函数判断输入的单词序列是否符合语法规则。为每个非终结符构造一个分析函数， 用前看符号指导产生式规则的选择

5. 各种语法分析算法：

（1）LL(1) 分析算法

1. 其中的第一个 L 代表从左向右扫描输入，第二个 L 表示产生最左推导，1 代表在决定分析器的每步动作时向前看一个输入符号。
2. LL(1)分析算法优点：算法运行高效，有现成的工具可用；缺点： 能分析的文法类型受限， 往往需要文法的改写

（2）LR(0) 分析算法

1. 从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看 0 个输入符号
2. L是指自左(Left)向右分析输入单词序列；R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)；括号中的 0 是指在决定当前分析动作时向右看的单词个数。
3. LR(0) 分析算法优点：容易实现；缺点：能分析的文法有限，LR(0) 分析表可能包含冲突。

（3）SLR 分析算法

1. 与 LR(0) 分析算法基本步骤相同，仅区别于对规约的处理。
2. 优点：有可能减少需要规约的情况；有可能去除需要移进-规约冲突。
3. 缺点：仍然有冲突出现的可能。

（4）LR(1)

1. 缺点：同心集的分裂使状态数目剧烈增长，导致存储容量的急剧增加。
2. 同心集：如果除前看符号外，两个LR(1)项目集是相同的，则称这两个项目集是同心的。

（5）LALR(1) 文法

1. LALR: lookahead-LR
2. 对 LR(1) 的同心集进行合并
3. 分析能力介于SLR和LR(1)二者之间：SLR < LALR(1) < LR(1)

6. 二义性文法在LR分析中的应用

1. 任何一个二义性文法不是LR类文法，也不是LL(k)文法
2. 任何一个二义性文法不存在与其相应的确定的语法分析器
3. 但对某些二义性文法，可以人为给出优先级和结合性的规定，构造出比相应的非二义性文法更优越的LR分析器

第五章 语义分析

1. 语法制导翻译

1. 基于属性文法的处理过程，对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。
2. 属性文法：是在短语结构文法的基础上加入每个短语和整个句子语义信息所构成的文法
3. 综合属性：用于“自下而上”传递信息。在语法树中，一个结点的综合属性的值，由其子结点的属性值确定。只包含综合属性的属性文法称为S-属性文法。
4. 继承属性：用于“自上而下”传递信息。 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的。既包含综合属性又包含继承属性的是L-属性文法。

2. 语义分析的概念

审查源程序有无语义错误，为代码生成阶段收集类型信息。其任务是检查程序结构（控制结构和数据结构）的一致性或完整性。比如控制流检查，唯一性检查，名字的上下文相关性检查，类型检查等。

第六章 中间表示

1. 中间表示的概念

进行了语法分析和语义分析阶段的工作后，将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。

2. 中间表示的结构：

图IR：语法分析树、抽象语法树、有向无环图、控制流图、依赖关系图、调用图

线性IR：堆栈机代码、三地址代码

第七章 代码优化

1. 代码优化概念

对被优化的程序进行的一种语义保持的变换，语义保持就是程序的可观察行为不能改变

2. 代码优化的目的和意义

代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行 一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。

3. 分类：前端优化、中间表示上的优化、窥孔优化、局部优化、循环优化、全局优化

第八章 目标代码生成

1. 目标代码生成概念

把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。其任务是给源程序的数据分配计算资源、给源程序的代码选择指令。