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

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

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

自顶向下分析算法概述

自顶向下分析的算法是一大类算法。总体来说,它是从一个非终结符出发,逐步推导出跟被解析的程序相同的 Token 串。
这个过程可以看做是一张图的搜索过程,这张图非常大,因为针对每一次推导,都可能产生一个新节点。下面这张图只是它的一个小角落。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《编译原理之美》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(17)

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

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

    11
  • czh
    今日份总结:今天是一个扫盲的学习,有以下两点总结 1.编译的过程:词法分析 语法分析 语义分析 1.1词法分析:读取的内容是字符,根据词法规则输出token。几乎不涉及语言的语法特性,是编译器的基础。 1.2语法分析:读取的内容是token,输出的是语法树AST。语言的表达式等功能又这部分中定义的上下文无关文法来实现。 1.3语义分析:操作的对象是AST,所谓语义主要完成上下文相关的推理逻辑,如类型问题,定义声明问题等 2.说说我对编译原理的初次见面感觉:编译原理相比于其他计算机基础知识而言,他的难主要集中在需要高度的对现实生活规则的抽象能力、逻辑思维能力,否则写不出没问题的上下文无关文法规则,以及无法发现、处理其中蕴含的一些“逻辑坑”,如左递归等问题。而一些其他的知识点,如算法部分,这些其实相比于抽象能力来说,就要简单、通用、好理解的多,更加考验你的编程基础,而不是脑子。

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

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

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

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

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

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

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

    2
    1
  • 瓜瓜
    这个符号通常记做 $,意味一个程序的结束。比如在表达式的语法里,expression 后面可能跟这个符号,expression 的所有右侧分支的后代节点也都可能跟这个符号,也就是它们都可能出现在程序的末尾。但另一些非终结符,后面不会跟这个符号,如 blockstatements,因为它后面肯定会有“}”。 这一段看了好几遍,没有看懂,老师能不能再解释下?

    作者回复: 就是说,根据语法规则,有的非终结符可能出现在程序的末尾的,另一些非终结符永远也不可能出现在程序末尾。 比如,在语法规则中,blockStatements是block的一部分,也只出现在这一个地方。而block呢,前后一定环绕着花括号,这就导致了blockStatements后面必然是跟着“}”的。 换句话说,block是可能出现在程序结尾的,而blockStatement不可能。

  • LeeR
    老师你好,$ 是不是就是EOF符号,表示程序和文件的结束?

    作者回复: $是整个输入串右边的结束标记(endmarker)。 我们可以用EOF表示这个结束标记,因为这个时候源代码文件已经到结尾了。但理论上你还可以用某个特殊的Token来表示程序结束,只不过不常见罢了。

  • 余晓飞
    我把程序打印输出的 First 和 follow 集合整理如下(其实打印输出还包含一些中间节点,这里就不展示了): 这段下面的图中 assign1 的First 集合应该包含 Epsilon

    作者回复: 你说的没错。谢谢你的细心! 带1的非终结符(assign1, equal1, rel1, add1, mul1)的First结合的都包含Epsilon。 运行LLParser.java会输出正确的First集合。 我让编辑同学改一下图。

  • 余晓飞
    expression : assign ; assign : equal | assign1 ; assign1 : '=' equal assign1 | ε; 文中这里第二行 assign 是不写错了? 我看代码SimpleGrammar.java中有这一行GrammarNode assign = exp.createChild("assign", GrammarNodeType.And); 注释中刚好缺了关于assign的内容。

    作者回复: 没有写错。 是注释没有跟代码同步,少了赋值表达式的规则,已经修改过了。 运行LLParser,可以dump这个语法规则。

  • 余晓飞
    下图是上述推导过程建立起来的 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行的展开顺序不一致?

    作者回复: 你看得很细。上下两个图没配起来,两张图用的语法规则是不同的,插图的时候插错了,而且推导过程跳了步骤,我修改一下! 多谢你帮我发现!

收起评论
显示
设置
留言
17
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部