编译原理之美
宫文学
北京原点代码 CEO
46197 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 45 讲
开篇词 (1讲)
编译原理 · 期中考试周 (1讲)
编译原理之美
15
15
1.0x
00:00/00:00
登录|注册

17 | First和Follow集合:用LL算法推演一个实例

计算方式
处理ε的情况
计算方式
避免回溯
搜索策略
避免回溯
性能上的损失
LLParser.java
分享思考
处理ε的关键点
LL算法的核心概念
First集合和Follow集合
自顶向下算法概述
优化LL(k)算法
抽取左公因子
避免左递归
Follow集合
First集合
预测性算法
Left-to-right, Leftmost
优化方向
深度优先和广度优先
预测能力的自顶向下分析算法
递归下降算法
示例代码
一课一思
课程小结
文法设计
LL算法
自顶向下分析算法

该思维导图由 AI 生成,仅供参考

在前面的课程中,我讲了递归下降算法。这个算法很常用,但会有回溯的现象,在性能上会有损失。所以我们要把算法升级一下,实现带有预测能力的自顶向下分析算法,避免回溯。而要做到这一点,就需要对自顶向下算法有更全面的了解。
另外,在留言区,有几个同学问到了一些问题,涉及到对一些基本知识点的理解,比如:
基于某个语法规则做解析的时候,什么情况下算是成功,什么情况下算是失败?
使用深度优先的递归下降算法时,会跟广度优先的思路搞混。
要搞清这些问题,也需要全面了解自顶向下算法。比如,了解 Follow 集合和 $ 符号的用法,能帮你解决第一个问题;了解广度优先算法能帮你解决第二个问题。
所以,本节课,我先把自顶向下分析的算法体系梳理一下,让你先建立更加清晰的全景图,然后我再深入剖析 LL 算法的原理,讲清楚 First 集合与 Follow 集合这对核心概念,最终让你把自顶向下的算法体系吃透。

自顶向下分析算法概述

自顶向下分析的算法是一大类算法。总体来说,它是从一个非终结符出发,逐步推导出跟被解析的程序相同的 Token 串。
这个过程可以看做是一张图的搜索过程,这张图非常大,因为针对每一次推导,都可能产生一个新节点。下面这张图只是它的一个小角落。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
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-22
    11
  • czh
    今日份总结:今天是一个扫盲的学习,有以下两点总结 1.编译的过程:词法分析 语法分析 语义分析 1.1词法分析:读取的内容是字符,根据词法规则输出token。几乎不涉及语言的语法特性,是编译器的基础。 1.2语法分析:读取的内容是token,输出的是语法树AST。语言的表达式等功能又这部分中定义的上下文无关文法来实现。 1.3语义分析:操作的对象是AST,所谓语义主要完成上下文相关的推理逻辑,如类型问题,定义声明问题等 2.说说我对编译原理的初次见面感觉:编译原理相比于其他计算机基础知识而言,他的难主要集中在需要高度的对现实生活规则的抽象能力、逻辑思维能力,否则写不出没问题的上下文无关文法规则,以及无法发现、处理其中蕴含的一些“逻辑坑”,如左递归等问题。而一些其他的知识点,如算法部分,这些其实相比于抽象能力来说,就要简单、通用、好理解的多,更加考验你的编程基础,而不是脑子。

    作者回复: 谢谢你分享自己的感受。 我再加几句。你说的对。编译器的前端,带有很强的形式体系的特征。形式语言能够描述程序的语法,也能用于描述数学上的公理体系。逻辑学、哲学领域,通常也需要这样抽象级别的体系。所以抽象程度确实挺高。

    2020-01-03
    4
  • 沉淀的梦想
    还是不太明白为什么要有Follow集这个东西,如果First集中查找不到的话,直接将推导为ε,然后接着去推导下一个,如果发现不在下一个的First集中再报错,好像也不会有什么性能损失,那为什么要费那么大力气构建Follow集呢?

    作者回复: 把箭头指在线上这种画法确实不大好,会有歧义。我回头更新一版图,让箭头指向每个存储位置的格子上。

    2019-09-22
    3
    3
  • 墨灵
    https://github.com/moling3650/Frontend-01-Template/blob/master/week12/ast.js 用JavaScript写了一个四则计算器,总算搞明白产生式和LL算法的对应关系了,这课真是太不容易了,对于一个前端来说。

    作者回复: 恭喜你! 并且,你不是孤独的。我们公司的一名前端工程师,已经被我忽悠到编译的道路上了:-) 而且,编译技术在完成很多高级的前端工作方面大有可为!

    2020-06-28
    1
  • 余晓飞
    下图是上述推导过程建立起来的 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-02
    1
  • Geek_f9ea2d
    老师好,对First集合我基本能理解,对Fllow集合的计算,我看的有点懵,这个方法:addToRightChild 为什么需要:把某个节点的Follow集合,也给它所有右边分枝的后代节点?

    作者回复: 因为这些孩子节点是父节点最右边的。那么父节点后面会跟什么终结符,这些子节点也会跟这些终结符。 如果一个非终结符位于上一级产生式的最右边,比如:A->abcdB中的B,(我们用大小写区分终结符和非终结符)那么找到可能出现在它右边的终结符,实际上不是那么好找。要看看A后面都可能跟啥,比如:C->abcAb,那么A的Follow集合中有b,B的Follow集合中也要有b。 实际上,我觉得自己的这个实现比较笨拙,受限于我采用的GrammarNode这样的数据结构。后面有时间的话,我再写个更加简洁的算法给大家参考。

    2019-09-28
    2
    1
  • 瓜瓜
    这个符号通常记做 $,意味一个程序的结束。比如在表达式的语法里,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
收起评论
显示
设置
留言
18
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部