编译原理｜FIRST、FOLLOW、SELECT集超详细解读（含例题）

编译原理FIRST、FOLLOW、SELECT集超详细解读含例题在编译原理的自顶向下语法分析中FIRST、FOLLOW、SELECT三个集合是核心基石——它们是构造LL(1)分析表、判断文法是否为LL(1)文法的关键。很多同学刚开始接触时会被抽象的定义和推导规则难住今天就结合通俗解读、严谨规则和两道例题帮大家彻底吃透这三个集合的求法与应用。建议阅读顺序先吃透三个集合的核心定义与规则再跟随经典算术表达式例题实操之后用简单例题查漏补缺最后通过总结掌握LL(1)判定方法循序渐进高效吃透。一、核心概念详解定义通俗解读求法规则先明确三个集合的核心定位FIRST集看“开头”FOLLOW集看“后面”SELECT集看“选择哪条产生式”三者层层递进、相互关联。1. FIRST集首符号集定义对于任意一个文法符号串α可以是终结符、非终结符或它们的组合FIRST(α) 就是α能够推导出的所有可能串中第一个终结符的集合。如果α能推导出空串ε文中也写作varepsilon那么ε也在FIRST集中。通俗理解想象你是一个“预言家”站在一个非终结符比如E的门口你想知道它变身后第一眼能看到的终结符实际的字符是什么如果它能直接隐身变成空串ε那ε也要算上。就像看一本书的下一章你想知道这一章最先可能看到哪些关键线索终结符。求法规则迭代计算直到集合不再增大终结符如果X是终结符则FIRST(X) {X}自己就是自己的首符号。空产生式如果有X→ε则将ε加入FIRST(X)。非终结符推导对于产生式X→Y₁Y₂…Yₖ先把FIRST(Y₁)中除ε以外的所有元素加入FIRST(X)如果Y₁能推出ε则继续把FIRST(Y₂)中除ε以外的所有元素加入FIRST(X)以此类推如果Y₁、Y₂、…、Yₖ全都能推出ε那么把ε也加入FIRST(X)。✅ 核心要点FIRST集的关键是“穿透空串”非终结符推导时只要前面的符号能推空就继续往后找首符号。2. FOLLOW集后跟符号集定义对于非终结符AFOLLOW(A)是在文法的某个句型中紧跟在A后面的所有终结符的集合。注意FOLLOW集只针对非终结符且如果A可以是句型的最后一个符号输入结束符通常记作#也属于FOLLOW(A)。通俗理解FOLLOW集就像是给非终结符找一个“贴身保镖”。我们要找出在所有合法的句型中谁终结符有资格紧跟在这个非终结符的屁股后面。如果它可能出现在句子的末尾那么结束符#也是它的保镖。就像某个主要角色非终结符的戏份暂时告一段落后接下来可能紧接着出现哪些场景或人物终结符。求法规则迭代计算直到集合不再增大开始符号将结束符#加入文法开始符号S的FOLLOW(S)中开始符号的最后一定是结束符。一般情况A→αBβ如果B后面跟着符号串β则将FIRST(β)中除ε以外的所有元素加入FOLLOW(B)β的首符号就是B的保镖。结尾或后面能推空A→αB 或 A→αBβ且β⇒ε这意味着B后面可能什么都没有或者β消失后B就到了结尾。此时将FOLLOW(A)中的所有元素加入FOLLOW(B)A的保镖也是B的保镖。✅ 核心要点FOLLOW集的关键是“继承保镖”若后续符号能推空就继承前面非终结符的FOLLOW集元素。3. SELECT集选择符号集定义SELECT集是针对产生式的。对于产生式A→αSELECT(A→α)表示在语法分析过程中当我们处于非终结符A且当前输入的终结符属于这个集合时我们就应该选择使用A→α这条规则进行推导。通俗理解SELECT集是“行动指南”。当你在语法分析时如果当前站在非终结符A上且手里的输入字符属于某个产生式的SELECT集你就必须果断选择这条产生式进行推导不会出错。求法规则如果α不能推导出εSELECT(A→α) FIRST(α)直接取右部的首符号集。如果α能推导出ε即α⇒*εSELECT(A→α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。通俗解释如果α能变成空那么当输入符号既不在α的开头里又恰好是A后面可能跟的符号时我们就让A推出空串把匹配权交给后面的符号。✅ 核心要点SELECT集的关键是“区分空与非空”非空右部看FIRST集空右部看FOLLOW集。掌握了三个集合的定义与规则后我们通过经典算术表达式文法实操把理论落地手把手教你推导过程帮你巩固核心知识点。二、经典例题演练深度实操为了帮大家巩固三个集合的求法我们选用编译原理中经典的算术表达式文法作为例题。这个文法不仅结构清晰还包含了空产生式ε非常适合用来练习。我们先对文法进行消除左递归处理得到以下产生式#代表输入结束符E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | i1. 求FIRST集首符号集步骤提示从无空串依赖的基础非终结符开始逐步推导依赖它的非终结符重点关注空产生式的处理。F的FIRST集看F的产生式F→(E) | i。它要么以(开头要么以i开头且不能推空。FIRST(F) { (, i }T’的FIRST集看T’→F T’ | ε。它要么以开头要么直接变空。FIRST(T’) { *, ε }T的FIRST集看T→F T’。T的开头取决于F因为F不能变空所以T的开头就是F的开头。FIRST(T) FIRST(F) { (, i }E’的FIRST集看E’→T E’ | ε。要么以开头要么变空。FIRST(E’) { , ε }E的FIRST集看E→T E’。E的开头取决于TT不能变空所以E的开头就是T的开头。FIRST(E) FIRST(T) { (, i }2. 求FOLLOW集后跟符号集步骤提示先确定开始符号的FOLLOW集再根据产生式中非终结符的位置结合“继承保镖”规则逐步推导。FOLLOW(E)E是开始符号所以必须有结束符#另外在产生式F→(E)中E的后面紧跟着)所以)也是FOLLOW(E)的元素。FOLLOW(E) { ), # }FOLLOW(E’)在E→T E’中E’处在末尾意味着E’的保镖就是E的保镖E’结束后E也就结束了。FOLLOW(E’) FOLLOW(E) { ), # }FOLLOW(T)在E→T E’中T后面跟着E’根据规则E’的FIRST集去掉ε要加入FOLLOW(T)即又因为E’可以变成ε所以E的保镖), #也要加入。FOLLOW(T) { , ), # }FOLLOW(T’)在T→F T’中T’在末尾所以它继承T的所有保镖。FOLLOW(T’) FOLLOW(T) { , ), # }FOLLOW(F)在T→F T’中F后面跟着T’T’的FIRST集去掉ε里有*加入FOLLOW(F)又因为T’可以变成ε所以T的保镖, ), #也要全部加入。FOLLOW(F) { *, , ), # }3. 求SELECT集选择符号集步骤提示先判断产生式右部是否能推空再根据规则选择FIRST集或FOLLOW集明确推导时的选择依据。E→T E’右部不能推出ε直接取FIRST(TE’)。SELECT(E→T E’) { (, i }E’→T E’右部不能推出ε直接取FIRST(TE’)。SELECT(E’→T E’) { }E’→ε右部就是ε取FOLLOW(E’)。SELECT(E’→ε) { ), # }通俗解释当你在E’处发现后面的输入是)或者已经结束了#说明E’这里不需要再匹配了直接让它变空隐身即可。T→F T’右部不能推出ε直接取FIRST(FT’)。SELECT(T→F T’) { (, i }T’→*F T’右部不能推出ε直接取FIRST(FT’)。SELECT(T’→F T’) { * }T’→ε右部就是ε取FOLLOW(T’)。SELECT(T’→ε) { , ), # }F→(E)右部不能推出ε直接取FIRST((E))。SELECT(F→(E)) { ( }F→i右部不能推出ε直接取FIRST(i)。SELECT(F→i) { i }经典例题侧重深度实操下面补充一道简单例题步骤更简洁适合入门巩固帮你查漏补缺强化对规则的记忆。三、基础例题巩固入门适配为了让大家进一步熟悉规则再补充一道简单文法的演练步骤更简洁适合入门巩固。假设有如下简单文法 S→AB A→aA | ε B→b1. 求FIRST集FIRST(B)B→b所以FIRST(B) {b}FIRST(A)A→aA加入aA→ε加入ε。所以FIRST(A) {a, ε}FIRST(S)S→AB。先看FIRST(A)加入a因为A能推ε继续看FIRST(B)加入b。所以FIRST(S) {a, b}2. 求FOLLOW集FOLLOW(S)S是开始符号加入#。所以FOLLOW(S) {#}FOLLOW(A)找A在产生式右部的位置在S→AB中A后面跟着B。将FIRST(B)中非空元素加入FOLLOW(A)即加入b。所以FOLLOW(A) {b}FOLLOW(B)在S→AB中B在最后。将FOLLOW(S)加入FOLLOW(B)。所以FOLLOW(B) {#}3. 求SELECT集SELECT(A→aA)aA不能推ε等于FIRST(aA)所以SELECT(A→aA) {a}SELECT(A→ε)ε能推ε等于(FIRST(ε) - {ε}) ∪ FOLLOW(A) ∅ ∪ {b}所以SELECT(A→ε) {b}SELECT(B→b)等于FIRST(b)所以SELECT(B→b) {b}SELECT(S→AB)等于FIRST(AB)所以SELECT(S→AB) {a, b}四、总结与应用4.1 核心知识点总结通过这两道例题你会发现求这三个集合的核心就在于对空串ε的处理记住三句话即可FIRST集遇到能推空的符号要“穿透”它继续往后看。FOLLOW集如果后面的符号能推空要把自己的保镖分给它。SELECT集能推空的产生式它的SELECT集由FOLLOW集决定不能推空的由FIRST集决定。4.2 LL(1)文法判定应用落地 判定规则看同一个非终结符的多个产生式的SELECT集是否有交集。如果所有非终结符的任意两个产生式的SELECT集都没有交集那么这个文法就是LL(1)文法。这三个集合的核心应用就是判断一个文法是不是LL(1)文法——LL(1)文法的精髓的是“向前看一个输入符号就能明确选择哪条产生式推导不产生二义性”。比如经典例题中E’的两个产生式SELECT集分别是{}和{), #}完全没有交集简单例题中A的两个产生式SELECT集分别是{a}和{b}也没有交集所以这两个文法都是LL(1)文法。最后提醒FIRST、FOLLOW、SELECT集的推导一定要遵循“迭代计算直到集合不再增大”的原则尤其是FOLLOW集常常需要反复推导才能得到最终结果。多练两道例题就能熟练掌握啦