FIRST集构造对于一条产生式:S->…
若右边第一个符号是终结符或者ε,则 将其加入FIRST(S)
若右边第一个符号是非终结符,则将其FIRST集加入FIRST(S)
若右边第一个符号是非终结符,且随后紧跟多个非终结符,这是判断是否有ε
若第i个非终结符有ε集,则可将i+1个非终结符去除ε的FIRST集加入FIRST(S)
若所有非终结符都能够推导出ε,则将ε也加入FIRST(S)
e.g 若给出G(S)如下
12345S->ABCDA->a|εB->b|εC->cD->d
则FIRST(S)= a,b,c
FOLLOW集构造
将所有产生式的候选式的非终结符都找到,定位到求解的FOLLOW集的非终结符的位置,从当前位置挨个检查
先检验这个非终结符的右边有无别的符号,例如A->aBC,求FOLLOW(B)时,其右侧有非终结符C的
将右边符号的FIRST集中非空符号加入当前符号的FOLLOW集,若右边符号FIRST含有ε,则将FOLLOW(A)也加入FOLLOW(B)
若右边没有符号了,例如这里的 C,那么可以将 FOLLOW(A)中的元素全部加入到 FOLLOW(C)中
断当前符号是不是文法的开始符号,比如 G[A] 中的非终结符 A 就是 G[A] 文法的开始符号,如果是的话就将“#”也加入到 FOLLOW集中去
e.g 若给出文法如下
123E->E+T|TF->(E)|iT->F|T*E
FIRST
FOLLOW
E
( i
# ) +
F
( i
# ) + *
T
( i
# ) + *
预测表的构造首先构造出预测分析表的第一行与第一列,第一行为文法出现的所有终结符以及‘#’(注意:没有 ε ,因为 Follow 集不含 ε),第一列为文法出现的所有非终结符
对文法G的每个产生式A->α 执行如下步骤:
对每个a∈First(α),把 A->α 加入M[A,a]
若 ε∈First(α),则对任何b∈Follow(A) ,把 A-> ε加至M[A,b]中
对如下文法
123S->AaS|BbS|dA->aB->ε|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