简介

概述

需要将分解好的Token进行语法匹配，生成抽象语法树(Abstract Syntax Tree , AST）。在此过程中需要检测非法语法，并指出问题所在。 在实现上一般由语法解析器驱动词法分析器进行分析。 实现上一般被称作Parser（解析器）。 语法分析程序产生器YACC，使用根据语法规则生成C语言语法分析器。

Abstract Syntax Tree（抽象语法树）

叶子节点是终止符（[[#定义]]），非叶子结点是非终止符（[[#定义]]）。

原理

Grammars（文法)

定义

文法是用来描述语言的语法成分结构构造的形式规则， 我们通常用G表示。

• 语法成分由句子和构成句子的词素组成
• 语言由句子组成

则将文法G定义为：

其中：

终止符（Terminal）集合为：，也可记为，也可以理解为语言中的字符串，不可分割 非终止符集合为：，也可记为，它需要不断被迭代替换为终止符组成的句子 开始符号为： 产生式为：，它定义了一组符号推导规则

推导

由文法开始符号开始推导， 用产生式的右部取代产生式的左部， 直到推到终结符号为止。 推导分为最左推导和最右推导， 最左推导每次替换式子的最左边， 最右替换每次推导式子的最右边。

示例

假定有文法

对于输入字符串：

可以得到整个推导过程：

规约

规约是句子通过文法规则将产生式的左部取代右部， 直到规约到开始符号为止。 规约也分为最左规约和最右规约。 最左规约和最右推导互为逆过程，同样，最右规约和最左推导互为逆过程。

语言形式

文法具体又可以分为0型文法， 1型文法， 2型文法，3型文法。下面的说明中

0型文法

中的产生式，其中并至少含有一个非终结符，。又叫做短语文法或无限制文法， 识别0型语言的自动机称为图灵机（TM）。

1型文法

中的产生式，除可能有外均有。若有，规定不得出现在产生式的右部。又称为上下文有关文法或者长度增加文法， 通过线性界限自动机（LBA）识别。

2型文法

中的产生式具有形式，其中，。又称为上下文无关文法，记作CFG（Context-Free Grammar）， 通过下推自动机（PDA）识别。

3型文法

中的产生式具有形式，或者，，其中，。又称为正规文法，记作RG（Regular Grammar）， 通过有限状态自动机识别。 Backus-Naur Form（BNF,巴克斯范式）是一种上下文无关文法。 通常研究上下文无关文法和正规文法， 因为程序设计语言的语法和词法规则主要与2型文法和3型文法有关。

Ambiguity（二义性）

一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。 二义性问题是不可判定问题，即不存在一个算法在有限步骤内，确切判定一个文法是否有二义性。

分析方法

自上而下

从文法的开发符号出发，反复使用各种产生式，寻找“匹配”的推导。 从树的根部开始，构造语法树。 主要方法有：递归下降算法和预测解析器 需要解决的核心问题：回溯问题和文法左递归问题

Recursive Descent Algorithm（递归下降算法）

树的构建过程从上而下，从左往右。

示例 假定有文法

输入字符串为： 第1次解析，推导到，左括号与int不匹配

第2次解析，推导到，左括号与int*T不匹配

第3次解析，推导到，左括号与(E)匹配，继续解析E

第4次解析，推导到，int匹配，继续解析(E)剩余部分

第5次解析，推导到，有括号匹配，解析完毕

实现

定义TOKEN，泛化为tokens类别 定义next为全局指针指向下一个输入的token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

tokens []TOKEN; // 词法解析的结果
TOKEN next=tokens[0]; // 初始化指向输入点

// 返回输入token类型与指定是否匹配
bool term(TOKEN tok) { return *next++ == tok; }

// 定义E的产生式
// E->T
bool E1() { return T(); }
// E->T+E
bool E2() { return T() && term(PLUS) && E(); }
// E相关产生式
bool E() {
	TOKEN *save = next;
	return (next=save, E1())
		|| (next=save, E2());
}

// 定义T的产生式
// T->int
bool T1() { return term(INT); }
// T->int*T
bool T2() { return term(INT) && term(TIMES) && T(); }
// T->(E)
bool T3() { return term(OPEN) && E() term(CLOSE); }
// T相关产生式
bool T() {
	TOKEN *save = next;
	return (next=save, T1())
		|| (next=save, T2())
		|| (next=save, T3());
}

特点 - 优点 非常容易实现 - 缺点 若部分成功，不会尝试其他推演； 不是适配所有语法 需要单独处理左递归和回溯问题

左递归问题

当存在一种推导路径，算法会陷入无限循环中。根据左递归方式，可以有如下处理方式。

产生式左递归

通用文法记为：，其中不包含起始的 重新改写为：

整体思路：将左递归改为右递归方式，先判断终止符再递归即可防止无限递归。 推导路径左递归

将非终止符按顺序排列，后面的非终止符不应包含前面非终止符的左递归形式，若存在则使用推导方式将其消除。然后就简化为产生式左递归，按照上面方式进行处理即可。

回溯问题

产生式中存在相同终止符开头的选择，算法需要暂时存储上下文，某条分支不匹配又需要重新恢复。消除这种选择即可消除回溯问题。

First Sets（首字符集）

获取字符集（即X = ）的可能包含的第一个终止符（包括），其定义如下：

特性： 若为终止符，则 若，则 若，并且每个都存在，则 若，并且每个都存在，则

Follow Sets（后继字符集）

获取字符集（即X = ）的可能的紧邻的一个终止符（包括文本结尾符），其定义如下：

特性： 若为开始符， 若每个产生式，则 若每个产生式，并且，则

示例

假定有文法

根据产生式(2)，可以得到；再根据产生式(1)，可以得到；综合可得。 同理，可得

得到非终止符的后继字符集：

根据产生式(4)，可得；再加上产生式(3)，可得和；

其他终止符同理，可以得到终止符的后继字符集：

Predictive Parsers（预测解析器）

在递归下降算法基础上，增加预测功能。即向后查看更多的token。 一般使用LL(1)，只预测一个token。

示例

假定有文法

对于产生式(1)要能生效，当前非终止符为，根据产生式(3)输入只能是(和int。 对于，需要根据文法和非终止符逆推非终止符后面可能的输入。比如，右侧有的只有产生式(1)，因，则；再逆推到产生式(3)有，则。具体建表规则间后面。 其他同理，可以得到LL(1)解析表：

步骤

1. 初始化栈为，并初始化next指向下一个输入token；
2. 获取栈顶两个元素；
3. 若为非终止符，则根据和输入token查找解析表。若命中表达式，则将重新入栈；若未命中则直接报错；
4. 若为终止符，则判断是否与输入token匹配，next指向下一个token。若匹配则将重新入栈；若未命中则直接报错；
5. 重复步骤2-4，直到栈为空；

使用表格推演示例解析输入过程：

解析表构建方法

对于文法需要构建LL(1)解析表，则每个产生式进行如下处理： - 每个终止符，都有 - 若存在，则每个终止符都有 - 若存在并且，都有

注意，对于表格项。若为空或多个不同值，则解析异常。

自下而上

从输入字符串开始，逐步进行归约，直到文法的开始符号。 从树的叶节点开始，构造语法树。 主要方法有：算符有限分析法和LR分析法 需要解决的核心问题：识别可规约串

算符优先法

特点

优点：简单，快速 缺点：可能错误接受非法句子 适用范围：用于分析各类表达式

示例

假定有文法

可以得到优先关系表：

优先关系表构建方法

下面小写字母为终结符，大写字母为非终结符。 - 确定满足关系的所有终结符对 ，当文法G中含有形如或的产生式 - 确定满足关系和的所有终结符对 ，当文法G中含有形如的产生式，而或；记为 ，当文法G中含有形如的产生式，而或；记为

关键转换为构建FIRSTVT(P)和LASTVT(P)。

构造FIRSTVT(P)的算法，反复使用下面规则： - 若有产生式，则 - 若，且有产生式，则

FIRSTVT(P)算法伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BEGIN
	FOR a,P in Vt,Vn DO
		F[P, a] := FALSE;
	FOR Product in G DO
		F[P, a] = TRUE;
		INSERT(P, a); // into STACK, P->a... P->Qa...
	WHILE STACK not empty DO
	BEGIN
		Q,a := top of STACK
		FOR Product in G DO
			F[P, a] = TRUE;
			INSERT(P, a); // P->Q...
	END OF WHILE;
END

LASTVT(P)伪码类似，按照定义编写即可。 优先关系表算法伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

FOR PRODUCT in G DO
BEGIN
	FOR i:=1 TO n-1 DO
	BEGIN
		IF Xi,Xi+1 in Vt THEN Xi EQ Xi+1
		IF i<=n-2 && Xi,Xi+2 in Vt && Xi+1 in Vn THEN Xi EQ Xi+2
		IF Xi in Vt && Xi+1 in Vn THEN
			FOR a in FIRSTVT(Xi+1) DO
				Xi LT a
		IF Xi in Vn && Xi+1 in Vt THEN
			FOR a in LASTVT(Xi) DO
				a GT Xi+1
	END
END

素短语

定义

一个文法G的句型是指一个短语，它至少包含一个终结符，并除它自身以外不再含任何更小的素短语。 最左素短语是指处于句型最左边的素短语。

定理

算符优先文法句型一般形式：。 一个算符优先文法G的任何句型的最左素短语满足如下条件的最左子串，

获取最左素短语伪码，其中LTD:, GTD:, EQD:, ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

k := 1;
S[k] := '#';
REPEAT
	a := READ string;
	IF S[k] in Vt THEN j:=k ELSE j:=k-1;
	WHILE S[j] GTD a DO
	BEGIN
		REPEAT
			Q:=S[j];
			IF S[j-1] in VT THEN j:=j-1 ELSE j:=j-2
		UNTIL S[j] LTD Q
		S[j+1]...S[k] => N
		k:=j+1
		S[k]:=N
	END OF WHILE
	IF S[j] LTD a OR S[j] EQD a THEN
		BEGIN k:=k+1;s[k]:=a END
	ELSE  ERROR
UNTIL a='#'

LR分析法

基本概念

1965年由Knuth提出“the art of computer programming” L：从左到右扫描输入串 R：自下而上进行归约

定义

令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有

则β称是句型相对于非终结符A的短语 如果有，则称β是句型相对于规则的直接短语 一个句型的最左直接短语称为该句型的句柄 规范归约是最左归约 规范归约的逆过程就是最右推导

最右推导也称为规范推导 由规范推导推出的句型称为规范句型 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即对于规范句型，β为句柄，如果， 则符号串是的活前缀。（必为终结符串）

分析过程

假定初始格局为：

分析器根据确定下一步动作 1. 若为移进，且s为下一状态，则格局变为： 2. 若为按归约，格局变为： 此处，，r为β的长度， 3. 若为“接受”，则格局变化过程终止，宣布分析成功。 4. 若为“报错”，则格局变化过程终止，报告错误。

LR(0)项目

有四个项目

称为归约项目 归约项目称为接受项目 称为移进项目 称为待约项目 识别活前缀的NFA

NFA转换为DFA，识别活前缀的DFA

项目集闭包CLOSURE

假定I是文法的任一项目集，定义和构造I的闭包CLOSURE(I)如下： 1. I的任何项目都属于CLOSURE(I); 2. 若属于CLOSURE(I)，那么，对于任何关于B的产生式，项目也属于CLOSURE(I)； 3. 重复上述两步骤直至CLOSURE(I)不再增大位置。

状态转换函数

为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I,X)定义为： 其中 J={任何形如的项目|属于I} 直观上说，若I是对某个活前缀有效地项目集，那么GO(I,X)便是对有效的项目集。

项目集的转移函数计算示例

构造算法

1
2
3
4
5
6
7
8
9

PROCEDURE ITEMSETS(G')
BEGIN
	C:={CLOSURE({S'->.S})};
	REPEAT
		FOR I in C and X in G' DO
			IF GO(I,X) and GO(I,X) not in  C THEN
				C.append(GO(I,X))
	UNTIL C not change
END

LR(0)文法

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

• 既含有移进项目又含归约项目；
• 含有多个归约项目

LR(0)分析表

1. 若项目属于且，a为终结符，则置ACTION[k,a]=“sj”
2. 若项目属于，那么对
3. 若项目S’->S.属于，则置ACTION[k,#]=“acc”
4. 若，A为非终结符，则置GOTO[k,A]=j
5. 分析表中凡不能用上述规则的空白格均置报错标志。