在消除LL(1)文法的回溯时,要用到两个与文法有关的函数:
符号串α的开始符号集合FIRST(α)
非终结符A的后继符号集合FOLLOW(A)
计算FIRST和FOLLOW集合的算法是非常简单的,我实现了一下FIRST集合,FOLLOW集合懒得实现了,因为算法虽然简单,但相关数据结构的存储和操作比较繁琐,如果利用事先封装好的集合数据类型则比较容易.

约定用法:
α: 字符串
a :终结符
A,B,P:非终结符
ε :空串
$:输入结束标记
... :任意字符串

FIRST集合算法:
先计算所有非终结符的FIRST集合,再求任意串的FIRST集合就非常容易了.
一般形式:
对于产生式A->αx...(α为满足α=>^*ε的右部最长子串,α可以不存在)
若x=a    : a加入到FIRST(A)
若x=B    : FIRST(B)加入到FIRST(A)
若x不存在: ε(空串)加入到FIRST(A)

Follow集合算法:
注意:α包括α不存在的情况.(α=>^*ε),而且此处的α不必像FIRST集合算法的α一样,满足最长子串
对于产生式P->...A       : A为句型最右符号,$(输入结束标记)加入到FOLLOW(A)
对于产生式P->...Aα     : FOLLOW(P)加入到FOLLOW(A)
对于产生式P->...Aαa... : a加入到FOLLOW(A)
对于产生式P->...AαB... : FIRST(B)加入到FOLLOW(A)

可以看到:
(1)FOLLOW集合的计算要依赖于FIRST集合
(2)FIRST集合的计算:清除产生式右部左端的"空串"α,再一步处理即可
   FOLLOW集合的计算:要对产生式右部的每一个非终结符A进行处理,需要多次执行相同的算法过程.
(3)需要事先计算每个非终结符A,A=>^*ε是否成立,这个也很容易,略.