构造FIRST集、FOLLOW集、 LL(1)预测分析表

FIRST集构造

对于一条产生式：S->…

1. 若右边第一个符号是终结符或者ε，则 将其加入FIRST(S)
2. 若右边第一个符号是非终结符，则将其FIRST集加入FIRST(S)
3. 若右边第一个符号是非终结符，且随后紧跟多个非终结符，这是判断是否有ε
   1. 若第i个非终结符有ε集，则可将i+1个非终结符去除ε的FIRST集加入FIRST(S)
   2. 若所有非终结符都能够推导出ε，则将ε也加入FIRST(S)

e.g 若给出G(S)如下

S->ABCD
A->a|ε
B->b|ε
C->c
D->d

则FIRST(S)= a,b,c

FOLLOW集构造

1. 将所有产生式的候选式的非终结符都找到，定位到求解的FOLLOW集的非终结符的位置，从当前位置挨个检查
2. 先检验这个非终结符的右边有无别的符号，例如A->aBC，求FOLLOW(B)时，其右侧有非终结符C的
   1. 将右边符号的FIRST集中非空符号加入当前符号的FOLLOW集，若右边符号FIRST含有ε，则将FOLLOW(A)也加入FOLLOW(B)
   2. 若右边没有符号了，例如这里的 C，那么可以将 FOLLOW(A)中的元素全部加入到 FOLLOW(C)中
3. 断当前符号是不是文法的开始符号，比如 G[A] 中的非终结符 A 就是 G[A] 文法的开始符号，如果是的话就将“#”也加入到 FOLLOW集中去

e.g 若给出文法如下

E->E+T|T
F->(E)|i
T->F|T*E

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

预测表的构造

首先构造出预测分析表的第一行与第一列，第一行为文法出现的所有终结符以及‘#’（注意：没有 ε ，因为 Follow 集不含 ε），第一列为文法出现的所有非终结符

对文法G的每个产生式A->α 执行如下步骤：

1. 对每个a∈First(α)，把 A->α 加入M[A,a]

2. 若 ε∈First(α)，则对任何b∈Follow(A) ,把 A-> ε加至M[A,b]中

对如下文法

S->AaS|BbS|d
A->a
B->ε|c

举个例子，对于第一个产生式，FIRST(AaS)={a}，则将S->AaS加入到[S,a]

	a	b	c	d
S	S->AaS
A
B

而对于B->ε，计算FOLLOW(B)中的所有元素将其加入。FOLLOW(B) = { b }，所以将产生式加入到M[B,b]

	a	b	c	d
S	S->AaS
A
B		B->ε

最后得到的完整LL(1)分析表

	a	b	c	d
S	S->AaS	S->BbS	S->BbS	S->d
A	A->a
B		B->ε	B->c