绪论

推荐视频：哈工大 - 陈鄞
推荐用书：龙书，豆瓣评分9.1

几乎每本编译原理的教材都是分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分

不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。

《龙书》是计算机相关书籍。本书深入讨论了编译器设计的重要主题，包括词法分析、语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等，并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例，每章都提供了大量的练习和参考文献。本书从介绍编译的原理性概念开始，然后通过构建一个简单的编译器来逐一解释这些概念。

参考链接：https://blog.csdn.net/kojhliang/article/details/82881788

第1章 绪论

1.什么是编译

2.编译系统的结构

3.词法分析

1.词法单元(token)

token <种别码，属性值>

第2章 语言及其文法

字母表 $\sum$

${\sum }^{+}$ 正闭包 ：长度为n的字符串集合
${\sum }^{\ast }$ 克林闭包： 任意长度的字符串集合。即是，正闭包加 空串$\epsilon$

$\epsilon$ (epsilon) /ˈepsɪlɑːn/

概念

终结符

• 小写字母：a、b、c
• 数字：0、1…9
• +、 *
• (
• id、if
  
  终结符 (token / terminal symbol)
  

非终结符

• 开始符号S
• 大写字母：A B C E T F
  

产生式

文法

Chomsky文法分类体系

0型文法 （Type-0 Grammar）

无限制文法 / 短语结构文法

1型文法（Type-1 Grammar）

上下文有关文法 (CSG)

2型文法（Type-2 Grammar）

上下文无关文法 (CFG)

3型文法（Type-3 Grammar）

正则文法 (RG)
①右线性文法
②左线性文法

第3章 词法分析

正则表达式

正则表达式 (Regular Expression，RE)

有穷自动机

1.有穷自动机 (Finite Automat，FA)

2.正则文法 $\iff$ 正则表达式RE $\iff$ 有穷自动机FA

确定的有穷自动机 DFA

1.确定的FA（Deterministic finite automata, DFA）
2.DFA更易于计算机计算

不确定的有穷自动机 NFA

1.不确定的FA（Nondeterministic finite automata, NFA）
2.NFA更易于人类阅读

从正则表达式到有穷自动机

RE->NFA->DFA

恐慌模式

第4章 语法分析

自顶向下的语法分析

1.最左推导：每次推导都选最左边的

2.最右推导：每次推导都选最右边的

3.自顶向下的缺陷：
①
②不能解决左递归问题

4.消除直接左递归

自底向上的语法分析

FIRST 串首终结符集

α的串首终结符集 FIRST(α)：可以从α推导出的所有串首终结符构成的集合。

S->aB(" -> "表示定义为)

FOLLOW

后继符号集 FOLLOW

SELECT 可选集

产生式的可选集

LL(1)文法

LL(1)文法：第一个L表示从左到右扫描输入串，第二个L表示生成的是最左推导

LR

LR(0) 分析法

LR(0)项目：右部有圆点的产生式
移进项目：点在右部的最左侧
待约项目：点在右部的中间
归约项目：点在右部的最右侧
后继项目：两个产生式，圆点的位置只相差一个符号

项目集闭包：点右边是非终结符，就会出现等价的状态。所有等价状态是一个项目集闭包，对应自动机的一个状态。

等价

SLR(1) 分析法

LR(0)加强

LR(1) 分析法

SLR加强

LALR 分析法

削弱，目的是减少状态数。代价是推迟了错误的发现。

第5章 语法制导翻译

语法制导翻译的概念

语法制导翻译使用CFG()来引导对语言的翻译，是一种面向文法的翻译技术。

5.1 语法制导定义 SDD

注释分析树
属性文法

5.2 SDD的求值顺序

S-属性定义
L-属性定义：S-属性定义一定是L-属性定义

5.3 语法制导翻译 SDT

1.定义：语法制导翻译 SDT（Syntax-directed translation）。是在产生式右部中嵌入了程序片段(称为语义动作)的CFG
基于属性文法的处理过程，对单词符号串进行语法分析，构造语法分析树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点处按语义规则进行计算。

语法制导翻译是指一种源语言代码的翻译完全由语法分析器驱动的编译器的实现方法。

第6章 中间代码生成

6.1 类型表达式

类型也有结构，类型的结构用类型表达式来表示。
基本类型是类型表达式。类型名也是类型表达式。将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式。

6.2 声明语句的翻译

lexeme 语义

[num] C₁：数组下标表达式序列

↑T₁：指针类型（↑：指针关键字）

6.3 简单赋值语句的翻译

赋值语句翻译的主要任务：生成对表达式求值的三地址码

赋值语句的SDT

gen(code)：生成三地址指令code

归约状态：

6.4 数组引用的翻译

6.5 控制流语句SDT

S.next：是一个地址，该地址中存放了紧跟在S代码之后的指令(S的后继指令)的标号

控制流语句的SDT

newlabel( )： 生成一个用于存放标号的新的临时变量L，返回变量地址

label(L): 将下一条三地址指令的标号赋给L

call：过程调用关键字
param指令

第7章 运行存储分配

7.1 运行存储分配概述

7.2 静态存储分配

1.顺序分配法

2.层次分配法

7.3 栈式存储分配

活动树

7.4 调用序列和返回序列

7.5 非局部数据的访问

访问链 (Access Links)、静态作用域原则：第i层可以调用i+1层(外层调用内层)
支持过程(函数)嵌套的语言：Pascal
不支持过程嵌套的语言：C语言、C++

访问链的建立

①外层调用内层

②本层调用本层：访问链相同，直接复制

③内层调用外层

7.6 堆存储分配

7.7 符号表、符号表的建立

第8章 代码优化 (降低资源消耗，加快运行速度)

代码优化：对代码进行等价的程序变换，使之运行的更快，或占用的空间更少，降低时间、空间复杂度。

8.1 流图

基本块

基本块划分算法

判断首指令：
①一个指令序列的第一条(三地址)指令是首指令
②跳转指令goto的目标指令是首指令
③跳转指令goto的下一条指令是首指令

流图 (Flow Graphs)

B→C：
①顺序执行，不存在无条件跳转指令
②跳转指令

8.2 常用的代码优化方法

1.代码优化的分类
①机器无关优化 （针对中间代码）
②机器相关优化 （针对目标代码）
③局部代码优化 （单个基本块范围内的优化）
④全局代码优化 （面向多个基本块的优化）

2.常用代码优化方法
①删除公共子表达式
同一个基本块内：局部公共子表达式
不在同一个基本块内：全局公共子表达式
将局部公共子表达式和全局公共子表达式进行删除。

②删除无用代码

③常量合并

④代码移动

⑤强度削弱 (Strength Reduction)
用较快的操作代替较慢的操作（运算代价高的指令代替运算代价低的指令），如用加代替乘，用乘代替除

⑥删除归纳变量
归纳变量：对于一个变量x ，如果存在一个正的或负的常数c，使得每次x被赋值时它的值总增加c ，那么x就称为归纳变量(Induction Variable)

8.3 基本块的优化

有向无环图 (Directed Acyclic Graph，DAG)
定值变量表：为什么变量定值，就把该变量添加到该结点的定值变量表中

基本块的DAG图

1.检测公共子表达式
基本块的DAG图，可以帮助我们自动检测出基本块中的局部公共子表达式。

2.删除无用代码
活跃变量：其值在之后可能被使用
无用代码：其值在之后不会被使用

8.4 数据流分析

语句的数据流模式

IN[s]：语句s之前的数据流值
OUT[S]：语句s之后的数据流值
f_s：语句s的传递函数

基本块的数据流模式

8.5 到达定值

用途：检测循环计算

①IN[B]ⁱ⁺¹：根据流图，知道IN[B]ⁱ⁺¹= OUT[B]ⁱ。
②OUT[B]ⁱ⁺¹：可根据gen{d_i}使得IN[B]ⁱ⁺¹第i位置1；根据kill{d_i}使得IN[B]ⁱ⁺¹第i位置0

8.6 活跃变量分析

引用-定值链(Use-Definition Chains)，简称ud链，是一个列表，对于变量的每一 次引
用，到达该引用的所有定值都在该列表中

use：引用
def：定值

定值-引用链(Definition-Use Chains)，简称du链，设变量x有一个定值d，该定值所有能够到达的引用u的集合称为x在d处的定值-引用链，简称du链

8.7 可用表达式分析

1.定义

2.作用
①消除全局公共子表达式
②进行复制传播

e_gen_B
e_kill_B

8.8 支配结点和回边

支配结点

①入口结点：支配流图中的所有结点（支配结点树的根结点）
②每个结点都至少支配它自己（支配结点树的叶结点）

支配结点树(Dominator Tree)
每个结点只支配它和它的后代

直接支配结点

回边

有指向自己的支配结点的边，称为回边。

8.9 代码移动

1.代码移动、前置首结点

第9章 代码生成

9.1 代码生成器的主要任务

9.2 窥孔优化