编译原理理论笔记

$\mathcal{Author:gpf}$

概论

源程序：用汇编语言或高级语言编写的程序

目标程序：用目标语言所表示的程序

翻译程序：将原程序转换为目标程序的程序称为翻译程序

汇编语言——汇编程序——>机器语言

高级语言——编译程序——>目标程序

解释程序：对源程序进行解释执行的程序

编译过程的5个基本阶段：词法分析、语法分析、语义分析+生成中间代码、代码优化、生成目标程序

词法分析：分析和识别单词（关键字、标识符、常数、分界符+运算符）
语法分析：根据语法规则，识别出各种语法成分，并进行语法正确性检查
语义分析、生成中间代码：进行语义分析并产生相应的中间代码
代码优化：得到高质量的目标程序
生成目标程序：根据机器进行

编译程序的7个逻辑部分：5个基本阶段+符号表管理+出错处理

遍（PASS）：对源程序或中间形式从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序

前端：与源程序有关的编译部分。词法分析、语法分析、语义分析、中间代码生成

后端：与目标机有关的部分。代码优化、目标代码生成

形式语言

语言

字母表（符号集合）、符号（字母表中的元素）、符号串（符号的又穷序列）、空符号串

符号串的连接：x=XX,y=YY——>xy=XXYY

符号串集合的乘积（笛卡尔积）：A=s,t；B=u,v——>AB=st,sv,tu,tv

幂运算、闭包同离散二

文法

文法 $G=(V_n,V_t,P,Z)$

$V_n$：非终结符号集
$V_t$：终结符号集（$V=V_n\cup V_t$，称文法的字汇表）
$P$：产生式或规则的集合
$Z$：开始符号（识别符号）
规则：$(U,x),|U|=1,|x|\ge0$ ，写作 $U::=x或U\rightarrow x$

语法规则：<句子>::=<主语><谓语>

推导：<句子>=><主语><谓语>

$v\overset{+}=>w$：根据规则推导一步或多步
$v\overset{*}=>w$：根据规则推导0步或多步
$vUy=|=>xuy$：规范推导（最右推导）

规范规约与规范推导互为逆过程

语言：$L(G[Z])=\{x|x\in V_t^*,Z\overset{+}=>x\}$

语言相同，则两种文法等价

句型：$\{x|x\in V^*,Z\overset{*}=>x\}$，即从开始符号随便推
句子：$\{x|x\in V_t^*,Z\overset{+}=>x\}$，推到全都是终结符为之

左递归、右递归

递归文法：可用有穷条规则定义无穷语言。但左递归文法不能用自顶向下的方法进行语法分析

句型与短语

句型的短语：句型w，其中一个成分U一步或多步推导到了u，则u是句型w相对于U的短语

句型的简单短语：1步推导称简单短语

句型的句柄：最左简单短语

注意：空串既不是终结符也不是非终结符，不是短语，也不在语法树里面

二义性

规范规约：对句型中最左简单短语进行的规约（相当于从最左边开始规约）

规范句型：通过规范推导或规范规约得到的句型

若对于一个文法的某一句型存在两颗不同的语法树，则该文法是二义性文法，否则是无二义性文法

若一个文法的某个句子存在两个不同的规范推导，则是二义性的

若一个文法的某规范句型的句柄不唯一，则二义性

有害规则：U::=U

多余规则：始终用不到的规则、退不出任何终结符号串的规则。

若文法中没有有害规则或多余规则，则称该文法是压缩过的

文法的其他表示：

扩充的BNF表示：<,>,::=,| 加上 {,},[,],(,)
语法图

文法分类

$L_3\subset L_2\subset L_1\subset L_0$

0型文法：$P：u::=v$ ，其中 $u\in V^+,v\in V^*,V=V_n\cup V_t$

称为短语结构文法，构成的语言L0可以用图灵机接受

1型文法：$P：xUy::=xuy$ ，其中 $U\in V_n,x、y、u\in V^*$

称为上下文有关/敏感文法，构成的语言L1可以由一种线性界限自动机接受

2型文法：$P：U::=u$ ，其中 $U\in V_n,u\in V^*$

称为上下文无关文法（与BNF表示等价），构成的语言L2可以由下推自动机接受

3型文法：$P：U::=t或U::=Wt$（左线性，W在右边称右线性），其中 $U、W\in V_n,t\in V_t$

称为正则文法，构成的语言L3又称正则语言可以由有穷自动机接受

0型文法可以产生L0、L1、L2、L3，
但2型文法只能产生L2、L3不能产生L0、L1
3型文法只能产生L3

数学上正则文法不允许有空串，但编译允许

词法分析（正则、DFA）

正则文法、左右线性文法、有穷自动机

正则文法与状态图

左线性文法，设开始状态为S，开始符号代表终止状态

若 $Q::=t,Q\in V_n,t\in V_t$ ，则画一条S指向Q，标记为t的线
若 $Q::=Rt,Q、R\in V_n,t\in V_t$ ，则画一条R指向Q，标记为t的线

右线性文法则线的方向相反

正则表达式与DFA

字母表上的正则表达式与正则集合：

$\Sigma$ 上的正则表达式	正则集合
$\varepsilon$	$\{\varepsilon\}$
$\phi$ （空正则表达式集合）	$\phi$
a（ $a\in\Sigma$ ）	$\{a\}$
$U\|V$	$L(U)\cup L(V)$
$U\cdot V$	$L(U)\cdot L(V)$
$U^*$	$L(U)^*$

正则表达式相等 $\Leftrightarrow$ 正则表达式表示的语言相等

正则表达式的|运算具有交换律、结合律、分配律

正则表达式与DFA等价：在 $\Sigma$ 上的一个子集 $V\subseteq\Sigma^*$ 是正则集合，当且仅当存在一个DFA M，使得 $V=L(M)$

确定的有穷自动机（DFA）

$M=(S,\Sigma,\delta,s_0,Z)$ ，其中

S——有穷状态集
$\Sigma$ ——输入字母表
$\delta$ ——映射函数，$S\times\Sigma\rightarrow S$ ，根据当前状态S以及输入的字母a（字母表内的字母）转移到下一个状态
$s_0$ ——初始状态
Z——终止状态集

NFA：映射函数是多值函数，或输入允许为空。即从同一状态出发，有以同一字符标记的多条边，或者有以ε标记的特殊边的自动机。

NFA的确定化

集合I的ε-闭包：设I是一个状态集的子集，则 $\varepsilon-closure(I)$ 包括：I本身的状态、从I中任意状态经过任意条ε弧能够到达的任何状态

$I_a$：设I是一个状态集的子集，$I_a=\varepsilon-closure(J)$ ，其中 $J=\underset{s\in I}\cup\delta(s,a)$

其实求 $I_a$ 只需三步：

求出从I中的状态出发，经过ε弧能够到达的状态

加上I中的状态本身，从这些状态出发，沿着a弧能到达的状态为 $I'$

$I'$ 以及走 $\varepsilon$ 到的状态集合为 $I_a$

确定化NFA：

将开始状态的ε-闭包作为新的开始状态
如图填表，新出现的状态填在下一行的最左侧，直到没有新状态为止
最左侧一列即为新的状态，右侧即为状态转移矩阵

DFA的最小化

状态S和T等价的条件是：

一致性条件：状态S和T必须同时为可接受状态或不可接受状态
蔓延性条件：对于所有输入符号，状态S和T必须转换到等价的状态里

“分割法” ：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的。

TODO:LEX考吗？

LEX

由三部分组成：辅助定义式、识别规则、用户子程序

辅助定义式：$D_1\rightarrow R_1,D_2\rightarrow R_2,……$ ，即正则表达式的名字->正则表达式

识别规则：$P_1\ \{A_1\},...$ ，Pi是定义在 $\Sigma\cup\{D_1,D_2,...\}$ 上的正则表达式，A1是语句序列，表示识别出词形为Pi的单词后，词法分析器所应作的动作（如返回单词的类别编码和单词值）

工作原理：扫描每条规则Pi，转化成NFA，然后转化成DFA，最后生成状态转移矩阵与控制执行程序

二义性问题：

最长匹配原则：可以识别为P1+P2或单独的P3，则P3优先
优先匹配原则：可以识别为P1或P2，则排在前面的P1优先（如保留字和标识符）

工作流程：一直吃字符直到走不动，然后退掉一个，看是否在终态里

语法分析（LL,LR,SLR）

自顶向下分析：递归子程序法、LL分析法

自底向上分析：算符优先文法、LR分析法

自顶向下

问题：左递归、回溯

处理左递归

法一：用扩充的BNF表示来改写文法

提因子—— $U::=xy|xw|...|xz$ 可改写为 $U::=x(y|w|...|z)$ ，注意把ε放在最后
消左递归—— $U::=x|y|...|z|Uv$ 可改写为 $U::=(x|y|...|z)\{v\}$

法二：改成多条文法

$P::=P\alpha|\beta$ 可改写为 $P::=\beta P',P'::=\alpha P'|\varepsilon$

为避免回溯，可以改写文法（反复提取左因子）/超前扫描

若无左递归、FIRST集两两不相交，则可以构造有效的、不带回溯的自顶向下分析器

递归下降分析法：编译实验。

递归子程序法、LL分析法对应的是最左推导

LL分析法

分析表+执行程序（人）+符号栈

符号栈的四种状态：

开始状态：#E
工作状态：#...X
出错状态
结束状态：#

分析表：符号栈栈顶为A、当前输入符号为a时，使用的规则为 $M[A,a]=A::=\alpha_i$

分析表的构造：

FIRST集——$FIRST(\alpha)=\{a|\}$ TODO 就是字面意思，A->a|c则ac

FOLLOW集——A->Ba则B的follow有a

求FIRST：

$\alpha=X_1X_2...X_n$

求FOLLOW

填分析表

LL(1)文法：一个文法G，其分析表不含有多重定义入口，则为LL1文法

另有充要条件：对于G的每个终结符A的任意两条规则 $A::=\alpha|\beta$ ，下列条件成立

$FIRST(\alpha)\cap FIRST(\beta)=\Phi$
若 $\beta\overset{*}=>\varepsilon$ ，则 $FIRST(\alpha)\cap FOLLOW(A)=\Phi$

若是左递归的或二义性的，则至少有多个多重入口

步骤、符号栈、读入符号、剩余符号、规则

自底向上

一般方法：移进-规约

将输入符号串移入符号栈，若形成当前句型（栈内符号串+未处理的输入）的句柄，则规约。直到读完所有符号

算符优先分析

算符文法（OG）：文法中没有形如 $U::=...VW...(V,W\in V_n)$ 的规则

算符优先文法（OPG）：任意两个终结符之间，至多只有优先关系中的一种

优先关系表示为a=b,a<b,a>b中的一种，三种符号中间都要加一个·，但是markdown打不出来，暂时用等号、小于号、大于号代替

算符优先分析方法可以分析二义性文法所产生的语言

构造优先关系矩阵：

求“=”：检查每一条规则，若有 $U::=...ab...$ 或 $U::=...aVb...$ 则 $a=b$

定义 $FIRSTVT(U)=\{b|U\overset{+}\Rightarrow b...或U\overset{+}\Rightarrow Vb...,b\in V_t,V\in V_n\}$

与first集的区别：first集不包括U->Vb的情况

求FIRST：

按定义
$U::=V...$，则 $FIRSTVT(V)\subseteq FIRSTVT(U)$

定义 $LASTVT(U)=\{a|U\overset{+}\Rightarrow ...a或U\overset{+}\Rightarrow ...aV,a\in V_t,V\in V_n\}$

与last集的区别：last集是跟在U后面的集合，lastvt是U的末尾集合

求LAST：类似

构造优先关系矩阵：

对于每条规则 $U::=x_1x_2...x_n$

对终结符填=
对于xi终结、xi+1非终结：FIRSTVT（xi+1）中的每个b置xi<b
xi非终结……a>xi+1
构造E'=#E#，补充#的优先关系

素短语：至少包括一个终结符号且除自身外不再包含其他素短语的短语

最左素短语：算符优先文法中，句型 $N_1a_1...N_na_nN_{n+1}$ 的满足 $a_{j-1}N_j...N_{i+1}a_{i+1}$ 且 $a_{j-1}<a_j=...=a_i>a_{i+1}$ 的最左子串（中间大，两边小）

步骤、符号栈、输入串、优先关系、动作

LR分析

规范句型：通过规范规约得到的句型

规范句型的活前缀：对于句型 $\alpha\beta t$ ，$\beta$ 表示句柄，若 $\alpha\beta=u_1u_2...u$

TODO:goto表、action表、SLR分析

步骤、状态栈、符号（状态栈去掉状态bian'hao）、输入串、动作

符号表与运行栈

符号表：编译过程中，编译程序用来记录源程序中各种名字的特性信息（名字+特性信息）

内容：名字+特性。其中特性包括

标识符的种类：一般变量、数组、参数、函数、过程、标号等等
类型：整数、浮点型、字符型、指针……
值
地址
大小

组织方式：统一符号表、不同类的不同表、折中（二者组成统一的表，用指针连接）

另组织方式：无序符号表、有序符号表、散列符号表

栈式符号表

画的时候从下往上画（下图的翻转），数组要存模板吗？

运行栈

ms-win+VS+X86下，从高地址到低地址分别是全局和静态量表、代码段、运行栈、内存堆

典型的运行栈包括：函数的返回地址、全局寄存器的保存区、临时变量的保存区、未分配到全局寄存器的局部变量的保存区、其他辅助信息的保存区（如display）

运行时的存储组织与管理包括：目标程序运行时所需存储空间的组织与管理、源程序中变量存储空间的分配

静态存储分配：编译阶段由编译程序实现的对存储空间的管理和为源程序中的变量分配存储的方法。要求编译时能确定空间，且运行时不变。

动态存储分配：运行阶段由目标程序实现对存储空间的组织与管理和……。编译时要生成进行动态分配的目标指令

活动记录

display区+参数区+局部数据区

局部数据区：局部变量（数组还要存模板）
参数区：（自下而上）ret value、ret addr、prev abp、形参，没有的部分可不填
display区：（自下而上）abp(i)，即自外而内的交叉的各个块

源程序的中间形式

波兰表示

后缀表达式

算数指令心算

抽象机代码P-code

仅能在栈顶进行计算

d=(a+b)*c：lod a,lod b,add,lod c,mul,sto d

N元表示

三元式

间接三元式：

四元式：LLVM IR、MIPS汇编……

+，A，B，T1

错误处理

错误处理能力：

诊察错误
报错及时准确
一次编译找出错误的多少
错误的改正能力
遏制重复的错误信息的能力

错误分类

编译角度：语法错误、语义错误

语法错误：源程序在语法上不符合文法
语义错误：程序不符合语义规则或超越具体计算机系统的限制
- 标识符定义相关（未定义、重复定义）
- 调用时形参和实参类型不匹配
- 运算的操作数类型不一致
- 下标变量不能越界
- 数据溢出
- 符号表、静态存储分配数据区溢出
- 动态存储分配数据区溢出

错误的诊察和报告

诊察：

对一般的语法、语义规则，在语法和语义分析时发现
下标越界、计算结果溢出、动态存储数据区溢出，在目标程序运行时发现

错误报告：

出错位置：源程序中出现错误的位置，可用行号计数器或单词序号计数器实现
出错性质：可直接显示文字信息或给出错误编码
报告错误：分析完后报告/边分析边报告

错误处理

错误改正
错误局部化处理
- 跳过所在语法成分继续向下分析
目标程序运行时，调用写好的异常处理程序，打印错误信息、运行现场，然后停止程序运行

语法制导翻译

用于语义分析和中间代码生成

代码生成

寄存器分类

通用寄存器
- 保留寄存器
- 临时寄存器（生存范围不超过基本块，不跨越函数调用）
- 全局寄存器（跨越基本快、跨越函数调用）
专用寄存器

$gp：全局指针寄存器、$sp：栈指针寄存器、$fp：Frame指针寄存器（活动记录基地址）

全局/静态量不参与全局寄存器分配，局部变量才参与

引用计数

一个局部变量被访问次数越多，获得全局寄存器的机会也较大

图着色

当两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们之间便有一条边连接。所谓变量i在代码n处活跃，是指程序运行时变量i在n处拥有的值，在从n出发的某条路径上会被使用。

数据流分析得到冲突图
找到第一个连接边数目小于k（全局寄存器数目）的节点，将它从图G中移走。重复此过程
找不到小于k的了，就选取适当节点，标记为不分配全局寄存器，移除，然后重复步骤2
按移除顺序的倒序加入图中，着色

寄存器池

——对临时寄存器的管理

进入基本块时，清空临时寄存器池
为当前中间代码生成目标代码时，无论临时变量还是局部变量（亦或全局变量和静态变量），如需使用临时寄存器，都可以向临时寄存器池申请
临时寄存器池接到申请后，如寄存器池中有空闲寄存器，则可将该寄存器标识为被该申请变量占用，并返回该空闲寄存器。如寄存器池中没有空闲寄存器，则选取一个在即将生成代码中不会被使用的寄存器写回相应的内存空间，标识该寄存器被新的变量占用，返回该寄存器
在基本块结尾，或者函数调用发生前，将寄存器池中所有被占用的临时寄存器写回相应的内存空间，
清空临时寄存器池

代码优化

划分基本块

基本块中的代码连续执行，仅能从第一句进入、最后一句离开

整个序列的第一条语句属于入口语句
能由跳转语句转移到的第一条语句属于入口语句
跳转语句之后的语句属于入口语句

流图：节点是基本块的有向图。B2可能紧跟B1执行，则从B1到B2有一条有向边。B1为B2的前驱，B2为B1的后继

消除局部公共子表达式

建立DAG图，右侧画节点表
从DGA图导出中间代码

可能考的大题

正则文法转状态图

正则文法要么是左线性，要么是右线性。左线性（非终结符在左边）则逆向推导的方向画箭头

正则表达式转NFA、DFA、最小化

转NFA：记得几个基础的怎么转，可以带epsilon

转DFA：先确定初始状态的epsilon-集合，作为新的初始状态。之后确定输入a能转移到哪些状态以及他们的epsilon-集合，作为新的状态集合。直到所有输入画完、没有新状态为止

最小化：

等价类法：枚举所有两两状态的组合，要求同时处于非终态或终态，而且转移到的状态集合必须等价
分割法：列表，先划分非终态和终态。遍历每个输入下的每个状态转移，如果前后转移到的状态被划分开，则这两个状态也要被划分

消除左递归

LL分析

建表

求FIRST集和FOLLOW集

求FIRST（S）：只看左侧有S的规则，将规则右侧的第一个符号（终结符或非终结符的first+。。。）加入FIRST

求FOLLOW（S）：从开始符号向后求，开始符号有#。只看右侧有S的规则，加终结符或左侧的FOLLOW

建表：横行为所有终结符和#，竖列为所有非终结符。遍历每条规则a，坐标（a的左侧，a的FIRST集）填a；a能推出空，则（a的左侧，a的FOLLOW集）填a

分析

步骤	符号栈	读入符号	剩余符号串	使用规则
1	#E	i	+i*i#
2	#E'T	i	+i*i#	E::=TE'
3
4

根据栈顶符号和读入符号查表
当符号栈栈顶符号和读入符号相等时，pop，读入下一个（相当于顶掉了）
否则查表后将栈顶符号换为规则右部的倒序

易错点

建表时，忘记#号
分析时，压符号栈要倒序
符号栈最左侧和剩余符号串最右侧都有#

算符优先分析

构造优先关系矩阵

求FIRSTVT（U）：只看左部有U的规则，b，Vb，V都要加进去。可以用栈的形式找

LAST同理

建表：连续终结符xy，x=y；xY，x<FIRST(Y)；Xy，LASTVT(X)>y

分析

当栈顶终结符的优先级大于栈外终结符的优先级，规约，否则移进

步骤	符号栈	输入串	优先关系	动作
1	#	i+i*i#	#<i	移进
2	#i	+i*i#	i>+	规约

易错点

符号栈最左侧和输入串最右侧都有#
比较的是终结符的优先级，不是非终结符
算符优先的“动作”指的是下一行要干什么，其他的指的是本行要做什么
规约时要规约最左素短语

LR分析

构造分析表见CSDN

ACTION中的r：项目集I有规则A->a.，则I行FOLLOW(A)的所有列置该规则。但E'->E对于#置acc

易错点：

记得ACTION表有#号

栈式符号表

（从下往上画）

名字	种类	类型
arr	var	array
x	var	real
P	para	int
M1	proc

运行栈

局部变量

参数

prev abp

ret value

ret addr

display（前几层的abp）

易错点：

标出当前的abp（指向display最下面）
prev和其他abp指向对应位置
数组还有模板

DAG图

易错点：

常量也要标号、复用？
输出变量的时候，尽可能赋值给下文可能要用的变量？

到达定义分析

\[ in[B]=\cup_{B的前驱}out[P]\\ out[B]=gen[B]\cup(in[B]-kill[B]) \]

易错点：

注意是针对每一条指令，而非变量
从上到下，从前到后顺序分析

活跃变量分析

\[ out[B]=\cup_{B的后继基本块P}in[P]\\ in[B]=use[B]\cup(out[B]-def[B]) \]

易错点：

注意针对变量，而非定义点
从下到上，从后向前逆序分析

冲突图

冲突的条件：一个变量在另一个变量定义处是活跃的

形参之间相互冲突

定义-使用链

先进行到达分析，得到每个定义点可以到达那些地方，随后按{定义点，使用点，使用点，。。。}的形式为每一个定义点构造链

若两个链之间有相同的使用点，则合并成一个网

构建网后，冲突图按网和网之间的冲突（其中一个网所代表的变量在另一个网的定义处是否活跃）来写

FIRST：只看左侧有S的规则

LAST：只看右侧有S的规则

FIRSTVT：只看左侧有S的规则

LASTVT：只看左侧有S的规则

LL分析表：遍历每条规则，S和S的FIRST集构成的坐标填规则

算符优先分析表：遍历规则中的每个aAaA

LR分析表：呵呵

LL1、SLR1都是2型文法。算符优先是

问题：

地址计算怎么算？考不考
运行栈怎么标号？
正则表达式有空串吗？正则文法有二义性吗？
运行栈进入C语言的{、pascall的block、procedure的begin end要不要新建？
为当前函数申请活动记录空间的指针是哪一个？
运行栈要不要记录局部函数？beating返回值是啥？（例题：20-21外国人）参数信息是什么
DAG图数组/指针怎么处理？左右子树能否交换？
空串在语法树叶节点中吗？对应短语怎么写？
冲突图只画跨块活跃、不只看定义点-活跃冲突？

算符、LL1、SLR1无二义性

正则有二义性

属性翻译、算符、LL1、SLR1是2型文法

声明一般不直接出现在翻译后的语句中

专业课

编译原理理论笔记

https://solor-wind.github.io/2025/01/01/编译原理理论笔记/

作者

gpf

发布于

2025年1月1日

许可协议

编译原理实验设计文档上一篇

OS理论笔记下一篇

\(\Sigma\) 上的正则表达式	正则集合
\(\varepsilon\)	\(\{\varepsilon\}\)
\(\phi\) （空正则表达式集合）	\(\phi\)
a（ \(a\in\Sigma\) ）	\(\{a\}\)
\(U\|V\)	\(L(U)\cup L(V)\)
\(U\cdot V\)	\(L(U)\cdot L(V)\)
\(U^*\)	\(L(U)^*\)

编译原理理论笔记

概论

形式语言

语言

文法

句型与短语

二义性

文法分类

词法分析（正则、DFA）

正则文法与状态图

正则表达式与DFA

字母表上的正则表达式与正则集合：

确定的有穷自动机（DFA）

NFA的确定化

DFA的最小化

LEX

语法分析（LL,LR,SLR）

自顶向下

处理左递归

LL分析法

自底向上

算符优先分析

LR分析

符号表与运行栈

栈式符号表

运行栈

活动记录

源程序的中间形式

波兰表示

抽象机代码P-code

N元表示

错误处理

错误分类

错误的诊察和报告

错误处理

语法制导翻译

相关概念

代码生成

寄存器分类

引用计数

图着色

寄存器池

代码优化

划分基本块

消除局部公共子表达式

可能考的大题

正则文法转状态图

正则表达式转NFA、DFA、最小化

消除左递归

LL分析

建表

分析

易错点

算符优先分析

构造优先关系矩阵

分析

易错点

LR分析

栈式符号表

运行栈

DAG图

到达定义分析

活跃变量分析

冲突图

定义-使用链

问题：