时长15:25大小14.14M
我想你应该知道,公式是 Excel 电子表格软件的灵魂和核心。除此之外,在 HR 软件中,可以用公式自定义工资。而且,如果你要开发一款通用报表软件,也会大量用到自定义公式来计算报表上显示的数据。总而言之,很多高级一点儿的软件,都会用到自定义公式功能。
既然公式功能如此常见和重要,我们不妨实现一个公式计算器,给自己的软件添加自定义公式功能吧!
本节课将继续“手工打造”之旅,让你纯手工实现一个公式计算器,借此掌握语法分析的原理和递归下降算法(Recursive Descent Parsing),并初步了解上下文无关文法(Context-free Grammar,CFG)。
我所举例的公式计算器支持加减乘除算术运算,比如支持“2 + 3 * 5”的运算。
在学习语法分析时,我们习惯把上面的公式称为表达式。这个表达式看上去很简单,但你能借此学到很多语法分析的原理,例如左递归、优先级和结合性等问题。
当然了,要实现上面的表达式,你必须能分析它的语法。不过在此之前,我想先带你解析一下变量声明语句的语法,以便让你循序渐进地掌握语法分析。
在“01 | 理解代码:编译器的前端技术”里,我提到语法分析的结果是生成 AST。算法分为自顶向下和自底向上算法,其中,递归下降算法是一种常见的自顶向下算法。
与此同时,我给出了一个简单的代码示例,也针对“int age = 45”这个语句,画了一个语法分析算法的示意图:
我们首先把变量声明语句的规则,用形式化的方法表达一下。它的左边是一个非终结符(Non-terminal)。右边是它的产生式(Production Rule)。在语法解析的过程中,左边会被右边替代。如果替代之后还有非终结符,那么继续这个替代过程,直到最后全部都是终结符(Terminal),也就是 Token。只有终结符才可以成为 AST 的叶子节点。这个过程,也叫做推导(Derivation)过程:
intDeclaration : Int Identifier ('=' additiveExpression)?;复制代码
你可以看到,int 类型变量的声明,需要有一个 Int 型的 Token,加一个变量标识符,后面跟一个可选的赋值表达式。我们把上面的文法翻译成程序语句,伪代码如下:
// 伪代码 MatchIntDeclare(){ MatchToken(Int); // 匹配 Int 关键字 MatchIdentifier(); // 匹配标识符 MatchToken(equal); // 匹配等号 MatchExpression(); // 匹配表达式 }复制代码
实际代码在 SimpleCalculator.java 类的 IntDeclare() 方法中:
SimpleASTNode node = null; Token token = tokens.peek(); // 预读 if (token != null && token.getType() == TokenType.Int) { // 匹配 Int token = tokens.read(); // 消耗掉 int if (tokens.peek().getType() == TokenType.Identifier) { // 匹配标识符 token = tokens.read(); // 消耗掉标识符 // 创建当前节点,并把变量名记到 AST 节点的文本值中, // 这里新建一个变量子节点也是可以的 node = new SimpleASTNode(ASTNodeType.IntDeclaration, token.getText()); token = tokens.peek(); // 预读 if (token != null && token.getType() == TokenType.Assignment) { tokens.read(); // 消耗掉等号 SimpleASTNode child = additive(tokens); // 匹配一个表达式 if (child == null) { throw new Exception("invalide variable initialization, expecting an expression"); } else{ node.addChild(child); } } } else { throw new Exception("variable name expected"); } }复制代码
直白地描述一下上面的算法:
解析变量声明语句时,我先看第一个 Token 是不是 int。如果是,那我创建一个 AST 节点,记下 int 后面的变量名称,然后再看后面是不是跟了初始化部分,也就是等号加一个表达式。我们检查一下有没有等号,有的话,接着再匹配一个表达式。
我们通常会对产生式的每个部分建立一个子节点,比如变量声明语句会建立四个子节点,分别是 int 关键字、标识符、等号和表达式。后面的工具就是这样严格生成 AST 的。但是我这里做了简化,只生成了一个子节点,就是表达式子节点。变量名称记到 ASTNode 的文本值里去了,其他两个子节点没有提供额外的信息,就直接丢弃了。
另外,从上面的代码中我们看到,程序是从一个 Token 的流中顺序读取。代码中的 peek() 方法是预读,只是读取下一个 Token,但并不把它从 Token 流中移除。在代码中,我们用 peek() 方法可以预先看一下下一个 Token 是否是等号,从而知道后面跟着的是不是一个表达式。而 read() 方法会从 Token 流中移除,下一个 Token 变成了当前的 Token。
这里需要注意的是,通过 peek() 方法来预读,实际上是对代码的优化,这有点儿预测的意味。我们后面会讲带有预测的自顶向下算法,它能减少回溯的次数。
我们把解析变量声明语句和表达式的算法分别写成函数。在语法分析的时候,调用这些函数跟后面的 Token 串做模式匹配。匹配上了,就返回一个 AST 节点,否则就返回 null。如果中间发现跟语法规则不符,就报编译错误。
在这个过程中,上级文法嵌套下级文法,上级的算法调用下级的算法。表现在生成 AST 中,上级算法生成上级节点,下级算法生成下级节点。这就是“下降”的含义。
分析上面的伪代码和程序语句,你可以看到这样的特点:程序结构基本上是跟文法规则同构的。这就是递归下降算法的优点,非常直观。
接着说回来,我们继续运行这个示例程序,输出 AST:
Programm Calculator IntDeclaration age AssignmentExp = IntLiteral 45复制代码
前面的文法和算法都很简单,这样级别的文法没有超出正则文法。也就是说,并没有超出我们做词法分析时用到的文法。
好了,解析完变量声明语句,带你理解了“下降”的含义之后,我们来看看如何用上下文无关文法描述算术表达式。
我们解析算术表达式的时候,会遇到更复杂的情况,这时,正则文法不够用,我们必须用上下文无关文法来表达。你可能会问:“正则文法为什么不能表示算术表达式?”别着急,我们来分析一下算术表达式的语法规则。
算术表达式要包含加法和乘法两种运算(简单起见,我们把减法与加法等同看待,把除法也跟乘法等同看待),加法和乘法运算有不同的优先级。我们的规则要能匹配各种可能的算术表达式:
思考一番之后,我们把规则分成两级:第一级是加法规则,第二级是乘法规则。把乘法规则作为加法规则的子规则,这样在解析形成 AST 时,乘法节点就一定是加法节点的子节点,从而被优先计算。
additiveExpression : multiplicativeExpression | additiveExpression Plus multiplicativeExpression ; multiplicativeExpression : IntLiteral | multiplicativeExpression Star IntLiteral ;复制代码
你看,我们可以通过文法的嵌套,实现对运算优先级的支持。这样我们在解析“2 + 3 * 5”这个算术表达式时会形成类似下面的 AST:
如果要计算表达式的值,只需要对根节点求值就可以了。为了完成对根节点的求值,需要对下级节点递归求值,所以我们先完成“3 * 5 = 15”,然后再计算“2 + 15 = 17”。
有了这个认知,我们在解析算术表达式的时候,便能拿加法规则去匹配。在加法规则中,会嵌套地匹配乘法规则。我们通过文法的嵌套,实现了计算的优先级。
应该注意的是,加法规则中还递归地又引用了加法规则。通过这种递归的定义,我们能展开、形成所有各种可能的算术表达式。比如“2+3*5” 的推导过程:
-->additiveExpression + multiplicativeExpression -->multiplicativeExpression + multiplicativeExpression -->IntLiteral + multiplicativeExpression -->IntLiteral + multiplicativeExpression * IntLiteral -->IntLiteral + IntLiteral * IntLiteral复制代码
这种文法已经没有办法改写成正则文法了,它比正则文法的表达能力更强,叫做“上下文无关文法”。正则文法是上下文无关文法的一个子集。它们的区别呢,就是上下文无关文法允许递归调用,而正则文法不允许。
上下文无关的意思是,无论在任何情况下,文法的推导规则都是一样的。比如,在变量声明语句中可能要用到一个算术表达式来做变量初始化,而在其他地方可能也会用到算术表达式。不管在什么地方,算术表达式的语法都一样,都允许用加法和乘法,计算优先级也不变。好在你见到的大多数计算机语言,都能用上下文无关文法来表达它的语法。
那有没有上下文相关的情况需要处理呢?也是有的,但那不是语法分析阶段负责的,而是放在语义分析阶段来处理的。
在讲解上下文无关文法时,我提到了文法的递归调用,你也许会问,是否在算法上也需要递归的调用呢?要不怎么叫做“递归下降算法”呢?
的确,我们之前的算法只算是用到了“下降”,没有涉及“递归”,现在,我们就来看看如何用递归的算法翻译递归的文法。
我们先按照前面说的,把文法直观地翻译成算法。但是,我们遇到麻烦了。这个麻烦就是出现了无穷多次调用的情况。我们来看个例子。
为了简单化,我们采用下面这个简化的文法,去掉了乘法的层次:
additiveExpression : IntLiteral | additiveExpression Plus IntLiteral ;复制代码
在解析 “2 + 3”这样一个最简单的加法表达式的时候,我们直观地将其翻译成算法,结果出现了如下的情况:
“additiveExpression Plus multiplicativeExpression”这个文法规则的第一部分就递归地引用了自身,这种情况叫做左递归。通过上面的分析,我们知道左递归是递归下降算法无法处理的,这是递归下降算法最大的问题。
怎么解决呢?把“additiveExpression”调换到加号后面怎么样?我们来试一试。
additiveExpression : multiplicativeExpression | multiplicativeExpression Plus additiveExpression ;复制代码
我们接着改写成算法,这个算法确实不会出现无限调用的问题:
private SimpleASTNode additive(TokenReader tokens) throws Exception { SimpleASTNode child1 = multiplicative(); // 计算第一个子节点 SimpleASTNode node = child1; // 如果没有第二个子节点,就返回这个 Token token = tokens.peek(); if (child1 != null && token != null) { if (token.getType() == TokenType.Plus) { token = tokens.read(); SimpleASTNode child2 = additive(); // 递归地解析第二个节点 if (child2 != null) { node = new SimpleASTNode(ASTNodeType.AdditiveExp, token.getText()); node.addChild(child1); node.addChild(child2); } else { throw new Exception("invalid additive expression, expecting the right part."); } } } return node; }复制代码
为了便于你理解,我解读一下上面的算法:
我们先尝试能否匹配乘法表达式,如果不能,那么这个节点肯定不是加法节点,因为加法表达式的两个产生式都必须首先匹配乘法表达式。遇到这种情况,返回 null 就可以了,调用者就这次匹配没有成功。如果乘法表达式匹配成功,那就再尝试匹配加号右边的部分,也就是去递归地匹配加法表达式。如果匹配成功,就构造一个加法的 ASTNode 返回。
同样的,乘法的文法规则也可以做类似的改写:
multiplicativeExpression : IntLiteral | IntLiteral Star multiplicativeExpression ;复制代码
现在我们貌似解决了左递归问题,运行这个算法解析 “2+3*5”,得到下面的 AST:
Programm Calculator AdditiveExp + IntLiteral 2 MulticativeExp * IntLiteral 3 IntLiteral 5复制代码
是不是看上去一切正常?可如果让这个程序解析“2+3+4”呢?
Programm Calculator AdditiveExp + IntLiteral 2 AdditiveExp + IntLiteral 3 IntLiteral 4复制代码
问题是什么呢?计算顺序发生错误了。连续相加的表达式要从左向右计算,这是加法运算的结合性规则。但按照我们生成的 AST,变成从右向左了,先计算了“3+4”,然后才跟“2”相加。这可不行!
为什么产生上面的问题呢?是因为我们修改了文法,把文法中加号左右两边的部分调换了一下。造成的影响是什么呢?你可以推导一下“2+3+4”的解析过程:
所以,我们前面的方法其实并没有完美地解决左递归,因为它改变了加法运算的结合性规则。那么,我们能否既解决左递归问题,又不产生计算顺序的错误呢?答案是肯定的。不过我们下一讲再来解决它。目前先忍耐一下,凑合着用这个“半吊子”的算法吧。
上面帮助你理解了“递归”的含义,接下来,我要带你实现表达式的求值。其实,要实现一个表达式计算,只需要基于 AST 做求值运算。这个计算过程比较简单,只需要对这棵树做深度优先的遍历就好了。
深度优先的遍历也是一个递归算法。以上文中“2 + 3 * 5”的 AST 为例看一下。
代码参见 SimpleCalculator.Java 中的 evaluate() 方法。
还是以“2+3*5”为例。它的求值过程输出如下,你可以看到求值过程中遍历了整棵树:
Calculating: AdditiveExp // 计算根节点 Calculating: IntLiteral // 计算第一个子节点 Result: 2 // 结果是 2 Calculating: MulticativeExp // 递归计算第二个子节点 Calculating: IntLiteral Result: 3 Calculating: IntLiteral Result: 5 Result: 15 // 忽略递归的细节,得到结果是 15 Result: 17 // 根节点的值是 17复制代码
你可以运行一下示例程序看看输出结果,而且我十分建议你修改表达式,自己做做实验,并试着让表达式不符合语法,看看语法分析程序能不能找出错误来。
今天我们实现了一个简单的公式计算器,尽管简单,相信你已经有了收获。那么我来总结一下今天的重点:
在后面的课程中,我们会在此基础上逐步深化,比如在变量声明中可以使用表达式,在表达式中可以使用变量,例如能够执行像这样的语句:
int A = 17; int B = A + 10*2;复制代码
实现了上述功能以后,这个程序就越来越接近一个简单的脚本解释器了!当然,在此之前,我们还必须解决左递归的问题。所以下一讲,我会带你填掉左递归这个坑。我们学习和工作的过程,就是在不停地挖坑、填坑,你要有信心,只要坚强走过填坑这段路,你的职业生涯将会愈发平坦!
递归算法是很好的自顶向下解决问题的方法,是计算机领域的一个核心的思维方式。拥有这种思维方式,可以说是程序员相对于非程序员的一种优势。
那么,你是否用递归算法或递归思维解决过工作中或者生活中存在的某些问题?你能否再找一些证据证明一下,哪些语法规则只能用上下文无关文法表达,用正则文法是怎样都写不出来的? 欢迎在留言区和我一起讨论。
最后,十分感谢你的阅读,如果这篇文章让你有所收获,也欢迎你将它分享给更多的朋友。
另外,为了便于你更好地学习,我将本节课的示例程序放到了码云和GitHub上,你可以看一下。
作者回复: 点赞!
作者回复: 这个实际上就是语法规则,是用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
上面这些不同的写法,都是等价的。你要能够看习惯,在不同的写法中自由切换。
不知道是否解答了你的疑问。
作者回复: 实际上,这些看上去比较正式的术语,是我在这篇文稿的最后一版才加上去的。其实,你忽略这些术语,也完全能看懂文稿。加上这些术语,是为后面正式讲算法做个铺垫。
我知道编译原理的术语本身就能吓倒很多人。但是这门课程的重点在于帮你建立直觉(Intuition)。建立起直觉来以后,你其实已经明白了语法分析的过程,你已经对它有熟悉感了。之后你再把这些直觉跟术语联系在一起,就不觉得困难了。
再次强调一点,首先建立直觉,然后再追求对术语和算法的严格理解。
学编译原理最大的困难不是这门课本身的难度,而是我们对它的畏惧心理。相信你自己!
作者回复: 你提的问题特别好!其他同学可能也会有这种疑问。
文法,英文叫做Grammar,是形式语言(Formal Language)的一个术语。所以也有Formal Grammar这样的说法。这里的文法有定义清晰的规则。比如,我们的词法规则、语法规则和属性规则,使用形式文法来定义的。我们的课程里讲解了正则文法(Regular Grammar)、上下文无关文法(Context-free Grammar)等不同的文法规则,用来描述词法和语法。
语法分析中的这个语法,英文是Syntax,主要是描述词是怎么组成句子的。一个语言的语法规则,通常指的是这个Syntax。
问题是,Grammar这个词,在中文很多应用场景中也叫做语法。这是会引起混淆的地方。我们在使用的时候要小心一点就行了。
比如,我做了一个规则文件,里面都是一些词法规则(Lexer Grammar),我会说,这是一个词法规则文件,或者词法文法文件。这个时候,把它说成是一个语法规则文件,就有点含义模糊。因为这里面并没有语法规则(Syntax Grammar)。
为你的认真思考点赞!
作者回复: 你说的很对!
实际上,你提到了递归的优化问题。这是一个专门的研究领域。在SICP(《计算机程序的构造和解释》)这本书中,对这个问题也很重视。
我们下一讲会提到尾递归的情形,也就是线性迭代的递归函数。它实际上可以转化成循环语句,就没有对栈的消耗了。这是在编译技术中常用的一种优化策略。你可以提前了解一下尾递归 : )
作者回复: 为了方便讨论,我们把规则简化一下,去掉乘法那一层。否则在乘法那就已经无限递归下去了。修改后为:
additive -> IntLiteral | additive Intliteral ;
我们假设是最左推导,也就是总是先展开左边的非中介符。
第一遍:additive->IntLiteral,但因为后面还有Token没处理完,所以这个推导过程会失败,要退回来。
这可能是你没理解的地方。我们是要用additive匹配整个Token串,而不仅仅是第一个Token。
第二遍:用第二个产生式,additive->additive->IntLiteral,还是一样失败。
第三遍:additive->additive->additive->IntLiteral。
第四遍:....
这样说,有没有帮助?
作者回复: 你提得很对。
可能是从右递归的推导过程拷贝过来,没改彻底。
谢谢!
作者回复: 点赞!
作者回复: 没错。很好。
既然你已经理解了,那么我再增加一点难度。当前推导是最左推导(LeftMost)推导的算法。也就是总是先把左边的非终结符展开。而且是深度优先的。
你再广度优先推演一下看看?
你再最右推导一下看看?
可能你的感受又不一样。很有意思的。可以作为消遣游戏 :-D
作者回复: 算法可以首先尝试产生式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)
这是严格的推导过程。我在示例代码的实现中,因为提取了左公因子,所以没用多次回溯。
这样说,你能明白吗?如果还不明白,就再问。
作者回复: 我觉得你在认真分析,点赞!
在讨论左递归会无穷次递归的时候,我们把语法简化了一下,是根本就不要乘法运算了,只看加法运算。这样来推演左递归更加方便一点。
简化后的规则为:
additive -> IntLiteral | additive Intliteral ;
解析过程:
第一遍:additive->IntLiteral,但因为后面还有Token没处理完,所以这个推导过程会失败,要退回来。
第二遍:additive->additive->IntLiteral,还是一样失败。
第三遍:additive->additive->additive->IntLiteral。
第四遍:....
Star就是*号,是一个Token符号。是词法分析过程中形成的。这样的问题建议你看看源代码,甚至运行一下,就更清楚了。
如果不清楚,继续问我。
作者回复: 学完课程,你应该会理解这两个的运作机制。
Babel,只是做语言翻译,只需要前端技术就可以了。翻译成AST,做完语义分析,再转成另一个版本的js。
Node.js基于v8,不仅仅做前端工作,更重要的是在后端运行时做各种优化。
作者回复: 嗯。谢谢你的建议。我看看是否需要把文稿表达得更细致一点。
如果不要乘法那一层,说明起来可能更简洁一些。否则,其实进入到乘法以后,就已经递归个不停了,根本回不到加法规则这来。
修改规则为:
additive -> IntLiteral | additive Intliteral ;
第一遍:additive->IntLiteral,但因为后面还有Token没处理完,所以这个推导过程会失败,要退回来。
第二遍:additive->additive->IntLiteral,还是一样失败。
第三遍:additive->additive->additive->IntLiteral。
第四遍:....
作者回复: 资料的推荐,请参考:
https://time.geekbang.org/column/article/125948
可以阅读一下参考书里对文法的描述。
无限调用,必须是在深度优先的算法里才会出现,递归下降是深度优先的。有另一个同学问我的时候,举的匹配过程其实是广度优先。
最好的办法,是动手编程试一试,就能更深刻理解为什么会出现左递归。
我尽量在答疑的那讲里把这个比较多次提的疑问再用更清晰的方式讲一遍。
作者回复: 1.终结符跟非终结符在04讲得更细一点,可以在04讲再体会一下。
2.它的左边,是指:
intDeclaration : Int Identifier ('=' additiveExpression)?;
这个规则,冒号的左边。
作者回复: 你要把文法规则和算法两件事情区分开。
同一个文法,用不同的算法去做,结果会不同。
文法规则当然是对的。但问题是算法,算法是按照一定的步骤去执行的。
你需要按照递归下降算法的逻辑去一步步推导一下。
作者回复: 哈哈!
你提供了一个很好的广度优先的自顶向下算法的例子。
递归下降算法是深度优先的。当你第二次试图用S匹配的时候,算法还是会试图匹配全部的Token,而不是只去匹配第一个Token。
我在第15讲里,把自顶向下的算法做梳理的时候,会提到这个广度优先算法。广度优先算法有好处,就是可以避免左递归。但它会导致更多次的回溯,是指数级上升的,所以没有实际用途。
而深度优先的递归下降算法,虽然会有左递归的毛病,但回溯次数不多,具有实际使用价值。
另外,动手写写算法验证一下马上就清楚了。
恭喜你,你可能比别的同学了解得更透彻!
作者回复: 上个星期刚发布了一个学习路径,请参考:
https://time.geekbang.org/column/article/125948
作者回复: 每次匹配失败以后,要把已经读出来的token再退回去,尝试别的产生式。这就是回溯。