Java 递归下降解析器实战：手写四则运算解析器，支持括号与错误处理

Java递归下降解析器实战构建健壮的四则运算解析器1. 解析器设计基础递归下降解析器是编译原理中最直观的语法分析方法之一它通过一组相互递归调用的方法来实现语法规则的解析。每个非终结符对应一个解析方法方法内部根据当前token决定如何继续解析。对于四则运算表达式我们需要处理以下语法元素数字字面量如123、3.14二元运算符、-、*、/括号改变运算优先级错误处理非法字符、括号不匹配等词法分析器Lexer示例代码public class Lexer { private final String input; private int pos 0; public Lexer(String input) { this.input input.trim(); } public Token nextToken() { if (pos input.length()) { return new Token(TokenType.EOF, ); } char ch input.charAt(pos); switch (ch) { case : return new Token(TokenType.PLUS, ); case -: return new Token(TokenType.MINUS, -); case *: return new Token(TokenType.MULTIPLY, *); case /: return new Token(TokenType.DIVIDE, /); case (: return new Token(TokenType.LPAREN, (); case ): return new Token(TokenType.RPAREN, )); default: if (Character.isDigit(ch)) { StringBuilder num new StringBuilder(); num.append(ch); while (pos input.length() (Character.isDigit(input.charAt(pos)) || input.charAt(pos) .)) { num.append(input.charAt(pos)); } return new Token(TokenType.NUMBER, num.toString()); } throw new RuntimeException(Unexpected character: ch); } } }2. 语法分析与优先级处理四则运算的优先级问题需要通过文法设计来解决。我们使用经典的表达式文法expression → term ( (|-) term )* term → factor ( (*|/) factor )* factor → NUMBER | ( expression )解析器核心结构public class Parser { private final Lexer lexer; private Token currentToken; public Parser(Lexer lexer) { this.lexer lexer; this.currentToken lexer.nextToken(); } private void eat(TokenType type) { if (currentToken.type type) { currentToken lexer.nextToken(); } else { throw new RuntimeException(Unexpected token: currentToken); } } public double parse() { double result expression(); if (currentToken.type ! TokenType.EOF) { throw new RuntimeException(Unexpected token at end: currentToken); } return result; } private double expression() { double result term(); while (currentToken.type TokenType.PLUS || currentToken.type TokenType.MINUS) { Token op currentToken; eat(op.type); double right term(); result (op.type TokenType.PLUS) ? result right : result - right; } return result; } private double term() { double result factor(); while (currentToken.type TokenType.MULTIPLY || currentToken.type TokenType.DIVIDE) { Token op currentToken; eat(op.type); double right factor(); result (op.type TokenType.MULTIPLY) ? result * right : result / right; } return result; } private double factor() { if (currentToken.type TokenType.NUMBER) { double value Double.parseDouble(currentToken.value); eat(TokenType.NUMBER); return value; } else if (currentToken.type TokenType.LPAREN) { eat(TokenType.LPAREN); double result expression(); eat(TokenType.RPAREN); return result; } else { throw new RuntimeException(Unexpected token: currentToken); } } }3. 错误处理与恢复健壮的解析器需要能够识别错误并提供有用的错误信息。我们扩展之前的解析器加入错误恢复机制增强的错误处理public class ParserWithErrorHandling extends Parser { public ParserWithErrorHandling(Lexer lexer) { super(lexer); } Override public double parse() { try { double result expression(); if (currentToken.type ! TokenType.EOF) { throw new ParseError(Expected end of input, found: currentToken.value, currentToken.position); } return result; } catch (ParseError e) { System.err.println(Parse error: e.getMessage()); System.err.println(At position: e.getPosition()); recoverFromError(); return Double.NaN; } } private void recoverFromError() { // 简单的错误恢复跳过直到遇到运算符或右括号 while (currentToken.type ! TokenType.EOF currentToken.type ! TokenType.PLUS currentToken.type ! TokenType.MINUS currentToken.type ! TokenType.MULTIPLY currentToken.type ! TokenType.DIVIDE currentToken.type ! TokenType.RPAREN) { currentToken lexer.nextToken(); } } } class ParseError extends RuntimeException { private final int position; public ParseError(String message, int position) { super(message); this.position position; } public int getPosition() { return position; } }4. 完整实现与测试将各个组件整合成完整的解析器并添加测试用例完整解析器类public class ArithmeticParser { private final Parser parser; public ArithmeticParser(String input) { this.parser new ParserWithErrorHandling(new Lexer(input)); } public double evaluate() { return parser.parse(); } public static void main(String[] args) { String[] testCases { 1 2 * 3, // 7 (1 2) * 3, // 9 10 / (2 3), // 2 3.5 * (2 4.1), // 21.35 1 2, // 错误 2 * (3 4 // 括号不匹配 }; for (String test : testCases) { System.out.println(Evaluating: test); try { ArithmeticParser parser new ArithmeticParser(test); double result parser.evaluate(); System.out.println(Result: result); } catch (Exception e) { System.out.println(Error: e.getMessage()); } System.out.println(); } } }测试用例输出示例Evaluating: 1 2 * 3 Result: 7.0 Evaluating: (1 2) * 3 Result: 9.0 Evaluating: 10 / (2 3) Result: 2.0 Evaluating: 3.5 * (2 4.1) Result: 21.35 Evaluating: 1 2 Parse error: Unexpected token: At position: 4 Error: Unexpected token: Evaluating: 2 * (3 4 Parse error: Expected end of input, found: null At position: 8 Error: Expected end of input, found: null5. 性能优化与扩展对于更复杂的应用场景我们可以对解析器进行以下优化和扩展1. 抽象语法树AST生成interface Expr { double evaluate(); } class NumberExpr implements Expr { private final double value; public NumberExpr(double value) { this.value value; } Override public double evaluate() { return value; } } class BinaryOpExpr implements Expr { private final Expr left; private final Expr right; private final String op; public BinaryOpExpr(Expr left, String op, Expr right) { this.left left; this.op op; this.right right; } Override public double evaluate() { switch (op) { case : return left.evaluate() right.evaluate(); case -: return left.evaluate() - right.evaluate(); case *: return left.evaluate() * right.evaluate(); case /: return left.evaluate() / right.evaluate(); default: throw new RuntimeException(Unknown operator: op); } } }2. 支持变量和函数调用class VariableExpr implements Expr { private final String name; private final MapString, Double variables; public VariableExpr(String name, MapString, Double variables) { this.name name; this.variables variables; } Override public double evaluate() { if (!variables.containsKey(name)) { throw new RuntimeException(Unknown variable: name); } return variables.get(name); } } class FunctionCallExpr implements Expr { private final String functionName; private final ListExpr arguments; public FunctionCallExpr(String functionName, ListExpr arguments) { this.functionName functionName; this.arguments arguments; } Override public double evaluate() { switch (functionName) { case sqrt: if (arguments.size() ! 1) { throw new RuntimeException(sqrt requires 1 argument); } return Math.sqrt(arguments.get(0).evaluate()); // 添加更多函数支持... default: throw new RuntimeException(Unknown function: functionName); } } }3. 内存优化技巧使用对象池复用AST节点对于常量表达式进行预计算采用迭代而非递归实现防止栈溢出提示在实际项目中考虑使用解析器生成工具如ANTLR可以大幅提高开发效率但对于学习编译原理和需要精细控制的情况手工编写递归下降解析器仍然是很有价值的选择。