编译原理学习笔记（八）~FIRST（）集和FOLLOW（）集的求法

FIRST（）

定义：

我的理解：对于一个X，求X的FIRST集合，就是在X 能够推导出来的 式子中的第一个终结符的集合。特殊情况：若X只能推出ε，那么就将ε加入FIRST集合

举例说明：

思路：FIRST集合可以按照 从下往上 的方法依次求出。
        对于F，我们可以发现，F–>(E)|id，意思就是说(E)|id就是F推导出来的式子，我们需要的FIRST(F)其实就是这个推导出来式子中的第一个非终结符。很明显，这里是 （和 id（注意这里竖线是 或 的意思）

∴ FIRST(F)={（，id }

        对于T，我们发现T→FT’，意思是：T推导出来的式子是FT’，这里求FIRST的时候就需要多考虑一下了。
首先，推导式中第一个是F，如果F推导出的式子中有终结符（FIRST(F)集合不为空或者没有ε），那么就把FIRST(F)中的元素加入FIRST(T)；如果FIRST(F)中含有ε,那么就得用同样的方法考虑FIRST(T’)

∴ FIRST(T)= FIRST(F)={（，id }

同理可得
最终FIRST集合就是：

变式：

变式解析：

FIRST()算法总结：

FOLLOW（）

定义：

我的理解：对于A，求FOLLOW(A)的意思就是：找出A后面跟着的第一个终结符 的集合。 与FIRST(A)的区别就是：FIRST(A)是在A推导出来的式子中找第一个终结符，而FOLLOW(A)则是直接在A后面找第一个终结符

举例说明：

思路：求FOLLOW()集合，一般都是从上往下依次求。
        对于FOLLOW(E)，首先E作为一个句型的最右符号（可以理解为最初推导的原符号），$ 一定是要加入FOLLOW(E)
∴ FOLLOW(E)={ $ }
然后我们需要找到E的后面是否含有终结符
所有的式子中，只有最后一个式子在推导式中可以找到E
F→(E)| id
可以看出，E后面 有个终结符： ）
∴ FOLLOW(E)={ $ ，）}
同理：
FOLLOW( E’ )={ $ ，) }

        而对于FOLLOW(T)，则相对于复杂一点了
推导式中有T的式子有：

• E→TE’
• E’→+TE’|ε

        对于第一个推导式，我们可以得出，T后面的第一个终结符可能出现中E’中，也就是E’的FIRST（）集合（这个应该不难理解吧），但是我们需要考虑一点，FIRST（E’）中是否含有ε，如果不含，则直接把FIRST（E’）加入FOLLOW(T)；如果含有，那么T后面的终结符其实就是E之后的第一个终结符，则就要把FOLLOW(E)加入FOLLOW(T)
        对于第二个推导式，用上面的方法同样计算
∴ FOLLOW( T)= {+ ，$， ) }
最终

变式：

变式解析：

算法总结：

总结

        开始学FIRST()和FOLLOW()的时候，真的真的是听不懂，后面同学给海轰说了一下，emm，还是有些东西不懂，特别是FOLLOW的求法，依然还是不会。后面在哔哩哔哩看了老师的讲解视频，茅塞顿开。（名校老师就是不一样，讲的通俗易懂，多听几次，自然就懂了）
        附上哈工大老师的FIRST、FOLLOW讲解视频

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/105248183