编译原理笔记

第一章 引论

重点:

翻译程序，编译，解释，源程序，中间代码，目标代码

了解编译的过程，编译程序的构架图（图1.1）

表格管理，遍

编译与翻译

• 翻译：是指能把某种语言的源程序，在不改变语义的条件下，转换成另一种程序语言->目标语言程序。

• 解释：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的解释结果，然后再接受下一句，关键：不产生目标程序，边解释边运行。

• 编译：将高级语言转为低级语言，产生目标程序。

编译程序的流程：

1. 词法分析
2. 语法分析
3. 语义分析
4. 中间代码生成
5. 优化
6. 目标代码生成

语法分析与语义分析的差别：语法分析主要检查编写代码时有无报错，即编译时错误；语义分析则是检查代码运行时是否符合规范，即运行时错误。

例如：

• else没有匹配的if => 语法分析错误
• 数组下标越界 => 语义分析错误

语法分析

主要有两种：推导和规约

最左推导 => 最右规约

最右推导 => 最左规约

中间代码生成

对语法分析识别出的各类语法范畴，分析其含义，进行初步翻译，产生介于源代码和目标代码之间的一种代码。

分为两阶段工作

• 对对每种语法范畴进行静态语义检查
• 若语义正确，就进行中间代码的翻译

中间代码的形式：

主要有：四元式，三元式和逆波兰式。

表格管理

• 用来记录源程序的各种信息以及编译过程中的各种状况。

与编译的前三个阶段有关的表格有：

• 符号表，常数表，标号表，分程序入口表，中间代码表等

遍

定义：是对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果和目标代码。

注意：遍与阶段毫无关系

单遍扫描与多遍扫描比较：

• 多遍扫描的优缺点：
• 优点：节省内存空间，提高目标代码质量，使编译的逻辑结构清晰。
• 缺点：编译时间较长。

注：在内存许可的情况下，还是遍数尽可能少些为好。

基本概念

• 高级语言编写的源程序都必须通过编译，产生目标代码后才能执行。（X）
• 多遍扫描的编译程序的多遍是指多次重复读源程序。（X）
• 目标程序一定是机器语言程序。 （X）
• 无论一遍扫描还是多遍扫描，编译器都要对源程序扫描一遍。（O）

第二章 高级语言及其语法描述

重点：

CHOMSKY形式语言描述0,1,2,3型文法，重点掌握2型上下文无关文法和正规文法

程序语言的语法描述：符号表示

上下文无关文法

重点：文法识别语言，或者给出语言写出相应文法，最左推导，最右推导

语法描述

主要有以下三种结构组成：

1. 字母表（alphabet）
2. 符号（字符）（symbol）
3. 符号串（string）

符号串运算：

1. 符号串的连结
2. 集合的乘积
3. 符号串的幂运算
4. 集合的幂运算
5. 集合的正闭包与星闭包(重要)

A+与A*的区别

A*不包括空串，A+包括。

上下文无关文法

文法

文法是规则的非空集合，即一个四元组：
$$
G=(V_N,V_T,P,S)
$$

1. V_n是非终结符的非空有限集
2. V_t是终结符的非空有限集
3. S是开始符号的非终结符
4. P是产生式的集合，且每个产生式形式为 p->α 。

描述语言的文法不是唯一的。

句型和句子

根据文法推导出来的符号串称为该文法的句型，仅含有终结符的句型称为句子。

规范推导与规范规约

每次推导时，都对字符串最右边的非终结符做替换，称为最右推导，也叫规范推导。

此时推出的句型称为规范句型。

反过来，规范推导的逆过程称为规范规约，即最左规约。

语言

根据文法产生的所有句子的集合，称为语言。

Chomsky四类文法

1. 0型文法：没有任何限制的文法(可能出现非终结符永远消除不了，无法终结)
2. 1型文法：上下文有关文法
3. 2型文法：上下文无关文法，推导与上下文无关
4. 3型文法：即正规文法，有左线性文法与右线性文法两种。

右线性：A->aB 或 A->a

左线性：A->Ba 或 A->a

语法树与文法二义性

如果某个文法存在句子对应两棵不同的语法树(最左或最右推导)，则称文法是二义性的。

第三章 词法分析

重点：

词法分析的任务，输出形式

状态转换图，正规式，正规集，正规文法，三者之间的关系

DFA,NFA

给出语言写出正规式

重点3.3节：正规式绘制出NFA,NFA的确定化以及最小化问题

正规文法与DFA之间的转换（P52）

词法分析是编译的第一阶段，在单词的级别上分析和翻译源程序。

理论基础:

• 有限自动机理论
• 有限自动机理论与正规文法、正规式之间在描述语言方面有一一对应的关系。

正规文法与有限自动机

正规文法、正规集与正规式：

一个正规语言可以用正规文法定义，也可以用正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；同样，对每个正规式，存在一个生成同一语言的正规文法；有些正规语言很容易用文法定义，有些则用正规式定义更容易；两者之间可以转换，结构上具有等价性。

由正规文法或正规式定义的正规语言的集合构成正规集

正规文法转为正规式：

1. 联立导出式
2. 把方程组中的非终结符当作自变量
3. 求出方程组的解，再得到开始符号非终结符S的解即为正规式

有限自动机(FA)

有限自动机是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具。

有限自动机是具有离散输入输出系统的数学模型，它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。

其当前状态概括了过去输入处理的信息。

确定有限自动机(NFA)与非确定有限自动机(DFA)：

NFA：状态 + 输入得到一个确定的状态

DFA：状态 + 输入得到多个状态

DFA由一个五元组描述：
$$
M = (S,\sigma,f,s_0,Z)
$$

• S为有限状态集合
• Σ为有限字母表
• f为单值映射
• s0为唯一的初态
• Z是终止状态集合

NFA与DFA类似，唯一的区别是：NFA的S是一个非空初态集，而不是确定的初态。

NFA的确定化

将NFA转为未化简的DFA，一般用子集法：

1. 例如有NFA的状态q0,q1，分别为初态和末态。

2. 设一个新状态集合I，则有初态I0={q0}，再代入NFA中，看I0接受字符之后转为的状态是否是I中没有的：

3. 例如有{q0,1}={q1}，此时将该状态加入I，即I1={q1}。继续考察I1接收字符后转成的状态是否是新状态，重复这个过程即可得到未化简的DFA。

DFA的最小化

1. 将DFA的状态集合分为终态集和非终态集：因为终态可以识别空串，但非终态不行，因此可以区分
2. 对划分后的集合分别读取各个终结符，判断产生的状态是否包含在已经划分的几个集合中。
3. 如果均包含，则该集合已经不需要划分；如果出现新集合，则需要继续划分。重复直到子集合数不再增加。

DFA与正规式转换

反过来由DFA写正规文法时，比较容易，需要根据下面两条规则：

1. 当产生的状态B不属于终态集时：A -> aB（右线性文法时）
2. B属于终态集时：A -> a | aB

第四章 自上而下的语法分析

重点：

语法分析器的功能，语法分析的方法

自上而下分析的问题：左递归和回溯，如何消除

LL（1）文法

首符集FIRST()，随符集FOLLOW（）

预测分析表的构造

利用分析表进行预测分析的步骤

1、语法分析的地位

• 是编译程序的核心部分。

2、语法分析的任务

• 识别由词法分析得出的单词序列是否是给定文法的句子。

3、语法分析的理论基础

• 上下文无关文法和下推自动机（PDA）

4、语法分析的两种思路和方式：

1. 自上而下分析：反复使用不同产生式做推导以匹配完整输入串；
2. 自下而上分析：对输入串寻找不同的产生式做规约，直到规约到文法开始符号的非终结符S。

下推自动机(PDA)

与FA相比，增加了一个下推栈。

PDA执行的动作由三个因素决定：

1. 当前状态
2. 读头所指向的符号
3. 下推栈的栈顶符号

当下推栈与输入带均为空串时，说明此时语法分析完成，且成功匹配输入串。

PDA是一个七元组，除了FA的四元组以外，还包括：

• 下推栈字母表
• 下推栈的栈初始符号(一般是#)
• 各种字母表间的有限子集映射

PDA的三种状态

1. 推导：栈顶为非终结符，将其出栈，并将其产生式入栈
2. 匹配：栈顶与读头均为终结符，则可以匹配成功，一起出栈
3. 回溯：若栈顶与读头均为终结符，但不匹配，则说明推导出错，需要返回上次推导现场。

若回溯到开始符号S，则此时PDA识别失败。

不带回溯的自上而下语法分析

消除左递归

例如有文法：P -> Pa | b

消除直接左递归后转为等价式：

1. P -> bP’
2. P’ -> aP’ | 空串

消除回溯

基本方法：预测和提取左因子

预测：根据读头下的字符对应的预测分析表，选择候选式，使其第一个字符与读头下相同，即相对于向前看了一个字符。此时消除回溯（即保证候选式的唯一性）。

因此需要求非终结符的首符号集First(A)。

但是会出现非终结符的候选式首符集相交(例如A->B|C，B和C的首符集可能都含有a)的情况，此时仍然需要回溯，因此需要提取公共左因子。

提取公共左因子：

预测分析程序与LL(1)文法

预测分析表：指示非终极符和终结符对应时，需要做哪种推导。

构造预测分析表需要先构造字母表的首符集和随符集。

First(α)集

• 对非终极符：

所有α可能推导出的第一个终结符或空串组成的集合。

如果α经过有限次推导可以得到空串，则将空串加入首符集。

• 对终结符：

终结符的首符集就是本身。

Follow(α)集

在产生式右端找的α后面的第一个终结符，加入α的随符集。

如果A可以推导出B，且B后无其他字符(如A->aB)，则将Follow(A)加入到Follow(B)；

最后将终止符#加入Follow集。

LL(1)文法

若文法G的预测分析表M中不含有多重定义项，则称G为LL(1)文法。

注意：

1. LL(1)文法是无二义的，二义文法一定不是LL(1)文法。

2. LL的含义是从左到右扫描输入串，采用最左推导分析句子。

3. 数字1表示分析句子时需向前看一个输入符号。

判断是否是LL(1)文法

1. 文法中不含有左递归和公共左因子
2. 对每一个非终极符A，A的各个产生式的候选首符集两两不相交。
3. 对于产生式中存在空串的非终极符B，First(B)与Follow(B)不相交。

预测分析表构造

构造是根据文法的每个产生式：

1. 如果有A->α(终结符或非终极符)，则对α的首符集里的每个终结符a..，都把A->α加入到M[A,a]中；
2. 如果右端产生式的首符集中有空串，则对左端A的Follow集中所有终结符b..，将产生式加入到M[A,b]中。

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

重点：

归约，句柄，规范归约（最左归约），最左素短语，算符优先，LR

注意：LR(0)，算符优先（FIRSTVT LASTVT）,分析表，给句子出来要会做相应分析

列出给定文法的LR(0)项目，构造识别活前缀的DFA，根据DFA判断文法是否是LR（0）（关键在项目族内是否是移近-归约冲突，或规约规约冲突），如果没有冲突项，就继续构造它的LR(0)分析表。根据分析表分析某个给定的句子，写出分析过程（符号栈，状态栈，输入串的变化）。

规范规约的相关概念

• 直接短语：构成一个更大非终极符的子树，且只有一次推导
• 素短语：至少包含一个终结符，且不包含其他更小素短语的直接短语。
• 句柄：最左直接短语(注意：不要求是素短语，因此可以不包含终结符)
• 最左素短语：语法分析树最左边的素短语，不要求是直接短语，可以跨代但必须含有终结符。

!!要注意直接短语与素短语的区别，句柄是直接短语，但可以不是素短语。!!

1. 自下而上的语法分析思想：

自下而上的语法分析是一个最左归约的过程：从输入串开始，朝文法的开始符号进行归约，直到到达文法的开始符号为止的过程。最左规约即最右推导的逆过程，也叫规范规约。

2. 自下而上的PDA工作流程：

主要是两种操作：移进和规约

自左至右把输入串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约)，若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。

3. 具体分析句子时，一般是先写出推导过程，再画出对应的语法树，找出其中的最左直接短语(即句柄)，再用PDA分析句子规约-移入。

此时就产生一个问题：当可以规约时，该如何规约？即如何刻画“可规约串”这个概念？

最直接的思路是：简单优先分析

简单优先文法

定义：一个文法G，如果它不含空串产生式，也不含任何右部相同的不同产生式。并且它的任何符号对(X,Y)（注：X、Y是非终结符或终结符），要么没有关系，要么存在优先级相同或低于、高于等关系之一，则这是一个简单优先文法。

PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。直到最后栈内只剩下开始符号，输入串读到#”为止。此时识别正确。

优先级的定义：

1. X = Y：当且仅当G中含有形如P -> …XY….
2. X < Y：当且伩当G中含有形如P -> …XQ….的产生式，其中Q -> Y….
3. X > Y：当且仅当Y为文法G的终结符，G中有形如P -> …QR..，且Q -> ..X，Y ∈ first(R)

算符优先文法

算符文法的定义：给定上下文无关文法G，若G中所有产生式右部都不包含两个相继的非终结符（即例如…AB…），则G为算符文法。

算符优先文法的优先级定义：

1. a = b：当且仅当G中含有形如P → ..ab..产生式，或者P->..aQb..产生式；
2. a < b：当且仅当G中含有形如P → ..aR..的产生式，其中R可以广义推导为b…或Qb…..(即a之后有可以推导出b的非终极符时，优先级别低于b)；
3. a > b：当且仅当G中有形如P → ..Rb..产生式，其中R广义推导为….a或….aQ。

(注：即能进一步推导时，优先级更高)

若G中任何终结符序偶(a,b)至多满足上述关系之一(即不能同时满足几个关系)，则称G为算符优先文法(OPG).

构造优先级表

FirstVT集和LastVT集

先求各个非终结符的FirstVT集和LastVT集:

这两个集合都很容易求，FirstVT即非终结符推导出的第一个终结符，或者经过多次推导得到的首个终结符；LastVT集即经过一步或多步推导得到的最后一个终结符。

构造完FirstVT集和LastVT集之后，就可以确定优先级关系：

通过优先级表判断规约优先级

1. 当栈顶字符的优先级大于读头时，即形成可规约串，对栈顶做规约。
2. 当读头优先级更高或者优先级相等时，做进栈操作。

LR分析法

基本思想：在规范归约过程中，一方面记住已移进和归约出的整个符号串，另一方面根据所用的产生式推测未来可能碰到的输入符号。

LR分析器分析三个方面的信息：

• 历史：记录在栈内的符号串移进、归约的历史情况；
• 展望：预测句柄之后可能出现的信息；
• 现实：读头下的符号。

L：从左向右扫描

R：构造最右推导的逆过程(即最左规约)

LR分析器的构成：语法分析程序(查分析表，做入栈出栈等操作) + 分析表。

因此关键就在如何构造和使用LR分析表。

最简单的分析表是LR(0)分析表。

LR(0)分析表使用

S_i是状态，a_i表示终结符，A_i非终结符。

总控程序执行的操作根据栈顶状态S_m与读头下符号a_i查看得到：

1. 移进：将(S_m,a_i)的下一个状态S' = GOTO(S_m,a_i)连通读头下的字符进栈，栈顶成为(S’,a_i)，读头前进一格；
2. 规约：指用某产生式A -> B进行归约。若B的长度为r，则弹出栈顶的r个元素，使得栈顶的状态变成S_m-r，然后把(S_m-r,A)的下一个状态S’=GOTO(S_m-r,A)连同非终结符A一起推进，栈顶变成(S’,A)，读头不动；
3. 接收
4. 报错

LR(0)分析表中符号定义：

即S_j的j是状态，r_j的j是第j个产生式，含义不同。

注意：碰到r_j时进行规约，是将产生式反过来用。

LR文法判断

定义：如果某一文法能够构造一张分析表，使得表中每一元素至多只有一种明确动作，则该文法称为LR文法。

注：并非所有CFG都是LR文法，但对于多数程序设计语言来说，一般都可以用LR文法描述。

LR(0)分析表构造

• 基本思想：只根据历史信息识别呈现于栈顶的句柄。

• 基本策略：构造文法G的有限自动机，使其可以识别文法中的所有活前缀。

前缀：字的任意首部，例如对ABC，前缀为空串，A，AB，ABC

活前缀：规范句型的一个前缀，且该前缀不含有句柄之后的任意字符(即凑出句柄以便规约)。

活前缀有两种类型：

1. 归态活前缀：即活前缀的尾部刚好是句柄的尾部，此时可以直接进行规约；
2. 非归态活前缀：句柄尚未凑出来，需要继续移入符号。

那么如何识别活前缀呢？

需要构造一个有限自动机：

识别活前缀的有限自动机

定义：由于产生式右部的符号串就是句柄，若这些符号串都已进栈，则表示它已处于归态活前缀，若只有部分进栈，则表示它处于非归态活前缀。要想知道活前缀有多大部分进栈了，可以为每个产生式构造一个自动机。由该自动机的“状态”来记住当前情况，此状态称为“项目”。

这些自动机的全体就是能识别所有活前缀的有限自动机。

项目：为文法的每一个产生式的右部添加一个圆点，圆点可以在产生式的任意位置，即生成不同的项目。

1. 例如产生式右部符号串长度为n，则可以产生n+1个项目
2. 可以把圆点看作栈内外的分界线，即句柄的凑成进度。
3. 生成空串的产生式只有一个项目。

例如：

1. A → ·XYZ：预期要归约的句柄是XYZ，但都未进栈；
2. A → X·YZ：预期要归约的句柄是XYZ，仅X进栈；
3. A → XY·Z：预期要归约的句柄是XYZ，仅XY进栈；
4. A → XYZ·：已处于归态活前缀，XYZ可进行归约。 <== 这个项目是归约项目

因此，根据给出的文法可以构造识别活前缀的NFA：

1. 将仅出现在左部的非终结符作为唯一的初态，然后把所有n个产生式标记为对应的n个状态，再根据圆点的位置，将各个状态的转化图画出来即得到NFA。(例如上面1状态，识别X即转化为2状态；2状态识别Y即达到3状态。)；
2. 将圆点在产生式最后时，到达终态；
3. 若圆点后为非终结符A，则将该终态读取空串到达所有A -> ·α(即圆点出现在最左边的A项目)的状态。

画出NFA之后，即可通过词法分析中的方法确定化为不含有空串的DFA。

构造识别活前缀DFA的另一种方法

对于拓广文法，即存在产生式S->S’的文法(不存在也可以构造)，有另一种写DFA的方法：

写NFA再确定化很麻烦，可以通过拓广文法的方式，直接写出DFA。

例如：起始状态对应的产生式为S->·E，此时圆点后为非终结符E，此时对该状态做拓广，扩大闭包范围，将所有E->·α的产生式加入状态0所代表的项目集，此时即为DFA中的起始状态。

圆点移动到E的后面时，此时识别完全，即为终结状态。

重复这个过程即可写出DFA。

构造LR(0)分析表

写出DFA之后，将状态写到分析表的的纵列，将终结符写道Action横列，非终结符写到GOTO横列。

此时即可构造LR(0)分析表，状态可以分成两类：归态(即圆点到达最后的状态)和非归态。

• 对非归态：接收终结符到达另一个状态n，此时写入s_n；接收非终结符到另一个状态n，直接将状态数n填入。

• 对归态：接收任意非终结符，均做该状态本身对应产生式的规约操作r_m。

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

属性文法

定义：属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。

属性一般分为两类：综合属性和继承属性。

• 综合属性用于“自下而上”传递信息
• 继承属性用于“自上而下”传递信息。

属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。

注意：

1）终结符只有综合属性，它由词法分析器提供；

2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

综合属性：

在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。

继承属性：

在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。

第七章 语义分析和中间代码的产生

紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。

静态语义检查通常包括：

1. 类型检查
2. 控制流检查
3. 一致性检查
4. 相关名字检查。

翻译为中间语言的好处：

（1）便于进行与机器无关的代码优化；

（2）使编译程序改变目标机更容易；

（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。

中间语言

首先要掌握几种中间语言的基本结构：逆波兰表示，图表示法（DAG 和抽象语法树），三地址代码（四元式、三元式、间接三元式）。

逆波兰式

将操作符放在后面，将操作数放在前面的中间语言写法。

例如：-a + b * (-c + d)

写出逆波兰式：(a-)b(c-)d+*+。先算乘除再算加减，其实很容易。

再比如 a + b * (c-d)/e - f

写出逆波兰式：a bcd-* e/ +f-

后缀式(即逆波兰式)优点：易于计算机处理，常用方法是使用一个栈，自左向右扫描后缀式，没碰到运算对象就压栈，每碰到K目运算符就把它作用于栈顶的K个运算对象，并用运算的结果来取代栈顶的K个运算对象。

三地址代码

三地址代码是由下面一般形式的语句构成的序列:

​ X:=y op z

其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符。

四元式

一个四元式是具有四个域的记录结构，表示为（op, arg1, arg2, result）。其中，OP表示运算符，arg1、arg2及result为指针，指向有关名字在符号表中的登记项或一临时变量。

四元式通过临时变量来传递数据。

三元式

三元式是只具有3个域的记录结构，表示为（op, arg1, arg2）。其中，op为运算符，arg1、arg2即可指向有关名字在符号表中得登记项或临时变量，由名字自身表示，也可以指向三元式表示的某一个三元式编号。

示例分析：写出赋值语句a:=b*(-c)+b*(-c)对应的三元式和四元式

三元式和四元式序列的顺序与表达式的计算顺序一致，其中四元式需要存放中间结果的临时单元，而三元式没有，用三元式的编号来代替，节省了编译程序需要的存储空间。在翻译时用*@来代表求一元负*。

三元式中arg2中的序号即前面三元式计算结果存储的地址。

基本概念

（1）从功能上说，程序语言的语句大体可分为(执行性)语句和(说明性)语句。

（2）所谓语句制导翻译方法是为每个产生式配上一个(翻译子程序)，并在(语法分析)的同时执行它们。

（3）语法制导的翻译是基于属性文法的，属性有两大类，即(综合)属性和(继承)属性。

（4）在语法树中，一个结点的综合属性的值由其（子节点）的属性值确定，而继承属性则由该结点的（父节点或兄弟节点）的某些属性确定。

（5）语义分析阶段所生成的与源程序等价的中间表示形式可以由（逆波兰式、四元式与三元式）。

（6）生成中间代码主要是为了使（目标代码的优化容易实现）。