语法分析

position = initial + rate * 60;

词法分析后：<id, position> <=> <id, initial> <+> <id rate> <*> <num, 60> <;>

构造赋值语句的分析树：

赋值语句：标识符(position)	=	表达式0	;

表达式0：表达式1	+	表达式2

表达式1：标识符(initial)

表达式2：表达式3	*	表达式4

表达式3：标识符(rate)

表达式4：数字(60)

e.g. 一个变量声明语句的分析树

这个变量声明语句的文法：

1
2
3

<D> -> <T> <IDS>;
<T> -> int | real | char | bool
<IDS> -> id | <IDS> , id

其中D表示declaration，T表示type，IDS表示identifier sequence，即标识符序列。

| 表示或关系。

一个标识符序列可由一个标识符id构成，也可以由一个标识符序列连接上一个逗号和一个标识符id构成。

int a, b, c; 的语法分析树：

<D>: <T>	<IDS>	;
<T>: int
<IDS>: <IDS> , id(c)
<IDS>: <IDS> , id(b)
<IDS>: id(a)

语义分析

高级程序设计语言中的语句可分为两类：声明语句和可执行语句。

语义分析的主要任务：

收集标识符的属性信息：

种属（kind）

类型（type）

存储位置、长度

值

作用域

参数和返回值信息
语义检查

变量或过程未经声明就使用

变量或过程名重复声明

运算分量类型不匹配

符号表是用于存放标识符的属性信息的数据表。

中间代码生成

常用的中间表示形式：

三地址码（Three-address Code）
语法结构树/语法树（Syntax Trees）

语法分析树是 parsing tree，和语法结构树不一样！

三地址码

由类似于汇编语言的指令序列组成，每个指令最多有三个操作数。

指令类型	指令形式
赋值指令	x = y op z, x = op y
复制指令	x = y
条件跳转	if x relop y goto n
非条件跳转	goto n
参数传递	param n
过程调用	call p, n
过程返回	return x
数组引用	x = y [i]
数组赋值	x [i] = y
地址及指针操作	x = & y, x = * y, * x = y

四元式：( op , y , z , x )

x = y op z ( op , y , z , x )

x = op y ( op , y , _ , x )

x = y ( = , y , _ , x )

if x relop y goto n ( relop , x , y , n )

goto n ( goto , _ , _ , n )

param n ( param , _ , _ , n )

call p, n (call , p , n , _)

return x ( return , _ , _ , x )

x = y [i] ( =[] , y , i , x )

x [i] = y ( []= , y , x , i )

x = & y ( & , y , _ , x )

x = * y ( =* , y , _ , x )

* x = y ( *= , y , _ , x )

一个三地址指令唯一地确定了一个运算顺序。

串s的n次幂：将n个串s连接起来。

e.g. s = ba, 则s^1 = ba, s^2 = baba, …

CFG的分析树

根节点的标号为文法开始符号

内部节点表示一个产生式A -> beta 的应用，该节点的标号是此产生式左部A。该节点的子节点的标号从左到右构成了产生式的右部beta。

叶节点的标号既可以是非终结符，也可以是终结符。从左到右排列的叶节点得到的符号串称为这棵树的产出（yield）或边缘（frontier）。

给定一个推导 S => a1 => a2 => … => an，对于推导过程中得到的每一个句型ai，都可以构造出一颗边缘为ai的分析树。

G:
E -> E + E
E -> E * E
E -> -E
E -> (E)
E -> id

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语（phrase）。

如果子树只有父子两代节点，那么这棵子树的边缘称为该句型的一个直接短语（immediate phrase）。因此，直接短语一定是某产生式的右部。但是，产生式的右部不一定是给定句型的直接短语。

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。

消歧规则：每个else和最近的尚未匹配的if匹配。

正则表达式

正则表达式（Regular Expression, RE）是一种用来描述正则语言的更紧凑的表示方法。

语言 L = {a}{a,b}*({epsilon} U ({.,_}{a,b}{a,b}*))

r = a(a|b)*(epsilon|(.|_)(a|b)(a|b)*)

表示：第一个字母是a，接下来连接任意长度的a或b串，然后，如果再连接一个空串epsilon，说明句子结束；否则，还可以连接后面指定的东西。

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式r定义（表示）一个语言，记为L(r)。

正则表达式的定义

空串epsilon是一个RE，L(epsilon) = {epsilon}.
如果a属于字母表Sigma，则a是一个RE，L(a) = {a}.
如果r和s都是RE，表示的语言分别是L(r)和L(s)，则：

r | s 是一个RE，L(r|s) = L(r) U L(s)

rs 是一个RE，L(rs) = L(r)L(s)

r* （r的克林闭包）是一个RE，L(r*) = (L(r))*

L(a|b) = L(a) U L(b) = {a} U {b} = {a, b}

L((a|b)(a|b)) = L(a|b) L(a|b) = {a, b} {a, b} = {aa, ab, ba, bb}

L(a*) = (L(a))* = {a}* = {epsilon, a, aa, aaa, …}

L((a|b)*) = {a, b}* = {epsilon, a, b, aa, ab, ba, bb, aab, …}

在C语言中：

十进制无符号整数的RE：(1|...|9)(0|...|9)*|0

八进制无符号整数的RE（八进制的第一个符号是0）：0(1|...|7)(0|...|7)*

十六进制无符号整数的RE（十六进制的前两个符号是0x）：0x(1|...|9|a|...|f|A|...|F)(0|...|9|a|...|f|A|...|F)*

可以用RE定义的语言叫正则语言（regular language）或正则集合（regular set）.

正则定义

正则定义是具有如下形式的定义序列：

d1->r1

…

dn->rn

其中，每个di都是一个新符号，即给ri取的名字。它们都不在字母表Sigma中，而且各不相同。每个ri都是字母表Sigma U {d1, …, dn}上的正则表达式。

因此，正则表达式就是给一些RE命名，并在之后的RE中像使用字母表中的符号一样使用这些名字。

C语言中标识符的正则定义：

1
2
3

digit -> 0|1|2|...|9
letter_ -> A|B|...|Z|a|b|...|z|_
id -> letter_(letter_|digit)*

（整型或浮点型）无符号数的正则定义：

digit -> 0|1|2|...|9
digits -> digit digit*
optionalFraction -> .digits|epsilon  //小数点后可以有或没有数字
optionalExponent -> (E(+|-|epsilon)digits)|epsilon
number -> digits optionalExponent optionalFraction

有穷自动机

有穷自动机（Finite Automata, FA）是对一类处理系统建立的数学模型。

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。其中，状态概括了对过去输入信息处理的状况。

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

FA模型

输入带（input tape）：用来存放输入符号串。

读头（head）：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动。

有穷控制器（finite cotrol）：具有有穷个状态数，根据当前状态和当前输入符号控制转入下一状态。

转换图（transition graph）：

节点：FA的状态
- 初始状态：只有一个，由start箭头指向
- 终止状态：可以有多个，用双圈表示
带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

FA定义（接收）的语言：

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收。

最长子串匹配原则（Longest String Matching Principle）：当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。

在到达某个终态后，只要输入带上还有符号，FA就继续前进，以便寻找尽可能长的匹配。

分类

确定的FA（Deterministic finite automata, DFA）

M = ( S, Sigma, sigma, s0, F )

S: 有穷状态集

Sigma: 字母表，即输入符号集合。假设空集epsilon不是字母表Sigma中的元素

sigma: 将 S*Sigma 映射到S的转换函数。对任意S中的元素s，Sigma中的元素a，sigma(s, a)表示从状态s出发，沿着标记为a的边所能到达的状态。

s0: 开始状态，是S的元素

F: 接收状态集合，是S的子集

可以用转换表表示DFA。

非确定的FA（Nondeterministic finite automata, DFA）

NFA与DFA的不同之处在于，NFA的sigma是将 S*Sigma 映射到2^S的转换函数。

正则文法、正则表达式、有穷自动机三者等价。

下图来自LINK：

NFA 和 DFA 的区别：DFA 可以认为是一种特殊的 NFA，它最大的特点，就是确定性。它的确定性在于，在一个状态下，输入一个符号，一定是转换到确定的状态，没有其他的可能性。

avatar

可以看到，在状态 1 这里，如果输入 a，其实有两种可能，如果后面的符号是 b，那么可以匹配成功，后面符号是 c 也能匹配成功。所以状态机在执行过程中，可能要尝试所有的可能性。在尝试一种可能路径匹配失败后，还要回到之前的状态再尝试其他的路径，这就是“回溯”。

但是 DFA 消除了这种不确定性，所以可以想见，其执行性能应该要比 NFA 更好，因为不需要回溯。

NFA 是可以转换为等价的 DFA 的，也就是说，理论上讲，正则表达式可以用 DFA 来实现，从而获得优于 NFA 的执行性能。但是 NFA 转换 DFA 的过程，会消耗更多资源，甚至最终得到的 DFA 要占用大量存储空间（据有的资料的说法，可能会产生指数级增长）。而且，DFA 相比 NFA，在实现一些正则表达式的特性时会更复杂，成本更高。所以当前的许多编程语言，其正则表达式引擎为 NFA 模式。

带有”epsilon-边”的NFA：即sigma是将 S*(Sigma U {epsilon}) 映射到S的转换函数。

DFA的算法实现：

输入：以文件结束符eof结尾的字符串x，DFA D的开始状态s0，接收状态集F，转换函数move.

输出：如果D接收x，则回答YES，否则回答NO。

s = s0;
c = nextChar();
while(c != eof) {
  s = move(s, c);
  c = nextChar();
}
if(c in F) return "YES";
else return "NO";

将正则表达式转换为DFA

先将正则表达式转换为NFA，再将NFA转换为DFA。

编译原理