AST抽象语法树-Java例子 作者:马育民 • 2025-11-17 21:50 • 阅读:10008 需要了解:[AST抽象语法树](https://www.malaoshi.top/show_1IX39EXaBJra.html "AST抽象语法树") # 介绍 在Java中实现抽象语法树(AST),核心是**定义节点模型**(描述语法成分)、**实现解析逻辑**(将输入文本转为树形结构),并支持**遍历/修改操作**。以下以“简单数学表达式AST”为例(如 `1 + 2 * 3 - 4`),完整演示AST的设计与实现,原理可迁移到SQL、JSON等其他语法的AST。 ### 一、核心概念:AST的构成 AST由**节点(Node)** 组成,每个节点对应一个语法单元,包含: - **节点类型**:如“数字节点”“加法节点”“乘法节点”。 - **属性**:节点的具体值(如数字节点的数值、运算符节点的运算符)。 - **子节点**:表示语法依赖关系(如加法节点有2个子节点:左操作数、右操作数)。 ### 二、步骤1:定义AST节点模型(接口+实现类) 先定义统一的`Node`接口,再按语法单元实现具体节点(如数字节点、二元运算符节点)。 #### 1. 节点接口(Node) 定义AST节点的通用行为(如计算值、打印结构): ```java // AST节点通用接口 public interface Node { // 计算节点的值(仅针对可计算的表达式节点) int evaluate(); // 打印节点结构(用于可视化AST) void print(int indent); // indent:缩进量,体现层级 } ``` #### 2. 具体节点实现 根据“简单数学表达式”的语法,需3类节点: - **数字节点(NumberNode)**:叶子节点,无后代,存储具体数字。 - **二元运算符节点(BinaryOpNode)**:非叶子节点,有2个子节点(左/右操作数),存储运算符(+、-、*、/)。 ```java 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):(、)。 ```java 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 tokenize(String input) { List 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`)。 ```java import java.util.List; import java.util.Stack; // 语法分析器:Token列表 → AST(根节点) class Parser { private final List tokens; private int pos; // 当前处理的Token索引 public Parser(List 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的正确性。 ```java 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 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”) ```java // 假设要修改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个核心步骤: 1. **定义节点模型**:按语法单元设计接口和实现类(叶子节点存储值,非叶子节点存储子节点)。 2. **实现解析器**:通过“词法分析(分词)→ 语法分析(递归构建树)”将文本转为AST。 3. **支持节点操作**:通过“访问者模式”(如扩展`Node`接口添加`accept(Visitor)`)实现遍历、修改、计算等功能。 若需实现SQL AST,可参考此模型,将节点替换为“SelectNode”“WhereNode”“ConditionNode”,解析逻辑替换为SQL语法规则(推荐基于JSqlParser等成熟库简化开发)。 原文出处:http://malaoshi.top/show_1GW2FGStwmbY.html