编译原理总结

约 8591 字大约 29 分钟

DLUT 编译原理

2026-05-13

该文档根据老师的总复习提纲ppt总结，如有知识点漏缺、错误等概不负责多看ppt多看题，多问搜索引擎

编译原理课程知识点总结

主要内容

NFA转DFA、最简DFA First、follow、左因子、左递归 LL(1)、预测分析表 SLR、LR、LALR、移进归约分析表 S属性语法制导定义 L属性语法制导的翻译方案（难）过程的活动、活动记录、控制栈三地址代码、语法树

第二章词法分析

基本概念

文法

文法G定义为一个四元组G=(V_T, V_N, S, P)\\ V_N：非终结符（或语法实体、变量）集\\ V_T：终结符集\\ P：规则（α\rightarrowβ）的集合，α∈(V_N∪V_T)*且至少包含一个非终结符，β∈(V_N∪V_T)*\\ V_N, V_T和P是非空有穷集\\ S：识别符或开始符，是一个非终结符，至少要在一条规则中作为左部出现在给出规则集时，可约定第一条规则的左部符号是识别符号\\

语言、句型与句子

语言：从开始符号推导得到所有终结符号串的集合称为该文法定义的语言（language）

句型： $设有文法G=(V_T,V_N,S,P)，若𝑆⇒^∗ 𝑎,𝑎∈𝑉^∗，则称𝑎为G的一个句型$ 从文法的开始符推导出的任意符号串均是该文法的句型，开始符自身也是一个句型，它由0步推导出

句子：全部由终结符组成的句型就是句子把文法G的所有句子的集合称为G产生的语言，记为 L(G) 如果在一个文法中包含有递归定义的产生式，那么该文法定义的语言是无限集合

文法类别

0型文法（短语文法）： $设𝐺=(𝑉_𝑁,𝑉_𝑇,𝑃,𝑆)，如果它的每个产生式是这样一种结构：α\rightarrow β且至少含有一个非终结符，而𝛼∈(𝑉_𝑁∪𝑉_𝑇 )^∗，则G是一个0型文法$

1型文法（上下文相关文法）： $文法𝐺的任何产生式α\rightarrowβ均满足|𝛼|≤|𝛽|。仅仅S\rightarrowε例外，但𝑆不得出现在任何产生式的右部。其中|𝑎|表示符号串的符号个数，即𝑎的长度；ε表示没有任何符号的符号串，即空符号串|𝜀| = 0$ 1型文法也称为上下文相关文法或前后文有关文法，简记为CSG

2型文法（上下文无关语言，CFL）： $文法G的任何产生式均为A\rightarrowβ的形式，其中，𝐴∈𝑉_𝑁,𝛽∈𝑉^∗称G为2型文法。2型文法的产生式左边仅有一个非终结符，它不受上下文限制$

3型文法（正则文法、右线性文法）： $文法G的任何产生式均为A\rightarrow aB或A\rightarrow a的形式，其中，𝐴,𝐵∈𝑉_𝑁,𝑎∈𝑉_𝑇^∗，称𝐺为3型文法$

4种文法的关系为： $0\supseteq 1 \supseteq 2 \supseteq 3$

正规式

正规式的例子 \sum = {a, b}\\ a | b \qquad {a, b}\\ (a |b)(a |b ) \qquad {aa, ab, ba, bb}\\ aa |ab |ba |bb \qquad {aa, ab, ba, bb}\\ a^* \qquad \qquad由字母a构成的所有串集，包含空串\\ a^+ \qquad \qquad由字母a构成的所有串集，不包含空串\\ (a | b)^* \qquad 由a和b构成的所有串集，包含空串\\ 复杂的例子: (00|11 | ( (01|10) (00|11)^* (01| 10)))^*\\ 句子：01001101000010000010111001

DFA、NFA、状态转移表

DFA

NFA

状态转移表

优点：快速定位缺点：字母表过大或大部分转换状态为空集时浪费空间

NFA与DFA的区别

1.NFA中允许 $\varepsilon$ 转换边，而DFA中不允许 2.NFA中move(s,a)可能是一个多元集合，而DFA中move(s,a)最多有一个元素

正规式 $\rightarrow$ NFA

子集构造法(NFA与DFA转换)

DFA化简

状态的可区分性:存在串w，使得从状态s开始，对w进行状态转换，最终停在某个接受状态；而对于从t开始对w进行状态转换后，却停在某个非接受状态根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系

第三章语法分析

基本概念

最左推导与最右推导与分析树

二义性

文法的二义性，是指对于符合文法规则的同一个句子，存在两种可能的分析树

如何消除二义性：离根越近的运算符优先级越低

归约

归约，是自下而上分析中的重要动作归约，对应着最右推导的逆过程

句柄

句柄: 和某产生式右部匹配的子串句柄是最左侧的直接短语句柄是句型的一个子串把句柄归约成非终结符代表了某一步最右推导的逆过程

句型的句柄，是该句型中与一个产生式右部匹配的字符串所有能够在最右推导中出现的句型，称为右句型 $右句型的\gamma句柄是一个产生式A->\beta的右部\beta ，并且该句柄\beta在用A替换\gamma中的句柄\beta之后，得到的是最右推导中的前一个句型$ $令 \gamma=\alpha\betaω，则\gamma可以通过产生式A->\beta归约为句型\alpha Aω$

自上而下分析

对应着使用最左推导构建语法树的过程

消除左递归

提取左公因子

First

$FIRST(\alpha)是从\alpha推导出的串的起始终结符的集合。$

$FIRST(\alpha) = \{ a | \alpha \Rightarrow^* a…, a \in V_T\}$ $特别是，\alpha \Rightarrow^* \varepsilon时，规定\varepsilon \in FIRST(\alpha)$

Follow

FOLLOW(A)是在所有句型中紧跟在A后面的终结符集合

$FOLLOW(A) = \{a | S \Rightarrow^* …Aa…，a\in V_T\}$ $如果A是某个句型的最右符号（S\Rightarrow^*aA），那么\$属于FOLLOW(A)$

LL(1)文法

基本思想：寻找输入符号串的最左推导，试图根据当前输入单词确定使用哪个产生式

基本过程：从S出发，构造输入符号串的最左推导。从根开始，按与最左推导相对应的顺序，构造输入符号串的语法分析树

如何判断是不是LL（1）文法：任何两个产生式$A \rightarrow^* \alpha | \beta $都满足下列条件：$ FIRST(\alpha) \cap FIRST(\beta) = \emptyset若\beta \Rightarrow^* \varepsilon ，那么FIRST(\alpha) \cap FOLLOW(A) = \emptyset$

没有公共左因子不是二义的不含左递归

非递归的预测分析

基于栈实现的非递归的预测分析

构造预测分析表

（1）对文法的每个产生式A \rightarrow a ，执行(2)和(3)。\\ （2）对FIRST(\alpha)的每个终结符a，把A \rightarrow \alpha加入 M[A, a]（即加入表中A行a列）。\\ （3）如果\varepsilon在FIRST(\alpha)中，对FOLLOW(A)的每个终结符b（包括\$）, 把A \rightarrow \alpha 加入M[A, b]。\\ （4）M的其它没有定义的条目都是error。\\

同步符号（用于解决预测错误）

自下而上分析

自下而上分析，对应最右推导的逆过程

LR分析法

在分析栈中增加了状态在移进-归约分析中，句柄总是出现在栈顶自下而上分析基于识别句柄分析器如何使用详见第11讲ppt的10-17页

活前缀

一个符号串的前缀是指从第一个符号开始的连续的若干个符号构成的子串。活前缀：右句型的前缀，该前缀不超过最右句柄的右端 $S\Rightarrow^*_{rm}\gamma Aw\Rightarrow_{rm}\gamma \beta w$ $\gamma\beta的任何前缀（包括\varepsilon和\gamma\beta本身）都是一个活前缀。$

活前缀已含有句柄的全部符号，表明产生式A→β的右部β已出现在栈顶。活前缀只含句柄的一部分符号如 $β_1表明A→β_1β_2的右部子串β_1$ 已出现在栈顶，当前期待从输入串中看到 $β_2$ 推出的符号。活前缀不含有句柄的任何符号，此时期望产生式A→β的右部所推出的符号串。

LR(0)项目集

点的左边代表历史信息，右边代表展望信息。直观地讲，项目表示在分析过程的某一阶段，已经看到了产生式的多大部分，以及希望看到的部分。

从文法构造识别活前缀的DFA

第一步：拓广文法当且仅当分析器使用 $E'\rightarrow E$ 归约时，宣告分析成功

第二步：构造LR(0)项目集规范族闭包函数closure(I) 1、I的每个项目均加入closure(I) 2、如果 $A\rightarrow α·Bβ$ 在 closure(I)中，且 $B\rightarrow γ$ 是产生式，那么如果项目 $B\rightarrow \cdot γ$ 还不在closure(I)中的话，那么把它加入。

核心项目：所有的点不在产生式右部的左端的项目非核心项目：通过对核心项目求闭包而获得

第三步：构造DFA

SLR(1)

一般性构造过程：首先对文法进行拓广，添加产生式S’->S 构建识别活前缀的DFA 基于DFA构建分析表

前两步同上（与LR（0）一模一样）

基于DFA构建分析表：如果出现动作冲突，那么该文法就不是SLR(1)的。（会出现移进归约冲突（也可能是归约归约冲突

LR(1)

与SLR(1)文法的区别:项目集的定义发生了改变,添加了前向搜索符项目集改变的目的是增强描述能力

前向搜索符: $一个项目A\rightarrow \alpha·\beta，如果最终用这个产生式进行归约之后，期望看见的符号是a，则这个加点项的前向搜索符是a$ $上述项目可以写成：A\rightarrow \alpha·\beta，a $

LR(1)项目：重新定义项目，让它带上搜索符，如 $[A\rightarrow \alpha·\beta，a]$

对于项目 $[A\rightarrow \alpha·\beta，a]$ : 当 $\beta$ 不为空时，采取移进操作（同LR(0)项目）；当 $\beta$ 为空时，是根据搜索符a来决定归约，而不是根据A的后继符FOLLOW(A)来规约（不同于LR(0)项目）,通常搜索符a的集合是 FOLLOW(A) 的子集。

计算前向搜索符

构造规范的LR分析表

如果用上面规则构造出现了冲突，那么文法就不是LR(1)的。

LALR

LALR是在SLR(1)和LR(1)之间进行了文法描述能力与分析表紧凑程度之间做的折衷 SLR(1)文法描述能力稍弱，而由于状态数目较小能够得到高效实现（不必消耗太多内存） LR(1)文法描述能力较强，但是由于状态数目多，分析表较大 LALR的描述能力与分析表大小介乎SLR(1)与LR(1)之间

三者的表达能力为：LR(1)>LALR>SLR(1) 包含关系为：LR(1)包含LALR包含SLR(1)

LALR的做法：合并识别 LR(1)文法的活前缀的DFA中的同心项目集

同心的LR(1)项目集：略去搜索符后它们是相同的集合例： $B \rightarrow·bB, $ 与 B \rightarrow·bB, b/a $合为$ B \rightarrow ·bB,b/a/$$

合并同心项目集可能会引起冲突不会引起新的移进归约冲突(本来就有的话会遗传过来) 同心集的合并有可能产生新的归约归约冲突

构造LALR(1)分析表

构造LR(1)项目集规范族C = $\{I_0, I_1, …, I_n\}。$ 寻找LR(1)项目集规范族中同心的项目集，用它们的并集代替它们。按构造规范的LR(1)分析表的方式进行构造

LR分析法与LL分析法的区别

LL(1)的分析表

需要求解First集和Follow集

LR的分析表

需要求解First集和Follow集、对应的项目集和DFA

第四章语法制导定义（多看ppt多看题，笔者自己可能都没学明白，此部分仅供参考）

语法制导与语法制导的翻译方案

语法制导：对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。带属性和规则的上下文无关文法在语法制导定义中的文法被称为基础文法

语法制导的翻译方案：在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。

综合属性：由分析树中它的子结点的属性值来计算继承属性：由结点的兄弟结点及父结点的属性值来计算。终结符只有综合属性，并且这些综合属性通常由词法分析器提供非终结符号既有综合属性也可有继承属性，文法的开始符号没有继承属性，除非另外加以说明。文法符号的综合属性集和继承属性集的交集应为空。

对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。

属性文法

属性文法是指语义规则函数无副作用的语法制导定义

注释分析树

注释分析树：每个结点的属性值都标注出来的分析树，称为注释分析树。分析树各结点属性的计算可以自下而上地完成

属性依赖图

在一棵分析树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。依赖图的任一拓扑排序都是一个合理的属性计算顺序

如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。

属性计算顺序

属性计算次序: 1、构造输入的分析树 2、构造属性依赖图 3、对结点进行拓扑排序 4、按拓扑排序的次序计算属性

语义规则的计算方法: 分析树方法：前面介绍的方法 (有环则失败) 基于规则的方法：静态确定语义规则的计算次序。忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制。

基于(语义)规则的方法：语法分析和属性计算分开，先构造分析树，然后按预先定义的策略遍历分析树来计算属性。语义规则的定义和计算顺序(翻译模式)在编译器构造之前确定。分析树遍历策略的确定（构造编译器时）要考虑语义规则的定义及计算顺序，因此是基于规则的方法。

忽略(语义)规则的方法：在进行语法分析的同时进行翻译，即边分析边计算属性，计算次序由分析方法确定而与语义规则无关。缺点：这样确定计算次序将限制能实现的语法制导定义的种类。优点：不构造依赖图，不对依赖图进行拓扑排序，提高了时空效率。

语法结构树

同样是产生式附带语义规则，不同的语义规则产生不同的作用。对算符结点，一个域存放算符并作为该结点的标记，其余两个域存放指向运算对象的指针。基本运算对象结点，一个域存放运算对象类别，另一个域存放其值。（也可用其他域保存其他属性或者指向该属性值的指针）

S属性文法

S属性定义：仅仅使用综合属性的语法制导定义综合属性可以在分析输入符号串的同时由自下而上的分析器来计算

栈代码

分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算

L属性文法

L属性定义：如果每个产生式 $A\rightarrow X_1 X_2 … X_n$ 的每条语义规则计算的属性是A的综合属性；或者是 $X_j$ 的继承属性， $1 \le j \le n$ , 但它仅依赖：该产生式中 $X_j$ 左边符号 $X_1, X_2, …, X_{j-1}$ 的属性；或 A的继承属性。

S属性属于L属性

S属性定义中，只要将产生式作为一个整体看待即可，语义规则可以视为是附着在整个产生式上 L属性定义则不一样，它跟属性所属的符号在产生式中的位置有关系

翻译方案

翻译方案：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来。在翻译方案中，和文法符号相关语义动作，用花括号{ }括起来，插入到产生式右部的合适位置上。这是一种动作和分析交错的方法，以表示动作的执行时机。语义动作（语义规则）插入到产生式右部的任何地方，以表达动作的执行时刻。如 $A\rightarrow B\{..\}C$

当只需要综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。

如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：

产生式右边的符号的继承属性必须在先于这个符号的动作中计算出来。
一个动作不能引用这个动作右边的符号的综合属性。
产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。

L属性自上而下

L属性自下而上

L属性的自上而下计算与自上而下的语法分析的过程是一致的但是，自上而下分析能够处理的文法局限于LL(1) 为了为更为一般的文法计算L属性，需要研究自下而上的L属性计算方法通过改写文法，使得所有嵌入在产生式中间的动作变换成只在产生式的最右端出现

第六章运行时存储空间的组织和管理

基本概念

过程的活动：过程的一次执行被称为过程的一次活动活动记录：过程活动时用于存放所需信息的存储空间

过程P一次活动的生存期：从执行该过程体第一步操作到最后一步操作之间的操作时间，包括执行P时调用其它过程花费的时间过程可以是递归的一个过程可对应多个活动

活动记录

被编译程序每次运行时，编译器从操作系统获得一块存储区（内存）活动记录：过程的活动中用于存放所需信息的存储空间, 称为活动记录

衬垫空白区

字节是可编址内存的最小单位。局部数据的地址可以用相对于某个位置（本过程对应的活动记录的起始位置）的偏移来表示。数据对象的存储安排深受目标机器寻址方式的影响，存在对齐问题。例如，要求整数（int，long）的相对地址可以被4整除。由于对齐而引起的无用空间称为衬垫空白区

程序块

语法如{声明语句} 本身含有局部变量声明的语句，可以嵌套

最接近的嵌套作用域规则: 程序块 B中声明的作用域包括B 如果名字x没有在B中声明，那么B中x的出现是在外围程序块B’的x声明的作用域中，且满足

  B’有x的声明
  B’比其他任何包含x声明的程序块更接近被嵌套的B

并列程序块不会同时活跃并列程序块的变量可以重叠分配

全局栈式存储分配

静态分配

名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。绑定的生存期是程序的整个运行时间。控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。每个活动记录的大小是固定的。过程调用时保存信息的地址在编译时也是已知的。

C语言中，如：声明在函数外面：

  外部变量

声明在函数里面：

  静态局部变量
  常量

静态分配的限制：

  递归过程不被允许
  数据对象的长度和它在内存中位置，必须是在编译时可以知道的
  数据结构不能动态建立

栈式分配（活动树和运行栈）

栈式分配主要用于管理过程的活动记录。局部变量的生存期是过程活动的时间。控制进入该过程时，局部变量绑定到存储单元，过程活动结束后，局部变量的空间释放。

栈式分配的限制：

  过程活动停止后，局部名字的值还必须维持
  被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流
  不遵守栈式规则的有Pascal语言和C语言的动态变量
  Java禁止程序员自己释放空间

活动树

用树来描绘控制进入和离开活动的方式活动树的特点：

  每个结点代表某过程的一个活动
  根结点代表主程序的活动
  结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动
  结点a 处于结点b 的左边，当且仅当a的生存期先于b的生存期
  活动执行的顺序等同于深度优先搜索

运行栈

运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）

过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等具体实例查看第19讲ppt的37-50页

过程调用序列:

  过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码

过程返回序列:

  被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码

设计这些序列和活动记录的一些原则:

  以活动记录中间的某个位置作为基地址
  长度能较早确定的域放在活动记录的中间
  一般把临时数据域放在局部数据域的后面
  把参数域和可能有的返回值域放在紧靠调用者活动记录的地方
  用同样的代码来执行各个活动的保存和恢复

栈式分配的动态释放空间引起悬空引用：引用某个已被释放的存储单元

堆式分配

内存分配与释放按照任意次序进行堆中可能包含交错的正在使用的和已经释放的区域

非局部名字的访问

无过程嵌套的静态作用域

有过程嵌套的静态作用域

访问链（静态）

基本概念

访问链：用来寻找非局部名字的存储单元访问链总是指向本活动的最近的外围过程的活动记录

建立访问链

假定嵌套深度为 $n_p$ 的过程p调用嵌套深度为 $n_x$ 的过程x:

$n_p < n_x$ 的情况: x肯定就声明在p中被调用过程的访问链必须指向调用过程的活动记录的访问链 S中有P的变量

$n_p > n_x$ 的情况: p和x的嵌套深度分别为 $1，2，…，n_x-1$ 的外围过程肯定相同追踪访问链 $n_p - n_x$ 次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链 P访问S需要按访问链跳2次

动态作用域

被调用过程的非局部名字a和它在调用过程中引用的是同样的存储单元基于运行时的调用关系而不是基于静态作用域来确定

实现方法分为深访问和浅访问：深访问：用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录

浅访问：为每个名字在静态分配的存储空间中保存它的当前值当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复

参数传递

值调用

实参的右值传给被调用过程值调用可以如下实现：

  把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。
  调用过程计算实参，并把右值放入形参的存储单元中。

引用调用

实参的左值传给被调用过程引用调用可以如下实现：

  把实参的左值放入形参的存储单元。
  在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。

  介乎源语言与目标代码之间，比源语言简单，比目标代码复杂。
  区分编译器的前端与后端，方便提出针对新机器的编译器。
  可以设计针对中间代码的优化器。

使用中间代码的优点：

  与机器无关，便于移植。
  便于进行独立于机器的代码优化

用语法制导定义和翻译方案的方法将源程序翻译成中间形式

中间代码的表示方法

后缀表示

表达式E的后缀表示可以如下递归定义：

如果E是变量或常数，那么E的后缀表示就是E本身。\\ 如果E是形式为E_1 op E_2的表达式，那么E的后缀表示是E_1' E_2' op，其中E_1'和E_2'分别是E_1和E_2的后缀表示。\\ 如果E是形式为(E_1)的表达式，那么E_1的后缀表示也是E的后缀表示。\\ 后缀表示不需要括号

(8 - 4) + 2 的后缀表示是8 4 - 2 +

最大优点：便于计算机处理表达式

图形表示

语法树是一种图形化的中间表示有向无环图(dag)也是一种中间表示

三地址代码

一般形式：x := y op z

表达式x + y * z翻译成的三地址语句序列是

t_1 := y * z \\ t_2 := x + t_1

常用的三地址语句:

赋值语句x := y op z， x := op y， x := y\\ 无条件转移goto\quad L\\ 条件转移if\quad x\quad relop\quad y\quad goto\quad L\\ 过程调用param\quad x 和call\quad p , n\\ 过程返回 return\quad y\\ 索引赋值x := y[i]和 x[i] := y\\ 地址和指针赋值x := \&y，x := *y和*x := y

  序列的第一个语句是入口语句
  能由条件转移语句或无条件转移语句转到的语句是入口语句　
  紧跟在条件转移语句或无条件转移语句后面的语句是入口语句

每个入口语句到下一个入口语句之前的语句序列构成一个基本块

基本块优化

三地址语句x = y + z引用y和z并对x定值一个名字的值在基本块的某一点以后还要引用的话，则说这个名字在该点是活跃的

基本块的等价

  两个基本块计算一组同样的表达式
  这些表达式的值分别代表同样的活跃名字的值

有很多等价变换可用于基本块

  局部变换
  全局变化