Compiler

一、引论

编译原理是良好的数学基础和好的工程结构功能的结合。

Compiler：编译，述而不作，忠于编写的东西

编译器从逻辑上可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示

1.1什么叫编译程序

翻译器（翻译程序）：Translater

能将一种语言程序（源语言程序）转换成另一种等价的语言程序（目标语言程序）

编译器（编译程序）：Compiler

能将一种计算机高级语言程序（源语言程序）转换成另一种等价的计算机低级语言程序（目标语言程序）

解释器（解释程序）：Interpreter

也是一种翻译程序，以一种语言写的源程序作为输入，但不产生目标代码，而是边解释边执行

解释器和编译器的区别：

①编译分成两步完成：先翻译，在运行

②解释只用一步就完成：边解释边执行

可变目标编译程序（Retargetable Compiler）

交叉编译程序（Cross Compiler）

1.2编译程序的组成

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

语法分析器：使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构。一个常用的表示方法便是语法树，树中的每个内部节点表示一个运算

语义分析器：使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中键代码生成过程中使用。

中间代码生成器：在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示。这些中间表示可以有多种形式。比如语法树是一种中间表示形式，通常在语法分析和语义分析中使用。

代码优化器：机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码

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

符号表管理器：记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息。

Tips:

如何学习构造编译程序

（1）源语言，对被编译的源程序深刻理解其结构和含义

（2）目标语言，假定目标语言是机器语言，就必须搞清楚硬件的系统结构和操作系统的功能

（3）编译方法，把一种语言翻译成另一种语言的方法很多，重点

二、高级语言及其语法描述

2.1程序语言的语法和语义

2.1.1语法

任何语言均可作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。

对于自然语言来说，他们是定义在某个字母表上的句子的集合

对于程序语言来说，他们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。

词法规则：单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。

语法规则：上下文无关文法或BNF（Backus-Naur范式）

2.1.2语义

语义，定义程序的意义

没有公认的形式系统描述语义

2.2程序语言的一般特征

高级语言的分类

• 强制性语言（Imperative Language）|过程式语言：Fortran，C，Pascal
• 应用式语言（Applicative Language）|函数式语言：LISP
• 基于规则的语言（Ruled-based Language）：Prolog
• 面向对象语言（Object-oriented Language）：JAVA，c++

2.3程序语言的语法描述

一、字母表和符号串

字母表：符号的非空有限集合 例：∑ ={a，b，c}

符号：字母表中的元素 例： a，b，c

符号串：符号的有穷序列 例：a, aa, ac, abc，..

空符号串：无任何符号的符号串( ε )

符号串集合：由符号串构成的集合。

符号串的形式定义

有字母表∑，定义：

（1）ε是∑上的符号串；

（2）若x是∑上的符号串，且a∈ ∑，则ax或xa是 ∑ 上的符号串；

（3）y是∑上的符号串，iff（当且仅当）y可由（1）和（2）产生。

二、符号串和符号串集合的运算

符号串相等：若x、y是集合上的两个符号串，则x＝y，iff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。

符号串的长度：若x为符号串，其长度|x|等于组成该符 号串的符号个数。（例：x＝STV， |x|=3）

符号串的连接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的连接 xy ＝ XYYX 也是Σ上的符号串。（注意：一般xy ≠ yx，但是εx = xε）

符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{ xy | x∈A, y∈B}

符号串集合的幂运算：有符号串集合A，定义A⁰ ={ε}, A¹=A, A²=AA, A³=AAA,…… ……, Aⁿ＝A^n-1A=AA^n-1 ，n>0

符号串集合的闭包运算：设A是符号串集合，定义 A^＋＝ A¹ ∪ A² ∪ A³ ∪……∪ Aⁿ ∪…… 称为集合A的正则闭包。A*＝ A⁰ ∪A^＋ 称为集合A的闭包。（A⁰ = { ε } ）

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？

若A为某语言的基本字符集

​ A＝{a,b,……z,0,1,……,9, +,－,×,_/, ( , ), =……}

B为单词集

​ B ={begin, end, if, then,else,for,……,<标识符>,<常量>,……}

则B ⊂ A* 。

语言的句子是定义在B上的符号串。

若令C为句子集合，则C ⊂ B^* , 程序 ⊂ C

三、文法的直观理解

1.什么是文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。

2.语法规则：我们通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由……组成“。

例如：

<句子>::=<主语><谓语>

<主语>::=<代词>|<名词>

<代词> ::=你|我|他

<名词>::= 王民|大学生|工人|英语

<谓语>::=<动词><直接宾语>

<动词>::=是|学习

<直接宾语>::=<代词>|<名词>

3.由产生式推导句子：3.有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。

​ 推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。

<句子> => <主语><谓语>

<主语><谓语> => <代词><谓语>

…… ……

这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。

说明：有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。

文法实在形式上对句子结构的定义与描述，而未涉及语义问题

4.语法树

一般用语法树来描述一个句子的语法结构。

四、文法和语言的形式定义

1.文法的定义

定义1: 文法 G =（V_N，V_T，P，Z）

​ V_N ： 非终结符号集 ​ V_T ： 终结符号集 ​ P： 产生式或规则的集合 ​ Z： 开始符号（识别符号） Z∈VN

• 产生式：产生式是一个有序对(U, x), 通常写为:

​ U ::= x 或U ➡ x； |U| = 1 |x| >= 0

• 非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为V_N

• 终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为V_T

无符号整数的文法:
G[<无符号整数>]=（VN，VT，P，Z）
	VN＝{<无符号整数>, <数字串>, <数字>}
	VT  = {0,1,2,3,4,5,6,7,8,9}
	P = {<无符号整数> → <数字串> ;
        <数字串> → <数字串> <数字> ;
        <数字串> → <数字> ;
    	<数字> →0;    <数字> →2; 	<数字> →3;	<数字> →4;	
    	<数字> →5;    <数字> →6;	<数字> →7;	<数字> →8;    <数字> →9; }
	Z = <无符号整数>;

注：产生式左边符合构成集合V_N，且Z ∈ V_N

​ 有些产生式有相同的左部，可以合在一起

​ 给定一个文法，实际上只需给出产生式的集合，并指定识别符号（开始符号）

2.推导与归约

**定义2：**直接推导：

有文法G：v = xUy，w = xuy，其中x、y∈V*，U∈V_N，u∈V*，

若U ::= u∈P，则v ⇒ w，

若 x = y = ε ， 有 U ::= u， 则U ⇒ u

x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为x⇒y。

定义3： +推导：x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为x =⁺=⇒y。

即，若有直接推导序列：x=U0==>U1==>U2==>……==>Un=y,则 x=⁺=>y 。

定义4：*推导：x和y是符号串，若使用0次或若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为x=^*=>y。

如：N=^*=>N， N=^*=>109

**定义5：**最右推导&最左推导

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

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

！！！规范推导＝最右推导

**定义6：**推导的逆过程为归约

x==>y，可称为x直接推导出y，也可称为y直接归约出x

3.语言的形式定义

**定义7：**文法G[Z]

​ （1）句型：x是句型 ⇔ Z =^*=>x,且 x∈V^*；

​ （2）句子：x是句子 ⇔ Z =⁺=> x, 且 x∈V_T^*；

​ （3）语言：L（G[Z]）={x| Z=⁺=>x， x∈V_T^* }；（文法G[z]产生的所有句子的集合）

定义8：G和G'是两个不同的文法，若L(G) = L(G')，则G和G'为等价文法

编译感兴趣的问题如下

给定终极符x，文法G，求x ∈ L(G)？

4.文法分类

• 形式语言：用文法和自动机所描述的没有语义的语言

语言定义： L(G[Z]) = { x | Z=⁺=>x，x∈V_T^* }

文法定义：乔姆斯基将所有文法定义为一个四元组：G = （V_N，V_T，P，Z）

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

文法和语言的分类：0型、1型、2型、3型

定义9： 0型文法

P： u → v ，其中 u ∈ V⁺，v ∈ V^*

0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。

0型语言：L0，这种语言可以用**图灵机（Turing）**接受

**定义10：**1型文法

P： xUy → xuy ，其中 U ∈V_N，x、y、u ∈ V^*

1型文法称为上下文有关或上下文敏感。即只有在x、y这样的上下文中才能将U改写为u

1型语言：L1，这种语言可以有一种线性界限自动机接受

**定义11：**2型文法

P： U → u ，其中 U ∈ V_N ，u ∈ V^*

2型文法称为上下文无关文法。即把U改写为u时，不必考虑上下文。

注意：2型文法与BNF表示相等价。

2型语言：L2，这种语言可以由下推自动机接受

**定义12：**3型文法

（左线型） P： U → T | U → wT ，其中 U、w ∈ V_N ，T ∈ V_T

（右线性）P： U → T | U → Tw ，其中 U、w ∈ V_N ，T ∈ V_T

3型文法称为正则文法。它是对2型文法进行进一步的限制

3型语言：L3，又称正则语言、正则集合，这种语言可以由有穷自动机接受

由上易知， L0 ⊃ L1 ⊃ L2 ⊃ L3

0型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1

5.语法树与二义性文法

1.推导与语法树

语法树：句子结构的图示表示法，通常表示称一棵倒立的树，即

结点： 符号

根节点： 识别符号

中间节点：非终结符

叶节点： 终结符或非终结符

边：表示节点间的派生关系

句型的推导及语法树的生成（自顶向下）

给定G[Z]，句型w：可建立推导序列，Z =^*=> w；可建立语法树，以Z为树根节点，每步推导生成语法树的一枝，最终可生成句型的语法树。

语法树的生成规律不同，但最终生成的语法树形状完全相同

一般推导

graph TB
   A[<无符号整数>] --> B[<数字串>]
   B --> C[<数字串>]
   B --> D[<数字>]
   C --> E[<数字>]
   E --> F[1]
   D --> G[0]

树与推导：句型推导过程 ⇔ 句型语法树的生长过程

①由推导构造语法树

从识别符号开始，自左向右建立推导序列 ⇒ 由根节点开始，自上而下建立语法树

②由语法树构造推导

自叶而根修剪子树的末端节点，直至把整棵树剪掉（留根），每剪一次对应一次归约 ⇒ 从句型开始，自右向左地逐步进行归约，建立推导序列

2.文法的二义性

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

换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同

比如二义性文法: G[E]:	E := E+E | E*E | (E) | i
					Vn = {E}
					VT = {+,*,(,),i}

针对 i+i*i 有两种不同的语法树

定义：若一个文法的某句子存在两个不同的规范推导（最右推导），则该文法是二义性的，否则是无二义性的

若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性

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

由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。

句柄：句型的句柄是和某产生式右部匹配的子串。句柄是直接短语，即某产生式的右部，具有最左性

若句柄不存在重复，就说明文法无二义性

如 S → ABC ，ABC为该句子的句柄

三、词法分析

• 词法分析 （Lexical Analysis）

实现词法分析器的程序称为词法分析程序（扫描器）

词法分析程序的主要任务：对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式——属性字（TOKEN）。

词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。

graph LR
	A[源程序] --> B[词法分析程序]
	B -- Token --> C[语法分析程序]
	C -- get token --> B
	

为什么将词法分析工作从语法分析工作中独立出来？

• 简化设计

• 改进编译效率

• 增加编译系统的可移植性

3.1 词法分析器的要求

• 功能：输入源程序，输出单词符号

单词符号是一个程序语言的基本语法符号

• 单词的分类：

1.**关键字：**由程序语言定义的具有固定意义的标识符。也称为保留字或基本字

2.**标识符：**用来表示程序中各种名字的字符串。

3.**常 数：**常数的类型一般有整型、实型、布尔型、文字型。

4.**运算符：**如+、－ 、*、/ 等。

5.**界限符：**如逗号、分号、括号等。

一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。

词法分析器所输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）

单词种别一般将①标识符归为一种，②常数按类型分种（整数实数布尔），③关键字全体视为一种，或者一个一种，④运算符可采用一符一种，⑤界符一般也用一符一种。

如果一个种别只含一个单词符号，那么对于这个单词符号，种别编码可完全代表其自身。若一个种别有多个单词符号，那么，对于每个单词符号，除了给出种别编码外，还应给出有关的单词符号的属性信息。

单词符号的属性是指单词符号的特性或特征。属性值是反应特性或特征的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

while(i>=j)i++;//以该语句为示例
//该句的单词符号序列如下:
<while, ->
<(, ->
<id, point(i)>//存放指向i的指针
<>=, ->
<id, point(j)>//存放指向j的指针
<), ->
<id, point(i)>
<--, ->
<;, ->

3.2 词法分析器的设计

Ⅰ、输入、预处理

词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。

预处理的主要工作

• 某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉
• 注解部分——仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉
• 空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。

Ⅱ、单词符号的识别：超前搜索

上图为词法分析器结构，当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，分析器就从此缓冲区种逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。

超前搜索的原因

• 在程序中有一些单词的识别经常需要多读入一些字符才能知道哪些字符组成一个单词

Ⅲ、状态转换图

状态转换图是一张有限方向图，是设计词法分析器的有效工具。

graph LR
	0--字母-->1
	1--字母或数字-->1
	1--其他-->2[*]
	

一个状态转换图可用于识别（或接受）一定的字符串

3.3 正规表达式与有限自动机

1.正规式与正规集

正规式也称正则表达式（regular expression），是说明单词的模式（pattern）的一种重要的表示法，是定义正规集的数学工具

正规式及其所表示的正规集的定义：

设字母表为∑，辅助字母表∑‘ = { φ，ε， |，•，*，（，）}，

① ε 和 φ 都是 ∑ 上的正规式，他们所表示的正规集分别为 { ε }和 { } ；

② 对任何 a ∈ ∑ ，a 是 ∑ 上的一个正规式，他所表示的正规集为 { a } ；

③ 假定 e₁ 和 e₂ 都是 ∑ 上的正规式他们所表示的正规集分别为 L(e₁) 和 L(e₂)，那么，( e₁ ) ， e₁ | e₂ ， e₁ • e₂ ， e₁^* 也都是正规式，他们所表示的正规集分别为 L( e₁ )， L( e₁ ) ∪ L( e₂ )， L( e₁ ) L( e₂ ) 和 ( L( e₁ ) )^* ；

④仅由有限次使用上述三步骤而定义的表达式才是 ∑ 上的正规式，仅有这些正规式所表示的集合才是 ∑ 上的正规集。

• 注意，| 、 • 、* 、均为正规式的运算符

| 表示或

• 表示连接

* 表示闭包，即任意有限次的自重复连接

在不混淆的情况下，括号可以省去，但规定算符的优先顺序为 *， • ，|。连接符 • 一般可省略不写，三个算符均为左结合的。

例:
a						{a}
a|b			 			{a,b}
ab						{ab}
(a|b)(a|b)	            {aa,ab,ba,bb}
a*	            		{ε,a,a,……,任意个a的串}
(a|b)*					{ε,a,b,aa,ab,bb,……,所有由a和b组成的串}

• 结论：程序设计语言的单词都能用正规式来定义

正规式的等价性：若两个正规式 e₁ 和 e₂ 所表示的正规集相同，则说 e₁ 和 e₂ 等价，写作 e₁ = e₂ 。

例:
e1 = (a|b) , e2 = (b|a) ,e1 == e2
e1 = b(ab)* , e2 = (ba)*b , e1 == e2

正规式服从的规律有：

• 或服从交换律：U|V = V|U
• 或的可结合律：U|(V|W) = (U|V)|W
• 连接的可结合律：(UV)W = U(VW)
• 分配律：U(V|W) = UV | UW，(V|W)U = VU | WU
• ε是连接的恒等律：εU = U，Uε = U
• 素零一律：U|U = U
• 或的抽取律： U* = ε|U|UU|...

2.确定有限自动机

确定有限自动机（有穷自动机）作为一种识别装置，能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具

有穷自动机分两类：确定的有限自动机（deterministic Finite Automata）和不确定的有限自动机（Nondeterministic Finite Automata）

graph LR
	RE(RE)
	RE --> NFA(NFA)
	NFA --> DFA(DFA)
	DFA --> minDFA(minDFA)

DFA

DFA定义：一个确定的有穷自动机（DFA）M是一个五元组： M = （ S ，∑ ，δ ，s₀ ，F ）

其中：

• S 是一个有穷集，他的每个元素称为一个状态；
• Σ 是一个有穷字母表，他的每个元素称为一个输入符号，所以也称 Σ 为输入符号表
• δ 是转换函数，实在 S × Σ → S 上的单值部分映射，即，如果 δ（s，a）= s‘ ， (s ∈ S，s' ∈ S ) 就意味着，当前状态为s，输入符为a时，将转换至下一个状态s’，s'称作s的一个后继状态
• s₀ ∈ S 是唯一的一个初态
• F ⊂ S 是一个终态集（可空），终态也称可接受状态或结束状态

DFA可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，即s行a列的矩阵元素表示 δ（s，a）的值。这个矩阵称为状态转换矩阵。

一个DFA也可以表示为一张确定的状态转换图

假定DFA M含有 m个状态和 n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用Σ中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。

一般来说，初态节点旁边标以 ⇒ ；终态节点用双圈表示。

例如：

如上表，可表示(a|b)*，也可画成如下图

DFA的确定性

1.映射δ ： S × Σ → S 是一个单值函数。也就是说，对任何状态s∈S和输入符号 a ∈ Σ ，f（s，a）唯一地确定了下一状态。从转换图的角度来看，假定字母表 Σ 含有n个输入字符，那么，任何一个状态结最多只有n条弧射出，而且每条弧以一个不同的输入字符标记。

NFA

NFA的定义：一个非确定的有穷自动机（NFA）M是一个五元组：M = （ S ，∑ ，δ ，S₀ ，F ）

其中：

• S 是一个有穷集，他的每个元素称为一个状态；
• Σ 是一个有穷字母表，他的每个元素称为一个输入符号，所以也称 Σ 为输入符号表
• δ 是转换函数，实在 S × Σ^* → S 上的单值部分映射，即， δ： S × Σ^* → 2^S 表明在某状态下对于某输入符号可能有多个后继状态
• S₀ ⊂ S 是一个非空初态集
• F ⊂ S 是一个终态集（可空），终态也称可接受状态或结束状态

如图，为一个NFA

∑^* 上的符号串 t 被 NFA M 接受也可以这样理解：

对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为ε，那么空字可为M所接受。

NFA M所能接受的符号串的全体记为L(M)

结论： Σ 上一个符号串集 V ⊂ Σ^* 是正规的，当且仅当存在一个 Σ 上的不确定的有穷自动机M，是的 V = L(M)

NFA构造方法:

Σ上的字母a是正规式,构造等价的NFA为
	一个初态,一个终态,中间标记ε弧

正规式A和B连接是正规式,构造等价NFA为
	初态是A的初态,终态是B的终态,从A的终态到B的初态标记为ε弧

A|B是正规式,构造等价的NFA为
	构造新的初态和终态,从初态引ε到A和B的初态,从到A到B的终态引ε到终态

A*是正规式,构造的等价NFA为
	构造新的初态和终态，从初态引ε到终态和A的初态,从A的终态引ε到终态和A的初态

NFA和DFA的等价性

• DFA是NFA的特例

对于每个NFA M，存在一个DFA M’ ，使得L( M ) =L( M’ )。对每个NFA M存在着与之等价的DFA M’。即：对于任何两个有穷自动机M和M’，如果L( M )=L( M’ )，则称M与M’是等价的。

有一种算法，将NFA转换成接受同样语言的DFA。这种算法称为子集法。

与某一NFA等价的DFA不唯一

从NFA的矩阵表示中，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：

• DFA的每一个状态对应NFA的一组状态。

DFA使用他的状态去记录在NFA读入的一个输入符号后可能达到的所有状态。

NFA确定化算法（ NFA → DFA 的转换）

假设NFA N = （ K， Σ ， f ，K₀，K_t ）按如下办法构造一个DFA M=（ S， å，δ，S₀ ，S_t），使得L(M) = L(N) ：

1. M的状态集 S 由 K 的一些子集组成。用 [ S₁ ，S₂ ，…，S_j ] 表示 S 的元素，其中 S₁ ，S₂ ，…，S_j 是K的状态。并约定， 状态 S₁ ，S₂ ，…，S_j 是按某种规则排列的，即对于子集{S₁ ，S₂ } = {S₂ ，S₁ }来说，S的状态就是 [S₁ ，S₂ ]

2. M和N的输入字母表是相同的，即 Σ

3. 转换函数是这样定义的： δ（ [ S₁ ，S₂ ，…，S_j ] ，a ） = [ R₁ ，R₂ ，…，R_t ] ，其中 { R₁ ，R₂ ，…，R_t } = ε-closure（ move（{S₁ ，S₂ ，…，S_j } ， a） ）

4. S₀ = ε-closure（ K₀ ）为 M 的开始状态

5. S_t = {S_i ，S_k ，…，S_e }， 其中 [ S_i ，S_k ，…，S_e ] ∈ S 且 {S_i ，S_k ，…，S_e } ∩ K_t ≠ φ

• 状态集合 I 的 ε-闭包，表示为ε-closure( I )，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。

  状态集合I的任何状态S都属于ε-closure(I)

• 状态集合 I 的 α 弧转换，定义状态集合 J 表示为 J = move(I,a) ，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。

  I_a = ε-closure( J ) = ε-closure( move( I , a ) )

如之前NFA的例子：

I={1},  ε-closure(I) = {1,2}；
I={5},  ε-closure(I) = {5,6,2}；
move( {1,2} , a ) = {5,3,4}
ε-closure({5,3,4}) = {2,3,4,5,6,7,8}；

构造NFA N的状态K的子集的算法：

​ 假定所构造的子集族为C，即 C = （T₁ ，T₂ ，… ， T_I ），其中 T₁ ，T₂ ，… ， T_I 为状态K的子集。

1.开始，令ε-closure(K0)为C中的唯一成员，并且他是未被标记的

2.while( C中尚未被标记的子集T )do{
	标记T;
	for 每个输入字母a do{
		U := ε-closure( move(T, a) );
		if U 不在 C 中:
			将U作为未标记的子集Ti加在C中;
	}
}

例：

如上图为实例NFA，构造其状态转换表

将其每个状态确定化，即得到如下等价DFA

N

状态转换表如下，将一组状态替换成对应符号。

minDFA

说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。即用一个状态代替所有与其等价的状态。

所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。

• DFA的最小化就是寻求最小状态DFA

**最小状态DFA的含义：**①没有多余状态（死状态）；②没有两个状态时互相等价的（不可区别）。

两个状态s和t可区别：不满足

• 兼容性：同时终态或同时非终态
• 传播性：从s出发读入某个a（a ∈ Σ ）和从t出发读入某个a到达的状态等价

两个状态s和t等价：

• 如果由 s 出发能导出的所有串的集合与 t 出发能导出的所有串的集合相等，我们称状态 s 与状态 t 是等价的。

如上面示例的DFA，C和F是等价的。

C和F同是终态，读入a到达C和F，C和F同是终态，C和F读入a都到达C，读入b都到达E。

同理D和E也是等价的

DFA最小化的算法：分割法（逐步分组试探法）

核心思想：把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。算法假定每个状态射出的弧都是完全的,否则，引入一个新状态，叫死状态，该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己。

设有DFA M = ( s , ∑ , f, s0 , sz ),最小状态DFA M'
1.  因为不难证明，如果si是非终结状态，而sj是终结状态，那么si和sj一定互不等价(根据等价的定义可知，它们导出的符号串集不同)。所以开始可以把K中的终态和非终态分开，分成两个子集，形成一个基本划分：
       P2＝{I1,I2}    (I1∪I2＝K, I1∩I2＝Φ)
2. 若此两个子集还可以进行划分，则作进一步的划分，形成Pm ,假定到某个时候Pm已经含有m个子集，记为：Pm＝{I1,I2,…,Im}，设s'和s"是Ii中的任意两个状态，如果对某个a∈Σ,存在Ij ，使  f(s',a), f(s",a)∈Ij ，则称s'和s"关于a是拟等价的。
    如果存在s'，s"∈Ii，使得对字母表Σ中的某个符号a, s'和s"不为拟等价，则我们说Ii是可分的。
    换句话说，令Ii ＝{s1，s2, …，sn} ，如果对某个a∈Σ，使得Ia i＝{ f(s1,a)，f(s2,a)，…，f(sn,a)}不全落在现行Pm的某一个子集Ij之中；即Ia i这个集合中的元素分别属于I1，I2，…，Im中的几个不同集合，则Ii可分为几个集合（至少可一分为二）。 
3．转2,上述过程务必一再重复，直到P中的每个集合均是不可再分时为止。
此时，P所含的集合数不再增加，即P中的每个集合中的状态互相等价，而不同集合间的状态互不等价。
4.为P中的每一组选一代表，这些代表构成M'的状态。把原来导入非代表状态的弧均导入其代表即可，即若s'是一代表且f(s',a)=t,令r是t组的代表，则M'中有一转换f'(s',a)=r，M'的开始状态是含有S0的那组的代表，M'的终态是含有F的那组的代表。
5.去掉M'中的死状态。 

正规式与有穷自动机的等价性（Re ⇔ NFA）

定理：①对于 Σ 上的NFA M，可以构造一个 Σ 上的正规式R，是的L(R) = L(M)。②对于 Σ 上的任一个正规式R，可以构造一个 Σ 上 的NFA M，是的L(M) = L(R)。

Re ⇒ NFA：

转换方法：我们把状态转换图的概念拓广，令每条弧可用一个正规式标记。
1. 在M的状态图上加进两个结点x、y。从x结点用ε弧 连接到M的所有初态结点，从M的所有终态结点ε弧 连接到y结点。形成一个与M等价的M'， M'只有一个初态和一个终态。
2. 逐步消去M'中的所有结点，直至只剩下x结点和y结点。在消结过程中，逐步用正规式来标记弧，其消结规则如下：
A--R1-->2--R2-->3			==>			1--R1R2-->2
1--R1-->2,1--R2-->2			==>			1--R1|R2-->2
1--R1-->2--R2-->2--R3-->3	==>			1--R1R2*R3-->2
最后x结点和y结点之间的弧上的标记就是所求的正规式R

NFA ⇒ Re

方法如上反转
首先，对正规式R构造如下拓广转换图
然后通过对R进行分裂和加进新结点的办法，逐步把这个图转变为：每条弧标记为中的一个字母或ε ，其转换规则如下:
1--R1R2-->2				==>			A--R1-->2--R2-->3
1--R1|R2-->2			==>			1--R1-->2,1--R2-->2
1--R1R2*R3-->2			==>			1--R1-->2--R2-->2--R3-->3
在整个分裂过程中，所有新结点均采用不同的名字，保留x和y为全图的唯一初态结点和终态结点，至此我们就可以得到一个与R 等价的NFA M

正规文法与有穷自动机的等价性

定理：①对于给定的正规文法G[R]，可以直接构造一个NFA M，使得L（M）=L（G）。②对于 Σ 上的任一个NFA M ，可以直接构造正规文法G[R] ，使得L（ R ）=L（ M ）。

把给定的正规文法G[R]转换为一个Σ上的NFA M构造规则:

设G[R]=（VN，VT，P，R）， NFA M=（ K，Σ，f，S，Z）
1.令 Σ = VT;
2. K = VN，S = R；即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态;
3.增加一个新状态Z，作为NFA M 的终态，Z∈K;
4.对G中的形如A->tB（其中t为终结符或ε；A和B为非终结符）的产生式,构造M的一个转换函数     f（A，t）=B;
5.对G中的形如A->t（其中t为终结符或ε；A和B为非终结符）的产生式,构造M的一个转换函数      f（A，t）=Z;

把给定的å上的NFA M转换为一个正规文法G[R]的构造规则:

设NFA M=（ K，Σ，f，S，Z）,G[R]=（VN，VT，P，R）,
1.令 VT = Σ ;
2.令VN =  K即对M的每一个状态生成G中的非终结符（不妨取相同的名字，G的开始符号是M的初态;
3.令S=R（如果M有多个初态，应先拓广自动机，引入新初态x）;
4.对M 的终态Z增加一个产生式： Z->ε;
5.对M的每一个转换函数f（A，t）=B可写G的一个产生式A->tB（其中t为终结符或ε;A和B为非终结符）;

词法分析程序的自动构造

​ 若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。

四、语法分析

语法分析的主要工作：是识别由词法分析器给出的单词序列是否是给定的正确句子（程序）

语法分析的常用方法：自顶向下的语法分析（Top-Down Parsing）和自底向上的语法分析（Bottom-Up Parsing）两大类

自顶向下语法分析

方法：从文法的开始符号（设为 <程序> ）开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造所给定的源程序串

关键：是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此必须对文法做一些限制，以便在任何情况下都唔那个确定应该用的产生式

主要思想：从开始符号出发，导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。

缺点：若在推导过程中，不对文法进行限制，那么产生式的选择成为无根据的，只好一一去尝试所有可能的产生式，直至成功为止。这种方法致命的地方是不断地回溯，大大影响速度。所以自顶向下分析法分为确定和不确定两种。我们在下面讨论确定的分析方法，这种方法简单直观，便于手工构造或自动生成语法分析器。

在推导过程中，对于产生式相同左部含有非终结符开始的右部时，在推到中选用哪个产生式是不能直接知道的，也就是该语法分析的缺点。

1. 首符集、后继符集、选择集（Fisrt(),Follow(),Select()）

首符集的定义

设G = （ V_N ，V_T ，P ，S）是上下文无关文法，α 是G的任一符号串，则有

First(α) = { a | α^* ⇒ αβ，α ∈ V_T ，α、β ∈ V^* }

特别地，若 α =^*⇒ ε，则规定 ε ∈ First(α)

即：Fisrt(α)集是从α出发推导出所有符号串首终结符或可能的ε构成的集合。

构造算法

1.求Fisrt(X)

对每一文法符号X∈(VN∪VT），求FIRST(X).

(a)若X∈VT,则令FIRST(X)={X};

(b)若X∈VN,且有产生式X→a……,(a∈VT)，则令a∈FIRST(X);

(c) 若X∈VN,有X→ε，则令 ε∈FIRST(X);

(d)若 X∈VN, y1, y2,……,yi都∈VN,且有产生式X→ y1 y2…..yn,      
   当y1, y2,…..yi-1 都 =*=>ε时，（其中1≤i≤n),则FIRST(y1)-ε,
FIRST(y2)-ε,….,FIRST(yi-1 )-ε,FIRST(yi)都包含在FIRST(X)中。

(e)当(d)中所有yi =*=> ε(i= 1,2,….,n),则FIRST(X)=FIRST(y1)∪FIRST(y2)∪….∪FIRST(yn)∪{ε}
反复使用上述（b)～(d) 步直到每个符号的FIRST集合不再增加
为止。

2.求Fisrt(α)

α = x₁x₂……x_n

法1:
1.若n=0,即α=ε,则令FIRST(α)={ε};
2.否则，对1≤i≤n,求FIRST(xi)
3.若n=1,则令 FIRST(α)=FIRST(x1);
4.若n≥2且对一切j=1,2,….,i-1都有ε∈FIRST(xj).
   则令FIRST(xi )-{ε}    FIRST(α),其中2≤i≤n;
   若对一切 j=1,2,…,n都有ε∈FIRST(xj),则令ε∈FIRST(α)

法2:
1.把FIRST(x1)中所有非ε元素加入到FIRST(α)中，即
                  FIRST(α )=FIRST(x1)-{ε };
若FIRST(x1)包含有ε，则把FIRST(x2)的所有非ε元素加入到
        FIRST(α)中，即FIRST(α)=FIRST(α)∪ (FIRST(x2)-{ε});
若FIRST(x1)和FIRST(x2)都包含有 ε，则把FIRST(x3)的所有
        非ε元素加到FIRST(α)中;……
     照此方法继续，一直到考察到xn。
2.若FIRST(xi ),i= 1,2,…,n;即每个FIRST(xi)中都有ε。则将ε加
      到FIRST(α)中。特别地， 若 α=ε ，则FIRST(α)={ε}.

后继符的定义

设G = （ V_N ，V_T ，P ，S）是上下文无关文法，A ∈ V_N 的后继符集合为

Follow(A) = { a | S =^*⇒ μAβ ，a ∈ V_T ， a ∈ First(β) ， μ ∈ V_T^* ，β ∈ V^* }

或 Follow(A) = { a | S =^*⇒ …Aa…，a ∈ V_T }

特别地，若S =^*⇒ …A ， 则# ∈ Follow(A) 。这里的#是代表一个输入串的结束符

表示所有句型中紧挨着A出现的终结符或#均是Follow(A)的元素

构造算法

落#下S
(a)对文法开始符号S,令# ∈ FOLLOW(S).

右部Follow
(b)若B→αAβ是一个产生式,则令FIRST(β)-{ε}
        属于FOLLOW(A);

守门员福利
(c) 若B→αA是一个产生式，或B→αAβ是一个产生式且有ε∈FIRST(β),
	则令FOLLOW(B)是FOLLOW(A)的子集。即把FOLLOW(B)的所有元素加入到FOLLOW(A)中。

(d)反复使用(b)直到每个非终结符的 FOLLOW集合不再增加为止。

选择集的定义

对于给出的上下文无关的文法产生式 A → α ， A ∈ V_N ， α ∈ V^* ，则

Select(A → α) = First(α) ，当 α =*⇒ ε 时

Select(A → α) = Fisrt(α) ∪ Follow(A) ，其他情况

构造算法

(a)求FIRST(α);

(b)若ε∈FIRST(α),则令SELECT(A→α)=FIRST(α)
         否则求FOLLOW(A),并令 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A).

2. LL(1)分析法

当一个文法是LL(1)文法时，则该文法一定能采用确定的自顶向下的分析方法进行分析。

定义：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A → α ，A → β ，满足 Select(A → α) ∩ Select(A → β) = ∅ ，其中，α和β不能同时 =*⇒ ε。

文法的等价变换

确定的自顶向下分析要求给定语言的文法必须是 LL(1)形式，然而，不一定每个语言都是LL(1)文法，对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是我们讨论的主要问题。由LL(1)文法的定义可知若文法中含有左递归或含有左公共因子，则该文法肯定不是LL(1)文法，因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换。

Ⅰ提取左公共因子

对A→ αβ1|  αβ2 | … |  αβn提取左公因子为：
　　　A→ α A'      
　　　A'→  β1 | β2 | … | βn
若在βi , βj , βk…中仍含有左公共因子，可再进行提取，这样反复进行提取直到所引进的新非终结符的有关产生式均无左公共因子为止

结论：一个文法提取了左公共因子后，只解决了相同左部产生式的右部FIRST集不相交问题。当改写后的文法不含有空产生式，且无左递归时，则改写后的文法是LL(1)文法。否则还需用LL(1)文法的判别方法进行判断才能确定是否为LL(1)文法。

Ⅱ消除左递归

一个文法含有下列形式的产生式之一时：

1. A→A β, A∈V_N , β ∈ V*

2. A→B β, B→A α, A,B∈VN, α ,β ∈ V*

则称该文法是左递归的。

含有左递归的文法不能采取自顶向下分析法。

1):把直接左递归改写为右递归

设有文法产生式: A→Aβ|γ.   其中β非空， γ不以A打头。
    可写为:    A → γA'      
    		  A' → βA' | ε
    一般情况下，假定关于A的产生式是：
    	A→A α1| A α2 | … | A αm | β1 | β2 | …| βn            
    	其中，αi(1≤i≤m)均不为空， βj(1≤j≤n)均不以A打头。
	则消除直接左递归后改写为：
		A → β1 A' | β2 A' | … | βn A'
		A'→ α1 A' | α2 A' | … | αm A' | ε


2):间接消除左递归

对于间接左递归的消除需要先将间接左递归变为直接左递归，然后再按1)清除左递归

哪一步有左递归，就把那一步的间接左递归代入产生式产生直接左递归


----------------------------------------------------

3):消除文法中一切左递归的算法

设非终结符按某种规则排序为A1, A2,… An 。
For i:=1 to n  do
   begin
      For j:=1 to i-1 do 
          begin
               若Aj的所有产生式为：
                Aj → δ1 | δ2 | … | δn
               替换形如Ai → Aj γ的产生式为：
                Ai → δ1γ | δ2γ | … | δnγ
          end
       消除Ai中的一切直接左递归
    end

递归下降分析程序构造

在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度

主要思想：对每个非终结符按其产生式结构写出相应的语法分析子程序。因为每个文法递归相应子程序也递归，子程序的结构与产生式结构一致。所以称此种方法称为递归子程序法或递归下降法。

用程序表示递归子程序的内部结构：

	设A是一个非终结符：A→β1 
					A→β2
					 ┊
					A→βn

	则写     ζ(A) <==> if char∈first(β1 )  thenζ(β1 )
                                else if char ∈ first(β2 )  then ζ(β2 )
                                              else…
                                                       if char∈first(βn )
                                                       		then ζ(βn)
                                                                else    ERROR

其中ζ(βi)表示调用处理符号串βi的子程序。


对A的任一右部i 设为：     βi = y1 y2 … yn
则定义ζ( βi) <==> beginζ(y1);ζ(y2);…;ζ(yn) end
其中yj可分为下列两种情况（j=1,…,n):
1)  yj∈VT,则
     ζ( yj) <==> if char≠ yj  then  ERROR  else    READ(char)
2)  yj∈VN,则ζ(yj)表示调用关于yj的递归子程序。


对文法加限制：
1.任一非终结符B都不是左递归的，否则会产生死循环。
2.对A的任意两个右部βi , βj ,有：first(βi) ∩ first(βj) = φ ,
First(βi)表示βi所能导出串的第一个符号的集合。显然，每个βi的first(βi)是互不相同的，否则则无法判断应执行哪个ζ(βi )。

预测分析程序

LL(k)文法是采取确定的自左至右扫描（输入串）和自顶向下分析技术的最大一类文法。

LL系指：自左向右扫描（输入串），自上而下进行最左推导。一般来说，一个文法当其分析器对输入串进行自左至右扫描并采用自顶向下方法进行分析的过程中，如果每步仅利用当前的非终结符（事实上此时它已位于分析栈顶）和至多向前查看k个输入符号就能唯一 决定采取什么动作，那么这个文法称为LL(K)文法。

对于大多数程序设计语言而言。K=1就足够了。因此我们将主要讨论k=1的情形。

LL(1)文法的分析过程

设分析的当前格局为（x1x2 …. xn#, y1y2 …. ym#)

其中xi表示句型的前端部分，诸yj表示输入流的后端部分（终结符串）。则可能有下述动作之一：

1.替代：当x₁∈V_N时，则选相应的候选式去替换x₁ 。

2.匹配：当x₁∈VT时，它与y₁进行匹配，其结果为两种可能，如

果匹配成功，则去掉x₁和y₁（即指针后移一位）否则报错。

3.接受：当格局为(#, #）时，报告分析成功结束。

从实现的角度来说，上述替换过程需要花较多的时间，因为它除了把一个候选式替换掉x1,还需要x2 … xn统统进行移位处理，这时很麻烦的。我们的处理方法是用栈来保存x1x2 … xn,而且是把xn作为栈底， x1作为栈顶，那么上述的替换动作就简单了，只需在栈顶进行替换。即去掉x1把候选式的符号串按逆序方式压入栈中即可。

LL(1)方法的实现

LL(1)方法在实现时用到一个LL(1)分析矩阵和一个分析栈以及预测分析程序。

分析矩阵的元素M[A,a]中的下标A为非终结符，a为终结符或句子结束标记"#"，矩阵元素M[A,a]的内容为一条关于A的产生式。

它表明当用非终结符A向下推导而当前输入符为a时，所应采用的候选式。当矩阵元素为空时，则表示用A往下推导时遇到了不应该出现的符号，即A与a不能匹配。因此应该转向出错处理。

预测分析程序如下图

①判断文法G[E]是否为LL(1)文法，若文法中含有左递归那么要先消除左递归，然后求select集

②构造预测分析表，对每个终结符或'#'号用a表示，则若a∈Select(A→α)。令 M[A,a]=A→α

把所有无定义的M[A,a]标上ERROR

伪代码如下：

其程序维护一个栈Stack用来储存非终结符，一个用于储存源程序的读入字符变量a，一个用于储存栈顶元素XX
其中M[A,a] = {X->x1x2……xk} 为 Select(X->x1x2……xk)={a,……},X为非终结符,a为终结符

#和开始符合入栈
把第一个输入符号读入a
Flag := True
while Flag Do:
	把栈顶元素出栈到X中
	if X ∈ VT then
		if X = a then 把下一个输入符号读入a
		else ERROR
	else if X = '#' then 
		     Flag := False 
		  else ERROR
	else if M[X,a] = {X->x1x2x3……Xxk} then
			把x1x2x3……xk入栈
	else ERROR
END of while
STOP/*分析成功，过程完毕*/
	

自底向上语法分析

原理：自左向右扫描，自下而上分析

从输入符号串入手，通过反复查找当前句型的可归约串，并使用文法的产生式把他归约成相应的非终结符来一步步地进行分析。最终把输入串归约成文法的开始符号，表明分析成功。

• 任何自下而上分析方法的关键就是要找出当前句型的可归约串，然后根据产生式判别将它归约成什么样的非终结符。

规范归约基本概念

G为文法，S为开始符号，假定α，β，δ是G的一个句型，如果 S =*=> αAδ 且 A=+=> β，

则称 β 是句型 α β δ 相对于非终结符A的短语。

如果 A ⇒ β ，则称β是句型 α β δ 相对于A的直接短语。

最左直接短语称为句柄。

从句子到开始符号的归约序列，如果每一步都是把句柄替换为相应产生式的左部符号而得到的，则称为规范归约。规范归约是最右推导（规范推导）的逆过程。

例：：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 并假定输入串为（i+i)*i，考察自下而上的分析过程

栈上的候选式不一定是句柄。例如，在第14步对栈顶为T，它是E的一候选式，但它不是句柄，不能归约成E。判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。

自下而上方法包括四个方法：

• 移进(shift)：把输入流的头符读到分析栈中
• 归约(Reduction)：把分析栈顶的句柄归约为一非终结符
• 接受：分析成功
• 报错：处理错误

算符优先分析

首先规定文法符号之间的优先关系和结合性质，然后再利用这种关系，通过比较两个相邻的符号之间的优先顺序来确定可归约串。

算符文法：任何产生式的右部都不含两个相继的非终结符

优先关系：

终结符ab的三种优先关系：

• a = b：当且仅当存在形如下面的产生式 U → … ab … 或 U → …aQb …
• a < b：当且仅当存在形如下面的产生式 U → …aW… 的产生式，且有 W =+=> b…
• a > b：当且仅当存在形如下面的产生式 U → …Vb… 的产生式，且有 V=+=>…a 或 V =*=>…aQ

如何从文法构造优先关系表

检查文法产生式的每个候选，可找出所有满足 = 的终结符对。

对于每个非终结符 P 构造两个集合 FIRSTVT(P) 和 LASTVT(P)

FisrtVt(P) = { a | P =+=> a… 或 P =+=> Qa… ，a ∈ V_T ，Q ∈ V_N }

LastVt(P) = { a | P =+=> …a 或 P =+=> …aQ ，a∈V_T ，Q ∈ V_N }

检查每个产生式的候选，若形如 …aP… ，则对任意b ∈ FisrtVt(P) ，我们有 a<b

若形如 …Pb… ，则对任何a ∈ LastVt(P)，我们有 a>b

对表达式文法的非终结符构造 FirstVt 和 LastVt 并建立优先关系表

算符优先分析算法

素短语：这样的一个短语，他至少包含一个终结符，不含比自身更小的素短语

最左素短语：句型最左边的素短语

定理：算法优先文法的句型 #N₁a₁N₂a₂……N_na_nN_n+1# 的最左素短语是满足如下条件的最左子串 N_ja_j……N_ia_iN_i+1 ， a_j-1 < a_j ， a_j = a_j+1 = a_i ， a_i > a_i+1

优先函数

LR分析法

• LR(K)分析是指自左向右扫描和自下而上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。

# X1X2 …… Xi …… Xn Xn+1 Xn+2 …… Xn+k Xn+k+1 …… #
		  |-------||----------------|
			 栈顶 	  扫描器的缓冲区 
			 扫到Xn+1,向前查看k个符号,来确定是把Xn+1移进栈,还是把Xi…Xn作为句柄进行归约

1) 要归约时，则根据某产生式 U → XiXi+1……Xn 进行归约: #X1X2 …… Xi-1 U Xn+1Xn+2 …… Xn+k …… #

2)要移进时，即把Xn+1进栈，并读入下一符号: #X1X2 …… Xi …… XnXn+1   Xn+2 …… Xn+k …… #
											|---|	 |---|   |-|
											栈中Xi  栈顶(Xn+1) 当前扫描符(Xn+2)
	
    

• LR(0)：表示再每一步分析时都不用向前输入符号
• LR(1)：表示再每一步分析时都向前看一个输入符号来决定当前的动作
• SLR(1)：表示简单的LR(1)，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号

LR分析器的逻辑结构及工作流程

如图为LR分析器的逻辑结构，所有LR分析器的总控程序大致相同，只有分析表（即Go-Action表）不相同。

• 规范LR分析表构造法：用此法构造的分析表功能最强而且也适合很多文法，但是实现代价较高
• 简单LR（即SLR）分析表构造法：比较容易实现的方法，但SLR分析表功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表
• 向前LR（即LALR）分析表构造法：这种方法构造的分析表功能介于规范LR分析表和SLR分析表之间。这种表适用于绝大多数的程序语言文法，而且也可以设法有效实现

LR的分析过程

两个栈：状态栈，符号栈

移进：

归约：

接受&报错：

所以各种LR分析器的最大区别在于其分析表，分析表决定了每一步该如何移进或者归约，直至接受，或者中途报错。

LR(0)分析表的构造

1.规范句型的活前缀

**前缀：**一个符号串的前缀是指该串的任意首部(包括ε)。

​ 例：abc的前缀为：ε，a，ab，abc

归约时，归约前和归约后的被归约部分与剩余部分合起来仅构成文法的规范句型，而用哪个产生式归约仅取决于当前句型的前面部分；X1X2…Xn[p]，其中Xi为文法的符号，[p]为第p个产生式序号

• 我们把规范句型的这种前端部分的串称为活前缀。实际上，它们恰好是符号栈栈顶形成句柄时符号栈中的内容。

**活前缀：**是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

• 这是因为一旦句型的句柄在符号栈顶形成，将会立即被归约之故。所以我们将规范句型具有上述性质（不含句柄之后的任何符号）的前缀称之为活前缀。

在规范归约过程中的任何时候只要已分析过的部分即在符号栈中的符号串为规范句型的活前缀，表明输入串的已被分析过的部分是该文法某规范句型的一个正确部分。

• 定义：若 S=^*_R⇒ αAω =_R⇒ αβω 是文法G的一个规范推导，如果符号串γ是 αβ 的前缀，则称γ是G的一个活前缀。其中S为文法开始符号

LR(0)项目

活前缀和句柄间的关系：

(1) 活前缀中已含有句柄的全部符合（句柄的最后符号就是活前缀的最后符号）

(2) 活前缀只含有句柄的前部分符号（句柄的最左子串为活前缀的最右子串）

(3) 活前缀中全然不包括句柄的任何符号

(1) 表明：此时某一产生式 A → β 的右部 β 已出现在符号栈顶，因此此时相应的分析动作应当是用此产生式进行归约。

(2) 表明：形如 A → β₁ β₂ 的产生式的右部子串已在符号栈栈顶了，如 β₁ ，正期待着从余留输入串中能看到由β推出的符号串，即期待 β₂ 进栈以便能进行归约。故此时分析动作是移进当前输入符号

(3) 表明：期望从余留输入串中能看到某产生式 A → α 的右部，即α所代表的符号串（即句柄），所以此时分析的动作也是读输入符进符号栈。

在产生式的右部相应位置上加一个圆点 . ，来指示识别位置，标明在 . 前的部分已被识别

如 (1) A → β. (2) A → β₁.β₂ (3) A → .α

右部某位置上标有圆点的产生式称为LR(0)项目(item)。

不同的LR(0)项目，反映了分析过程中符号栈顶的不同情况。

每个项目的意义与圆点的位置有关

圆点左边的子串表示在分析过程的某一时刻用该产生式归约时句柄中已识别过的部分，圆点右边的子串表示待识别的部分

文法的全部LR(0)项目将是构造他的所有活前缀的有穷自动机的基础

LR(0)项目的分类

• A → α.：表明右部符号串已出现在栈顶，此时相应的分析动作应当是按此产生式进行归约，此种项目称为规约项目。
• S' → S.：称为接受项目。
• A → α.Xβ：其中α可以为ε，当X为终结符时，相应的分析动作应将当前的符号移入栈中，将此项目称为移进项目。
• A → α.Xβ：其中α可以为ε，当X为非终结符时，期待从余留的输入符中进行归约后而得到X，此类项目称为待约项目。

把终结符和非终结符都可看成一个有限自动机的输入符号，每把一个符号进栈相当于已识别过该符号，而状态进行转换（到下一个状态），当识别到可归约前缀时相当于栈顶已形成句柄，则认为达到了识别句柄的终态。、

==>>>构造识别活前缀的DFA：DFA中的每一个状态由若干个LR(0)项目所组成的集合(称为项目集)来表示。

举例：构造识别前缀的DFA
用I0表示这个DFA的初态，
将项目S'→.S列入项目集I0。
将项目S→.A和S→.B加入I0中。
将A→.aAb和A→.c和B→.aBb, B→.d加入I0中。

项目集I0将由如下项目组成：
I0 :   S'→.S,   S→.A,  S→.B,  A→.aAb, A→.c,   B→.aBd,   B→.d

>>> S'→.S称为项目集I0的基本项目，从基本项目出发构造项目集I0的过程，可用closure({S'→.S})表示。

closure(I)的定义:

Closure(I) = I ∪ { A → .μ | A → μ∈G ∧ K→ α.Aβ∈closure(I) ∧ α∈V∧β∈V}

构造closure(I)的算法: 1）I 中的每一个项目都属于 closure(I) 2）若形如 K→α.Aβ 的项目属于I，且 A→μ 是文法的一个产生式，任何形如 A→.μ 的项目也应加到 closure(I) 中 3）重复上述过程，直至不再有新的项目加入到closure(I)中为止。

如何确定从I0可能转移到的下一状态？

若I0中有项目 K→a **.**Ab，从输入串识别出A后，进入下一状态。设此状态为 I_i ，显然 I_i 中必含有形如 K→aA .b 的项目，称为 K→a .Ab 的后继项目。后继项目组成集合 J，则J中的每个项目都是项目集 I_i 的基本项目，有： I_i =closure( J )

定义状态转移函数：GOTO(I,A)=closure(J)

其中，I 是当前状态，A为文法符号，J 是 I 中所有形如K→a**.Ab的项目之后继项目K→aA.**b所组成的集合，而closure(J)就是项目集 I（即状态I)关于符号A的后继项目集（即后继状态）。

将G[S']的全部项目集称为文法G[S']的LR(0)项目集规范族，并记为C=(I₀ ，I₁ ，I₂ ，……，I_n )

识别文法G[S']的全部活前缀的DFA为 M = ( C，V，GoTo ， I₀ ， Z )

其中，C：M的状态集，即文法G[S'] 的LR(0) 项目集规范族 I₀ ~~~ I_n

V：M的字母表，即在M中的所有符号

GoTo：M的状态转换函数，即上述的GoTo函数

I₀ ：M的唯一初态

Z：M的终态集，Z ⊂ C 为规范族中所有含有规约项目的那些项目集

例如下图：

文法G':
(0) S' → S
(1) S → A
(2) S → B
(3) A → aAb
(4) A → c
(5) B → aBd
(6) B → d

如上为一个DFA，通过读入字符进行状态转换，以及在每个状态内进行closure闭包。

LR(0)分析表构造

要求每一个项目集中的的诸项目不出现下列的情况：

• （1）移进项目和归约项目并存，即存在移进—归约冲突；

• （2）多个归约项目并存，即存在归约—归约冲突。

​ 如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含有冲突的项目，则称G为LR(0)文法。

只有当一个文法是LR(0)文法时，才能对它构造不含冲突动作的LR(0)分析表。

构造LR(0)分析表的算法为：
     (1)对于每一项目集Ii中形如A→α.Xβ的项目，且有GO(Ii,X)=Ij,
			若X为一终结符号 a 时，则置ACTION[i,a]=Sj;
			若X为一非终结符号时，则置GOTO[i,X]=j
     (2)若Ii中有归约项目A→α. ,设A→α为文法第j个产生式，则对文法的任何终结符和“#”（均记为a）,置ACTION[i,a]=Rj
     (3)若接受项目S'→S .属于Ii ,则置ACTION[i,#]=acc。
	 (4)在分析表中,凡不能按上述规则填入信息的元素,均置为“出错”。
	 

如上图的DFA可构造分析表为:

                 ACTION											GOTO
		a		b		c		d		#					S    A    B
0		S4				S5		S6							1    2    3
1										Acc
2		R1		R1		R1		R1		R1
3		R2		R2		R2		R2		R2
4		S4				S5		S6								  7	  9
5		R4		R4		R4		R4		R4
6		R6		R6		R6		R6		R6
7				S8
8		R3		R3		R3		R3		R3
9								S10
10		R5		R5		R5		R5		R5

>>> 表中Ri代表用第i个产生式归约,Si代表移进Action表的第i行

分析器的工作过程如下：

根据输入串当前符号 a 和 分析栈栈顶状态 i 查找分析表应采取的动作：

1）若ACTION[i,a]=Sj, a∈V_T ,则把 a 移进符号栈， j 移进状态栈。

2）若ACTION[i,a]=Rj，a∈V_T 或 # ，则用第j个产生式归约。并将两个栈的指针减去K(其中，K为第j 个产生式右部的串长度），并把产生式的左部符号A压入符号栈，同时用符号对（ S_i-k , A )去查GOTO表（其中S_i-k 为状态栈当前栈顶元素，若 GOTO[S_i-k ,A] = j ,则j压入状态栈，使得两个栈内的元素一样多。

3）若ACTION[i,a]=Acc,（此时a应为“#”号），则表明分析成功，结束分析。

4）若ACTION[i,a]=空白，转出错处理。

SLR分析表构造

大多数程序设计语言的文法不是LR(0)文法。

对LR(0)规范族中有冲突的项目集（状态）用向前查 看一个（输入）符号的办法进行处理，以解决冲突。即为SLR(1)。

SLR(1) 分析表构造与LR(0) 分析表构造基本相同

SLR(1) 之所以是1，是因为向前看了一步Follow集。

假定有一个LR(0)规范族中含有如下项目集(状态)I:

I={X→a.bβ , A→g. , B→d.}其中a,b,g,d为符号串，b∈VT ,I中含有移进—归约和归约—归约冲突。

只要FOLLOW(A)和FOLLOW(B)互不相交，且都不包含b,即:
FOLLOW(A)∩FOLLOW(B)=φ
FOLLOW(A)∩{b}=φ
FOLLOW(B)∩{b}=φ

当状态I面临某输入符号a时，则动作为：
1）若a = b,则移进。
2）若a ∈ FOLLOW(A),则用产生式A→g归约。
3）若a ∈ FOLLOW(B),则用产生式B→d归约。

一般地，对于LR(0)规范族的一个项目集I可能含有多个移进项目和多个归约项目，我们可假设项目集I中有m个移进项目： A1→a1**.** b1b1, A2→ a2**.** b2b2, …, Am→ am**.** bmbm;同时含有n个归约项目：B1→g1**.** , B2→ g2**.** ,…, Bn→ gn**.** ,只要集合{b1, b2,…bm}和FOLLOW(B1),FOLLOW(B2),…,FOLLOW(Bn) 两两交集都为空，则我们仍可用上述归则来解决冲突：

1）若a∈{b1, b2,…,bm},则移进。

2）若a∈FOLLOW(Bi),i=1,…,n，则用 Bi→ gi 进行归约。

3）此外，则报错。

SLR分析表构造方法

(1) 对于每一项目集Ii中形如A.X的项目，且有GOTO(Ii,X)=Ij, 若X为一终结符号a时，则置ACTION[I,a]=S; 若X为一非终结符号时，则仅置GOTO[i,X]=j；

(2) 若归约项目A→α**.** 属于Ii,设A→α为文法第j个行产生式，则对任何属于FOLLOW(A)的输入符号a,置ACTION[i,a]=Rj；

(3) 若接受项目S' → S**.**属于Ii ,则置ACTION[i,#]=acc。

(4) 在分析表,凡不能按上述规则填入信息的元素,均置为“出错”。

（例：TODO：后面补充，ppt--Bottom-Up--P42-47）

规范LR分析表构造

SLR(1) 方法：若状态K含有 A ➡ α. ，若 α ∈ Follow(A) ，则用 A ➡ α. 归约

当状态Ix下，有产生式A ➡ α. 和A ➡ α. = … ，此时，SLR(0)不知道是将此归约成A还是移进至=，若没有其他情况能产生=，则这里产生移进归约冲突，导致错误！！！

LR(1)项目

(A→a**.** β，x) 表示： a在栈顶，输入串头部可由βx导出。

LR(1)的状态：LR(1)项目的集合

该算法为:
      令初态: Closure( (S’→.S，#) )
      
Closure(I)=
    repeat
        for any item( A→α.Xβ ，z) in I
            for any production X →γ
                for any w∈FIRST(βz)
                          I←I∪{X → .γ, w}
    until I does not change

GO (I,X)=
    J ←{}
    for any item(A→α.Xβ，z) in I
        add ( A→αX.β，z )  to J
    return Closure(J)

LALR分析表的构造

同心项目集：除去搜索符之外都相同的LR(1)项目集

合并同心项目集不会产生新的移进-归约冲突

将 LR(1) 合并同心项目集，如果没有归约-归约冲突，则为LALR(1)文法。

参考，各语法分析器的区别

各文法的区别：

• LL(1)就是向前只搜索1个符号，即与FIRST()匹配，如果FIRST为空则还要考虑Follow集
• >>>见到First集就移进，见到Follow集就归约。
• LR(0):见到First集就移进，见到终态就归约
• SLR(1)见到First集就移进，见到终态先看Follow集，与Follow集对应的项目归约，其它报错。
• >>>SLR分析法包含的展望信息是体现在利用了Follow(A)信息，可以解决“归约－归约”冲突
• SLR分析法没有包含足够的展望信息，不能完成解决“移进－归约”冲突，需要改进。
• LALR同心集合并不会产生“移进－归约”冲突 ，但会产生“归约－归约”冲突
• LR(1)

语法制导的翻译（Syntax-Directed Translation）

一种语义描述方法：语法制导的翻译

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

语法制导翻译=语法分析+语义分析+中间代码生成

语义翻译 = 语义分析 + 中间代码生成

属性文法

如何表示语义信息？为文法符号设置语义属性，用来表示语法成分对应的语义信息。

语法制导定义：是对上下文无关文法的推广，将每个文法符号和一个语义属性集合相关联，将每个产生式和一组语义规则相关联，这些用于计算该产生式中各文法符号的属性值

属性文法定义的形式

• 基础文法

• 每个文法符号有一组属性

• 每个文法产生式 A ➡ α 有一组形式为 b := f(c1,c2,……,ck) 的语义规则，其中 f 是函数，b和c1,c2,……,ck是该产生式文法符号的属性

  • 综合属性：如果b是A的属性，c1,c2……,ck是产生式右部文法符号的属性或A的其他属性

  • 继承属性：如果b是产生式右部某个文法符号X的属性

文法符号的属性分为：综合属性和继承属性。

综合属性（Synthesized Attribute）

S属性定义：仅仅使用综合属性的语法制导定义

例：

语法分析树如下

分析树的各节点属性的计算自下而上完成

继承属性（Inherited Attribute）

例：语法规则如下：

分析树如下：

分析树的依赖图如下

其中，L ➡ L₁ ，id ； L₁.in := L.in；addtype(id.entry , L.in)；

基于属性文法的处理方法

属性计算次序

拓扑排序：节点的一种顺序，是的边只会从该次序中先出现的节点到后出现的节点

①构造输入的分析树，②构造属性依赖图，③对节点进行拓扑排序，④按拓扑排序的次序计算属性。

当然，也可以多次扫描分析树，如果属性文法不存在循环依赖，每次至少会计算出一个属性值，但是编译更偏向于一边扫描的处理方法。

抽象语法树

• 语法分析与语义处理阶段分离

• 语法分析树不适合语义处理的因素：

  • 提取公共左因子
  • 消除左递归等引入新的产生式和符号、标点等语法要素不含任何语义信息

• 抽象语法树是语法分析和后续阶段的接口

S属性文法的自下而上的计算

将LR分析器增加一个域来保存综合属性值

L属性文法的自上而下的计算

---边分析边翻译的方式能否用于继承属性

属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制

分析树的节点是自左向右生成

如果属性信息是自左向右流动，那么有可能在分析的同时完成属性计算。

L属性的定义

如果每个产生式 A ➡ X₁X₂…X_n 的每条语义规则计算的属性是A的综合属性；或者X_j (1≤j≤n)的继承属性，但他仅依赖①该产生式中X_j 左边符号 X₁X₂…X_j-1 的属性；②A的继承属性

变量类型声明的语法制导定义是一个L属性定义

翻译方案，例：把有加减的中缀表达式翻译成后缀表达式，如果是8+5-2，则输出8 5 + 2 -

E ➡ T R
R ➡ addop T {print(addop.lexeme)} R1 | ε
T ➡ num {print(num.val)}

如 8+5-2可翻译成:
	E ⇒ T R ⇒ num {print (8)} R
	   ⇒ num{print (8)}addop T{print (+)}R
	   ⇒ num{print(8)}addop num{print(5)}{print (+)}R
	   … {print(8)}{print(5)}{print(+)}addop T{print(-)} R
       … {print(8)}{print(5)}{print(+)}{print(2)}{print(-)}

预测翻译器的设计

把预测分析器的构造方法推广到翻译方案的实现

如:产生式R ➡ +TR | ε 的分析过程

procedure R;
	begin
		if lookahead = '+' then begin
			match ('+');T;R;
		end
		else begin /*Do nothing*/
	end
end

语义规则的两种描述方法：属性文法和翻译方案

• S属性的自下而上计算（边分析便计算）
• L属性的自上而下计算（边分析便计算）
• L属性的自下而上计算（边分析便计算）

中间代码生成

代码优化

代码改进变换的原则

• （1）等价原则。经过优化后不应改变程序运行的结果。

• （2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。

• （3）合算原则。应尽可能以较低的代价取得较好的优化效果。

优化：①公共子表达式删除②复写传播③死代码删除④代码外提⑤强度削弱和归纳变量删除

基本块：连续的语句序列，控制流从他的开始进入，并从他的末尾离开