自上而下语法分析

递归下降分析法

当文法没有公共左因子，没有左递归时，让每个非终结符对应一个过程（函数），该过程对相应的非终结符产生式的右部短语进行语法分析，这种方法称为递归下降分析法。这样的分析程序称为递归下降分析器。实际上相当于有限自动机的实现模型。

注意先消除公共左因子和左递归
由于消除了公共左因子，所以在语法分析时不存在回退，一旦开始匹配某个符号，中途出现不匹配时就不用回退，直接报错。

对于语法
$E\to TE'$
$E'\to +TE' | \epsilon$
$T\to FT'$
$T\to *FT'|\epsilon$
$F\to (E)|i$

void parse_E(){
	parse_T();
	parse_Ep();
}

void parse_Ep(){
	if (cur == '+'){
		advance();
		parse_T();//不存在回退
		parse_Ep();
	} else {
		return;//遇到epsilon还是回退
	}
}

void parse_T(){
	parse_F();
	parse_Tp();
}

void parse_Tp(){
	if (cur == '*'){
		advance();
		parse_F();
		parse_Tp();
	} else {
		return;//遇到epsilon还是回退
	}
}

void parse_F(){
	if (cur == '('){
		advance();
		parse_E();
		if (cur == ')'){
			advance();
			return;
		} else {
			error();
		}
	} else if (cur == 'i'){
		advance();
	} else {
		error();
	}
}

使用拓展的BNF来简化文法

递归下降分析法对较深的语法树分析效率较低，可以将BNF文法转化为EBNF的文法，可以消除左递归且更加简化，递归下降分析器也更简单

对于与上文相同的文法，EBNF更加简洁
$E\to T{+T}$
$T\to{*F}$
$F\to (E)|i$
分析起来也更简洁

void parse_E(){
	parse_T();
	while (cur == '+'){
		advance();
		parse_T();
	}
}

void parse_T(){
	parse_F();
	while (cur =='*'){
		advance();
		parse_F();
	}
}

void parse_F(){
	//同上
}

预测分析法

由表驱动的分析方法，由下推栈，预测分析表和控制程序组成，它实际上是一种下推自动机的实现模型。

• 预测分析表
  一个由（当前栈顶符号, 当前字符串指向的符号）构成的表，指向此种栈顶符号按照文法可以推导出的符号序列（或者出错）

控制程序分析过程：

1. 准备一个栈，压入栈底标志#和文法开始符号，开始分析
2. 如果栈顶为#，代表栈其实已空，没有要分析的符号了，分析结束
3. 如果栈顶是终结符，将此与当前字符串指针指向的字符进行匹配（弹出栈顶，字符串指针后移，或报错）
4. 如果栈顶为非终结符，则查分析表M，先将栈顶弹出栈，再将对应项按逆序压入栈（或报错）

其实下推栈中的玩意儿就是“当前要分析的非终结符表”

如何构建预测分析表（难）

• First集（首字符集）：一个非终结符的First集为其所有可能产生的首个终结符的集合
• Follow集（跟随符集）：一个非终结符的Follow集为其在推导中所有可以排在此非终结符之后的终结符的集合

做题的时候要求求First集和Follow集时，即使没有明确说，也需要先消除文法中公共左因子和左递归，然后求处理之后的文法的First集和Follow集。

构造X的首字符集：

如果X是终结符，那其First集就是X
如果$X\to a...$，则将a加入First集（包括$\epsilon$也要加入）
如果$X\to Y$，则将Y的First集中除了$\epsilon$外的所有项加入X的First集
如果$X\to Y_1Y_2...Y_k$，且$Y_1...Y_j \Rightarrow \epsilon$，($j \le k$)则需要将$Y_1...Y_j$的First集中除了$\epsilon$外的所有项加入X的First集（如果推出的项可以推出空，则需要继续向后看）
重复上述步骤，直到首字符集不再增长

其实就是$\epsilon$项需要特殊处理，一个非终结符的First集中包含$\epsilon$项当且仅当它可以推出空（推出一个“以空开头”的子串是没有意义的）

构造A的跟随符集：
对右边包含A的每一个文法

如果A是文法开始符号，则把#加入Follow(A)
对于$C\to aAB$，将B的First集中除了$\epsilon$外的项加入Follow(A)
对于$C\to aA$或者$C\to aAB$但$B\Rightarrow \epsilon$，则将C的跟随符集加入Follow(A)
重复上述步骤，直到跟随符集不再增长

跟随符集中不会包含$\epsilon$，这没有意义

• 构建分析预测表
  以每一个终结符和#为表的列，以每一个非终结符为表的行。
  对于表的每一行（每一个非终结符，比如A），将其First集中除了$\epsilon$外所有终结符的对应列中填入对应的文法。如果First集中包含$\epsilon$，则将其Follow集中所有终结符对应列中填入$A \to \epsilon$（反之如果不包含$\epsilon$，Follow就根本没有用）

LL(1)文法

每一个非终结符的First集都不包含$\epsilon$或First集与Follow集没有交集（如果First集中包含了$\epsilon$，则需要其与Follow集中不包含相同符号），则其为LL(1)文法（在填写分析预测表的时候不会遇到需要在同一个格子里填入两个文法的情况）
显然非LL(1)文法无法使用LL(1)语法分析。
光消除左递归和公共左因子并不能保证语法一定是LL(1)文法，可能需要进一步改写。