编译原理知识汇总

编译原理

文章目录

• 编译原理

• 引论

• • 编译程序
  • 编译过程
  • 编译程序的结构

• 高级语言及其语法描述

• • 文法和语言
  • 文法和语言的形式定义

• 词法分析

• 语法分析

• 语义分析

• 中间代码生成

• 代码优化

• 目标代码生成

• 总结

引论

编译程序

在计算机上执行一个高级语言程序通常分为两个步骤:首先,通过编译器将高级编程语言转换为底层机器代码;其次,这些生成的机器代码被用来计算最终的结果。

编译程序 : 一般而言,人们所指的翻译程序即为这样一个系统,它能够将某一特定领域的知识表示为计算机可处理的形式,并将其转化为另一种形式以供计算机执行相应的操作,而这种转化过程从逻辑角度看与原始知识表示具有等价性。

如果将源代码视为诸如FORTRAN、Pascal、C、Ada、Smalltalk或Java等'高级编程语言'而目标代码则被视为诸如汇编指令或机器指令等'底层编程工具'的情况下，则实现这种将源代码转换为目标代码的过程则被称为编译程序

解释程序 : 作为处理该语言源代码的独特机制存在的一种软件系统，在接受该语言编写的源代码作为输入时，并不会生成最终的目标代码文件；相反地，在运行过程中同步解析并执行原始代码内容这一特性使其具备动态交互能力。其中包含了许多基于编译器原理构建和优化这些系统的通用方法论基础。

编译过程

编译器的工作流程通常包括词法分析、语法分析、中间代码转换以及若干核心环节及目标编码部分的生成等主要步骤，并在这一过程中还需要进行表格处理以及错误检测。

如果编译程序生成的目标实体是机器代码程序 ，则源代码的执行将划分为两个部分：机器级优化与链接操作 和其他相关操作 。若目标应用采用汇编语言，则源代码的操作步骤将分解为三个部分：机器级优化与链接操作 、汇编级处理流程 和其他相关操作 。

编译程序的结构

高级语言及其语法描述

文法和语言

语法规则 是一种系统或一套规范，并且不仅用于生成符合语法的程序，并且还可以用于评估某个程序是否符合特定语言规范。

程序设计语言的语义包括静态语义 和动态语义 。

• 静态语义由明确的限制条件构成，并用于判断哪些合法程序是正确的；
• 动态语义被称作语义或执行语义，并说明程序需要完成的任务以及如何进行处理。

文法的概念 : 描述语言的语法结构的形式规则

• 文法是阐述语法的一个工具

字母表-符号集：是字母的有穷非空集合。

符号串—字母表的符号组成的任何有穷序列。

空符号串：用ε表示，长度为0（不含任何符号）

符号串的连接：

设x，y是符号串，连接xy是y符号写在x符号之后。

例：x=ab, y=MN 则xy=abMN

符号串的方幂：

设x是符号串，则z=xx……xx，称z为x的方幂,

记z=x^n。

因此 x^0=ε, x^1=x, x^2=xx, x^3=xxx

显然n>0时, 有x^n =x·x^{n-1} ＝ x ^{n-1}·x

符号串的集合：

若集合A中的全部元素均为给定的字母表上的符号序列，则称A为该字母表上的符号序列集合。

​ 两个符号串集合A、B乘积定义：

​ AB=\{xy| x∈A且y∈b\}

例：A={a,b}，B={c,d}

则AB= \{ac，ad，bc，bd\}

闭包（∑^*）

字母表∑，用∑^* 表示∑上所有有穷长的串集合，∑^*称为∑的闭包。

例：字母表∑={0,1}

则∑^*=\{ε,0,1,00,01,10,11,000,001,010……\}

​ =∑^0∪∑^1 ∪ ∑^2∪. …∪∑^n

正闭包(∑+)

∑^+ =∑^1 ∪ ∑^2∪. …∪∑^n

∑^+称∑的正闭包。

显然：∑^*＝ ∑^0∪∑^+

​ ∑^+ ＝ ∑∑^*＝∑^*∑

文法和语言的形式定义

产生式(规则、重写规则、生成式)

形如\alpha \rightarrow \beta (\rightarrow的叫法：“定义为”)

a 称规则的左部，β称规则的右部。

注意: \rightarrow : 表示"定义为" ; 而 \Rightarrow : 表示"推导" , 用于语法分析中。

文法定义 : 描述语言语法结构的形式规则

文法G 定义为四元组 (V_N, V_T, P, S)

V_N：非终结符号集（一般用< > 或大写字母表示）

V_T ：终结符号集 ，不能分割，即单词符号

P ：产生式（规则）

S ：识别符号或称产生式，在生成规则中通常出现在左边，并且必须在至少一个这样的生成式中位于左边

​ 规定：（1）V_N ，V_T，P是有穷非空集合；

​ （2）V_N∩V_T＝\emptyset （不含公共元素）

注意：通常而言，在计算机科学领域中使用希腊字符来表示"earth"或其他类似概念（world）。这表明这些字符既可以作为终结符使用（例如像$这样的标记），也可作为非终结符（如像@这样的标识）。此外，在文法理论中这些符号通常被用来表示任意的字符集合或是由多个字符组成的字符串

直接推导的定义

\alpha \rightarrow \beta 是文法G=（V_N ，V_T ，P，S）的规则，

\gamma 和 \delta 是V^*中的任意符号，若有符号串V，W满足：

V= \gamma \alpha \delta ，W＝\gamma \beta \delta 则表示V被\gamma, \alpha, \delta所共同决定或W是由\gamma, \beta, \delta共同导致的结果, 进而可理解为\textbf{W由V被\gamma, \alpha, \delta共同决定}**, 并以符号形式记录为 V\Rightarrow W$.

​ 若存在直接推导的序列：

​ V=W_0 \Rightarrow W_1 \Rightarrow W_2 \Rightarrow … W_n ＝W (n>0)

​ 则称V推导W (或W规约到V) ，记 V \stackrel{+}{\Rightarrow}W (一步或若干步推导)

如果V \stackrel{+}{\Rightarrow}W ，或者V = W，则表示为 V \stackrel{*}{\Rightarrow}W（零步或若干步推导）。

句型的定义

设G为一个文法,S作为起始符号, 当 S \stackrel{*}{\Rightarrow} \alpha时, 我们称\alpha为一个句型. 仅由终结符构成的句型即被视为一个句子.

​ 句子一定是句型，句型不一定是句子

状态转换图的功能：识别（接受）一定的符号串（单词）

状态转换图的程序实现的思路：为每个状态结点都编写一个子程序

字母表的概念：一般用∑表示

闭包的概念：闭包V*中的每个字都是由V中的字经过若干次连接而成的

正则闭包V+的概念：是V上所有符号串的集合

∑^* (闭包)定义：表示∑上所有字的全体，空字ε也包括在其中

∑^+ : (正闭包)空字ε不包含，非ε

ε，{ }，{ε}之间的区别

ε所对应的正规集为{ε}

正规式与正规集的定义：知道如何用正规式表示一个正规集

简述NFA和DFA的定义与区别

若M中存在一些节点既是初始状态也是终止状态，并且存在这样的情况：从一个初始状态到一个终止状态有一条由ε组成的通路，则空字ε可用于M中。

正规式与优先自动机的等价性

定理2.对于∑上的每一个正规式V，存在一个∑上的DFA M，使得L(M)=L(V)

DFA M的化简涉及其定义及其操作流程：区分终态与非终态的能力各异，并因这一差异而存在本质区别——这是因为终态具备识别空字符串ε的能力而非性端不具备这种能力

构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串

词法分析

1.状态转换图的功能： 识别（接受）一定的符号串（单词）

此图表是一个相当简单的状态迁移图。此图表表明：从状态0经X弧转移至状态1，并经Y弧转移至状态2

2. 字母表 的定义：包含有限个字符或记号的集合∑被称为某个形式语言的字母表

例： ∑ = {a , b , c}

​ 元素：a，b，c

字母表中的字符可以连接在一起组成一个序列,例如: aa, ab, bc, bbc 等; 不同的顺序决定了不同的序列.

不包含任何字符的序列称为空字，用ε来表示

另外有几个概念必须先了解：

字(符号串)的连接

设x和y是两个字(符号串)，则定义xy为他们的连接

例：ab和ba连接是abba

注: (1) ε（空字）是连结运算的恒等元素εx = xε= x

​ (2)字(符号串)的n次连接

​ x^n = xxx…x

​ 规定x^0 = ε

​ x^1= x，x^2=xx，x^3= xxx

集合的(连接)积

设U和V是两个“字(符号串)的集合，

则定义UV为他们的(连接)积

​ UV={xy|x∈U且y∈V}

例：设U={a, ab}, V={b, ba},

则UV=\{ab, aba, abb, abba\}

集合V的n次(连接)积记为：

​ V^n = V V V…V

​ n个 V

​ 规定 V^0= \{ε\}

例：设V={a, b}，那么

​ V^0= \{ε\}

​ V^1= \{a,b\}​

​ V^2=VV=\{aa,ab,ba,bb\}​

​ V^3=VVV=V^{2}V=\{aaa,aba,baa,bba,aab,abb,bab,bbb\}

3. 闭包的概念 ：

设V是一个字（符号串）的集合，

则V的闭包定义为V*，

​ V* = V^0∪V^1∪V^2∪…

注：闭包V* 中的每个字都是由V中的字经过有限次连接而成的

正则闭包V^+的定义为

​ V^+ = VV^*

闭包与正则闭包的主要区别在于前者包含空字ε。这是因为前者包括了集合V^0的原因。而正则闭包是在这种情况下附加了一个V的结果。

∑^*定义：表示∑上所有字的全体，空字ε也包括在其中

∑^+表示∑​上所有字的全体，但不包括ε

4. ε，{ }，{ε}之间的区别

ε 空字：表不包含任示何字符的序列称

{ }：表示一个空集

{ε}： 表示含有空字ε的集合

5.正规式与正规集 的定义：

将具有相同特征的字归为一类形成一个集合，并称之为正规集；随后采用一种形式化的表示方法来描述这个集合被称为正规式

• 正规式是描述单词结构的一种形式；
• 正规集是该类单词的全集。

举例

对于下面的案例,应该认真分析接下来四个方面的含义,这对解答大题非常有帮助。在解答大题时,遇到的实际问题往往需要我们将其转化为规范集合,然后用正则表达式表示出来,这样才能顺利开展后续步骤。

ε所对应的正规集为{ε}

6.简述有限自动机NFA和DFA的定义与区别

NFA代表非确定的有限自动机；DFA代表确定的有限自动机

所谓有限自动机实际上并不是真实存在的机器 只是作为一种数学模型存在 简单来说类似于函数和数列等都属于数学模型范畴 利用函数表达式能够实现其功能 当输入自变量时 能够根据给定的函数表达式计算出相应的因变量值 而有限自动机则是基于状态转移图来进行功能处理 当提供初始状态以及一个输入符号时 能够将系统从当前的状态转移到指定的状态 这种机制能够模拟计算机的基本识别过程

下面简单介绍一下DFA（确定的有限自动机）的五元式表示法：(重要)

定义：一个确定有限自动机（DFA）M是一个五元式：

M = (S, ∑, f, S_0, F)​，其中

S是一个有限的状态集合，它的每个元素我们称为一个状态

∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符

f是从 S×∑ →S的单值部分映射

S_0是S的一个元素，为初始状态，它是唯一的

状态集合F是终止状态的集合，它是S的子集(可空)

一个非确定有限自动机（NFA）

M是一个五元式 : M = (S, ∑, f, S_0, F)，其中

⑴S是一个有限的状态集合，它的每个元素我们称为一个状态

⑵∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符

该函数f: S×∑^* ↦ 2S为一个部分映射关系，在此定义域内f并非双值对应（即M不是确定状态）

⑷状态集合S_0是初始状态集合，它是S的子集

⑸状态集合F是终止状态的集合，它是S​的子集

注：DFA和NFA的区别在于（3）和（4），其他几点都差不多，要记住他们的区别和联系

7. DFA的识别功能

对于∑^*中的每一个α来说，在存在一条从初始状态节点通向某一个最终状态节点的道路时，并且这条路上的所有标记符号连接起来形成与α相同的字符串，则该字符串可以通过DFA M被识别（接受或读取）。

如果图M中有某些节点同时属于初始状态和终止状态，并且存在一条从某个初始状态到某个终止状态的ε路径，则空字ε可以被图M识别

8.状态转换图的分裂规则（大题步骤）

例子：(这里Y有两个圈圈代表他是最终状态的点)

划到最后要求每条弧上都只有一个字母或者数字

9. ε\_CLOSURE(I)​​​ 和 I_a =ε\_CLOSURE(J)​​的构造方法（大题步骤）

这里先需要了解几个定义

我们假设有某个状态集I，这个集合中含有不同的状态。

定义1 状态集I的a弧转换：

move(I,a)表示为从I中的各个状态通过每条a弧所到达的所有状态集合。

定义2 状态集I的ε(空字)闭包：

• ε\_CLOSURE(I)是一个状态集, 由两个组成部分构成:
• 状态集I中的全部初始状态。
• 从I中的任一状态出发经过若干条ε弧, 可达的所有状态集合。

定义3 I_a =ε\_CLOSURE( move( I, a ) )是一个状态集。

下面给出一个实例：

例：有如下一个状态转换图假定 I={1, 2}，求Ia = ？

J=move(I,a)={5,4,3}

I_a=ε\_CLOSURE(J) = \{5,4,3,6,2,7,8\}

（即先做a弧转换，将求得的状态再求空字闭包）

10.如何用子集法将非确定的有限自动机确定化（大题步骤）

方法：先画一张表

1.这张表的首行上首列上固定是大写字母I

在表格中存在若干列数，在这种情况下其数值多少直接决定了表中的列数。当有限自动机具有n个不同的输入符号时，则表中共存在n列。我们定义I_a I_b中的下标a和b分别表示该有限自动机所接受的所有不同输入符号。

在这一位置上是恒定的，在这一位置上是恒定的位置参数值也保持不变，在这一位置上的值同样保持不变。其中 S_{\text{init}}} 表示该有限自动机的初始状态，在本系统中我们假设所得到的状态集合被命名为 A

4.将A所对应的I_a I_b 分别求出来，我们假设是B和C

5.如果B和C都分别于A不同，需要将B，C作为新的状态集合加入到第一列中

接着求出B和C所对应的I_a I_b ，随后再次检查：针对DEFG这四个状态集合是否存在与ABC不同的情况？如果有，则将其添加到第一列下方的位置；如果发现其与之前的ABC一致，则无需进行后续计算。

接着求出B和C所对应的I_a I_b ，随后再次检查：针对DEFG这四个状态集合是否存在与ABC不同的情况？如果有，则将其添加到第一列下方的位置；如果发现其与之前的ABC一致，则无需进行后续计算。

采用该方法持续下去,直到第一列中没有新增的状态集合为止,则表格即可完成构建.

8.再画一张表，与上面的表相对应

| 0
1
2
3
4
| 1
3
4
2
…
| 2
4
3
1
…
||

就其构造而言, 上述表格显得非常简便. 此外, 大家也可以选择将其直接标注在原有的表格中而不必另作一张.

该表格的来源为：在原有表格的第一列中依次添加s01234……其中a和b保持不变。随后根据第一列中的数值对应的状态集合，在后续的各列中标注相应的数值。例如，在第一列中若出现B，则将其标记为1；若出现C，则标记为2；依此类推完成后续标注工作。

绘制该表格并对其加以标注后, 即可按照此表格绘制相应的状态转换图. 例如, 在0状态下通过a弧可转至1状态, 通过b弧可转至2状态; 在1状态下通过a弧可转至3状态, 通过b弧可转至4状态, 以此类推. 完成该状态转换图后, 即可实现一个非确定有限自动机的确定化过程.

11.有限自动机DFA的化简

整体的思路如下：

按照第10步所得出的确立DFA的所有状态进行分类处理，并将其划分为两组：一组为明确标记的状态（即终止状态），另一组则未被标记（即非终止状态）。此外，在上一步骤构建的表格中，请特别关注s这一列中的节点属于哪一类（终止或非终止）？这取决于最初正规式所设定的那一类状态特征。例如，在下面所示的情况下（假设Y为终止状态），以上表格中的任何包含Y的状态集合都将被归类为终止集。

将每个分组进行审查，请大家查看下面的实际例子，并自行理解其中的含义。

3.每个不能再被分割后的分组中（如果该分组仍包含超过两个元素），则其所有内部的状态均等价；可以用其中一个替代它们；具体操作如下：假设以状态1替代状态2，则需移除该被替代的状态及其所有引出弧，并将所有原本指向被替代的状态（即原来的输入）的所有弧重新指向替代的状态（即新的目标）。

例：

12.

例题：构造一个DFA，它接受∑={x，y}上所有倒数第二个字符为y的字符串

上面这道题的分析思路是

1.根据他所描述的功能，构造出一个正规式，正规式先给大家：（x|y）*y (x|y)

2.构造一个初始状态X和和最终状态Y，将正规式写在他们的转换弧上。

3.遵循第8点所述的分割标准对它实施分割直至每一条转换弧仅包含单一字符

4.分裂后所得的状态转换系统本质上就是一个NFA（非确定的有限自动机）

在掌握第9点知识后, 就可以按照第10点所述的方式, 将所求的NFA确定化为确定型有限自动机（DFA）。

通过获得确定化后的状态转换图后, 接下来需要进行的就是简化工作. 这相当于第11条所述的内容.

语法分析

（1）基本定义

上下文无关文法的定义

句型、句子的概念

语义与语用之间的对应关系，通过文法规则生成句子的整体集合构成了该语言。

语法分析树及其二义性：判定文法是否具有二义性的方法在于是否存在至少一个句子能够产生两棵不同的语法树。若一个文法存在至少一个句子能够产生两棵不同的语法树，则称此文法为具有二义性的文法。

3型文法是正规文法、正则文法、线性文法

2型文法也称为称为上下文无关文法

若一个文法是递归的，则由它产生的语言的句子个数是无限的

（2）自上而下

文法左递归的定义

消除文法的左递归的方法：直接左递归

消除回溯的方法：提取公共左因子

递归下降分析法的概念，应满足什么条件？

递归下降法对文法的每个非终结符构造一个相应的子程序

预测分析法：为文法构造预测分析表时需要执行以下步骤：消除左递推、避免回溯现象、计算First集和Follow集。举例说明时，则得到文法变换式如S \rightarrow a | aS | (T)

（3）自下而上

短语、直接短语的概念

句柄的概念（一个句型的最左直接短语）

规范归约（最左）、规范推导（最右）、规范句型

规范归约的关键问题是寻找句柄

在规范归约中，可归约串必出现在栈顶

算符文法、算符优先文法的概念，如何判断

构造算符优先关系表、Fisrtvt、lastvt集合，可不考虑#号

素短语：算符优先归约的关键问题是寻找最左素短语

算符优先法尤其适用于表达式的分析

给出文法G（P）

X → jYj

​ Y → kZ | i

Z → Yid

该文法属于哪种类型？为了更好地理解这一特性，请您参照FIRSTVT和LASTVT集合构建相应的算符优先关系表进行详细说明。

该文法属于哪种类型？为了更好地理解这一特性，请您参照FIRSTVT和LASTVT集合构建相应的算符优先关系表进行详细说明。

欲构造行之有效的自上而下分析器，则必须消除文法中含有的左递归

LR分析法属于自底向上分析方法

从文法出发构造LR（0）分析表的步骤

1）基本定义

1. 上下文无关文法的定义

文法：是描述语言的语法结构的形式规则（或称语法规则）

上下文无关文法概念:

它所表征的语法范畴（或语法单位）不依赖于这种范畴可能出现的存在环境，并不受其所在语境的影响。

上下文无关文法G可定义为一个四元式(V_T，V_N，S，P)

V_T是终结符号集合，它的每个元素称为终结符号，用小写字母表示。

V_N是非终结符号集合，它的每个元素称为非终结符号，用大写字母表示。

S是一个开始符号，是一个非终结符，至少在一个产生式作为左部出现

在其中由P组成的集合中每一个元素即为一条产生式规则。它可以用符号形式表达为： P \rightarrow \alpha | b 其中非终结符即为生成规则的左部部分。这些\alpha和b各自都被视为候选生成规则。它们既可以是终止符号也可以是非终止符号甚至是由终止与非终止符号组成的复合形式。

2. 句型、句子的概念（小题）

令G为一个文法，则其起始符号S若可推导出一序列α（即S\stackrel{*}{\Rightarrow}α），其中α属于非终结符与终结符的组合集合(V_N∪V_T)* ，则该序列α即为该文法的一个句型；若进一步满足条件使得该序列仅由终结符构成（即S\stackrel{+}{\Rightarrow}α），则此类序列被称为该文法的一个句子；值得注意的是，在这种语境下所形成的句子本质上就是一种仅包含终结符的式子

3. 文法和语言的对应关系：

由文法G生成的所有句子组成一个语言。当给定一个特定的文法后，则能唯一确定其生成的语言；已知一种特定的语言，则可找到相应的能够产生这种语言的文法。

4. 语法分析树与二义性：

通过建立一棵语法树的形式模型来描述句型的推导过程。当同一个文法规则能够推导出两种不同的语法结构时，相应的句子被定义为存在二义性。这种现象表明该文法具有二义性。

3型文法是正规文法、正则文法、线性文法（用于词法分析）

2型文法也称为上下文无关文法（用于语法分析）

1型文法也称为上下文有关文法

若一个文法是递归的，则由它产生的语言的句子个数是无限的 。

（2）自上而下

8. 文法左递归的定义

在文法中存在某个非终结符P满足条件：P→Pα。亦即，在该产生式中其最左侧符号即是该非终结符本身的情况发生时，则称该文法为具有左递归特性。

9. 消除文法的左递归的方法 ：

只要求消除直接左递归，方法见下面的例子。

设有产生式 P→Pα|β

其中β的首字母不是P，并且α也不等于ε。这意味著我们可以将P的规则转换为相应的非直接左递归形式。

​ P→βP’

​ P’→αP’|ε

这样就消除了P→Pα|β这个式子的左递归。

（提醒：当解题过程中，全面检查每一个语法生成式，并通常存在多个带有左递归特征的生成式，应逐一去除）

10. First集合Follow集的构造方法（较抽象）

First集的构造方法：

对于任意一个符号X，构造他的frist集的方法是：

​ (1)若X∈VT （终结符），则FIRST(X)={X}.

(2) 如果X是一个非终结符，并且存在一个产生式X→a...（其中小写字母a代表任意一个终结符号），那么将该符号添加到FIRST(X)集合中；此外，在存在生产规则X→ε的情况下，则将空字符串ε也包含在FIRST(X)集合中。

若存在产生式X→Y…（其中大写Y代表任意一个非终结符号，并且处于候选状态），则将FIRST(Y)中所有非ε元素加入到FIRST(X)中。

FOLLOW集的构造方法：（书上的表述很难懂，大白话表述）

(1)对于文法中给定的开始符号S，置#与FOLLOW(S)中；

(2)将所有产生式侯选式中的非终结符都标出来，并从前往后挨个检查

为了便于讨论，在本节中我们假定A→αBC是一个产生式。（其中B和C是非终结符而α是终结符）

先进行检测，在当前情况中,B是非终结符的第一项候选，并且其右侧有符号C存在

当检测到某个非终结符右侧存在其他符号时，
比如这里的B，
检查该右侧符号对应的 FIRST 集合，
这里指的是 。
随后将这些元素添加至 FOLLOW(B) 中；
特别地，在此情况下，
若该集合包含空字符 ε，
还需将来自 FOLLOW(A) 中的元素包含进 FOLLOW(B)
无需考虑这一点。

当检测到的终止符右侧没有其他符号时

在分析中，在考虑文法规范时，在某些特定情况下（即当涉及左部符号时），我们发现这些符号的存在并不会对后续分析产生实质影响（即α的存在对分析没有实质影响）。换句话说，在检测某个候选文法时只需关注其右侧部分即可（即无需过多关注左侧符号的具体存在与否）。按照前面所述的方法进行处理（即逐一检查每个候选文法中的非终结符），最终可确定所有候选文法的FOLLOW集合。

11. 递归下降分析法的概念，应满足什么条件？

该技术能够用于递归下降分析技术来解析可解析的语法结构，并且这些结构属于LL(1)语法类别。需满足以下要求：包括单一 productions 和无冲突的情况。

文法中没有左递归结构（值得一提的是：移除非文法中的左递归结构将有助于构建有效的自上而下分析器）

(2)对于文法中每一个非终极符号A的所有候选表达式，在其产生式集合中对应的first集合彼此互不相交。也就是说，在任意两个候选表达式α和β属于同一个非终极符号A的产生式集合，则其first集合first(α)和first(β)必定没有共同元素。

​ A→α1|α2|…|αn

​ 则 FIRST(αi)∩FIRST(αj)=Φ (i≠j)

在文法中每一个非终结符A,如果该候选式的FIRST集合包含空字符串ε,则必须满足某种条件.

​ FIRST(A)∩FOLLOW(A)=Φ

12. 预测分析表的构造

构建预测分析表的方法如下：（1）首先绘制一个表格；该表格的第一行列出文法中的所有终结符集合；第一列则对应所有产生式的左侧。

分析文法时需对每个产生式的候选符号逐一进行分析。我们假设这里存在一个文法中的产生式A→α|b，在分析其候选符号时发现：如果FIRST集合α包含终结符a，则将该候选符号对应到状态机的状态M[A,a]中；如果FIRST集合b包含终结符β，则将该候选符号对应到状态机的状态M[A,β]中；重复上述步骤直至所有候选符号都被处理完毕并记录于状态机表格中

特别地，在某个产生式侯选式的FIRST集中出现空子ε的情况下（如前所述），我们考虑如下情况：在A→α|b这种形式下，如果FIRST(α)集合中还包括ε，则需要确定FOLLOW(A)集合中的所有终结符元素（例如设其中一个为β），然后将规则"A→α"记录于M[A,β]中；接着依次检查FOLLOW(A)集合中的每个元素，并在对应的表格位置填写"A→α"即可完成处理

13. 实际大题

给出一个文法，要你最终构造出他的预测分析表，整个过程的步骤如下:

1.消除文法左递归

2.构造每个产生式左部（即->符号左边的非终结符）的First集、Follow集

3.构造每个产生式的每个侯选式的first集

4.证明文法是一个LL(1)文法

5.构造出预测分析表。

例：设有文法G(V_T，V_N，S，P)，

其中 VT={a， ∧ ，, ，(，) }；VN={S,T}；S = S

P:

​ S → a | ∧ | (T)

​ T → T,S | S

(1)消除其产生式的左递归.

(2)经改写后的文法是否是LL(1)的？给出它的预测分析表

解：

(1)消除其产生式的直接左递归

对于T → T,S | S (按照第9点中介绍的知识，这里P=T，α=,S ，β=S)

​ 所以变成

T→ST’

​ T’→,ST’|ε

所以文法改写后变为：

​ S → a | ∧ | (T)

​ T→ST’

​ T’→,ST’|ε

(2)经改写后的文法是否是LL(1)的？给出它的预测分析表。

依据第十点的知识，构造出相应的FIRST集及FOLLOW集；继而按照第11点的知识论证其为LL（1）文法；最后依照第12点的知识求取预测分析表

解：首先计算所有产生式左部非终结符号的FIRST集合，并依据第十点所述的方法论执行相关运算步骤

FIRST( S )={ a ∧ ( };

​ FIRST( T )={ a ∧ ( };

​ FIRST( T’)={ , ε };

随后计算所有候选式的一阶集（FIRST集），具体步骤如下：对于每个候选式而言，在其起始符号为一个小写字母或空字符ε时，则该候选式的FIRST集即为此小写字母或空字符ε；若起始符号是非终结符，则将其一阶集中除了空字符ε之外的所有元素全部纳入当前候选式的一阶集。

FIRST(ST’)={ a ∧ ( }; （S的FIRST集中除空字以外的元素）

​ FIRST(,ST’)={ , }; （, 本身）

​ FIRST(a)={ a }; （a 本身）

​ FIRST(∧)={ ∧ };

​ FIRST((T))={ ( };

FIRST（ε）={ε} （ε本身）

注意：遇到这种情况时可以暂时记录下来，并继续按照步骤推进。最终一旦遇到某个终结符对应的FOLLOW集合较为明确时，则将其列出后回过头来填充之前留下的空白部分即可。

FOLLOW(T)={ ) };

FOLLOW (T’)={ ) };

FOLLOW (S)={ # , } };

完事之后要证明他是LL（1）文法，用到第十一点中的知识。

证明：

S → a | ∧ | (T)

​ T→ST’

T’→,ST’|ε

（1）文法已经消除了左递归

（2）FIRST(a)∩FIRST(∧) ∩FIRST((T))={a}∩{∧} ∩{(}=Φ

FIRST(,ST’) ∩FIRST（ε）=Φ

（3）在T’→,ST’|ε中，FIRST（ε）={ε}，里面含有空字，所以需要检验：

FIRST( T’)∩FOLLOW (T’)={ ，,ε}∩{ ) }=Φ

接下来构造他的预测分析表

（3）自下而上

14. 短语、直接短语的概念

归约被称为基于文法的生成式规则将右部分为左符号的过程。实际上，在（2）中我们研究的是自上而下由左边导向右边的过程。本质上来说，推导与归约是互为反向的过程

15. 句柄的概念

一个句型的最左直接短语 是这个句型的句柄

16. 规范归约、规范推导、规范句型

规范归约 （最左归约）是一个关于**规范推导（**最右推导）的逆过程

在自上而下的讨论过程中，在我们的分析过程中始终采用的是最左推导的方法。即，在这种分析方法中，我们会始终将候选式中最左边的非终结符首先推导为终结符。为了帮助大家更好地理解这一概念，请回顾一下FIRST集合的相关计算方法。这一过程实际上正是我们在自上而下分析时所采用的方式。

由规范推导推出的句型称为规范句型 。

由于句子结构是由规范推导所推出的句子结构（Normative phrase structure），因此该句子结构的句柄右侧仅包含终结符号（因为这是最右推导过程，在此过程中右侧的非终结符号必定被转换为终结符号）。

规范归约的关键问题是寻找句柄

在规范归约中，可归约串必出现在栈顶

19. 算符文法、算符优先文法的概念，如何判断

这种文法其特点是没有这样的结构：任何产生式右部都不会出现两个连续出现的非终结符。也就是说，在这种文法中不存在形如...QR...这样的产生式右边结构。

算符之间的优先关系表示：（重要）

1. a 等于 . b 当且仅当文法 G 包含有形式为 P → …ab... 或 P → …aQb... 的产生式；
   2 号 . a 小于 . b 当且仅当文法 G 包含有形式为 P → …aR... 的产生式； 而 R -> ...b... 或者 R -> ...Qb...
   3 号 . a 大于 . b 当且仅当文法 G 包含有形式为 P → …Rb... 的产生式； 而 R -> ...a 或者 R -> ...aQ

在此部分讨论的是运算符优先级的问题，请注意运算符之间的优先级关系有三种，请特别注意符号右下角的那一点是不能少的（正确的写法应该是将点写在那三个符号的里面），这与数学上简单的等于大于和小于有所不同，在某些情况下可能出现a<.a的情况都是可能的，并且即使有a <. b也并不意味着有b>.a的关系这一点看起来很荒谬但在解题过程中却非常重要请务必记住以后如果求得运算符之间的优先关系是a <. b千万不要自作聪明地写成b>.a否则就全错了切记切记！

如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：

​ a=.b

​ a>.b

​ a<.b

则称G为一个OPG语法（算符优先文法）。若存在两个算符之间的关系多于一种，则该文法不是算符优先文法。

20. 素短语

elemental phrase is a phrase within a sentence structure, which must contain at least one terminal symbol and, beyond itself, does not include any other elemental phrases.

最左素短语： 处在句型最左端那个素短语成为最左素短语

算符优先归约的关键问题是寻找最左素短语

算符优先法尤其适用于表达式的分析

21. Firstvt集合和lastvt集合的构造方法

Firstvt集合构造方法：

（1） 若有产生式P→a…或P→Qa…，

​ 则aÎFIRSTVT§；

（2）若aÎFIRSTVT(Q)，且有产生式P→Q…，

​ 则aÎFIRSTVT§。

lastvt集合的构造方法

（1） 若有产生式P→… a或P→… aQ ，

​ 则aÎ LASTVT§；

（2）若aÎ LASTVT(Q)，且有产生式P→… Q ，

​ 则aÎ LASTVT§。

这些集合的构建方法被认为比传统的FIRST和FOLLOW方法更为简洁。我对上述理论的理解以及构建思路进行补充说明。具体来说，则是从其对应的产生式中进行分析。对于firstvt, 其实有两种情况需要考虑：第一种情况是某个候选式的起始符号为终结符（如P→a...），那么就可以直接将该终结符加入到P的第一个vt集合中；第二种情况则是起始符号为非终结符（如P→Q...），那么就需要将Q的所有vt元素纳入到P的第一个vt集中（需要注意的是，在这种情况下不包括ε）。至于LASTVT集的构造，则与firstvt集的方式正好相反，请大家自行理解其中的道理即可无需赘述。需要注意的是，在某些特殊情况下（例如某个候选式只有一个字符时），即当形式为P→a或P→Q时，则该字符既会被视为第一个字符也被视为最后一个字符，在构建两个vt集中都需要予以特别考虑

22.算符优先关系表的构造方法

该方法建立于你已掌握了前述两个集合构建的方法之上。有了这两个集合之后则能根据它们确定文法中所有终结符间的优先关系具体步骤如下

（1）假定有个产生式的一个候选形为···ab····或aPb····，有a=.b

(2)假定有个产生式的一个候选形为(a代表终结符，P代表非终极符)

…aP…

那么，对任何bÎFIRSTVT§，有a <. b。

(3)假定有个产生式的一个候选形为

…Pb …

那么，对任何aÎLASTVT§，有a >. B

（解析：(1)的情况很简单，对（2）和（3），这里的方法概括起来说就是，找到侯选式中所有一个终结符紧挨着一个非终结符的情况，如aP或者Pa,如果是前者，那么得出a<.P的所有FIRSTVT集合中的元素；如果是后者,那么得出P的所有LASTVT集合中的元素>.a 只要把所有候选式里的这两种情况都考虑完，所有算符之间的优先关系也就找到了。还是请大家注意，a<.P的所有FIRSTVT集合中的元素这句话，并不等同于P的所有FIRSTVT集合中的元素>.a,千万别反过来写，一定把两种情况的顺序记清楚，a是在前面还是在后面。）

一旦确定了文法中所有终结符之间的优先顺序，则可构建一张算符优先关系表。该表由首行与首列共同构成，并将列出文法的所有终结符（请确保两者顺序一致）。如图所示表格即为此处所指）。在填充这张表格时，请先关注列上的符号对应的右侧元素再读取行上的符号对应的左侧元素即可完成填充工作

当完成表格填充后需进行判断：若上表中任一空白单元格最多只能容纳单一符号，则可表述为：鉴于所述文法规则规定任两个相邻字符间的兼容性仅限于>.<.=.之中的一种情况存在，则该文法规则属于算符优先类文法；反之若某空白单元格可容纳超过一字符，则可推断该文法规则不具备算符优先性

例：给出文法G（P）

X → jYj

Y → kZ|i

Z → Yid

这一文法是否属于算符优先文法？请根据FIRSTVT、LASTVT集合构造相应的算符优先关系表并加以说明。

LR分析法属于自底向上分析方法

26. 从文法出发构造LR（0）分析表的步骤

(1)构造文法G的拓广文法G’

(2)构造LR(0)项目

(3)构造G’的项目集规范族(CLOSURE和GO函数)

(画出一个确定的有限自动机DFA)

(4)构造分析表

语义分析

综合属性和继承属性概念

综合属性

用于“自下而上”传递信息

在语法树中，一个结点的综合属性的值由其子结点的属性值确定。

基于此，在构建系统时, 常常用 bottom-up approach 来为每个节点应用语义规则以计算各属性的综合值。

仅仅使用综合属性的属性文法称S—属性文法五、中间代码生成

继承属性

用于“自上而下”传递信息。

在语法树中，其继承属性基于此节点的父节点及其兄弟节点的一些属性确定。

用继承属性来表示程序语言结构中的上下文依赖关系很方便。

中间代码生成

中间代码是一种面向语法，易于翻译成目标代码的代码

后缀式（逆波兰式）的概念

逆波兰式中各运算法出现的顺序与实际运算顺序一致

后缀式与抽象语法树（表达式树）的关系

DAG的含义

四元式表示方法，联系时通过临时变量，可以翻译各种语句

将赋值语句表示成后缀式和四元式

1. 中间代码：

是一种面向语法，易于翻译成目标代码的代码

中间语言的形式主要包含三种类型：一是逆 Polish 表示法；二是图形化表示方法（其中一种是抽象语法树（AST），另一种是基于有向无环图（DAG）的表示方法）；三是三地址代码。

2. 后缀式（逆波兰式）的概念

把运算量(操作数)写在前面，把算符写在后面。

例如：a+b，写成ab+

逆波兰式中各运算法出现的顺序与实际运算顺序一致

(1) a*(-b+c)

(2) a+b*(c+d/e)

(3) -a+b*(-c+d)

(4) not A or not (C or not D)

(5) (A and B) or (not C or D)

(6) (A or B) and (C or not D and E)

解：

(1) ab-c+*

(2) abcde/+*+

(3) a-bc-d+*+

(4) A not C D or not or not

(5) A B and C not D or or

(6) A B or C D not E and or and

3. 后缀式与抽象语法树（表达式树）的关系

后缀式其实是抽象语法书的线性表示形式，并且是按后根序遍历得到的。

4. 将赋值语句表示成后缀式和四元式

无需赘述具体方法了；关于后缀式求法的说明已经给出。至于四元式的问题，请看下面这个例子的分析和说明。

将表达式a:=(b+c)*e+(b+c)/f分别表示成后缀式、四元式（这道题2012年考的是原题）

解：

1.后缀式：a b c + e * b c + f / + :=

2. 四元式

(1) ( +, b, c, T1 )

(2) ( *, T1, e, T2 )

(3) ( +, b, c, T3 )

(4) ( /, T3, f, T4 )

(5) ( +, T2, T4, T5 )

(6) ( :=, T5, , a )

再给一个例子：

表达式-(a+b)*(c+d)-(a+b+c)分别表示成四元式

解：1. 四元式

(1) ( +, a, b, T1 )

(2) (-, T1, , T2 )

(3) ( +, c, d, T3 )

(4) ( *, T2, T3, T4 )

(5) ( +, a, b, T5 )

(6) ( +, T5, c, T6 )

(7) ( -, T4, T6, T7)

代码优化

简述代码优化的原则与优化的级别，并列举三种常用的优化技术

基本块、流图的概念，如何画、节点对应基本块

局部优化的方法，DAG是对基本块进行优化的有效工具

不变运算的代码外提的条件

循环优化中的强度削弱的含义

1. 简述代码优化的原则与优化的级别，并列举三种常用的优化技术 (小题)

三个原则：

¨ 等价原则：经过优化后不应改变程序的结果；

¨ 有效原则：使优化后所产生的目标代码时间较短，占用的存储空间较小；

¨ 合算原则：应尽可能以较低的代价取得较好的优化效果

​ 优化级别：

¨ 局部优化

¨ 循环优化

¨ 全局优化

常用的优化技术：

¨ 删除公用子表达式

¨ 代码外提

¨ 强度消弱

2. 基本块、流图的概念，如何画、节点对应基本块、要求进行局部和循环优化

一：首先要了解两种语句的概念和特征 ，对于后面的做题方法很重要

1.转移语句：如果某个句子中含有goto··语句，那么他就是一个转移语句

转移语句可划分为两类：a类为带有条件判断的转移,采用if结构配合goto关键字; b类为无条件转移,在程序中仅包含goto关键字。

2.停语句：halt 这样的语句被称为是停语句。

二：接着要知道入口语句 的求法：有三种语句是入口语句

程序的第一个语句，

可经由条件转移指令或无条件转移指令引导指向的一组指令（即被GOTO指令引导指向的一组后续指令），亦即那些被GOTO指令引导指向的具体后续执行路径。例如，在第（3）条指令中有GOTO引导至第（8）条指令，则该条指令即为入口指令。

紧跟在条件转移语句后面的一个语句。

三：分类四元式程序为快速基础 的方法：（这部分内容可能有些抽象，在学习过程中可能会遇到困难；通过后面的例题分析和讲解，大家应该能够理解）

对求出的每个入口语句，确定其所属的基本块。它是由

A一个入口语句到下一入口语句(不包括该入口语句)之间的语句序列

B一个入口语句到一转移语句(包括该转移语句)之间的语句序列

C 一个入口语句到一停语句(包括该停语句)之间的语句序列组成的

四：流图 的画法：（这里看起来也比较抽象，大家跟着看后面的例题就会理解）

每个流图均采用基本块作为节点进行构建。当一个节点对应的基本块在其流程图中位于程序开始位置时，则称该节点为首节点。当在一个执行流程中包含两个相邻的基本块B1和B2时...

存在一个转换语句从B1的最后一条指令转向B2的第一条指令

在程序的序列中，在B1之后紧接着的是B2，并且同时满足B1的最后一条语句不是无条件转移语句。

我们就说B1是B2的前驱，B2是B1的后继，并从B1画一条有向边到B2

五：给出实际的例题（这是复习PPT上的例题）

给出程序的四元式表达形式，画出基本块和流图

(1) read C

(2) A:=0

(3) B:=1

(4) A:=A+B

(5) If B>=C goto (8)

(6) B:=B+1

(7) goto (4)

(8) write A

(9) halt

解：

第一步环节 主要涉及找出入口语句：

• 第1步对应于程序的第一句话。
• 第4步由第7步引导至。
• 第6步接着第5步执行。
• 第8步由第5步引导至。

第二步 画基本块：主要通过使用方框来将语句包裹起来（这里不好画 因此没有进行绘制操作）

对于前三个项目：

• （1）、（2）、（3）
  属于这一类别的一种方法。
• （4）、(5)
  属于这一类别的一种方法。
• (6)、(7)、(8)、…、…
  属于这一类别的一系列方法。
• (9)
  属于这一类别的一种方法.

第三步 画流图：

3. 局部优化的方法

DAG是对基本块进行优化的有效工具

利用DAG可以实现局部优化

(1)合并已知量

(2)删除多余运算

(3)删除无用赋值

4. 不变运算的代码外提的条件

不变运算所在的结点是循环L所有出口结点的必经结点.

对于一个loop-invariant operation A := B op C，在该运算符所在循环体内所有使用场景中均未被再次赋值的情况下，则可将该运算提取到循环之外。

循环中所有A的引用点只有S中的A的定值才能到达。

5. 循环优化中的强度削弱的含义

把程序中执行时间较长的运算转换为执行时间较短的运算 。

强度消弱主要是对与归纳变量有线性关系的变量赋值进行；

经过强度消弱后，循环中可能出现一些新的无用赋值；

对于消弱下标变量地址计算的强度非常有效

目标代码生成

编译程序生成的目标程序种类(309)

目标代码一般有以下三种形式：

能够立即执行的机器语言代码 所有地址已经定位；

在运行时, 通过集成或结合程序将待装配的机器语言模块与相关程序进行连接, 并将其转换为可执行的机器语言代码.

汇编语言代码 尚须经过汇编程序汇编，转换成可执行的机器语言代码。

总结

这门课涉及的知识点确实不少。难度较大。学习这门课程只能说拓宽了视野。自己构建一个编译器更是相当有挑战性的。其中提到的知识点主要来源于老师的讲解以及相关的参考资料。可能存在一些误差，请随时指出。这里只是编译原理的部分知识也可说算是核心基础知识若想深入研究还需参考其他书籍

此处提供两本参考书籍：《编译原理》由陈国旺编写，并提供PDF版本下载链接：https://pan.baidu.com/s/1o5rxO-ycQ7gymVA_khrK4Q，提取码为6666

编译原理方面，《龙书》提供了一本电子版PDF教材，并附带了访问该电子资源的密码