title: 编译原理课程笔记
description:
published: true
date: 2023-12-07T08:56:52.454Z
tags:
editor: markdown
dateCreated: 2023-12-04T06:10:03.782Z
¶ 编译原理
¶ 大纲
¶ 题型
一共六个大题：
- 概念题
- 词法分析
- 语法分析（自上而下和自下而上俩题）
- 中间代码生成
- 代码生成+优化
¶ 各章考点及历年考试覆盖内容
按课本知识顺序（也是编译原理的工作顺序）从前往后组织这部分内容。
¶ 1. 基础概念
只会出前面的概念/简答题。
- 自动机/正规式/正规集的概念
- 句子/句型/文法的概念
- 中间代码生成的概念，方法及优缺点
- 基本块/流图的概念
- 活动记录/内存分配方式
- 参数传递方式，1）传值，2）传地址，3）传名，4）传地址+值的结果
- 等等
¶ 2. 词法分析
词法分析核心知识在于“正规集->正规式->DFA”的过程，需要掌握化简方法，占一个大题。
¶ 3. 语法分析
语法分析出两道大题，分别是自上而下和自下而上方法。题目会给文法，要求给出分析表。
- 自上而下的语法：递归下降和
LL(1) - 自下而上的语法都是LR语法，包括
LR(0)（重点），SLR(1)（重点），LR(1)，LLR(1)
¶ 4. 语法制导翻译
只会出概念题。
¶ 5. 中间代码生成
出一道大题，解决从语句 -> 中间代码的问题。
¶ 6. 代码生成+优化
- 给一个基本块
- DAG优化（局部优化）
- 生成汇编语言代码
¶ 词法分析
¶ 应试必读
词法分析器的任务很简单，就是将输入的字符串流处理为Token流，用于后面的计算。在词法分析器这部分，至少需要了解如下几个概念：
- 字符流其实就是输入的源程序，例如
int a = 20;。代码在输入到编译器的时候也是一个字符一个字符的串，包括空白符、换行符等等。 - Token可以理解为比程序中的“关键字”更宽泛的概念，例如一个变量也是Token，Token是整个编译程序工作的最小单位。词法分析器通过对原始程序的处理，获得了一系列Token，在此之后编译程序都是在处理Token的相关问题而不是字符串。
- Token是根据语言提前进行定义的，例如
if语句会是一个Token，变量声明也是Token，对于不同的Token进行处理也就是后面语法分析要进行的操作。 - 词法分析器对字符流的处理首先依靠正则表达式，也就是通过正则匹配识别程序的关键字，将其对应到Token上。
- 在正则表达式匹配的过程中，自动机是重要的工具。例如
if和int在刚读到i的时候其实词法分析器也不知道对应到哪个Token，但是知道这玩意儿会是哪些Token中的一个（或者啥都不是，报错），这个匹配的中间阶段就被称为自动机的一个状态，通过不断读取输入的字符，自动机在不同状态之间转换就能得到一个字符串最终匹配的Token。
以上描述可能有一些概念性的错误，主旨在于快速理解。需要指出的错误在这里单独列出，可以在完全学习词法分析后回来看看：
- 还没想好
在词法分析这部分，需要掌握的核心知识就是通过代码分析出最后需要的自动机。具体来讲，涉及这四个问题：
- 根据单词集得到正规集（可以由正规表达式描述的一类集合）和正规式
- 通过正规式设计NFA
- 通过NFA设计DFA
- 简化DFA
能掌握以上四个足够应对考试。
¶ 词法分析器的作用
- 扫描字符流，滤掉空白符、换行符、制表符、注释等，分离出词素，输出词法单元序列
- 将词素添加到符号表中(可选)
- 在逻辑上独立于语法分析，但是通常和语法分析器处于同一趟中
与语法分析的关系如下：
独立的词法分析器可以：
- 简化编译器的设计
- 提高编译器效率
- 增强编译器的可移植性
在词法分析部分，字符串、正则表达式、语言、自动机和词法分析器的关系如下图所示：
¶ 词法单元的模式（正则表达式）
¶ 词法单元的模式
词法分析器中包含两个要素：
- 词素 (lexeme)：源程序中一段连续的字符序列；我们感兴趣的是满足一定规则（模式）的词素，有了模式才有识别的依据。
- 词法单元 (token)：对于满足某一种模式的词素，归为一类，类名即是token名
token = ⟨token名、属性值⟩；下一阶段的语法分析器通过 token 名即可确定程序的语法结构；属性值通常用于语义分析及之后的阶段（语法制导翻译）；属性值是可选的，即可以有，也可以没有。
当一个token对应多个词素时，必须通过属性来传递附加的信息。属性值将被用于后面的语义分析、代码生成等阶段，不同的token需要不同的属性。
如何选择词法单元（通常情况下）：
- 每一个关键词给一个自己的token。
- 每一个标点符号给一个自己的token
- 将标识符归为一组，给一个自己的token
- 将数字常量归为一组，给一个自己的token
- 将字符串归为一组，给一个自己的token
- 空白符、换行符、回车符、制表符一概不予理会
¶ 正则表达式
正则表达式可以用来快速识别词法单元对应的模式。
字符与字符串相关的概念包括：
-
字母表：一个有限的符号集合。
-
串及相关术语：字母表中符号的优先序列。相关术语还包括：
- 前缀
- 后缀
- 子串：删除串的某个前缀和某个后缀得到的串。
- 真前缀、真后缀、真子串
- 子序列：从原串中删除0个或多个符号后得到的串。
串的运算有：
- 连接
- 指数运算（幂运算）
-
语言：某个给定字母表上的串的可数集合。相关运算包括：
- 并
- 连接
- Kleene闭包
- 正闭包
-
正则语言：可以用一个正则表达式定义的语言。
编程语言通常需要同时处理多种模式，即多个正则表达式，为方便起见，引入“变量”，给一些正则表达式命名，并在之后的正则表达式中像使用字母表中的符号一样使用这些名字。正则定义是如下形式的定义序列：
其中：
- ：表示一个新符号。
- 是一个正则表达式。
引入正则定义及运算符扩展的唯一目的就是使正则表达式更简洁，而其描述能力并无增强。
¶ 词法单元的识别
¶ 词法单元的识别方法
词法分析器要求能够检查输入字符串，在其前缀中找出和某个模式匹配的词素，进而获得token。这个识别过程中词法分析器可能处于若干已经确定的状态中，最终到达一个结束态获得一个对应的token。
首先通过正则定义来描述各种词法单元的模式，然后构造状态转换图（在纸上，或者在你脑海里），用程序模拟状态转换图的状态转换过程。
状态转换图由两部分构成：
- 状态：表示在词素识别过程中可能出现的情况。
- 可以看作是对前一部分字符串处理情况的总结；
- 某些状态为接受状态或最终状态，表明已找到词素；
- 加*的接受状态表示最后读入的符号不纳入词素；
- 开始状态 (初始状态)：用start边表示。
- 边：从一个状态指向另一个状态。
- 边的标号是一个或多个符号；
- 若当前状态为
s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态。
作用：词法分析器的主要代码就是模拟状态转换图的运行过程。
在词法分析中，状态表示词法分析器在处理输入字符串时所处的状态。这些状态反映了词法分析器的内部状态，例如正在识别某个词法单元的一部分，或者已经识别完整的词法单元等。通过状态转换图，可以清晰地表示词法分析器在不同状态下对输入字符的处理方式，以及状态之间的转换条件。状态转换图可以以多种形式存在于编译器中，其中两种常见的形式是：
- 图形表示：状态转换图可以在纸上画出，或者以图形的形式在计算机中呈现。在图形中，每个状态用节点表示，每条边表示状态之间的转换关系。边上标记的字符表示触发状态转换的输入字符。
- 数据结构表示：在计算机程序中，状态转换图可以用数据结构来表示。常见的数据结构包括有限状态自动机（Finite State Automaton）和状态转换表（Transition Table）。有限状态自动机是一种抽象的数学模型，可以用于表示状态和状态之间的转换关系。状态转换表是一种表格形式的数据结构，用于存储状态转换图的信息，包括当前状态、输入字符和下一个状态。
无论是图形表示还是数据结构表示，状态转换图都提供了一种清晰的方式来描述词法分析器的状态和状态之间的转换关系。通过状态转换图，词法分析器可以根据当前状态和输入字符，确定下一个状态，并根据状态转换图的定义进行状态转换。这样，词法分析器就能够逐步解析输入字符串，并识别出其中的词素。
¶ 保留字和标识符的识别
在很多时候，关键词也符合标识符的模式，导致识别标识符的状态转换图也会识别关键词。
两种解决方法：
- 在符号表中先填关键词，并指明它们不是普通标识符
- 为保留字建立独立的、高优先级的状态转换图
¶ 词法分析器的体系结构
根据前面的分析，通过设计语法及对Token的正则表达进行设计，可以得到一个状态转换图用来识别输入串的模式（也就是获得Token），而词法分析器的工作就是模拟这个根据状态转换图分析输入串所属Token的过程，因此需要从状态转换图构造词法分析器的方法：
- 变量
state记录当前状态。 - 一个
switch根据state的值转到相应的代码。 - 每个状态对应于一段代码。这段代码根据读入的符号，确定下一个状态；如果找不到相应的边，则调用
fail()进行错误恢复。 - 进入某个接受状态时，返回相应的词法单元。注意状态有
*标记时，需要回退forward指针。
¶ 词法分析器生成（有限状态自动机为主）
¶ 词法分析器的构建步骤
如前面体系结构所描述，词法分析器的构建步骤包括：
-
选择词法单元。
-
给出词法单元的正则表达式。
-
将正则表达式转换为有限状态自动机。
这一步可以手工完成也可以使用Flex等生成工具完成。
-
以有限状态自动机为基础设计词法分析程序。
有限自动机是一种偏数学的算法描述手段，它与正则表达式的关系极其密切，而token的模式恰好用正则表达式描述。很自然地，就可以以有限自动机为基础设计token 的识别过程。概括之，有限自动机是实现词法分析器的基础。
¶ 有限自动机
本质上和状态转换图相同，但有限自动机只回答Yes/No。分为两类：
- 非确定有限自动机：对边上的标号没有限制，一个符号可以出现在离开同一个状态的多条边上，可以做标号。
- 确定有限自动机：对于每个状态以及每个标号，有且只有一条边（或最多只有一条边）。
FA边上的标号也就是字母表中的符号。
两种自动机的功能是一致的，前者能识别的模式后者也一定能识别；同理亦然。
一个自动机接受的输入串，当且仅当存在一条从开始状态到某个接受状态的路径，且该路径各条边上的标号按顺序组成该串。
同理，自动机接受的语言就是从开始状态到达接受状态的所有路径的标号串的集合。
NFA的定义包括如下部分：
- 一个有限的状态集合
- 一个输入符号集合
- 转换函数
- 一个被指定的开始状态
- 一组被指定为接受状态的接受状态集合
一个NFA的示例（包括正则、NFA图和转换表）如下：
一个体现出“NFA”的例子：
其中状态“a”出现在离开状态0的两条边上。
DFA是一种特殊的NFA，他们的差异在于：
- 没有的转换
- 不会有多个离开统一状态的相同标号的边
显然，判断一个串能否被DFA接受要比NFA更高效；而且每一个NFA都有与之等价的DFA存在。
¶ 正则表达式到自动机
通过正则表达式，可以确定出一个DFA进行模式匹配，其过程包含两步：
- 正则表达式 -> NFA：Thompson算法
- NFA -> DFA
从正则表达式构建NFA的过程，基本思想是根据正则表达式的递归定义，按照正则表达式的结构，递归地构造出相应的NFA。具体来讲包括两步：
- 构造
\epsilon的单个符号的NFA - 对于每个正则表达式运算，通过组合的方法构建相应的NFA
构造过程略过，对多个NFA的合并方法如下：
- 引入新的开始状态，并引入从该开始状态到各个原开始状态的转换，得到具有多个接受状态的新NFA
- 新NFA接受的语言是原来各个NFA所接受语言的并集
- 新NFA中不同的接受状态代表不同的模式
按照Thompson算法构造的NFA都只有一个接受状态，但是合并步骤会使新NFA出现多更多接受状态。
从NFA到DFA使用子集构造法完成，这个算法包含三个函数：
| 操作 | 描述 |
|---|---|
| 能够从 NFA 的状态开始，只通过转换到达的 NFA 状态集合 | |
| 能够从中的某个 NFA 状态开始，只通过转换到达的 NFA 状态集合，即 | |
| 能够从中的某个 NFA 状态出发，通过标号为的转换到达的 NFA 状态集合 |
算法描述如下图所示：
但是子集构造法不一定得到最简DFA，如图所示：
理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。
DFA的接受状态所对应的NFA状态子集中至少包括一个NFA的接受状态。如果其中包括多个对应于不同模式的NFA接受状态， 则表示当前的输入前缀对应于多个模式，存在冲突，解决方式：找出第一个列出的这样的模式，将该模式作为此DFA接受状态的输出。
最后通过Hopcroft算法获得最小DFA。通过DFA的最小化, 可得到状态数量最少的DFA (不计同构，这样的DFA是唯一的)。
最小化DFA的基本问题是状态之间的可区分关系：
- 如果存在串，使得从状态和，一个到达接受状态，而另一个到达非接受状态，那么就区分了和
- 对于两个状态和，如果存在某个串区分了和，我们说和是可区分的， 否则它们是不可区分的
可区分状态可以理解为两个（或多个）状态根本不是一类，根据下一个输入的符号，不同状态得到的结果可能会出现不同。而不可区分状态就是，这两个（或多个）状态，无论下一个接收的符号是什么，得到的结果都是一样的。
Hopcroft算法的基本思想，要理解需要对抽象代数略作回忆：
- 发现：原DFA状态之间的“不可区分”关系满足自反、对称、传递三个性质，因此是等价关系。
- 先确定状态，首先构造新DFA的两个状态，分别对应原DFA的接受状态集合和非接受状态集合，这两个集合可能不是等价类；Hopcrof算法的目标（也是过程）就是根据每个集合中原DFA状态之间是否可区分，将之分裂，直到每个集合都成为（基于不可区分关系的）等价类为止。
- 再确定转换，即根据原DFA中状态之间的转换关系，确定新DFA状态之间的转换关系
¶ 语法分析
¶ 应试必读
语法分析器用于对前面处理好的Token流进行分析检查，例如是否符合语言文法的定义。这部分在考试中最重要并且比较难，首先需要大致了解一以下概念：
- 文法：文法用于描述编程语言的句法结构和语法规则，也就是一大堆产生式。程序设计语言通常使用的叫做上下文无关文法（CFG）。
- 语法：语法是编程语言中定义的语法规则，用于规定程序的结构和正确组织方式。语法分析器根据文法规则进行词法分析和语法分析，检查源代码的语法正确性，并构建语法树表示程序的结构，总之就是关系很大，但语法指的通常更抽象一些。
- 语法解析树：对于前面的Token流，根据文法可以解析出来一个具有层次关系的结构，这个结构就被称为解析树。
- 自上而下和自下而上方法：两种不同的构建解析树的思路。
采用自上而下方法的分析技术主要有两种：
- 递归下降法
- LL（1）
自下而上的方法有：
- LR(0)
- LR(1)
- SLR(1)
- LALR(1)
不同的分析技术需要不同的工具以实现功能，并且对语言的描述能力也存在差异。对于应试，至少需要掌握以下技能：
- 写文法（也就是写正则表达式）
- 构造LL(1)文法的分析表
- 构造LR(0)文法的分析表
- 了解SLR文法
¶ 语法分析器的作用
¶ 上下文无关文法
上下文无关文法（Context-Free Grammar，CFG）是一种形式语言描述工具，用于描述上下文无关语言的语法结构。它是计算机科学中的一种形式化的表示方法，广泛应用于编译器设计、自然语言处理和人工智能等领域。上下文无关文法由四个元素组成：
-
一个非终结符集合
-
一个终结符集合
-
一个产生式规则集合
-
一个起始符号。
其中，非终结符表示语法结构的符号，终结符表示语言中的实际词汇，产生式规则定义了语法结构的生成规则，起始符号表示语法结构的起点。
上下文无关文法的生成过程是通过不断地应用产生式规则来替换非终结符，直到最终得到一个只包含终结符的字符串，即语法结构的句子。这个过程可以看作是一个推导过程，其中每一步应用的产生式规则被称为推导步骤。
上下文无关文法可以表示一类语言，称为上下文无关语言。这类语言在形式上具有简单的结构，不依赖于上下文信息，因此被广泛应用于描述自然语言的语法结构和编程语言的语法规则。常见的编程语言如C、Java和Python都可以用上下文无关文法来描述其语法结构。
推导是指将非终结符替换为它的某个产生式的体一次替换，连续多次替换也称推导。语法分析树就是推导过程的图形表示。推导和解析树是多对一的，给定文法和某个句子，可能有多个推导对应一棵解析树，例如：
解析树无法捕捉推导所采用产生式的先后次序，但这不是问题，反而是优点，因为我们的最终目标是确定程序的结构，而推导过程本身并不是语法分析的最终目标。
根据推导的顺序可以将推导分为最左推导和最右推导：
- 最左推导
- 最右推导
二者和解析树都是一对一的，其中最右推导及其对应的最左规约也被称为规范推导和规范规约。
¶ 消除二义性
通常要求程序设计语言的文法是无二义性的，否则就会导致一个程序有多种“正确”的解释。即使文法看似允许二义性(以方便文法或语法分析器的设计)，但仍需要在文法之外加以说明，来剔除不要的语法分析树。
二义性有两个主要的来源：
- 算术表达式（算符结合性二义，算符优先级二义）
- 悬空else（dangling else，else与哪个then匹配二义）
消除二义性的两个主要方法：
- 改写原文法（rewriting）
- 引入消除二义性的规则（disambiguating rule）
¶ 消除左递归
左递归是指在产生式规则中存在直接或间接地将同一非终结符作为产生式右侧的第一个符号的情况。例如，对于产生式 ，其中 是非终结符， 是由终结符和非终结符组成的符号串，就存在左递归。
左递归可能导致语法分析过程中的无限循环或者无法终止，从而使分析器陷入死循环。这是因为在尝试匹配左递归产生式时，分析器会不断地展开同一非终结符，而无法向后推导到其他的产生式规则。
为了消除左递归，可以采取以下步骤：
-
检测左递归：对于每个非终结符 ，检查其产生式规则中是否存在以 开头的产生式右侧。如果存在，则存在左递归。
-
消除直接左递归：对于存在直接左递归的非终结符 ，可以通过引入新的非终结符来消除左递归。具体步骤如下：
- 将所有以 开头的产生式规则拆分为两组：一组是直接左递归的规则，另一组是非左递归的规则。
- 对于直接左递归的规则，创建一个新的非终结符 ，将这些规则中的左递归部分替换为 。同时，添加一个新的产生式规则 ，其中 是直接左递归规则中的非左递归部分。
- 对于非左递归的规则，将其末尾添加新的产生式规则 ，其中 是原始规则的右侧部分。
-
消除间接左递归：如果存在间接左递归，即存在形如 和 的产生式规则，可以通过以下步骤消除间接左递归：
- 为每个非终结符 创建一个新的非终结符 。
- 对于每个存在间接左递归的规则 ，将其替换为 。
- 对于每个存在间接左递归的规则 ，将其替换为 。
以下为一个简单的消除直接左递归的例子：
通过消除左递归，可以确保语法分析过程的终止，并且得到一个等价的无左递归的文法。这样的文法更适合用于自上而下的语法分析方法，如递归下降分析和LL(1)分析。
¶ 自顶向下的语法分析技术
自顶向下的语法分析技术基本思想就是沿着根到叶的方向构造解析树，直到构造出符合要求的语法解析树，否则报错。如下图所示，自顶向下的分析算法大致有如下几种：
¶ 回溯算法
回溯算法的核心思想是通过递归地尝试不同的产生式规则来匹配输入字符串。算法从文法的起始符号开始，根据当前输入符号和产生式规则，选择一个规则进行推导。如果选择的规则无法匹配当前输入符号，算法将回溯到上一个选择点，尝试其他的规则。这个过程会一直进行，直到找到一个匹配的规则或者所有的选择点都被尝试完。
回溯算法在自上而下的语法分析中被广泛应用，例如在递归下降分析和LL(1)分析中。递归下降分析是一种基于产生式规则的递归函数调用实现的语法分析方法，回溯算法可以用于选择适当的产生式规则。LL(1)分析是一种预测分析方法，回溯算法可以用于处理分析表中的冲突或者错误。
回溯算法有两个主要缺点：
- 对某些文法，算法会陷入无限循环（或递归）-> 需要消除左递归
- 对于简单文法尚可应付，对于复杂文法，往往因频繁回溯，耗时过多，从而不堪用；特别地，若输入有语法错误，最坏时间复杂度是指数级的 -> 引入预测分析算法
¶ 预测分析技术与LL(1)文法
基本思想：采用深度优先策略构建解析树，每次为非终结符号选择适当的产生式，以避免回溯。具体实现上通过向前查看输入中的一个或多个尚未被匹配的终结符来选定产生式。
对于非左递归文法，因不再回溯所以速度更快；但是仍存在无法处理的文法。
考虑通过向前查看一个输入符号就能用预测分析算法解析的文法：人们将这类文法定义为LL(1)文法。一个文法是LL(1)文法的充要条件是每个非终结符A的两个不同产生式满足。
其中第一个“L”表示从左向右扫描输入，第二个“L”表示最左推导，“1”表示只需要看一个输入符号。这个命名规则在后面同样适用。
要进行这样的预测就需要语法分析表，构建语法分析表的过程需要和两个函数的辅助，二者都可以辅助选择合适的生成式：
- ：可以出现在导出的句型的开头的终结符的集合；如果，那么也包含在中。
- ：可能在某些句型中紧跟在右边的终结符的集合。
¶ 递归下降算法
¶ 求first(x)
- 如果X是一个终结符，那么
- 如果X是一个非终结符，且，那么如果对于某个,在中且在所有的中，那么把加入中
- 如果，那么把放入中
¶ 求串的first
对于串
-
向中加入中的所有非符号
-
如果在中，那么把加入中所有非符号加入......以此类推
-
最后，如果对于所有的，在中，那么把加入
¶ 求FOLLOW集
不断应用以下规则，知道没有新的终结符可以加到任何FOLLOW集合。
- 将放入中，其中S是开始符号，是输入右端的结束标记
- 如何存在一个产生式，那么中所有非符号都在中
- 如果存在一个产生式，或存在且包含，那么中的所有元素都在中这里说明了一种FOLLOW(B)对于FOLLOW(A)的依赖关系
求FOLLOW的过程是不断更新的过程，FOLLOW集直接有依赖关系，如果后面一个FOLLOW集更新了，那么所有依赖他的FOLLOW集都需要更新。可以在他们之间建一条边，说明这种依赖关系。
¶ 求SELECT集
对于一个产生式，求
- 若，那么
- 若，那么
¶ 文法的等价变换
确定的自顶向下分析要求给定语言的文法必须是 LL(1)的形式，所以如果一个文法不是LL(1)文法，需要先进行转换。
-
提取左公因子
当一个文法中含有产生式时，，就不符合LL(1)文法的条件
所以需要提取公因式。
对提取公因式
如果还有公因式，就继续提取。
-
消除左递归
a) 将间接左递归转为直接左递归
例如，若有，，说明存在间接左递归。
将的产生式带入转化为直接左递归
b) 消除直接左递归(将左递归改写成右递归)
若有产生式，那么转化成，
更一般的情况
¶ 自底向上的语法分析技术
¶ LR文法概述
LR文法分析的过程要一句LR分析表进行。还需要维护一个状态栈和符号栈。
- 对于action表中的某一列a的sn，表示将符号a、状态n入栈
- 对于action表中的rn表示使用第n个产生式进行规约。
分析过程（可能比较抽象，但是思路不难）
注意，每次都是用状态栈的栈顶状态与剩余输入的第一个在action表中进行转移。
-
情况一，如果action表中给出了sx的答案，表示不需要规约，那么只要将新状态x入栈，将字符a入栈即可。
-
情况二，如果action给出了rx的答案， 说明需要规约，那么就按照产生式进行规约，规约之后状态栈会比符号栈少一个字符，然后再GOTO表中按照状态栈顶和符号栈顶求出一个状态，压入状态栈顶中。
-
情况三四，如果转移到了acc，说明完成了，如果转移到了err说明错误了。
¶ LR(0)分析法
LR(0)提供了一种构造分析表的方法。
¶ LR(0)项目
右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目。例如
同属于一个产生式的项目，如果圆点的位置只相差1，那么后者是前者的后继项目。例如的后继项目是。
¶ 等价项目
当一个项目的圆点后面是非终结符的时候，那么他就存在等价项目，例如与就是一个等价项目。因为第一个项目的圆点后面是，所以作为左部的产生式中，所有以圆点开头的都是他的等价项目。所有等价项目构成一个等价闭包
¶ 构造LR(0)自动机
如图所示，从初始状态开始，对于每个项目，都求一下后继项目，然后连一条边到那个项目的等价闭包。最后可以构建出如上图的自动机。
¶ 构建分析表
由上面的自动机可以构建出分析表。方法就是行上列出所有状态号，列上，终结符放入action中，非终结符放入GOTO中。可以构建出如下的分析表
¶ 冲突
LR(0)文法是存在冲突的
如图，这个状态，第一个项目认为是一个结束状态，可以规约了，但是第二个状态认为还可以接收*。这样就导致了移入/归约冲突。同样的还存在归约/归约冲突，就是同一个闭包中，两个状态希望规约到不同的非终结符。
¶ SLR文法
面对上面LR(0)中的冲突，我们可以进行改进得到SLR文法。方法就是在构建分析表时，根据产生式左部的follow集进行归约。
反省一下之前LR(0)文法时，如果一个状态可以归约了，那么不管他剩余输入的第一个字符是什么，都进行规约。
在SLR文法中，根据剩余输入的第一个，采取不同的规约动作。
如上图，中，存在规约/规约冲突，观察B的follow集，只有d，所以在ACTION中，当待输入符号的第一个是d的时候，用第四个产生式进行归约，同理，当剩余输入的第一个是b和$的时候，采用第二个产生式进行输入。
限制：要求一个项目闭包中，归约项目的左部的follow集与移进项目的剩余输入的首字符不相同。
¶ 语法分析器生成工具
¶ 语法制导翻译
语法制导翻译的基本思想在于为CFG中的文法符号设置语义属性，以表示其对应的语义信息。对于语义属性的计算，需要由语义规则来给出规定。
在制定与执行语义规则上，提出了语法制导定义（SDD）和语法制导翻译方案（SDT）。
¶ 语法制导定义（SDD）
SDD是对CFG的推广，将每个文法符和一个语义属性集合相关联。
将每个产生式和一组语义规则相关联，这些规则用于产生该产生式中各文法符号的属性值。
如果是一个文法符号，是的一个属性，则用表示属性在某个标号为$X 的分析树结点上的值。
¶ 综合属性
在分析树上结点N的综合属性通过N的子节点和N本身的属性值来定义。
例如对于产生式，综合属性对应的语义规则可以是。
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则。
¶ 继承属性
在分析树上N结点的继承属性只能通过N的父节点、兄弟节点或者N本身的属性值来定义。
终结符没有继承属性，终结符从词法分析器处获得的属性值被归为综合属性值。
在上面这个SDD就是一个带有继承属性的SDD。首先根据产生式(1)对应的语义规则，得到了最上面的，然后根据产生式(4)对应的语义规则，得到，然后同样的道理依据产生式(4)得到
¶ 属性文法
在SDD中，副作用是指在语法规则的语义动作中对属性进行修改或操作的行为。一个没有副作用的SDD也称为属性文法（在属性文法的语义规则中，仅仅通过其它属性值和常量来定义一个属性值）。
副作用可以改变属性的值，更新符号表、计算表达式的结果等。副作用的一个常见示例是在语义动作中更新符号表，当遇到变量声明时，可以通过语义动作将变量添加到符号表中，并分配内存空间。
其实这与纯函数编程中对副作用的定义应该是相似的，有待考证。
例如：
¶ SDD的计算顺序
SDD为CFG中的文法符号设置语义属性。对于给定的输入串，我们将应用语义规则，计算分析树中各结点对应的属性值。SDD声明了语法分析树上属性之间的依赖关系，按照这种依赖关系的拓扑排序可以确定他们的求值顺序。
依赖图是一个有向图，它描述了分析树中结点属性之间的依赖关系。一个依赖关系图有拓扑排序的充要条件是无环。一个依赖图的示例如下所示：
一般说来，给定一个SDD，很难确定是否存在某棵语法分析树，但是，**S-属性定义（S-SDD）和L-属性定义（L-SDD）**一定存在一个拓扑排序，并且这两类SDD可以和自顶向下和自底向上的语法分析过程一起实现。
¶ S-SDD
仅仅使用综合属性的SDD称为S属性的SDD，也叫S-属性定义，S-SDD。
例如：
这里面所有属性均是综合属性，都是根据子构造的属性 计算出父构造的属性，所以可以自底向上的计算每个属性。
¶ L-SDD
L-属性定义，也叫L属性的SDD或者L-SDD。
一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式，其右部符号的继承属性仅依赖于下列属性：
- A的继承属性
- 产生式中左边的符号 的属性
- 本身的属性，但 的全部属性不能在依赖图中形成环路
所以对于L-SDD，所有的分析树属性都依赖于左边或者下边的节点。所以不会存在环路。
每个S-属性定义都是L-属性定义
¶ 语法制导翻译方案（SDT）
SDT是在产生式右部嵌入了程序片段的CFG，这 些程序片段被称为语义动作。按照惯例，语义动作放在花括号内，如下图所示：
SDT可以看作是对SDD的一种补充，是SDD的具体实施方案；它明确指明语义规则的计算顺序，说明实现细节。
¶ 抽象语法树（AST）
¶ 中间代码生成
真几把难。
¶ 中间代码表示方式
中间代码是位于源语言与目标语言之间的一种表示形式，通过中间代码可以使不同的源语言、不同的机器之间得到不同的编译器组合。而不用为每一种组合都写一个编译器。
中间代码的表示形式有后缀表达式、图形表示、三地址编码三种方式
¶ 后缀表达式
后缀表达式也叫逆波兰表达式，是把运算符放到运算元素后面的一种表示形式，这种方法无需使用括号。
例如写作。写作
¶ 图形表示
中间代码的图形表示方法分为语法树和DAG两种。
-
语法树刻画了源程序的自然层次结构，适用于静态类型检查。
-
DAG与语法树类似，但是DAG表达会更见简洁，他会合并公共的部分。
¶ 三地址表示
三地址表示是语法树或者DAG的线性表示形式。
三地址代码中包含地址和指令。
每条指令的右侧最多只有一个运算符。三地址代码的名字对应于语法树的内部节点。
三地址代码适用于目标代码的生成和优化。
三地址指令：
- x = y op z
- x = op y
- x = y
- goto L
- if x goto L 或者 if false x goto L
- if x relop y goto L
- x = y[i] 或者 x[i] = y
- x = &y, x = *y, *x = y
三地址代码的表示方式
-
四元式
op, arg1, arg2, result
-
三元式
op, arg1, arg2
表达式的DAG表示和三元式式等价的
-
间接三元式
¶ 代码优化
¶ 基本块
基本块是满足下列条件的最大的连续三地址指令序列。
- 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
- 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机
基本块中的只能怪要么全都执行，要么全都不执行。基本块的第一条指令叫做基本块的首指令。
划分基本块的方式：
首先确定首指令的位置，首指令有以下三种
- 指令序列的第一个指令
- 条件或者无条件调转语句的目标指令
- 紧跟在一个条件或者无条件转移之后的指令。
然后每个首指令对应的基本块包含了从他开始一直到下一个首指令（不含）或者指令结尾的位置。
¶ 流图
流图的节点是一些基本块。
从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行。
确定边的方式
- 有一个从B的结尾跳转到C的开头的条件或者无条件跳转语句。
- 按照原来的三地址语句序列中的顺序，C紧跟在B之后，且B的结尾不存在无条件跳转语句
如下图，左边的三地址指令序列可以得到右侧的流图，然后将代码填入的右侧的框图中。
¶ 优化方法
优化方法分析全局优化和局部优化
全局优化包括：
- 全局公共子表达式
- 复制传播
- 死代码消除
- 代码移动
- 归纳变量
- 强度削减
局部优化包括
- 局部公共子表达式
- 消除死代码
- 代数恒等式
- 数组引用
- 指针赋值
- 过程调用
¶ 删除公共子表达式
很多中间代码可能是进行了相同的计算，所以可以把重复的部分删除。
公共子表达式
如果表达式先前已经被计算过，并且从先前的计算到现在，中变量的值没有改变，那么的这次出现就称为公共子表达式。可以删除掉公共子表达式，并把所有用到公共子表达式的地方，替换成他第一次出现的地方的临时变量。
如上图，和出现了两次，可以把后面用到的替换成，换成。
效果如下图
如果出现的两次位于同一个基本块中，那么就是局部公共子表达式，否则是全局公共子表达式。上面就是一个局部公共子表达式的例子，下面是一个全局公共子表达式。
如上图，与中的，与中的属于公共子表达式，这就是全局公共子表达式。
同理中的许多公共子表达式也是可以删除的。删除后结果如下：
是不能被替换为的，因为在被赋值之后，可能会进入再进入，而在中包含对于a的赋值语句。
¶ 复制传播
在优化的过程中可能会产生大量的复制语句。
形如u = v的复制语句使得语句后面的程序点上u的值等于v的值
-
如果在某个位置上u一定等于v，那么可以把u替换为v
-
有时可以彻底消除对u的使用，从而消除对u的赋值语句
复制传播本省并不是优化，但是他给其他的优化提供机会
¶ 死代码删除
如果一个变量在某个程序点上的值在之后可能被使用，那么这个变量在这个点上就是活跃的，否则就是死的。此时对于该变量的赋值就是没有用的死代码，可以删除。
死代码多半是因为前面的优化导致的。
比如在复制传播时，对于赋值语句，将后面所有用到的地方都用代替，这可能会导致不再被引用，所以就会成为死代码
¶ 代码外提
循环中的代码可能会执行很多次，如果循环的同一次运行的不同迭代中，表达式的值不变，那么可以在循环入口之前计算这个不变的表达式，减少在循环中的计算。
代码外提是循环优化的一种
例如：
¶ 强度削减和归纳变量
强度削减：用较快的操作替代较慢的操作，例如用加替代乘法
归纳变量：对于一个变量x，如果存在一个正的或者负的常数c使得每次x被赋值时他的值总是增加c，那么x就称为归纳变量
归纳变量可以通过每次在循环迭代中进行一次简单的增量运算（加法或者减法）来计算。
例如
¶ 基本块的优化
基本块优化也叫局部优化
¶ 活跃变量
如果一个变量的值在某个程序点之后可能会被用到，那么就说这个变量在这个程序点是活跃的。
¶ 基本块的DAG表示
基本块的DAG表示对于局部优化有很好的效果。DAG图可以反应变量及其值对其他变量之间的依赖关系。
DAG的节点定义和构造方法如下：
-
DAG中的每个非叶子节点N对应一个三地址指令s，N的标号是其对应三地址指令中的运算符。N同时还关联了一组变量，这些变量表示s是这个基本块中最晚对于这些变量进行定值的语句。
-
对于一个基本块，从上到下依次扫描其三地址指令，对于指令$x=y\ op\ z opxy,z$所关联的节点。
-
对于指令，假设关联到N，那么x也关联到N。
-
扫描结束后，对于所有在出口处活跃的变量x，将关联的节点设置为输出节点。
例子：
对于基本块
a=b+c
b=a-d
c=b+c
d=a-b
其DAG状态依次如下，
首先处理a=b+c得到
然后处理b=a-d，这里注意，如果在处理某个变量的时，这个变量已经存在与某个节点关联的符号表中，那么需要从此符号表中删除这个变量，例如，下图中需要删除叶子节点中关联的节点。
然后处理c=b+c，同样的，需要从叶子节点中删除
最后处理d=a-d，发现已经存在这个表达式，就是b。所以直接把d加入到b所在的节点中即可。
¶ 局部公共子表达式
其实上面的例子已经用到了局部公共子表达式的使用。在DAG图上，如果需要新加的一个节点M，他的两个子节点与之前的某个节点N具有相同的运算符和子节点，那么就不需要生成新的子节点，直接用N代表M即可。
¶ 消除死代码
在DAG图上消除没有附加活跃变量的**根节点。**就是消除死代码。
如下图，如果c,e不是活跃变量，那么就可以删除标号为e,c的节点。
¶ 基于代数恒等式的优化
-
消除计算步骤
-
局部强度削减
-
常量合并
例如2 * 3.14可以替换成6.28