小卷毛奶爸
如何在LL(1)文法中计算fowllow集的具体步骤？
在LL(1)文法中计算follow集时，有哪些关键细节会影响最终结果的准确性呢？
作为历史上今天的读者，我在学习编译原理时发现，follow集的计算是构建LL(1)分析表的基础，很多人觉得难，其实是没理清步骤和逻辑。下面就详细说说具体该怎么做。
第一步：明确follow集的核心含义
首先得知道，follow集是针对非终结符而言的，指的是在所有可能的句型中，紧跟在某个非终结符后面的所有终结符，还包括句子结束符#。
比如在文法G中，有产生式S→aAb，那么对于非终结符A来说，b就可能是它follow集中的元素。那为什么要包含#呢？因为当非终结符处于句子末尾时，后面就没有其他符号了，这时候#就代表句子结束，自然要算进去。
第二步：准备工作——掌握first集的计算
为什么计算follow集前要先搞定first集？因为很多时候，follow集的推导需要借助first集的结果。
first集简单说就是某个符号（终结符或非终结符）能推导出的所有开头终结符的集合。举个例子，如果有产生式B→cD|ε，那么B的first集就是{c, ε}（ε表示空串）。
如果连first集都算不对，后续follow集的计算就像建房子没打好地基，肯定会出问题。
第三步：具体计算步骤
1. 初始化操作
- 对于文法的开始符号，要把句子结束符#加入它的follow集。这是因为开始符号后面可能就是整个句子的结束，这一点是固定的，必须记住。
- 其他非终结符的follow集初始化为空，后续再逐步添加元素。
2. 根据产生式推导
假设有产生式A→αBβ，其中α、β是文法符号串，B是某个非终结符。这时该怎么处理呢？ - 先计算β的first集。如果β的first集中不包含空串，那么就把β的first集中所有终结符加入B的follow集。 - 要是β的first集包含空串，那就不仅要把β的first集中的终结符（除了空串）加入B的follow集，还要把A的follow集中的元素也加入B的follow集。为什么要这样？因为当β推导出空串时，B后面就相当于跟着A后面的符号了，所以A的follow集自然要传递给B。
3. 处理特殊情况
当产生式是A→αB（也就是β为空）时，直接把A的follow集中的所有元素加入B的follow集。这是因为B后面没有其他符号，它的后续符号就和A的后续符号一样。
| 产生式示例 | 处理方式 | 结果 | | --- | --- | --- | | S→aBc | 计算c的first集（就是{c}），且c不能推导出空串，所以把{c}加入B的follow集 | B的follow集新增{c} | | S→AB | B后面没有符号，所以把S的follow集加入B的follow集 | 若S的follow集有#，则B的follow集加入# |
第四步：反复迭代直至结果稳定
计算follow集不是一次性就能完成的，需要多次循环处理所有产生式，直到所有非终结符的follow集不再有新元素加入为止。
为什么要反复迭代？因为有些产生式之间是相互关联的，一次处理可能无法涵盖所有情况。比如有产生式A→BC和B→ε，第一次处理可能只加入了部分元素，第二次处理才能把C的相关元素传递给A。
常见错误及避免方法
- 忘记将#加入开始符号的follow集，这会导致句子结束的情况被忽略，影响后续分析。
- 处理包含空串的产生式时，漏传follow集元素。比如前面提到的β含空串的情况，要是只加了β的first集，没加A的follow集，结果就会不完整。
- 没有迭代到稳定状态就停止计算，导致部分该加入的元素没有被包含进去。
实际案例演示
假设文法G如下： - S→AB - A→a|ε - B→b
我们来计算各非终结符的follow集： 1. 开始符号是S，所以初始化follow(S) = {#}。 2. 看产生式S→AB：这里α是ε，B是当前非终结符，β是空。所以把S的follow集加入B的follow集，即follow(B) = {#}。 3. 再看产生式A→a|ε和S→AB：对于A来说，产生式S→AB中，β是B。B的first集是{b}，且B不能推导出空串，所以把{b}加入A的follow集，即follow(A) = {b}。 4. 检查是否有遗漏，多次确认后，各follow集就是最终结果。
作为学习编译原理的人，我觉得掌握follow集的计算，关键在于理解每一步的逻辑，而不是死记硬背规则。在实际编写简单的语法分析器时，这些步骤都是基础，一步错就可能导致整个分析过程出错。根据我接触到的一些编程爱好者反馈，只要按照步骤慢慢来，多练习几个例子，就能熟练掌握，毕竟它的规则是很明确的，只是需要一点耐心而已。