封面

---

简介：本篇博客记录了我学习编译原理的过程，由于编译原理包含了大量概念和算法，所以在最开始阐述编译原理的大框架，帮助形成学习体系，更好理解。
  

---

零. 编译原理框架

1. 词法分析

词法分析是用于分析一个单词合法与否，比如变量aaaa是合法的，但1aaaa是不合法的，词法分析的目的就是让机器能够理解一套词法规则来判断单词的合法性。为此学习以下方面：

1. 识别单词的词法规则：正规式
2. 正规式的数据结构：DFA/NFA
3. 词法分析的工作器：词法分析器

要使得机器能够完成词法分析，就要先书写我们需要的词法的正规式，然后构造能让机器理解的正规式的数据结构，最后构造词法分析器，其利用了该数据结构完成词法分析。

2. 语法分析

语法分析和词法分析是非常相似的，语法分析是用于分析语法合法与否，比如int a=1;是合法的，int a=是不合法的。语法分析的目的就是让机器能够理解一套语法规则来判断语句的合法性。为此学习以下方面：

1. 识别语句的语法规则：上下文无关法
2. 上下文无关法的数据结构：预测分析表/移进规约分析表
3. 词法分析的工作器：递归预测分析器、非递归预测分析器、移进规约预测分析器

要使得机器能够完成语法分析，就要先书写我们需要的语法的上下文无关法，然后构造让机器能理解的上下文无关法的数据结构，最后构造语法分析器，其中不同的数据结构代表机器的不同的理解方式，其构造出的语法分析器也就不同。

一. 编译器概述

1. 计算机语言

面向机器语言：机器指令、汇编
面向人类语言：通用程序设计语言、数据查询语言…

2. 语言之间的翻译

2.1 翻译模式

正向工作：

1. 汇编语言->机器指令：汇编/交叉汇编
2. 高级语言->汇编语言/机器指令：编译/交叉编译
3. 高级语言->高级语言：转换/预编译/预处理
   （如#include)

逆向工作：
反汇编/反编译

2.2 翻译形态

2.2.1 编译器：先翻译后执行

特点：工作效率高（时间快、空间省）、交互性与动态特性差、可移植性差
功能：完成翻译

2.2.2 解释器：便翻译边执行

特点：工作效率低（时间慢、空间费）、交互性与动态特性好、可移植性好
功能：完成翻译

3. 编译器的构成与工作原理

3.1 通用程序设计语言的主要成分

基本抽象：过程（函数）、抽象数据类型、类
定义方式：声明+操作
组成部分：头+体（如函数头+函数体）
（ 其中：
体包括：

1. 声明性语句
   编译器生成相应环境（存储空间）
2. 操作性语句
   编译器生成可执行代码序列
   ）

3.2 编译器的工作阶段

1. 词法分析：识别记号（关键字（保留字）、标识符、字面量、特殊符号）
2. 语法分析：识别语言结构，并以树的形式表示
3. 语义分析：语义计算和处理。如考察结构正确的句子是否语义合法、修改树结构、查填符号表
4. 中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于代码优化
5. 中间代码优化（可选）：优化实际上是等价变换，变换前后功能完全相同，但空间时间上都更好
6. 目标代码生成：不同形式的目标代码，如：汇编、可重定位的二进制代码、内存形式（Load and Go）
7. 符号表管理：合理组织符号，便于各阶段查找、填写等
8. 出错处理：词法错、语法错、静态语义错（x/0)、动态语义错(x/y，y在运行中可能为0)
   

3. 编译器的构造方法

架构：
分析（前端）->中间代码->综合（后端）
构造方法：

1. 直接使用汇编语言/通用程序设计语言
2. 利用编译器编写工具
3. 基于编译器基础架构的编译器构造系统（开放式编译器，如GCC/LLCM/SUIF/COINS）

二. 词法分析

1. 基本概念

1. 单词：被识别出的元素自身的值，也叫词值。
   类别：
   关键字：kw，如if while
   标识符：id，如变量名
   字面量：literal，如60
   特殊符号：ks，如= +
2. 模式：产生和识别单词（元素）的规则
3. 记号：按照某个模式识别出的元素
   记号=记号类别+记号属性
   

词法分析器：
特征：唯一接触源程序的部分
任务：

1. （根据模式）识别记号，并交给语法分析器
2. 过滤源程序无用成分，如注释、空格、回车
3. 处理与具体平台有关的输入（如回车）
4. 调用符号管理器或出错处理器

工作方式：

1. 单独扫描一遍
2. 作为语法分析器的子程序（需要时调用词法分析器）
3. 并行（词法分析器生成记号流同时语法分析器处理）

2. 正规式

2.1 语言与字符串

在词法分析的角度，语言L是有限字母表上有限长度字符串的集合（语言是由记号组成的集合）
字符串运算：

集合运算：

2.2 正规式与正规集

其中：
正规式运算优先级从高到低为：闭包运算、连接运算、或运算

2.3 等价正规式

若正规式P，Q表示同一正规集，则P和Q等价，记作P=Q
证明方法：

1. 证明不同正规式表示的集合相同
2. 根据正规式代数性质运算
   

2.3 简化正规式

若r是表示L（r）的正规式，则

1. 正闭包：r⁺=rr*=r*r,r*=r|ε
   其中：*和⁺运算优先级相同
2. 可缺省：r?=r|ε
   其中：*和?运算优先级相同
3. 串："r"=r,ε=""
   可用于字符转义，如：“|”表示字符|而非或运算
4. 字符组：r=[r']
   其中：r是由若干字符进行或运算构成的正规式，
   r’有两种书写形式：
   1. 枚举：a|b|c|d=[abcd]
   2. 分段：a|b|c|d=[a-d]
5. 非字符组：[^r]是表示∑-[r]的正规式
6. 辅助定义：名字=正规式
   名字仅供正规式内部使用（类似于C语言中define）

2.4 正规式说明记号

记号=正规式
如：relation = <|>|<=|>=|=

3. 不确定的 有限自动机（NFA）

模式的识别/正规集的描述：正规式
记号的识别/正规集的识别：有限自动机
最大的特点：不确定性（即某一状态对于一个字符可能有多个状态转移）

3.1 定义

NFA是一个五元组：M=(S,∑,move,s0,F)
其中：

1. S：有限个状态的集合
2. ∑：有限个输入字符的集合
3. move：状态转移函数。
   move(si,ch)=sj表示当前状态si遇到输入字符ch转移到状态sj
4. s0：唯一的初态（开始状态）
5. F：终态集（接收状态集），它是S的子集，包含所有终态

3.2 表示方法

• 状态转换图：
  节点：代表NFA中每个状态
  边：代表NFA中的状态转移函数。连接两个状态，边上标记输入的字符

• 状态转移矩阵：
  行标：∑中的字符
  列标：S中的状态
  矩阵值：对应状态接受对应字符后转移到的状态集合
  

3.3 识别方法

对于一个输入序列：

1. 从NFA初态开始
2. 对于输入的每个字符，寻找其下一个状态转移，直到到达一个终态，或没有下一个状态转移（根据最长匹配原则，要求所有字符都被输入）
   1. 如果此时处于终态，则NFA接受该序列
   2. 否则，回溯+试探：沿原路返回，对于每个状态寻找另一种可能的状态转移，若能到达终态，则NFA接受该序列，否则（一直返回到初态都不能到达终态）不接受
      

3.4 等价有限自动机

若有限自动机M和M’识别同一正规集，则M和M’等价，记作M=M’

3.5 构造NFA

使用Thompson算法，先将正规式分解，然后使用以下规则构造NFA：

4. 确定的有限自动机（DFA）

由于DFA识别记号时需要尝试所有路径才能确定一个序列不被接受，且识别时要进行大量回溯，算法较为复杂，时间复杂度高，所以提出构建一种有限自动机，其在任一状态下遇到同一字符最多有一个状态转移

4.1 定义

DFA是NFA的一个特例，其中

1. 没有状态具有ε状态转移（即状态中没有标记ε的边）
2. 对于每个状态和每个字符，最多有一个下一状态

4.2 构造DFA（确定化NFA）

ε-闭包

ε-闭包(T)：状态集T上的ε-闭包(T)代表从状态集T出发，经过ε（即不经过任何字符）可到达的状态全体，其构造方法为：

1. （初始化）T中所有状态属于ε-闭包(T)
2. （更新）将smove(ε-闭包(T),ε)中的状态添加进ε-闭包(T)
3. 循环2，直到不能转移到任一其它状态

其中：smove(S,ch)代表对于S中的每个元素接受字符ch后能够到达的状态（move(item_in_S,ch)）的合集

子集法构造DFA

输入：NFA，M=(S,∑,move,s0,F)
输出：DFA，DM=(DS,D∑,Dmove,Ds0,DF)

1. （初始化）初态Ds0为ε-闭包(s0)；令DS∪=Ds0
2. 对于DS中每个元素ds，∑中每个字符ch，计算得smove(ds,ch)=new_ds；令DS∪=ε-闭包(new_ds)，move+=(move(ds,ch)=ε-闭包(new_ds))
3. 循环2，直到DS中所有元素都被计算过

其中：D∑=∑，终态DF为DS中包含终态F中元素的元素集合

例：

1. 初态：求0的ε的闭包：经过任意条ε所能到达的状态，集合为{0,1,3,4,5,6,7,9}，将其填入表格第一行第一列

	a	b
{0,1,3,4,5,6,7,9}

2. {0,1,3,4,5,6,7,9}中：1接受a到达2，4接受a到达4，其余没有接受a到达某个状态，所以集合为{2,4}，其的ε-闭包为{2,4,6,7,9}，将其填入第一行第二列
3. {0,1,3,4,5,6,7,9}中：同2，接受b，最后得到集合{5,6,7,8,9}，将其填入第一行第第三列

	a	b
{0,1,3,4,5,6,7,9}	{2,4,6,7,9}	{5,6,7,8,9}

4. 观察{2,4,6,7,9}和{5,6,7,8,9}未在第一列出现，将他们填入第一列

	a	b
{0,1,3,4,5,6,7,9}	{2,4,6,7,9}	{5,6,7,8,9}
{2,4,6,7,9}
{5,6,7,8,9}

5. 同2，3对{2,4,6,7,9}和{5,6,7,8,9}计算，然后同4添加元素，再重复计算，最终得到表格，并对新的状态集重新编号：
   
6. 根据状态表绘制状态图：
   

4.2 最小化DFA

• 可区分：对于状态s和t，若其中一个状态接受字符串w而另一个状态不接受，或者存在字符串w使得s和t接受后到达不同的状态，则s和t是可区分的

• （不可区分：对于状态s和t，接受任意字符串到达的状态都是一样的，则s和t不可区分）

• 死状态：接受任意字符都转向其自身，且不是终态

• 不可达状态：从初态不可到达的状态

最小化算法

对于DFA：D=(S,∑,move,s0,F)

1. 初始化分∏={S-F,F}
2. 开始新一轮划分，对于两个状态s，t，若它们接受任意字符后到达的状态同属于∏中的某一个状态集合，则将它们划分至一个状态，否则它们就是不同的状态。
   遍历每个状态（不包括∏中不可再划分的状态集合中的元素），应用上述规则，产生新的∏
3. 循环2，直到∏中的每个状态集合都不可以再划分
4. 得到最终的∏，包含s0的状态集合为新的初始状态，包含F的状态集合构成新的终态集，然后对于其中的每个状态集合，用状态集合中的某一个元素代替该集合，并继承所有对该集合的状态转移函数
5. 删除死状态和不可达状态

例：

1. 初始划分∏={ABCD,E}
2. ∏[2]不可再划分，所以只遍历ABCD，ABCD接受a都到达B，B属于∏[1]，ABC接受b分别到达CDC，CDC都属于∏[1]所以ABC不可区分，划分为同一组，而D接受b到达E，E属于∏[2]，所以D划分为另一组，于是∏更新为{ABC,D,E}
3. 同理对ABC遍历，∏更新为{AC,B,D,E}
4. 对AC遍历，AC不可再划分，此时所有组都已经不可被划分，所以最终∏={AC,B,D,E}
5. 选代表，用A代替组AC，更新状态转移表，删除死状态和不可达状态（此例没有）得到DFA如图
   

5. 词法分析器（基于DFA）

5.1 表驱动型词法分析器

使用时，驱动器调用DFA查表

5.2 直接编码型词法分析器

将驱动器和DFA操作合并，直接模拟DFA输入

5.3 对比

	表驱动	直接编码
分析器速度	慢	快
程序与模式关系	无关	有关
适合的编写方式	工具生成	手工编程
分析器的规模	较大	较小

三. 语法分析

词法分析：字母是元素，组成字符串，记号的集合，线性结构
语法分析：记号是元素，组成句子，句子的集合，树结构
语法的含义：

1. 语法规则：上下文无关法
2. 语法分析：下推自动机，自上而下和自下而上分析

1. 基本概念

语法分析器作用：

1. 根据词法分析器提供的记号流，构造语法树
2. 检查输入中的语法（可能包括词法）错误，并调用出错处理器进行处理。

源程序中出现的错误：

1. 词法错误：如非法字符、拼写错误（20id，intege）
2. 语法错误：语法结构出错，如缺少分号、begin/end不匹配
3. 静态语义错误：如类型不一致、参数不匹配
4. 动态语义错误（逻辑错误）：如死循环、除数为0

错误的恢复策略

1. 紧急方式恢复：抛弃若干输入，直到接受合法输入
2. 短语级恢复：采用串替换方式（抛弃+插入）方式对剩余输入局部纠正
3. 出错产生式：用出错产生式捕捉错误，用预制的短语级恢复
4. 全局纠正：寻找相近输入序列

2. 上下文无关法（CFG）

2.1 定义

CFG是一个四元组：G=(N,T,P,S)
其中：

1. N是非终结符的有限集合
2. T是终结符的有限集合，且N∩T=ф
3. P是产生式的有限集合（产生式A->a，其中A∈N（左部），a∈(N∪T)*（右部），若a=ε，则称A->ε为空产生式，也记为A->）
4. S是非终结符，称为文法的开始符号

2.2 表示方法

由产生式集表示CFG
约定：

1. 第一个产生式左部是文法开始符号S
2. 大写英文字母表示非终结符，小写英文字母表示终结符
   分析树
3. 当若干个产生式左部相同时，可以将它们合并为一个产生式，所有右部用或运算连接

例：简单的算术表达式可以表示为
N={E} T={+,*,(,),-,id} S=E
p:
E->E + E
E->E * E
E->(E)
E->-E
E->id
或者表示为
E->E + E|E * E|(E)|-E|id

2.3 上下文无关语言（由CFG定义的语言）

推导

推导是产生语言的方法

1. 直接推导：对于产生式A->γ，令αAβ替换为 αγβ的过程叫做直接推导，记作αAβ⇒αγβ
2. 零步或多步推导：α1⇒α2⇒…⇒αn，记作α1⇒∗αn，其中α1=α2的情况为零步推导
3. 至少一步推导：对于零步或多步推导，若α1不等于αn则为至少一步推导，记作α1⇒^+^αn

若每次推导均替换句型中最左边非终结符，则称为最左推导，由最左推导产生的句型为左句型，另外最右推导也被称为规范推导

语言

由上可知：
由CFG G产生的语言L(G)被定义为：
L(G)={ω|S⇒^+^ ω and ω∈T^∗^ }

L(G)称为上下文无关语言，ω称为句子
（句型：若 S⇒^∗^α,α∈(N∩T)^∗^则α为G的一个句型）

例：
N={E} T={+,*,(,),-,id} S=E
可有以下推导：
E⇒−E⇒−(E)⇒−(E+E)⇒−(id+E)⇒−(id+id)
其中-(id+id)为句子，其余除了E都为句型

2.4 分析树和语法树

对于CFG的句型，其分析树（具体语法树）被定义为：

1. 根由开始符号标记
2. 对于推导出CFG的每一步推导 αAβ⇒αγβ，将γ中的每一个终结符、非终结符（或ε）从左到右添加为A的孩子

其语法树（抽象语法树）被定义为:
3. 根与内部节点由操作符标记
4. 叶子节点由操作数标记
5. 用于改变优先级的括号被隐含在语法树结构中

例：

左边为分析树，右边为语法树

2.4 二义性

（了解什么是二义性，和消除二义性的方法，不要求具体实现）
二义性：若文法 G 对 同 一句子产生不止一棵分析树，则称G是二义的
造成文法二义性的原因：文法对文法符号优先级缺少规定
消除二义性：

1. 改写二义文法为非二义文法
2. 规定二义文法中符号的优先级和结合性
   （3. 修改语言的语法）

2.5 左递归左因子

左递归

若文法G中的非终结符A，对某个文法符号序列$\alpha$存在推导$A\Rightarrow ^+A\alpha$，则G是左递归的

消除左递归

对于A⇒Aα1∣Aα2∣…∣Aαm∣β1∣β2∣…∣βn，其中αi非空，βj均不以A开始，用下述产生式替代：
A⇒β1A′∣β2A′∣…∣βnA′
A′⇒α1A′∣α2A′∣…∣αmA′∣ε

左因子

若文法G中的非终结符A，存在推导A⇒αβ1∣αβ2，则文法有公共左因子

消除左因子

对于A⇒αβ1∣αβ2∣…∣αβn∣γ，用下述产生式替代：
A⇒αA′∣γ
A′⇒β1∣β2∣…∣βn

2.6 正规式的上下文无关法

正规式所描述的语言均可用CFG表示，但反之不一定

构造法

首先构造正规式的NFA，然后构造CFG：

1. 若0为初态，则A0为开始符号；
2. 对于move(i,a)=j，引入产生式Ai→aAj；
3. 对于move(i,ε)=j，引入产生式 Ai→Aj；
4. 若i是终态，则引入产生式Ai →ε。

经验法

拆分正规式，如r=(a|b) * abb包含(a|b) *和abb两部分，则引入A->HT,H->ε| aH | bH,T->abb

2.7 其它文法

文法G=(N，T，P，S)的每个产生式α→β中，均有α∈(N∪T)^* ，且至少含有一个非终结符，β∈(N∪T)^* ，则称G为0型文法。
对0型文法施加以下第i条限制，即得到i型文法。

1. G的任何产生式α→β（S→ε除外）满足|α|≤|β|
2. G的任何产生式形如A→β，其中A∈N，β∈(N∪T)^* ；
3. G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T。

3. 递归下降分析器

递归下降分析器使用了自上而下语法分析的思想，对于任意一个输入序列（记号流），从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。自上而下语法分析是从开始符号一步步推导到句子的过程。
递归下降分析器使用文法的状态转换图实现

3.1 文法状态转换图

3.1.1 定义

对于产生式A→X1X2…Xn，生成一个初态和终态，然后构造从初态到终态的路径，边标记依次为X1，X2，…，Xn。

3.1.2 化简

对于产生式A→X1X2…Xn的状态转换图，化简如下：

1. 标记为A的边可等价为标记ε的边转向初态
2. 合并ε边连接的两个状态
3. 合并不可区分的状态

3.2 EBNF文法

EBNF文法有别于上下文无关法的一种文法，它使用以下特殊符号

1. { }：重复0或若干次
2. [ ]：可缺省
3. | ：括弧之内的或关系
4. ( )：改变运算的优先级和结合性

3.3 分析器构造过程

1. 构造文法的状态转换图并且化简
2. 将转换图转化为EBNF表示
3. 从EBNF构造子程序:
   每个非终结符都是一个函数，该非终结符的产生式右部中，遇到非终结符则进入该非终结符对应函数，遇到终结符则与输入记号进行匹配
   ({}：while，[]:if，|:case)

4. 非递归预测分析器

非递归预测分析使用自上而下的思想
非递归预测分析使用了预测分析表来辅助推导句子。下面将阐述如何构造预测分析表以及非递归预测分析器的工作步骤

4.1 预测分析表

理解：预测分析表是一张可以根据当前非终结符和我要经过推导得到的终结符告诉我我需要将该非终结符替换成什么内容，如果预测分析表对应处是空白，则意味着该非终结符没法推导得到该终结符

4.1.1 First集合

文法符号序列α的First集合为：
First(α)={a|α⇒^^a…,a∈T}，特别的，若α⇒^^ε，则ε∈First(α)

理解：对于每个α能推导到的序列，该序列以终结符开头，则将该终结符加入First(α)集合

计算方法：

1. 若X是终结符，则First(X)={X}
2. 若X是非终结符，且有X⇒^*^ε，则将ε加入First(X)
3. 若X是非终结符且有X⇒Y1Y2…Yk，则应用以下规则：将First(Y1)中所有元素（除ε）加入到First(X)，若First(Y1)包含ε，则将First(Y2)元素加入。以此类推若First(Yj)包含ε则将First(Yj+1)元素加入（除ε）

4.1.2 Follow集合

非终结符A的Follow集合为：
Follow(A)={a|S⇒^*^…Aa…,a∈T}，若A是某句型的最后一个符号，则#∈Follow(A)

计算方法：

1. 若S是开始符号，加入#到Follow(S)
2. 若有产生式A->αBβ，则将First(β)的所有元素（除ε）加入到Follow(B)
3. 若有产生式A->αB或A->αBβ（且First(β)包含ε），则将Follow(A)的所有元素加入到Follow(B)

例：

4.1.3 构建分析表

1. 对文法的每个产生式A->α，执行2和3
2. 对First(α)中的每个终结符a，令M[A,a]=α
3. 若ε∈First(α)，则对Follow(A)中的每个终结符b（包括#），令M[A,b]=α

4.2 工作过程

1. 初始栈中为#S，匹配符号为原句子第一个符号
2. 若栈顶为终结符：如果栈顶符号=匹配符号，pop栈，然后匹配符号移至下一个符号；若栈顶为非终结符，根据栈顶符号和匹配符号查询预测分析表，将栈顶符号替换为预测分析表对应内容；
3. 若不满足2中所有情况，则报错，该语句不符合语法
4. 循环2、3，直到栈中只剩#，并且原句子所有符号都已经被匹配过，则该语句符合语法，否则出错

4.3 LL(1)分析器

LL(1)分析器是非递归预测分析器的特例，当且仅当它的预测分析表没有多重定义的条目（一个格子里出现多个选项），构成该预测分析表的文法被称为LL(1)文法。
(LL(K)的含义是：L：从左到右扫描，L：最左推导，K：向前看K个符号知道下一个动作）

判定方法

文法G是LL(1)的，当且仅当G的任意两个产生式 A->α|β 满足：

1. 对任何终结符a，α和β不能同时推导出以a开始的串
2. α和β最多有一个可以推导出ε
3. 若β可以推导出ε，则α不能推导出以Follow(A)中终结符开始的任何串

二义性、有左递归或者左因子的不是LL(1)文法

5. 移进规约预测分析器

非递归预测分析其使用了自下而上语法分析的思想，对于任意一个输入序列（记号流）ω，从ω开始进行反复用产生式的左部替换产生式的右部、谋求对ω的匹配,最终得到文法的开始符号，或者发现一个错误。自下而上语法分析是从句子一步步推导得到开始符号的过程
移进规约预测分析器通过移进规约分析表指导其工作，通过不断移进（将剩余输入的下一字符入栈）和规约（将栈顶句柄（符合某一产生式右部）替换为产生式左部）完成分析。要想构建移进规约预测分析器，就要先想清楚如何识别一个文法的活前缀

5.1 基础概念

5.1.1 短语

设αβγ是文法G的一个句型，若存在S⇒αAγ，A⇒+β，则：
称β是句型αβγ相对于A的*短语
特别的，若有A->β，则称β是句型αβγ相对于A->β的直接短语
一个句型的最左直接短语称为句柄

利用语法分析树快速查找短语：

1. 短语：以非终结符为根的子树中所有从左到右的叶子
2. 直接短语：短语中以非终结符为根的子树树高为2（其和其为根的子树中所有叶子都为父子关系）
3. 句柄：最左边的直接短语
   

5.1.2 最左规约

文法G的句子α的一个最左归约为一个序列
αn，αn-1，…，α0，其中

1. αn = α
2. α0 = S（S是G 的开始符号）
3. 对任何i(0<i<=n)，αi-1是将αi中的句柄替换为 相应产生式左部非终结符得到的。

最左规约又称规范规约，最左规约的逆过程是一个最右推导（规范推导）

例：

利用语法分析树快速得到最左规约：

最左规约在语法分析树上的表现是不断剪句柄的过程，不断在语法分析树上剪去当前语法分析树的句柄，直到只剩下开始符号
例：

5.1.2 活前缀

5.1.3 项目

项目：在产生式的基础上，在其右部某一位置添加一个 .
可移进项目：项目A->α.β，且β不为空
可规约项目：项目A->α.β，且β为空

理解：项目A->α.β代表的含义是，我现在已经有了α，我期待一个β出现在α后面，这样我可以把αβ规约为A
例：
对于产生式E->E-T|T，其能生成的全部项目有：
E->.E-T ; E->E.-T ; E->E-.T ; E->E-T.
E->.T ; E->T.

5.1.4 拓广文法

拓广文法G‘=G∪{S’->S}

5.1.5 closure项目集

项目集I的closure(I)是这样一个项目集：

1. I中所有项目属于closure(I)
2. 若对于非终结符B，A->α.Bβ属于closure(I)，则若有形如B->γ的产生式，那么B->.γ项目属于closure(I)

例：

5.1.6 goto项目集

对于项目集I，终结符或非终结符X，goto(I,X)是这样一个项目集：

• 项目集I中若存在形如A->α.Xβ的项目，则A->αX.β属于goto(I,X)

例：

5.2 识别活前缀的DFA

1. 计算DFA的初态，初态I0=closure({S’->.S})
2. 对于状态集Ii，对其中形如A->α.Xβ的产生式，引入move(li,X)=lj，其中lj的内容=closure(goto(Ii,X))（若lj内容已经和DFA的某个状态的内容一样，则li只用指向已经存在的那个状态，否则新建一个状态）
3. 对于所有未被计算过的状态集执行2，直到所有状态集都被计算过
4. 内容中包含S’->.S的状态为初态，包含S’->S.的状态为终态

例：

其中I0是初态，I1是终态

5.3 SLR(1)分析表

移进规约分析表包含两部分，一部分是action用于指导移进规约（横标题为终结符的部分），另一部分是goto用于指导状态转移（横标题为非终结符的部分）
(LR(K)的含义是：L：从左到右扫描，R：逆序的最右推导，K：向前看K个符号知道下一个动作）

5.3.1 定义

如果项目没有冲突或者冲突可以解决，则该分析表是SLR(1)分析表，构造其的文法是SLR(1)文法

项目冲突：

1. 移进/归约冲突：A→β1.β2和B→β.：既可移进又可归约
2. 归约/归约冲突：A→α.和B→β.：均可指导下一步分析

SLR(1)方法解决冲突：

1. 移进/归约冲突：若FIRST(β2)∩FOLLOW(B)=Φ，冲突可解决
2. 归约/归约冲突：若FOLLOW(A)∩FOLLOW(B)=Φ，冲突可解决

另外补充，如果有冲突就不是LR(0)文法

5.3.2 构造分析表

根据识别活前缀的DFA构造SLR(1)分析表：

1. 对于DFA每个状态转移move[i,x]=j ：
   1. 若x是终结符，令action[i,x]=sj
   2. 若x是非终结符，令goto[i,x]=j
2. 每个状态i的可归约项A→α.：
   1. 若该项目为S’→S.，令action[i, #]=acc
   2. 否则，对于Follow(A)中的每个元素b，令action[i,b]=rk。 其中k代表第k个产生式，该产生式可以生成项目A→α.

例：

5.4 工作过程

对于输入序列ω，分析器分析器的步骤为：

1. 初始栈中为(#0)，剩余输入为(ω#)
2. 设栈中最右符号为T，剩余输入最左符号为a，查询分析表得到action[T,a]=Z，若：
   1. Z为sj，将a和j入栈，a从剩余输入移走。（完成移进）
   2. Z为rj，找到第j个产生式，不断弹出栈中内容，直到弹出的所有终结符和非终结符构成了产生式的右部，此时栈中最右符号是一个状态Ta，将产生式左部F入栈，然后将goto[Ta,F]的内容入栈（完成规约）
   3. Z为acc，分析成功，接收该输入序列
   4. Z为空白，报错
3. 循环2，直到分析成功或报错

四、语义分析

语法是语言的结构
语义是附着于语言结构上的实际含义
语义分析作用，检查结构正确的句子所表示的意思是否合法，执行规定的语义动作

1. 语义规则

1.1 属性

属性就是附着在非终结符或终结符的一些值，如A.value可以代表附着在A上的值，A.type可以代表附着在A上的类型，这些值是由自己定义的

1.2 语义规则

对于产生式A->X1X2…Xn，其语义规则可以表示为有关属性的函数f：
b=f(c1,c2,…,ck)，称b依赖于c1,c2,…,ck

1. 若b是A的属性，c是x中或A的属性，则b是A的综合属性
2. 若b是x中xi的属性，c是x中或A的属性，则b是xi的继承属性
3. 若b为空（即语义规则为f(c1,c2,…,ck)），则其为A的虚拟属性

语义规则的两种形式：

1. 语法制导定义：抽象的属性和运算。如公式
2. 翻译方案：具体的实际和运算。如程序

例：表达式的语义规则

1.3 语法制导翻译

语法制导翻译：以语法分析为基础，伴随语法分析的各个步骤，执行相应语义动作

1. 用文法符号属性代表语言结构的意思
2. 用语义规则规定语言结构的关系（计算属性）
3. 执行语义规则

简而言之就是在语法分析的某些过程中，根据语义规则做计算属性、返回属性等操作

1.3.1递归下降分析器语法制导翻译

在产生式右部任意位置语义操作，文法符号的属性通过返回值、变量、参数等体现

1.3.1 移进规约分析器语法制导翻译

方式一：在规约时，执行相应语义操作
方式二：增加语义栈，存放文法符号属性值，根据属性进行相应语义操作

2. 中间代码的语义规则

2.1 中间代码

中间代码的表现形式有后缀式、三地址码、注释语法树

2.1.1 后缀式

后缀式：操作符在前，操作数紧随其后
如3+5 * 2/7的后缀式为：352 * 7/+

计算后缀式：
从左往右扫描后缀式，

1. 如果是操作数，入栈
2. 如果是操作符，查算符表得到该操作符是几元运算符，然后从栈中取出对应数量操作数，计算结果，将结果入栈

2.1.2 三地址码

类型有：

1. 二元运算：result=arg1 op arg2
2. 一元运算：result=op arg1
3. 直接拷贝：result=arg1

其中：op代表操作符，arg代表操作数，用操作符计算操作数，然后将等式右边结果存放在result中

例：x=a+b * c的三地址码序列为
T1=b * c
T2=a+T1
x=T2

三地址码有两种表现形式

1. 三元式：(i)(op,arg1,arg2)
   序号i唯一标识了三元式，且代表了结果存放的位置
2. 四元式：(i)(op,arg1,arg2,result)
   序号不再代表结果存放位置，而由result代表

例：x=a+b * c的三元式序列为
(1)( * ,b,c)
(2)(+,a,(1))
(3)(=,x,(2))
四元式序列为：
(1)( * ,b,c,T1)
(2)(+,a,T1,T2)
(3)(=,x,T2,T3)

2.1.3 注释语法树

注释语法树就是在语法树的基础上，在节点处标记一些信息

树的优化表示DAG：在构建的时候，查找要构造的节点是否存在，若已存在，则无需构造新的节点，直接返回指向已有节点的指针即可

2.3.4 注释语法树转后缀式和三地址码

转后缀式：对树进行深度优先后序遍历，遍历的序列就是后缀式

转三地址码：对树进行深度优先后续遍历，每遇到一个非叶子节点，就生成一个三地址码，操作符是其本身，操作数是其孩子的信息。

2.2 生成中间代码的语义规则

2.2.1 四元式语义规则

2.2.2 注释语法树语义规则

3. 声明语句的语义规则

声明语句的翻译主要是为变量分配存储空间，并将变量信息正确的填入符号表中

3.1 符号表

符号表就是用于区分记号类型都为ID的变量、标识符、保留字、特殊符号，并记录相关信息，如作用域

存储方式

1. 直接存储：变量名就是变量文本本身
2. 间接存储：变量名通过其它文本存储，如存储1代表aaa，存储2代表abd。解决了直接存储由于变量名不定长而难以存储的问题。

类型

1. 线性表
2. 哈希表

3.1 变量声明的翻译

3.2 过程声明的翻译

3.2.1 过程简介

过程和函数类似，有过程头（包含参数）、过程体，但是没有返回值

过程的参数调用有三种类型：

1. 值调用：形参
2. 引用调用：实参
3. 复写恢复类型：过程内对参数修改不会影响实参，返回时将形参内容恢复给实参
4. 换名调用：宏定义
   左值 右值（等式右边）

3.2.2 符号表树

由于作用域的存在，若过程允许嵌套，那么就不单单是往符号表里填过程声明的信息，而是要构建符号表树来表示每个过程定义的变量的作用域，每个过程就对应一个符号表

作用域规则

1. 静态作用域规则：
   静态读取程序就能知道名字的作用域
2. 最近嵌套原则：
   若程序块A有变量x的声明，则x的作用域包括A，若A中没有x的声明，但是引用了x，x的由嵌套A的程序块中离A最近且有x的声明的程序块定义

符号表树定义

3.2.3 过程声明的翻译

1. 函数mktable(previous)：建立一个新的符号表节点，并返回指向该节点的指针。参数previous是逆向链，指向该节点的前驱，即外层的符号表节点。
2. 过程enter(table, name, type, offset)：在table指向的符号表节点中，为变量name建立新的条目，包括名字的类型和存储位置等。
3. 过程addwidth(table, width)：计算table指向的符号表节点中所有条目的累加宽度，并记录在table的头部信息中。
4. 过程enterproc(table, name, newtable)：在table指向的符号表节点中，为过程name建立一个新的条目。参数newtable是正向链，指向过程name自身的符号表节点。

4. 可执行语句的语义规则

4.1 简单算术表达式的语义规则

涉及到强制类型转换的语义规则还要改变，核心思想是低精度类型转为高精度类型进行在进行运算

4.2 数组元素引用的语义规则

a[0..2, 2..4]代表三行三列，其中列标从2开始
若以行存放，则顺序为：
a[0,2] a[0,3] a[0,4] a[1,2] a[1,3] a[1,4] a[1,2] a[1,3] a[1,4]
若以列存放，则顺序为：
a[0,2] a[1,2] a[2,2] a[0,3] a[1,3] a[2,3] a[0,4] a[1,4] a[2,4]
下面按以行存放设计翻译方案：

1. 属性.array：数组名在符号表中的入口(数组首地址a)。
2. 属性.dim：数组维数计数器，记录当前分析到的维数。
3. 属性.place：
   下标列表EL：存放vj=vj-1*dj+ij (j=2，3，…, n)的地址（临时变量），
   简单变量id：仍然表示简单变量的地址，
   数组元素id[EL]：存放不变部分，一般可以是一个临时变量。
4. 属性.offset：保存数组元素地址中的可变部分，简单变量的offset为空，可记为null。
5. 函数limit(array, k)：计算并返回数组array中第k维成员个数dk。

4.3 布尔表达式的语义规则

布尔表达式：由not，and，or以及关系运算构成的表达式，结果为true或者false

4.3.1 直接计算布尔表达式的语义规则

将布尔表达式翻译成三地址码

1. not、and、or构成的运算的三地址码
   A or B and not C的三地址码：
   T1 := not C
   T2 := B and T1
   T3 := A or T2
2. 关系运算构成的三地址码
   a<b的三地址码：
   (0) if a<b goto (3)
   (1) t1 := 0
   (2) goto (4)
   (3) t1 := 1
   (4) …

语义规则

4.3.2 短路计算布尔表达式的语义规则

短路计算：一旦能确定布尔表达式，就返回结果，如A or B，如果A已经为ture，表达式结果就为true，不必考虑B的值。短路计算还可以这样的逻辑，如if (p!=NULL&&p->a==0)，如果p为空就不会执行p->a，避免了错误

核心思想

真出口：A的属性A.ture，指向A为真时要前往的地址
假出口：A的属性A.false，指向A为假时要前往的地址

对于布尔表达式E-> E1 or E2
E1.ture=E2.true=E.true
E2.false=E.false
E1.fasle=E2.code的地址
即如果E1或者E2为真，那么表达式E就为真，转向E为真要转向的地址
如果E1为假，那么还要继续执行E2的代码，如果E2还为假，那么表达式E为假，转向E为假要转向的地址
可见.ture属性是一个继承属性

拉链回填技术

为设计短路计算的翻译方案，要设计一种翻译方案，使得仅对分析树进行一次遍历即可生成所需的中间代码序列，确定所有真出口假出口。
为此设计拉链回填技术：
当三地址码中的转向不确定时，将所有转向同一地址的三地址码拉成一个链；一旦所转向的地址被确定，则为此链上的所有三地址码中回填入此地址。

翻译方案

新增属性与函数：

1. 属性. tc：真出口链，链接所有转向同一真出口的三地址码；
2. 属性.fc：假出口链，链接所有转向同一假出口的三地址码。
3. 函数mkchain(i)：为序号是i的三地址码构造一个新链，且返回指向该链的指针；
4. 函数merge(P1，P2)：合并链P1和P2，且P2成为合并后的链头，并返回链头指针；
   过程backpatch(P，i)：向P链中所有三地址码均回填 出口地址为值 i

4.4 控制语句的翻译

---

结语：缺少活前缀
  

---

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 21009200039@stu.xidian.edu.cn