LL(1)文法

自顶向下构建语法分析树，根节点是起始符号S，每个中间结点表示堆某个非终结符应用某个产生式进行推导。叶节点是词法单元流，仅包含终结符和EOF($)。

LL(1)总是选择最左边的非终结符进行展开，从左到右读入词法单元

递归下降

递归下降的典型实现：

void A(){
	选择一个A产生式,A -> X1X2...Xk;
	for(i = 1 to k) {
		if(Xi是非终结符)
			Xi();
		else if(Xi等于当前输入符号a)
			读入下一个输入符号;
		else
			error();
	}
}

预测分析表

预测分析表指明了每个非终结符在面对不同的词法单元或文件结束符时，该选择哪一个产生式或者报错。

例如对于以下的产生式

• $S\rightarrow F$
• $S\rightarrow (S+F)$
• $F\rightarrow a$

可以产生以下的预测分析表

如果文法G的预测分析表是无冲突的，则G是LL(1)文法。对于当前选择的非终结符，仅根据输入中当前的词法单元即可确定需要使用哪条产生式。

计算

$First(\alpha)$是可从$\alpha$推导得到的句型的首终结符号的集合

对于任意的$\alpha\in (N\cup T)^*$，

$Follow(A)$是可能在某些句型中紧跟在$A$右边的终结符的集合

对于任意的非终结符$A\in N$,

$First(\alpha)$的计算方法

1. procedure $First(X)$
   1. if $X\in T$ then 规则1：X是终结符
      1. $First(X)=X$
   2. for $X\rightarrow Y_1Y_2…Y_k$ do 规则2：X是非终结符
      1. $First(X)\leftarrow First(X)\cup {First(Y_1)\backslash{\epsilon}}$
      2. for $i\leftarrow 2$ to $k$ do
         1. if $\epsilon \in L(Y_1…Y_{i-1})$ then
            1. $First(X)\leftarrow First(X)\cup {First(Y_i)\backslash{\epsilon}}$
      3. if $\epsilon \in L(Y_1…Y_{k})$ then 规则3：X可推导出空串
         1. $First(X)\leftarrow First(X)\cup {\epsilon}$

不断应用上面的规则，直到每个$First(X)$都不再变化

$Follow(X)$的计算方法

1. procedure $Follow(X)$
   1. for $X$是开始符号 do 规则1：X是开始符号
      1. $Follow(X)\leftarrow Follow(X)\cup {$}$
   2. for $A\rightarrow \alpha X$ do 规则2：X是某产生式右部的最后一个符号
      1. $Follow(X)\leftarrow Follow(X)\cup Follow(A)$
   3. for $A\rightarrow \alpha X\beta$ do 规则3：X是某产生式右部中间的一个符号
      1. $Follow(X)\leftarrow Follow(X)\cup (First(\beta)\backslash {\epsilon})$
      2. if $\epsilon \in First(\beta)$ then
         1. $Follow(X)\leftarrow Follow(X)\cup Follow(A)$

预测分析表的产生则是根据以下规则，在表格$[A,t]$中填入生成式$A\rightarrow \alpha$（编号）

1. $t\in First(\alpha)$
2. $\alpha \Rightarrow^* \epsilon\and t\in Follow(A)$在无冲突的文法中即$\epsilon\in First(\alpha)\and t\in Follow(A)$