03 | 语法分析（一）：纯手工打造公式计算器
解析变量声明语句：理解“下降”的含义
请订阅文章所属专栏。
精选留言(65)
Sam 置顶初学者看了 8 遍, 终于看懂了, 不急不燥, 慢慢看就行了作者回复: 点赞！
2019-08-22 1 19
许童童老师你好，
additiveExpression
: multiplicativeExpression
| additiveExpression Plus multiplicativeExpression
;
multiplicativeExpression
: IntLiteral
| multiplicativeExpression Star IntLiteral
;
这种DSL怎么理解？作者回复: 这个实际上就是语法规则，是用BNF表达的。以addtive为例，它有两个产生式。
产生式1：一个乘法表达式
产生式2：一个加法表达式 + 乘法表达式。
通过上面两个产生式的组合，特别是产生式2的递归调用，就能推导出所有的加减乘数算术表达式。
比如，对于2*3这个表达式，运用的是产生式1。
对于2+3*5，运用的是产生式2。
我上面用的语法规则的写法，实际上是后面会用到的Antlr工具的写法。你也可以这样书写，就是一般教材上的写法：
A -> M | A + M
M -> int | M * int
我们每个非终结符只用了一个大写字母代表，比较简洁。我在文稿中用比较长的单词，是为了容易理解其含义。
其中的竖线，是选择其一。你还可以拆成最简单的方式，形成4条规则：
A -> M
A -> A + M
M -> int
M -> M * int
上面这些不同的写法，都是等价的。你要能够看习惯，在不同的写法中自由切换。
不知道是否解答了你的疑问。2019-08-19 4 35
长方体混凝土移动工程师2 + 3 的推导过程就是要找到一个表达示可以正确的表达这个计算规则。顺序的消耗掉三个token,找到能表达这个式子的公式推导过程完成,并成功。
如果使用A: M | A + M 的方式来递归代入,步步推导无法消耗完三个token的情况下就会陷入无限循环
推导过程:
--------------------------------------------------------------------------
1. 2 + 3 不是M表达式,使用A + M的方法匹配
2. A + M 在推导A的时候重复第1步操作,因为此时我们并没有消耗掉token,将完整的token代入A重复第1步推导,无限循环
--------------------------------------------------------------------------
但如果使用A: M | M + A 的方式来递归代入
推导过程:
--------------------------------------------------------------------------
1. 2 + 3 不是一个M，使用M + A推导,变成M + A
2. 使用2去匹配M可以顺序推导并消耗掉2这个字面量token,此时流中剩下 + 3两个token
3. 使用M + A规则中的+号消耗掉 + 3中的+号token
4. 将M + A中的A再次推导成M
5.最终推导成M + M,此时剩下的最后一个字面量token 3被消耗掉
--------------------------------------------------------------------------作者回复: 没错。很好。
既然你已经理解了，那么我再增加一点难度。当前推导是最左推导（LeftMost）推导的算法。也就是总是先把左边的非终结符展开。而且是深度优先的。
你再广度优先推演一下看看？
你再最右推导一下看看？
可能你的感受又不一样。很有意思的。可以作为消遣游戏 :-D2019-08-22 5 21
鸠摩智老师您好，请问语法和文法有什么区别和联系？作者回复: 你提的问题特别好！其他同学可能也会有这种疑问。
文法，英文叫做Grammar，是形式语言（Formal Language）的一个术语。所以也有Formal Grammar这样的说法。这里的文法有定义清晰的规则。比如，我们的词法规则、语法规则和属性规则，使用形式文法来定义的。我们的课程里讲解了正则文法(Regular Grammar)、上下文无关文法(Context-free Grammar)等不同的文法规则，用来描述词法和语法。
语法分析中的这个语法，英文是Syntax，主要是描述词是怎么组成句子的。一个语言的语法规则，通常指的是这个Syntax。
问题是，Grammar这个词，在中文很多应用场景中也叫做语法。这是会引起混淆的地方。我们在使用的时候要小心一点就行了。
比如，我做了一个规则文件，里面都是一些词法规则（Lexer Grammar），我会说，这是一个词法规则文件，或者词法文法文件。这个时候，把它说成是一个语法规则文件，就有点含义模糊。因为这里面并没有语法规则（Syntax Grammar）。
为你的认真思考点赞！2019-08-19 1 18
张辽儿为什么出现左递归无限调用我还没有理解，例如2+3；当进入加法表达式递归的时候，参数不是已经变成了2吗，然后就是乘法表达式，最后形成字面常量。请老师解答下我的疑问，谢谢作者回复: 为了方便讨论，我们把规则简化一下，去掉乘法那一层。否则在乘法那就已经无限递归下去了。修改后为：
additive -> IntLiteral | additive Intliteral ;
我们假设是最左推导，也就是总是先展开左边的非中介符。
第一遍：additive->IntLiteral，但因为后面还有Token没处理完，所以这个推导过程会失败，要退回来。
这可能是你没理解的地方。我们是要用additive匹配整个Token串，而不仅仅是第一个Token。
第二遍：用第二个产生式，additive->additive->IntLiteral，还是一样失败。
第三遍：additive->additive->additive->IntLiteral。
第四遍：....
这样说，有没有帮助？2019-08-20 3 16
阿尔伯特https://github.com/albertabc/compiler
读了几遍老师的讲义。才逐渐理解了语法解析中用的推导。接着前一讲，攒了个程序。
就这个推导说说我目前的理解，其中最开始不能理解的根本原因就是没能理解语法规则之间的相互关系，以及与此相关的token的消耗。
比如例子A->Int | A + Int
在最开始的理解中，错误以为，这两条是顺序关系，与此相应就想当然认为token的消耗是像字符串匹配一样“一个接一个”的进行。这种错误思路是这样的：2+3， 首先看token 2， 它是int所以消耗掉，然后类推。
而实际上，这两条规则是从某种程度上是“互斥”的关系。也就是说，2+3 要么是Int， 要么是A+Int，在没有找到合适的规则前，token是不会被消耗的。由此，在深度优先实现中，就有老师所说的推导实现过程。总的要解决的问题是，2+3 是不是A，能不能用这条A规则来解释。那么就看它是否满足A的具体规则。首先，2+3 显然不是Int，因此没有token消耗。然后，在匹配A + Int时，上来就要看 2+3 是不是A，不断要解决原来的问题，从而就产生了所谓左递归。
所以在深度优先情况下，打破无穷递归，就把规则改为A->Int|Int + A。这时，推导， 2+3显然不是Int。于是看Int + A。2显然是Int，于是消耗掉；再看+，消耗掉；再看3是不是A，3显然是Int，所以返回。
作为老师的示例程序，并没有体现出对A->M|M+A 两条“互斥”标准的分别处理，所以可能造成了一定疑惑。我是这样理解的，程序事实上合并了对于M的处理，一段代码，处理了第一全部和第二一部分。比如2+3*5，机械按照刚才的理解，2+3*5显然不是M，于是任何token都不消耗，退回。再匹配第二条，第二条上来就会找，它是不是M开头，如果是就消耗掉+之前的token；然后消耗+；然后再看看A。程序是不管如何，上来就看，是不是M开头。如果不是，那肯定就不是A，就返回NULL。如果是，就看你有没有“+”，如果没有，你就直接是规则第一条，如果有，就看你是不是第二条。从而就实现了两条M的合并处理。
在看了评论后，又看到了广度优先的推导，以及老师说有大量回溯，刚开始不甚理解。后来有点理解，A->Int|A+Int.该规则在深度优先中，会导致左递归。如果用广度优先，则会有如下方式。所谓广度优先，通俗理解就是“横”着来。那我理解是，2+3显然不是Int。因此要找第二条规则那就是首先要从头扫描，找“+”，然后再“回头”看2是不是A，这就带来了回溯吧。但是由于只用了部分token，即判断2而不是2+3是不是A，所以，避免了左递归。
请老师和各位同学有空帮忙指正。谢谢作者回复: 哇，这么认真，这么仔细:-)
竖线“|”是或者的关系，怪我忘了强调这一点了。在正则文法、上下文无关文法中，“|”都是代表几个不同的选项。
另外，在前端技术的算法篇，会再把我们对算法的理解提升一下。我尽量做几个示例程序，演示出深度优先和广度优先的差别来。特别是，为什么广度优先的回溯会太多。
当然，如果你能先于我写一个，也可以分享给大家，就省了我的事了 :-)
为你的认真精神点赞！2019-09-05 2 12- 阿名如果没有基础 比较难听得懂 比如文法推导 终结符 非终结符 这些概念 本身就不好理解
作者回复: 实际上，这些看上去比较正式的术语，是我在这篇文稿的最后一版才加上去的。其实，你忽略这些术语，也完全能看懂文稿。加上这些术语，是为后面正式讲算法做个铺垫。
我知道编译原理的术语本身就能吓倒很多人。但是这门课程的重点在于帮你建立直觉（Intuition）。建立起直觉来以后，你其实已经明白了语法分析的过程，你已经对它有熟悉感了。之后你再把这些直觉跟术语联系在一起，就不觉得困难了。
再次强调一点，首先建立直觉，然后再追求对术语和算法的严格理解。
学编译原理最大的困难不是这门课本身的难度，而是我们对它的畏惧心理。相信你自己！2019-08-19 1 11 
朱天超课下可以参考下:《编译系统透视：图解编译原理》2019-08-19 9- 💪😊递归容易表达很多算法，但是计算机本身执行递归有栈溢出和效率等问题，如何平衡呢？
作者回复: 你说的很对！
实际上，你提到了递归的优化问题。这是一个专门的研究领域。在SICP（《计算机程序的构造和解释》）这本书中，对这个问题也很重视。
我们下一讲会提到尾递归的情形，也就是线性迭代的递归函数。它实际上可以转化成循环语句，就没有对栈的消耗了。这是在编译技术中常用的一种优化策略。你可以提前了解一下尾递归 : )2019-08-19 8 
kaixiao7老师您好：
additiveExpression
: multiplicativeExpression
| multiplicativeExpression Plus additiveExpression
;
multiplicativeExpression
: IntLiteral
| IntLiteral Star multiplicativeExpression
;
在用上述文法求解 2+3*5 时，首先会匹配乘法规则， 根据代码，这一步返回字面量2，显然是产生式1匹配的结果， 我的问题是这里不应该用 产生式1 匹配 2+3*5 整个token串吗？
另外，再计算表达式 2*3*5 时， 返回的AST为 2*3，而 *5 丢失了，因此multiplicative()方法中的SimpleASTNode child2 = primary(tokens); 是不是应该递归调用multiplicative()呢？
期待您的解惑！作者回复: 算法可以首先尝试产生式1。推导顺序是这样的：
additive -> multiplicative(加法的产生式1)
-> Intliteral（2）（乘法的产生式1）
这时候只消化了一个Token呀。我们是要用一个表达式把这5个Token都消化掉才行。所以会继续尝试乘法的产生式2。
additive -> multiplicative(加法的产生式1)
-> Intliteral * multiplicative （乘法的产生式2）
这次尝试不成功，因为我们下一个Token是加号，不是乘号。
现在，退回来尝试加法的产生式2。
additive -> multiplicative + additive(加法的产生式2)
-> Intliteral(2) + additive
->Intliteral(2) + multiplicative
-> Intliteral(2) + Intliteral(3) 不行，因为还有Token
-> Intliteral(2) + Intliteral(3) * multiplicative 又用上乘法的产生式2了
->Intliteral(2) + Intliteral(3) * Intliteral(5)
这是严格的推导过程。我在示例代码的实现中，因为提取了左公因子，所以没用多次回溯。
这样说，你能明白吗？如果还不明白，就再问。2019-08-21 2 7
Rockbean小白读得有些吃力
> "我们首先把变量声明语句的规则，用形式化的方法表达一下。它的左边是一个非终结符（Non-terminal）。右边是它的产生式（Production Rule）。"
“它的左边”的“它”是指变量声明语句"int age = 45"呢还是什么，如果是变量声明语句,那左边是左到哪里，是“int age”还是什么？非终结符，是什么，往前翻了几个课也没有找到，或者说终结符是什么？同样的右边是右从哪里开始算右边？产生式是“=45”吗？小白对这些基础词汇有点蒙，见笑了作者回复: 1.终结符跟非终结符在04讲得更细一点，可以在04讲再体会一下。
2.它的左边，是指：
intDeclaration : Int Identifier ('=' additiveExpression)?;
这个规则，冒号的左边。2019-08-25 1 3
中年男子
总结一下：开头讲的推导过程就是递归过程
针对加法表达式 2+3
最初规则：
additive
:multiplicative
| additive Plus multiplicative
;
multiplicative
: IntLiteral
| multiplicative Star IntLiteral
;
简化：
additive
：IntLiteral
| additive Plus IntLiteral
；
multiplicative
：IntLiteral
| multiplicative Star IntLiteral
；
遍历整个token串，运用产生式1 ，不是 IntLiteral，运用产生式2，这里会出现左递归
解决左递归， 把additive 调换到 加号（plus）后边去。相应的multiplicative 也调换位置
additive
: IntLiteral
| IntLiteral Plus multiplicative
;
multiplicative
: IntLiteral
| IntLiteral Star multiplicative
;
再解析 “2+3+4”
这里我就不明白了，为什么首先调用乘法表达式匹配函数，就能成功返回字面量2呢？
文法规则里的 “Star” 是什么意思？ 还请老师解惑！作者回复: 我觉得你在认真分析，点赞！
在讨论左递归会无穷次递归的时候，我们把语法简化了一下，是根本就不要乘法运算了，只看加法运算。这样来推演左递归更加方便一点。
简化后的规则为：
additive -> IntLiteral | additive Intliteral ;
解析过程：
第一遍：additive->IntLiteral，但因为后面还有Token没处理完，所以这个推导过程会失败，要退回来。
第二遍：additive->additive->IntLiteral，还是一样失败。
第三遍：additive->additive->additive->IntLiteral。
第四遍：....
Star就是*号，是一个Token符号。是词法分析过程中形成的。这样的问题建议你看看源代码，甚至运行一下，就更清楚了。
如果不清楚，继续问我。2019-08-21 1 2
William前端开发，表示有些吃力。很好奇Babel、Node.js的编译机制。作者回复: 学完课程，你应该会理解这两个的运作机制。
Babel，只是做语言翻译，只需要前端技术就可以了。翻译成AST，做完语义分析，再转成另一个版本的js。
Node.js基于v8，不仅仅做前端工作，更重要的是在后端运行时做各种优化。2019-08-20 2
小广解析“2 + 3”遇到左递归问题那一段，需要解析到 + 号的时候，才会发生下面的递归循环的问题，一开始看有点断档，因为第一个字符2是不会遇最递归的问题的，如果老师可以提示一下话，可能看起来会更加流畅一点O(∩_∩)O~作者回复: 嗯。谢谢你的建议。我看看是否需要把文稿表达得更细致一点。
如果不要乘法那一层，说明起来可能更简洁一些。否则，其实进入到乘法以后，就已经递归个不停了，根本回不到加法规则这来。
修改规则为：
additive -> IntLiteral | additive Intliteral ;
第一遍：additive->IntLiteral，但因为后面还有Token没处理完，所以这个推导过程会失败，要退回来。
第二遍：additive->additive->IntLiteral，还是一样失败。
第三遍：additive->additive->additive->IntLiteral。
第四遍：....2019-08-20 2 2
Void_seT“2+3*5”的表达式推导中，第三行到第四行的推导
-->IntLiteral + IntLiteral * multiplicativeExpression
是否应该是
-->IntLiteral + multiplicativeExpression * IntLiteral
因为上面定义的multiplicativeExpression只包含了左边multiplicativeExpression star IntLiteral，却没有包含IntLiteral star multiplicativeExpression。作者回复: 你提得很对。
可能是从右递归的推导过程拷贝过来，没改彻底。
谢谢！2019-08-19 1 2
恩佐https://github.com/shaojintian/learn_compiler/blob/master/calculator/calculator_test.go
老师我完全自己实现了calculator，可否看一下，指点一下，多谢作者回复: 看到你的工程经常更新，我已经在github上加了关注。
简单地用go test运行了一下你的lexer和calculator。运行的输出挺漂亮!
如果有小的建议的话，就是再稍微多写点注释。否则过一阵你自己看代码会想不起来了...2019-11-07 1 1
MCadditionSubtractionExpression //加法、减法的表达式的规则
: multiplyDivideExpression //乘法、除法的表达式规则，优先级高于加法、减法。
| multiplyDivideExpression Add additionSubtractionExpression //表达式 + 表达式
| multiplyDivideExpression Sub additionSubtractionExpression //表达式 - 表达式
;
multiplyDivideExpression //乘法、除法的表达式的规则
: primary_expression //一元表达式
| primary_expression Mul multiplyDivideExpression //表达式 * 表达式
| primary_expression Div multiplyDivideExpression //表达式 / 表达式
;
primary_expression //一元表达式的规则
: IntLiteral //int的字面量
;作者回复: 你补充了以后，很详细准确，但是太长了。乘法运算有时还要加上求余数的，越加越长。
所以有时候就用一个单词代表算了：
additive：代表有加有减。
multiplicative：代表乘、除、求余。
assignment：代表=，+=， -=， *=， /=...2019-10-25 1
陈越最近在做leetcode，所有与树相关的题目都可以用递归解决，虽然有些也可以用栈或队列解决，但使用递归的代码真的更简洁。
另外，记得当年看盗梦空间的时候，心里就想，这不就是递归吗:D作者回复: 感谢分享！
是的，递归的最大优点就是直观、简洁。
当然，如果递归嵌套层数太多，系统开销会比较大。这个时候需要改写和优化。对于嵌套层数有限的场景，用递归就行了。2019-09-12 1
SUNFEI宫老师，看了几遍，还是没有理解 下面所表达的含义。
它的左边是一个非终结符（Non-terminal）。右边是它的产生式（Production Rule）。在语法解析的过程中，左边会被右边替代。如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符（Terminal）。
谢谢。作者回复: 这个地方确实写得不够细，没有交代清楚什么是非终结符，什么是终结符。后来在下一讲里有更多的描述。
总体来说，终结符，就是我们在词法分析阶段获得的Token。在建立AST的时候，它们是叶子节点。因为不管是表达式也好，语句也好，最终都是由这些Token构成的。
非终结符就相当于AST非叶子节点，它们是由Token构成的一些语法结构，比如表达式、语句。
如果把AST这种直观的理解换成文法的推导过程，那么就是反着来的。从非终结符一步步替换，直到全部替换成终结符。也就是从树根，一步步生成一棵AST。2019-09-03 1 1
鱼_XueTr写了几个Antlr的语法，然后回来再看，终于看着有感觉了。作者回复: 是的。
学习也是这么多次迭代的过程。
前面的即使学了，可能也隔着一层。等学到后面，再回过头来看前面，会有新的体会。
这就是最宝贵的直觉。是我们课程里着力培养的。就是你说的“感觉”。有了直觉，直观的理解一件事情了，再去细究，就不难了！2019-08-27 1