04 | 语法分析（二）：解决二元表达式中的难点

作者回复: 对。总结得很好！描述得很直观。 改写左递归的算法，实际上是有公式的。限于篇幅，我没有去陷入这个公式的细节。 在编译原理里面还有很多这样的细节。我希望能在后续出的书里都包含到，并且仍然保持容易理解。

作者回复: 你往深里又想了一层，探究背后的why，这很好，值得肯定！所以，我也拿出比较多的篇幅来回复你的问题。 1.为什么可以改写文法。 这其实有个前提，就是存在多个文法能生成相同语句。你可能有这样的经验，当需要写一个正则表达式来匹配字符串的时候，你能写出多个等价的正则表达式。对于上下文无关文法也一样，存在多个文法，能生成相同模式的语句。 既然存在等价的文法，那么自然可以去选择一个文法，能够更好的与某个算法去适配。LL算法是不能处理左递归的，那么就找到一个等价的文法，并且避免左递归就好了。 需要注意的是，虽然多个文法可以生成相同的语句，但是生成过程是不一样的。这也就导致解析树是不一样的。所以，有时候需要把解析树重新变换，来生成AST。 2.为什么想到EBNF EBNF实际上等价于产生式，只不过写法不一样而已。实际上有很多跟EBNF等价的文法书写方式。它们都是用来描述一种语言的结构，或者是一种文档（如XML文档）的结构的，所以它们也被叫做元语言（Metalanguage）。我在后面的元编程一章对Meta的级别有阐述，你也可以看一下。 所以，你的问题实际就变成了，为什么一个语言的文法会想到用产生式或者EBNF来描述。 实际上，一门语言不是必须用产生式或EBNF来描述的。有些类型的语言用其他方式描述更简单和方便，比如Indexed Language（https://en.wikipedia.org/wiki/Indexed_language）。不过，对于大多数计算机语言来说，用上下文无关文法描述是比较合适的，而上下文无关文法采用的是一种字符串重写规则（String Rewiting System, SRS）,也就是把一个字符串中的一部分不断地替换成另外的字符串。采用这种工具没有别的原因，就是因为它在描述语言的语法方面是很有效的。如果你追求它的数学根基，你可以去看半图厄理论，在数理逻辑里有。 SRS这种工具出现的历史比较早，最早是用来研究自然语言的。后来，在逻辑学（作为哲学的一部分）、数学中也得到了广泛的使用。比如现代数学的公理化运动，也就是把数学（比如欧几里得几何）看做一个形式系统；把数学定理的推导，看做是一个纯粹的形式化的变换过程。所以，它首先需要一门形式化的语言来描述数学中的命题，然后再基于一套推导逻辑去变换它们。然后再来看是否在有限的时间内一定能够推导出来，这也就是图灵的停机问题。 总结起来，我们在编译原理里面用到了一些形式语言方面的工具，它是被数学、语言学、逻辑学等多个学科共享的。它们都认为，该学科被研究的对象某种意义上是一些纯形式的变换。这种严谨的形式变换的过程，构筑了西方现代科学的严密推理体系，是那么多科学发现的底层根基。从这个角度，你其实可以体会到编译原理搞的是很基础的东西，是这个世界的一些底层的思维逻辑。 再次非常肯定你的思考精神。通过这种思考，你可以越挖越深，这个过程非常有趣。而且，你挖到一定程度，会发现很多知识体系都是通着的。比如，通过今天的探讨，你已经知道现代数学和编译原理是通着的。顺着这条线，你还会发现更多通着的知识。比如，逻辑学和集成电路的底层是通着的；计算机的底层逻辑跟数学的底层逻辑是一回事；计算过程又跟物理学的某些原理是一回事。很有意思。

作者回复: 我给你解释一下吧： 以 add -> mul | add + mul 为例， -> 意思是推导出； | 意思是“或者” 这个加号，我回头修改一下吧，可以用引号引起来，'+'只是匹配一个+号字符的意思，没有别的意思。 所以，这个产生式的意思是： 加法表达式，要么是一个乘法表达式，要么是一个加法表达式，后面跟个+号，然后再跟一个乘法表达式。 参考书的话，看看这个链接：https://time.geekbang.org/column/article/125948

作者回复: 转化成EBNF：add ::= mul ( '+' mul)* 一个表达式就解决了，更简洁。不需要add'了。 推导过程，要看算法。每种算法采用的推导过程是不一样的。如果用递归下降算法，推导：2+3*5 我们按照调用过程分成几层： 第1层：采用 mul add'，因为mul能完整的匹配2，不能再往后匹配了，所以第一个子节点建立完毕。接着用add'去建立第二个子节点。 第2层：运用add'的第一个产生式，先匹配上了+号，之后去匹配mul，也就是3*5，也是成功的。然后再去匹配add'。 第3层：这次用add'的时候，还是先尝试第一个产生式，失败。为什么呢？因为没有+号。回溯。尝试第二个产生式，即epsilon。也就是返回空。那么第3层就完成了。 第3层成功后第2层，第2层也就成功完成了。 同理，返回第1层，第1层也成功。 这个过程是否听得清楚？ 可以换着不同的例子多推导几遍，就会变得很熟练了！

作者回复: 是的。 我们通过改写规则的方法，能够避免左递归，但无法同时照顾结合性。这是很多教科书都没有提到的一件事情。 好在，这个事情比较简单，因为改写后的规则，是多了一个标准的“尾巴”。对，很多人都称呼它为尾巴。这个尾巴可以特别处理。 也就是说，结合性的信息已经不是单纯通过上下文无关文法提供了，要辅助额外的信息。 无独有偶，还有的作者用别的方法来解决算法优先级问题，比如LLVM的一个初学者教程，用的也是标注算符优先级的方法，也要在文法的基础上提供额外的信息给算法。 http://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html 本课程讲究实践。在实践中才会看到这些教科书上讲不到的点，但在面对实际问题时必须要解决。

作者回复: 有道理！用EBNF的话，+号有特殊含义。 我们修改一下文稿。 谢谢你的建议，你很细心，并且自己去做研究了！

作者回复: 嗯，你总结出了其中的要点！ 后面的课程里，还有别的方法来破除这些障碍，比如LR算法不怕左递归。 在另一门课，《编译原理实战课》中，你会看到常用语言其实用一个很优雅的运算符优先级算法就能解决常见的二元运算的表达式的解析问题。

作者回复: 好的，我对于公式推导过程再加个图。加完了在回复中告诉你。 你指的是用： add -> mul add' add' -> + mul add' | ε 来推导2+3+4的过程不清楚吗？

作者回复: 厉害！点赞！

作者回复: 是，没错。