三、语法分析

自顶向下的语法分析

自顶向下语法分析器从语法分析树的根开始，系统化地向下扩展树，直至树的叶节点与词法分析器返回的以归类单词相匹配。该过程在树的下边缘选择一个非终结符，选定某个适用于该非终结符的产生式，用与该产生式右侧相对应的子树扩展结点。

自顶向下语法分析器的优化

而自顶向下语法分析器的效率极其依赖于其在扩展非终结符时选择正确产生式的能力。如果语法分析其总是做出正确的选择，那么其效率是非常高的；如果与之相反，那么分析代价将直线上升。在编程语言实现模式一书中，提到通过记忆化，可以使得回溯变代价变小。

递归下降分析算法

语法分析器可以利用一个简单的修改来避免回溯。在语法分析器去选择下一条规则时，他可以同时考虑当前关注的符号以及下一个输入符号，称为前瞻符号。通过前瞻一个符号，可以消除在解析右递归表达式语法时多种选择造成的不确定性。

// 递归下降语法框架
假设有如下文法产生式：
	A -> B11 ... B1i
		| B21 ... B2j
		| B31 ... B3k
		| ...

那么就可以为 A 写出如下分析代码：

parse_A() 
	token = nextToken()
	switch (token)
	case ...: // B11 ... B1i
	case ...: // B21 ... B2j
	case ...: // B31 ... B3k
	...
	default: error(...);

为了描述这个前瞻符号，需要引入 FIRST 集合和 FOLLOW 集合。对于每个语法符号 a, 集合 FIRST(A) 为：从 A 推导出的每个符号串的第一个单词所对应的终结符的集合；而对于 FOLLOW(A) 表示紧跟在 A 导出的符号串之后的所有可能单词。使用 FIRST 和 FOLLOW 集合，可以准确的使得某个语法对自顶向下语法分析器无回溯的条件。对于产生式 A -> B ，定义其增强 FIRST 集合 FIRST+ 如下：

FIRST+(A->B) = FIRST(B) 	如果 FIRST(B) 不包含空产生式
				FIRST(B) U FOLLOW(A) 	否则

在介绍 FIRST 集构造方法之前，需要引入 NULLABLE 集合的概念。如果一个非终结符X属于集合 NULLABLE ，当且仅当：

基本情况：X ->
归纳情况：X -> Y1 …. Yn 中， Y1, ….Yn 是 n 个非终结符，且都属于 NULLABLE 集

下面看到的是 NULLABLE 集合算法：

NULLABLE = {}
while (nullable is still changing) 
	foreach (production p : x -> B)
		if (B == null)
			NULABLE U= {X}
		if (B == Y1 ... Yn) 
			if (Y1 belong NULLABLE && .... && Yn belong NULLABLE)
				NULLABLE U= {X}

下面，展示 First 集的不动点算法：

foreach (nonterminal N) 
	FIRST(N) = {}

while (some set is changing) 
	foreach (production p : N->B1 ... Bn)
		foreach (Bi form B1 upto Bn)
			if (B1 == a)
				FIRST(N) U= {a}
				break;
			if (Bi == M) 
				FIRST(N) U= FIRST(M)
				if (M is not in NULLABLE)
					break;

刚开始的时候每个非终结符都为空集。如果每次遍历完成，仍然有集合被改变时，可能会影响到其他的非终结符的集合，所以仍然需要遍历。对于每一个产生式，第一个元素如果是终结符，把该终结符加入 FIRST 集合；如果第一个是非终结符，那么把该非终结符加入 FIRST 集合，如果该非终结符属于 NULLABLE ，那么还需要再次判断紧接着的符号。

现在来看 FOLLOW 集的不动点算法：

foreach (nonterminal N)
	FOLLOW(N) = {}

while (some set is changing) 
	foreach (production p : N -> B1 ... Bn)
		temp = FOLLOW(N)
		foreach (B1 form Bn downto B1)
			if (Bi == a)
				temp = {a}
			if (Bi == M)
				FOLLOW(M) U= temp;
				if (M is not NULLABLE)
					temp = FIRST(M)
				else temp U= FIRST(M)

其中 temp 表示的是当前位置的 FOLLOW 集，初始时为当前产生式的 FOLLOW 集。现在计算该产生式关联到的非终结符的 FOLLOW 集。因此从产生式后往前看，如果是终结符，则把 temp 更新为当前终结符。如果当前为非终结符 M ，由于 temp 是当前位置的 FOLLOW 集，所以将其加入 M 的 FOLLOW 集中。现在考虑 temp 位置移动，如果当前 M 不属于 NULLABLE ，那么表示不会穿过 M ，所以 temp = FIRST(M) ，否则应该 temp U= FIRST(M) 。

通过 FIRST 和 FOLLOW 集合，可以得到 FIRST+ 集合，这样就可以编写程序实现了。当然，并不是所有的语法都是无回溯的。这个时候需要重写产生式，将公共左因子提取出来，从而消除回溯。

左递归

在自顶向下分析中，如果产生式中有做递归的情况，分析器将出现无限循环的现象。这个时候，需要将左递归转换为右递归。对于直接做递归，引入一个新的非终结符即可解决，对于间接左递归，需要先重写为直接左递归，然后再修改右递归。

程序实现

这里给出描述的这门语言的文法产生式，可以看到该语言文法产生式十分简单，对于手写来说，并不算复杂。

atom_exp:
	ID
	| FLOAT_LITERAL
	| INTEGER_LITERAL
	| CHAR
	| STRING
	| "(" exp ")"
	| ID "(" exp_list　")"
	| "[" exp_list "]"

exp_list:
	exp { "," exp }

not_exp:
	atom_exp [ "[" exp "]" ]
	
mul_div_exp:
	"!" mul_div_exp
	| not_exp	
	
add_sub_exp:
	mul_div_exp ("*" | "/" | "%") mul_div_exp
	| mul_div_exp	
	
conditon_exp:
	add_sub_exp ("+" | "-") add_sub_exp
	| add_sub_exp	
	
and_exp:
	condition_exp ("<" | ">" | ">=" | "<=" | "==") condition_exp 
	| conditoin_exp

or_exp:
	and_exp "&&" and_exp 
	| and_exp
	
exp:
	or_exp "||" or_exp 
	| or_exp

assign_exp:
	exp "=" exp
	| exp

var_decl:
	"var" ID "=" assign_exp ";" 
	
statement:
	block
	| "if" "(" assign_exp ")" statement ["else" statement]
	| "while" "(" assign_exp ")" statement
	| "return" assign_exp ";"
	| "break" ";"
	| "continue" ";"
	| assign_exp ";"
	| var_decl

block:
	"{" { statement} "}"

formal_list:
	ID { ","  ID }
	
function_decl:
	"function" ID "(" formal_list ")" block

program: 
	{ function_decl }

这里使用 EBNF 进行描述。在写代码时，对于每一个非终结符，都有与之对应的 parseXXX 函数对它进行解析。这里使用 if 语句的文法产生式，能够很清楚的看到编码方式：

//statement:
//	block
//	| "if" "(" assign_exp ")" statement ["else" statement]
//	| "while" "(" assign_exp ")" statement
//	| "return" assign_exp ";"
//	| "break" ";"
//	| "continue" ";"
//	| assign_exp ";"
//	| var_decl
//
private void parseStatement() {
	//System.out.println(current.toString());
	if (current.kind == Kind.TOKEN_LBRACE) {
		parseBlock();
		return;
	} else if (current.kind == Kind.TOKEN_KEYWORD) {
		switch (current.keyword) {
		case KEYWORD_IF: {
			advance();
			eatToken(Kind.TOKEN_LPAREN);
			parseAssignExp();
			eatToken(Kind.TOKEN_RPAREN);
			parseStatement();
			if (current.kind == Kind.TOKEN_KEYWORD &&
				current.keyword == Keyword.KEYWORD_ELSE) {
				advance();
				parseStatement();
			}
			return;
		}
		case KEYWORD_WHILE: {
			advance();
			eatToken(Kind.TOKEN_LPAREN);
			parseAssignExp();
			eatToken(Kind.TOKEN_RPAREN);
			parseStatement();
			return;
		}
		case KEYWORD_RETURN: {
			advance();
			if (current.kind != Kind.TOKEN_SEMI) {
				parseAssignExp();
			} 
			eatToken(Kind.TOKEN_SEMI);
			return;
		}
		case KEYWORD_CONTINUE: {
			advance();
			eatToken(Kind.TOKEN_SEMI);
			return;
		}
		case KEYWORD_BREAK: {
			advance();
			eatToken(Kind.TOKEN_SEMI);
			return;
		}
		case KEYWORD_VAR:
			parseVarDecl();
			return;
		default:
			error();
			break;
		}
	} else {
		parseAssignExp();
		eatToken(Kind.TOKEN_SEMI);
		return;
	}
}

代码中的 advance() 部分如下：

private void advance() {
	current = lexer.nextToken();
}

eatToken() 一部分如下：

private void eatToken(Kind kind) {
	if (kind == current.kind)
		advance();
	else {
		// 错误处理
	}
}

那么可以清晰的看到，我们每次都通过当前读入的 Token ，选择相应的文法树。一直重复这个过程，就可以实现语法分析。需要注意的是，这里面关于表达式的匹配的部分也是使用文法定义，导致这部分代码占据了大部分的内容。且还要注意各个符号的结合性（将在下一部分看到）。关于表达式中代码是隐含了运算符的优先级，所以不需要单独判断。不过有部分 parse 在实现表达式解析的时候，单独采用了表达式解析法，而不是递归下降分析法。