：我是如何通过一个语法分析实验彻底搞懂First集与Follow集的)
从PL/0到LL(1)我是如何通过一个语法分析实验彻底搞懂First集与Follow集的第一次看到LL(1)文法这个词时我的反应和大多数编译原理初学者一样——满脑子问号。那些晦涩的定义、抽象的数学符号还有教授口中反复强调的First集、Follow集就像一堵高墙挡在面前。直到在PL/0表达式文法的实验里当我把课本上的BNF规则变成实际可运行的代码时所有的概念碎片突然拼接成了一幅完整的图景。这篇文章就是记录这段从困惑到顿悟的旅程。1. 为什么我们需要First和Follow集记得刚开始学编译原理时最让我头疼的就是这两个概念。书上说它们是预测分析的基础但为什么要预测预测什么直到动手实现递归下降分析器时我才真正理解它们的意义。想象你正在编写一个计算器程序需要解析像35*2这样的表达式。当看到数字3时程序应该立即知道这是一个项(term)的开始还是需要先处理可能的正负号这就是First集的用武之地——它告诉我们每个语法规则可能最先出现的终结符号。而Follow集解决的是另一个关键问题当某个非终结符可以推导出空串(ε)时我们需要知道后面可能跟随什么符号。比如在解析a*(bc)时遇到右括号)意味着当前因子的解析可以结束因为)在Follow集中。关键认知转折点First集解决从哪里开始的问题Follow集解决到哪里结束的问题两者共同确保分析器在每一步都能做出确定性的选择2. PL/0表达式文法的实战拆解让我们以经典的PL/0表达式文法为例这是许多编译原理实验的首选案例表达式 :: [|-]项{加法运算符 项} 项 :: 因子{乘法运算符 因子} 因子 :: 标识符|无符号整数| ( 表达式 )2.1 手算First集的全过程计算First集有一套系统的方法但初次接触时很容易漏掉细节。以因子为例Y - SFirst(Y)包含First(S)即所有标识符Y - N加入First(N)即所有数字Y - ( B )加入左括号(最终得到First(Y) {标识符, 数字, (}这个过程中最容易犯的错误是忘记处理产生式右部开头是非终结符的情况忽略ε产生式的影响没有递归计算嵌套的First集2.2 Follow集计算的陷阱与技巧Follow集的计算更微妙。以项(X)为例我们需要考察所有包含X的产生式在B - JX(JX)|X(JX)中X后面直接跟)时)加入Follow(X)X后面跟/-时这些运算符加入Follow(X)在Y - (B)中当B推导出X时Follow(B)的)也要加入Follow(X)常见错误包括漏掉产生式末尾的情况忘记处理递归嵌套混淆First和Follow的传播规则3. LL(1)文法的三大检验标准判断一个文法是否是LL(1)的需要验证三个关键条件3.1 消除左递归原始PL/0文法已经满足这一点。左递归会产生无限循环的风险比如如果写成表达式 :: 表达式 项 /* 错误左递归 */递归下降分析器会陷入无限调用。改造方法是用右递归表达式 :: 项 { 项} /* 正确 */3.2 First集不相交对于每个非终结符A所有A产生式的First集必须两两不相交。例如A - aB | bC 是OK的 (First(aB){a}, First(bC){b}) A - aB | aC 就不是LL(1) (冲突的First集{a})PL/0的表达式文法完美满足这一条件。3.3 ε产生式的特殊处理如果有A - ε产生式则First(A)和Follow(A)必须不相交。PL/0文法中没有ε产生式所以这一条自动满足。4. 从理论到代码递归下降的实现艺术理解了这些概念后实现递归下降分析器就水到渠成了。以下是核心代码片段// 因子分析 void factor() { if (current_token IDENTIFIER || current_token NUMBER) { advance(); } else if (current_token LPAREN) { advance(); expression(); if (current_token ! RPAREN) { error(缺少右括号); } advance(); } else { error(非法的因子开始); } } // 项分析 void term() { factor(); while (current_token TIMES || current_token SLASH) { advance(); factor(); } } // 表达式分析 void expression() { if (current_token PLUS || current_token MINUS) { advance(); } term(); while (current_token PLUS || current_token MINUS) { advance(); term(); } }每个函数都严格对应文法中的一个非终结符函数内部的决策完全基于First集和Follow集的知识。比如在expression()中我们检查/-是因为它们在First(expression)中而在term()的while循环中我们检查*//是因为它们在Follow(term)中。5. 常见错误模式与调试心得在实验过程中我遇到了几乎所有可能的错误类型这些经验或许对你更有价值5.1 First集计算不完整症状分析器在某些合法输入上意外报错原因漏掉了某个产生式的First元素修复系统地检查每个产生式特别是嵌套情况5.2 Follow集传播错误症状分析器过早终止或跳过有效输入原因没有正确处理产生式链中的Follow传播修复画出所有产生式引用关系图确保Follow正确传递5.3 递归终止条件缺失症状程序栈溢出原因没有为递归函数设置明确的终止条件修复确保每个递归函数都有基于First/Follow集的终止检查6. 超越实验这些知识在实际编译器中的应用虽然PL/0是个教学用的小语言但其中的原理直接适用于现代编程语言。比如Python的运算符优先级正是通过类似PL/0的层次化文法实现的Java的类型解析使用First/Follow集解决语法歧义C的模板语法复杂的嵌套结构需要精确的LL(k)分析理解这些基础概念后再看真实编译器的源码如GCC的parser部分会变得容易很多。你会认出那些递归下降的函数结构发现First/Follow集的影子无处不在。7. 进阶思考当文法不是LL(1)时怎么办不是所有有用的文法都天然满足LL(1)条件。面对这种情况我们有几种选择文法改造提取左公因子消除左递归引入新的非终结符使用更强大的分析器LL(k)分析器前瞻更多符号LR分析器自底向上处理更复杂的文法容忍一定程度的回溯某些现代解析器如PEG允许有限回溯在PL/0实验中我有意尝试修改原始文法让它违反LL(1)条件然后观察分析器如何失败。这种破坏性测试极大地加深了我的理解。8. 工具推荐从手算到自动化虽然手算First/Follow集是必修课但在实际项目中我们会使用工具# 使用ANTLR生成解析器 antlr4 YourGrammar.g4 javac YourGrammar*.java grun YourGrammar rule -gui input.txt或者用Python的PLY库import ply.yacc as yacc # 定义文法规则 def p_expression_plus(p): expression : expression PLUS term p[0] p[1] p[3]这些工具背后仍然运用着First/Follow集的原理只是自动化了计算过程。理解底层机制能帮助你更好地使用它们并在出现问题时有效调试。9. 实验之外的收获计算思维的培养这个实验的价值远不止于掌握某个特定算法。通过反复推敲First/Follow集我培养了几种关键能力系统性思维将大问题分解为可管理的子问题精确性思维每个符号、每个集合都必须准确无误调试思维通过失败案例反向理解理论约束这些能力在后续学习操作系统、数据库等课程时都发挥了重要作用。编译原理之所以被称为CS的明珠正是因为这种思维训练的价值。10. 给后来者的建议如果你正在学习编译原理以下建议可能帮到你一定要动手实现概念在代码中才会真正具象化从小例子开始PL/0这样的微型语言是理想起点可视化分析过程画语法树、跟踪函数调用栈与他人讨论不同视角能发现你忽略的细节不要惧怕数学符号它们最终都会对应到具体的代码逻辑在完成这个实验后的某天当我阅读《Compilers: Principles, Techniques, and Tools》龙书中关于LL(1)的章节时突然发现那些曾经晦涩的数学描述变得异常清晰。那一刻我意识到真正的理解不是来自被动阅读而是来自将理论付诸实践的完整过程。
从PL/0到LL(1)：我是如何通过一个语法分析实验彻底搞懂First集与Follow集的
发布时间：2026/6/7 5:35:42
从PL/0到LL(1)我是如何通过一个语法分析实验彻底搞懂First集与Follow集的第一次看到LL(1)文法这个词时我的反应和大多数编译原理初学者一样——满脑子问号。那些晦涩的定义、抽象的数学符号还有教授口中反复强调的First集、Follow集就像一堵高墙挡在面前。直到在PL/0表达式文法的实验里当我把课本上的BNF规则变成实际可运行的代码时所有的概念碎片突然拼接成了一幅完整的图景。这篇文章就是记录这段从困惑到顿悟的旅程。1. 为什么我们需要First和Follow集记得刚开始学编译原理时最让我头疼的就是这两个概念。书上说它们是预测分析的基础但为什么要预测预测什么直到动手实现递归下降分析器时我才真正理解它们的意义。想象你正在编写一个计算器程序需要解析像35*2这样的表达式。当看到数字3时程序应该立即知道这是一个项(term)的开始还是需要先处理可能的正负号这就是First集的用武之地——它告诉我们每个语法规则可能最先出现的终结符号。而Follow集解决的是另一个关键问题当某个非终结符可以推导出空串(ε)时我们需要知道后面可能跟随什么符号。比如在解析a*(bc)时遇到右括号)意味着当前因子的解析可以结束因为)在Follow集中。关键认知转折点First集解决从哪里开始的问题Follow集解决到哪里结束的问题两者共同确保分析器在每一步都能做出确定性的选择2. PL/0表达式文法的实战拆解让我们以经典的PL/0表达式文法为例这是许多编译原理实验的首选案例表达式 :: [|-]项{加法运算符 项} 项 :: 因子{乘法运算符 因子} 因子 :: 标识符|无符号整数| ( 表达式 )2.1 手算First集的全过程计算First集有一套系统的方法但初次接触时很容易漏掉细节。以因子为例Y - SFirst(Y)包含First(S)即所有标识符Y - N加入First(N)即所有数字Y - ( B )加入左括号(最终得到First(Y) {标识符, 数字, (}这个过程中最容易犯的错误是忘记处理产生式右部开头是非终结符的情况忽略ε产生式的影响没有递归计算嵌套的First集2.2 Follow集计算的陷阱与技巧Follow集的计算更微妙。以项(X)为例我们需要考察所有包含X的产生式在B - JX(JX)|X(JX)中X后面直接跟)时)加入Follow(X)X后面跟/-时这些运算符加入Follow(X)在Y - (B)中当B推导出X时Follow(B)的)也要加入Follow(X)常见错误包括漏掉产生式末尾的情况忘记处理递归嵌套混淆First和Follow的传播规则3. LL(1)文法的三大检验标准判断一个文法是否是LL(1)的需要验证三个关键条件3.1 消除左递归原始PL/0文法已经满足这一点。左递归会产生无限循环的风险比如如果写成表达式 :: 表达式 项 /* 错误左递归 */递归下降分析器会陷入无限调用。改造方法是用右递归表达式 :: 项 { 项} /* 正确 */3.2 First集不相交对于每个非终结符A所有A产生式的First集必须两两不相交。例如A - aB | bC 是OK的 (First(aB){a}, First(bC){b}) A - aB | aC 就不是LL(1) (冲突的First集{a})PL/0的表达式文法完美满足这一条件。3.3 ε产生式的特殊处理如果有A - ε产生式则First(A)和Follow(A)必须不相交。PL/0文法中没有ε产生式所以这一条自动满足。4. 从理论到代码递归下降的实现艺术理解了这些概念后实现递归下降分析器就水到渠成了。以下是核心代码片段// 因子分析 void factor() { if (current_token IDENTIFIER || current_token NUMBER) { advance(); } else if (current_token LPAREN) { advance(); expression(); if (current_token ! RPAREN) { error(缺少右括号); } advance(); } else { error(非法的因子开始); } } // 项分析 void term() { factor(); while (current_token TIMES || current_token SLASH) { advance(); factor(); } } // 表达式分析 void expression() { if (current_token PLUS || current_token MINUS) { advance(); } term(); while (current_token PLUS || current_token MINUS) { advance(); term(); } }每个函数都严格对应文法中的一个非终结符函数内部的决策完全基于First集和Follow集的知识。比如在expression()中我们检查/-是因为它们在First(expression)中而在term()的while循环中我们检查*//是因为它们在Follow(term)中。5. 常见错误模式与调试心得在实验过程中我遇到了几乎所有可能的错误类型这些经验或许对你更有价值5.1 First集计算不完整症状分析器在某些合法输入上意外报错原因漏掉了某个产生式的First元素修复系统地检查每个产生式特别是嵌套情况5.2 Follow集传播错误症状分析器过早终止或跳过有效输入原因没有正确处理产生式链中的Follow传播修复画出所有产生式引用关系图确保Follow正确传递5.3 递归终止条件缺失症状程序栈溢出原因没有为递归函数设置明确的终止条件修复确保每个递归函数都有基于First/Follow集的终止检查6. 超越实验这些知识在实际编译器中的应用虽然PL/0是个教学用的小语言但其中的原理直接适用于现代编程语言。比如Python的运算符优先级正是通过类似PL/0的层次化文法实现的Java的类型解析使用First/Follow集解决语法歧义C的模板语法复杂的嵌套结构需要精确的LL(k)分析理解这些基础概念后再看真实编译器的源码如GCC的parser部分会变得容易很多。你会认出那些递归下降的函数结构发现First/Follow集的影子无处不在。7. 进阶思考当文法不是LL(1)时怎么办不是所有有用的文法都天然满足LL(1)条件。面对这种情况我们有几种选择文法改造提取左公因子消除左递归引入新的非终结符使用更强大的分析器LL(k)分析器前瞻更多符号LR分析器自底向上处理更复杂的文法容忍一定程度的回溯某些现代解析器如PEG允许有限回溯在PL/0实验中我有意尝试修改原始文法让它违反LL(1)条件然后观察分析器如何失败。这种破坏性测试极大地加深了我的理解。8. 工具推荐从手算到自动化虽然手算First/Follow集是必修课但在实际项目中我们会使用工具# 使用ANTLR生成解析器 antlr4 YourGrammar.g4 javac YourGrammar*.java grun YourGrammar rule -gui input.txt或者用Python的PLY库import ply.yacc as yacc # 定义文法规则 def p_expression_plus(p): expression : expression PLUS term p[0] p[1] p[3]这些工具背后仍然运用着First/Follow集的原理只是自动化了计算过程。理解底层机制能帮助你更好地使用它们并在出现问题时有效调试。9. 实验之外的收获计算思维的培养这个实验的价值远不止于掌握某个特定算法。通过反复推敲First/Follow集我培养了几种关键能力系统性思维将大问题分解为可管理的子问题精确性思维每个符号、每个集合都必须准确无误调试思维通过失败案例反向理解理论约束这些能力在后续学习操作系统、数据库等课程时都发挥了重要作用。编译原理之所以被称为CS的明珠正是因为这种思维训练的价值。10. 给后来者的建议如果你正在学习编译原理以下建议可能帮到你一定要动手实现概念在代码中才会真正具象化从小例子开始PL/0这样的微型语言是理想起点可视化分析过程画语法树、跟踪函数调用栈与他人讨论不同视角能发现你忽略的细节不要惧怕数学符号它们最终都会对应到具体的代码逻辑在完成这个实验后的某天当我阅读《Compilers: Principles, Techniques, and Tools》龙书中关于LL(1)的章节时突然发现那些曾经晦涩的数学描述变得异常清晰。那一刻我意识到真正的理解不是来自被动阅读而是来自将理论付诸实践的完整过程。
