编译原理之美
宫文学
北京物演科技CEO
立即订阅
8171 人已学习
课程目录
已完结 43 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 为什么你要学习编译原理?
免费
实现一门脚本语言 · 原理篇 (13讲)
01 | 理解代码:编译器的前端技术
02 | 正则文法和有限自动机:纯手工打造词法分析器
03 | 语法分析(一):纯手工打造公式计算器
04 | 语法分析(二):解决二元表达式中的难点
05 | 语法分析(三):实现一门简单的脚本语言
06 | 编译器前端工具(一):用Antlr生成词法、语法分析器
07 | 编译器前端工具(二):用Antlr重构脚本语言
08 | 作用域和生存期:实现块作用域和函数
09 | 面向对象:实现数据和方法的封装
10 | 闭包: 理解了原理,它就不反直觉了
11 | 语义分析(上):如何建立一个完善的类型系统?
12 | 语义分析(下):如何做上下文相关情况的处理?
13 | 继承和多态:面向对象运行期的动态特性
实现一门脚本语言 · 应用篇 (2讲)
14 | 前端技术应用(一):如何透明地支持数据库分库分表?
15 | 前端技术应用(二):如何设计一个报表工具?
实现一门脚本语言 · 算法篇 (3讲)
16 | NFA和DFA:如何自己实现一个正则表达式工具?
17 | First和Follow集合:用LL算法推演一个实例
18 | 移进和规约:用LR算法推演一个实例
实现一门脚本语言 · 热点答疑与用户故事 (2讲)
19 | 案例总结与热点问题答疑:对于左递归的语法,为什么我的推导不是左递归的?
用户故事 | 因为热爱,所以坚持
编译原理 · 期中考试周 (1讲)
期中考试 | 来赴一场100分的约定吧!
免费
实现一门编译型语言 · 原理篇 (12讲)
20 | 高效运行:编译器的后端技术
21 | 运行时机制:突破现象看本质,透过语法看运行时
22 | 生成汇编代码(一):汇编语言其实不难学
加餐 | 汇编代码编程与栈帧管理
23 | 生成汇编代码(二):把脚本编译成可执行文件
24 | 中间代码:兼容不同的语言和硬件
25 | 后端技术的重用:LLVM不仅仅让你高效
26 | 生成IR:实现静态编译的语言
27 | 代码优化:为什么你的代码比他的更高效?
28 | 数据流分析:你写的程序,它更懂
29 | 目标代码的生成和优化(一):如何适应各种硬件架构?
30 | 目标代码的生成和优化(二):如何适应各种硬件架构?
实现一门编译型语言 · 应用篇 (2讲)
31 | 内存计算:对海量数据做计算,到底可以有多快?
32 | 字节码生成:为什么Spring技术很强大?
实现一门编译型语言 · 扩展篇 (3讲)
33 | 垃圾收集:能否不停下整个世界?
34 | 运行时优化:即时编译的原理和作用
35 | 案例总结与热点问题答疑:后端部分真的比前端部分难吗?
面向未来的编程语言 (3讲)
36 | 当前技术的发展趋势以及其对编译技术的影响
37 | 云编程:云计算会如何改变编程模式?
38 | 元编程:一边写程序,一边写语言
结束语 (1讲)
结束语 | 用程序语言,推动这个世界的演化
编译原理之美
登录|注册

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

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

自顶向下分析算法概述

自顶向下分析的算法是一大类算法。总体来说,它是从一个非终结符出发,逐步推导出跟被解析的程序相同的 Token 串。
这个过程可以看做是一张图的搜索过程,这张图非常大,因为针对每一次推导,都可能产生一个新节点。下面这张图只是它的一个小角落。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《编译原理之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(9)

  • LeeR
    老师你好,$ 是不是就是EOF符号,表示程序和文件的结束?
    2019-12-01
  • Lamont
    我把程序打印输出的 First 和 follow 集合整理如下(其实打印输出还包含一些中间节点,这里就不展示了):

    这段下面的图中 assign1 的First 集合应该包含 Epsilon
    2019-10-29
  • Lamont
    expression : assign ;
    assign : equal | assign1 ;
    assign1 : '=' equal assign1 | ε;

    文中这里第二行 assign 是不写错了?
    我看代码SimpleGrammar.java中有这一行GrammarNode assign = exp.createChild("assign", GrammarNodeType.And);
    注释中刚好缺了关于assign的内容。
    2019-10-23
  • Lamont
    下图是上述推导过程建立起来的 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
  • Lamont
    这样就形成了四条搜索路径,分别是 mul+mul、add+mul+mul、add+pri 和 add+mul+pri。
    这里最后一个是不是应该为add+mul*pri

    作者回复: 没错,mul展开成mul*pri。笔误了。多谢指出!

    2019-10-01
  • Geek_f9ea2d
    老师好,对First集合我基本能理解,对Fllow集合的计算,我看的有点懵,这个方法:addToRightChild 为什么需要:把某个节点的Follow集合,也给它所有右边分枝的后代节点?

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

    2019-09-28
  • 沉淀的梦想
    https://github.com/RichardGong/PlayWithCompiler/blob/master/lab/16-18/src/main/java/play/parser/LLParser.java#L242

    作者回复: 这句看不懂?我抽空多加点注释。

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

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

    2019-09-22
  • 沉淀的梦想
    Antlr中LL(k)中k是多少,是Antlr根据我们的文法动态决定的吗?还是老师文中说的那些写LL文法的注意点,我们在写Antlr文法的时候需要注意吗?Antlr会帮助我们自动处理这些吗?

    作者回复: 是的。它会自动处理。
    Antlr这个工具做了大量的工作,让开发者编写语法的时候,可以效率更高。
    这样的工具,也不是采用固化的LL(1)或LL(2)算法,而是有能力根据语法去决定解析策略。实在不行了还可以回溯。你会发现:1.生产中使用的编译器,会综合采用多种技术,而不仅仅是单纯的采用某个算法。
    2.如果要写符合LL(1)算法的语法,其实语法很啰嗦。这是在编译技术发展的早期,计算能力有限,大家更重视执行的效率。而现在,计算能力很强,可以更加照顾开发者效率,而不是计算效率。所有Antlr的语法很友好,很人性化。从表达式的语法就可见一斑。

    2019-09-22
收起评论
9
返回
顶部