17 | First和Follow集合：用LL算法推演一个实例
该思维导图由 AI 生成，仅供参考
自顶向下分析算法概述
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了自顶向下分析算法及其在语法解析中的应用。首先介绍了深度优先和广度优先两种搜索策略在递归下降算法中的性能表现，指出了它们在内存占用和计算量上的特点。随后详细解释了LL算法的原理和应用，以及计算和使用First集合和Follow集合的方法。文章还探讨了符合LL(k)特别是LL(1)算法的文法设计，强调了避免左递归和抽取左公因子的重要性。总结时指出，掌握处理ε的关键点对于理解LL算法至关重要。整体而言，本文通过对自顶向下分析算法的概述和LL算法的详细解释，帮助读者更好地理解了这一算法体系的原理和应用。
《编译原理之美》，新⼈⾸单¥59
全部留言(18)
- 最新
- 精选
沉淀的梦想Antlr中LL(k)中k是多少，是Antlr根据我们的文法动态决定的吗？还是老师文中说的那些写LL文法的注意点，我们在写Antlr文法的时候需要注意吗？Antlr会帮助我们自动处理这些吗？作者回复: 是的。它会自动处理。 Antlr这个工具做了大量的工作，让开发者编写语法的时候，可以效率更高。 这样的工具，也不是采用固化的LL(1)或LL(2)算法，而是有能力根据语法去决定解析策略。实在不行了还可以回溯。你会发现：1.生产中使用的编译器，会综合采用多种技术，而不仅仅是单纯的采用某个算法。 2.如果要写符合LL(1)算法的语法，其实语法很啰嗦。这是在编译技术发展的早期，计算能力有限，大家更重视执行的效率。而现在，计算能力很强，可以更加照顾开发者效率，而不是计算效率。所有Antlr的语法很友好，很人性化。从表达式的语法就可见一斑。
2019-09-2211
czh今日份总结：今天是一个扫盲的学习，有以下两点总结 1.编译的过程：词法分析 语法分析 语义分析 1.1词法分析：读取的内容是字符，根据词法规则输出token。几乎不涉及语言的语法特性，是编译器的基础。 1.2语法分析:读取的内容是token，输出的是语法树AST。语言的表达式等功能又这部分中定义的上下文无关文法来实现。 1.3语义分析:操作的对象是AST，所谓语义主要完成上下文相关的推理逻辑，如类型问题，定义声明问题等 2.说说我对编译原理的初次见面感觉：编译原理相比于其他计算机基础知识而言，他的难主要集中在需要高度的对现实生活规则的抽象能力、逻辑思维能力，否则写不出没问题的上下文无关文法规则，以及无法发现、处理其中蕴含的一些“逻辑坑”，如左递归等问题。而一些其他的知识点，如算法部分，这些其实相比于抽象能力来说，就要简单、通用、好理解的多，更加考验你的编程基础，而不是脑子。作者回复: 谢谢你分享自己的感受。 我再加几句。你说的对。编译器的前端，带有很强的形式体系的特征。形式语言能够描述程序的语法，也能用于描述数学上的公理体系。逻辑学、哲学领域，通常也需要这样抽象级别的体系。所以抽象程度确实挺高。
2020-01-034- 沉淀的梦想还是不太明白为什么要有Follow集这个东西，如果First集中查找不到的话，直接将推导为ε，然后接着去推导下一个，如果发现不在下一个的First集中再报错，好像也不会有什么性能损失，那为什么要费那么大力气构建Follow集呢？
作者回复: 把箭头指在线上这种画法确实不大好，会有歧义。我回头更新一版图，让箭头指向每个存储位置的格子上。
2019-09-2233 
墨灵https://github.com/moling3650/Frontend-01-Template/blob/master/week12/ast.js 用JavaScript写了一个四则计算器，总算搞明白产生式和LL算法的对应关系了，这课真是太不容易了，对于一个前端来说。作者回复: 恭喜你！ 并且，你不是孤独的。我们公司的一名前端工程师，已经被我忽悠到编译的道路上了:-) 而且，编译技术在完成很多高级的前端工作方面大有可为！
2020-06-281
余晓飞下图是上述推导过程建立起来的 AST，“1、2、3……”等编号是 AST 节点创建的顺序 对这段话后前后两幅图有疑惑，前面一副图中的第4行是怎么直接到第5行的， 如果通过下面右递归版的产生式推导似乎省略了一步？ add -> mul | mul + add mul -> pri | pri * mul pri -> Id | Num | (add) 后面一幅图中节点8, 9, 10在节点12, 13之前生成，似乎这与前一幅图第6到8行的展开顺序不一致？作者回复: 你看得很细。上下两个图没配起来，两张图用的语法规则是不同的，插图的时候插错了，而且推导过程跳了步骤，我修改一下！ 多谢你帮我发现！
2019-10-021- Geek_f9ea2d老师好，对First集合我基本能理解，对Fllow集合的计算，我看的有点懵，这个方法：addToRightChild 为什么需要：把某个节点的Follow集合，也给它所有右边分枝的后代节点？
作者回复: 因为这些孩子节点是父节点最右边的。那么父节点后面会跟什么终结符，这些子节点也会跟这些终结符。 如果一个非终结符位于上一级产生式的最右边，比如：A->abcdB中的B，（我们用大小写区分终结符和非终结符）那么找到可能出现在它右边的终结符，实际上不是那么好找。要看看A后面都可能跟啥，比如：C->abcAb，那么A的Follow集合中有b，B的Follow集合中也要有b。 实际上，我觉得自己的这个实现比较笨拙，受限于我采用的GrammarNode这样的数据结构。后面有时间的话，我再写个更加简洁的算法给大家参考。
2019-09-2821 
瓜瓜这个符号通常记做 $，意味一个程序的结束。比如在表达式的语法里，expression 后面可能跟这个符号，expression 的所有右侧分支的后代节点也都可能跟这个符号，也就是它们都可能出现在程序的末尾。但另一些非终结符，后面不会跟这个符号，如 blockstatements，因为它后面肯定会有“}”。 这一段看了好几遍，没有看懂，老师能不能再解释下？作者回复: 就是说，根据语法规则，有的非终结符可能出现在程序的末尾的，另一些非终结符永远也不可能出现在程序末尾。 比如，在语法规则中，blockStatements是block的一部分，也只出现在这一个地方。而block呢，前后一定环绕着花括号，这就导致了blockStatements后面必然是跟着“}”的。 换句话说，block是可能出现在程序结尾的，而blockStatement不可能。
2020-02-05
LeeR老师你好，$ 是不是就是EOF符号，表示程序和文件的结束？作者回复: $是整个输入串右边的结束标记（endmarker）。 我们可以用EOF表示这个结束标记，因为这个时候源代码文件已经到结尾了。但理论上你还可以用某个特殊的Token来表示程序结束，只不过不常见罢了。
2019-12-01- 余晓飞我把程序打印输出的 First 和 follow 集合整理如下（其实打印输出还包含一些中间节点，这里就不展示了）： 这段下面的图中 assign1 的First 集合应该包含 Epsilon
作者回复: 你说的没错。谢谢你的细心！ 带1的非终结符（assign1, equal1, rel1, add1, mul1）的First结合的都包含Epsilon。 运行LLParser.java会输出正确的First集合。 我让编辑同学改一下图。
2019-10-29 - 余晓飞expression : assign ; assign : equal | assign1 ; assign1 : '=' equal assign1 | ε; 文中这里第二行 assign 是不写错了？ 我看代码SimpleGrammar.java中有这一行GrammarNode assign = exp.createChild("assign", GrammarNodeType.And); 注释中刚好缺了关于assign的内容。
作者回复: 没有写错。 是注释没有跟代码同步，少了赋值表达式的规则，已经修改过了。 运行LLParser，可以dump这个语法规则。
2019-10-23
