编译原理知识总结提纲

第一章引论

高级语言程序的执行方式：
- 编译方式：先将源程序整体翻译成目标程序，然后再执行该目标程序。
- 解释方式：以源程序作为输入，在运行期间不产生独立的目标代码，而是边解释边执行源程序本身。
编译和解释的主要区别：是否产生目标代码。
编译程序的工作过程：一般可以划分为五个阶段：
- 词法分析：
  - 规则依据：词法规则。
  - 描述工具：正规式和有限自动机（FA）。
  - 主要任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号，如基本字、标识符、常数、算符、界符等。
- 语法分析：
  - 规则依据：语法规则。
  - 描述工具：上下文无关文法。
  - 主要任务：在词法分析的基础上，根据语言的语法规则对单词符号串进行语法分析，识别出各类语法单位（如短语、子句、句子、程序段和程序等），最终判断输入串是否构成语法上正确的程序。
- 语义分析与中间代码产生：
  - 规则依据：语义规则。
  - 描述工具：属性文法。
  - 主要任务：对语法分析器识别出的各类语法单位分析其含义，并进行静态语义检查与翻译（产生中间代码）。
  - 包含两部分工作：
    1. 对每种语法范畴进行静态语义检查。
    2. 若语义正确，则进行中间代码翻译。
- 代码优化：
  - 变换规则：等价变换规则。
  - 优化原则：等价原则（不改变程序运行结果）、有效原则（目标代码运行时间短、空间小）、合算原则（低代价换取好效果）。
  - 主要任务：对中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
- 目标代码生成：
  - 依赖条件：有赖于目标机器的硬件系统结构和指令系统的语义。
  - 主要任务：把中间代码（或经优化处理后的代码）变换成特定机器上的低级语言代码，实现最后的翻译。
表格管理与出错处理：编译程序的五个阶段都需要进行表格管理和出错处理。
编译前端与后端：
- 编译前端：由与源语言有关但与目标机无关的那些部分组成。主要包括：词法分析、语法分析、语义分析与中间代码产生，部分代码优化工作也可包括在前端。
- 编译后端：包括编译程序中与目标机器有关的那些部分，如与目标机器有关的代码优化和目标代码生成等（不依赖于源语言而仅仅依赖于中间语言，便于编译器移植和代码重用）。

第二章高级程序设计语言的语法描述

语言的定义：程序语言主要由语法（Syntax）和语义（Semantics）两个方面定义。
文法二义性的证明：
- 若一个文法中存在某个句子，它有两个不同的最左（或最右）推导，或者说同一个句子存在两棵不同的语法分析树，则该文法为二义文法。
上下文无关文法（CFG）：
- 所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的一种文法。
文法的 Chomsky 分类：
- $0$ 型文法：短语文法；
- $1$ 型文法：上下文有关文法；
- $2$ 型文法：上下文无关文法；
- $3$ 型文法：正规文法（分为右线性文法和左线性文法）；
- （注：描述语法规则的工具通常为上下文无关文法）
核心技能：掌握最左推导过程和最右推导（规范推导）过程。

第三章词法分析

输出格式：词法分析器输出的单词符号常常表示成二元式形式：（单词种别，单词符号的属性值）。
互化与转换：
- 熟练掌握正规式和正规集的互化（参见课本 P46 页）。
- 掌握 NFA 转化为 DFA 的子集构造法（参见课本 P49 ~ P51 页）。
- 掌握 DFA 的化简（最小化）算法（参见课本 P57 页）。
- （注：课本 P49 页图 3.6 状态 1 到 4 的箭头方向有误；P65 页的题 15 不作要求）

第四章自顶向下语法分析

$\text{LL}(1)$ 文法的判定：
- 掌握 $\text{LL}(1)$ 文法的三个条件（用于判定是否为 $\text{LL}(1)$ 文法）。
集合构造：
- $\text{FIRST}$ 集合和 $\text{FOLLOW}$ 集合的构造算法。
分析表构造：
- $\text{LL}(1)$ 预测分析表的构造方法。
分析过程：
- 预测分析程序的运行和分析过程。

第五章自下而上语法分析

可归约串的刻画：
- 在算符优先分析中，用最左素短语来刻画“可归约串”。
- 在规范归约分析中，用句柄来刻画“可归约串”。
中心问题：自下而上分析的中心问题是怎样判断栈顶的符号串是否可归约，以及如何归约。
短语分析能力：给定一个句型，要能够分析出其短语、直接短语、素短语、最左素短语以及句柄。
优先关系判定：终结符优先关系的判断与计算（参见课本 P89 页）。
算符优先集合： $\text{FIRSTVT}$ 和 $\text{LASTVT}$ 集合的构造。
分析表与过程：
- 算符优先关系表与优先函数的构造。
- 算符优先分析的分析过程（参见课本 P93 页算法）。
LR 分析：
- 掌握 $\text{LR}(0)$ 项目集规范族的构造。
- 掌握三元式（移进-归约状态）的四种变化情况（参见课本 P101 页）。
- （注：所有 $\text{LR}(0)$ 文法都是 $\text{LR}(1)$ 文法；LALR 文法本学期不作要求）

第六章属性文法与语法制导翻译

属性的分类：
- 属性通常分为综合属性和继承属性。
- 终结符只有综合属性，且通常由词法分析器提供。
- 非终结符既可以有综合属性，也可以有继承属性。
S-属性文法与 L-属性文法：
- S-属性文法：只含有综合属性的属性文法。
- L-属性文法：对任意产生式 $A \to X_1 X_2 \dots X_n$ $A \to X_{1} X_{2} \dots X_{n}$ ，其每个语义规则中的属性或者是综合属性，或者是一个继承属性 $X_j$ $X_{j}$ ，且仅依赖于：
  1. 该产生式中 $X_j$ 左边的符号 $X_1, X_2, \dots, X_{j-1}$ 的属性；
  2. 产生式左部非终结符 $A$ 的继承属性。
- （ $\text{S}$ -属性文法是 $\text{L}$ -属性文法的一个特例）

第七章中间代码生成

中间代码的形式：
- 后缀式（逆波兰表示法）；
- 三地址代码：三元式、四元式、间接三元式；
- 图表示法：有向无环图（DAG）、抽象语法树（AST）。
后缀式转换：后缀式与中缀表达式的互化。
图的绘制与区别：
- 熟练绘制 DAG 和抽象语法树。
- DAG 与抽象语法树的区别：在一个 DAG 中，代表公共子表达式的结点具有多个父结点（被共享）；而在抽象语法树中，公共子表达式被表示为重复的子树。
三地址代码表示：会用三元式、四元式和间接三元式表示句子。
语法制导翻译：给定一个文法，能够判断使用何种方式进行翻译，并能写出翻译结果（重点掌握 $\text{S}$ -属性文法的自下而上翻译方式，注意课本 P196 页的例 7.6）。

第八章符号表

组成结构：符号表主要包括名字栏和信息栏。
基本操作：
1. 查询给定名字是否已在符号表中。
2. 往表中填入一个新的名字。
3. 访问给定名字的某些信息。
4. 往表中填写或更新给定名字的某些信息。
5. 删除一个或一组无用的项。
名字栏组织方式：直接填写式和间接方式（使用指针指向名字串的存储空间）。
内情向量表：数组信息表又称内情向量表，用于存放数组的维数、各维上下界以及元素类型等关键信息（注意课本 P223 页的图 8.1）。
常用表格：编译前三个阶段产生的主要表格包括：符号名表（SNT）、常数表（CT）、入口名表（ENT）、标号表（LT）、四元式表（QT）。

第九章运行时存储空间组织

静态正文与运行时联系：
- 编译程序的最终目的是将源程序翻译成等价的目标程序。在生成目标代码前，需要把程序的静态正文和实现这个程序的运行时的活动联系起来，确定在代码运行时刻，源程序中定义的各种变量、常量等用户定义的量是如何存放以及如何访问的。
过程的活动：一个过程的活动指的是该过程的一次执行。
参数传递途径：传地址（Call by Reference）、传值（Call by Value）、传名（Call by Name）、传结果（Call by Result）。
存储分配：编译程序为了使它编译后得到的目标程序能够运行，需要从操作系统中获得一块存储空间。
活动记录（Activation Record）：为了管理程序在一次执行过程中所需的信息，使用一个连续的存储块，该连续存储块称为活动记录。
活动记录的结构：
- 连接数据：
  - 返回地址：保存子程序调用结束后的返回点。
  - 动态链：指向调用该过程前最新活动记录地址的指针（用于维护动态调用栈）。
  - 静态链：指向静态直接外层最新活动记录地址的指针，用于访问非局部数据。
- 形式单元：存放相应的实在参数的地址或值。
- 局部数据区：存放局部变量、内情向量以及临时工作单元。
数据空间分配策略：
- 静态分配策略：在编译时对所有的数据对象分配固定的存储单元，且在运行时始终保持不变。
- 栈式动态分配策略：在运行时把存储器作为一个栈进行管理。每当调用一个过程，其活动记录就动态分配在栈顶；过程退出时释放所占用的空间。
- 堆式动态分配策略：在运行时把存储器组织成堆结构，方便用户程序动态申请与归还。申请时从堆中划出块，释放时退回给堆。

第十章代码优化

优化的定义：对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
目的：产生更高效（时间更短、空间更小）的目标代码。
优化遵循的原则：
- 等价原则：经过优化后不应该改变程序运行的结果。
- 有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小。
- 合算原则：应尽可能以较低的代价取得较好的优化效果。
常见的优化技术：
- 局部优化（属于基本块级别）：删除公共子表达式、复写传播、删除无用代码。
- 循环优化（属于循环级别）：代码外提、强度削弱、删除归纳变量。
基本技能：
- 熟练划分基本块并绘制控制流图（DFG）。
- 会用 DAG（有向无环图） 进行基本块内的局部优化。

第十一章目标代码生成

输入信息：代码生成器的输入主要包括中间代码和符号表中的信息。
基本任务：把语义分析后或优化后的中间代码变换成特定机器上的目标代码。
目标代码的三种形式：
1. 能够立即执行的绝对机器语言代码（所有地址均已定位）；
2. 待装配的机器语言模块（可重定位目标模块，需经链接装配）；
3. 汇编语言代码（尚需经过汇编程序汇编，转换成可执行的机器语言代码）。
着重考虑的两个问题：
1. 如何使生成的目标代码较短；
2. 如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数（这两个问题都直接影响目标代码的执行速度）。

音乐

音乐

编译原理知识总结提纲

编译原理知识总结提纲

第一章引论

第二章高级程序设计语言的语法描述

第三章词法分析

第四章自顶向下语法分析

第五章自下而上语法分析

第六章属性文法与语法制导翻译

第七章中间代码生成

第八章符号表

第九章运行时存储空间组织

第十章代码优化

第十一章目标代码生成

音乐

课程

编译原理知识总结提纲

编译原理知识总结提纲#

第一章 引论#

第二章 高级程序设计语言的语法描述#

第三章 词法分析#

第四章 自顶向下语法分析#

第五章 自下而上语法分析#

第六章 属性文法与语法制导翻译#

第七章 中间代码生成#

第八章 符号表#

第九章 运行时存储空间组织#

第十章 代码优化#

第十一章 目标代码生成#

编译原理知识总结提纲

第一章引论

第二章高级程序设计语言的语法描述

第三章词法分析

第四章自顶向下语法分析

第五章自下而上语法分析

第六章属性文法与语法制导翻译

第七章中间代码生成

第八章符号表

第九章运行时存储空间组织

第十章代码优化

第十一章目标代码生成