对编译原理中First、Follow、Select集的一些不算太抽象的理解

对编译原理中First、Follow、Select集的一些不算太抽象的理解

刚开始接触的时候非常懵，不知道是在算什么，在干什么，去询问大佬和老师是否有更生动的理解方式，但是他们都达成一致说反向理解(然而我还是没听懂)

趁着写课后作业的机会再翻了翻书本，看了书上例题，进行了预习回顾，研究了一些个人认为不算太差的适合普通人类大学牲理解的角度，在此记录

下面以一道例题作为例子，核心是通过一个树状推导结构来理解！

有一说一，可以不看上面这图，直接看下面的推导图即可，重在理解！

我们之前学过推导和归约，我们这里先用推导，画出一个推导的树状结构

1. 以S的First为例：

图中红色的非终结符就是S的First集，即{ε,a,b}

来想一想First集含义：First(S)是指S能经过多步得到的左边第一个终结符

当然，既然是终结符，你就会想，有个特殊的终结符ε，需要对他特殊处理吗？

答：暂时放在这里，First集是可以包含ε的，就如上面S的First集里面有空一样，目前先保留着

2. 下面以另一题的Follow(A)分析为例：

你可以先去书本上看着规则啃一啃，然后会发现，Follow都是看产生式的右边该字母后面跟的是啥终结符，这一点理解很关键，意思就是：如果在上面这颗树中找Follow(A)，那么按照规则，就是找到了A后面的B(这符合Follow的含义)，然后取First，即First(B).

当然，你可能会想，要是A的是最后一个符号呢？它后面没有上图一样的B，该怎么办？

答：按照书上，继续对产生式左侧求Follow，也即求Follow(S)

总的来说：

• First(A)就是取A能产生的、第一位是终结符的集合
• Follow(A)就是取产生式右边紧跟在A后面的那个符号的First集

接下来是重量级Select集合

可以这么说，前面的First和Follow集都是为Select集做铺垫的，他们只是工具，目的只是为了求Select集，因此前面求得基本上不会全用上！！！

Select集含义：找出产生式能推导出的非终结符
我觉得像是对一条产生式能力的评估，找出一条产生式能够有多大的"潜力"(能推导出哪些终结符)，这就是所谓“Select集”正在Select的东西

那么我们来想一想，Select集怎么依据前面的First和Follow集得到呢？
或者说，一条产生式的“潜力”怎么通过First和Follow集得到？

回顾一下前面的总结：

First(A)就是取A能产生的、第一位是终结符的集合

Follow(A)就是取产生式右边紧跟在A后面的那个符号的First集

例如有产生式A=>α，那么它的“潜力”有多大？

1. 我们肯定会想：如果说，α可以在不断地左推能推导到一个第一个符号为终结符的串，那就可以说这个产生式具有这样的“潜力”
2. 但是，如果α走了什么歪门邪道，在命运的交叉路口选错了方向，最后得到了一整个空串，那么该怎么鉴定它的“潜能”呢？这时，说明A选择α是一个错误的选择，A会寻找自己的Follow，因为根据这条产生式走下去是死路一条
3. 不管怎么样，Select核心就是找这条产生式能产生的第一个终结符，可以理解为，都是找一个First，但是First找到空的话，就用到Follow，寻找空之后的第一个终结符（当然要是空的话继续找），Follow本质也是找第一个非空的终结符，只是前面的符号推出的都是空串，这个使命就落到了后面的符号身上（即Follow）

​ 于是，这时我才发现大佬和老师为什么说逆向理解了orz，其实归根到底都是为了研究一条产生式能变出什么花来，我们要的是产生式能推出的第一位是终结符的集合，来衡量一条产生式的“潜力”，然后编译器其实就是根据这种“潜力”来选择合适的产生式，进行推导化简的。
​ 其实是先有这个需求，然后生出了“如何合理选择合适产生式”的问题，于是有了Select集，目的是取产生式能推出来的第一位终结符，在之后就有了First集，但是若在First集中遇到空，说明第一个符号“白干了”，一点“潜力”都没有，于是要用到Follow集，也就是相应的“第一个符号不行，就找第二个”，由于第一个符号推出空，那么“整个产生式能推出的第一个终结符”就会由之后的符号的First确定！也就是相应的“第一个符号不行，就找第二个”，由于第一个符号推出空，那么“整个产生式能推出的第一个终结符”就会由之后的符号的First确定！

相信认真读完的你，结合书上的例题，写一写，相信会有不少的收获和更好的理解~