手把手带你写一门编程语言
宫文学
北京原点代码 CEO
7534 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 49 讲
起步篇:让一门超简单的语言跑起来 (21讲)
结束语 (1讲)
手把手带你写一门编程语言
15
15
1.0x
00:00/00:00
登录|注册

03|支持表达式:解析表达式和解析语句有什么不同?

你好,我是宫文学。
到目前为止,我们已经学习了一些语法分析的算法。不过,我们主要是分析了如何来解析语句,比如函数声明、函数调用,没有把重点放在解析表达式上。
其实我是刻意为之的,故意把表达式的解析往后推迟一下。原因是表达式解析,特别是像“2+3*5”这样的看似特别简单的二元运算的表达式解析,涉及的语法分析技术反而是比较复杂的。所以,从循序渐进的角度来说,我们要把它们放在后面。
表达式的解析复杂在哪里呢?是这样,我们在解析二元表达式的时候,会遇到递归下降算法最大的短板,也就是不支持左递归的文法。如果遇到左递归的文法,会出现无限循环的情况。
在这一节里,我会给你分析这种左递归的困境,借此加深你对递归下降算法运算过程的理解。
同时,我也要给出避免左递归问题的方法。这里,我没有采用教科书上经常推荐的改写文法的方法,而是使用了业界实际编译器中更常用的算法:运算符优先级解析器(Operator-precedence parser)。JDK 的 Java 编译器、V8 的 JaveScript 编译器和 Go 语言的 GC 编译器,都毫无例外地采用了这个算法,所以这个算法非常值得我们掌握。
好了,那我们首先来了解一下用递归下降算法解析算术表达式会出现的这个左递归问题。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了解析表达式和解析语句在语法分析算法中的挑战,特别关注了解析二元表达式所涉及的复杂语法分析技术。作者详细分析了左递归问题的本质,并提出了改写文法和其他算法的解决方法。针对解析二元表达式,作者选择了运算符优先级算法,这是实际编译器广泛采用的算法。通过介绍左递归问题和解决方法,读者能够深入理解递归下降算法的运算过程,以及掌握运算符优先级算法的实际应用。文章内容深入浅出,为读者提供了有价值的技术知识。文章还介绍了运算符优先级算法的原理和实现,以及在实际编译器中的应用情况。通过对二元表达式的解析,读者可以了解混合使用LL算法和运算符优先级算法的语法解析器实现方法。文章内容丰富,适合对语法分析算法感兴趣的读者阅读。文章还介绍了LR算法和LL算法的概念,以及它们在语法分析中的应用。通过对LR算法和LL算法的介绍,读者可以更全面地了解自底向上和自顶向下的语法分析算法。最后,文章提出了思考题,引发读者对右结合运算的实现方式进行思考。整体而言,本文通过深入讨论语法分析算法的挑战和解决方法,为读者呈现了丰富的技术内容,适合对编译原理和语法分析算法感兴趣的读者阅读。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《手把手带你写一门编程语言》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(8)

  • 最新
  • 精选
  • 陈迪
    gitee的仓库里缺了03的内容
    2021-10-02
    4
  • Gaollard
    我在另外一本书看到做法是:解析时先去尝试将语句解析为 运算符最低的表达式,然后逐渐下降。比如 F 语言 有 条件表达式,以及 + * 运算法。那么它的逻辑是这样的:tryParseConditional -> tryBinaryExp -> tryParseAddExp -> tryParseMulExp。总体就是将运算符优先级比较高的表达式因子,作为 运算符较低表达式的运算因子。 老师的这种通过引入运算符优先级管理(运算符优先级映射表)是好很多的做法,babel 依赖的 acorn.js 也是这么做的。
    2022-01-14
    1
  • Geek_2116e8
    不违反优先级的运算 即使是右结合答案也不会错啊
    2021-09-06
    1
  • 有学识的兔子
    常见运算中,赋值运算和幂运算是符合右结合的。在计算ast时,碰到幂运算时多向前获取一个token,构建一个独立的ast片段,不受其它运算符的影响。
    2021-08-15
    1
  • ifelse
    学习了
    2022-09-10归属地:浙江
  • 阿章
    老师,求03节的代码呀
    2021-11-26
  • bugfree
    首先词法分析需要把运算符单元准确的给出来,不管是-也好,=也罢,还是**,都行,要解析好给出来,然后如果是右结合,那就再往后拿一个token来进行独立ast树的构建,同时按照优先级进行单调栈的排序,当然如果遇见括号这种就进入递归环节了
    2021-09-02
  • 写点啥呢
    请问宫老师,在2+3+4这个例子中在判断4之后的运算符是*的情况所画的AST,感觉绿色AST将4*的AST节点和2+3的节点画在同一个+号节点的两个字节点是不对的,这会导致2+3先于4*x的表达式求值而违反运算符优先级
    2021-08-16
    2
收起评论
显示
设置
留言
8
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部