需要了解：AST抽象语法树
介绍
在Java中实现抽象语法树（AST），核心是定义节点模型（描述语法成分）、实现解析逻辑（将输入文本转为树形结构），并支持遍历/修改操作。以下以“简单数学表达式AST”为例（如 1 + 2 * 3 - 4），完整演示AST的设计与实现，原理可迁移到SQL、JSON等其他语法的AST。
一、核心概念：AST的构成
AST由节点（Node） 组成，每个节点对应一个语法单元，包含：
- 节点类型：如“数字节点”“加法节点”“乘法节点”。
- 属性：节点的具体值（如数字节点的数值、运算符节点的运算符）。
- 子节点：表示语法依赖关系（如加法节点有2个子节点：左操作数、右操作数）。
二、步骤1：定义AST节点模型（接口+实现类）
先定义统一的Node接口，再按语法单元实现具体节点（如数字节点、二元运算符节点）。
1. 节点接口（Node）
定义AST节点的通用行为（如计算值、打印结构）：
// AST节点通用接口
public interface Node {
// 计算节点的值（仅针对可计算的表达式节点）
int evaluate();
// 打印节点结构（用于可视化AST）
void print(int indent); // indent：缩进量，体现层级
}
2. 具体节点实现
根据“简单数学表达式”的语法，需3类节点：
- 数字节点（NumberNode）：叶子节点，无后代，存储具体数字。
- 二元运算符节点（BinaryOpNode）：非叶子节点，有2个子节点（左/右操作数），存储运算符（+、-、*、/）。
import java.util.Objects;
// 1. 数字节点（叶子节点）
class NumberNode implements Node {
private final int value; // 数字值
public NumberNode(int value) {
this.value = value;
}
@Override
public int evaluate() {
return value; // 数字节点的值就是自身存储的数值
}
@Override
public void print(int indent) {
// 打印缩进 + 节点类型 + 值（叶子节点无后代）
System.out.println(" ".repeat(indent) + "NumberNode: " + value);
}
// Getter（后续解析时可能需要）
public int getValue() {
return value;
}
}
// 2. 二元运算符节点（非叶子节点）
class BinaryOpNode implements Node {
public enum Op {
ADD('+'), SUB('-'), MUL('*'), DIV('/');
private final char symbol;
Op(char symbol) {
this.symbol = symbol;
}
@Override public String toString() {
return String.valueOf(symbol);
}
}
private final Op operator; // 运算符（+、-、*、/）
private final Node left; // 左操作数节点
private final Node right; // 右操作数节点
public BinaryOpNode(Op operator, Node left, Node right) {
this.operator = Objects.requireNonNull(operator);
this.left = Objects.requireNonNull(left);
this.right = Objects.requireNonNull(right);
}
@Override
public int evaluate() {
// 递归计算左、右子节点的值，再按运算符计算结果
int leftVal = left.evaluate();
int rightVal = right.evaluate();
return switch (operator) {
case ADD -> leftVal + rightVal;
case SUB -> leftVal - rightVal;
case MUL -> leftVal * rightVal;
case DIV -> {
if (rightVal == 0) throw new ArithmeticException("除零错误");
yield leftVal / rightVal;
}
};
}
@Override
public void print(int indent) {
// 1. 打印当前节点（缩进 + 运算符）
System.out.println(" ".repeat(indent) + "BinaryOpNode: " + operator);
// 2. 递归打印左子节点（缩进+2，体现层级）
System.out.print(" ".repeat(indent) + "├─ Left: ");
left.print(indent + 2);
// 3. 递归打印右子节点
System.out.print(" ".repeat(indent) + "└─ Right: ");
right.print(indent + 2);
}
// Getter（后续修改AST时可能需要）
public Op getOperator() { return operator; }
public Node getLeft() { return left; }
public Node getRight() { return right; }
}
三、步骤2：实现解析器（将文本转为AST）
解析器是AST的“构造器”，需完成词法分析（分词） 和语法分析（构建树） 两步，这里针对“简单数学表达式”（支持加减乘除、括号、优先级）实现简化版解析器。
1. 词法分析（Tokenization）
将输入字符串（如1 + 2 * 3）拆分为不可再分的“令牌（Token）”，支持3类Token：
- 数字（NUMBER）：如1、23。
- 运算符（OP）：
+、-、*、/ - 括号（PAREN）：
(、)
import java.util.ArrayList;
import java.util.List;
// 词法分析器：输入字符串 → Token列表
class Lexer {
// Token类型枚举
public enum TokenType { NUMBER, OP, PAREN }
// Token实体：包含类型和值
public static class Token {
public final TokenType type;
public final String value;
public Token(TokenType type, String value) {
this.type = type;
this.value = value;
}
@Override public String toString() {
return "[" + type + ":" + value + "]";
}
}
// 核心方法：将输入字符串拆分为Token列表
public List<Token> tokenize(String input) {
List<Token> tokens = new ArrayList<>();
int i = 0;
int n = input.length();
while (i < n) {
char c = input.charAt(i);
if (Character.isWhitespace(c)) {
// 跳过空格
i++;
} else if (Character.isDigit(c)) {
// 解析数字（支持多位数，如123）
int j = i;
while (j < n && Character.isDigit(input.charAt(j))) j++;
String numStr = input.substring(i, j);
tokens.add(new Token(TokenType.NUMBER, numStr));
i = j;
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
// 解析运算符
tokens.add(new Token(TokenType.OP, String.valueOf(c)));
i++;
} else if (c == '(' || c == ')') {
// 解析括号
tokens.add(new Token(TokenType.PAREN, String.valueOf(c)));
i++;
} else {
throw new IllegalArgumentException("非法字符：" + c);
}
}
return tokens;
}
}
2. 语法分析（构建AST）
基于Token列表，按“数学运算优先级”（先括号、再乘除、后加减）构建AST，核心是递归下降解析（用递归处理嵌套结构，如(1+2)*3）。
import java.util.List;
import java.util.Stack;
// 语法分析器：Token列表 → AST（根节点）
class Parser {
private final List<Lexer.Token> tokens;
private int pos; // 当前处理的Token索引
public Parser(List<Lexer.Token> tokens) {
this.tokens = tokens;
this.pos = 0;
}
// 核心方法：解析Token列表，返回AST根节点
public Node parse() {
return parseAddSub(); // 从最低优先级的“加减”开始解析（递归递进）
}
// 1. 解析加减运算（优先级最低）
private Node parseAddSub() {
Node node = parseMulDiv(); // 先解析更高优先级的“乘除”
// 循环处理后续的加减运算符（如1+2-3：先解析1+2，再用结果减3）
while (pos < tokens.size()) {
Lexer.Token token = tokens.get(pos);
if (token.type == Lexer.TokenType.OP && ("+".equals(token.value) || "-".equals(token.value))) {
pos++; // 消耗当前运算符Token
// 递归解析右侧的乘除表达式（保证优先级）
Node right = parseMulDiv();
// 构建二元运算符节点，更新当前节点（链式处理）
BinaryOpNode.Op op = "+".equals(token.value) ? BinaryOpNode.Op.ADD : BinaryOpNode.Op.SUB;
node = new BinaryOpNode(op, node, right);
} else {
break; // 不是加减，退出循环
}
}
return node;
}
// 2. 解析乘除运算（优先级高于加减）
private Node parseMulDiv() {
Node node = parsePrimary(); // 先解析“原子表达式”（数字或括号包裹的表达式）
// 循环处理后续的乘除运算符（如2*3/4）
while (pos < tokens.size()) {
Lexer.Token token = tokens.get(pos);
if (token.type == Lexer.TokenType.OP && ("*".equals(token.value) || "/".equals(token.value))) {
pos++; // 消耗当前运算符Token
// 递归解析右侧的原子表达式
Node right = parsePrimary();
// 构建二元运算符节点
BinaryOpNode.Op op = "*".equals(token.value) ? BinaryOpNode.Op.MUL : BinaryOpNode.Op.DIV;
node = new BinaryOpNode(op, node, right);
} else {
break;
}
}
return node;
}
// 3. 解析原子表达式（数字或括号包裹的表达式，优先级最高）
private Node parsePrimary() {
Lexer.Token token = tokens.get(pos);
if (token.type == Lexer.TokenType.NUMBER) {
// 数字节点：直接创建NumberNode
pos++; // 消耗数字Token
return new NumberNode(Integer.parseInt(token.value));
} else if (token.type == Lexer.TokenType.PAREN && "(".equals(token.value)) {
// 括号表达式：递归解析括号内的加减运算
pos++; // 消耗左括号Token
Node node = parseAddSub(); // 括号内优先解析加减（递归回到顶层）
// 检查右括号
if (pos >= tokens.size() || !")".equals(tokens.get(pos).value)) {
throw new IllegalArgumentException("缺少右括号");
}
pos++; // 消耗右括号Token
return node;
} else {
throw new IllegalArgumentException("非法Token：" + token);
}
}
}
四、步骤3：测试AST的构建与使用
通过 输入表达式 → 分词 → 构建AST → 打印AST → 计算结果 的流程，验证AST的正确性。
public class AstDemo {
public static void main(String[] args) {
// 1. 输入待解析的数学表达式
String expression = "1 + 2 * 3 - (4 + 5)"; // 预期结果：1 + 6 - 9 = -2
// 2. 词法分析：生成Token列表
Lexer lexer = new Lexer();
List<Lexer.Token> tokens = lexer.tokenize(expression);
System.out.println("词法分析结果（Token列表）：");
System.out.println(tokens + "\n");
// 3. 语法分析：构建AST
Parser parser = new Parser(tokens);
Node astRoot = parser.parse();
// 4. 打印AST结构（可视化层级）
System.out.println("AST结构（缩进表示层级）：");
astRoot.print(0); // 从根节点开始打印，缩进0
// 5. 计算AST的值（验证逻辑正确性）
int result = astRoot.evaluate();
System.out.println("\n表达式计算结果：" + expression + " = " + result);
}
}
运行结果
词法分析结果（Token列表）：
[[NUMBER:1], [OP:+], [NUMBER:2], [OP:*], [NUMBER:3], [OP:-], [PAREN:(], [NUMBER:4], [OP:+], [NUMBER:5], [PAREN:)]]
AST结构（缩进表示层级）：
BinaryOpNode: -
├─ Left: BinaryOpNode: +
│ ├─ Left: NumberNode: 1
│ └─ Right: BinaryOpNode: *
│ ├─ Left: NumberNode: 2
│ └─ Right: NumberNode: 3
└─ Right: BinaryOpNode: +
├─ Left: NumberNode: 4
└─ Right: NumberNode: 5
表达式计算结果：1 + 2 * 3 - (4 + 5) = -2
五、AST的核心扩展能力
基于上述模型，可轻松扩展AST的功能（如修改节点、添加新语法）：
1. 修改AST（如将“减5”改为“减10”）
// 假设要修改AST中“4+5”的右节点（5→10）
private static void modifyAst(Node node) {
if (node instanceof BinaryOpNode binaryOpNode) {
// 递归遍历左子节点
modifyAst(binaryOpNode.getLeft());
// 递归遍历右子节点
modifyAst(binaryOpNode.getRight());
// 找到“4+5”的节点，修改右子节点为10
if (binaryOpNode.getOperator() == BinaryOpNode.Op.ADD
&& binaryOpNode.getLeft() instanceof NumberNode leftNum
&& leftNum.getValue() == 4) {
binaryOpNode = new BinaryOpNode(BinaryOpNode.Op.ADD, leftNum, new NumberNode(10));
}
}
}
2. 扩展语法（如支持平方运算）
- 新增
SquareNode（一元运算符节点，只有一个子节点）。 - 在
Lexer中添加“^2”的Token解析。 - 在
Parser的parsePrimary()中添加平方运算的解析逻辑。
总结：AST实现的通用逻辑
无论针对SQL、JSON还是其他语法，AST的实现都遵循以下3个核心步骤：
- 定义节点模型：按语法单元设计接口和实现类（叶子节点存储值，非叶子节点存储子节点）。
- 实现解析器：通过“词法分析（分词）→ 语法分析（递归构建树）”将文本转为AST。
- 支持节点操作：通过“访问者模式”（如扩展
Node接口添加accept(Visitor)）实现遍历、修改、计算等功能。
若需实现SQL AST，可参考此模型，将节点替换为“SelectNode”“WhereNode”“ConditionNode”，解析逻辑替换为SQL语法规则（推荐基于JSqlParser等成熟库简化开发）。