microwind Interpreter Pattern (解释器模式)
核心概念
Interpreter是一种Behavioral设计模式。
定义: 给定一个语言或表达式，定义它的文法，并建立一个解释器来解释该语言中的句子。它为特定的应用领域设计一套灵活的语言。
核心思想
- 文法表示: 将语言的文法规则用类层次表示
- 递归解析: 根据文法递归构建表达式树
- 统一处理: 所有表达式都遵循统一的接口
- 可扩展: 易于新增语言规则
何时使用
触发条件
- 需要解析特定格式的表达式 - SQL、配置语言、公式
- 文法规则已明确定义 - BNF、EBNF格式
- 需要多种解析策略 - 不同方言或变体
- 需要动态执行表达式 - 脚本、模板、规则引擎
- 需要编译或优化表达式 - 如JIT编译
不适合场景
- ❌ 语言规则非常复杂 - 解释器模式会导致类爆炸
- ❌ 性能要求极高 - 解释执行效率低，应使用编译
- ❌ 语言会频繁变化 - 维护成本高
- ❌ 只需简单的表达式求值 - 直接使用脚本引擎
基本结构
参与者
- AbstractExpression - 抽象表达式，定义interpret接口
- TerminalExpression - 终结符表达式，不再包含其他表达式
- NonterminalExpression - 非终结符表达式，包含其他表达式
- Context - 上下文，存储解释时所需的全局信息
UML关系
┌──────────────────────────┐
│ AbstractExpression │
├──────────────────────────┤
│ + interpret(context) │
└──────────────────────────┘
△
│ implements
┌────┴───────────────────┐
│ │
┌───────────────┐ ┌─────────────────┐
│Terminal │ │Nonterminal │
│Expression │ │Expression │
├───────────────┤ ├─────────────────┤
│ + interpret() │ │ - expressions │
└───────────────┘ │ + interpret() │
└─────────────────┘
Context 维护全局状态（变量、堆栈等）
实现方式对比
方法1: 递归下降解析 (Classic)
特点: 最基础的解释器，按表达式优先级递归
// 简单的计算器: E := E+T | E-T | T
// T := T*F | T/F | F
// F := (E) | number
class Parser {
private Scanner scanner;
private int currentToken;
public Parser(String input) {
scanner = new Scanner(input);
nextToken();
}
public Expression parse() {
return parseExpression();
}
private Expression parseExpression() {
Expression expr = parseTerm();
while (currentToken == '+' || currentToken == '-') {
int op = currentToken;
nextToken();
Expression right = parseTerm();
expr = new BinaryExpression(expr, op, right);
}
return expr;
}
private Expression parseTerm() {
Expression expr = parseFactor();
while (currentToken == '*' || currentToken == '/') {
int op = currentToken;
nextToken();
Expression right = parseFactor();
expr = new BinaryExpression(expr, op, right);
}
return expr;
}
private Expression parseFactor() {
if (currentToken == '(') {
nextToken();
Expression expr = parseExpression();
if (currentToken == ')') nextToken();
return expr;
}
return new NumberExpression(parseNumber());
}
}
方法2: 访问者模式结合解释器
特点: 分离表达式结构和解释逻辑
interface ExprVisitor {
int visit(NumberExpr expr);
int visit(BinaryExpr expr);
int visit(VariableExpr expr);
}
class EvaluationVisitor implements ExprVisitor {
Map<String, Integer> variables;
@Override
public int visit(NumberExpr expr) {
return expr.value;
}
@Override
public int visit(BinaryExpr expr) {
int left = expr.left.accept(this);
int right = expr.right.accept(this);
return applyOperation(expr.op, left, right);
}
private int applyOperation(String op, int left, int right) {
switch(op) {
case "+": return left + right;
case "-": return left - right;
case "*": return left * right;
case "/": return left / right;
default: throw new IllegalArgumentException();
}
}
}
方法3: AST + 解释器模式
特点: 先构建完整AST，再遍历解释
// AST节点
interface ASTNode {
void accept(ASTVisitor visitor);
}
class Program implements ASTNode {
List<Statement> statements;
@Override
public void accept(ASTVisitor visitor) {
visitor.visit(this);
}
}
class Interpreter implements ASTVisitor {
Map<String, Integer> variables = new HashMap<>();
@Override
public void visit(Program program) {
for (Statement stmt : program.statements) {
stmt.accept(this);
}
}
@Override
public void visit(AssignmentStatement stmt) {
int value = evaluateExpression(stmt.expression);
variables.put(stmt.variable, value);
}
}
方法4: JIT编译解释 (高性能)
特点: 解释部分表达式后编译为字节码
class JITInterpreter {
private Map<String, CompiledExpression> cache = new HashMap<>();
public int evaluate(String expression, Map<String, Integer> vars) {
CompiledExpression compiled = cache.computeIfAbsent(expression, expr -> {
// 解析表达式
Expression ast = parse(expr);
// 编译为字节码
return compile(ast);
});
return compiled.execute(vars);
}
@FunctionalInterface
interface CompiledExpression {
int execute(Map<String, Integer> variables);
}
}
6个真实使用场景
场景1: SQL查询解析
应用: 数据库引擎, ORM框架
// SQL SELECT statement
class SelectStatement implements Expression {
String table;
List<Column> columns;
Expression where;
public void interpret(Context context) {
List<Row> rows = context.getTable(table);
for (Row row : rows) {
if (where == null || where.evaluate(row)) {
processRow(row, columns);
}
}
}
}
class WhereClause implements Expression {
Expression condition;
public boolean evaluate(Row row) {
return condition.evaluate(row);
}
}
场景2: 配置语言解析
应用: 配置管理, DSL
// 配置: key = value, key: [item1, item2]
class ConfigParser {
public Config parse(String input) {
Config config = new Config();
for (String line : input.split("\n")) {
if (line.contains("=")) {
KeyValuePair pair = parseKeyValue(line);
config.set(pair.key, pair.value);
} else if (line.contains(":")) {
ListDefinition list = parseList(line);
config.set(list.key, list.values);
}
}
return config;
}
}
场景3: 正则表达式引擎
应用: 文本匹配, 字符串处理
// 简单的正则: a|b (a或b), a* (a重复), a+ (a至少一次)
interface RegexExpr {
boolean matches(String text);
}
class CharacterExpr implements RegexExpr {
char c;
public boolean matches(String text) {
return text.length() > 0 && text.charAt(0) == c;
}
}
class AlternationExpr implements RegexExpr {
RegexExpr left, right;
public boolean matches(String text) {
return left.matches(text) || right.matches(text);
}
}
class RepetitionExpr implements RegexExpr {
RegexExpr expr;
public boolean matches(String text) {
int i = 0;
while (i < text.length() && expr.matches(text.substring(i))) {
i++;
}
return true;
}
}
场景4: 模板引擎解析
应用: 代码生成, HTML模板, Velocity/FreeMarker
// 模板: Hello ${name}, you have {{count}} messages
interface TemplateExpr {
String render(Map<String, Object> context);
}
class LiteralExpr implements TemplateExpr {
String text;
public String render(Map<String, Object> context) {
return text;
}
}
class VariableExpr implements TemplateExpr {
String name;
public String render(Map<String, Object> context) {
Object value = context.get(name);
return value != null ? value.toString() : "";
}
}
class IfStatementExpr implements TemplateExpr {
String condition;
TemplateExpr thenPart, elsePart;
public String render(Map<String, Object> context) {
boolean condResult = evaluateCondition(condition, context);
return condResult ? thenPart.render(context) : elsePart.render(context);
}
}
场景5: 规则引擎
应用: 业务规则, 权限检查, 审批流
// 规则: if user.role == 'admin' and user.status == 'active'
interface Rule {
boolean evaluate(Context context);
}
class AndRule implements Rule {
Rule left, right;
public boolean evaluate(Context context) {
return left.evaluate(context) && right.evaluate(context);
}
}
class ComparisonRule implements Rule {
String field;
String operator;
Object value;
public boolean evaluate(Context context) {
Object fieldValue = context.getFieldValue(field);
return compare(fieldValue, operator, value);
}
}
场景6: 公式求值器
应用: Excel, 财务计算, 报表系统
// 公式: IF(A1>100, A1*0.9, A1)
interface Formula {
Number evaluate(Map<String, Number> vars);
}
class FormulaParser {
public Formula parse(String formula) {
// 解析: =IF(condition, trueExpr, falseExpr)
// 或: =SUM(A1:A10)
// 或: =A1+B1*C1
return new CompositeFormula(parseExpression(formula));
}
}
class FunctionCall implements Formula {
String name;
List<Formula> args;
public Number evaluate(Map<String, Number> vars) {
switch(name) {
case "SUM": return args.stream().map(f -> f.evaluate(vars))
.reduce(0, (a, b) -> a.doubleValue() + b.doubleValue());
case "IF": return evaluateIf(args, vars);
default: throw new IllegalArgumentException();
}
}
}
4个常见问题及解决方案
问题1: 语法错误恢复困难
症状:
- 语法错误时直接失败，无法给出有意义的错误信息
- 无法进行错误恢复和部分解析
解决方案:
// ✅ 使用异常和错误恢复
class RobustParser {
List<ParseError> errors = new ArrayList<>();
public Expression parse(String input) throws ParseException {
try {
return parseExpression();
} catch (SyntaxException e) {
errors.add(new ParseError(e.getLine(), e.getMessage()));
// 尝试恢复
return recoverAndContinue();
}
}
private Expression recoverAndContinue() {
// 跳过直到找到有效的同步点
while (currentToken != ';' && currentToken != EOF) {
nextToken();
}
return null; // 或返回默认表达式
}
}
// ✅ 提供详细的错误信息
class ParseError {
int line, column;
String message;
String[] suggestions;
ParseError(int line, String message) {
this.line = line;
this.message = message;
// 生成建议
}
}
问题2: 性能低，递归解析太慢
症状:
- 深层嵌套表达式导致栈溢出
- 解释执行速度远低于编译执行
解决方案:
// ✅ 转换迭代式解析 + 虚拟机
class VirtualMachine {
Stack<Integer> stack = new Stack<>();
List<Instruction> instructions;
public int execute() {
for (Instruction instr : instructions) {
switch(instr.op) {
case PUSH: stack.push(instr.value); break;
case ADD: stack.push(stack.pop() + stack.pop()); break;
// ...
}
}
return stack.pop();
}
}
// ✅ 使用字节码缓存和JIT
class CachedInterpreter {
Map<String, ByteCode> cache = new HashMap<>();
public int evaluate(String expr, Variables vars) {
ByteCode code = cache.computeIfAbsent(expr, e -> compile(e));
return code.execute(vars);
}
}
// ✅ 限制递归深度
class DepthLimitedParser {
int maxDepth = 100;
int currentDepth = 0;
public Expression parse() {
if (currentDepth++ > maxDepth) {
throw new ParseException("Expression too deep");
}
try {
return parseExpression();
} finally {
currentDepth--;
}
}
}
问题3: 上下文管理复杂
症状:
- 变量作用域混乱
- 函数调用时的栈帧管理复杂
- 递归调用时状态污染
解决方案:
// ✅ 使用显式的Context stack
class ContextStack {
Stack<Map<String, Object>> stack = new Stack<>();
public void pushScope() {
stack.push(new HashMap<>());
}
public void popScope() {
stack.pop();
}
public void set(String name, Object value) {
stack.peek().put(name, value);
}
public Object get(String name) {
for (int i = stack.size() - 1; i >= 0; i--) {
if (stack.get(i).containsKey(name)) {
return stack.get(i).get(name);
}
}
return null;
}
}
// ✅ 使用ThreadLocal隔离并发上下文
class ThreadSafeContext {
static ThreadLocal<Context> context = ThreadLocal.withInitial(Context::new);
public static Context current() {
return context.get();
}
public static void clear() {
context.remove();
}
}
问题4: 表达式优化困难
症状:
- 相同子表达式重复计算
- 无法进行常数折叠优化
- 表达式树过大
解决方案:
// ✅ 表达式优化和简化
class ExpressionOptimizer {
public Expression optimize(Expression expr) {
if (expr instanceof BinaryExpression) {
BinaryExpression binary = (BinaryExpression) expr;
Expression left = optimize(binary.left);
Expression right = optimize(binary.right);
// 常数折叠
if (left instanceof NumberExpr && right instanceof NumberExpr) {
Number result = evaluate(binary.op,
((NumberExpr)left).value,
((NumberExpr)right).value);
return new NumberExpr(result);
}
// 单位元优化 (+ 0, * 1)
if (isIdentity(binary.op, left) || isIdentity(binary.op, right)) {
return isIdentity(binary.op, left) ? right : left;
}
return new BinaryExpression(left, binary.op, right);
}
return expr;
}
}
// ✅ 使用Flyweight共享常见表达式
class ExpressionCache {
static Map<String, Expression> cache = new HashMap<>();
static Expression getOrCreate(String key, Function<String, Expression> creator) {
return cache.computeIfAbsent(key, creator);
}
}
与其他模式的关系
| 模式 | 关系 | 何时结合 |
|---|---|---|
| Visitor | 分离结构和解释逻辑 | 表达式树结构复杂 |
| Composite | 构建表达式树 | 组织不同类型表达式 |
| Factory | 创建表达式节点 | 隐藏表达式创建细节 |
| Strategy | 不同的解释策略 | 支持多种求值方式 |
| Flyweight | 共享常见表达式 | 优化内存使用 |
| Builder | 构建复杂表达式 | 逐步构建AST |
最佳实践
1. 清晰的文法定义
// ✅ 使用BNF或EBNF明确文法
// Expr := Term (('+' | '-') Term)*
// Term := Factor (('*' | '/') Factor)*
// Factor := Number | '(' Expr ')'
// Number := [0-9]+
// ✅ 通过ANTLR等工具生成解析器
@grammar("simple_expr.g4")
class Expr {}
2. 使用访问者模式分离关注
// ✅ 表达式结构只关注表示
// 解释逻辑通过访问者实现
interface Expr {
void accept(ExprVisitor visitor);
}
interface ExprVisitor {
void visit(NumberExpr expr);
void visit(BinaryExpr expr);
}
3. 提供有意义的错误报告
// ✅ 准确的错误位置和建议
throw new ParseException(
"Unexpected token at line " + line + ", column " + column +
". Expected '" + expected + "', got '" + actual + "'." +
" Did you mean: " + suggestion
);
4. 优化常见情况
// ✅ 缓存解析结果
// ✅ 进行表达式优化
// ✅ 使用JIT编译热路径
何时避免使用
- ❌ 语言过于复杂 - 解释器会变得非常复杂
- ❌ 性能至关重要 - 解释执行效率低
- ❌ 可以使用已有工具 - ANTLR, Bison等成熟方案
- ❌ 语言会频繁变化 - 维护成本太高
总结
解释器模式通过为特定领域的语言建立解释机制，提供了一种灵活的方式来实现和执行表达式。关键是：
- 清晰定义文法规则
- 正确实现递归解析或遍历
- 有效管理上下文和作用域
- 提供优化和缓存机制