纯手工打造公式计算器：从语法分析到递归下降算法
纯手工打造公式计算器：从语法分析到递归下降算法
本文将带你手工打造一个公式计算器，通过语法分析的原理和递归下降算法来实现。从变量声明语句的语法解析开始，逐步讲解上下文无关文法、递归下降算法以及表达式求值的过程。
解析变量声明语句：理解“下降”的含义
在编译器前端技术中，语法分析的结果是生成抽象语法树（AST）。递归下降算法是一种常见的自顶向下算法。我们先定义变量声明语句的文法：
intDeclaration : Int Identifier ('=' additiveExpression)?;
将其翻译成程序语句的伪代码：
//伪代码
MatchIntDeclare(){
MatchToken(Int); //匹配Int关键字
MatchIdentifier(); //匹配标识符
MatchToken(equal); //匹配等号
MatchExpression(); //匹配表达式
}
实际代码示例：
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 后面的变量名称，再看后面是否跟了初始化部分，即等号加一个表达式。检查是否有等号，有的话，接着匹配一个表达式。
通常会对产生式的每个部分建立一个子节点，但这里做了简化，只生成了一个子节点，变量名称记到 ASTNode 的文本值里去了。
运行这个示例程序，输出 AST：
Programm Calculator
IntDeclaration age
AssignmentExp =
IntLiteral 45
用上下文无关文法描述算术表达式
算术表达式需要包含加法和乘法两种运算，加法和乘法运算有不同的优先级。规则要能匹配各种可能的算术表达式：
additiveExpression
: multiplicativeExpression
| additiveExpression Plus multiplicativeExpression
;
multiplicativeExpression
: IntLiteral
| multiplicativeExpression Star IntLiteral
;
通过文法的嵌套，实现对运算优先级的支持。解析“2 + 3 * 5”这个算术表达式时会形成类似下面的 AST：
为了完成对根节点的求值，需要对下级节点递归求值，所以先完成“3 * 5 = 15”，然后再计算“2 + 15 = 17”。
解析算术表达式：理解“递归”的含义
在讲解上下文无关文法时，提到了文法的递归调用。为了解决左递归问题，可以将“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;
}
同样的，乘法的文法规则也可以做类似的改写：
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 做求值运算。这个计算过程比较简单，只需要对这棵树做深度优先的遍历就好了。
以上文中“2 + 3 * 5”的 AST 为例：
对表达式的求值，等价于对 AST 根节点求值。首先求左边子节点，算出是 2。接着对右边子节点求值，这时候需要递归计算下一层。计算完了以后，返回是 15（3*5）。把左右节点相加，计算出根节点的值 17。
代码参见 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
课程小结
初步了解上下文无关文法，知道它能表达主流的计算机语言，以及与正则文法的区别。理解递归下降算法中的“下降”和“递归”两个特点。通过遍历 AST 对表达式求值，加深对计算机程序执行机制的理解。
在后面的课程中，我们会在此基础上逐步深化，比如在变量声明中可以使用表达式，在表达式中可以使用变量，例如能够执行像这样的语句：
int A = 17；
int B = A + 10*2;
实现了上述功能以后，这个程序就越来越接近一个简单的脚本解释器了！当然，在此之前，我们还必须解决左递归的问题。所以下一讲，会带你填掉左递归这个坑。我们学习和工作的过程，就是在不停地挖坑、填坑，要有信心，只要坚强走过填坑这段路，职业生涯将会愈发平坦！
一课一思
递归算法是很好的自顶向下解决问题的方法，是计算机领域的一个核心的思维方式。拥有这种思维方式，可以说是程序员相对于非程序员的一种优势。那么，你是否用递归算法或递归思维解决过工作中或者生活中存在的某些问题？你能否再找一些证据证明一下，哪些语法规则只能用上下文无关文法表达，用正则文法是怎样都写不出来的？
另外，为了便于更好地学习，将本节课的示例程序放到了码云和GitHub上，你可以看一下。
本文原文来自CSDN