自上而下的语法分析：从开始符号S出发，看能否找到一个最右推导，使得$S\Rightarrow \omega$；或从S出发，能否构成一个语法树，使得树的叶节点自左向右构成$\omega$。

一、回溯分析法

1. 提取公共左因子

$$A\to \alpha\beta_1|\alpha\beta_2|\ldots|\alpha\beta_n|\delta$$

提取公共左因子后：

$$\begin{aligned} A\to &\alpha B|\delta \\ B\to &\beta_1|\beta_2|\ldots|\beta_n \end{aligned}$$

2. 消除左递归

消除直接左递归

直接左递归：文法中直接出现左递归，即有形如$A\to A\alpha$的产生式。

$$A\Rightarrow A\alpha\Rightarrow A\alpha\alpha\Rightarrow\ldots$$

产生无限推导。

将左递归的产生式改写成等价的右递归的产生式。

$$A\to A\alpha_1|A\alpha_2|\ldots|A\alpha_n|\beta$$

改写后：

$$\begin{aligned} A\to &\beta A' \\ A'\to &\alpha_1A'|\alpha_2A'|\ldots|\alpha_nA'|\varepsilon \end{aligned}$$

消除间接左递归

间接左递归：通过推导产生的左递归。

$$\begin{aligned} S\to &Aa\\ A\to &Sb|c \end{aligned}$$

$$S\Rightarrow Aa\Rightarrow Sba\Rightarrow Aaba\Rightarrow Sbaba\Rightarrow\ldots$$

存在间接左递归同样会产生无限推导。

例：

$$\begin{aligned} S\to &Qc|c\\ Q\to &Rb|b\\ R\to &Sa|a \end{aligned}$$

1. 用R代入Q

$$Q\to Sab|ab|b$$

2. 用Q代入S

$$S\to Sabc|abc|bc|c$$

消除直接左递归：

$$\begin{aligned} S\to &abcS'|bcS'|cS'\\ S'\to &abcS'|\varepsilon \end{aligned}$$

3. Q和R为多余可删除，最后答案如上式

二、递归下降分析法

当文法改造为无公共左因子，无左递归时，让每个非终结符对应一个过程，该过程对相应的非终结符产生式的右部短语进行语法分析。

文法$G=\{E\to T|E+T,T\to F|T*F,F\to (E)|i\}$，消除左递归后得到：

$$\begin{aligned} E\to &TE'\\ E'\to &+TE'|\varepsilon\\ T\to &FT'\\ T'\to &*FT'|\varepsilon\\ F\to &(E)|i \end{aligned}$$

对输出串$i+i*i$的执行过程：

扩充的BNF

• $\{\alpha\}$表示$\alpha$的0到任意多次重复，即$\alpha^*$
• $\{\alpha\}_0^n$表示0次到n次重复，$\{\alpha\}_0^0=\{\alpha\}^0=\varepsilon$
• $[\alpha]$表示$\alpha$可有可无（即$\alpha|\varepsilon$）

文法G可以改写为：

$$\begin{aligned} E\to &T\{+T\}\\ T\to &F\{*F\}\\ F\to &i|(E) \end{aligned}$$

$i+i*i$的分析过程：

三、预测分析法

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

预测分析表

• 形式：$M[A,a]$矩阵，$A\in V_N$，$a\in V_T\cup\{\#\}$
• 内容：$A\to\alpha$或出错标志（空白）

例：文法$G=\{E\to T|E+T,T\to F|T*F,F\to (E)|i\}$，消除左递归后得到

$$\begin{aligned} E\to &TE'\\ E'\to &+TE'|\varepsilon\\ T\to &FT'\\ T'\to &*FT'|\varepsilon\\ F\to &(E)|i \end{aligned}$$

1. 构造FIRST集和FOLLOW集

FIRST集：

• $A\to a\ldots$，$a\in FIRST(A)$
• $A\to B\ldots$，$FIRST(B)\subset FIRST(A)$
• $A\to BC\ldots$，$B$可产生$\varepsilon$，$FIRST(C)\subset FIRST(A)$

FOLLOW集：

• $\#\in FOLLOW(S)$
• $S\to\ldots Aa\ldots$，$a\in FOLLOW(A)$
• $S\to\ldots AB\ldots$，$FIRST(B)-\varepsilon\subset FOLLOW(A)$
• $S\to\ldots A$，$FOLLOW(S)\subset FOLLOW(A)$
• $S\to\ldots AB$，$B$可以产生$\varepsilon$，$FOLLOW(S)\subset FOLLOW(A)$

	FIRST	FOLLOW
E	( i	) #
E'	+ ε	) #
T	( i	+ ) #
T'	* ε	+ ) #
F	( i	* + ) #

2. 构造预测分析表

• 横$V_T$与$\#$，纵$V_N$
• $a\in FIRST(A)$，$[A,a]$填对应产生式
• $A$可以产生$\varepsilon$，$a\in FOLLOW(A)$，$[A,a]$填$A\to\varepsilon$

	i	*	+	(	)	#
E	E->TE'			E->TE'
E'			E'->+TE'		E'->ε	E'->ε
T	T->FT'			T->FT'
T'		T'->*FT'	T'->ε		T'->ε	T'->ε
F	F->i			F->(E)

3. 预测分析过程

• 栈、输入串、归约
• 栈放$\#S$
• 根据栈顶与当前字符查表归约，产生式右部倒序入栈
• $[\#,\#]=acc$

栈	输入串	归约
#E	i+i*i#	E->TE'
#E'T	i+i*i#	T->FT'
#E'T'F	i+i*i#	F->i
#E'T'	+i*i#	T'->ε
#E'	+i*i#	E'->+TE'
#E'T	i*i#	T->FT'
#E'T'F	i*i#	F->i
#E'T'	*i#	T'->*FT'
#E'T'F	i#	F->i
#E'T'	#	T'->ε
#E'	#	E'->ε
#	#	acc

4. LL(1)文法

设有文法$G$，若它的任一产生式$A\to\alpha_1|\alpha_2|\ldots|\alpha_n$，均满足：

• $FIRST(\alpha_i)\cap FIRST(\alpha_j)=\varnothing$，其中$i\neq j$，$i,j=1,2,\ldots,n$
• 若$\alpha_i{\overset{+}{\Rightarrow}}\epsilon$，则$FIRST(\alpha_j)\cap FOLLOW(A)=\varnothing$，$j=1,2,\ldots,n$且$j\neq i$

则文法G称为LL(1)文法。

自上而下分析时，若当前输入字符为$a$，分析栈待匹配的非终结符为A，$A\to\alpha_1|\alpha_2|\ldots|\alpha_n$，则当

• $a\in FIRST(\alpha_i)$
• 若$\alpha_i{\overset{+}{\Rightarrow}}\epsilon$，$a\in FOLLOW(A)$

则$A\to \alpha_i$便是唯一与$a$匹配的产生式。即LL(1)文法中的两个条件保证了自上而下匹配的唯一性。

Note

预测分析表没有多重入口，则该文法是LL(1)文法。