AST抽象语法树-Java例子-马育民老师

需要了解：[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;
    }
}
```

```java
// 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<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`）。

```java
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的正确性。

```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<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”）

```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://www.malaoshi.top/show_1GW2FGStwmbY.html