编译原理

一、编译器概述

1.1 定义

编译器是一个程序,完成由源代码=>目标代码

解释器也是一种处理程序的一种程序，它直接输出程序的结果并不是可执行文件

1.2 编译器核心功能

生成的目标代码和原代码语意相同

1.3 编译器简史

Fortran是第一个编译器

为什么要学习编译原理？

编译原理集中体现了计算机科学的很多核心思想

算法，数据结构，软件工程等

....

1.4 编译器结构

具有非常模块化的高层结构

前后端：前端为输入代码、后端指如何将前端映射到指令集

前端：词法分析、语法分析

后端：指令生成、指令优化

通过符号表进行交互

偏译器由多个阶段组成,每个阶段都要处理不同的问题，所以需要合理的划分组织各个阶段

接口清晰
编译器容易实现、维护

eg:

前端生成一个语法生成树，然后后端根据规则生成代码，例如此加法通过后续遍历，如果是数字就push，‘+’就执行add

整体流程：前端=>中间表示=>中段=>后端=>代码

中段主要负责优化

二、词法分析

2.1 词法分析的任务

词法分析器作用：字符流=>记号流

字符流:和被编译的语言密切相关(ASCII,Unicod....)

记号流:编译器内部定义的数据结构，编码所识别出的词法单元

记号的数据结构定义：关键词与关键词的值

2.2 词法分析器的手工构造

2.2.1 词法分析器分类

实现词法分析器方案:手工编码实现法、词法分析器的生成器

2.2.2 转移图

理解手工构造的核心问题是转移图

例如识别符号的转移图

实现代码

2.2.3 标识符的转移图

例如c语言中的变量名

2.3 自动生成词法分析器

2.3.1 正则表达式

通过声明式的规范，可以通过正则表达式。

声明式规范：正则表达式

词法分析器：有限状态自动机(DFA)

正则表达式定义：

例如在c语言中，字符集则是 ASCII

正则表达式的形式表示：

标识符：第一部分字符或下划线，第二部分加上数字且可能有多个即闭包

无符号整数：(十进制整型数）或者是0;或者是以1到9开头，后跟零个或多个0到9 => 0｜【（1｜…｜9）（0｜…｜9）*】

2.3.2 语法糖

概念：通过抽象一些概念使得程序编写更加容易

e? === e | 空串

2.3.3 有限状态自动机

FA 判断输入的字符串能否识别，能识别就回复 yes

接收的概念是输入的字符串是指能到达接受(终止)状态（双圈）

非确定有限状态自动机 NFA：不确定的含义是,存在这样的状态,对于某个输入符号，它存在不止一种转换。接受状态较难判断，一般转换为 DFA 后判断是否接受

确定有限状态自动机 DFA：确定的有限自动机从任何状态出发,对于任何输入符号,最多只有一个转换。

2.3.4 DFA 的实现

带有边和节点有向图

三、RE=>NFA

从正则表达式=>非确定转换机

3.1 RE=>NFA Thompson

对基本的RE直接构造，对复合的RE递归构造。递归算法,容易实现

e转化：本质上是说0=>1不需要吃掉字符串，没有任何代价

复合RE自动机状态 e1 e2

e1 | e2

例子：

a(b|c)*

3.2 NFA=>DFA 子集构造算法

NFA与DFA接受的字符串要完全等价

先任意输入字符串

例如 n0=>n1 输入a，但n1可通过e到{n1,n2,n3,n4,n6,n9} (即求e闭包) 得到边界q1

q1 输入 b 可以到 n5, 得到边界 q2

依次推出所有边界集合

子集构造算法代码

算法不可能无限循环

时间复杂度最坏

O （ 2^{N})

N表示NFA状态节点个数

3.2.1 eps闭包的计算

通过深度优先算法

sq q

3.3 DFA 最小化 Hopcroft算法

3.4 DFA生成分析算法

先生成 DFA 代码表示 (转移表类似于邻接矩阵)

驱动代码输入字符串后可判断识别

3.4.1 最长匹配

四、语法分析

4.1 语法分析任务

早期语法分析只判断，是否有语法错误，后续语法分析演变成生成抽象生成树

需要语法规则来判断是否符合语言规则

使用语法树

4.2 上下文无关文法

4.2.1 概念

总共四类文法：三性=>零性文法：正则表达式=>上下文无关文法=>上下文有关文法=>任意文法

上下文无关法本来是用来描述自然语言的，用来形式化自然语言

S(句子) => N(名词) V（动词) N（名词)

上下文无关文法G = (T,N,P,S) 是一个四元组

T:是终结符集合 N: 终结符 P:一组产生规则 S:唯一的开始符号

每条规则的形式: X => β_{1} β_{2} \dots β_{n}, X \in N, β \in (T \cup N)

所有终结符都是大写符号

4.2.2 推导

不停的替换非终结符,直到句子全是终结符停止。

最左推导:每次总是选择最左侧的符号进行替换
最右推导:每次总是选择最右侧的符号进行替换

语法分析器需要做什么：给定文法G和句子s（无非终结符叫句子)，判断是否存在对句子s的推导

4.3 分析树和二义性

4.3.1 分析树

推导得到对应的分析树，推导得到分析树和推导顺序无关(最左最右...)

特点：

树中的每个内部节点代表非终结符
每个叶子节点代表终结符
每一步推导代表如何从双亲节点生成它的直接孩子节点

树的每一层往下都代表一次替换，最终叶子节点表示终结符。树的意义通过后续遍历来表达。

因此两颗树产生了二义性

4.3.2 二义性文法

给定文法G，如果存在句子s,它有两棵不同的分析树，那么称G是二义性文法。

解决方式：文法分析

表达式文法的重写

4.4 自顶向下分析

语法分析:给定文法G和句子s,回答s是否能够从G推导出来?

基本算法思想:从G的开始符号出发，随意推导出某个句子t比较t和s

若t==s，则回答“是”
若t!=s，并不能直接返回“否”，可能是推导顺序不对需要回溯

从开始符号出发推出句子，因此是自顶向下

伪代码实现：

注意压栈的时候需要逆序压入。

此种算法效率太低，需要一种线性时间算法，避免回溯。

因此引入递归下降分析算法，和 LL(1)分析算法

前看符号避免回溯

4.5 递归下降分析算法

也称预测分析算法

分析高效(线性时间）
容易实现(方便手工编码)错误定位和诊断信息准确
被很多开源和商业的编译器所采用 GCC 4.0，LLVM...

算法基本思想：分治法

每个非终结符构造一个分析函数
用前看符号指导产生式规则的选择

如果是终结符就判断是否相等，否则递归调用非终结符的分析函数

eg： x=> a B

parse_x() token==a;

parse_B();

error()

4.5.1 出现两种转化都可以辨别时如何处理

当输入 num 时 E转化两种形式都可以识别当前的字符

4.5.2 错误分析

递归向下分析算法必须具有调整机制

插入单词

插入单词来进行错误恢复是一种危险的做法，可能插入会进一步导致其他错误，陷入死循环。插入法不必对实际的输入调整，假装存在某个单词，输出错误信息，然后返回即可。
删除单词

跳过若干个单词直至达到一个属于 FOLLOW 集合的单词为止。

4.6 LL(1)分析算法

总结来说：算出 First集和FOLLOW集，对应每一条产生式，求出每条产生式的Select集，当产生式能推出空串的时候需要将follow集加入到此情况中，其他按照first集来计算

从左(L)向右读入程序，最左(L)推导,采用一个(1)前看符号就叫做LL(1)分析算法，是一种自顶向下分析算法

分析高效(线性时间)
错误定位精确
有很多开源或商业的生成工具：ANTLR

算法思想：基于表驱动的分析算法

思想等同于自顶向下分析算法

问题转化为判断什么是正确的符号，然后将其压入栈中，这样避免了回溯

横表示非终结符，列表是此符号开头，数组的值代表正确的转换方式

分析表，数组的值代表对应的转化规则，当匹配到相应的规则时，压入对应的字符

4.6.1 FIRST集的不动点算法代码

从非终结符N开始推导得出的句子开头的所有可能的终结符的集合，得到FIRST集(开始集)

FIRST集的不动点算法

对应文法产生的FIRST集

# 0:S -> N V N
# 1:N -> s
# 2:   | t
# 3:   | g
# 4:   | w
# 5:V -> e
# 6:   | d

foreach(nonterminal N)   
	FIRST(N) = {}   # init FIRST(N) = {} 初始化每个集合为空

while(some set is changing)  // 当每一轮中有集合发生了变化继续循环  
    foreach(production p: N -> b1, b2 ..... bn)  # 对于N的每一个生成式
    if(b1 == a....)
        FIRST(N) U= {a}
	else if(b1 == M....)
    	FIRST(N) U= FIRST(M)

N\迭代次数	0	1
S	{}	{}
N	{}
V	{}

当我们把FIRST推向所有字符串的时，即不局限于非终结符。

FIRST_S(b1,b2,b3.....bn) // Sentences句子
	FIRST(N)	IF b1 == N
	{a}         IF b1 == a

这样就得到了所有转化关系的FIRST集,因此构造出分析表。

且得出LL(1)定义，如果分析表中每个表项都只有一个值，则成其为LL(1)文法

非终结符\终结符	s	t	g	w	e	d
S	0	0	0	0
N	1	2	3	4
V					5	6

如果是集合S，那么将所有FIRST(S)集合中的元素填入对应的转化关系编号到表中

4.6.2 分析表中的冲突

分析表中表项有超过一个的情况会产生冲突

非终结符\终结符	s	t	g	w	e	d
S	0	0	0	0
N	1	2	3	4、5
V					6	7

# 0:S -> N V N
# 1:N -> s
# 2:   | t
# 3:   | g
# 4:   | w     => {w}
# 5:   | w V   => {w} 
# 6:V -> e
# 7:   | d

此情况两种转化式都满足w开头，因此可能再次出现回溯

对N的两条产生式规则N=>β和N=>γ，要求FIRST_S(β)∪FIRST_S(γ)=={},如果不为空集则会产生冲突

4.6.3 一般条件下的LL(1)文法

FIRST_S(XYZ)

一般情况下需要知道XY是否可为空串,NULLABLE
且需要知道某个非终结符后面跟着什么符号，跟随集FOLLOW

NULLABLE集合定义：**非终结符x**属于集合NULLABLE,当且仅当:

# 基本情况
# X -> eps    # e为空串

# 归纳情况
# X -> b1 b2 ... bn
	当且仅当b1 b2 ... bn都属于NULLABLE时，X才为NULLABLE

得到NULLABLE集合的算法

NULLABEL = {}   # init nullable

while(nullable is still change)
	foreach(production p: X -> b) // 遍历每条产生式
		if(b == e)
			NULLABLE U= {X}
		else if (b == Y1, Y2, .... Yn) //注意 Yn 也要是NULLABLE
			if(Y1 属于 NULLABLE && Y2 属于 NULLABLE && .....)
				NULLABLE U= {X}

0	1	2
NULLABLE	{}

# Z -> d
# 	 | X Y Z
# Y -> c
# 	 | e   # e为空串
# X -> Y
# 	 | a

有了NULLABLE便可推FIRST集合的完整计算公式

# 基本情况：
	X -> a  #是终结符的情况
		FIRST(X) U= {a}
# 归纳情况：
	X -> Y1,Y2,Y3...Yn
		FIRST(X) U= FIRST(Y1)
		if Y1 属于 NULLABLE
			FIRST(X) U= FIRST(Y2)
		if Y1, Y2 属于 NULLABLE
			FIRST(X) U= FIRST(Y3)
		.......

得到伪代码

foreach(nonterminal N)
	FIRST(N) = {}
	
while(some set is changing)
	foreach(prduction p: N->b1,b2,b3...bn)
		foreach(bi from b1 to bn)
			if (bi == a...)
				FIRST(N) U= {a}
				break
			if (bi == M...)
				FIRST(N) U= FIRST(M)
				if(M not in NULLABLE)
					break 
                //else  // 如果M是在NULLABLE中需要加上其后面跟着符号的FIRST集合 可以不写让他继续遍历下去
                //   FIRST(N) U= FOLLOW(M)

N\FIRST	0	1	2	3
Z	{}
Y	{}
X	{}

FOLLOW集合的不动点算法

foreach( nonterminal N)
	FOLLOW(N) = {} 			# init nonterminal N
	
while(some set is changing)  // 注意计算非终结符follow集并不是单独计算的，在每个产生式中都需要执行每一个符号
	foreach(production p: N -> b1, b2, b3.... bn) 
		temp = FOLLOW(N)  # temp一开始代表N的结束后跟着的集合 每一次都往前移
		foreach(bi from bn to b1)  # 逆序！
			if(bi == a ...) 
				temp = {a} 
			if(bi == M ...)
				FOLLOW(M) U= temp
				if(M is not NULLABLE)
					temp = FIRST(M) # M不能为空当前得到的FOLLOW只能是M的开头
				else
					temp U= FIRST(M)   # M可以为空所以当前得到的FOLLOW是 FIRST(M) + 原来temp

根据此算法得出非终结符的FOLLOW集合

N\FOLLOW	0	1	2
X	{}	{}	{}
Y	{}
Z	{}

得到了NULLABLE和FOLLOW最终得出 FIRST_S 的算法

foreach(production p)
	FIRST_S(p) = {}
	
calculte_FIRST_S(production p: N -> b1, b2, ... bn)
	foreach(bi from b1 to bn)
		if(bi == a ...)     # 第一个符号是终结符就直接加入FIRST_S 并返回函数结束
			FIRST_S(p) U= {a}
			return
		if(bi == M ...)
			FIRST_S(p) U= FIRST(M) # 非终结符计算对应的FIRST(M)
				if(M is not NULLABLE) # 如果可以为空则需要继续看后面的符号 继续foreach
					return 
	FIRST_S(p) U= FOLLOW(N) # 如果上面始终没有返回代表全部可以为空，则需要加上FOLLOW(N)集合

4.6.4 回看分析表中的冲突

消除左递归可以解决冲突，任何有左递归的文法都不是LL(1)文法

#0:E -> E + T				#0: E -> TE'			
#1:   | T					#1: E'-> +TE'
#2:T -> T * F     =>   		#2:    | 
#3:   | F 					#3: T -> FT'
#4:F -> n					#4: T'-> *FT'
							#5:    |
							#6: F -> n

	n	+	*
E	0
E’		1
T	3
T’		5	4
F	6

提取左公因子

# 0: X -> aY
# 1:    | aZ

# 可以通过提取公因子的方法，比如对上述文法提取一个{a}.就可变为

# 0: X -> aX'
# 1: X'-> Y
# 2:    | Z

也可以解决一定冲突

4.7 LR(0)

LL(1)分析文法有限，往往需要文法的改写.

LR分析算法(移进-归约算法),是一种自底向上分析算法。

从左(L)向右读入程序，最右(L)推导,不用前看符号来决定产生式的选择(0个前看符号)

产生式从左到右称为推导，从右到左称为归约

是一个最右推导的逆过程，需要两个步骤。

点左边代表已经读入栈中，点号的右侧是待输入的字符

移进一个记号到栈顶上，或者
归约栈顶上的n个符号（某产生式的右部)到左部的非终结符(当我们发现一个原点到达项的末尾)

对产生式 A->β1 ...βn

如果βn ... β1在栈顶上，则弹出βn...β1压入A=---------------

4.7.1 移进和归约的时机

利用一个有记忆能力的自动机帮助我们匹配字符

加入一个项目集合：带有·号的产生式

shift 2 表示到达2状态

reduce 2 表示利用产生式2进行归约

分析 : x x y $
起始状态 :     *  x x y $   # 开始点的左侧没有读入
		   1 x * x y $     # 开始后读入第一个字符x ，并且是从1号状态开始的
		   1 x 2 x 3 y 4 * $  # 读入 x 后到达状态2压入栈中，后面同理
		   1 x 2 x 3 T * $    # 当到达$后需要开始归约
		   1 x 2 x 3 T 5 * $  # 3 T => 5 则压入并且开始归约 x x T
		   1 S * $            # 1 S => 6 是一个终止状态则成功匹配

stack = []
push ($) // $: end of file
push (1) // 1: initial state
while (true)
    token t = nextToken()
    state s = stack[top]
    if (ACTION[s, t] == "si")
        push (t); 
        push (i)
    else if (ACTION[s, t] == "rj")
        pop (the right hand of production "j: X -> B")
        state s = stack[top]
        push (X); 
        push(GOTO[s, X])
else error (…)