文章链接

https://gitee.com/fakerlove/fundamentals-of-compiling

编译原理

1. 引论

• 词法分析 --第三章

• 语法分析- 第四章-第六章

• 语义分析及中间代码生成 -第七章-第八章

• 代码优化 第九章

• 代码生成

1.1 什么是编译原理

1.1.1 常见概念

名称	内容
翻译程序	把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。
编译程序	把高级语言所写的源程序翻译成与之等价的低级语言（如汇编语言、机器语言等）的目标程序。如果编译阶段目标程序是机器语言程序，则分为编译阶段和运行阶段；如果生成的是汇编程序，则分为编译阶段、汇编阶段和运行阶段。
解释程序	也是一种翻译程序，将源程序作为输入，边解释边执行，但其不产生目标程序，而是按照源语言的定义解释执行源程序本身。
编译器	阅读以某一种语言（源代码）编写的程序，并把该程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序。
解释器	另一种常见的语言处理器，并不通过翻译的方式生成目标程序，直接利用用户提供的输入执行源程序中指定的操作。
预处理器	一个源程序可能被分割成多个模块，并存放于独立的文件中，把源程序聚合在一起的任务有时会由一个被成为预处理器的程序独立完成。
链接器/加载器	一个文件中的代码可能指向另一个文件中的位置，而链接器能够解决外部内存地址的问题。最后，加载器把所有的可执行目标文件放到内存中执行。
汇编器	对编译器产生的汇编语言程序进行处理，并生成可重定位的机器代码。

1.1.2 流程

1.2 编译器的结构和过程

1.2.1 结构

编译器的两个组成部分：分析部分和综合部分。

1.2.2 编译的五个阶段

一个编译器的各个步骤：

1) 词法分析

• 词法分析/扫描：词法分析器读入组成源程序的字符流，并且将它们组织成为有意义的词素的序列。

• 每个词素都被映射成如下语法单元，传送给语法分析：

 <token-name, attribute-value>

分隔词素的空格会被词法分析器忽略掉。

• 描述词法规则的有效工具是正规式和有限自动机

2) 语法分析

• 语法分析/解析：语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。

• 赋值语句语法规则

  • A::=V=E
  • E::=T|E+T
  • T::=F|T*F
  • F::=V|(E)|C
  • V::=标识符
  • C::=常数

• 语法分析的两种放法

  • 推导
  • 归约

• 计算机的做法是 语法树

  x=a+b*50的语法树

  

3) 语义分析和中间代码生成

• 语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。

• 它同时也收集类型信息，并把这些信息存放在语法树或者符号表中，以便在随后的中间代码生成过程中使用。

• 三地址代码的中间表示形式

  （运算符，运算对象1 运算对象2 结果)

4) 代码优化

5) 代码生成

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

1.2.3 编译的七大程序

1) 表格程序管理程序

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

符号表一般有符号表，常数表，标号表，分程序入口表，中间代码表

• 将多个步骤组合成趟
• 编译器构造工具

2) 出错处理程序

流程

一个赋值语句的翻译：

1.3 编译程序生成

• 直接用机器语言编写编译程序

• 用汇编语言编写编译程序

• 用高级语言编写编译程序--常用方法

  c语言编写的编译程序 把源程序变成目标程序

  C语言编写的编写程序 --> c 语言的编译器 变成exe

1.4 总结

1.4.1 三种程序的解释

翻译程序

• 把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。

编译程序

• 把高级语言所写的源程序翻译成与之等价的低级语言（如汇编语言、机器语言等）的目标程序。如果编译阶段目标程序是机器语言程序，则分为编译阶段和运行阶段；如果生成的是汇编程序，则分为编译阶段、汇编阶段和运行阶段。

解释程序

• 也是一种翻译程序，将源程序作为输入，边解释边执行，但其不产生目标程序，而是按照源语言的定义解释执行源程序本身。

编译程序和解释程序都是用来对高级语言程序进行编译，

汇编程序是对汇编程序语言的程序进行编译

1.4.2 编译的五个阶段

这五个阶段为逻辑关系而非执行上的先后顺序

• 词法分析：对构成源程序的字符串从左到右进行
  • 扫描和分解；
  • 根据语言的词法规则识别出一个一个具有独立意义的单词/单词符号/符号。
• 语法分析：
  • 根据语法规则（是语法单位的形成规则，规定了如何从单词符号形成语法单位）从单词符号串中识别出各种语法单位（如表达式、说明等）；
  • 进行语法检查，即检查各种语法单位在语法结构上的正确性。
• 语义分析及中间代码生成：对语言的各种语法单位赋予具体的意义
  • 对每种语法单位进行静态的语义审查；
  • 分析其含义；
  • 用另一种语言形式（更接近于目标语言的中间代码/目标语言，如一个完整表达式分解为多个子表达式）来描述该语义。
• 代码优化：对前一阶段产生的中间代码进行等价变换或改造，目的是获取更高效的(时间、空间)目标代码。主要有局部优化和循环优化等。
• 目标代码生成：将中间代码变换成
  • 特定机器上的绝对指令代码；
  • 可重定位的指令代码；汇编指令代码。

注意点，有些最简单的编译程序在语法分析阶段就直接产生了目标代码，这样子的编译程序就没有完全包含这5个阶段

1.4.3 编译的七大程序

• 上述五个阶段的每个程序
• 表格管理程序： i. 记录源程序中所使用的变量的名字； ii. 收集与名字属性相关的各种信息，如存储分配、类型、作用域，如果是函数名则还包含参数数量、传参方式、返回类型等； iii. 各个阶段中需要构造、查找、修改或存取表中信息。
• 出错处理程序：定位和跟踪错误，在五个阶段中都会用到。

扫描遍数：

• 指对源程序或者等价的中语言程序从头到尾扫描一遍并完成规定加工处理工作。
• 遍和阶段的含义毫无关系
• 多遍扫描程序：相比一遍扫描占用存储空间少，可使各遍所要完成的功能相对独立，逻辑结构更加清晰；但遍数增加会导致输入输出的开销，会降低编译效率。

注意：

a) 编译程序是系统软件，而非应用软件； b) 代码优化、中间代码生成并非必不可少的部分； c) 含有优化部分的编译程序的执行效率不一定会高。

2. 文法和语言

一个程序设计语言是一个记号系统，如同自然语言一样，它的完整定义应该包括语法和语义两个方面，所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序

语言是定义在一些有限字母表上的

语言是一个层次化的记号系统，有字母表上的字母按照一定的规则构成单词，由单词按照一定的规则构语句和文章

2.1 概念

2.1.1 语法(文法)

描述词法规则和语法规则的工具是文法

1) 词法规则

语言中具有独立意义的最基本结构。

– 词法规则规定了字母表中那些字符串是单词符号。

– 单词符号一般包括：常数、标识符、基本字、算符、界限符等。

– 我们用正规式和有限自动机理论来描述词法结构和进行词法分析。

2) 语法规则

– 表达式、子句、语句、函数、过程、程序

– 规定了如何从单词符号来形成语法单位。

– 现在多数程序语言使用上下文无关文法来描述语法规则。

– 语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据。我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”。

例如： <句子>::=<主语><谓语> <主语>::=<代词>|<名词> <代词> ::=你|我|他 <名词>::= 王民|大学生|工人|英语 <谓语>::=<动词><直接宾语> <动词>::=是|学习 <直接宾语>::=<代词>|<名词>

2.1.2 语义

对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。

– 离开语义，语言只是一堆符号的集合。

– 各种语言中有形式上完全相同的语法单位，含义却不尽相同。

– 对某种语言，可以定义一个程序的意义的一组规则称为语义规则。

– 目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义。

2.1.3 语法规则符号相关概念

(1)非终结符

– 出现在规则的左部、用<>括起来、表示一定语法概念的词。

– 非终结符集合用VN表示。

(2)终结符

– 语言中不可再分割的字符串(包括单个字符组成的串)。注：终结符是组成句子的基本单位。

– 终结符集合用VT表示

(3)开始符号

– 表示所定义的语法范畴的非终结符。

– 注：开始符号又称为识别符号。

(4)产生式

– 是用来定义符号串之间关系的一组(语法)规则。

– 形式：A → α （A产生α ）

(5)推导

– 推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。

– 最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非终结符。

注：最左推导和最右推导称为规范推导

(6)归约

– 归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。

– 最左(右)归约是最右(左)推导的逆过程。

– 注：最左归约和最右归约称为规范归约

(7)句型、句子和语言

• 句型：

  – 句型是从文法的开始符号S开始，每步推导（包括0步推导）所得到的字符串α。

  – 记作：S α，其中α ∈ （VN∪ VT ）*

• 句子：是仅含终结符的句型

(8)文法规则的递归定义

– 非终结符的定义中包含了非终结符自身。

– 使用文法的递归定义要谨慎

(9) 文法规则的扩充表示

扩充的BNF表示

BNF的元符号： <, >, ::=, | 扩充的BNF的元符号： <, >, ::=, |, {, }, [, ] (, ) 1.{ t }：t可重复连接0到任意多次。如果有限制（上标m，下标n），则可重复连接n到m次。 2.[ t ]：t可有可无。 3.( )：元符号，注意不要与Vt混淆。

• () ——提因子

  例:把U→ax|ay|az 改写为U→a(x|y|z)

• {} ——重复次数的指定

  例：<标识符>→<字母>{<字母>|<数字>}50.

• [] ——任选符号

  例:<整数>→[+|-]<数字>{<数字>}

(10)元语言符号

用来说明文法符号之间关系的符号，如，“→”和“|”称为元语言符号

例题

有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。 <句子> => <主语><谓语> <主语><谓语> => <代词><谓语> …… …… 这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。 说明： (1) 有若干语法成分同时存在时，我们总是从 最左的语法成分进行推导，这称之为最左推导。类似地还有最右推导（一般推导、规范推导）。 (2) 除了最左和最右推导，还可能存在其它形式的推导。 (3) 从一组规则可推出不同的句子

2.1.4 总结

• 任何语言程序都可以看成是一定字符集（字母表）上的字符串。

• 语法使得这串字符形成一个形式上正确的程序。

• 语法＝词法规则＋语法规则

• 例如：0.5x1+c

  – 0.5、x1、c、*、+是语言的单词符号

  – 0.5*x1+c是语言的语法单位

2.2 字母表与符号串(单词符号)

2.2.1 概念

名称	概念
字母表	– 是符号的非空有穷集合。 – 用Σ、V表示。
符号	是语言中最基本的不可再分的单位。
符号串	– 符号串是字母表中符号组成的有穷序列。 – 空串：不含有任何符号的串称作空串，记作ε。
句子	字母表上符合某种规则构成的串。
语言	字母表上句子的集合

2.2.2 符号串集合的运算

1) 连接（乘积）运算：

若串集A={α1， α2， …}，串集B={β1,β2， …}，则乘积AB={α β| α ∈ A and β ∈ B}

注：1）串集的自身乘积称作串集的方幂

2）A0={ε}

3）字母表A的n次方幂是字母表A上所有长度为n的串集

例如：串集A＝{a}的各次方幂定义为：

A0={ε}

A1=A={a}

……

An=AAn-1(n>0)={a…a}

2) 字母表的闭包与正闭包⭐

a. 字母表A的闭包（A*）：

A*=A0∪A1∪A2∪…

即：由A上符号组成的所有串的集合（包括空串ε ）。

$例题:(a,b{)}^{\ast }代表w\in \{\epsilon ,a,b,ab,aa,bb,....\}$

b. 字母表A的正闭包（A+）：

A+= A1 ∪A2∪ …=A*-{ε}

即：由A上符号组成的所有串的集合（不包括空串ε ）。

c. 语言: 是字母表上符合某种规则的语句组成的。

– 字母表上语言：是字母表上正闭包的子集

2.3 文法和语言的形式定义

1.文法定义

$从形式上说文法G是一个四元式(V_N,V_T,P,S)$

文法$G=（V_n，V_t，P，Z）$

• Vn：非终结符号集
• Vt：终结符号集
• P：产生式或规则的集合
• Z：开始符号（识别符号） Z∈Vn

注： ①V＝Vn ∪ Vt 称为文法的字汇表 ②规则：规则是一个有序对(U, x), 通常写为 U ::= x 或U→x（其中U∈Vn, x∈V* 因此也有|U| = 1且|x| >= 0） ③给定一个文法，实际只需给出产生式集合，并指定识别符号。（识别符号一般约定为第一条规则的左部符号）

例：无符号整数的文法： G[<无符号整数>]=（Vn，Vt，P，Z） Vn＝{<无符号整数>,<数字串>, <数字>} Vt = { 0, 1, 2, 3, … 9 } P = {<无符号整数> → <数字串> <数字串> → <数字串> <数字> <数字串> → <数字> <数字> →0 <数字> →1 ………… <数字> →9 } Z = <无符号整数>

2.推导定义

一步推导： 注：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。

多步推导： 任意步推导： 规范推导： 直观意义上：规范推导＝最右推导

3.语言定义

对于文法G[Z]： （1）句型x：由开始符号Z经任意步推导得到x，且x∈V*； （2）句子x：由开始符合Z经1多步推导得到x，且x∈Vt* （3）语言L：所有根据该文法推到得到的句子组成的集合

形式语言理论可以证明以下两点： （1）G →L(G)：已知文法，求语言，通过推导； （2）L(G)→G1，G2，……，Gn：已知语言，构造文法，无形式化方法，更多是凭经验。

等价文法：G和G’是两个不同的文法，若 L(G) = L(G’) , 则G和G’为等价文法。

4.递归文法

①递归规则：规则右部有与左部相同的符号 对于 U::= xUy 若x=ε,即U::= Uy，左递归； 若y=ε,即U::= xU，右递归。

②递归文法：文法G，存在U ∈Vn if U=+=>…U…, 则G为递归文法(自嵌入递归)； if U=+=>U…, 则G为左递归文法； if U=+=>…U, 则G为右递归文法。

③左递归文法的缺点：不能用自顶向下的方法来进行语法分析

④递归文法的优点：可用有穷条规则，定义无穷语言

5.句型的短语、简单短语和句柄

给定文法G[Z], w::=xuy∈V+，为该文法的句型, 若 Z==> xUy, 且U=+=>u, 则u是句型w相对于U的短语； 若 Z==> xUy, 且U==>u, 则u是句型w相对于U的简单短语。 其中U ∈Vn，u ∈V+，x, y ∈V*

短语的直观理解：短语是前面句型中的某个非终结符所能推出 的符号串。 句柄：任一句型的最左简单短语称为该句型的句柄

给定句型找句柄的步骤： 短语-> 简单短语-> 句柄

注意：短语、简单短语是相对于句型而言。一个句型 可能有多个短语、简单短语，但句柄只能有一个。

2.4 文法和语言分类

2.4.1 Chomsky对文法的分类⭐

文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。

0型

1型

2型

3型

$从形式上说文法G是一个四元式(V_N,V_T,P,S)$

文法类型	别称	对产生式的限制	可被接受目标
0型文法	短语结构文法	P:u::=v 其中 u∈V＋,v∈V*	图灵机(Turing)
1型文法	上下文敏感（有关）文法	P: xUy::= xuy 其中 U∈Vn,x、y、u∈V*	线性界限自动机
2型文法	上下文无关文法	P: U::= u 其中 U∈Vn,u∈V* 左边的必须是非终结符，右边是字符串	下推自动机
3型文法	正则文法	$$\begin{gathered} ①P:U::=T或U::=wT其中U、w\in V_n,T\in V_t(右线性) \\ ②P:U::=T或U::=T_w其中U、w\in V_n,T\in V_t(左线性) \end{gathered}$$ 人话来说，左边的必须是非终结符， 右边的非终结符要么都在左边，要么都在右边	有穷自动机

注：

• 3型文法是我们判断单词是否正确的方法

• 2型语言是我们判断句子是否正确的方法

• 2型文法与BNF表示相等价。

• 3型语言（L3）又称正则语言、正则集合

• 四种语言的关系：

2.4.2 i型语言

由i型文法生成的语言成为i型语言。

– 记为：L(G)；L(G)={w|w ∈VT* ，且S →+ w}

2.4.3 文法的构造和简化

1) 构造-> 文法

例一

设文法G1＝({S},{a,b},P,S)

其中P为:

(0) S →aS

(1) S →a

(2) S →b

L(G1)={ai(a|b)|i>=0}

例二

设文法G2＝({S},{a,b},P,S)

其中P为:

(0) S →aSb

(1) S →ab

L(G2)={anbn|n>=1}

2) 构造->文法

$设L_2=a^i{b}^j{c}^k|i,j,k>=1且a,b,c\in V_T试构造生成L_2的文法G_2$

解：S →aS

S → aB

B →bB

B →bC

C →cC | c

设L4={ω | ω ∈(0,1)* 且ω中1的个数为偶数}试构造生成L4的文法G4

解：

S → ε

S →0S， S → 1A

A →0A , A →1S

3) 简化文法

简化规则

• 查找有无形如P→P的产生式，若有则删除；
• 若某个产生式在推导过程中永远不会被用到，删除它；
• 若某个产生式在推导过程中不能从中导出终结符，删除它；
• 最后，整理所有剩余产生式，就得到简化的文法。

例题

简化

(0)S → Be (1)S → Ec (2)A → Ae (3)A →e

(4)A →A (5)B →Ce (6)B →Af (7)C →Cf

(8)D →f

答案

(0) S → Be

(1)A → Ae

(2)A →e

(3)B →Af

2.4.4 构造无ε产生式的上下文无关文法

无ε产生式的上下文无关文法要满足条件

P中要么不含有ε产生式，要么只有S → ε；

若S → ε，则S不出现在任何产生式右部。

构造无ε产生式的上下文无关文法变换算法：

$G=(V_N,V_T,P,S)G’=(V{’}_N,V{’}_T,P’,S’)$

• 由文法G找出所有经过若干步推导能推出ε的非终结符，放在V0集合中。
• 再按下列步骤构造G’的产生式集合P’；
  • A)若V0集合中的某元素出现在某产生式的右端，则将它变成两个产生式：分别以ε和其原型代入；将新产生式加入P’
  • B)不满足上一条的P中其他产生式除去ε产生式后也加入P’
  • C)如果P中有产生式S → ε，将它在P’中改为S ‘→ ε | S，S’是新的开始符号，$把它加入V_N，形成V{’}_N$

设G1=({S},{a,b},P,S),其中

– P: (0) S → ε (1) S →aSbS (2) S →bSaS

(1)V0={S}

(2)P’: (1) → S →abS|aSbS|aSb|ab

(2) → S →baS|bSaS|bSa|ba

(0) → S’ → ε | S

故：文法G1’=({S’,S},{a,b},P’,S’),其中

P’: (0) S’ → ε | S

(1) S →abS|aSbS|aSb|ab

(2) S →baS|bSaS|bSa|ba

2.5 语法树与二义性文法

2.5.1 语法树

1) 概念⭐

语法树的叶子节点是句子的单词，非叶子节点的是语法成分。

名称	内容
子树	除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
修剪子树	除叶子结点之外的任意结点连同它的所有子孙结点构成子树。
句型	在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。
短语	子树的末端符号自左到右连成串，相对于子树树根而言称为短语。
简单短语（直接短语）	定义： 若 S ⇒* αβδ，且文法中包含产生式 A → β，则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。 语法树： 在语法树中表示为该短语只有上下相邻父子两代 人话就是 ，是由所有叶子节点组成，并且叶子节点的父亲，没有其他子树
句型的短语	该句型中哪些符号串可构成某子树根的短语。
句柄	“可规约串”，句柄对应某个产生式的右部，是某个，但不是任意一个。作为一种规约对象，句柄表示最左直接短语。 语法树： 在语法树上，则表示为最左边的只包含相邻父子节点的短语（最左直接短语）
素短语	定义： 是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语
最左素短语	定义： 最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。 语法树： 通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。

语法图

例题

直接短语的为 S 、（T）、b，短语有S、（T）、b、Sd（T)、Sd（T）db 、（Sd（T）db）。

(T),为什么都是直接短语，是因为(T)，三个都是叶子节点，父亲节点S没有其他子树

d不是直接短语,因为d所在的树还有子树所以它不是 ！

2) 短语，直接短语，句柄

给定句型：

T*P↑(T*F)

给定文法：

G[T]: T → T*F|F F → F↑P|P P → (T)|i

解析：

推导步骤为：

T ⇒ T*F ⇒ T*F↑P ⇒ T*P↑P ⇒ T*P↑(T) ⇒ T*P↑(T*F)

画出语法树为：

该语法树的 5 个子树及 5 个短语为：

求直接短语方法： 该句型的语法树有两颗直接子树（最左边的两颗子树），由这两颗直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语 P 和 T*F。

求句柄： 因为 P 相对 T*F，在语法树上的左侧，所以句柄是 P

最终结果：

类型	内容
短语 5 个	P，TF，(TF)，P↑(TF)，TP↑(T*F)
直接短语 2 个	P，T*F
句柄	P

3) 素短语，最左素短语

给定句型：

FF↑a

给定文法：

G[T]: T → T*F|F F → F↑P|P P → (T)|i

解析：

推导步骤为：

T ⇒ TF* ⇒ TFF ⇒ TF↑*\F* ⇒ TF↑a

画出语法树：

最终结果：

根据定义可以找出素短语有：

类型	内容
素短语 2 个	F↑，a
最左素短语	F↑

2.5.2 二义性

1) 判断二义性文法

依据：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。如果文法是非二义性文法，那么语法树的生成规律不同，但最终生成的语法树形状完全相同；如果文法是二义性文法，那么最终生成的语法树形状有可能不相同。 方法1：若对于一个文法的某一句子存在两棵不同的语法树（或两个不同的 规范推导）；或者自底向上看，对于同一个规范句型，存在两个不同的句柄。则该文法是二义性文法，否则是无二义性文法。 方法2：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。 文法二义性的判定？？：在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。解决方法：提出一些限制条件，称为无二义性的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的。

2) 子树与短语

子树：子树由语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 关系：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。

3) 规约

自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。 规范规约：对句型中最左简单短语（句柄）进行的规约称为规范规约。 注：规范规约与规范推导 互为逆过程。

规范句型：通过规范推导或规范规约所得到的句型称为规范句型。

3. 词法分析

3.1 设计——状态转换图

3.1.1 词法分析概述

• 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。

• 词法分析器(Lexical Analyzer) / 扫描器(Scanner) 功能：输入源程序、输出单词符号 单词符号的种类：基本字、标识符、常数、运算符、界符。 输出的单词符号的表示形式：(单词种别，单词自身的值)

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

  

3.1.2 词法分析器的设计

词法分析程序自动生成有哪些困难？

• 编程过程的设计以及二义性问题。

1) 词法分析器的结构

• 为保证可以扫描完全，我们将扫描缓冲区分为两个半区，互补使用。
• 比如有些语言规定，标识符长度不能超过128，我们就可以推断出编译器的扫描缓冲区总长度为256。

2) 超前搜索

• 某些语言允许程序员编写程序时，不写空格，或可以将基本字再定义。给程序员带来了便利，却给词法分析带来的困难。
• 比如上述的例子，必须超前搜索到“，”与“.” 处，才能分辨出两条语句的不同，才能确定哪些是基本字。
• 几点限制——不必使用超前搜索 所有基本字都是保留字;用户不能用它们作自己的标识符 基本字作为特殊的标识符来处理，使用保留字表 如果基本字、标识符和常数(或标号)之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔

3) 状态转换图

• 状态转换图是一张有限方向图
• 结点代表状态，用圆圈表示
• 状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类
• 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态

4) 状态转换图的实现

不含回路的分叉结点

• 可用一个CASE语句或一组IF-THEN-ELSE语句实现

含回路的分叉结点

• 对应一段由WHILE结构和IF语句构成的程序

终态结点

• 表示识别出某种单词符号，对应返回语句 其中，C为单词种别，VAL为单词自身值

3.2 正规集和正规式

3.2.1概念

设A是非空的有限字母表，A={ai| i=1,2,……n},正规式和正规集的递归定义，对给定的字母表Σ：

• ε和∅都是Σ上的正规式，它们所表示的正规集为{ε}和∅;
• 任何a∈Σ ，a是Σ上的正规式，它所表示的正规集为{a} ;
• 假定e1和e2都是Σ上的正规式，它们所表示的正规集为L(e1)和L(e2)，则：
  • (e1|e2)为正规式，它所表示的正规集为L(e1)∪L(e2)
  • (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)
  • (e1)*为正规式，它所表示的正规集为(L(e1))*仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式表示的字集才是Σ上的正规集。

3.2.2 正规式性质

对正规式，下列等价成立：

若α、β、γ是字母表A上的正规式，且ε∉L(γ)，则

α= β| α γ 当且仅当 α= β γ*

α= β| γ α当且仅当 α= γ* β

3.2.3 正规文法-> 正规式⭐

• 由正规文法G的各个产生式写出对应的正规方程式，得到联立方程组。
• 把方程组中的非终结符当作变元。
• 求此正规式方程组的解，得到关于开始符号S的解：S=w , w ∈VT*，w就是所求正规式。

文法产生式	正规式
$A\to xB,B\to y$	A=xy
$A\to xA\mid y$	$A=x^{\ast }y$
$A\to x,A\to y$	$A=x\mid y$

例题

已知正规文法G1的产生式，求出它

所定义的正规式。

产生式为：S → aS | aB

B → bB|bA

A → cA | c

解：

1.由产生式写出对应的联立方程组

S ＝ aS | aB ……（1）

B ＝ bB|bA ……（2）

A ＝ cA | c ……（3）

2.根据定理2，

由（1） S ＝ aS | aB得： S=a*aB=a+B ……（4）

同理，由（2） B ＝ bB|bA得： B=b+A ……（5）

同理，由（3） A ＝ cA | c得： A=c*c=c+ ……（6）

将（6）代入（5）得：B=b+c+ ……（7）

将（7）代入（4）得：S=a+b+c+ ……（8）

3.故：正规式为S=a+b+c+

3.2.4 正规式-> 正规文法⭐

需要借助有限自动机

3.3 有限自动机(FA)

• 有限自动机是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具。
• 有限自动机是具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去输入处理的信息。

3.3.1 确定有限自动机(DFA)

• 对状态图进行形式化定义
• 确定有限自动机(Deterministic Finite Automata，DFA) M是一个五元式 M=(S,Σ, f, S0, F)，其中： （1）S: 有穷状态集 （2）Σ：输入字母表(有穷) （3）f: 状态转换函数，为S×Σ→S的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’，s’称为s的一个后继状态 （4）S0∈S是唯一的一个初态 （5）F⊆S：终态集(可空)
• 例：DFA M=( {0，1，2，3}，{a，b}，f，0，{3})，其中f定义如下： f(0，a)=1 f(0，b)=2 f(1，a)=3 f(1，b)=2 f(2，a)=1 f(2，b)=3 f(3，a)=3 f(3，b)=3
• 上题对应状态转换矩阵与状态转换图：

• 对于Σ*中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于α，则称α为DFA M所识别(接收)
• DFA M所识别的字的全体记为L(M) L(M)={含aa或bb的字}

3.3.2 非确定有限自动机(NFA)

• 一个非确定有限自动机(Nondeterministic Finite Automata，NFA) M是一个五元式 （1）M=(S,Σ, f, S0, F)，其中： （2）S: 有穷状态集 （3）Σ ：输入字母表(有穷) （4）f: 状态转换函数，为S×Σ*→2S的部分映射S0⊆S是非空的初态集 （5）F⊆S ：终态集(可空)
• 从状态图看NFA 和DFA的区别 （1）NFA可以有多个初态 （2）弧上的标记可以是Σ*中的一个字(甚至可以是一个正规式)，而不一定是单个字符 （3）同一个字可能出现在同状态射出的多条弧上 （4）DFA是NFA的特例
• 对于Σ*中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记字连接成的字等于α(忽略那些标记为ε的弧)，则称α为NFA M所识别(接收)。
• 例题： 答：L(M1)={含aa或bb的字} 答：L(M2)={ambn | m，n≥1}

3.2.3 DFA和NFA 等价条件

• 定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价
• 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的
• 对于每个NFA M存在一个DFA M’，使得L(M)=L(M’)
• DFA与NFA识别能力相同!
• DFA很容易用程序来实现，但设计较难
• NFA设计更容易

3.4 NFA 确定化⭐

3.4.1 解决初始状态唯一性

• 引进新的初态结点X和终态结点Y，X,Y∉S，从X到S0中任意状态结点连一条ε箭弧， 从F中任意状态结点连一条ε箭弧到Y。

3.4.2 简化弧上的标记

• 对M的状态转换图进一步施行替换，其中k是新引入的状态。

3.4.3 对含有ε的NFA 确定化⭐

• 设I是的状态集的一个子集，定义I的ε-闭包，ε-closure(I)为:ε-closure(I)=I∪{s’|从某个s∈I出发经过任意条ε弧能到达s’}
• 设a是Σ中的一个字符，定义Ia=ε-closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。
• 例题：
• Ia=ε-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合
• 对于上一部分的NFA M’，有：

• 这样就得到了状态集之间的关系转换表
• 把表看成状态转换矩阵，子集视为状态，于是转换表唯一刻划了一个DFA
• 初态是ε-closure({X}) 终态是含有原终态Y的子集
• 于是：NFA和DFA等价
• 对刚刚的转换表以及M’进行化简，就将NFA转换为了一个DFA：

3.5 FA 化简⭐

1) 状态的等价性

• DFA的化简(最小化)就是：对于给定的DFA M，寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)
• 状态的等价性定义：如果从状态s出发能读出某个字α而停止于终态，那么同样，从t出发也能读出α而停止于终态；反之亦然两个状态不等价，则称它们是可区别的
• DFA化简基本思想：把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。

2) 化简算法

• 首先，把S划分为终态和非终态两个子集，形成基本划分Π。
• 一般地，对某个a和I(i)，若Ia(i) 落入现行Π中 N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的Π同一子集。重复上述过程，直到Π所含子集数不再增长
• 我们对刚刚得到的DFA进行化简：

1. 划分终态与非终态： I(1)={0, 1, 2}，I(2)={3, 4, 5, 6}
2. 写出Ia(1)={1, 3} ，发现分别落入两个子集，说明第一个子集应该继续划分： I(11)={0, 2}，I(12)={1}，I(2)={3, 4, 5, 6}
3. 写出Ia(11) ={1}，Ib(11)={2, 4}，发现Ib(11)落入两个子集，应该继续划分： I(111) ={0}，I(112) ={2}，I(12) ={1}，I(2)={3, 4, 5, 6}
4. 前三个子集都只有一个元素，不需要看了，看最后一个子集 写出Ia(2) ={3, 6}，Ib(2) ={4, 5} 发现这两个子集都在划分的这一子集中 划分完毕，新子集为：{0} {1} {2} {3, 4, 5, 6} 用3来代表4，5，6，对图进行化简： （所谓代表，就是456射出的弧，都由3来射出，射入也一样）

至此，由NFA等价变换为DFA，并将得到的DFA化简的内容结束。

3.6 正规式和有限自动机的等价性

• 一个正规式r与一个有限自动机M等价 L(r)=L(M)
• FA ->正规式 对任何FA M，都存在一个正规式r，使得L( r )=L(M)。
• 正规式 -> FA 对任何正规式r，都存在一个FA M，使得L(M)=L(r)。
• 由于NFA与DFA是等价的，所以这里的FA具体是哪个并不重要，后续的讨论将使用NFA。

3.6.1 NFA-->正规式⭐

• 定理：对Σ上任一NFA M，都存在一个Σ上的正规式r，使得L®=L(M)。
• 假定NFA M=<S,Σ,δ, S0, F>，我们对M的状态转换图进行以下改造：

1. 在M的转换图上加进两个状态X和Y，从X用ε弧连接到M的所有初态结点，从M的所有终态结点用ε弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，显然L(M)=L(M’)。
2. 然后，反复使用下面的三条规则，逐步消去结点，直到只剩下X和Y为止。 即：增加弧上的标记，减少状态的数量。
3. 最后，X到Y的弧上标记的正规式即为所构造的正规式r 显然L( r )=L(M’)=L(M)

• 得证： 对Σ上任一NFA M，都存在一个Σ上的正规式r，使得L®=L(M)。

3.6.2 数学归纳法

• 定理: 对于Σ上的正规式r，都存在一个NFA M，使L(M)=L®，并且M只有一个初态和一个终态，而且没有从终态出发的箭弧。
• 对给定正规式r中的运算符数目进行归纳：

1) 验证r中的运算符数目为0时，结论成立。

若r具有零个运算符，则r=ε或r=φ或r=a，其中a∈Σ。 结论成立

2) 假设结论对于运算符数目少于k(k≥1)的正规式成立

• 假设对于运算符数目少于k(k≥1)的正规式成立。
• 当r中含有k个运算符时，r有三种情形：

r = r1|r2

• 由归纳假设，对ri存在Mi=<Si,Σi,δi, qi, {fi}>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。
• 不妨设S1∩S1=φ，在S1∪S2中加入两个新状态q0，f0。
• 令M=<S1∪S2∪{q0,f0},Σ1∪Σ2,δ, q0, {f0}>，其中δ定义如下：

于是：L(M)=L(M1)∪L(M2)=L(r1)∪L(r2)=L(r1|r2)= L( r )

r = r1·r2

• 令M=<S1∪S2,Σ1∪Σ2,δ, q1, {f2}>，其中δ定义如下：

于是：L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r1·r2)=L( r )

r = r1*

• 令M=<S1∪{q0, f0},Σ1,δ, q0,{f0}>，其中q0, f0∉S1，δ定义如下(M的状态转换如右图) ：

于是：L(M) = L(M1)* = L(r1)* = L(r1*)= L( r ) 至此，基于该假设，证明结论对于运算符数目为k的正规式成立。

3.6.3 算法与示例

• 现给一个正规式：(a|b)* (aa|bb) (a|b) *
• 构造一个等价的NFA

最后得到： 我们还可以根据之前学到的子集法，把上面这个NFA化简为一个DFA。

有了这些等价关系，我们可以实现词法分析的自动生成。

3.7 正规文法和有限自动机的等价性

3.8 词法分析程序自动生成LEX

LEX的工作过程：

1. 对每条识别规则Pi构造一个相应的非确定有限自动机Mi；
2. 引进一个新初态X，通过ε弧，将这些自动机连接成一个新的NFA；
3. 把M确定化、最小化，生成该DFA的状态转换表和控制执行程序。

• 词法分析程序的自动产生——理论和实践相结合的典范：经典理论是我们进行实践操作的理论支撑。先进技术工具是我们要提高自身能力必须使用的方式。二者结合才能综合提高自身能力。

3.9 总结

• 正规文法、正规集与正规式的概念和关系；
• 如何由正规文法得到正规式；
• NFA的确定化；
• DFA的最小化；
• 对含有ε弧的NFA进行确定化；
• 正规文法、正规式和自动机之间的相互转换

4. 语法分析

4.1 概述

4.1.1功能

编译程序的核心部分

根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。

4.1.2 基本任务

识别符号串S是否为该文法的某语法成分。

4.1.3 两大类方法

①自顶向下分析 基本思想： ②自底向上分析 基本思想： 对比：

类型	方法	主要问题
自顶向下分析	递归子程序法、LL分析法等	①左递归问题：左递归（直接或间接）会 必然 导致分析过程出现死循环 ②回溯问题：试探失败时，需要将输入串指针和语法树都回溯到试探开始时的状态，这很影响效率
自底向上分析	算符优先分析法、LR分析法等	①如何识别句柄 ②二义性文法

4.1.4 理论基础

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

上下文无关法已经讲过了

4.1.5 下推自动机PDA

1) 概念

下推自动机的定义：一个不确定的PDA可以表达成一个7元组： M = (Σ, Q, Γ, δ, q0, Z0, F) 其中，Σ 是输入符号的有穷集合； Q 是状态的有限集合； q0 ∈ Q 是初始状态； Γ 为下推存储器符号的有穷集合； Z0∈Γ 为最初出现在下推存储器顶端的开始符号; F 是终止状态集合，F ⊆ Q； δ 是从 Q×(Σ∪{ε})×Γ 到 Q×Γ* 的子集的映射。

映射关系 δ(q, a, Z) = {(q1, γ1), (q2, γ2), …, (qm, γm)} 其中, q1, q2, …, qm∈Q, a∈Σ, Z∈Γ, γ1, γ2,…,γm∈Γ*。 该映射的意思是：当PDA处于状态 q，面临输入符号 a时，自动机将进入到 qi, i = 1, 2, …, m 状态，并以 γi 来代替下推存储器（栈）顶端符号Z，同时将输入头 指向下一个字符 。当 Z 被 γi 取代时，γi 的符号按照 从左到右的顺序依次从下向上推入到存储器。

特殊情况下，δ(q, ε, Z)={(q1, γ1), (q2, γ2), …, (qm, γm)} 时，输入头位置不移动，只用于处理下推存储器内部 的操作，叫作 “ε移动”。

这些定义我看得快炸了，没理解这是什么意思。下面是一个图，可能比较直观的显示出，下推自动机与有限自动机的区别就是多出一个下推存储器。

以上的定义都是教材的内容，如果光看理论，我反正是一头雾水，不知所云。不过结合一个例子可能会有所理解。下面的例子是判断一个句子是否能够被下推自动机所接受。

2) 下推自动机接受的语言

下推自动机 M 所接受的语言定义为： T(M) = {x|x: (q0, Z0) (q, M γ), γ ∈Γ*, q ∈F }。下面通过这个例子来走一遍过程。看着下面这些符号实在是头大，不过通过具体的例子分析也不难理解。

对于输入 abbcbba 这个句子。下推自动机 是怎么样判断这个句子是否合法呢？它的处理步骤如下：

（一）、#是开始符号，0是初始状态。首先从输入带的第一个字符读入。输入了a，根据规则 1。将A压入栈。状态仍然为0；

（二）、状态为0，输入b。根据规则 2。将B压入栈，状态仍然为0.

（三）、状态为0，输入b。根据规则 2。将B压入栈，状态仍然为0.

（四）、状态为0，输入c。根据规则 3。将ε（空串）压入栈中，也就是什么都不做，状态变为1.

（五）、状态为1，输入b。根据规则 5。将B弹出栈，状态仍然为1.

（六）、状态为1，输入b。根据规则 5。将B弹出栈，状态仍然为1.

（七）、状态为1，输入b。根据规则 4。将A弹出栈，状态仍然为1。

到此为止，所有的字符读取完毕，此时检查到栈里面也只有开始字符，状态为1（中止状态）。因此abbcbba被此下推自动机所接受。

4.2 自顶向下分析

4.2.1 一般过程

给定符号串S，若预测它是某一语法成分，那么可根据该语法成分的文法，设法为S构造一棵语法树。 若成功，则S最终被识别为某一语法成分。即S∈L(G[Z]) 其中G[Z]为某语言成分的文法。 若不成功，则 S 不属于 L(G[Z]) 。

4.2.2 特点

1. 分析过程是带有 预测性 的。即要根据输入符号串中下一个单词，来预测之后的内容属于什么语法成分，然后用相应语法成分的文法建立语法树。
2. 分析过程是一种 试探 过程，是尽一切办法（选用不同规则）设法建立语法树的过程。由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。
3. 最左推导可以编出程序来实现，但在实际上价值不大，效率低，代价高。

4.2.3 解决问题

1) 消除左递归⭐

使用扩充的BNF表示来改写文法

消除直接左递归

通过以下两条规则，就能消除文法的直接左递归，并且保证文法的等价性：

改写规则： （1）提因子 每当出现形如 U∷= x y | x w |….| x z的规则，则将其改写为：U∷= x ( y | w |….| z ) 其中若还有形如y = y1 y2, w = y1 w2的情况，则继续改写为 U∷= x ( y1 ( y2 | w2 ) |….| z )

注： ①若情况是 y x | w x |….| z x，则x 不是公因子，不进行提取。 ②若有规则：U∷= x | x y，则应改写为：U∷= x ( y |ε)，而不是U∷= x (ε| y)。要尽量 将ε安排为最后的选项。 （2）改写直接左递归 若有文法规则：U∷= x | y |…| z | U v，就改写为U∷= ( x | y |…| z ) { v }

消除一般左递归

方法： 1.把G的非终结符整理成某种顺序A1，A2，……An ，使得 A1::= δ1|δ2|……|δk A2::= A1r…… A3::= A2u |A1 v…… ……. 注：即在后面（按序号排）规则的右部中包含前面规则左部的非终结符。

2.根据算法： 3.化简步骤2得到的文法。

2) 将左递归规则改为右递归规则

若有规则：P∷= P α | β 则可改写为：P ∷= β P’ ，P’ ∷= β P’ | ε

3) 消除回溯⭐

回溯：分析工作要部分地或全部地退回去重做叫回溯。 回溯的条件：文法中，对于某个非终结符号的规则其 右部有多个选择，并根据所面临的输入符号不能准确地确定所要的产生式，就可能出现回溯。 例如： U::= α1 | α2 | α3 回溯的坏处：效率严重低下，只有在理论上的意义而无实际意义。 避免回溯的方法 定义：设文法G（不具左递归性），U∈Vn U::= α1 | α2 | α3 FIRST(αi) = {a | αi => a…, a ∈Vt } 方法： 要求文法满足：FIRST(αi ) ∩ FIRST(αj ) =φ (i ≠ j) 即：对文法中的任意一个Vn，其规则右部有多个选择时，由各选择推出的终结符号串的 头符号集合 要两两不相交。

消除回溯的方法 1.改写文法 做法：对具有多个右部的规则 反复 提取左因子 2.超前扫描 做法：当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即 向前侦察 各输入符号串的第二个、第三个符号来确定要选择的目标。

4) 小结

为了实现不带回溯的自顶向下分析，对文法需要满足两个条件： 1、文法是非左递归的； 2、对文法的任一非终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。

解决问题的方法：

消除左递归方法总结

• 对非终结符排序

• 处理第一个非终结符

  如果不存在直接左递归，照搬

• 若第二个非终结符，有中间某个候选式存在直接左递归，就把候选式替换为处理后的结果，再看有没有左递归

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

LL(1)-自左向右扫描(L)、自左向右地分析和匹配输入串(L)、每进行一步推导，只需要向前查看一个输入符号（1）。其分析过程也表现为 最左推导 的性质

4.3.1 LL分析程序构造及分析过程⭐

此过程由三部分组成：分析表、执行程序 (总控程序）、符号栈（分析栈） 分析表示例： 执行程序分析过程：

1. 把 # 和文法识别符号 E 推进栈，并读入输入串的第 一个符号 a，重复下述过程直到正常结束或出错。
2. 根据栈顶符号 X 和当前输入符号a，执行如下操作： ①若X (∈Vt ) = a = #，分析成功，停止。E匹配输入串成功。 ②若X (∈Vt ) = a≠#，把 X 退出栈，再读入下一个符号。 ③若X (∈Vt ) ≠ a，转出错处理。 ④若X∈Vn，查分析表 M： a) M [ X , a ] = X∷= U V W 则将 X 弹出栈，将 U V W逆序入栈 注：U在栈顶 （最左推导） b) M [ X , a ] = error 转出错处理 c) M [ X , a ] = X:: =ε a为X的后继符号，则将X弹出栈（不读下一符号）继续分析。

4.3.2 LL(1)分析表的构造

设有文法G [ Z ] : 定义1 FitstVt集合： 定义2 FollowVt集合：

① 构造集合FIRST的算法

设α= X1 X2 … Xn , Xi∈Vn∪Vt (1) 若Xi∈Vt，则 FIRST( Xi ) = { Xi } (2) 若Xi∈Vn 且 Xi ∷= a…|ε， a∈Vt 则 FIRST( Xi ) = { a , ε} (3) 若Xi∈Vn且Xi∷= y1 y2 …yk，则按如下顺序计算FIRST(Xi) ●若ε∈ FIRST(y1) 则将FIRST(y1) 加入 FIRST(Xi) ； ●若ε∈ FIRST(y1) 则将FIRST(y2) – {ε}加入FIRST(Xi)且若ε∈ FIRST(y2) 则将FIRST(y3) – {ε}加入FIRST(Xi) … ε∈ FIRST(yk-1) 则将FIRST(yk) – {ε}加入FIRST(Xi) 最后，若ε ∈FIRST(y1) ～ FIRST(yk) 则将ε加入FIRST(Xi) 这样，得到FIRST(Xi)，即可求出FIRST(α)。

② 构造集合FOLLOW的算法

设S, A, B∈Vn, 算法：连续使用以下规则，直至FOLLOW集合不再扩大： (1) 若S为识别符号，则把“ # ”加入FOLLOW(S)中； (2) 若A∷=αBβ(β≠ε)，则把FIRST(β)-{ε}加入FOLLOW(B)； (3) 若A∷=αB 或A∷=αBβ， 且β =*> ε则把FOLLOW(A)加入FOLLOW(B) 中去。 注意：FOLLOW集合中不能有ε!!!

③构造分析表

基本思想: 当文法中某一非终结符呈现在栈顶时，根据当前的输入符号，分析表应指示要用该非终结符里的哪一条规则去匹配输入串（即进行下一步最左推导）。 算法： LL(1)文法：对于能用上述算法构造分析表的文法我们称为LL(1)文法，即M [ A , a ] 只对应一条规则或Error。 定义：一个文法G，其分析表M不含多重定义入口（即分析表中无两条以上规则），则称它是一个LL(1) 对于某些文法（非LL(1)文法），有些M[A,a]中可能有若干条规则，这称为分析表的多重定义或者多重入口。 也就是说：如果G是左递归或二义的，那么M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。 反之，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。 改写： 只有部分文法可以从非LL(1)文法改写为LL(1)文法。 LL分析的错误恢复： 当符号栈顶的终结符和下一个输入符号不匹配，或栈顶是非终结符A，输入符号a，而M [ A , a ]为空白（即error）时，则分析发现错误。 错误恢复的基本思想：跳过一些输入符号，直 到期望的同步符号之一出现为止。同步符号是指可重新开始继续分析的输入符号。 非终结符A的同步符号集：FOLLOW(A)∪FIRST(A)∪语句开头的关键字集合 终结符在栈顶而不能匹配：弹出该终结符并发出错误信息信息后继续分析。（把所有其他符号均作为该符号的同步集合元素）

包含左递归和公共左因子的文法肯定不是LL(1)文法

4.3.3 首符号集和后继符号集的求法

1) First集(首符号集)

注：（1）ay是由x经过0到多步推出来的 且a是终结符号，若x是终结符号，First( x ) = { x }; 举例：

2) Follow集(后继符号集,跟随符集)

（1）定义 1.例如：再求FOLLOW( T )的时候，在产生式右边寻找含有T的产生式，并且把它的右边的终结符号写入集合中。

例题： 注解：对于文法开始符号，#都要加进去。

3) 构造首符号集

构造符号的FIRST集步骤： 构造文法符号穿的FIRST的步骤 注：步骤2的j， 1<=j<i. 例题：

四、构造非终结符号的FOLLOW集

说明：比如求FOLLOW(E) ,

1. 从产生式右侧找E，在第5个产生式。
2. 注意形式F -> ( E ) | i,满足形式2，）加入集合中。

求FOLLOW( F ) :
1.找到3式：根据步骤2，FIRST( T ， )加入结合 ，（*）
2.找到4式：因为空串在FIRST( T ， )，所以FOLLOW（T , ）加入集合中，（*，），#，+）；

4.4 递归下降分析法⭐

4.4.1 思想

为文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，按LL(1)形式唯一确定选择哪个候选式进行推导，若遇到某候选式为ε，认为其自动匹配。把这些递归过程组合起来就构成了文法的递归下降分析程序。

注：绝大多数程序设计语言可用CFG来描述，CFG的特点在于其递归性，因此适合使用递归下降程序来分析

4.4.2 实现

• 使用LL(1)文法

  先将文法消除左递归、提取公共左因子，使之成为LL(1)文法，后将每个非终结符对应一个递归过程，过程体是按照相应产生式的右部符号串顺序编写。每匹配一个终结符，则再读入下一个符号，对产生式右部的每个非终结符，则调用相应的过程。注：使用递归实际上与下推栈的原理相同。

• 使用BNF范式

  先将文法改写为BNF形式，后再书写递归子程序。

4.4.3 缺点

1）对文法的要求高，必须满足LL(1)文法。

2）高深度的递归调用会影响语法分析的效率，速度慢，占空间多

4.5 递归子程序法

对语法的每一个 非终结符 都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析序。 过程意义：递归子程序法对应的是 最左推导 过程 优点与缺点： 优点： ①结构、层次清晰，可读性好 ②易于手工实现 ③时空效率较高 主要缺点：更多的手工编写和调试工作

算法框图示例： 注： ①子程序出口前要读符号 ②子程序定义时若需要调用其它子程序，调用前要先读符号。

5. 自底向上分析

基本算法思想: 若采用自左向右地扫描和分析输入串，那么自底向上的基本算法是： 从输入符号串开始，通过反复查找当前句型的句柄（最左简单短语），并利用有关规则进行规约。若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子；否则有语法错误。 分析过程是 重复以下步骤 ： 1、找出当前句型的句柄 x （或句柄的变形）； 2、找出以 x 为右部的规则 X::= x ； 3、把 x 规约为X，产生语法树的一枝。 关键：找出当前句型的句柄 x (或其变形）

5.1 移进—规约分析

要点：设置符号栈，用来纪录分析的历史和现状 ，并根据所面临的状态，确定下一步动作是移进还是规约。 分析器： 分析过程： 注意： 这种方法我们是默认： ① 栈内符号串 + 未处理输入符号串 = 当前句型 ② 句柄都在栈顶（未真正解决句柄的识别问题） 也就是说，移进-规约分析实际上是不靠谱 的，因为： 我们不能认为：对句型 xuy 而言，若有U∷= u，即U => u 就断定u是简单短语，u 就是句柄。而是要同时满足Z =*> xUy。

5.2 简单优先分析法

5.2.1 基本概念

通过语法树来理解这三个概念更加简单：

文法G1[S]： S→AB A→bB A→Aa B→a B→Sb

语法树

1. 短语：若S=*=>αAδ且A=+=>β，则称β是相对于非终结符A的句型αβδ的短语。

   即：语法树中以非终结符的作为根的子树的叶子所组成的字符串。

   如：ba是相对于非终结符A的句型AB的短语。句型baSb的短语有ba，a，Sb，baSb。

2. 直接短语：若S=*=>αAδ且A=>β，则称β是相对于非终结符A的句型αβδ的直接短语。

   即：语法树中以非终结符的作为根的子树，它的孩子都是叶子，没有其他子树。

   如：Sb是相对于非终结符B的句型AB的短语。句型baSb的短语有a，Sb。

3. 句柄：位于句型最左边的直接短语称为该句型的句柄。

   即：位于语法树中最左边的直接短语。

   如：句型baSb的句柄是a。

5.2.2 优先关系定义

1. X和Y优先级相等，表示为 X=·Y，当且仅当G中存在产生式规则A=>···XY···。

   解读：X、Y的优先级相同，当XY存在一个句柄之中，它们将同时被归约。表现在语法树中S=·b。

优先级相等在语法树中

1. X优先级小于Y，表示为 X<·Y ，当且仅当G中存在产生式规则A=>···XB···，B=+=>Y···。

   解读：X优先级小于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，Y一定比X先被规约。表现在语法树中b<·a。

优先级小于语法树中

1. X优先级大于Y，表示为 X>·Y ，当且仅当G中存在产生式规则A=>··BD···，B=+=>···X，D=*=>Y···。

   解读：X优先级大于Y，当XY存在一个句型中时，它们将不可能出现在同一个句柄中，X一定比Y先被规约。表现在语法树中a>·S。

优先级大于在语法树中

1. X和Y的优先级为空，表示在文法的任何句型中都不会出现该符号对相邻出现的情况。

注意：以上优先关系之间不具有对成性。

5.2.3 简单优先文法定义

一个文法是简单优先文法，需要满足以下两个条件：

1. 在文法符号集中V，任意两个符号之间必须之后一种优先关系存在。（显然满足）
2. 在文法中，两个产生式不能有相同的右部。

5.2.4 简单优先分析法的操作步骤

1. 将输入输入串a1a2···an#依次压栈，不断比较栈顶符号ai和下一个待输入符号aj的优先级，若ai>·aj则进行下一步，否则重复此步骤。

   解读：停止条件是ai>·aj表示前面输入串一定比后面先归约，所以只需要在前面找句柄就行了。

2. 栈顶符号ai即为句柄尾，从此处向左寻找句柄头ak，满足ak-1<·ak。

   解读：从后向前找ak-1<·ak表示ak之前的输入串一定比ai···ak后归约，由此确定现在就是要归约ai···ak。

3. 由句柄ai···ak在文法中寻找右部为ai···ak的产生式；找到则将句柄替换为相应左部，找不到则说明该输入串不是该文法的句子。

4. 重复以上步骤直到归约完成。

5.2.5 实例

由于还是以上面的例子不满足简单优先文法定义（b和b的优先关系不唯一），这里我们用另一个文法来举例。

文法G2[S]： S→bAb ① A→(B ② A→a ③ B→Aa) ④

输入串为b(aa)b#

1. 首先我们做出文法符号的优先关系矩阵：

	S	A	B	a	b	(	)	#
S
A				=	=
B				>	>
a				>	>		=
b		=		<		<
(		<	=	<		<
)				>	>
#

这里#比其相邻所有符号的优先性都要小。

1. 然后按照简单优先分析法进行归约：

步骤	栈S	当前输入符	输入串剩余部分	动作
1	#	b	(aa)b#	移进
2	#b	(	aa)b#	移进
3	#b(	a	a)b#	移进
4	#b(a	a	)b#	归约③
5	#b(A	a	)b#	移进
6	#b(Aa	)	b#	移进
7	#b(Aa)	b	#	归约④
8	#b(B	b	#	归约②
9	#bA	b	#	移进
10	#bAb	#		归约①
11	#S	#		接受

其语法树如下：

语法树

5.2.3 缺点

缺点：适用范围小，分析表尺寸太大。

5.3 算符优先分析

算符优先分析法是一种经典的自底向上分析法，简单直观，并被广泛使用。开始主要是对表达式的分析，现在已不限于此，可以用于一大类上下文无关文法（称为OPG）。 特点：仿效四则运算过程，预先规定相邻终结符之间的优先 关系，然后利用这种优先关系来确定句型的句柄（或句柄的变式），并进行规约。 分析器： 优先关系矩阵示例： 分析步骤： (1) 确定终结符之间的优先关系，构造优先关系矩阵。 优先关系： （2）根据优先关系矩阵，利用算法： 当栈顶项（或次栈顶项）终结符的优先级大于栈外的终结符的优先级则进行规约，否则移进。 （3）出错情况

1. 相邻终结符之间无优先关系。
2. 对双目运算符进行规约时，符号栈中无足够项。
3. 非正常结束状态。

重要说明： （1）上述分析过程不一定是严格的最左规约（即不一定是规范规约）。也就是每次规约不一定是规约当前句型的句柄，而是句柄的变形，但也是短语。 （2）实际应用中，文法终结符间优先关系一般不用矩阵表示，而是采用两个优先函数来表示： f — 栈内优先函数 g — 栈外优先函数 若 a < b 则令 f ( a ) < g ( b ) 若a = b 则令 f ( a ) = g ( b ) 若a > b 则令 f ( a ) > g ( b ) 特点： ① 优先函数值不唯一。 ② 优点： • 节省内存空间。 若文法有n个终结符，则关系矩阵为n^2，而优先函数为2n。 • 易于比较：算法上容易实现。数与数比，不必查矩阵。 ③ 缺点：可能掩盖某些错误。

5.4 算符优先分析法的进一步讨论

5.4.1 算符优先文法（OPG）

条件： ①若文法中无形如U∷= …VW…的规则，这里V, W∈Vn，则称G为OG文法，也就是算符文法。 即：算符文法不允许两个非终结符相邻！ ②在任意两个终结符之间，优先关系唯一，则称该文法为算符优先文法(OPG)。 三种可能的优先关系的条件：

5.4.2 构造优先关系矩阵

构造FIRSTVT(U)的算法： 1)若有规则U∷= b…或U∷= V b… 则b∈FIRSTVT(U)（FIRSTVT的定义中一步推导） 2)若有规则U∷= V…且 b∈FIRSTVT(V), 则b∈FIRSTVT(U)（FIRSTVT的定义中多步推导） 有这两个集合后，按照以下规则确定这两种优先关系： 构造LASTVT(U)的算法： 1）若有规则U::=…a 或 U::=…aV，则a∈LASTVT(U) 2）若有规则U::=…V，且a∈LASTVT(V) 则a∈LASTVT(U) 构造优先关系矩阵的算法

优先关系矩阵构造的自然语言描述

（1）构造出FirstVt、LastVt集合。 （2）找出规则右部所有VtVn、VnVt的组合。 （3）对每个（2）中组合找出Vt和FirstVt集或LastVt集的关系。 （4）整理关系，填表。

5.4.3 算符优先分析算法的实现

先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的“句柄”并进行归约。 这里的“句柄”实际上叫做：最左素短语。

素短语

定义：文法G的句型的素短语是一个短语。它至少包含有一个终结符号，并且除它自身以外不再包含其它素短语。 个人理解：含有Vt的短语单元：不能从它里面截出更小的含Vt短语。 注意：素短语可以不是简单短语！ 最左素短语 设有OPG文法句型为: #N1 a1 N2 a2 …Nn an Nn+1# 其中Ni 为非终结符(可以为空)，ai 为终结符。 注意：出现在 aj 左端和 ai 右端的非终结符号一定属于这个素短语，因为我们的运算是中缀形式给出的（OPG文法的特点）。 个人理解：如果不把这两个Vn纳入素短语，经多步规约到某一步后，必然会出现两个Vn相邻情况，且其他情况的短语都已经规约完成了，而OPG不允许有这种规则右部，无法继续规约。 分析过程： 基本部分是找句型的最左子串（最左素短语）并进行规约： ①当栈内终结符的优先级＜或＝栈外终结符的优先级时，移进； ②当栈内终结符的优先级＞栈外终结符的优先级时，表明找到了素短语的尾，再往前找其头，并进行规约。 ③接受条件为符号栈只剩#和开始符合，输入串只剩#。

6. LR分析法

LR分析：从左到右扫描(L)自底向上进行规约®(是规范规约，也即最右推导）是自底向上分析方法的高度概括和集中。（历史 + 展望 + 现状 => 句柄）

6.1 简介

（1）LR分析法的优缺点

① 适合文法类足够大，适用于所有上下文无关文法 ② 分析效率高 ③ 报错及时 ④ 可以自动生成 ⑤ 但手工实现工作量大

（2）分析表的种类

① SLR分析表（简单LR分析表） 构造简单，最易实现，大多数上下文无关文法 都可以构造出SLR分析表，所以具有较高的实用价值。使用SLR分析表进行语法分析的分析器叫SLR分析器。 ② LR分析表（规范LR分析表） 适用文法类最大，所有上下文无关文法 都能构造出LR分析表，但其分析表体积太大，实用价值不大。 ③ LALR分析表（超前LR分析表） 这种表适用的文法类 及其实现上难易 在上面两种之间，在实用上很吸引人。使用LALR分析表进行语法分析的分析器叫LALR分析器。

（3）LR分析器

LR分析器的构成 LR分析器有三部分: 状态栈、分析表、控制程序。

状态栈： 可进一步划分： 状态栈： 划分后的上部，放置分析器状态和文法符号。 S0, S1, …, Sm 状态 S0—初始状态 Sm —栈顶状态 栈顶状态概括了从分析开始到该状态的全部分析历史和展望信息。 符号串： x1 x2… xm 其中：xi∈Vn∪Vt 划分后的下部，为从开始状态(S0)到当前状态(Sm)所识别出的 规范句型的活前缀。 规范句型前缀：将输入串的剩余部分与其连结起来就构成了规范句型。如： x1 x2 … xm ai… an为规范句型。 活前缀：若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀。 规范句型的活前缀： 对于句型αβｔ，β表示句柄，如果αβ= u1 u2 … ur ，那么符号串u1 u2 …ui (1≤i≤r)即是句型αβｔ的活前缀。 个人理解：语法分析没有出错状态下的规范句型前缀就称为规范句型的活前缀。 分析表： 由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同的构造方法。 a. 状态转移表 (GOTO表) 一个矩阵： 行—分析器的状态 列—文法符号（包括Vn和Vt） GOTO[Si-1, xi] = Si Si-1—当前状态（栈顶状态） xi —新的栈顶符号 Si —新的栈顶状态（转移状态） Si需要满足条件是： 若x1 x2 …. xi-1 是由 S0 到 Si-1 所识别的规范句型的活前缀，则 x1 x2 …. xi 是由 S0 到 Si 所识别的规范句型的活前缀。 实际上：状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀。 b. 分析动作表（ACTION表） ACTION[ Si , a ] =分析动作 a∈Vt 分析动作： ① 移进 (shift) ACTION[ Si , a ] = s 动作：将 a 推进栈，并设置新的栈顶状态为 Sj 。Sj =GOTO[ Si, a ]，并将指针指向下一个输入符号。 ② 规约 (reduce) ACTION[ Si, a ] = rd d：文法规则编号(d) A→β 动作：将符号串β(假定长度为n ) 连同状态从栈内弹 出，再把 A 推进栈，并设置新的栈顶状态为Sj。 Sj = GOTO[ Si-n , A ] ③ 接受(accept) ACTION[ Si , # ] = accept ④ 出错 (error) ACTION[ Si , a ] = error a∈Vt 控制程序：执行分析表所规定的动作，对栈进行操作。 1、 根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行由分析表所规定的操作； 2、并根据GOTO表设置新的栈顶状态（即实现状态转移）。 由分析过程可以看到： (1) 每次规约总是规约当前句型的句柄，是规范规约！ (2) 分析的每一步栈内符号串均是规范句型的活前缀，且与输入串的剩余部分构成规范句型。

（4）构造LR分析表

方法： （1）根据文法构造识别 规范句型活前缀 的有穷自动机DFA： ①构造DFA： DFA 是一个五元式 M = ( S, V, GOTO, S0, Z ) S：有穷状态集 在此具体情况下，S = LR(0)项目集规范族。 项目集规范族：其元素是由项目所构成的集合。 V：文法字汇表 S0：初始状态 Z：终态集合 Z = S - { S0 } GOTO：状态转移函数 GOTO[Si , x]=Sj（Si, Sj∈S Si, Sj为项目集，x∈Vn∪Vt） 表示当前状态 Si 面临文法符号 x 时，应将状态转移到Sj 。 构造方法： 一、 确定 S 集合，即LR(0)项目集规范族，同时确定S0 二、确定状态转移函数GOTO ②构造LR(0) LR(0)是DFA的状态集，其中每个状态又都是项目的集合。 项目：文法 G 的每个产生式（规则）的右部添加一个圆点就构成一个项目。 例1： 产生式：A→ X Y Z 项 目： A→ . X Y Z A→ X .Y Z A→ X Y. Z A→ X Y Z . 例2： 产生式：A→ε 项 目： A→. 项目的直观意义：指明在分析过程中的某一时刻的已经规约部分和等待规约部分。 构造方法：

1. 将文法扩充 目的：使构造出来的分析表只有一个接受状态， 这是为了实现上的方便。 方法：修改文法，使识别符号（开始符号）的 规则只有一条。
2. 根据文法列出所有的项目
3. 将有关项目组合成集合，即DFA中的状态；所有状态构成了LR(0) 项目集规范族。 ③ 将有关项目组成项目集，所有项目集构成的集合即为LR(0)。 为实现这一步，需先定义： • 项目集闭包 closure • 状态转移函数GOTO GOTO ( I, X ) = closure (J) I：项目集合 X：文法符号，X∈V J：项目集合 J = { 任何形如A→αX.β的项目| A→α.Xβ∈I } closure (J)：项目集 J 的闭包仍是项目集合。 直观意义： 规定了识别文法规范句型活前缀的DFA从状态I (项目集)出发，经过X弧所应该到达的状态(项目集) 。 LR (0) 项目集规范族的构造算法: ④构造DFA M = ( S , V , GOTO , S0, Z) 其中：S = LR(0) V = { Vn∪Vt} GOTO( Im , X) = In S0 = I0 Z = S - { I0 } 关于该自动机的说明 ①从 I0 到每一状态（除 I0 以外）的每条路径都识别和接受一个规范句型的活前缀。 ②要求状态中每个项目对该状态能识别的活前缀都有效。有效项目定义：若项目A→α.β，对活前缀φα有效，则其条件是存在规范推导： E’=|>φA w =|> φαβw 注意：项目中圆点前的符号串称为活前缀的后缀。 有效项目能预测分析的下一步动作 ③有效项目能预测分析的下一步动作 例： ④DFA中的状态既代表了分析历史又提供了展望信息 每条规范句型的活前缀都代表了一个确定的规范规约过程，故有效状态可以代表分析历史。由于状态中的项目都是有效项目，所以提供了下一步可能采取的动作。 确定当前句柄！： ------------------------------分界线--------------------------------------
4. 正式构造出LR分析表： 1.GOTO表可由DFA直接求出 例： 2.ACTION表由项目集规范族求出 根据圆点所在的位置和圆点后是终结符还是非终结符，把项目集规范族中的项目分为以下四种： 求SLR文法ACTION表的一般方法： 假定一个LR(0)规范族中含有如下的一个项目集（状态） I＝{ X→α·bβ，A→α·，B→β·}（规约-规约冲突） FOLLOW(A)和FOLLOW(B)的交集为空，且不包含b，那 么，当状态I面临任何输入符号a 时:
5. 若a = b，则移进；
6. 若a∈FOLLOW(A)，用产生式A→α进行归约；
7. 若a∈FOLLOW(B)，用产生式B→β进行归约；
8. 此外，报错。

（5）关于LR文法

①对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。 ②并非所有的上下文无关文法都是LR文法。但对于多数程 序语言来说，一般都可用LR文法描述。

6.2 LR(0)文法⭐

定义：假若一个文法G的拓广文法G’的活前缀识别自动机中的每个状态(项目集)不存在下述情况：

1. 既含移进项目又含归约项目
2. 含有多个归约项目 则称G是一个LR(0)文法。 若： a) 移进和归约项目同时存在。移进-归约冲突 b) 归约和归约项目同时存在。归约-归约冲突特点：LR(0)分析器的特点是不需要向前查看任何输入符号就能归约。即当栈顶形成句柄，不管下一个输入符号是什么，都可以立即进行归约而不会发生错误。 LR(0)文法过于简单。即使是定义算术表达式这样的简单文法也不是LR(0)文法，所以没有实用价值！移进-规约冲突 移进和归约项目同时存在 如： 解决方法 — 看FOLLOW集 一般地，假定LR(0)规范族的一个项目集： 如果集合{a1, …, am}, FOLLOW(B1) , … , FOLLOW(Bn)两两不相交（包括不得有两个FOLLOW集合有 # ），则： 说明： • 按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法（向前看了一步）。 • 使用SLR表的分析器叫做一个SLR分析器。 • 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的。

6.3 规范LR(1)分析法⭐

若项目集[ A→α•Bβ ]属于 I 时，则[ B→• γ ] 也属于I。 把FIRST(β)作为用产生式归约的搜索符（称为向前搜索符），即用产生式B→γ归约时查看的符号集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符号的集合也放在相应项目的后面，这种处理方法即为LR(1)分析方法。 LR(1)项目集族的构造： 针对初始项目S’→•S, # 求闭包后再 用转换函数逐步求出整个文法的LR(1)项目集族。 1）构造LR(1) 项目集的闭包函数 a) I 的项目都在closure(I)中； b) 若A→α•Bβ, a属于closure(I)，B→γ是文法的产生式， β∈V*，b∈first(βa)，则B→• γ, b也属于closure(I)； c) 重复b)直到closure(I)不再扩大为止。 2) 转换函数的构造 GOTO(I, X) = closure（J） 其中：I为LR(1)的项目集，X为一文法符号 J = {任何形如A→αX•β, a的项目 | A→α•X β, a属于I } LR(1)分析表的构造算法： LR(1)分析法的特点： • 可适用的文法范围最大。 • 每个SLR(1)文法都是LR(1)文法，但反之不成立！ • LR(1)项目集的构造对某些项目集的分裂可能使状态数目剧烈地增长。

LALR(1)分析⭐

• 对LR(1)项目集规范族合并同心集，若合并同心集后不产生新的冲突，则为LALR(1)项目集。 • 相应的分析方法即为LALR(1)分析法。 合并同心集的几点说明 • 同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集； • 合并同心集后转换函数自动合并； • LR(1)文法合并同心集后只可能出现归约-归约冲突，而没有移进-归约冲突； • 合并同心集后可能会推迟发现错误的时间，但错误出现的位置仍是准确的。

6.4 SLR⭐

LR(0)文法要求文法的每一个LR(0)项目都不含有冲突的项目，这个条件比较苛刻。对于大多数程序设计语言来说，一般都不能满足LR(0)文法的条件。

例如：

不难看出在状态$I_2$中既存在规约项目，又存在移进项目，因而这个文法不是LR(0)文法。

为了对语言句子进行确定性的分析，需要解决冲突。可以采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突，这种分析法称为简单的LR分析法，即SLR(1)分析法。

分析构造LR(0)分析表的方法，易看出是分析表出现多重定义的原因在于其中的规则2。即对于每一个项目集$I_k$中的规约项目$A\to \alpha \cdot$，不管当前输入符号是什么，都将ACTION表中第k行的各个元素均置为$r_j$。

因此当一个LR(0)项目集闺范族中存在一个含有冲突的项目集，例如：

$I_k = { X \to δ ⋅ b B ， A → α ⋅ ， B → r ⋅ } $ 当遇到符号b时，必然会出现多重定义元素。

如要解决则需要向前查看一个输入符号以考察当前所处环境。对规约项目$A\to \alpha \cdot 和B\to r\cdot ,$只需要考察当讲句柄$\alpha$或r规约为A或B时，直接跟在A或B后面的终结符集合即FOLLOW(A)和FOLLOW(B)互不相交且不包含移进符号b，即满足： $FOLLOW(A)\cap FOLLOW(B)=\varnothing$

$FOLLOW(A)\cap \{b\}=\varnothing$

$FOLLOW(B)\cap \{b\}=\varnothing$

那么，当状态k面临输入符号a是，可按下列规则解决冲突：

1. 若a=b则移进
2. 若$a\in FOLLOW(A)$，则用规则$A\to \alpha$进行规约
3. 若$a\in FOLLOW(B)$，则用规则$B\to r$进行规约
4. 此外都报错

SLR分析法的基本思想

这种用来解决分析动作冲突的方法称为SLR(1)方法。如果对于一个文法的某些LR(0)项目集或LR(0)分析表中所含有的动作冲突都能用SLR(1)方法解决，则称这个文法是SLR(1)文法。

SLR(1)分析表的构造

SLR(1)分析表的构造与LR(0)分析表的构造基本相同。（LR(0)分析表的构造方法在这里）

仅对LR(0)分析表构造方法的第二步进行如下修改：

若规约项目$A\to \alpha \cdot$属于$I_k$，则对任何终结符$\alpha \in FOLLOW(A)$置$ACTION[k,a]=r_j$，其中$A\to \alpha$为文法的第j条的规则。

例题

由于LR(0)的能力实在是太弱了。例如：

I = { X=>α·bβ，

A=>α·，

B=>α· }

这时候就存在两个冲突。

1、移进和规约的冲突；

2、规约和规约的冲突。

SLR（1）就是为了解决冲突而设计的，解决冲突的方法就是向后多看一个字符，这就是SLR（1）。

简而言之就是为每个非终结符，计算出它们的follow集。从而可以解决移进与规约、规约与规约的冲突了。

SLR（1）所说的多看一个字符在构造分析表的时候就根据follow集已经构造好了，分析程序和LR(0)是一样的，分析表不同。

具体实现如下：

拓广文法 G'[S']:

(0) S'→S

(1) S→ABC

(2) A→Aa

(3) A→a

(4) B→Bb

(5) B→b

(6) C→Cc

(7) C→c

1、计算初始状态的项目集

Q0=CLOSURE({S'→•S })={ S'→•S , S→•ABC, A→•Aa, A→•a };

2、计算每个状态的项目集

Q1=GO(Q0,a)=CLOSURE({A→a •})={ A→a• };

Q2=GO(Q0,S)=CLOSURE({S'→S •})={ S'→S • };

Q3=GO(Q0,A) = CLOSURE({S→A•BC, A→A•a}) = {S→A•BC, A→A•a, B→•Bb, B→•b}; Q4=GO(Q3,a)=CLOSURE({A→Aa• })={ A→Aa• };

Q5=GO(Q3,b)=CLOSURE({B→b• })={ B→b•};

Q6=GO(Q3,B)=CLOSURE({S→AB•C, B→B•b }) ={ S→AB•C, B→B•b , C→•Cc , C→•c }; Q7=GO(Q6,b)=CLOSURE({B→Bb •})={ B→Bb •};

Q8=GO(Q6,c)=CLOSURE({C→c •})={ C→c •};

Q9=GO(Q6,C)=CLOSURE({S→ABC•, C→C•c })={ S→ABC•, C→C•c }; Q10=GO(Q9,c)=CLOSURE({C→Cc• })={ C→Cc•};

3、构造识别可归约前缀的 DFA

4、计算文法的 FIRST 和 FOLLOW 集合

非终结符	FIRST	FOLLOW
S	a	#
A	a	a,b
B	b	b,c
C	c	c,#

状态节点 Q9= { S→ABC•, C→C•c }中存在存在移进-规约冲突。

{b}∩FOLLOW(S) ={b}∩{#}=Φ，因此文法是 SLR(1)文法。

5、构造 SLR(1)分析表

	a	b	c	#	S	A	B	C
0	S1				2	3
1	R3	R3
2				acc
3	S4	S5					6
4	R2	R2
5		R5	R5
6		S7	S8					9
7		R4	R4
8			R7	R7
9			S10	R1
10			R6	R6

实验程序：

#include<bits/stdc++.h>
#define ROW 12
#define COLUMN 9
using namespace std;
//产生式
string products[8][2]={
{"S'","S"},
{"S","ABC"},
{"A","Aa"},
{"A","a"},
{"B","Bb"},
{"B","b"},
{"C","Cc"},
{"C","c"}
};
//SLR（1）分析表
string actiontable[ROW][COLUMN]={
{"","a","b","c","#","S","A","B","C"},
{"0","s1","","","","2","3","",""},
{"1","r3","r3","","","","","",""},
{"2","","","","acc","","","",""},
{"3","s4","s5","","","","","6",""},
{"4","r2","r2","","","","","",""},
{"5","","r5","r5","","","","",""},
{"6","","s7","s8","","","","","9"},
{"7","","r4","r4","","","","",""},
{"8","","","r7","r7","","","",""},
{"9","","","s10","r1","","","",""},
{"10","","","r6","r6","","","",""}
};
stack<int> sstatus; //状态栈
stack<char> schar; //符号栈
struct Node{
    char type;
    int num;
};
//打印步骤
void print_step(int times){
    stack<char> tmp2;
    cout<<times<<setw(4);
    while(!schar.empty()){
        char t=schar.top();
        schar.pop();
        tmp2.push(t);
        cout<<t;
    }
    while(!tmp2.empty()){
        int t=tmp2.top();
        tmp2.pop();
        schar.push(t);
    }
}
//查表
Node Action_Goto_Table(int status,char a){
    int row=status+1;
    string tmp;
    for(int j=1;j<COLUMN;j++){
        if(a==actiontable[0][j][0]){
            tmp=actiontable[row][j];
        }
    }
    Node ans;
    if(tmp[0]>='0'&&tmp[0]<='9'){
        int val=0;
        for(int i=0;i<tmp.length();i++){
            val=val*10+(tmp[i]-'0');
        }
        ans.num=val;
        ans.type=' ';
    }else if(tmp[0]=='s'){
        int val=0;
        for(int i=1;i<tmp.length();i++){
            val=val*10+(tmp[i]-'0');
        }
        ans.type='s';
        ans.num=val;
    }else if(tmp[0]=='r'){
        int val=0;
        for(int i=1;i<tmp.length();i++){
            val=val*10+(tmp[i]-'0');
        }
        ans.type='r';
        ans.num=val;
    }else if(tmp[0]=='a'){
        ans.type='a';
    }else{
        ans.type=' ';
    }
    return ans;
}
//SLR(1)分析算法
bool SLR1(string input){
    while(!sstatus.empty()){
        sstatus.pop();
    }
    while(!schar.empty()){
        schar.pop();
    }
    int times=0;
    bool flag=true;
    int st=0;
    sstatus.push(st);
    schar.push('#');
    int i=0;
    char a=input[i];
    while(true){
        Node action=Action_Goto_Table(st,a);
        if(action.type=='s'){
            st=action.num;
            sstatus.push(st);
            schar.push(a);
            a=input[++i];
            print_step(++times);
            cout<<setw(10)<<'s'<<st<<endl;

        }else if(action.type=='r'){
            int n=action.num;
            string ls=products[n][0];
            string rs=products[n][1];
            for(int j=0;j<rs.length();j++){
                sstatus.pop();
                schar.pop();
            }
            schar.push(ls[0]);
            st=sstatus.top();
            action =Action_Goto_Table(st,ls[0]);
            st=action.num;
            sstatus.push(st);
            print_step(++times);
            cout<<setw(10)<<'r'<<" "<<ls<<"->"<<rs<<endl;

        }else if(action.type=='a'){
            flag=true;
            break;
        }else{
            flag=false;
            break;
        }
    }
    return flag;
}
int main(){
    string input;
    while(cin>>input){
        if(SLR1(input)){
            cout<<"syntax correct"<<endl;
        }else{
            cout<<"syntax error"<<endl;
        }
    }
    return 0;
}

6.4 LR分析法总结

关系

7. 语法制导的语义计算

7.1 基本概念

语义分析是上下文有关的，目前较为常见的是用属性文法来描述程序语言语义，并采用语法制导翻译的方法完成对语法成分的翻译工作。

1) 属性文法

• 属性文法，也称属性翻译文法
• Knuth在1968年提出
• 以上下文无关文法为基础

在文法G[S]的基础上，为文法符号关联有特定意义的属性，并为产生式关联相应的语义动作或条件谓语，称之为属性文法，并称文法G[S]为之的基础文法。

属性文法AG是一个四元式，即AG = (G, A, R, B)：G是上下文无关文法，A是属性的有限集合，R是语义规则式的有限集合，B是样式的有限集合。

例子：

产生式	语义动作
S -> ABC	{B.in_num := A .num; C.in_num := A .num; if (B.num=0 and (C.num=0) then print(“Accepted!” ) else print(“Refused!” ) }
A -> A1a	{ A.num := A1.num + 1 }
A -> ε	{ A.num := 0 }
B -> B1b	{ B1.in_num := B.in_num; B.num := B1.num-1 }
B -> ε	{ B.num := B.in_num }
C -> C1c	{ C1.in_num := C.in_num; C.num := C1.num-1 }
C -> ε	{ C.num := C.in_num }

2)两种属性：

1. 综合属性

用于“自下而上”传递信息 对关联于产生式 A -> α 的语义规则 b:=f(c1, c2, …, ck) ，如果 b 是 A的某个属性, 则称 b 是 A 的一个综合属性 。

• 自下而上传递信息
• 语法规则：根据右部候选式中的符号的属性计算左部被定义符号的综合属性
• 语法树：根据子结点的属性和父结点自身的属性计算父结点的综合属性

2. 继承属性

用于“自上而下”传递信息 对关联于产生式 A-> α 的语义规则b:=f(c1, c2, …, ck)，如果 b 是产生式右部某个文法符号 X 的某个属性，则称 b 是文法符号 X 的一个继承属性。

例子：

在上例的属性文法中A .num，B.num 和 C.num 是综合属性值，而B.in_num 和 C.in_num 是继承属性值。比如在产生式C -> C1c中，C1.in_num 是产生式右部符号C1的属性，由产生式左部符号C的in_num 属性确定，所以它是继承属性，“自上而下”的传递信息；C.num 是产生式左部符号C的属性，由产生式右部符号C1的num属性确定，所以它是综合属性，“自下而上”的传递信息。

3) 带标注语法分析树

即在语法树的基础上，将原来的非终结符结点修改为综合属性的赋值。

下面是一个简单表达式文法G[S]的一个仅含综合属性的属性文法(开始符号为S) S→E{print(E.val)} E→E1+T{E.val:=E1.val+T.val} E→T{E.val:=T.val} T→T1∗F{T.val:=T1.val×F.val} T→F{T.val:=F.val} F→(E){F.val:=E.val} F→d{F.val:=d.lexval}

其中d.lexvald.lexval表示数值，E.val,T.val,F.val都为综合属性 现在要给表达式3∗(5+4)构造语法树和带标注语法分析树：

下面则是一个包含综合属性、继承属性的属性文法： E→TR{R.in:=T.val;E.val:=R.val} R→+TR1{R1.in:=R.in+T.val;R.val:=R1.val} R→−TR1{R1.in:=R.in−T.val;R.val:=R1.val} R→ε{R.val:=R.in} T→num{T.val:=lexval(num)} 其中lexval(num)表示从词法分析程序得到的常数值。 可见E.val,T.val,R.val都为综合属性，R.in为继承属性 现在要给表达式3+4−5构造语法树和带标注语法分析树：

S-属性文法

只包含综合属性的属性文法。

L-属性文法

可以包含综合属性，也可以包含继承属性。但产生式右端某文法符号的继承属性的计算只取决于该符号左边文法符号的属性（对于产生式左边文法符号，只能是继承属性）。

4) 语义计算模型

• 属性文法：侧重于语义计算规则的定义
• 翻译模式：侧重于语义计算过程的定义

7.2 基于属性文法的语义计算

按照语义规则进行属性计算的3种方法

• 依赖图
• 树遍历
• 一遍扫描

7.2.1 语义子程序

1) 作用

用来描述一个产生式所对应的翻译工作。

– 如：改变某些变量的值；查填各种符号表；发现并报告源程序错误；产生中间代码等。

• 注：这些翻译工作很大程度上决定了要产生什么形式的中间代码。

2) 写法

语义子程序写在该产生式后面的花括号内。X →α {语义子程序1}

注：在一个产生式中同一个文法符号可能出现多次，

但他们代表的是不同的语义值，要区分可以加上角标。

如：E →E(1)+E (2)

3) 语义值

为了描述语义动作，需要为每个文法符号赋予不同的语义值：类型、地址、代码值等

4) 语义栈

• 各个符号的语义值放在语义栈中

  当产生式进行归约时，需对产生式右部符号的语义值进行综合，其结果作为左部符号的语义值保存到语义栈中。

• 下推栈包含3部分：

  状态栈、符号栈和语义栈

  注：语义栈与状态栈和符号栈是同步变化的。

5) 例题

产生式	语义子程序
S` →E	{PRINT E•VAL}
E →E(1)+E(2)	{E•VAL= E (1) •VAL +E(2) •VAL }
E →E (1)*E(2)	{E•VAL= E (1) •VAL *E(2) •VAL }
E →(E (1))	{E•VAL= E (1) •VAL }
E → i	{E•VAL= LEXVAL }

注：LEXVAL指的是词法分析送来的机内二进制整数。

7.2.2 依赖图

通过寻找属性之间的依赖关系，来确定属性计算的先后顺序，选择相应的语义规则，完成语义计算。

• 在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由依赖图（有向图）来描述。
• 为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b :=f（c 1，c 2…c k）的形式
• 依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点用一条有向边连到属性b的结点。E→E1+E2 E.val := E1.val+E2.val
• 依赖图的构建算法

//第一遍循环
for (结点 n : 语法树){
	for(文法符号属性 a : n){
		在依赖图中为a建立结点;
	}
}
//第二遍循环
for (结点 n : 语法树){
	for(语义规则 b : n){
		//语义规则的形式为 b := f(c1,c2,...,ck)
		//ci为b所依赖的属性
		for(依赖属性 c: b){
			构造从 c 指向 b 的有向边;
		}
	}
}
12345678910111213141516

• 对于属性文法：

产生式	语义规则
D→TL	L.in := T.type
T → int	T.type := integer
T → real	T.type := real
T→T1*F	T.val := T1.val*F.val
L → L1,id	L1.in := L.in addtype(id.entry, L.in)
L → id	addtype(id.entry, L.in)

语句 real id1,id2,id3的依赖图可以画成： 注意⑦⑨⑩是虚拟结点

• 良定义的属性文法
  • 如果一属性文法不存在属性之间的循环依赖关系，则称该文法为良定义的
  • 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序
• 属性的计算次序
  • 基础文法用于建立输入符号串的语法分析树
  • 根据语义规则建立依赖图
  • 根据依赖图的拓扑排序，得到计算语义规则的顺序输入串→语法树→依赖图→语义规则计算次序

7.2.3 树遍历

通过树遍历的方法计算属性的值

• 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性
• （不需要建立依赖图）以某种次序遍历语法树，直至计算出所有属性
• 深度优先，从左到右的遍历输入串→语法树→遍历语法树计算属性

树遍历算法

while(还有未被计算的属性){
	VisitNode(S);//S 是开始符号
}

//从根节点开始递归计算属性
void VisitNode(Node N){
	if(N是非终结符){
		//N的继承属性应该已经被计算出或者由编译器提供
		//假定当前产生式是 N-> X1 X2 ... Xm，共m项
		for(int i=1;i<=m;i++){
			if(Xi 是非结符){
				计算Xi 中能够计算的继承属性;
				VisitNode(Xi);
				计算Xi 中能够计算的综合属性;
			}
		}
		计算N中能够计算的综合属性;
	}
}
12345678910111213141516171819

树遍历示例

反复调用VisitNode(S)直到所有继承属性和综合属性都能被计算出来或者不再有更多的属性可以被计算为止。 第一次调用可以计算出Z.h=0和Z.g=1 第二次调用可以计算出X.c=1、X.d=2和S.b=0 第三次调用可以计算出Y.e=0和Y.f=0 请直接观看视频。

7.2.4 一遍扫描

• 在语法分析的同时计算属性值
  • 所采用的语法分析方法
  • 属性的计算次序
• 所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则
• 语义规则被计算的时机
  • 自上而下分析，一个产生式匹配输入串成功时
  • 自下而上分析，一个产生式被用于进行归约时
• 在语法分析的同时计算属性值
• 适用于 S-属性文法 / L-属性文法

抽象语法树AST

抽象语法树(Abstract Syntax Tree，AST)，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示 3*5+4：

建立表达式的抽象语法树

函数声明	作用
mknode(op, left, right)	建立一个运算符号结点，标号是op， 两个域left和right分别指向左子树和右子树
mkleaf(id, entry)	建立一个标识符结点，标号为id， 一个域entry指向标识符在符号表中的入口
mkleaf(num, val)	建立一个数结点，标号为num， 一个域val用于存放数的值

运用以上函数，可以写出以下产生式的语义规则：

产 生 式	语 义 规 则
E→E1+T	E.nptr := mknode(‘+’, E1.nptr, T.nptr ) 注意：此时我们认为E1和T已经被构建成了某一语法子树的根节点
E→E1-T	E.nptr := mknode(‘-’, E1.nptr, T.nptr )
E→T	E.nptr := T.nptr
T→ (E)	T.nptr := E.nptr 括号对于计算是多余的
T→id	T.nptr := mkleaf ( id, id.entry )
T→num	T.nptr := mkleaf ( num, num.val )

显然这种抽象语法树特别适合于自下而上的属性计算。

a - 4 + c对应的抽象语法树如下：

总结

了解综合属性和继承属性。已知属性文法和输入符号串，构建语法树和带标注语法分析树。

属性 描述文法符号的类型、值等有关的一些信息，它可以被计算或传递。

语义动作 指产生式相关联的指定操作

条件谓词 指产生式关联的接受条件，或者根据该条件谓词决定做什么语义动作

语义规则集 通常是产生式关联的一组语义规则，每个语义规则可以是一个语义动作或条件谓词。

属性attatt可以与某个文法符号aa关联，用a.atta.att来表示这种关联

现有一文法： E→T1+T2∣T1&&T2 T→num∣true∣false

将上面的文法描述为类型检查的属性文法：

E→T1+T2{T1.type=int&&T2.type=int} E→T1&&T2{T1.type=bool&&T2.type=bool} T→num{T.type=int T→true{T.type=bool} T→false{T.type=bool}

8. 静态语义分析和中间代码生成

8.1 中间语言

8.1.1 概述

「特点」

• 独立于机器
• 复杂性界于源语言和目标语言之间

「优点」

• 使编译程序的结构在逻辑上更为简单明确
• 便于进行与机器无关的代码优化工作
• 易于移植

「常用的中间语言」

• 后缀式：逆波兰表示
• 图表示：抽象语法树（AST）、有向无环图（DAG）
• 三地址代码：四元式、三元式、间接三元式

8.1.2 逆波兰式(后缀式)

1) 定义

逆波兰表示法即为后缀表示法，而默认我们使用的表达式是中缀表示法

程序设计语言中的表示	-----逆波兰表示-----
a+ba+b	ab+ab+
−a−a	a@a@
a+b∗ca+b∗c	abc∗+abc∗+
(a+b)∗c(a+b)∗c	ab+c∗ab+c∗
a:=b∗c+b∗da:=b∗c+b∗d	abc∗bd∗+:=abc∗bd∗+:=
a:=b∗(c+b)∗(−d)a:=b∗(c+b)∗(−d)	bcb+∗d@∗:=bcb+∗d@∗:=

逆波兰式的使用：需使用额外的标识符栈。顺序扫描逆波兰表达式的时候，遇到标识符直接入栈。

遇到运算符时：

1. 根据运算符目数，从栈顶取出相应数目的标识符做运算，并把运算结果压栈
2. 运算结束时，标识符栈应该只剩下一个元素，且为运算结果

2) 计算方式

3) 表达式 => 后缀式

• 表达式 => 后缀式的属性文法
• 中缀表达式 => 后缀式

8.1.3 图表示法

1) 有向无环图

• 对表达式中的每个子表达式，DAG中都有一个结点
• 一个内部结点代表一个操作符，它的孩子代表操作数
• 在一个 DAG 中代表公共子表达式的结点具有多个父节点

树形表示和三元式表示非常相似，如a:=b∗c+b∗da:=b∗c+b∗d表示为： 注意赋值表达式中被赋值对象在树的左孩子节点位置

单目运算−T1−T1直接表示成：

2) 举例

8.1.4 三地址代码

1) 概述

• 「形式」x : = y o p z x:=y\ op \ zx:=y o**p z
• 「理解」三地址代码可以看成是抽象语法树或有向无环图的一种线性表示
• 「抽象语法树 vs. 三地址代码」
• 「有向无环图 vs. 三地址代码」
• 「三地址语句的种类」

2) 四元式

四元式(op,A1,A2,R)(op,A1,A2,R)

opop为运算符 A1A1为第一运算对象 A2A2为第二运算对象 RR为运算结果

例如a:=b∗c+b∗da:=b∗c+b∗d的四元式表示： (1)(∗,b,c,t1)(1)(∗,b,c,t1) (2)(∗,b,d,t2)(2)(∗,b,d,t2) (3)(+,t1,t2,t3)(3)(+,t1,t2,t3) (4)(:=,t3,−,a)(4)(:=,t3,−,a)

和三元式的差别在于，四元式对中间结果的引用必须通过给定的名字(临时变量)

它的三地址码写法为： t1:=b∗ct1:=b∗c t2:=b∗dt2:=b∗d t3:=t1∗t2t3:=t1∗t2 a:=t3a:=t3

3) 三元式

在四元式基础上优化，用编号代表结果。

三元式(op,A1,A2)(op,A1,A2)

opop为运算符 A1A1为第一运算对象 A2A2为第二运算对象

例如a:=b∗c+b∗da:=b∗c+b∗d表示为： (1)(∗,b,c)(1)(∗,b,c) (2)(∗,b,d)(2)(∗,b,d) (3)(+,(1),(2))(3)(+,(1),(2)) 这里用(1)和(2)来表示中间计算结果的显式引用 (4)(:=,(3),a)(4)(:=,(3),a) 这里相当于a:=(3)a:=(3)

而单目运算的−b−b可以表示成(−,b,/)(−,b,/)

4) 间接三元式

在三元式的基础上再度优化，使得式子发生变化时，可变性更强。

• 「定义」间接三元式 = 三元式表 + 间接码表
  • 间接码表：一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置
• 「优点」方便优化，节省空间

8.2 赋值语句的翻译

8.2.1 赋值语句的属性文法

1) 概述

• 「赋值语句形式」$i d : = E $
• 「赋值语句意义」
  • 对表达式 E 求值并置于变量 T 中
  • $id.place:=T$
• 「赋值语句 => 三地址代码的 S-属性文法」

2) 语义规则

• 赋值语句生成三地址代码的 S-属性文法
• g e n ( ) 函数用于生成语句的三地址代码

8.2.2 赋值语句的翻译模式

• 产生赋值语句三地址代码的翻译模式

8.3 数组元素引用的翻译

8.3.1 数组元素地址计算

1) 计算公式

• 设A为n维数组，按行存放，每个元素宽度为w

  • $l o w_i $为第 i 维的下界
  • $u{p}_i$为第 i维的上界
  • $n_i$为第 i ii 维可取值的个数$(n_i=u{p}_i-lo{w}_i+1)$
  • base为 A 的第一个元素相对地址

• 元素

  $A[i_1,i_2,...,i_k]$相对地址公式

  • 可变部分 $V=((...((i_1{n}_2+i_2)n_3+i_3)...)n_k+i_k)\ast w$
  • 不变部分$C=base-((...((lo{w}_1{n}_2+lo{w}_2)n_3+lo{w}_3)...)n_k+lo{w}_k)\ast w$
  • 相对地址 = V + C

2) 产生式 / 属性定义

• 产生式
• 属性定义

8.3.2 带数组元素引用的赋值语句翻译模式

此翻译模式与自下而上的语法分析方法结合在一起，可以一遍扫描就完成语法分析和翻译。

1) 赋值语句类别

2) 赋值语句翻译

8.3.3 类型转换

「类型转换的三个功能」

• 检查操作数类型
• 确定结果的类型
• 如果有必要，将整型转变为实型

「类型转换的三地址代码举例」

「类型转换属性文法」

「类型转换的语义动作举例」

8.4 布尔表达式的翻译

8.4.1 布尔表达式概述

1) 文法 & 用途

「文法」

$E\to EorE|EandE|notE|(E)|iropi|i$

• rop 为关系运算符，包含 [>, >=, <, <=, <>, ==]
• i 表示单个布尔变量
• 运算优先级：括号 > 条件表达式 > not > and > or

「用途」

• 用于逻辑演算，计算逻辑值
• 用于控制语句的条件式

2) 布尔表达式两种计算方法

「数值表示法」

• 如同计算算术表达式一样，一步步算
• 举例

「带优化的翻译法」

• 相比数值表示法，可以减少很多冗余计算，效率更高
• 适合于作为条件表达式的布尔表达式使用
• 举例

8.4.2 按数值表示法翻译

1) 数值表示法

「a or b and not c」

• $T_1:=notc$
• $ T_2:=b \ and\ T_1$
• $T_3:=aor{T}_2$

「a < b」

• 等价于「if a < b then 1 else 0」，进行如下翻译
• $100:ifa<bgoto103$
• $101:T:=0$
• $102:goto104$
• $103:T:=1$
• 104 :

2) 翻译模式

「基础说明」

• 过程 emit 将三地址代码送到输出文件中
• nextstat: 输出序列中下一条三地址语句的地址索引
• 过程 emit 每产生一条指令，nextstat 加 1
• 举例

「布尔表达式翻译模式」

「布尔表达式 a<b or c<d and e<f 翻译举例」

8.4.3 带优化的翻译

「核心思想」从左到右判断，当结果已经得出时，退出。

「举例」

8.4.4 布尔表达式的属性文法

1) 属性

• 语义函数 newlabel，返回一个新的符号标号
• 对于一个布尔表达式 E，设置两个继承属性
  • E.true 是 E 为 ‘真’ 时控制流转向的标号
  • E.false 是 E 为 ‘假’ 时控制流转向的标号
• E.code 记录 E 生成的三地址代码序列

2) 文法

• 产生布尔表达式三地址代码的属性文法

$E\to E_{1}or{E}_2$

$ E\rightarrow E_1 \ and\ E_2$

$E\to not{E}_1,E\to (E_1)$

$E\to i{d}_{1}relopi{d}_2$

• 举例

「布尔表达式：a < b or c < d and e < f」

「翻译流程：第一遍扫描 — 构建语法树」

• 整个表达式的真假出口分别置为 Ltrue、Lfalse

「翻译流程：第二遍扫描 — 自上而下求出继承属性」

「翻译流程：第三遍扫描 — 自上而下求出综合属性 E.code」

E.code: (red)
    if a < b goto Ltrue
    goto L1
E.code: (blue)
    if c < d goto L2
    goto Lfalse
E.code: (green)
    if e < f goto Ltrue
    goto Lfalse

E.code: (purple)
    if c < d goto L2
    goto Lfalse
L2: if e < f goto Ltrue
    goto Lfalse

E.code: (black)
    if a < b goto Ltrue
    goto L1
L1: if c < d goto L2
    goto Lfalse
L2: if e < f goto Ltrue
    goto Lfalse

8.4.5 布尔表达式的一遍扫描翻译模式

1) 定义引入

「翻译过程以四元式为中间语言」

• 四元式存入一个数组中，数组下标代表四元式的标号
• 约定
  • 四元式 (jnz, a, -, p) 表示 if a goto p
  • 四元式 (jrop, x, y, p) 表示 if x rop y goto p
  • 四元式 (j, -, -, p) 表示 goto p
• 过程 emit 将四元式代码送到输出数组中

「E 综合属性 E.truelist 和 E.falselist」

• E.truelist 和 E.falselist 分别记录布尔表达式 E 所对应的四元式中需回填 “真”、“假” 出口的四元式的标号所构成的链表
• 举例

「语义变量和过程」

• 变量nextquad
  • 指向下一条将要产生但尚未形成的四元式的地址（标号）
  • nextquad 初值为 1，每当执行一次 emit 之后，nextquad 自动增一
• 函数makelist(i)
  • 创建一个仅含 i 的新链表，其中 i 式四元式数组的一个下标（标号）
  • 函数返回指向这个链的指针
• 函数merge(p_1,p_2)
  • 把以$p_1$和$p_2$为链首的两条链合并为一
  • 函数值返回合并后的链首
• 过程$backpatch(p,t)$
  • 完成 “回填”
  • 把 p 所链接的每个四元式的第四区段都填为 t

「布尔表达式的文法」

• $E\to E_{1}orM{E}_2$
• $E\to E_{1}andM{E}_2$
• $E\to not{E}_1$
• $E\to (E_1)$
• $E\to i{d}_{1}relopi{d}_2$
• $E\to id$
• $M\to \epsilon$
  • $\{M.quad:=nextquad\}$

2) 布尔表达式翻译模式

「举例：一遍扫描」

8.5 控制语句的翻译

「常用的控制语句」

• 单分支：$S\to ifEthen{S}_1$
• 双分支：$S\to ifEthen{S}_{1}else{S}_2$
• 循环: $S\to whileEdo{S}_1$

8.5.1 控制语句的属性文法

1) 基础定义

「属性定义」

• E.true、E.false 表示 E 为真 / 假时的跳转语句标号
• S.begin、S.next 表示语句 S 开始执行、执行结束后的地址

「if-then 语句的属性文法」

「if-then-else 语句的属性文法」

「while-do 语句的属性文法」

2) 三遍扫描示例

「三遍扫描的属性计算示例」

while a<b do
    if c<d then x:=y+z
    else x:=y-z
123

• 第一遍：构建语法树
• 第二遍：自上而下计算继承属性
• 第三遍：自下而上计算综合属性（code）

即上述 while 控制语句最终得到如下所示的翻译结果：

L1: if a<b goto L2
    goto Lnext
L2: if c<d goto L3
    goto L4
L3: T1 := y+z
    x := T1
    goto L1
L4: T2 := y-z
    x := T2
    goto L1
12345678910

8.5.2 控制语句的属性文法

「控制语句的文法」

• $S\to ifEthenS$
• $S\to ifEthenSelseS$
• $S\to whileEdoS$
• $S\to beginLend$
• $S\to A$
• $L\to L;S$
• $L\to S$

其中 S 表示语句，L 表示语句表，A 表示赋值语句，E 表示布尔表达式。

1) if 语句的翻译模式

「改写后的产生式」

• $S\to ifEthenM{S}_1$
• $S\to ifEthen{M}_1{S}_{1}Nelse{M}_2{S}_2$
• $M\to \epsilon$
• $N\to \epsilon$

「翻译模式」

• S.nextlist 属性：保存 S 翻译生成的代码中需要回填的，要跳转到 S 的后继语句的那些四元式。

2) while-do 语句的翻译模式

「改写后的产生式」

• $S\to while{M}_{1}Edo{M}_2{S}_1$
• $M\to \epsilon$

「翻译模式」

3) 复合语句的翻译模式

「改写后的产生式」

• $S\to beginLend$
• $L\to L_1;MS|S$
• $M\to \epsilon$

「翻译模式」

「其它语句的翻译」

4) 一遍扫描示例

「控制语句示例」

while a<b do
    if c<d then x:=y+z;

5) for循环语句翻译

现需要翻译语句：forI:=1step1untilYdoX:=X+1 等价于C语言的：

for(I=1;I<=Y;++I) X=X+1;
I:=1100
goto 103
I:=I+1
if I<=Y goto 105
goto 108
T:=X+1
X:=T
goto 102

6) 数组的翻译

对于一个静态的n维数组，要访问其中一个元素，可以使用下标法：A[i1,i2,...,in]

由于内存是一维连续空间，对于行主数组，比如一个2×32×3的二维数组，在内存中的布局A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]

现知道数组AA的地址为aa，那A[i,j]A[i,j]的地址为：

a+(i−1)×3+(j−1)

设BB为n维数组B[l1:u1,l2:u2,...,ln:un]

显然di=ui−li+1。令b是数组首元素地址，那么行主数组下B[i1,i2,...,in]的地址D为：

D=b+(i1−l1)d2d3...dn+(i2−l2)d3...dn+(in−1−ln−1)dn+(in−ln)

对式子展开可以提取出式子中的固定部分和变化部分：

D=constPart+varPart constPart=b−C C=l1d2d3...dn+l2d3...dn+...+ln−1dn−1+lndn varPart=i1d2d3...dn+i2d3...dn+...+in−1dn−1+indn

访问数组元素A[i1,i2,...,in]需要产生两组计算数组的四元式：

1. 一组计算varPart，存放结果到临时单元T中
2. 一组计算constPart，存放结果到另一个临时单元T1中

用T1[T]表示数组元素的地址

变址取数的四元式：(=[],T1[T],−,X),相当于X:=T1[T] 变址存数的四元式：([]=,X1,−,T1[T])相当于T1[T]:=X

现在有一个10*20的数组A，即d1=10,d2=20。则X:=A[I,J]的四元式序列为： (∗,I,20,T1) (+,T1,J,T1) (−,A,21,T2) (=[],T2[T1],−,T3) (:=,T3,−,X)

对应： varPart=20∗I+J constPart=A−(1∗20+1)=A−21

9. 运行时存储组织

9.1 概述

运行时的存储组织及管理是目标程序运行时所需要存储空间的组织与管理以及源程序中变量存储空间的分配。

静态存储分配

在编译阶段由编译程序实现对存储空间的管理，和为源程序中的变量分配存储的方法。

条件：如果在编译时能够确定源程序中变量在运行时的数据空间大小，且运行时不改变

但并不是所有数据空间大小都能在编译过程中确定！

动态存储分配

在目标程序运行阶段由目标程序实现对存储空间的组织与管理，和为源程序中的变量分配存储的方法。

特点：在目标程序运行时进行分配；编译时要生成进行动态分配的目标指令。

9.2 静态存储分配

（1）分配策略

由于每个变量所需空间的大小在编译时已知，因此可以用简单的方法给变量分配目标地址。

具体步骤：

• 开辟一数据区。(首地址在加载时确定)
• 按编译顺序给每个模块分配存储。
• 在模块内部按顺序给模块的变量分配存储，一般用相对地址，所占数据区的大小由变量类型确定。
• 目标地址填入变量的符号表中。

这种分配策略要求语言不允许指针或动态分配，不允许递归调用过程（如果递归调用，就相当于又多加了一个函数，又需要分配存储空间了）。典型的例子是Fortran77

（2）模块（fortran子程序）的完整数据区

子程序需要在数据区中保留返回地址，形参也要分配存储以存放相应的实参信息。编译时还要分配临时变量空间（用于存放表达式计算的中间结果等）

FORTRAN子程序的典型数据区：

9.3 动态存储分配

由于编译时还不能具体确定某些数据空间的大小，故对它们分配存储空间必须在程序运行时进行。这时，编译程序生成有关存储分配的目标代码，实际上的分配要在目标程序运行时进行。这种分配方式称为动态存储分配。

对于分程序结构，而且允许递归调用的语言，常使用栈式动态存储分配，即使用一个类似于堆栈的“运行栈”来实现数据区的分配。

分配策略

整个数据区为一个堆栈

1. 当进入一个过程时，在栈顶为其分配一个数据区。
2. 当退出一个过程时，撤消该过程的数据区。

9.3.1 活动记录

一个典型的活动记录可以分为三部分：

（1）局部数据区：存放模块中定义的各个局部变量

（2）参数区：存放隐式参数（不出现在用户源程序中）和显式参数（出现在用户源程序中）。

形参数据区:每一形参都要分配数据空间，形参单元中存放实参值或者实参地址。

prev abp:存放调用模块记录基地址。该函数执行完时，释放其数据区，数据区指针指向调用前的位置。

ret addr:返回地址，即调用语句的下一条执行指令地址。

ret value :函数返回值(无值则空)，比如void函数，就是空的。

（3）display区：存放各外层模块活动记录的基地址。

变量二元地址（BL、ON）

BL：变量声明所在的层次，可以用它找到该层数据区开始地址。此为嵌套层次，并列过程具有相同的层次。

ON：相对于显式参数区开始位置的位移（相对地址）。

例如：

程序模块1:

x（1,0） x在第一层中被声明，在显式参数区开始的位置是0；

y（1，1） NAME（1，2）

过程块M1:

IND（2，0） x（2，1）

注意⚠️：高层(内层)模块可以引用低层(外层) 模块中的变量，例如在M1中可引用外层模块中定义的变量 Y。 在 M1 中引用Y时，可通过其 display 区找到程序块 1 的活动记录基地址，加上 Y 在该数据区的相对地址就可以求得 y 的绝对地址，具体如何引用将在后面提到。

以下是运行栈的跟踪情况：

因此可以画出完整的运行栈图：

(e)当模块4执行完，则abp:=prev abp，这样abp恢复到进入模块4时情况，运行栈情况如(c)。

(f)当M2执行完，则abp:=prev abp，这样abp恢复到进入模块M2时情况，运行栈情况如(b)。

(g)当M1执行完，则abp:=prev abp，这样abp恢复到进入模块M1时情况，运行栈情况如(a)。

(h)当最外层模块执行完，运行栈恢复到进入模块时的情况，运行栈空。

9.3.2 建造display区的规则

从i层模块进入（调用）j层模块：

（1）若j=i+1

复制i层的display，然后增加一个指向i层模块记录基地址的指针

（第j层模块的display）

（2）若j<=i ,即调用外层模块或同层模块

将i层模块的display区中的前面第j-1个复制到第j层模块的display区

若发生了j>=i+2的情况，例如图中，i想要调用模块k

在这种情况是不行的，因为k的生命周期在j里面。当j执行完后到CALL k后，j（k的外层）生命周期已完结，不能直接调用k。

如果举一个特例的话，如果k中要调用j的变量，如果i直接调用k，那么k将会找不到来自外层的j的变量。

9.3.3 运行时的地址计算

假设要访问的变量的二元地址为:(BL，ON) ，要在LEV层模块中引用BL层模块定义的变量。

如：

在abp（3）引用IND（2，0），会将abp设为display（2），即abp（2），加上display区大小BL-1=1，再加上隐式参数区大小nip=2，与偏移量0，即使IND的地址。

10. 代码优化和目标代码生成

10.1 代码优化概念

1) 基本概念

「优化」

• 对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
  • 等价：不改变程序的运行结果
  • 有效：目标代码运行时间短，占用存储空间小

「遵循的原则」

• 等价原则：优化不应改变程序运行的结果
• 有效原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小
• 合算原则：应尽可能以较低的代码取得较好的优化效果

「优化的级别」

• 局部优化、循环优化、全局优化

2) 优化的种类

「总体列举」

• 删除多余运算（删除公用子表达式）
• 合并已知量
• 复写传播
• 删除无用赋值
• 代码外提
• 强度消弱
• 变换循环控制条件

原代码

void quicksort(m, n);
int m, n;
{
    int i, j, v, x;
    if(n <= m) return;
    i = m-1, j = n, v = a[n];
    while(1) {
        do i = i+1; while(a[i] < v);
        do j = j-1; while(a[j] > v);
        if(i >= j) break;
        x = a[i], a[i] = a[j], a[j] = x;
    }
    x = a[i], a[i] = a[n], a[n] = x;
    quicksort(m, j); quicksort(i+1, n);
}
123456789101112131415

删除公共子表达式

T1 = 4*i
T2 = 4*i

T1 = 4*i
T2 = T1
12345

复写传播

T4 = T2
T3 = T4 + 1

T4 = T2
T3 = T2 + 1
12345

删除无用赋值

T4 = T2 // T4 无用
T3 = T2 + 1

T3 = T2 + 1
1234

强度削弱

i = i + 1
T2 = 4 * i

i = i + 1
T2 = T2 + 4
12345

删除归纳变量

• 如下例所示，i、j 可以被 T2、T4 取代，因此删除 i、j

3) 数据流方程

入口活跃变量 = 出口活跃变量 - 被定义的变量 + 被引用的变量

10.2 代码优化技术

10.2.1 局部优化

「局部优化」

• 局限于基本块范围内的优化

1) 基本块

概述

「基本块」

• 程序中一顺序执行语句序列，只有一个入口和一个出口。
• 入口就是第一个语句，出口就是最后一个语句。

「定值 & 引用」

• 对三地址语句为 x := y + z，称 x 定值并引用 y 和 z

「活跃的」

• 基本块中的一个名字在程序中的某个给定点是活跃的，指如果在程序中（本基本块 + 其它基本块）它的值在该点以后被引用

划分基本块

一、找出中间语句程序中各个基本块的入口语句（三地址语句）

• 程序第一个语句
• 能由条件转移语句或无条件转移语句转移到的语句
• 紧跟在条件转移语句后面的语句

二、对以上求出的每个入口语句，确定其所属的基本块

• 入口语句 => 下一入口语句的前一天语句
• 入口语句 => 转移语句
• 入口语句 => 停语句

三、凡未被纳入某一基本块中的语句，可以从程序中删除

基本块划分举例

2) 流图

• 基本块为结点，程序第一条语句所在基本块是首结点
• 连边
  • B2 紧接着 B1 之后执行，且 B1 最后一条语句不是无条件转移语句，则 B1 => B2
  • B1 最后一条语句是（无）条件转移语句，转移到 B2 的第一条语句，则 B1 => B2

3) 基本块的 DAG 表示

DAG 扩充

• 在 DAG 上增加标记和附加信息
  • **「叶结点」**以标识符或常数作为标记，表示该结点代表该变量或常数的值
  • **「内部结点」**以运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果
  • **「附加」**各个结点可能附加一个或多个标识符表示这些变量具有该结点所代表的值

四元式的 DAG 表示

「0型：A := B」(:=, B, -, A)

「0型：goto (s)」(j, -, -, (s))

「1型：A := op B」(op, B, -, A)

「2型：A := B op C」(op, B, C, A)

「2型：A := B[C]」(=[], B, C, A)

「2型：if B rop C goto (s)」(jrop, B, C, (s))

「3型：D[C] := B」([]=, B, D, C)

4) 基本块的优化算法

优化算法概述

• 一个基本块，可用一个 DAG 来表示
• 对基本块中每一条四元式代码，依次构造对应的 DAG 图，最后基本块中所有四元式构造出来的 DAG 连成整个基本块的 DAG
• 具体流程
  • 准备操作数的结点
  • 合并已知量
  • 删除公共子表达式
  • 删除无用赋值

示例

「示例」

「优化结果」

构造基本块的 DAG 算法

参考上述示例，引入下述的具体过程。

• 引入函数 Node，保存和计算 DAG 中标识符与结点的对应关系
• 对基本块中每一四元式，依次执行以下步骤
  1. 准备操作数的结点
  2. 合并已知量
  3. 删除公共子表达式
  4. 删除无用赋值

「1. 准备操作数的结点」

• 如果 Node(B) 无定义，则构造一标记为 B 的叶结点并定义 Node(B) 为这个结点
  • 如果四元式为 0 型（A := B），则记 Node(B) = n，转 4
  • 如果四元式为 1 型（A := op B），转 2(1)
  • 如果四元式为 2 型（A := B op C）
    • 如果 Node© 无定义，则构造一标记为 C 的叶结点并定义 Node© 为这个结点
    • 转 2(2)

「2. 合并已知量」

• 如果 Node(B) 是标记为常数的叶结点，转 2(3)，否则转 3(1)
• 如果 Node(B) 和 Node© 都是标记为常数的叶结点，则转 2(4)，否则转 3(2)
• 执行 op B（合并已知量），令得到的新常数为 P
  • 如果 Node(B) 是处理当前四元式时新构造出来的结点，则删除它
  • 如果 Node§ 无定义，则构造一用 P 作标识符的叶结点 n，置 Node§ = n
  • 转 4
• 执行 B op C（合并已知量），令得到的新常数为 P
  • 如果 Node(B) 或 Node© 是处理当前四元式时新构造出来的结点，则删除它
  • 如果 Node§ 无定义，则构造一用 P 作标记的叶结点 n，置 Node§ = n
  • 转 4

「3. 删除公共子表达式」

• 检查 DAG 中是否已有一结点，其唯一后继为 Node(B)，且标记为 op，即公共子表达式
  • 如果没有，则构造该结点 n
  • 否则，把已有的结点作为它的结点并设该结点为 n，转 4
• 检查 DAG 中是否已有一结点，其左后继为 Node(B)，右后继为 Node©，且标记为 op，即公共子表达式
  • 如果没有，则构造该结点 n
  • 否则，把已有的结点作为它的结点并设该结点为 n，转 4

「4. 删除无用赋值」

• 如果 Node(A) 无定义，则把 A 附加在结点 n 上并令 Node(A) = n
• 否则，先把 A 从 Node(A) 结点上的附加标识符集中删除
  • 如果 Node(A) 为叶结点，则其 A 标记不删除
  • 把 A 附加到新结点 n 上并置 Node(A) = n，转处理下一四元式

「信息总结」

• 在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标记符
• 在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是 DAG 各结点上的那些标记或者附加标识符

10.2.2 循环优化

循环优化，主要有三大措施：

1. 代码外提
2. 强度消弱
3. 删除归纳变量（变换循环控制条件）

1) 循环不变运算

• 具体定义
• 寻找算法
  • 反复遍历

2) 代码外提

• 找到不变运算
• 检查是否符合代码外提条件
• 保持次序前提下提出代码
• 举例

3) 强度消弱

• 核心思想
  • 将程序中执行时间较长的运算转换为执行时间较短的运算
  • 例如将乘法换成加法
• 举例
• 适用范围
  • 强度消弱通常是针对循环控制变量有先行关系的变量赋值进行
  • 经过强度消弱后，循环中可能出现一些新的无用赋值
  • 对于消弱下标变量地址计算的强度非常有效

4) 删除归纳变量

归纳变量

• 基本归纳变量、归纳变量的定义

具体算法

• 具体算法
• 举例

10.3 目标代码生成概念

1) 任务

将分析、翻译、优化后的中间代码变换成目标代码

2) 输入

• 源程序的中间表示，以及符号表中的信息
• 类型检查均已完成

3) 输出

• 绝对指令代码：能够立即执行的机器语言代码，所有地址已经定位
• 可重新定位指令代码：机器语言模块，需要与运行程序链接才能执行
• 汇编指令代码：需要汇编程序转换成可执行机器语言代码

10.4 目标代码生成概念

10.4.1 抽象计算机模型

其中 (M) 表示主存中 M 位置的数据。

其它指令

10.4.2 代码生成

1) 代码生成原则

• 以基本块为单位生成目标代码
  • 依次把四元式的中间代码变换成目标代码
  • 在基本块的范围内考虑如何充分利用寄存器
  • 进入基本块时，所有寄存器空闲
  • 离开基本块时，把存在寄存器中的现行的值存回主存中，释放所有寄存器
  • 不特别说明，所有说明变量在基本块出口之后均为非活跃变量
• 在一个基本块的范围内考虑充分利用寄存器
  • 

2) 待用信息和活跃信息

概念解释

活跃信息 - 将来会不会被引用

待用信息 - 将来在什么地方会被引用

符号表示

• 二元组 (x, x) 表示变量的待用信息和活跃信息
  • 第 1 元: i 表示将会在第 i 行被引用、^表示非待用
  • 第 2 元: y 表示活跃，^表示非活跃
• 信息变化
  • (x, x) -> (x, x)，用后者更新前者
• 计算方法
  • 

3) 变量地址、寄存器描述

目的

推出 AVALUE、RVALUE 目的：

• 四元式指令：指令中各变量在将来会被使用的情况
• 变量：每个变量现行值的存放位置
• 寄存器：每个寄存器当前的使用情况

概念

• AVALUE（变量地址描述数组）
  • 动态记录各变量现行值的存放位置
  • AVALUE[A] = {R1, R2, A}
• RVALUE（寄存器描述数组）
  • 动态记录各寄存器的使用信息
  • RVALUE[R] = {A, B}

注意，对于四元式 A:=B

• 如果 B 的现行值在某寄存器 R i R_iR**i 中，则无须生成目标代码
• 只须在 RVALUE(R i R_iR**i) 中增加一个A，并把 AVALUE(A) 改为 R i R_iR**i

4) 代码生成算法

算法描述

• 总体流程
• 寄存器分配算法

算法举例

• 为基本块生成代码示例

10.4.3 DAG的目标代码

作用：重排中间代码，减少目标代码

算法：

1. 构建 DAG，结点标记写在结点圆圈中，叶结点未编号，内部结点的编号写在各结点下面
2. 倒序填写中间代码编号，找到无父节点的结点，向左进行递归拓扑，遇到子结点或无法拓扑则停止

举例：

• 中间代码

T1 := A+B
T2 := A-B
F := T1*T2
T1 := A-B
T2 := A-C
T3 := B-C
T1 := T1*T2
G := T1*T3
12345678

• DAG图
• 节点重排