手把手带你写一门编程语言
宫文学
北京原点代码 CEO
7235 人已学习
新⼈⾸单¥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
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《手把手带你写一门编程语言》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(8)

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