1. 核心概念：抽象语法树 (AST) 与递归下降解析
在处理字符串表达式时，将其转换为一种结构化的数据表示形式是常见的做法，抽象语法树（abstract syntax tree, ast）便是其中一种。ast以树形结构表示程序代码的语法结构，每个节点代表源代码中的一个构造，例如操作符、操作数或表达式。这种结构便于后续的分析、优化或代码生成。
为了从字符串表达式构建AST，我们通常会采用解析技术。本教程将采用递归下降解析（Recursive Descent Parsing）方法。这是一种自顶向下的解析策略，通过一组递归函数来识别输入字符串中的语法结构。每个函数对应语法规则中的一个非终结符，并尝试匹配相应的终结符或调用其他函数来匹配子规则。
2. 数据结构：表达式节点
首先，我们需要定义一个数据结构来表示AST中的每个节点。一个表达式节点可以代表一个操作数（如变量a、b），也可以代表一个操作符（如+、-、*、/），并连接其左右操作数（如果适用）。
record Node(String name, Node left, Node right) {
@Override
public String toString() {
// 重写toString方法，便于打印和调试AST结构
return "Node[" + name
+ (left != null ? ", " + left : "")
+ (right != null ? ", " + right : "") + "]";
}
}Node记录包含三个字段：
- name: 节点的名称，对于操作数，它是变量名（如"a"）；对于操作符，它是操作符符号（如"+"）。
- left: 左子节点，通常是二元操作的左操作数或一元操作的唯一操作数。
- right: 右子节点，通常是二元操作的右操作数。
3. 解析器实现：递归下降算法
解析器的核心是一个parse方法，它将接收一个字符串表达式并返回其对应的AST根节点。我们将通过一个内部匿名对象来实现递归下降逻辑，这样可以方便地管理解析状态（如当前解析位置）。
立即学习“Java免费学习笔记（深入）”；
static Node parse(String input) {
return new Object() {
int index = 0; // 当前解析到的字符串位置
// 获取当前字符，如果已到达字符串末尾则返回-1
int ch() {
return index < input.length() ? input.charAt(index) : -1;
}
// 尝试消耗一个预期字符。会跳过空白字符。
// 如果当前字符与预期字符匹配，则消耗并返回true；否则返回false。
boolean eat(char expected) {
while (Character.isWhitespace(ch())) { // 跳过所有空白字符
++index;
}
if (ch() == expected) {
++index;
return true;
}
return false;
}
// 解析一个“因子”：可以是数字、变量、带括号的表达式或一元负号表达式
Node factor() {
Node node;
boolean minus = eat('-'); // 检查是否存在一元负号
if (eat('(')) { // 如果遇到左括号，则解析一个完整的表达式
node = expression();
if (!eat(')')) { // 确保有匹配的右括号
throw new RuntimeException("')' expected");
}
} else if (Character.isAlphabetic(ch())) { // 如果是字母，则认为是操作数
node = new Node(Character.toString(ch()), null, null);
++index;
} else { // 遇到未知字符，抛出异常
throw new RuntimeException("unknown char '" + (char)ch() + "'");
}
if (minus) { // 如果之前有一元负号，则将其作为操作符包裹住解析出的节点
node = new Node("-", node, null);
}
return node;
}
// 解析一个“表达式”：由一个或多个因子通过二元操作符连接而成
Node expression() {
Node node = factor(); // 首先解析左侧的因子
while (true) { // 循环处理后续的二元操作符及其右操作数
if (eat('*')) {
node = new Node("*", node, factor());
} else if (eat('/')) {
node = new Node("/", node, factor());
} else if (eat('+')) {
node = new Node("+", node, factor());
} else if (eat('-')) {
node = new Node("-", node, factor());
} else {
break; // 没有更多操作符，表达式解析完成
}
}
return node;
}
}.expression(); // 从解析最顶层的表达式开始
}3.1 辅助方法详解
- ch(): 这是一个简单的辅助方法，用于获取当前index位置的字符。如果index超出了字符串长度，则返回-1，表示已到达末尾。
- eat(char expected): 此方法是解析器的基石之一。它首先跳过所有遇到的空白字符，然后检查当前字符是否与expected匹配。如果匹配，它会递增index（即“吃掉”该字符）并返回true；否则返回false。
3.2 核心解析逻辑
-
factor() 方法：factor方法负责解析表达式中的最小单元。它处理以下几种情况：
- 一元负号 (-)： 如果在解析因子之前遇到-，minus标志会被设为true。解析完后续的表达式或操作数后，如果minus为true，则会创建一个以"-"为操作符，解析出的节点为左子节点的Node，表示一元负号操作。
- 带括号的表达式 ((expression))： 如果遇到(，factor会递归调用expression()来解析括号内的完整表达式，然后期望找到一个匹配的)。这确保了括号内的内容作为一个整体被处理，并维护了括号平衡。
- 操作数 (a, b等)： 如果当前字符是字母，它被视为一个操作数，并创建一个简单的Node。
- 错误处理： 如果遇到上述任何情况都不匹配的字符，则抛出RuntimeException。
-
expression() 方法：expression方法负责解析由二元操作符连接的因子。它的工作方式如下：
- 首先，它调用factor()来解析表达式的左侧部分。
- 然后，它进入一个循环，尝试识别并“吃掉”二元操作符（*, /, +, -）。
- 每当识别到一个操作符，它就会再次调用factor()来解析操作符的右侧操作数。
- 接着，它会创建一个新的Node，以当前识别的操作符为name，之前解析的node作为left子节点，新解析的factor作为right子节点。这个新的Node就成为了当前表达式的根节点，继续参与后续的解析。
- 循环会一直持续，直到没有更多的二元操作符可以识别。
关于操作符优先级： 值得注意的是，根据问题描述，此解析器不需要处理复杂的操作符优先级（例如乘除优先于加减），因为“如果存在多于一个二元操作，输入表达式将包含括号”。这意味着表达式如 a*b+c 将会以 (a*b)+c 或 a*(b+c) 的形式给出。因此，expression() 方法中按顺序检查 *, /, +, - 并进行左结合处理是足够的，它在当前上下文中 effectively 实现了所有二元操作符的左结合性。
4. 示例与测试
为了验证解析器的功能，我们可以编写一些测试用例，并打印解析结果的AST。
public class ExpressionParser {
record Node(String name, Node left, Node right) {
@Override
public String toString() {
return "Node[" + name
+ (left != null ? ", " + left : "")
+ (right != null ? ", " + right : "") + "]";
}
}
static Node parse(String input) {
return new Object() {
int index = 0;
int ch() { return index < input.length() ? input.charAt(index) : -1; }
boolean eat(char expected) {
while (Character.isWhitespace(ch())) ++index;
if (ch() == expected) {
++index;
return true;
}
return false;
}
Node factor() {
Node node;
boolean minus = eat('-');
if (eat('(')) {
node = expression();
if (!eat(')'))
throw new RuntimeException("')' expected");
} else if (Character.isAlphabetic(ch())) {
node = new Node(Character.toString(ch()), null, null);
++index;
} else
throw new RuntimeException("unknown char '" + (char)ch() + "'");
if (minus) node = new Node("-", node, null);
return node;
}
Node expression() {
Node node = factor();
while (true)
if (eat('*')) node = new Node("*", node, factor());
else if (eat('/')) node = new Node("/", node, factor());
else if (eat('+')) node = new Node("+", node, factor());
else if (eat('-')) node = new Node("-", node, factor());
else break;
return node;
}
}.expression();
}
static void testParse(String input) {
System.out.printf("%-22s -> %s%n", input, parse(input));
}
public static void main(String[] args) {
testParse("a+b");
testParse("(a/b) - (c*v)");
testParse("((a/(b))) - (((c)*v))");
testParse("-a");
testParse("-a + (-c/v)");
testParse("-(c)");
testParse("(-(c))");
}
}运行结果：
a+b -> Node[+, Node[a], Node[b]] (a/b) - (c*v) -> Node[-, Node[/, Node[a], Node[b]], Node[*, Node[c], Node[v]]] ((a/(b))) - (((c)*v)) -> Node[-, Node[/, Node[a], Node[b]], Node[*, Node[c], Node[v]]] -a -> Node[-, Node[a]] -a + (-c/v) -> Node[+, Node[-, Node[a]], Node[/, Node[-, Node[c]], Node[v]]] -(c) -> Node[-, Node[c]] (-(c)) -> Node[-, Node[c]]
从输出可以看出，解析器成功地将各种复杂的字符串表达式转换成了正确的抽象语法树结构，准确识别了操作数、二元操作符和一元负号，并正确处理了括号。
5. 注意事项与扩展
- 括号平衡： 解析器通过 eat('(') 和 eat(')') 的配对检查来确保括号的平衡。如果缺少右括号，将会抛出运行时异常。
- 一元负号处理： factor() 方法中 boolean minus = eat('-') 的设计巧妙地处理了一元负号，无论其操作数是单个变量还是一个完整的括号表达式。
- 操作符优先级： 如前所述，此实现依赖于输入表达式中通过括号明确指定优先级。对于需要自动处理复杂操作符优先级（如乘除优先于加减）的通用表达式解析器，通常需要更复杂的语法规则（例如，将expression拆分为term和factor等多个层次，或采用Shunting-yard算法）。
- 错误处理： 当前解析器仅通过抛出 RuntimeException 来处理语法错误。在生产环境中，应实现更健壮的错误报告机制，提供更详细的错误信息和位置。
- 支持更多操作符和数据类型： 要扩展解析器以支持更多操作符（如 %, ^）或不同类型的数据（如数字、浮点数），只需修改 factor() 方法以识别数字字面量，并更新 expression() 方法以包含新的操作符。
- 性能考量： 对于非常长的表达式，递归下降解析的性能通常是可接受的。然而，如果表达式极其复杂或嵌套层级非常深，可能会有栈溢出的风险。
6. 总结
本教程展示了如何使用Java和递归下降解析技术，构建一个能够将字符串表达式转换为抽象语法树的解析器。该解析器能够有效地处理二元操作、一元负号以及通过括号明确指定的表达式结构。通过理解Node数据结构、factor()和expression()等核心方法的逻辑，读者可以掌握表达式解析的基本原理，并在此基础上进行扩展，以适应更复杂的解析需求。
