03 | 语法分析（一）：纯手工打造公式计算器
该思维导图由 AI 生成，仅供参考
解析变量声明语句：理解“下降”的含义
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了如何手工打造一个公式计算器，通过语法分析的原理和递归下降算法来实现。作者首先解析了变量声明语句的语法，以及如何用上下文无关文法描述算术表达式。在解析变量声明语句时，作者使用了伪代码和实际代码示例，详细说明了算法的执行过程。同时，作者还介绍了上下文无关文法的概念，并通过示例展示了如何描述算术表达式的文法规则。文章深入浅出地介绍了语法分析的原理和算法，对于想要了解语法分析的读者来说，是一篇很有价值的文章。 在讲解上下文无关文法时，作者提到了文法的递归调用，以及递归下降算法的原理。通过示例和算法实现，作者详细解释了递归下降算法中的“下降”和“递归”特点，并探讨了左递归问题的解决方法。 此外，文章还介绍了如何基于抽象语法树（AST）对表达式进行求值，展示了深度优先遍历的递归算法。通过对AST的遍历，实现了对表达式的求值，加深了对计算机程序执行机制的理解。 总的来说，本文通过深入讲解语法分析原理和递归下降算法，以及实现表达式求值的过程，为读者提供了一篇技术深度和实用性兼具的文章。
《编译原理之美》，新⼈⾸单¥59
全部留言(110)
- 最新
- 精选
Sam置顶初学者看了 8 遍, 终于看懂了, 不急不燥, 慢慢看就行了作者回复: 点赞！
2019-08-22595
许童童老师你好， 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-199109
阿尔伯特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-051357
鸠摩智老师您好，请问语法和文法有什么区别和联系？作者回复: 你提的问题特别好！其他同学可能也会有这种疑问。 文法，英文叫做Grammar，是形式语言（Formal Language）的一个术语。所以也有Formal Grammar这样的说法。这里的文法有定义清晰的规则。比如，我们的词法规则、语法规则和属性规则，使用形式文法来定义的。我们的课程里讲解了正则文法(Regular Grammar)、上下文无关文法(Context-free Grammar)等不同的文法规则，用来描述词法和语法。 语法分析中的这个语法，英文是Syntax，主要是描述词是怎么组成句子的。一个语言的语法规则，通常指的是这个Syntax。 问题是，Grammar这个词，在中文很多应用场景中也叫做语法。这是会引起混淆的地方。我们在使用的时候要小心一点就行了。 比如，我做了一个规则文件，里面都是一些词法规则（Lexer Grammar），我会说，这是一个词法规则文件，或者词法文法文件。这个时候，把它说成是一个语法规则文件，就有点含义模糊。因为这里面并没有语法规则（Syntax Grammar）。 为你的认真思考点赞！
2019-08-19446
长方体混凝土移动工程师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）推导的算法。也就是总是先把左边的非终结符展开。而且是深度优先的。 你再广度优先推演一下看看？ 你再最右推导一下看看？ 可能你的感受又不一样。很有意思的。可以作为消遣游戏 :-D
2019-08-22842
张辽儿为什么出现左递归无限调用我还没有理解，例如2+3；当进入加法表达式递归的时候，参数不是已经变成了2吗，然后就是乘法表达式，最后形成字面常量。请老师解答下我的疑问，谢谢作者回复: 为了方便讨论，我们把规则简化一下，去掉乘法那一层。否则在乘法那就已经无限递归下去了。修改后为： additive -> IntLiteral | additive Intliteral ; 我们假设是最左推导，也就是总是先展开左边的非中介符。 第一遍：additive->IntLiteral，但因为后面还有Token没处理完，所以这个推导过程会失败，要退回来。 这可能是你没理解的地方。我们是要用additive匹配整个Token串，而不仅仅是第一个Token。 第二遍：用第二个产生式，additive->additive->IntLiteral，还是一样失败。 第三遍：additive->additive->additive->IntLiteral。 第四遍：.... 这样说，有没有帮助？
2019-08-20827
炎发灼眼老师，又把文章读了好几遍，然后仔仔细细看了你所有问题的回复，重新理解了下，是不是这样； 例如：2+3这个式子，用A->Int | A + Int去推导，就是用2+3去匹配第一个式子Int，不满足，然后看是否满足第二个式子A + Int， 这个时候，因为我们能直接看到整个表达式是什么样子的，现在是2+3，所以我们本能的就使用了广度优先算法，觉得用2匹配A，+自然匹配，Int刚好消耗掉3，完美； 但是计算机拿到TOKENS的时候，是不知道这个是什么样子的，所以按照写好的深度优先算法来匹配，每一次的匹配，都想尽办法尽可能多的 消耗掉TOKENS中的TOKEN，所以，在A + Int的时候，用整个TOKENS来和A匹配，看看最多能消耗掉多少个TOKEN，其实这个时候， 对于计算机来说，是不知道这个式子后面还有 + Int这个的，然后回到了那一步，先用TOKENS匹配Int，不对，退回来，进行另一个式子的尝试， 又回到了A + Int，然后又是对A + Int中的A进行尽可能的多匹配，周而复始，就是所谓的左递归了作者回复: 不错。你已经思考得挺细致的了！值得表扬！ 如果你想继续做一下脑体操，可以看看17讲中与广度优先有关的算法，看看能否把深度优先和广度优先在大脑里转换自如！
2020-04-11425
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-21720- 阿名如果没有基础 比较难听得懂 比如文法推导 终结符 非终结符 这些概念 本身就不好理解
作者回复: 实际上，这些看上去比较正式的术语，是我在这篇文稿的最后一版才加上去的。其实，你忽略这些术语，也完全能看懂文稿。加上这些术语，是为后面正式讲算法做个铺垫。 我知道编译原理的术语本身就能吓倒很多人。但是这门课程的重点在于帮你建立直觉（Intuition）。建立起直觉来以后，你其实已经明白了语法分析的过程，你已经对它有熟悉感了。之后你再把这些直觉跟术语联系在一起，就不觉得困难了。 再次强调一点，首先建立直觉，然后再追求对术语和算法的严格理解。 学编译原理最大的困难不是这门课本身的难度，而是我们对它的畏惧心理。相信你自己！
2019-08-19317 
Rockbean小白读得有些吃力 > "我们首先把变量声明语句的规则，用形式化的方法表达一下。它的左边是一个非终结符（Non-terminal）。右边是它的产生式（Production Rule）。" “它的左边”的“它”是指变量声明语句"int age = 45"呢还是什么，如果是变量声明语句,那左边是左到哪里，是“int age”还是什么？非终结符，是什么，往前翻了几个课也没有找到，或者说终结符是什么？同样的右边是右从哪里开始算右边？产生式是“=45”吗？小白对这些基础词汇有点蒙，见笑了作者回复: 1.终结符跟非终结符在04讲得更细一点，可以在04讲再体会一下。 2.它的左边，是指： intDeclaration : Int Identifier ('=' additiveExpression)?; 这个规则，冒号的左边。
2019-08-25211
