编译原理

课程主要内容是设计和实现编译器

第一章：引论

基本概念

[广义·课本原文]编译器是一个程序，读入某种语言(源语言)编写的程序并将其翻译成一个与之等价的另一种语言(目标语言)编写的程序。作为这个翻译过程的一个重要部分，编译器能够将用于报告被编译的源程序中出现的错误。

• 但根本任务、关键任务是程序翻译。

[狭义]把人类更容易理解和使用的高级语言转化为计算机能“理解”和运行的机器语言（或者较为接近的汇编语言）。

• 翻译程序(Translator)：把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序

• 编译程序(Compiler)：把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。

  

  运行编译程序的计算机：宿主机 运行目标程序的计算机；目标机 根据用途和侧重，编译程序可分为：

  • 诊断编译程序(Diagnostic Compiler)

  • 优化编译程序(Optimizing Compiler)

  • 交叉编译程序(Cross Compiler)：编译程序产生不同于其宿主机的目标代码

  • 可变目标编译程序(Retargetable Compiler)：不需要重写编译程序中与机器无关的部分。

• 解释程序(Interpreter)：

  • 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序

为什么不直接把源程序翻译成目标代码

这是因为高级语言（m种）和机器语言（n种）都有很多种，两两配对的话编译器种类就太多了（m*n），借助简单的中间代码，就可以减少编译器的种类（m+n）

组成

编译器由两个部分组成：分析（analysis）和综合（synthesis）。分析部分被称为编译器的前端（front end），综合部分被称为后端（back end）

分析部分：把源程序分解成多个组成要素，并在这些要素之上加上语法结构。然后使用这个结构来创建该源程序的一个中间表示。

如果分析部分检查出源程序没有按照正确的语法构成，或者语义不一致，它就必须提供有效的信息，使得用户可以按此进行改正。分析部分还会收集有关源程序的信息，并把信息存在符号表（symbol table）中。符号表将会和中间表现形式一起传送给综合部分。

综合部分：根据中间表示和符号表中的信息来构造用户期待的目标程序。

前端与源语言相关，后端与目标语言相关。

分析·前端

分析部分包括词法分析（lexical analysis）、语法分析（syntactic analysis）和语义分析（contextual analysis）。

• 词法分析器

  • 输入：源程序字符串， 输出：单词符号表（单词类型和单词本身）
  • 对字符串进行扫描和分解，在这个过程中要正确识别哪些内容属于同一个单词（比如大于等于
    号>=就是一个单词，而不是>和=）。使用正规式和有限自动机描述词法规则。
  • 如果这个过程出错，表示源程序中有词法错误。

• 语法分析器

  • 输入：单词符号表，输出：一系列语法单位（语法树）
  • 按照早就定义好的语法，把单词符号划分为一系列语法单位，比如算术表达式、赋值语句、调
    用语句、子程序、总程序等。这些语法单位通常以语法树的形式呈现。
    在第二章中可以看到语法树的示例。
  • 如果这个过程出错，表示源程序中有语法错误。

• 语义分析器

  • 输入：语法树，输出：包含语义（属性）的语法树
  • 按照语义规则（通常是属性文法），检查各部分是否合乎语义，比如是否引用了未定义的量，
    是否调用了未定义的函数等，为生成中间代码做准备。
  • 如果这个过程出错，表示源程序中有语义错误。

编译的每个阶段都可能遇到错误。在编译过程中遇到错误后，必须以恰当的方式进行错误处理，使编译器能继续运行，以检测出源程序中的更多错误。发现错误即停止运行的编译器不是一个好的编译器。

语法分析和语义分析阶段通常能够处理编译器所能检测到的大部分错误。词法分析阶段能够检测出输入中不能形成源语言任何记号的错误字符串。语法分析阶段可以确定记号流中违反源语言结构（语法）规则的错误。语义分析阶段试图检测出具有正确的语法结构但对操作无意义的部分。

词法分析

又称扫描（scanning），词法分析器读入组成源程序的字符流，并且将它们组织成有意义的词素（lexeme）的序列。对每个词素，分析器产生如下格式的词法单元：

<token-name, attribute-value>

token-name是一个有词法分析步骤使用的抽象符号。attribute-value指向符号表中关于这个词法单元的条目。符号表条目的信息会被语义分析和代码生成步骤使用。比如以下语句

position = initial + rate * 60

这个 赋值语旬中的字符可以组合成如下词素，并映射成为如下词法单元。

• position是一个词素，被映射成词法单元<id,1>，其中id是表示标识符(identifier)的 抽象符号，而 1指向符号表中position对应的条目。 一个标识符对应的符号表条目存放该标识符有关的信息，比如它的名字和类型。

• 赋值符号＝是一个词素，被映射成词法单元<＝>。因为这个词法单元不需要属性值，所以我们省略了第二个分量。 也可以使用assign这样的抽象符号作为词法单元的名字，但是为了标记上的方便，我们选择使用词素本身作为抽象符号的名字。

以此类推，结果如下：

<id, 1> < = > <id, 2> < + > <id,3> < * > <60>

从技术上讲，我们应该为语法单元60建立一个形如<number，4>的词法单元，其中4指向符号表中对应于整数60的条目。但是我们要到第2章中才讨论数字的词法单元。第三章将讨论建立词法分析器的技术。

语法分析

又称解析（parsing）。语法分析器用词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。常用语法树表达，树中的每个内部结点表示一个运算，该节点的子节点表示该运算的分量。

语义分析

使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时收集类型信息，并把这些信息存放在语法树或符号表中。

语义分析的一个重要组成部分是类型检查。类型检查负责检验每个操作符的操作数是否满足源语言的说明。例如：很多程序设计语言都要求每当一个实数用于数组的索引时都要报错。程序设计语言可能允许一些操作数的强制类型转换。例如：一个二元算术操作符的操作数可以是一个整数和一个实数。这种情况下，编译器把整数强制转换成实数

中间代码生成

在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示，这些中间表示可以有多种形式。语法树是一种中间表示形式

中间代码可以看成某种抽象机的程序。源程序的中间表示应该具有两个重要性质。一是易于产生，二是易于翻译成目标程序。

比如用三地址码表示，类似于某种机器的汇编语言，这种机器的每个存储单元的作用类似于寄存器。三地址码由指令序列组成，每个指令最多有三个操作数。

 

综合·后端

代码优化

优化目标可以是更快，也可以是更短或者能耗更低。不同编译器优化结果不一样。

代码生成

代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言。

• 依赖于硬件系统结构和机器指令的含义
• 目标代码三种形式
  • 汇编指令代码: 需要进行汇编
  • 绝对指令代码: 可直接运行
  • 可重新定位指令代码: 需要链接
• 这一阶段的一个关键问题是变量的寄存器分配。

 

样例全流程

上面对代码生成的讨论忽略了对源程序中的标识符进行存储分配的重要问题。

 

编译器的趟（pass）

趟，有的资料称作遍，不做区分

编译器的若干个阶段通常是以一趟来实现的，每趟读一次输入文件、产生一个输出文件（但这其实是很难的）。编译器的阶段组合为趟的方式千差万别，因此我们趋向于按阶段而不是按趟来讨论编译器。

例如词法分析、语法分析、语义分析以及中间代码生成可以被组合为一趟。这样，词法分析形成的记号流可以被直接翻译成中间代码。语法分析器根据读到的记号token识别语法结构，当需要下一个记号时，通过调用词法分析器获得所需的记号。一旦语法结构找出来了，语法分析器就调用中间代码生成器完成语义分析并生成中间代码的一部分。

减少编译的趟数

如果编译的趟数越少，读写中间文件的时间开销就小。但是如果将多个阶段组合为一趟，就不得不将这个程序保存在内存中，但是这样消耗的空间就急剧提高。

一般词法分析器和语法分析器之间的接口通常被限制于单个记号token，所以在某些情况下，可以为某些尚不知晓的信息留下空白位置，待获得这些信息后再填上这些空白位置。通过回填技术，把中间代码和目标代码划归到一趟中。

 

基本知识：语言及其文法的基本概念

这一部分来自于中国大学慕课，哈工大编译原理课程

字母表 $\sum$

字母表 $\sum$ 是一个有穷符号集合

符号：字母、数字、标点符号、…

乘积

字母表 $\sum_1$ 与 $\sum_2$ 的乘积：$\sum_1\sum_2 = \{ab|a\in\sum_1,b\in\sum_2\}$（类似于笛卡尔积。）

如：$\{0,1\}\{a,b\}=\{0a,0b,1a,1b\}$

幂

字母表 $\sum$ 的n次幂：

$\sum^0=\{\epsilon\},\sum^n=\sum^{n-1}\sum,n\geq1$ （$\epsilon$ 为空串）

如 $\{0,1\}^3=\{0,1\}\{0,1\}\{0,1\}=\{000,001,010,011,100,110,111\}$

正闭包

正闭包：长度为正数的符号串构成的集合（相当于排除空串 $\epsilon$）

$\sum^+ = \sum\cup\sum^2\cup\sum^3...$

克林闭包

克林闭包是任意符号串构成的集合

$\sum^*=\sum^0\cup\sum^+=\sum^0\cup\sum\cup\sum^2\cup\sum^3...$

 

串（string）

设 $\sum$ 是一个字母表，$\forall x\in\sum^*$，$x$ 称为该字母表上的一个串。

即：串是字母表中符号的一个有穷序列。

串 $x$ 的长度记作 $|x|$，指x中符号的个数。特别的，$|\epsilon|=0$

连接

如果 $x$ 与 $y$ 是串，那么二者的连接是把 $y$ 附加到 $x$ 后面形成的串，记作 $xy$ 。

特别的，$\epsilon s=s\epsilon=s$ 。

如果 $s = xy$，称 $x$ 是 $s$ 的前缀，$y$ 为 $s$ 的后缀。

串的幂

$s^0=\epsilon,s^n=s^{n-1}s,n\geq1$

文法部分掺杂在了下一部分

 

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

这一章主要是对第三到六章的总括。重点是编译器的前端部分：词法分析、语法分析和中间代码生成。

程序设计语言描述的两方面定义：程序模式(语言的语法、程序的正确形式)、程序含义(语言/程序的语义)

• 语法：用来形成和产生一个合适的程序的规则，包括词法规则和语法规则。
  • 词法规则是单词符号的形成规则。单词符号一般包括：各种类型的常数、标识符、基本字、算符和界符等。
  • 语法规则是语法单位的形成规则。语法单位包括表达式、语句、分程序、函数、过程和程序等等。
• 语义：定义每个程序在运行时做什么事情，没有公认的形式系统描述语义。

语法的表示法：上下文无关文法或者BNF(Backus-Naur范式)。使用现有的表示法描述语言的语义要比描述语言的语法难的多。因此，在定义语言的语义时，使用非形式化方法和启发性实例。

上下文无关除了可以用于定义语言的语法之外，还可用于指导源程序的翻译。面向语法的编译技术，如语法制导翻译技术（2.3），语法扫描/语法分析（2.4），对于组织编译器的前端十分有用。

两种中间代码生成

一种称为抽象语法树(abstract syntax tree)，或简称为语法树(syntax tree)。它表示了源程序的层次化语法结构。在图2-3的模型中，语法分析器生成一棵语法树，它又被进一步翻译为三地址代码。有些编译器会将语法分析和中间代码生成合并为一个组件。

图2-4a中的抽象语法树的根表示整个do-while循环。根的左子树表示循环的循环体，它仅包含赋值语句i=i+1;，根的右子树表示循环控制条件a[i] < v。后文将介绍一个构造语法树的方法。

图2-4b中给出了另一种常见的中间表示形式，它是一组” 三地址”指令序列，这个中间代码形式的名字源于它的指令形式：x = y Op z，其中op是一个二目运算符，y和z是运算分址的地址，x是运箕结果的存放地址。 三地址指令最多只执行一个计算。

 

前端模型与样例

我们考虑构造一个把中缀表达式转换成后缀表达式的语法分析器。例如中缀表达式9+5-2的后缀表达形式为95-2+，可以使用一个堆栈把后缀表达式直接转换成计算该表达式的计算机代码。我们之所以先考虑这样的简单表达式，主要目的是简化这个语法分析器， 使得它在处理运符分址和运符符时只需要考虑单个字符。

词法分析器使得翻译器可以处理由多个字符组成的构造，比如标识符。 标识符由多个字符组成，但是在语法分析阶段被当作一个单元进行处理。这样的单元称作词法单元(token)。例如，在表达式count+ 1中，标识符count被当作一个单元。

 

语法定义

一个语法非常自然地描述了许多程序设计语言结构的层次结构。例如java的if-else语句具有如下形式:

if (表达式) 语句 else 语句

整个语句是由一个关键字if、一个左括号、一个表达式、一个右括号、一条语句、关键字else和另外一条语句组成的序列。如果使用变量expr来标识表达式，使用变量stmt来标识一条语句

stmt -> if (expr) stmt else stmt

这里，箭头可以读作“可以具有形式”。这样的规则称为产生式(production)。在一个产生式中，像关键字if和括号这样的词法元素称为记号(token)，像expr和stmt这样的变量表示一个记号序列，并称之为非终结符(nonterminal)

 

文法/上下文无关文法

包含如下四个部分:

• 一个终结符号集合 $V_T$，有时称为词法单元，终结符号是该文法所定义的语言的基本符号集合。
• 一个非终结符集合 $V_N$，它们有时也称为语法变量。每个非终结符号表示一个终结符号串的集合。
• 一个产生式集合 $P$：每个产生式具有一个左部和右部，左部和右部由箭头连接，左部是一个非终结符，右部是终结符和(或)非终结符序列。产生式主要用来表示某个构造的某种书写形式。如果产生式头非终结符号代表一个构造，那么该产生式体就代表了该构造的一种书写方式。
• 一个开始符号 $S$。开始符号是一个指定的非终结符。

定义语法时只需列出文法的产生式，并把以开始符号为左部的产生式列在最前面。数字、类似于<=的符号、类似于while的黑体关键字均为终结符，斜体名字表示非终结符，任何非斜体的名字或者符号都是记号token。

为了表示上的方便，常把具有相同左部的产生式合并，写成一个产生式，其左部为所有产生式共有的那个非终结符，右部为所有产生式右部的组合，每个右部用’|‘分隔，’|‘读作’或’

对于表达式9-5+2,下面的文法描述了这些表达式的语法，产生式为：

list -> list + digit
list -> list - digit
list -> digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

左部的非终结符皆为list(列表)的按个产生式的右部可以合并为:

list -> list + digit | list - digit | digit

文法的记号是下列符号

+ - 0 1 2 3 4 5 6 7 8 9

斜体词 list 和 digit 是非终结符，list是开始非终结符，因为它所对应的产生式列在最前面。

如果一个非终结符出现在一个产生式的左部，该产生式称为该非终结符的产生式。记号串是零个或多个记号的序列。一个包含零个记号的记号串称为空串（empty string），记为 $\epsilon$ 。

老师给的符号约定：

推导

从开始符号出发，反复代替产生式中的非终结符(用该非终结符的产生式的右部)，一个文法可产生一个串。由一个文法的开始符号产生的记号串形成了该文法定义的语言。

上面的例子就可以这样推导。

注意，在optparams(“可选参数列表”)的产生式中，第二个可选规则体是 $\epsilon$ ，它表示空的符号串。也就是说，optparams 可以被替换为空串，因此一个call可以是函数名加上两个终结符号 ”( “和“ ) ”组成的符号串。

又比如：

推导与规约

最右推导：若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最右非终结符进行替换。

最左推导：若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最左非终结符进行替换。

规范推导：最右推导。

规约：推导的逆过程，例如：x => y,可称为x直接推导出y，也可称为y直接归约成x。

规范归约：对句型中最左边的简单短语（句柄）进行的归约。

规范归约和规范推导互为逆过程。

• 等价文法：$G$ 和 $G'$ 是两个不同的文法，若 $L(G) = L(G')$，（ $L(G)$ ：文法G的语言，即使用文法G能推导出的全部句子）则 $G$ 和 $G’$ 为等价文法。

• 递归产生式：产生式右部有与左部相同的符号。

  • 左递归：产生式 $U → xUy$，若 $x=ε$，即 $U → Uy$；
  • 右递归：产生式 $U → xUy$，若 $y=ε$，即 $U → xU$；

• 递归文法：文法G，存在 $U ∈V_N，U =>…U…$，则文法G递归；

  • 左递归文法：$U=>U…$；
  • 右递归文法：$U=>…U$；

• 递归文法的优点：可用有穷条产生式，定义无穷语言（包含无数个句子的语言）。

语法分析 (parsing) 的任务是：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法。 如果不能从文法的开始符号推导得到该终结符号串，则报告该终结符号串中包含的语法错误。 语法分析是所有编译过程中最基本的问题之一，主要的语法分析方法将在第4章中讨论。 在本章中，为简单起见，我们首先处理像9-5+2这样的源程序，其中的每个字符均为一个终结符号。 一般情况下，一个源程序中会包含由多字符组成的词素，这些词素由词法分析器组成词法单元，而词法单元的第一个分量就是被语法分析器处理的终结符号。

语言的形式化定义

由文法G 的开始符号S推导出的所有句子构成的集合称为文法G 生成的语言，记为$L(G)$ 。即

$L(G)=\{w|s\rightarrow^*\,w,w \in V_T^*\}$

如文法 $E → E+E | E*E | (E ) | id$ 生成的语言中包含多少个句子？

答案是无限个，因为克林闭包可以无限次推导

 

形式语言理论与文法类型

根据上述讨论，$L_0 \subset L_1 \subset L_2 \subset L_3$ 。

0型文法可以产生$L_0、L_1、L_2、L_3$，但2型文法只能产生$L_2$，不能产生$L_1$。

2型文法（上下文无关文法）是我们之后主要学习的文法。

正则文法能描述程序设计语言的多数单词

 

语法分析树

语法分析树用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程。如果非终结符号A有一个产生式A->XYZ，那么在语法分析树中就可能有一个标号为A的内部结点，该结点有三个子结点，从左向右的标号分别为X、Y、Z。

正式地讲，给定一个上下文无关文法，该文法的一棵语法分析树(parse tree)是具有以下性质的树：

• 根结点的标号为文法的开始符号。
• 每个叶子结点的标号为一个终结符号或 $\epsilon$ 。
• 每个内部结点的标号为一个非终结符号。
• 如果非终结符号A是某个内部结点的标号，并且它的子结点的标号从左至右分别为 $X_1,X_2 , ···, X_n$，那么必然存在产生式$A\rightarrow X_1X_2...X_n$，其中 $X_1,X_2 , ···, X_n$既可以是终结符号，也可以是非终结符号。作为一个特殊情况，如果 $A\rightarrow \epsilon$ 是一个产生式，那么一个标号为 A 的结点可以只有一个标号为 $\epsilon$ 的子结点。

样例

9-5+2 的语法分析树，参考上面提到的产生式。

一棵分析树从左到右的叶节点是这棵分析树生成的结果。分析树生成的结果是由根节点的非终结符生成或推导得出的串。任何树的叶节点都满足从左到右都满足从左到右排列的自然顺序，即如果 X 和 Y 具有相同的父节点，且 X 在 Y 的左边，则 X 和 X 的所有后代都在 Y 和 Y 的所有后代的左边。

一个文法生成的语言是它的某个分析树生成的串的集合。为给定的记号串找到一个分析树的过程称为这个串的语法分析(parsing)

 

语法树的二义性

一棵分析树读完它的叶节点只能生成唯一的一个串，但是一个文法可能有多棵分析树生成相同的记号串。这样的文法称为具有二义性的文法。

判断一个文法是否具有二义性，只需检查是否存在一个具有多棵分析树的记号串。在构造程序设计语言及其编译器时，需要设计无二义性文法，或者使用增加了额外的规则解决二义性问题的二义性文法。

二义性文法：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。

或者说若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。

文法的二义性是不可判定的：即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性

文法二义性的解决：提出一些无二义性文法的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的。

或者改写文法使其变为无二义性文法。或者确定相应的编译方法。

 

第三章：词法分析

词法分析器的设计

什么是词法分析器

词法分析 (Lexical Analysis）/扫描 (Scanning）

词法分析器读入源程序的字符流，将其组织成有意义的词素（Lexeme）序列，产生形如<token name, attribute value>的词法单元作为输出。如：

词法分析的任务

从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。

即：输入源程序，输出单词符号，过滤空白、换行、制表符、注释等，将词素添加到符号表中。

超前搜索：识别单词符号

• 需要的情况
  • 
• 不需要的情况
  • 

词法分析器在编译器中地位

在逻辑上独立于语法分析，但是通常和语法分析器处于同一趟中。

将词法分析作为一个独立阶段的好处

• 简化编译器的设计
  • 词法分析器可以首先完成一些简单的处理工作
• 提高编译器效率
  • 相对于语法分析，词法分析过程简单，可高效实现
  • （下推自动机 vs. 有穷自动机）
• 增强编译器的可移植性

词法分析器的输出

• 词法单元 （token）

  • <词法单元名，属性值（可选）>
  • 单元名是表示词法单位种类的抽象符号，语法分析器通过单元名即可确定词法单元序列的结构
  • 属性值通常用于语义分析之后的阶段

• 模式 （Pattern）

  • 描述了一类词法单元的词素可能具有的形式

• 词素 （Lexeme）

  • 源程序中的字符序列
  • 它和某个词法单元的模式匹配，被词法分析器识别为该词法单元的实例
  • 类似于类的对象

这些词法单元都省略了属性值。词法单元与词素的关系就好比类与对象。

 

词法单元的识别（状态转换图）

状态转换图 (Transition diagram)

• 状态 ( State)：表示在识别词素时可能出现的情况

  • 状态看作是已处理部分的总结
  • 某些状态为 接受状态 或 最终状态，表明已找到词素
  • 加*的接受状态表示最后读入的符号不在词素中
  • 开始状态/初始状态 用 Start 边 表示
  • 终止状态（接收状态）可以有多个，用双圈表示
  • 

• 边( Edge)：从一个状态指向另一个状态

  • 边的标号是一个或多个符号
  • 当前状态为 s 下 一 个输入符号为 a ，就沿着从 s 离开标号为 a 的边到达下一个状态

输入缓冲

没讲

词法单元的规约

串和语言

某个字母表上的一个串(string)是该字母表中符号的一个有穷序列。

语言(language)是某个给定字母表上一个任意的可数的串集合。

还有一些闭包与语言的形式化定义的东西，第二章里有写。

正则表达式与正则定义

就是正则表达式，书上挺绕的。

 

有穷自动机

有穷自动机（Finite Automata，FA）是对一类处理系统建立的数学模型，这类模型具有一系列离散的输入输出信息和有穷数目的内部状态。

系统根据当前所处的状态和当前的输入信息就可以决定后继行为，并相应地改变当前状态。

最长子串匹配原则（Longest String Matching Principle）

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配，如：

NFA与 DFA

不确定的有穷自动机（Nondeterministic Finite Automata, NFA）对其边上的标号没有任何限制。 一个符号标记离开同一状态的多条边，并且空串 $\epsilon$ 也可以作为标号。

对于每个状态及自动机输入字母表中的每个符号，确定的有穷自动机（DeterministicFinite Automata, DFA）有且只有一条离开该状态、以该符号为标号的边。

DFA是NFA的一个特例。

确定的和不确定的有穷自动机能识别的语言的集合是相同的。 事实上，这些语言的集合正是能够用正则表达式描述的语言的集合。集合中的语言称为正则语言。

DFA

DFA由以下几部分组成：

也就是说，$\delta(s,a)$ 是 $s$ 沿着标记 $a$ 所能到达的后继状态

其中 $S=\{0,1,2,3\}$ ，$\sum=\{a,b\}$ ，$\delta$ 可以用转换表来表示，如 $\delta(0,a)=1$

NFA

NFA由以下几部分构成

也就是说，$\delta(s,a)$ 是 $s$ 沿着标记 $a$ 所能到达的后继状态集合，而DFA后继状态只有一个

注：状态转换函数为每个状态和 输入符号集合与空串的并集（$\sum\cup\,\{\epsilon\}$）给出相应的后继状态，是带空边的NFA

等价性

对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D

对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

正则表达式

前文提过一嘴

比如：

代数定律

正则文法与正则表达式等价。

正则定义

RE到NFA

讲的有点语焉不详，可以参考https://gene-liu.blog.csdn.net/article/details/108050274

NFA到 DFA 的转换算法

DFA简化算法

状态等价性

• 状态等价性

• 化简思想

化简算法

• 首先，将 S 划分为终态与非终态两个子集
  • 原因是终态可以识别空字，而非终态不可以
• 其次，对于每个子集检查能不能进一步划分

• 重复第二步，直至子集数不再增长
• 最后，若 I 含有原来的初态，则为新的初态；若含有原来的终态，则为新的终态。

示例

• 化简算法

• 生成化简后的 DFA

 

第四章 语法分析

自顶向下的分析(Top-Down Parsing)

从分析树的顶部（根节点）向底部（叶节点）方向构造分析树，可以看成是从文法开始符号 $S$ 推导出词串 $w$ 的过程。

• 每一步推导中，都需要做两个选择
  • 替换当前句型中的哪个非终结符
  • 用该非终结符的哪个候选式进行替换
• 我们后续会给出这两个问题的解决方案。

最左与最右

自顶向下的语法分析采用最左推导方式

总是选择每个句型的最左非终结符进行替换，根据输入流中的下一个终结符，选择最左非终结符的一个候选式。

样例：

前文讲过默认第一行产生式的左部是开始符，所以我们先构造如下语法树：

此时最开始，读取输入内容的指针指向id。

按照最左推导，我们先处理左子树的 $T$，可选文法只有一个，且产生式只有一个可选右部（候选式），进行构造，如下

然后最左的是 $F$，可选文法有两个候选式，一个候选式以左括号开头，另一个以id开头，现在指针指向的内容是id，所以我们选择第二个候选式， $F$ 子树为 id，如下：

完成了一个匹配，指针指向下一个字符，即为 $+$

接下来最左非终结符为 $T'$，同样两个候选式，一个以 $*$ 开头，一个是空串，显然第一个候选式无法满足，所以我们选择空串：

此时可能有两个及以上候选式以 $*$ 开头，我们只能依次尝试，尝试失败之后要进行回溯，后面会讲。

以此类推，最后：

最后构造出了这样的语法树，也就是说我们的输入满足上面的文法。

 

设计文法

文法能够描述程序设计语言的大部分语法成分，但不能描述程序设计语言的全部语法成分。当词法分析器从输入字符串产生记号序列时，将完成一定量的语法分析工作。对输入字符串的某些限制(如标识符的声明必须先于它们的使用)不能用上下文无关文法来描述。语法分析器接受的记号序列形成了程序设计语言的超集。语法分析以后的各编译阶段必须分析语法分析器的输出，以保证输入字符串符合语法分析器无法检查的那些规则。

考虑词法分析器和语法分析器的分工。每种语法分析方法只能处理一种形式的文法。为了适应所选择的分析方法，常常不得不改写初始文法。适于表达式的文法常常用结合律和优先级信息来构造

正则表达式和上下文无关文法的比较

正则表达式所描述的每一种结构都可以用上下文无关文法来描述。例如正则表达式(a|b)*abb和下述文法描述的语言皆为由a和b组成的以abb结尾的字母串：

$$A_0 \rightarrow aA_0 \,|\, bA_0 \,|\, aA_1\\ A_1 \rightarrow bA_2\\ A_2 \rightarrow bA_3\\ A_3 \rightarrow \epsilon$$

可以机械地把一个不确定的有穷自动机(NFA)转换成一个等价的上下文无关文法，该文法可以按照下列规则构造:

• 对NFA的每个状态 $i$，创建一个非终结符 $A_i$
• 如果状态 $i$ 遇见的输入符号 $a$ 转换到状态 $j$，则引入产生式 $Ai \rightarrow aA_j$
• 如果状态 $i$ 遇见的输入符号 $\epsilon$ 转换到状态j，则引入产生式 $A_i \rightarrow A_j$
• 如果状态 $i$ 是结束状态/终止状态，则引入产生式 $A_i \rightarrow \epsilon$
• 如果状态 $i$ 是开始状态，则 $A_i$ 是文法的开始符号

使用正则表达式而不用上下文无关文法定义语言的词法

• 语言的词法规则通常非常简单，不必用强大的文法来描述
• 对于记号，正则表达式比上下文无关文法提供了更简洁且易于理解的定义
• 从正则表达式可以自动地构造出有效的词法分析器，从任何文法都很难构造词法分析器
• 把语言的语法结构分成词法和非词法两部分为编译器前端的模块划分提供了方便的途径。

注意：正则表达式对描述标识符、常数和关键字等词法结构时最常用。另一方面，文法在描述括号配对、begin-end配对、if-then-else对应等嵌套结构时最常用。正则表达式不能描述这些嵌套结构

消除二义性

有些二义性文法可以通过改写来消除二义性。例子：消除“不匹配else”文法的二义性。

stmt -> if expr then stmt
    | if expr then stmt else stmt
    | other            

这里，other代表任何其他语句。复合条件语句

if E1 then if E2 then S1 else S2

具有二义性的，因为串if E1 then if E2 then S1 else S2有两棵分析树。

而一般规则是，每个else和前面最近的没有配对的then配对，当然这条避免二义性的规则可以直接并入文法中。

例如，可以把上述文法改写成下面的无二义性文法，其基本思想是：出现在then和else之间的语句必须是“已匹配”的，即中间语句不能以一个未匹配（或者说，开放）的then后面跟随任意的非else语句结束（也就是说，没有else与then进行匹配，即：开放）。一个已匹配的语句是一个不包含开放语句的if-then-else语句或者任何非条件语句。因此，按照上述思想改写后的文法如下：

        stmt -> matched_stmt
             | open_stmt
matched_stmt -> if expr then matched_stmt else matched_stmt
             | other
   open_stmt -> if expr then stmt 
             | if expr then matched_stmt else open_stmt

消除左递归

如果文法 $G$ 具有一个非终结符 $A$ 使得对某个字符串 $α$ 存在推导 $A \overset + \Rightarrow Aα$，则称 $G$ 是左递归的。自顶向下语法分析法不能处理左递归文法，因此需要一种消除左递归的变换。

左递归产生式 $A \rightarrow A α\,|\,β$ 可以由下面的非左递归产生式来代替:

$$A \rightarrow βA' \\ A' \rightarrow αA' \,|\, \epsilon$$

这种变换没有改变从 $A$ 推导出的字符串集合。这条规则适用于很多文法。

例子：考虑下面的算术表达式文法

E -> E + T | T
T -> T * F | F
F -> (E) | id

消除 E 和 T 的直接左递归(形如 $A \rightarrow A α$ 的产生式)，可以得到

E -> TE'
E' -> +TE'| e
T -> FT'
T' -> *FT' | e
F -> (E) | id

无论有多少 $A$ 产生式，都可以用下面的技术来消除直接左递归。首先，把 $A$ 产生式放在一起：

$A \rightarrow Aα_1 \,|\, Aα_2 \,|\, ... \,|\, Aα_m \,|\, β_1 \,|\, β_2 \,|\, ... \,|\, β_m$

其中，每个 $β_i$ 都不以 $A$ 开头。然后用下面的产生式代替 $A$ 产生式：

$$A \rightarrow β_1A' \,|\, β_2A' \,|\, ... \,|\, β_mA'\\ A' \rightarrow α_1A' \,|\, α_2A' \,|\, ... \,|\, α_mA' \,|\, \epsilon$$

变换后的非终结符 $A$ 与变换前的非终结符 $A$ 产生同样的字符串集合，但已经没有左递归了。这种方法可以从 $A$ 产生式和 $A'$ 产生式(假定 $α_i$ 都不等于 $\epsilon$ )消除直接左递归，但不能消除包括两步或多步推导的左递归。例如，考虑文法

$$S \rightarrow Aa \,|\, b\\ A \rightarrow Ac \,|\, Sd \,|\, \epsilon$$

非终结符 $S$ 是左递归的，因为 $S \Rightarrow Aa \Rightarrow Sda$，但不是直接左递归。

下面的算法4.1能够系统地消除文法中的左递归。该算法对于所有无循环推导($A \overset + \Rightarrow Aα$的推导，相当于图中的环)和 $\epsilon$ 产生式(形如 $A\rightarrow\epsilon$ 的产生式)的文法都有效。循环推导和 $\epsilon$ 产生式都可以系统地从文法中消除掉。

注意：因为有 $\epsilon$ 产生式，算法不一定有效，但在这种情形下产生式 $A \rightarrow \epsilon$是无害的

提取左因子

提取左因子是一种对产生适合预测分析的文法非常有用的文法变换。提取左因子的基本思想是：当不清楚应该用两个选择中的哪一个来替换非终结符 $A$ 时，可改写 $A$ 产生式来推迟这种决定，制导看见足够多的输入能做出正确的选择为止。

例如，有如下两个产生式：

stmt -> if expr then stmt else stmt
      | if expr then stmt

看到输入记号 $if$ 时，不能立即立刻决定选择哪个产生式来扩展 $stmt$ 。一般地，如果$A\rightarrow αβ_1|αβ_2$ 是 $A$ 的两个产生式，输入字符串从 $α$ 导出的非空串开始，不知道是用 $αβ_1$来扩展 $A$ 还是用 $αβ_2$ 。然而，可以通过先将 $A$ 扩展到 $αA'$ 来推迟这个决定。然后，扫描完由 $α$ 导出的输入字符串后，再把$A'$ 扩展成 $β_1$ 或 $β_2$，亦即提取左因子。这样的变换以后，原来的产生式变为：

$$A \rightarrow αA' \\ A'\rightarrow β_1 \,|\, β_2$$

问题的解决

串首终结符与串首终结符集

串首终结符：串首第一个符号，并且是终结符。简称首终结符

给定一个文法符号串 $α$， $α$ 的串首终结符集 $FIRST(α)$ 被定义为可以从 $α$ 推导出的所有串首终结符构成的集合。

对于 $\forall \alpha\in(V_T\cup V_N)^+,FIRST(\alpha)=\{a\,|\,\alpha\Rightarrow^*a\beta,a\in V_T,\beta\in(V_T\cup V_N)^*\}$

如果 $α \Rightarrow^* ε$，那么 $ε$ 也在 $FIRST(α)$ 中。

比如：

FOLLOW集

$FOLLOW(A):$ 可能在某个句型中紧跟在A后面的终结符 $a$ 的集合

$FOLLOW(A)=\{a\,|\,S\Rightarrow^*\alpha Aa\beta,a\in V_T,\alpha,\beta\in(V_T\cup V_N)^*\}$

如果 A 是某个句型的的最右符号，则将结束符 $ 添加到 $FOLLOW(A)$中

比如求 $FOLLOW(F)$，在5个式子中，非终结符 $F$ 后面的非终结符只有 $T'$ 所以将 $FOLLOW(T')$ 加入 $FOLLOW(F)$，同时由于 $T'\rightarrow*F\,T'$，将 $*$ 加入 $FOLLOW(F)$。

可选集SELECT

对于产生式 $A\rightarrow \alpha$

• 如果 $\epsilon \notin FIRST(\alpha)$，那么 $SELECT(A\rightarrow \alpha) = FIRST(\alpha)$
• 如果 $\epsilon \in FIRST(\alpha)$，那么 $SELECT(A\rightarrow \alpha) = (FIRST(\alpha)-\{\epsilon\})\cup FOLLOW(A)$
• $FOLLOW(\epsilon)=\{\epsilon\}$

LL(1)文法

• 第一个“L”表示从左向右扫描输入

• 第二个“ L”表示产生最左推导

• “1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作

$FIRST(),FOLLOW(),SELECT()$ 与预测分析

X	FIRST(X)	FOLLOW(X)
$E$	$( id$	$\$ )$
$E '$	$+ ε$	$\$ )$
$T$	$( id$	$+ ) \$$
$T '$	$* ε$	$+ ) \$$
$F$	$( id$	$* + ) \$$

递归的预测分析法

递归的预测分析法是指：在递归下降分析中，根据预测分析表进行产生式的选择

根据每个非终结符的产生式和LL(1)文法的预测分析表**，**为每个非终结符编写对应的过程

对于 $<DECLISTN>\rightarrow\epsilon$ ，那么其 $SELECT$ 集 $SELECT(4)=FOLLOW(<DECLISN>)$，依赖于 $FOLLOW(<DECLIST>)=\{:\}$ ，$<STLISTN>\rightarrow\epsilon$ 同理。

递归程序如下：

非递归的预测分析法

栈从左到右依次是栈顶到栈底

1. 取出栈顶元素，读入输入的最开始的字符，查表，如果表为空，报错，不为空则按照生成式进行替换。
2. 如果栈顶出现终结符，若该终结符与输入的终结符不一样，报错，否则两者同时出栈
3. 直到栈和输入都为 $，匹配成功。

总结

自底向上的语法分析

从分析树的底部 (叶节点) 向顶部 (根节点) 方向构造分析树

可以看成是将 输入串w 归约为 文法开始符号S 的过程

自底向上的语法分析采用最左归约方式（反向构造最右推导）

在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串 $β$ 进行归约为止，然后，它将β归约为某个产生式的左部。

语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止。

移入-归约分析中存在的问题

造成错误的原因：错误地识别了句柄，或者说，使用了错误的句柄。这个问题与自顶向下的产生式选择问题有类似之处。本应使用（3）的地方使用了（2）

LR 分析法

• L： 对输入进行从左到右的扫描

• R：反向构造出一个最右推导序列

• $LR(k)$ 分析

  • 需要向前查看 k 个输入符号的 LR分析

• $k = 0$ 和 $k = 1$ 这两种情况具有实践意义，当省略 $(k)$ 时，表示 $k =1$

自底向上分析的关键问题是什么？如何正确地识别句柄

句柄是逐步形成的，用“状态”表示句柄识别的进展程度

LR 分析表的结构

$sn$：将符号 $a$、状态 $n$ 压入栈，$rn$：用第 $n$ 个产生式进行归约（状态和符号出栈，归约结果入栈）。GOTO下的数字 $n$ 表示将状态 $n$ 入栈。

例如，文法：

$$S\rightarrow BB\\ B\rightarrow aB\\ B\rightarrow b$$

输入为：$bab$ ，使用上表进行归约。

约定从左到右为栈底到栈顶。

1. 初始时，状态栈为 $0$ ，符号栈为 $\$$ ，剩余输入为 $bab\$$ 。

2. 对于状态 0，输入 b，查表为 s4，将符号 b、状态4入栈。

   状态栈 04

   符号栈 $b

   剩余 ab$

3. 对于状态4，符号b，查表为 r3，将状态与符号出栈，根据文法第三行，将b归约为B，入栈

   状态栈 0

   符号栈 $B

   剩余 ab$

4. 对于状态0，符号B，查表为 GOTO 2，将状态2入栈

   状态栈 02

   符号栈 $B

   剩余 ab$

5. 对于状态2，输入a，查表为s3，将状态3、输入a入栈

   状态栈 023

   符号栈 $Ba

   剩余 b$

6. 对于状态3，输入b，查表为s4，将状态4、输入b入栈

   状态栈 0234

   符号栈 $Bab

   剩余 $

7. 对于状态4，符号b，查表为r3，将状态4、符号b出栈，符号B入栈

   状态栈 023

   符号栈 $BaB

   剩余 $

8. 对于状态3，符号B，查表为GOTO 6，将状态6入栈

   状态栈 0236

   符号栈 $BaB

   剩余 $

9. 对于状态6，输入$，查表为r2，将状态36、符号aB出栈，B入栈

   状态栈 02

   符号栈 $BB

   剩余 $

10. 对于状态2，符号B，查表为 GOTO 5，将状态5入栈

    状态栈 025

    符号栈 $BB

    剩余 $

11. 对于状态5，符号B，查表为r1，将状态25、符号BB出栈，符号S入栈，完成

    状态栈 0

    符号栈 $S

    剩余 $

规律：复合栈中，状态栈与符号栈元素数不一样时，优先使用两个栈顶状态与终结符将状态栈进行补齐。补齐时尝试使用栈顶元素进行归约，无法归约则使用栈顶元素与输入进行读入。

也就是说，尝试进行 $sn,rn,GOTO \,n$的循环，一轮循环中，可能没有 $sn$，也可能没有 $rn,GOTO \, n$

LR(0)项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目），形如：$A\rightarrow\alpha_1·\alpha_2$ 。

项目描述了句柄识别的状态。

• $S\rightarrow·\,bBB$ ，点后跟着终结符，称为移进项目
• $S\rightarrow b\,·BB$，点前后都有非终结符，称为待约项目
• $S\rightarrow bB\,·B$，待约项目
• $S\rightarrow bBB\,·$ ，点后没有符号，称为归约项目
• 产生式 $A→ε$ 只生成一个项目 $A→ · $

增广文法 (Augmented Grammar)

如果 $G$ 是一个以 $S$ 为开始符号的文法，则 $G$ 的增广文法 $G'$ 就是在 $G$ 中加上新开始符号 $S'$ 和产生式 $S' → S$ 而得到的文法。引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

例：

项目分类

初始项目就是开始符号在左的移进项目。接收项目就是开始符号在左的归约项目

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目

比如 $A\rightarrow\alpha \,·X\beta$ 的后继项目是 $A\rightarrow \alpha X\,·\beta$

等价项目

对于(0)、(2)，$S'$ 在等待 $S$ ，$S$ 在等待 $v$，那么(0)跟(2)是等价的。

可以把等价的项目组成一个项目集 ( $I$ ) ，称为项目集闭包 (Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态。

圆点后面有非终结符时就有等价项目。

LR(0)自动机举例

其中对于 $I_0$ 中的 $S'\rightarrow ·S$，识别出 S 之后，归约进程可以前进一步到 $I_1$，我们就将该项目的后继项目放入 $I_1$ 中，且该项目是归约项目，所以集合（闭包）中不再有其他项目，也不会有后继闭包。

对于 $S\rightarrow ·BB$，识别出 B 后可以前进一步到 $I_2$，将其后继项目 $S\rightarrow B\,\cdot B$ 放入闭包，同时由于其是待约项目，所以等价项目也放入该项目集闭包中。

对于剩下的两个项目，同理。

遍历完 $I_0$ 中项目后，遍历后续其他闭包的项目，直到完成所有项目。

完成后，针对转换图画出分析表。

对于 $I_0$（状态0），遇到终结符 a 进入状态3，将 终结符a与状态3入栈， 遇到 终结符S ，进入状态2。以此类推。

对于归约项目，比如 $I_4$，$B\rightarrow b\,·$，即(3)，所以就是用(3)进行归约。

算法见PPT第六讲P40

冲突

对于$I_2$，有一个归约项目，有一个待约项目。对于 $E\rightarrow T\,·$ ，应该用 r2 进行归约，对于下一个项目，应该入栈 $*$ 并跳转到状态7（进行移进）。称为移进/归约冲突。

$I_2$ 有两个归约选择，即 归约/归约冲突

SLR分析

LR(0)分析的问题在于它没有向前考虑，SLR向前考虑了一位（也就是SLR(1)）。

可以发现 $*$ 不在 $FOLLOW(E)$ 中，所以如果把 T 归约成 E，后面也不可能会连接有 $*$，所以我们不应该进行归约。

样例

对于这个归约/归约冲突，对于移入符号b，在 $FOLLOW(T)$ 中，所以用 $T\rightarrow \epsilon$ 即 r2归约，同理移入符号d用r4归约。

同样对上面移入/归约冲突，对于移入符号 $*$，在集合 $\{a_1,a_2...a_m\}$ 中（也就是$\{*\}$，所以选择移入。

LR(1)分析法

SLR只是简单地考察下一个输入符号b是否属于与归约项目 $A→α$ 相关联的 $FOLLOW(A)$，但 $b∈FOLLOW(A)$ 只是归约 $α$ 的一个必要条件**，**而非充分条件。也就是说， $b∈FOLLOW(A)$ 则一定可以归约，但可以归约却不一定满足 $b∈FOLLOW(A)$ 。

LR(1)分析法的提出

对于产生式 $A→α$ 的归约，在不同的使用位置，A会要求不同的后继符号

对于 $S\rightarrow L=R\,·,\$$，这意味着只有栈顶为 $\$$ 时才将 $L=R$ 归约为 $S$，此处我们应当按照归约的方式去理解，因为 $R$ 是产生式 $S\rightarrow L=R$ 的最后一个符号，也就是说此处的R后面一定是$。同样，对于 $L\rightarrow *R\,\cdot ,=$，意味着只有栈顶为 $=$ 时才将 $*R$ 归约为 $L$，这是因为在如图的树中，该位置的R后面一定是 =。

将一般形式为 $[A→α·β, a]$ 的项称为 LR(1) 项，其中 $A→αβ$ 是一个产生式，$a$ 是一个终结符(这里将$视为一个特殊的终结符)，它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)

• LR(1) 中的1指的是项的第二个分量的长度

• 在形如 $[A→α·β, a]$ 且 $β ≠ ε$ 的项中（也就是对于待约项目与移入项目），展望符 $a$ 没有任何作用

• 形如 $[A→α·, a]$ 的项（归约项目）在只有在下一个输入符号等于 $a$ 时才可以按照 $A→α$ 进行归约

• 这样的 $a$ 的集合总是 $FOLLOW(A)$ 的子集，而且它通常是一个真子集

等价LR (1) 项目

样例

与LR (0) 类似，从产生式0的待约项目 $S'\rightarrow ·\,S,\$$开始，将其等价项目、以及等价项目的等价项目加入，作为项目集闭包 $I_0$，读入 $L$ 时， $I_0$ 中有两个产生式符合，即：$S\rightarrow ·L=R,\$$，$R\rightarrow ·L,\$$，将其放入 $I_2$，且这两个项目没有等价项目。

总结：非终结符的情况往右上写，终结符往右下写，遍历每个闭包中产生式右部的首个点后非终结符以寻找可能的移入，递归地找出所有等价项目放入闭包。

当然，展望符也可以合并，如：

如果除展望符外，两个LR (1) 项目集是相同的，则称这两个LR(1)项目集是同心的：

如 $I_4$ 与 $I_{11}$，$I_8$ 与 $I_{10}$

分析表构造算法

PPT 第七章20-24.

 

LALR分析法

LR (1) 项目集有很多是同心的，我们或许可以进行简化

LALR ( lookahead-LR ) 分析的基本思想

寻找具有相同核心的LR (1) 项集，并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合（就是合并同心项目集）。然后根据合并后得到的项集族构造语法分析表。

如果分析表中没有语法分析动作冲突**，**给定的文法就称为LALR (1) 文法，就可以根据该分析表进行语法分析。

合并同心项集不会产生移进-归约冲突，但可能存在归约-归约冲突，我们可以进行遍历-回溯。

其实被合并的$I_{10}-I_{13}$是一定会经过一个等号的，所以他们的展望符中不会有等号，但是 $I_{4、5、7、8}$ 展望符就会有等号。

LALR (1) 的特点

• 形式上与 LR (1) 相同

• 大小上与 LR (0) / SLR 相当

• 分析能力介于 SLR 和 LR(1) 二者之间

  SLR<LALR(1)<LR(1)

  • 合并后的展望符集合仍为FOLLOW集的子集

 

第五章 语法制导翻译

什么是语法制导翻译

语义分析与中间代码生成通常放在一起实现，称为语义翻译，把语法分析与语义翻译放在一起实现称为语法制导翻译。

语法制导翻译使用CFG（上下文无关文法）来引导对语言的翻译，是一种面向文法的翻译技术。

语法制导翻译的基本思想

如何表示语义信息？

为上下文无关文法中的文法符号（终结符非终结符）设置语义属性，用来表示语法成分对应的语义信息

语义属性其实是值的集合。

如何计算语义属性？

文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的

对于给定的输入串 x ，构建 x 的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值

将语义规则同语法规则（产生式）联系起来要涉及两个概念

• 语法制导定义(Syntax-Directed Definitions, SDD)

• 语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

SDD

• SDD是对CFG的推广。

  • 将每个文法符号和一个语义属性集合相关联（并非一对一）
  • 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值。

• 如果 $X$ 是一个文法符号，$a$ 是 $X$ 的一个属性，则用 $X.a$ 表示属性 $a$ 在某个标号为 $X$ 的分析树结点上的值。

• 是关于语言翻译的高层次规格说明，隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序

SDT

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内。

一个语义动作在产生式中的位置决定了这个动作的执行时间。

可以看作是对SDD的一种补充，是SDD的具体实施方案。显式地指明了语义规则的计算顺序，以便说明某些实现细节。

比如第一行，就意味着计算出T的type之后就可以用其计算L的inh。第二行意味着右部计算完成（其实就是int）后就可以计算出（得出）T的type。

语法制导定义SDD

• SDD是对CFG的推广。

  • 将每个文法符号和一个语义属性集合相关联（并非一对一）
  • 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值。

• 文法符号的属性

  • 综合属性 (synthesized attribute)
  • 继承属性 (inherited attribute)

综合属性(synthesized attribute)

在分析树结点 N上的非终结符 A 的综合属性只能通过 N的子结点 或 N本身 的属性值来定义。

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则

val就是E的一个综合属性。

继承属性(inherited attribute)

在分析树结点 N上的非终结符 A 的继承属性只能通过 N的父结点、N的兄弟结点或 N本身 的属性值来定义。

终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值。

inh就是L的一个继承属性。

根据表的规则构造分析树。

属性文法 (Attribute Grammar)

• 一个没有副作用的SDD有时也称为属性文法

• 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

• SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值

• 按照什么顺序计算属性值？

  • 语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图(Dependency Graph)

• 依赖图是一个描述了分析树中结点属性间依赖关系的有向图

• 分析树中每个标号为 $X$ 的结点的每个属性a都对应着依赖图中的一个结点

• 如果属性 $X.a$ 的值依赖于属性 $Y.b$ 的值，则依赖图中有一条从 $Y.b$ 的结点指向 $X.a$ 的结点的有向边

$L.in=T.type$，所以图中有一条从T的type指向L的in的边。

注意的一点是$L_1.in=L.in$，意味着子节点的in依赖于父节点的in。

此外addtype(id.lexeme,L.in)，我们将其看做是定义产生式左部非终结符L的虚综合属性的规则（也就是说实际上并没有这个综合属性），式中用到了子节点的lexeme与自身的in，所以各有一条边指向这个虚综合属性。

属性值的计算顺序

拓扑排序。

对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值

对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值。

A的综合属性S与B的继承属性有循环关系，无法进行拓扑排序。

S-属性定义与L-属性定义

S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值。S-属性定义可以在自底向上的语法分析过程中实现。

L-属性定义

L-属性定义 (也称为L属性的SDD或L-SDD) 的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左(因此称为L属性的，L是Left的首字母)

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：

假设存在一个产生式 $A→X_1X_2…X_n$，其右部符号 $X_i (1\leq i\leq n)$ 的继承属性仅依赖于下列属性**：**

• A的继承属性，而不依赖于综合属性

  • 这是因为父节点的综合属性可能依赖于子节点的属性，也就包括子节点的继承属性，如果子节点的继承属性依赖于父节点的综合属性就会成环
  • 

• 产生式中 $X_i$ 左边的符号 $X_1, X_2, … , X_{i-1}$ 的属性

• $X_i$ 本身的属性，但 $X_i$ 的全部属性不能在依赖图中形成环路

每个S-属性定义都是L-属性定义。

对于$T'.inh=F.val$，对应到产生式中$T'$依赖于左边的$F$，所以存在 $F$ 指向 $T'$ 的边，不违反L-SDD的规则（也就是满足上面的第二条）。

对于$T'_1.inh=T'.inh\times F.val$，同理，$T',F$ 都在产生式中$T'_1$的左边，所以也满足要求。

语法制导翻译方案SDT

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在大括号内。

一个语义动作在产生式中的位置决定了这个动作的执行时间。

可以看作是对SDD的一种补充，是SDD的具体实施方案。显式地指明了语义规则的计算顺序，以便说明某些实现细节。

比如第一行，就意味着计算出T的 type 之后就可以用其计算L的inh。第二行意味着右部计算完成（其实就是int）后就可以计算出（得出）T的 type。

SDT可以看作是SDD的具体实施方案

本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在语法分析过程中实现

• 基本文法可以使用LR分析技术，且SDD是S属性的

• 基本文法可以使用LL分析技术，且SDD是L属性的

S-SDD转换为SDT

S属性的SDD中仅有综合属性，也就是只有所有子节点的综合属性计算完成后才能计算父节点的综合属性，所以计算改综合属性的语义动作要放在产生式的最右面，所以：将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后。

如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现

扩展的LR语法分析栈

将语义动作中的抽象定义式改写成具体可执行的栈操作：

例：在自底向上语法分析栈中实现桌面计算器

例如：输入 $3*5+4$，初始时栈为（ _ 代表无）（注意下方是栈顶，上方为栈底，PPT如此）

状态	符号	属性
0	$	_

0号状态读入数字，为digit，后进行移入，到达状态5，栈为：

状态	符号	属性
0	$	_
5	d	3

然后输入指针指向下一个符号$*$，看到5号状态是一个规约状态，将d归约为F，对应产生式（7），不过该产生式没有任何动作，因为根据该产生式的语义规则，F的属性值就等于digit的属性值，所以我们直接将栈顶的5号状态与符号d出栈，将F入栈，初始状态遇到F进入3号状态：

状态	符号	属性
0	$	_
3	F	3

对于栈顶的3号状态，也是规约状态，也就是应用5号产生式，语义规则为 $T.val=F.val$，于是将F出栈，T入栈，0号状态遇到T后进入状态2，状态2遇到下一个符号 $*$ 采取移入动作进入7号状态，*没有属性值：

状态	符号	属性
0	$	_
2	T	3
7	*	_

继续读入下一个符号5，属于符号d，状态7遇到符号d采取移入，入栈并进入状态5：

状态	符号	属性
0	$	_
2	T	3
7	*	_
5	d	5

5号状态进行归约，5号状态符号d出栈，F入栈，7号状态遇到F进入10号状态，规约状态，将栈中的 $T*F$ 归约为 $T$，对应产生式（4），按照其语义动作，$3\times 5=15$放在原来3的位置（top-2）然后将 $T,*,d$ 出栈，$T$ 入栈，0号状态遇到 $T$进入2号状态：

状态	符号	属性
0	$	_
2	T	15

2号状态第一个产生式是一个归约动作，将T归约为E，对应产生式（3），将T出栈，E入栈，0号状态遇到E进入1号状态：

状态	符号	属性
0	$	_
1	E	15

1号状态遇到下一个输入符号+进入状态6，6号状态遇到下一个输入4进行移入，进入状态5（这里有两次移入）：

状态	符号	属性
0	$	_
1	E	15
6	+	_
5	d	4

状态5进行归约将（5，d）出栈，符号F入栈，6号状态遇到F进入3号状态，F出栈，T入栈，6号状态遇到符号T进入9号状态，遇到输入符号为$（也就是输入的最后），进行归约，将$E+T$ 进行相应计算、出栈、E入栈，0号状态遇到E进入1号状态：

状态	符号	属性
0	$	_
1	E	19

1号状态遇到$，进入$E'$，成功接收。

L-SDD转换为SDT

将L-SDD转换为SDT的规则

• 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上

• 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

L-属性定义的SDT 实现

如果一个L-SDD的基本文法可以使用LL分析技术，也就是说，满足LL文法的规则，那么它的SDT可以在LL或LR语法分析过程中实现。

LL文法：具有相同左部的产生式的SELECT集不相交

在非递归的预测分析过程中进行语义翻译

注意继承属性与综合属性的计算时机是不同的，综合属性是要子节点全部计算完成后才能计算，而继承属性是在即将出现的时候进行计算。所以将两种属性存放在不同的记录中。

假设输入为 $3*5$，规定从左到右为栈顶到栈底，初始时分析栈中只有初始符号T，T无动作记录，但有综合记录（$T.val$）：

我们将T出栈，但是Tsyn不能出栈，因为要等其所有子节点计算完成，将产生式（1）右部部分入栈：

注意综合记录、动作记录也需要入栈。栈顶为终结符F，使用产生式（4）替换为 $digit\{a_6\}$，此时栈顶digit就可以与输入的数字匹配，下一个输入为 $*$，可以将 digit出栈，出栈前根据动作$\{a_6\}$ 将digit的lexval进行备份，digit出栈前栈为：

此时栈顶为动作 $a_6$，对应的动作是将digit属性值给F的综合属性计算并赋值，所以给 $Fsyn$ 赋值为 $val=3$，如上图，然后将 $a_6$ 出栈。然后栈顶为Fsyn，可以出栈，但由于动作 $a_1$ 中 $T'$ 的继承属性要用到 $Fsyn$，所以将Fsyn的值保存到 $a_1$，然后出栈，出栈前的栈：

出栈后栈顶为 $a_1$，对应的操作是将 $F.val$ 赋值给 $T'.inh$，然后出栈，出栈前的栈：

出栈后栈顶为 $T'$，对应产生式（2），将 $T'$ 出栈，产生式右部及记录入栈，而因为 $a_3$ 要使用 $T'.inh$，所以将该值赋值过去，此时栈顶 $*$ 就可以与输入匹配，下一个输入为5：

栈顶为F，根据产生式（4），将F出栈， $digit\{a_6\}$ 入栈，栈顶digit与输入的5匹配，将属性 $digit.lexval=5$ 备份到 $a_6$ 后出栈，输入指向下一个字符为 $，digit出栈：

$a_6$ 的动作属性就是给Fsyn的val赋值，如上图，此后 $a_6$ 出栈，Fsyn也已经计算出来，将 $Fval$ 备份到 $a_3$，出栈：

$a_3$ 语义代码是进行乘法计算后给 $T'_1$ 赋值，出栈，栈顶为 $T'$ ，使用产生式（3），相当于将栈顶替换为 $a_3$ ，如下：

$a_5$ 给 $T'_1syn$ 赋值后出栈，而 $T'_1syn$ 出栈前将属性备份到 $a_4$ ，如上，出栈后栈顶为 $a_4$，进行赋值，如下：

然后 $a_4$ 出栈，同时 $T'syn$ 值保存到 $a_2$ 后出栈，$a_2$ 对 $Tsyn$ 赋值后出栈，如下：

此时 $Tsyn.val$ 计算出来了，可以出栈，此时栈中 $ 与输入匹配，计算完成。

总结

分析栈中的每一个记录都对应着一段执行代码，具体而言。综合记录出栈时，要将综合属性值复制给后面特定的语义动作。变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作。

也就是说：

 

第六章 中间代码生成

类型表达式

基本类型是类型表达式，如integer、real、char、boolean、type_error (出错类型)、void (无类型)。

可以为类型表达式命名，类型名也是类型表达式

将类型构造符 (type constructor) 作用于类型表达式可以构成新的类型表达式

• 数组构造符array
  • 若 $T$ 是类型表达式，则 $array(I,T)$ 是类型表达式 ( $I$ 是一个整数 )
  • 也就是 $I$ 个 $T$ 类属性
  • 
• 指针构造符pointer
  • 若 $T$ 是类型表达式，则 $pointer(T)$ 是类型表达式，它表示一个指针类型\
• 笛卡尔乘积构造符 $\times$
  • 若 $T_1$ 和 $T_2$ 是类型表达式，则笛卡尔乘积 $T_1 \times T_2$ 是类型表达式
• 函数构造符 $→$
  • 若 $T_1、T_2、…、T_n$ 和R是类型表达式，则 $T_1\times T_2 \times…\times T_n→ R$ 是类型表达式
  • $T_i$ 为函数参数， $R$ 为返回值类型
• 记录构造符record
  • 若有标识符 $N_1 、N_2 、…、N_n$ 与类型表达式 $T_1 、T_2 、…、T_n$ ， 则 $record((N_1\times T_1 )\times( N_2\times T_2)\times(N_n\times T_n))$ 是一个类型表达式
  • 这表示一个记录，有n个名为 $N_i$ 的字段，名为 $T_i$ 的标志符

声明语句的翻译

局部变量的存储分配

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址

• 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)

• 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址

名字的类型和相对地址信息保存在相应的符号表记录中

样例

输入：real x; int i;：

首先判断是不是LL(1)，即判断相同左部的SELECT集是否有重叠。

初始时树的根节点为 $P$，子节点为 $\{a_1\}$ 和 $D$，其中 $\{a_1\} = \{offset=0\}$，从子节点从左到右执行，$\{a_1\}$ 初始化 $offset = 0$，然后考虑非终结符 $D$，当前输入符号为 real，使用产生式2，子节点为 $T,id,;,\{a_2\},D$，其中 $\{a_2\} = \{enter(...);offset=offset+T.width;\}$，如下：

此时栈顶为 $T$，对于输入的 real，使用产生式4，子节点为 $B\{a_3\}C\{a_4\}$，语义动作含义同上。此时栈顶为 $B$，对于输入的real，使用产生式7，子节点为 $real\{a_5\}$，如下：

此时栈顶 real 与输入相匹配，将栈顶 real 出栈，输入指向下一个表达式为 $x$，且栈顶为 $\{a\}=\{B.type=real;B.width=8;\}$，即将B的type与width进行赋值后，出栈，栈顶为B，出栈，栈顶为语义动作 $\{a\}=\{t=B.type;w=B.width;\}$，将B的变量type，width赋值给变量t与w，然后栈顶为C，对于输入x，是一个id，在产生式8的SELECT集中，使用产生式8，子节点为 $\epsilon,\{a\}$，如下：

空串直接忽略，对于 $\{a\}=\{C.type=t;C.width=w;\}$，使用变量给C相应的变量赋值。此时栈顶为 C 右侧的语义动作 $\{T.type=C.type;T.width=C.width;\}$，给T的相应属性赋值，如下：

然后栈顶为 T 右侧节点 id，与 x 相匹配，继而下一个节点与下一个输入分号匹配，下一个输入为 int，栈顶为语义动作 $\{enter(...);offset=offset+T.width\}$，向符号表中添加记录并给 $offset$ 赋值，此时栈顶为 D，对于输入 int，使用产生式2，子节点为 $T,id,;,\{a_2\},D$，过程同理。

下例同理：

 

简单赋值语句的翻译

赋值语句的SDT

综合属性 code 表示符号对应的三地址码，addr表示表达式值的存放地址。

比如 $E \rightarrow id \{E.addr=lookup(id.lexeme;if\,E.addr==nil\,then\,error;E.code='';\}$，也就是说，查询符号表中标志符id的存放地址，如果没找到就说明出现了未声明就使用的错误，对于该赋值，不涉及任何运算，没有三地址指令。

对于 $E\rightarrow (E_1)$，容易理解。

对于 $E\rightarrow E_1+E_2$，首先生成临时变量，存放 $E_1+E_2$ 的值，即使用 newtemp() 函数，将返回值赋值给$E.addr$，对于 $E.code$，为 $E_1,E_2$ 以及 $E_1.addr+E_2.addr$ 赋值给 $E.addr$ 的三地址指令，其中 $||$ 为表示连接的符号，其余的同理。

对于 $S\rightarrow id=E;$，调用 $lookup()$ 查询 id 的地址赋值给p，$S.code$ 为 $E.code$ 连接上将 $E.addr$ 赋值给 p 对应的三地址指令。

增量翻译 (Incremental Translation)

我们发现对于code属性，会调用右侧表达式的code，右侧表达式计算code时可能还会调用另一个生成式右侧表达式的code，造成效率较低。而我们发现计算code就是在右侧表达式code的连接之后再连接一个三地址表达式。

我们可以不使用code属性，而是直接在已经生成的三地址码后面追加三地址指令，这样在增量方法中，gen()不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后。

样例

第四章中介绍过此SDT的基础文法可以使用LR分析技术，且所有语义动作位于产生式右部末尾，所以可以采用自底向上的方式进行翻译。

初始时，输入为x，状态栈中存放初始状态0号状态以及符号栈中存放 $（栈底标记）。

0号状态对于输入 id采取移入动作，进入状态2，将$[2,id,x]$ 入栈，输入指针指向下一个输入 $=$，状态2对于等号进行移入，进入状态3，将 $[3,=]$ 入栈，输入指针指向下一个输入 $($ ，3号状态对于左括号采取移入动作，进入状态6，将 $[6,(]$ 入栈，输入指针指向下一个输入a，状态6对于a也就是id采取移入动作，进入状态7，将 $[7,id,a]$ 入栈，输入指针指向下一个输入 $+$，最终栈如图：

7号状态为规约状态，采用产生式6进行归约，将 $[7,id,a]$ 出栈，E入栈，同时执行其语义动作，将 $E.addr$ 赋值为符号表中 a 的地址。6号状态对于E采取移入的动作进入状态12，对于输入符号 $+$，采取移入动作进入状态9，将 $[9,+]$ 入栈，输入指针指向下一个输入 ，即为 id，状态9对于输入 id采取移入动作，进入状态7，将 $[7,id,b]$ 入栈，输入指针指向下一个输入 $)$ 。

同样7号状态进行归约，$[7,id,b]$ 出栈，E入栈，同时执行其语义动作，将 $E.addr$ 赋值为符号表中 b 的地址。栈顶状态9对于E采取移入动作，进入状态13，$[13,E,b]$ 入栈，此处b指的也是b的地址，状态13为归约状态，采用产生式2进行归约，我们首先调用 newtemp()生成一个临时变量 $t_1$，将其地址赋值给 $E.addr$，然后生成三地址指令，其中 $E_1.addr$ 就是a的地址，$E_2.addr$ 是b的，于是指令就是 $t_1=a+b$，于是 $E_1,+,E_2$出栈，E入栈，状态栈栈顶状态6对于E采取归约动作，进入状态12，于是$[12，E，t_1]$ 入栈，此时输入仍然为 $)$，状态12对于该输入采取归约动作，进入状态15，$[15,)]$ 入栈，输入指针指向下一个输入 $*$。

状态15是规约状态，采用产生式5进行归约，进行地址赋值后，将栈顶三层出栈，E入栈，状态3对于E采取移入动作，进入状态4，即 $[4,E,t_1]$ 入栈：

状态4对于当前输入 $*$ 采取移入动作，进入状态10，$[10,*]$ 入栈，输入指针指向下一个输入 $c$，状态10对于id采取移入动作，进入状态7，即 $[7,id,c]$ 入栈，输入指针指向下一个输入 $;$，状态7同样采用产生式6进行归约，id出栈，E入栈，状态栈顶的状态10对于E采取移入动作进入状态14，$[14,E,c]$ 入栈，此处c指的也是地址。

状态14采用产生式3进行归约，我们首先调用 newtemp()生成一个临时变量 $t_2$，将其地址赋值给 $E.addr$，然后生成三地址指令，其中 $E_1.addr$ 就是 $t_1$ 的地址，$E_2.addr$ 是c的，于是指令就是 $t_2=t_1+c$，于是 $E_1,+,E_2$出栈，E入栈，状态3对于E采取移入操作，进入状态4，$[4,E,t_2]$ 入栈，对于下一个输入 $;$，状态4采取移入动作，进入状态8，$[8,;]$ 入栈，输入指针指向下一个输入 $。

状态8采用产生式1进行归约，查询符号表中 x 的地址并给 p赋值，然后产生三地址指令，其中 $E.addr$ 为$t_2$的地址，所以指令为 $x=t_2$，然后将栈顶的四层出栈，S 入栈，状态0对于S采取移入动作，进入状态1，为接收状态，此时输入为 $，栈中为开始符号S，可以接收。

最终的三地址码就是：$t_1=a+b$，$t_2=t_1+c$， $x=t_2$ 。

 

数组引用的翻译

赋值语句的基本文法

$S \rightarrow id = E; \,|\, L = E;$

$E \rightarrow E_1 + E_2 \,|\, -E_1 \,|\, (E_1) \,|\, id \,|\, L$

$L \rightarrow id [E] \,|\, L_1 [E]$

引入新的符号L，L可以生成一个标志符连接上一个数组下标表达式的序列，也就是说，L表示的是一个数组元素。

L的综合属性：

• L.type：L生成的数组元素的类型

• L.offset：指示一个临时变量，该临时变量用于累加公式中的$i_j × w_j$项，从而计算数组引用的偏移量

• L.array：数组名在符号表的入口地址

第二个产生式指出了一个数组下标就是一个表达式。

第一个产生式则指出我们能够为数组元素赋值。

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址。

数组元素寻址 (Addressing Array Elements )

如：

如 $length(a[i_1])=4\times 5\times 8$，因为整形长度为4。

带有数组引用的赋值语句的翻译

数组引用的SDT

假设 $type(a)= array(3, array(5, array(8, int) ) )$，翻译语句片段 $a[i_1][i_2][i_3]$。

我们使用自底向上的翻译，从左到右扫描符号串，读入 $a[i_1]$ 后，可以归约为非终结符L，通过查询符号表可以确定a的类型表达式与基地址，确定了公式中的base与 $i_1$，然后需要确定 $w_1$

L的综合属性：

• L.type：L生成的数组元素的类型

• L.offset：指示一个临时变量，该临时变量用于累加公式中的 $i_j × w_j$ 项，从而计算数组引用的偏移量

• L.array：数组名在符号表的入口地址

$w_1=int.width\times 5\times 8$，其中 L 对应的 $type=array(5,array(8,int))$，

对于该树，我们在扫描一遍，自底向上的使用语义动作构建三地址表达式：

控制流语句及其SDT

控制流语句的基本文法

三种控制流：顺序、分支、循环，第四行给出了基本文法（不是全部，仅作示例）

控制流语句的代码结构

布尔表达式B被翻译成由跳转指令构成的跳转代码，例如：

$S \rightarrow if\,\, B \,\, then \,\, S_1 \,\, else \,\, S_2$

继承属性

• S.next：是一个地址，该地址中存放了紧跟在S代码之后的指令(S的后继指令)的标号。

• B.true：是一个地址，该地址中存放了当B为真时控制流转向的指令的标号。

• B.false：是一个地址，该地址中存放了当B为假时控制流转向的指令的标号。

以上属性中，指令的标号标识一条三地址指令

控制流语句的SDT

其中：

• newlabel(): 生成一个用于存放标号的新的临时变量L，返回变量地址
  • SDT中我们将该初始值赋给 $S.next$，用于以后存放下一个三地址语句的地址
• label(L): 将下一条三地址指令的标号赋给L
  • SDT中我们使用该函数对上面新建的变量赋值
  • 也就是说，等S分析完后我们才能确定 $S.next$ 的值
  • 第二个产生式中，$label(S_1.next)$ 表示 $S_1$ 执行完后会执行 $S_2$ 的第一条指令，$S_2.next=S.next$ 表示 $S_2$ 执行完后会执行 $S$ 的下一条指令。

if-then-else语句的SDT

布尔表 达式及其SDT

在跳转代码中，逻辑运算符&&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的

布尔表达式的SDT

例如，$gen(\,'if’ \,\,E_1.addr \,\, relop \,\, E_2.addr \,\, 'goto’ \,\, B.true\,);$，表示的是如果 $E_1.addr\,\,relop\,\,E_2.addr$ 为真，则跳转到 $B.true$ 。

例如：

$B → B1 \,\, or \,\, B2$ 的SDT

布尔表达式的回填

基本思想

生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到 能够确定正确的目标标号时，才去填充这些指令的目标标号。

非终结符B的综合属性

B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号

B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

函数

• makelist(i)

  • 创建一个只包含 i 的列表，i 是跳转指令的标号，函数返回指向新创建的列表的指针

• merge(p1, p2)

  • 将 p1 和 p2 指向的列表进行合并，返回指向合并后的列表的指针

• backpatch(p, i)

  • 将 i 作为目标标号插入到 p 所指列表中的各指令中

布尔表达式的回填

• $B\rightarrow E_1 \,\, relop \,\, E_2$

  • {
    B.truelist = makelist(nextquad);
    B.falselist = makelist(nextquad+1);
    gen('if' E1.addr relop E2.addr 'goto_');
    gen('goto_');
    }
      - 其中分别生成了为true和false时的标号列表，并分别生成为true和false时的三地址表达式
    
    - $B\rightarrow true$
    
      - ```text
        {
        B.truelist=makelist(nextquad);
        gen('goto_');
        }
    
    

• $B\rightarrow false$ 、$B\rightarrow (B_1)$ 同理

• $B\rightarrow not B_1$

  • {
    B.truelist=B1.falselist;
    B.falselist=B1.truelist;
    }
    

• $B\rightarrow B_1 \,\,or\,\,B_2$

  • 
  • 显然 $B_1.truelist,B_2.truelist$ 都要放到 $B.truelist$，$B_1.falselist$ 中的指令都是要跳转到 $B_1$ 的假出口，$B_1$ 为假时我们要判断 $B_2$ 的值，所以 $B_1$ 的假出口就是 $B_2$ 的第一条指令。而当 $B_2$ 的值也是假时整个表达式为假，所以要将 $B_2.falselist$ 添加到 $B.falselist$ 中。
  • 我们得出，在分析 $B_2$ 前我们需要使用 $B_2$ 第一条指令的标号回填 $B_1.falselist$ 中的指令地址，我们可以记录下 $B_2$ 第一条指令的标号，在归约时完成回填。
  • 我们在 $B_2$ 之前插入标记非终结符 M，M关联的语义动作就是记录下 $B_2$ 的第一条指令的标号，$M.quad=nextquad;$ ，也就是说，$M.quad$ 就是 $B_2$ 的第一条指令的标号，我们使用 $M.quad$ 回填指令地址。
  • 

例

$a<b\,\, or \,\, c<d \,\, and \,\, e<f$，都是综合属性，所以可以采用自底向上的方案。

从左向右扫描，将 $a<b$ 归约为 B，首先进行 makelist() 生成只包含下一条标号的列表，假设标号从100开始，然后生成跳转指令

接下来读入输入符号 or ，使用上面提到过的生成式，赋值 $M.quad=102$ ，继续读入 $c<d$，归约为 B，使用的生成式还是 $B\rightarrow E_1 \,\, relop \,\,E_2$：

接下来读入and，我们将栈顶的空串归约出标记非终结符 M，$M.quad=104$ ，对于 $e<f$，同理。

由于and优先级更高，所以将栈顶 $B \,\,and\,\,M\,\,B$ 归约为 B，同时按照产生式进行回填并对list进行赋值

然后将 $B\,\,or\,\,M\,\,B$ 进行归约：

当B的truelist,falselist确定后我们回填当前三地址码中未回填的地址。

 

控制流语句的回填

设置综合属性：S.nextlist，指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

B.code = true时跳转到 $S_1.code$ 的第一条语句，否则跳转到 $S.nextlist$ 对应的指令。

在分析 $S_1.code$ 前用 $M.quad$ 回填$B.truelist$ 中的指令，然后计算 $S.nextlist$ 即可。

下同理。

第七章 代码优化

基本块

基本块是满足下列条件的最大的连续三地址指令序列

• 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令

• 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机

也就是说，基本块中的指令要么全都执行，要么全都不执行。

基本块划分算法

简单来说，我们只需要划分首指令，从前一个首指令到下一个首指令就是一个基本块。

由于控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令

• 也就是说一个跳转指令的目标指令就是一个首指令
• 紧跟在跳转指令的下一个指令是另一个分支的开始，因此也是首指令。

首先，第一条指令是首指令，其次，每个转移语句的目标指令，即5,9,23是首指令，转移指令之后的指令是一个首指令，即9,13,14,23是一个首指令，然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令(不含)或者指令序列结尾之间的所有指令。

流图

流图的结点是一些基本块，从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行。此时称B是C的前驱 (predecessor) ，C是B的后继 (successor)

有两种方式可以确认这样的边：

• 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句

• 按照原来的三地址语句序列中的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句，（条件跳转是可以的）

常用的优化方法

删除公共子表达式

如果表达式 x op y 先前已被计算过，并且从先前的计算到现在，x op y 中变量的值没有改变，那么 x op y 的这次出现就称为公共子表达式(common subexpression)

前面我们构造的流图中就有公共子表达式，如下：

其中 $t_7,t_{10}$ 就是公共子表达式，其值已经存储在 $t_6，t_8$ 且没有改变，我们可以将 $B_5$ 替换为右上角基本块中的指令。

其实我们可以看到， $t_6$ 的值在先前的 $t_2$ 中已经被计算且没有改变过，$t_8$ 同理，所以存在全局公共子表达式，我们可以对 $B_5$ 进行进一步优化：

对于优化后的基本块，我们发现 $a[t_2]$ 在 $B_2$ 中也已经被计算且未改变，所以可以进一步优化

对于 $B_6$ 同理：

在优化后的表达式中 $a[t_2]$ 仍然是全局公共子表达式，可以优化。

$a[t_1]$ 貌似也是，但将其作为公共子表达式是不稳妥的，因为控制进入 $B_6$ 前可能进入 $B_5$， $B_5$ 中有对a的赋值，因为我们并不保证 $t_1 \neq t_2$ 或者 $t_1\neq t_4$ ，所以不能作为公共子表达式。

为什么 $a[t_2]$ 就可以呢？整个程序的流程是一个循环，起初循环会走 $B_5$ ，最后走 $B_6$ 且不会再走 $B_5$，而且每次 $B_5$ 出来后 $a[t_2]$ 的值都会更新到 $t_3$ 中而 $a[t_1]$ 没有。

删除无用代码

复制传播

常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句 (形如 x = y 的赋值语句)

如下图中 $x = t_3$：

复制传播：在复制语句 x = y 之后尽可能地用 y 代替 x

无用代码

无用代码 (死代码Dead-Code) ：其计算结果永远不会被使用的语句

如下图， $x=t_3$ 就是无用的赋值。

常量合并 ( Constant Folding )

如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为常量合并。

代码移动 ( Code Motion )

这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式 (即循环不变计算，loop-invariant computation) ，在进入循环之前就对它们求值。

循环不变计算的相对性

对于多重嵌套的循环，循环不变计算是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变计算

强度削弱 ( Strength Reduction )

用较快的操作代替较慢的操作，如用加代替乘。

循环中的强度削弱

• 归纳变量

对于一个变量 x ，如果存在一个正的或负的常数 c 使得每次 x 被赋值时它的值总增加 c ，那么 x 就称为归纳变量(Induction Variable)

删除归纳变量

基本块的优化

很多重要的局部优化技术首先把一个基本块转换成为一个有向无环图 (directed acyclic graph，DAG)

基本块的 DAG 表示

• 基本块中的每个语句s都对应一个内部结点N 。
  • 结点N的标号是s中的运算符；同时还有一个定值变量表被关联到N，表示s是在此基本块内最晚对表中变量进行定值的语句。
  • N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点。如果s的某个运算分量在基本块内没有在s之前被定值，则这个运算分量对应的子结点就是代表该运算分量初始值的**叶结点 **(为区别起见，叶节点的定值变量表中的变量加上下脚标0) 。
  • 在为语句 x=y+z 构造结点N的时候，如果x已经在某结点M的定值变量表中，则从M的定值变量表中删除变量x（存疑，后文讲）
  • 对于形如 x=y+z 的三地址指令，如果已经有一个结点表示 y+z ，就不往DAG中增加新的结点，而是给已经存在的结点的定值变量表附加定值变量x

例如，$a=b+c$ 的DAG表示如下：

运算符为加号，所以结点的标号是加号。该语句是为a定值，所以定值变量表中的变量集合为 {a}，

因为这个节点对应的是第一条语句，因此它的两个运算分量b和c在基本块内还没有被定值，因此，这两个运算分量对应的子结点就是代表该运算分量b和c初始值的叶结点。

对于下例：

$$a=b+c\\ b=a-d\\ c=b+c\\ d=a-d\\$$

对于第2条指令，因为运算分量a在这个节点的定值变量表中，因此，它将作为该节点的一个子节点。第二个运算分量d在基本块内还没有被定值，因此，这个运算分量对应的子结点就是代表该运算分量d初始值的叶结点。

此时我们对b进行了定值，所以将左下角 $b_0$ 从其定值变量表中删除。

对于第三条指令，易知其结点标号与定值变量表，其一个子节点是 b ，另一个子节点（运算分量）c 还没有被定值，所以指向右下角已经存在的定值变量表中含有 $c_0$ 的节点。然后将 $c_0$ 从定值变量表中删除。

在为第四条语句构造结点的时候，第一个运算分量a在这个节点的定值变量表中，因此，它将作为该节点的一个子节点。第二个运算分量d在这个节点的定值变量表中，因此，它将作为该节点的另一个子节点，运算符是“-”，由此可见，DAG中已经有一个节点表示这条语句对应的表达式了。

该节点对应语句2，这实际上意味着，表达式的值已经在基本块中的语句2中计算过了，因此它是一个局部公共子表达式。此时，不需要创建新结点，而是把d加到语句2对应节点的定值变量表中。然后 $b_0$ 可以被删除。

这样，我们可以基于基本块的DAG检测局部公共子表达式。具体来说，就是当我们为一条语句构造节点的时候，如果DAG中已经有一个节点表示这条语句对应的表达式了，就说明这个表达式是一个局部公共子表达式。如下：

注意：

第二条和第四条语句都对表达式 a-d 进行计算。因为在这两条指令之间没有对b和c重新定值，因此两条指令的运算分量对应的结点是相同的，因此第四条语句中的表达式 a-d 是局部公共子表达式。

第一条和第三条语句都对表达式 b+c 进行计算，但b在这两条指令之间的第2条语句中被重新定值了，导致这两条语句的运算分量b对应不同的结点，因此第三条语句中的表达式 b+c 不是局部公共子表达式。

又：在为语句 x=y+z 构造结点N的时候，如果x已经在某结点M的定值变量表中，则从M的定值变量表中删除变量x 。这个可以不删除，老师的解释是涉及定值变量表，所以不讲。

也就是说，可以这样：

基于基本块的 DAG 删除无用代码

从一个DAG上删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根结点 。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的结点

目前根节点是 a、e，根节点 e 没有附加活跃变量（注意一个节点的定值变量表中可能有多个变量），所以删除，此时b、c成为根节点，同理，删除c。

数组元素赋值指令的表示

例：

$$x=a[i]\\ a[j]=y\\ z=a[i]$$

看上去第一条与第三条指令是公共子表达式，但由于第二条指令中无法确定 $j=i$ 是否不成立，所以并不能认为是公共子表达式。

对于 $x=a[i]$ ，构造DAG，节点标号就是 $=[\,]$ （认为这是一个操作符），子节点 $a_0,i_0$，定值变量表中只有变量 x，对于形如 $a[j] = y$ 的三地址指令，创建一个运算符为 $[\,]=$ 的结点，这个结点有3个子结点，分别表示 $a、j$ 和 $y$，该结点没有定值变量表，且该结点的创建将杀死所有已经建立的、其值依赖于a的结点，一个被杀死的结点不能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式。

比如 $=[\,]$ 节点依赖于 a，所以将被杀死。

根据基本块的DAG可以获得一些非常有用的信息

• 确定哪些变量的值在该基本块中赋值前被引用过

  • 在DAG中创建了叶结点的那些变量

• 确定哪些语句计算的值可以在基本块外被引用

  • 在DAG构造过程中为语句s（该语句为变量x定值）创建的节点N，在DAG构造结束时x仍然是N的定值变量

从 DAG 到基本块的重组

• 对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值

  • 倾向于把计算得到的结果赋给一个在基本块出口处活跃的变量 ( 如果没有全局活跃变量的信息作为依据，就要假设所有变量都在基本块出口处活跃，但是不包含编译器为处理表达式而生成的临时变量 )

• 如果结点有多个附加的活跃变量，就必须引入复制语句，以便给每一个变量都赋予正确的值

DAG构造总例

1-5对应如图，由于B是常量，所以在编译时可以直接确定，我们在图中直接标注：

6是2的公共子表达式，7是3的公共子表达式，所以在D所在的结点的定制变量表中添加变量 H，对于表达式8，运算分量在结点F的子节点中，所以在F的定值变量表中添加 J ，此后表达式同理：

然后我们根据DAG重新生成基本块，首先我们可以删除无用代码，对于存在的两个根节点 LM、G，由于仅变量L在基本块出口之后活跃，所以我们删除结点 G ，对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值，也就是说，我们只保留其中一个定值变量，如下：

如果没有说明 仅变量L 在基本块出口之后活跃，我们默认最后一条赋值语句左侧变量为默认活跃，也就是上面的变量 M。

对于所有原有的基本块，$B=3$ 可以直接用固定值代替，表达式 2,3,4 的运算结果 $D,E,F$ 都存在于DAG某个节点的定值变量表中，所以保留，表达式 5 所在节点已经被删除，所以删除该表达式， 对于表达式 6 ，H 已经从DAG的节点的定值变量表中删除，这意味着表达式 6 是一个局部公共子表达式，可以删除，表达式 7,8 同理，表达式 9 等价于赋固定值 $K=15$ 所以也可以直接删除， 使得表达式10 变为 $L=15+F$，其中 J 使用 F 来代替（公共子表达式）。表达式 11 所在节点已经被删除，所以删除该表达式。

数据流分析

一组用来获取程序执行路径上的数据流信息的技术，在每一种数据流分析应用中，都会把每个程序点和一个数据流值关联起来。

数据流分析模式

语句的数据流模式

• $IN[s]$：语句s之前的数据流值

• $OUT[s]$：语句s之后的数据流值

• $f_s$：语句s的传递函数 (transfer function)

  • 一个赋值语句s之前和之后的数据流值的关系
  • 传递函数的两种风格
  • 信息沿执行路径前向传播 (前向数据流问题)
    • $OUT[s] = f_s (IN[s])$
  • 信息沿执行路径逆向传播 (逆向数据流问题)
    • $IN[s] = f_s (OUT[s])$

• 基本块中相邻两个语句之间的数据流值的关系

  • 设基本块B 由语句 $s_1, s_2, … , s_n$ 顺序组成，则
  • $IN[s_{i+1}]= OUT[s_i],,,i=1, 2, … , n-1 $
  • 也就是说，下一个语句的输入就是上一个语句的输出

基本块上的数据流模式

• $IN[B]$：紧靠基本块B之前的数据流值

• $OUT[B]$：紧随基本块B之后的数据流值

• 设基本块B由语句 $s_1,s_2,…,s_n$ 顺序组成，则

  • $IN[B] = IN[s_1]$
  • $OUT[B] = OUT[s_n]$

• $f_B$：基本块B的传递函数

  • 前向数据流问题：$OUT[B] = f_B(IN[B])$

    • $$\begin{aligned} OUT[B] &=OUT[s_n]\\ &=f_{s_n}(IN[s_n])\\ &=f_{s_n}(OUT[s_{n-1}]) &(OUT[s] = f_s (IN[s]))\\ &=f_{s_n}·f_{s_{n-1}}(IN[s_{n-1}])\\ &=f_{s_n}·f_{s_{n-1}}(OUT[s_{n-2}])\\ &...\\ &= f_{sn}·…·f_{s2} ·f_{s1}(IN[s_1])\\ &=f_{sn}·…·f_{s2} ·f_{s1}(IN[B]) \end{aligned}$$

    • 所以 $f_B=f_{sn}·…·f_{s2} ·f_{s1}$

  • 逆向数据流问题：$IN[B] = f_B(OUT[B])$

    • $f_B = f_{s1}·f_{s2}· …·f_{sn}$

到达定值分析

• 定值 (Definition)

  • 变量x的定值是(可能)将一个值赋给x的语句

• 到达定值(Reaching Definition)

  • 如果存在一条从紧跟在定值d后面的点到达某一程序点p的路径，而且在此路径上d没有被“杀死” ，则称定值d到达程序点p
    • 如果在此路径上有对变量x 的其它定值 $d'$，则称变量x 被这个定值 $d'$ “杀死”了
  • 直观地讲，如果某个变量x的一个定值d到达点p，在点p处使用的x的值可能就是由d最后赋予的

例：

假设每个控制流图都有两个空基本块，分别是表示流图的开始点的 ENTRY 结点和结束点的 EXIT 结点（所有离开该图的控制流都流向它）

对于 $d_1,d_2,d_3$，到达 $B_2$ 入口处对 $i,j,a$ 没有改变，所以三个定值都可以到达入口处，同理， $d_5,d_6,d_7$ 到达 $B_2$ 入口处也没有改变 $j,a,i$ 的值，所以也可以，对于$d_4$ 在到达 $B_2$ 入口处的路径上对 i 的定值被 $d_7$ 改变，也就是说 $d_7$ 杀死了 $d_4$ 对变量i 的定值，所以无法到达 $B_2$ 入口。

同理 $d_1,d_2,d_7$ 无法到达 $B_3$ 入口，等等。

到达定值分析的主要用途

循环不变计算的检测

如果循环中含有赋值 x=y+z ，而 y 和 z 所有可能的定值都在循环外面 (包括 y 或 z 是常数的特殊情况) ，那么 y+z 就是循环不变计算

常量合并

如果对变量x 的某次使用只有一个定值可以到达，并且该定值把一个常量赋给 x ，那么可以简单地把 x 替换为该常量。

判定变量x在p点上是否未经定值就被引用

“生成”与“杀死”定值

定值d：$u = v + w$ ，该语句“生成”了一个对变量u 的定值d，并“杀死”了程序中其它对 u 的定值

• 这里，“+” 代表一个 一般性的二元运算符

到达定值的传递函数

• $f_d$：定值d: $u = v + w$ 的传递函数
  • $f_d(x) = gen_d∪(x-kill_d)$，$f_d(x)$ 就是在定值d 之后所有到达定值的集合
  • $gen_d$ ：由语句d 生成的定值的集合 $gen_d=\{d\}$
  • $kill_d$ ：由语句d 杀死的定值的集合（程序中所有其它对 u 的定值）

可以看出，语句d 会生成新的定值，并杀死x 中的一部分定值。

• $f_B$：基本块B 的传递函数

  • $f_B(x)=gen_B∪(x-kill_B)$

  • $kill_B =kill_1 ∪ kill_2 ∪ … ∪ kill_n$

    • $kill_n$ 表示基本块中第n条语句杀死的定值的集合

    • $kill_B$ 表示被基本块B中各个语句杀死的定值的集合

  • $gen_B = gen_n ∪(gen_{n-1} – kill_n ) ∪(gen_{n-2} –kill_{n-1} – kill_n ) ∪ … ∪ (gen_1 –kill_2 –kill_3 – … – kill_n)$

    • $gen_B$ 表示基本块中没有被块中各语句“杀死”的生成的定值的集合
    • 比如$(gen_1 –kill_2 –kill_3 – … – kill_n)$表示由第一条语句生成但没有被后面的语句杀死的定值

样例

计算下例中基本块B 的 $gen_B$ 和 $kill_B$ ：

另如：$B_5$ :

$$d_1:i=m-1\\ d_2=j=n\\ d_3=i=u1$$

则，$gen_{B_5}=\{d_2,d_3\}$，这是因为 $d_1$ 被$d_3$ kill 了，或者说 $gen_3-kill_3=\emptyset$

到达定值的数据流方程

• $IN[B]$：到达流图中基本块B的入口处的定值的集合

• $OUT[B]$：到达流图中基本块B 的出口处的定值的集合

• 方程

  • $OUT[ENRTY]=Φ$
  • $OUT[B]=f_B(IN[B])(B≠ENTRY)$
    • 代入 $f_B(x)=gen_B∪(x-kill_B)$，得 $OUT[B] = gen_B ∪(IN[B]-kill_B )$
  • $IN[B]= ∪_{P是B的一个前驱}OUT[P]\,(B≠ENTRY)$
    • 也就是说，B的前驱P的出口处的定值都可以到达入口处的定值。

其中，$gen_B$ 和 $kill_B$ 的值可以直接从流图计算出来，因此在方程中作为已知量。

计算到达定值的迭代算法

活跃变量分析

对于变量x 和程序点p，如果在流图中沿着从 p 开始的某条路径会引用变量x 在p点的值，则称变量x 在点p 是活跃(live)的，否则称变量x 在点p 不活跃(dead)

以变量i 为例，对于 $B_1$ 的出口处，在后续的路径上，$B_2$ 引用了变量i，所以其在 $B_1$ 出口处是活跃的。对于 $B_2$ 的出口处，在此后的路径中只是对变量进行了重新定值，而没有对变量进行引用（如作为运算分量），所以变量i 在 $B_2$ 出口处不活跃。$B_3$ 中没有对变量i 进行定值，也就是说一定不会引用变量i 在 $B_3$ 出口点的值，所以在 $B_3$ 出口处不活跃。同理在 $B_4$ 出口处活跃。

主要用途

删除无用赋值

• 无用赋值：如果x在点p的定值在基本块内所有后继点都不被引用，且x在基本块出口之后又是不活跃的，那么x在点p的定值就是无用的

为基本块分配寄存器

• 如果所有寄存器都被占用，并且还需要申请一个寄存器，则应该考虑使用已经存放了死亡值的寄存器，因为这个值不需要保存到内存

• 如果一个值在基本块结尾处是死的就不必在结尾处保存这个值

活跃变量的传递函数

变量只有两种出现的形式，一种是定值，另一种是引用。

逆向数据流问题：$IN[B] = f_B(OUT [B])$，用 x 表示出口处活跃的变量的集合，$f_B(x)$ 表示程序入口处活跃的集合。

• $f_B (x) = use_B ∪(x-def_B )$
  • $def_B$ ：在基本块B中定值，但是定值前在B中没有被引用的变量集合
    • 在基本块中首次出现是以定值变量出现的变量集合。
    • 因此在入口处肯定是不活跃的
  • $use_B$ ：在基本块B中引用，但是引用前在B中没有被定值的变量集合

样例：

、

活跃变量数据流方程

• $IN[B]$：在基本块B的入口处的活跃变量集合

• $OUT[B]$：在基本块B的出口处的活跃变量集合

方程

• $IN[EXIT] = Φ$

• $IN[B] = f_B(OUT[B])\,\,( B≠EXIT )$

  • $f_B (x) = use_B ∪(x-def_B )$，代入得 $IN[B]=use_B\cup(OUT[B]-def_B)$

• $OUT[B]= ∪_{S是B的一个后继} IN[S] ( B≠EXIT )$

$use_B$ 和 $def_B$ 的值可以直接从流图计算出来，因此在方程中作为已知量

计算活跃变量的迭代算法

定值-引用链 (Definition-Use Chains)

定值-引用链：设变量x 有一个定值d，该定值所有能够到达的引用u 的集合称为 x 在 d 处的定值-引用链，简称du链

• 如果在求解活跃变量数据流方程中的OUT[B]时，将OUT[B]表示成从B的末尾处能够到达的引用的集合，那么，可以直接利用这些信息计算基本块B中每个变量x在其定值处的du链
  • 情况一：如果B中x 的定值d 之后有x 的第一个定值 $d'$，则 $d$ 和 $d'$ 之间 x 的所有引用构成 d 的du链
  • 
  • 情况二：如果B中 x 的定值d 之后没有 x 的新的定值，则B中 d 之后 x 的所有引用以及 OUT[B] 中 x 的所有引用构成 d 的du链
  • 

可用表达式分析

可用表达式

• 如果从流图的首节点到达程序点p 的每条路径都对表达式 $x\,op\, y$ 进行计算，并且从最后一个这样的计算到点p 之间没有再次对 x 或 y 定值，那么表达式 $x \,op\, y$ 在点 p是可用的 (available)

表达式可用的直观意义

在点p 上，$x \,op\, y$ 已经在之前被计算过，不需要重新计算

可用表达式信息的主要用途

消除全局公共子表达式

例：如何让 $4*i$ 在 $B_3$ 入口处可用，

一种情况是 $B_2$ 不含对变量i 的引用与定值，或者可以包含对表达式的计算比如包含 $t_0=4*i$，也可以先定值再计算，如：

$$i=...\\ t_0=4*i$$

进行复制传播

复习前面复制传播的概念，比如对于下面的 $x=y$ ，在用到变量x 的地方都可以尝试用 y代替

右侧程序点有多条路径可达且其中一条对 x 进行了定值，所以不能复制传播。

在 x 的引用点u 可以用 y 代替 x 的条件：复制语句 $x = y$ 在引用点u 处可用

也就是说，从流图的首节点到达 u 的每条路径都存在复制语句 $x = y$，并且从最后一条复制语句 $x = y$ 到点u 之间没有再次对x 或y 定值

可用表达式的传递函数

对于可用表达式数据流模式而言，如果基本块B 对 x 或者 y 进行了(或可能进行)定值，且以后没有重新计算 $x \,op\, y$，则称B 杀死表达式 $x op y$ 。如果基本块B 对 $x op y$ 进行计算，并且之后没有重新定值 x 或 y ，则称 B 生成表达式$x \,op\, y$

• $f_B(x)= e\_gen_B ∪(x- e\_kill_B)$
  • $e\_gen_B$ ：基本块B 所生成的可用表达式的集合
  • $e\_kill_B$ ：基本块B 所杀死的 U 中的可用表达式的集合
  • U ：所有出现在程序中一个或多个语句的右部的表达式的全集

$e\_gen_B$ 的计算

• 初始化：$e\_gen_B = Φ$

• 顺序扫描基本块的每个语句：$z = x\,op\,y$

  • 把 $x\,op\,y$ 加入 $e\_gen_B$
  • 从 $e\_gen_B$ 中删除和 z 相关的表达式

$e\_kill_B$ 的计算

• 初始化：$e_kill_B = Φ $
• 顺序扫描基本块的每个语句：$z = x\,op\, y$
  • 从 $e\_kill_B$ 中删除表达式 $x\,op\,y$
  • 把所有和 z 相关的表达式加入到 $e\_kill_B$ 中

第八章 代码生成

代码生成器的主要任务

• 选择适当的目标机指令来实现中间表示(IR)语句

上面这种逐条语句进行翻译的方案能够翻译出正确的代码，但很容易产生冗余指令，如：

上图中第三条指令说明 $R_0$ 中的值就是 $a$，所以我们没有必要执行第四条指令。

• 寄存器分配和指派：把哪个值放在哪个寄存器中
• 指令排序：按照什么顺序来安排指令的执行

一个简单的目标机模型

我们使用一个汇编语言下的三地址目标机模型，有加载、保存、运算、跳转等操作，其内存按字节寻址，有n个通用寄存器 $R_0, R_1, …, R_{n-1}$，假设所有运算分量都是整数，指令之间可能有一个标号

主要指令

• 加载指令 LD dst, addr

  • 将addr中的值赋值给 dst

  • 可以是将值加载到寄存器，也可以是将寄存器的值赋值给另一个寄存器。

• 保存指令 ST x,r

  • 将 r 中的内容保存到 x 中

• 运算指令 OP dst, src1, src2

  • 将运算符 OP 作用于 src1,src2，结果存储在 dst 中

• 无条件跳转指令 BR L

  • BR 是 Branch 的缩写，表示将控制转到标号为 L 的指令。

• 条件跳转指令 Bcond r, L

  • Bcond r 表示对寄存器 r 中的值进行Bcond 条件的测试，如果满足，就跳转到标号为 L 的指令。否则继续执行下一条指令。
  • 例：BLTZ r, L（LTZ：Lower Than Zero）

寻址模式

• 变量名a

  • 例：LD R1, a
    • R1 = contents(a)
    • 相当于直接寻址

• a®

  • a是一个变量，r是一个寄存器
    • 例：LD R1, a(R2)
    • 即：R1 = contents(a + contents(R2))，即a的地址加上R2中的值
    • 相当于基址寻址

• c®

  • c是一个整数

    • 例：LD R1 , 100 (R2)

    • R1 = contents(contents(R2) + 100)

    • 相当于变址寻址（？）

• *r

  • 在寄存器r的内容所表示的位置上存放的内存位置
    • 例：LD R1 , *R2
    • R1 = conents(contents(contents(R2)))，contents(R2)是R2的地址。
    • 间接寻址：寄存器间接寻址

• *c®

  • 在寄存器r中内容加上c后所表示的位置上存放的内存位置
    • 例：LD R1, *100(R2)
    • R1 = conents(contents(contents(R2) + 100))
    • 相当于 *r 与 c® 的组合

• #c

  • 例：LD R1, #100
  • R1 = 100
  • 立即数寻址

指令选择

对于三地址加法/减法：尽可能避免使用上面的全部四个指令，因为可能存在如下两种情况：

• 所需的运算分量已经在寄存器中了

• 运算结果不需要存放回内存

M是标号为L的三地址指令所产生的目标代码中的第一个指令的标号

寄存器选择

寄存器描述符和地址描述符

• 寄存器描述符 ( register descriptor )

  • 记录每个寄存器当前存放的是哪些变量的值

• 地址描述符 ( address descriptor )

  • 记录运行时每个名字的当前值存放在哪个或哪些位置
    • 该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合
    • 这些信息可以存放在该变量名对应的符号表条目中
    • 这是因为有些值被计算了出来但是还没有写入寄存器。

基本块的收尾处理

对于一个在基本块的出口处可能活跃的变量 x , 如果它的地址描述符表明它的值没有存放在 x 的内存位置上, 则生成指令 $ST\,\, x, R$ ( R 是在基本块结尾处存放 x 值的寄存器 )（将变量x保存回其内存位置）

管理寄存器和地址描述符

当代码生成算法生成加载、保存和其他指令时，它必须同时更新寄存器和地址描述符

• 对于指令 LD R , x

  • 修改 R 的寄存器描述符，使之只包含 x
  • 修改 x 的地址描述符，把 R 作为新增位置加入到 x 的位置集合中
  • 从任何不同于 x 的地址描述符中删除 R（避免其他地址指向R）

• 对于指令 $OP\, R_x,\,R_y,\,R_z$

  • 修改 $R_x$ 的寄存器描述符，使之只包含 x

  • 从任何不同于 $R_x$ 的寄存器描述符中删除 x

  • 修改x的地址描述符，使之只包含位置 $R_x$

  • 从任何不同于x的地址描述符中删除 $R_x$

• 对于指令 $ST\,x,R$

  • 修改x的地址描述符，使之包含自己的内存位置

• 对于复制语句 $x=y$ ，如果需要生成加载指令 $LD\, R_y , \,y$ 则

  • 修改 $R_y$ 的寄存器描述符，使之只包含 $y$
  • 修改 $y$ 的地址描述符，把 $R_y$ 作为新增位置加入到 $y$ 的位置集合中
  • 从任何不同于 $y$ 的变量的地址描述符中删除 $R_y$
  • 修改 $R_y$ 的寄存器描述符，使之也包含 $x$
  • 修改 $x$ 的地址描述符，使之只包含 $R_y$

寄存器选择函数 getReg()

比如对于 $x=y\,op\,z$，如何选择 $R_y$ ？

其中i是计数器，即for(int i = 1; i <= n; i++)

$x=y\,op\,z$ 中寄存器 $R_x$ 的选择

选择方法与 $R_y$ 类似，区别之处在于

• 因为 x 的一个新值正在被计算，因此只存放了 x 的值的寄存器对 $R_x$ 来说总是可接受的，即使 x 就是 y 或 z 之一(因为我们的机器指令允许一个指令中的两个寄存器相同)

• 如果 y 在指令 I 之后不再使用，且(在必要时加载 y之后) $R_y$ 仅仅保存了 y 的值，那么， $R_y$ 同时也可以用作 $R_x$ 。对 z 和 $R_z$ 也有类似选择

当 I 是复制指令 $x=y$ 时，选择好 $R_y$ 后，令 $R_x =R_y$

窥孔优化

窥孔(peephole)是程序上的一个小的滑动窗口。窥孔优化是指在优化的时候，检查目标指令的一个滑动窗口(即窥孔) ，并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列。也可以在中间代码生成之后直接应用窥孔优化来提高中间表示形式的质量。

冗余指令删除

有标号，也就是说有指令可能跳转到第四条指令。

控制流优化

代数优化

• 代数恒等式

  • 消除窥孔中类似于 $x=x+0$ 或 $x=x*1$ 的运算指令

• 强度削弱

  • 对于乘数(除数)是2的幂的定点数乘法(除法) ，用移位运算实现代价比较低
  • 除数为常量的浮点数除法可以通过乘数为该常量倒数的乘法来求近似值

特殊指令

充分利用目标系统的某些高效的特殊指令来提高代码效率。

例如：INC指令可以用来替代加1的操作。

参考

https://blog.csdn.net/Follower_JC/article/details/83996643

https://github.com/Peefy/CompileDragonBook

https://zhangt.top/CS/Compilation-Principles-Study-Notes/