FIRST 集合（首符号集）学习笔记

文章目录FIRST 集合首符号集学习笔记一、这个知识点到底在干嘛二、前置概念必须先搞清楚三、FIRST 集合的核心操作四、特殊情况空串 ε五、实战演示六、避坑指南七、与其他集合的关系预览八、做题流程总结FIRST 集合首符号集学习笔记一、这个知识点到底在干嘛FIRST 集合解决的是一个非常朴素的问题从某个符号出发推导出来的句子第一个字可能是谁把所有可能的第一个字收集起来就是 FIRST 集合。二、前置概念必须先搞清楚概念大白话例子终结符最终成品不能再变的符号a,[,],,非终结符半成品/占位符还需要继续替换S,L产生式规则造句规则箭头左边能变成右边S → a推导按照规则一步步替换的过程S → [L] → [S] → [a]三、FIRST 集合的核心操作一句话口诀盯着箭头右边最左边的符号看。具体分两种情况情况 1箭头右边第一个是终结符直接把这个终结符抓进 FIRST 集合游戏结束。例S → a第一个是终结符a所以a ∈ FIRST(S)。情况 2箭头右边第一个是非终结符需要去查那个非终结符的 FIRST 是什么递归查找。例A → Bc第一个是B非终结符那就去看FIRST(B)里有什么把它们都加进FIRST(A)。四、特殊情况空串 ε如果某个非终结符能推导出空串即可以隐身消失那么当前符号不算继续往后看下一个符号。如果后面的也能消失就再往后看直到碰到一个不能消失的终结符为止。类比排队时前面的人突然消失了你就得看再后面那个人是谁。五、实战演示文法 G[S]S → [L] | a L → L, S | S求 FIRST(S)看 S 的产生式S → a箭头右边第一个是终结符a→a ∈ FIRST(S)S → [L]箭头右边第一个是终结符[→[ ∈ FIRST(S)结果FIRST(S) { a, [ }常见错误把]也算进去]在[L]中排在最后面是车尾FIRST 只管排头兵车尾不归它管]属于 FOLLOW 集合的管辖范围六、避坑指南FIRST 只管第一个字符不管中间和末尾的字符。看到产生式箭头右边眼睛只盯最左边那个符号。终结符直接收录非终结符才需要递归查找。后面的符号除非前面的都能变空ε否则一律不看。左递归如L → L, S不影响 FIRST因为递归展开后最左边的符号还是由基础情况决定的。七、与其他集合的关系预览集合管什么口诀FIRST推导出的句子的第一个终结符看排头兵FOLLOW某个非终结符后面紧跟的终结符看屁股后面SELECT决定用哪条产生式的依据FIRST FOLLOW 的组合八、做题流程总结求 FIRST(X) 1. 找出 X 的所有产生式 2. 对每条产生式看箭头右边第一个符号 - 是终结符 → 直接加入 FIRST(X) - 是非终结符 → 递归求它的 FIRST加入 FIRST(X) - 能推导出 ε → 继续看第二个符号重复上述步骤 3. 所有产生式都看完收集完毕本质就是FIRST 集合 从某个符号出发所有可能推导出的句子中站在最前面的终结符的集合。记住排头兵三个字这章的题就是送分题。