Java递归下降解析器实现：表达式与参数列表解析分支判断问题

看起来你在实现Java递归下降解析器时遇到了经典的起始符号歧义问题——当多个产生式（比如numeric_expression和arglist）都以expression开头时，无法判断该调用哪个解析方法。结合你给出的语法规则和已实现的代码，我来帮你梳理可行的解决方案：

给定语法规则 #

expression ::= numeric_expression | identifier | "null"
identifier ::= "a..z,$,_"
numeric_expression ::= ( ( "-" | "++" | "--" ) expression ) | ( expression ( "++" | "--" ) ) | ( expression ( "+" | "+=" | "-" | "-=" | "*" | "*=" | "/" | "/=" | "%" | "%=" ) expression )
arglist ::= expression { "," expression }

已实现的parseNumericExpr()方法 #

NumericAST<? extends OpAST> parseNumericExpr() {
    OpAST op;
    if (token.getCodes() == Lexer.CODES.UNARY_OP) {
        //Check for unary operator like "++" or "--" etc
        op = new UnaryOpAST(token.getValue());
        token = getNextToken();
        AST expr = parseExpr(); // Method that returns expression node.
        if (expr == null) {
            op = null;
            return null;
        } else {
            if (checkSemi()) {
                System.out.println("UNARY AST CREATED");
                return new NumericAST<OpAST>(expr, op, false);
            } else {
                return null;
            }
        }
    } else {
        // Binary operation like "a+b", where a,b ->expression
        AST expr = parseExpr();
        if (expr == null) {
            return null;
        } else {
            token = getNextToken();
            if (token.getCodes() == Lexer.CODES.UNARY_OP) {
                op = new UnaryOpAST(token.getValue());
                return new NumericAST<OpAST>(expr, op, true);
            } else if (token.getCodes() == Lexer.CODES.BIN_OP) {
                op = new BinaryOpAST(token.getValue());
                token = getNextToken();
                AST expr2 = parseExpr();
                if (expr2 == null) {
                    op = null;
                    expr = null;
                    return null;
                } else {
                    if (checkSemi()) {
                        System.out.println("BINARY AST CREATED");
                        return new NumericAST<OpAST>(expr, op, expr2);
                    } else {
                        return null;
                    }
                }
            } else {
                expr = null;
                return null;
            }
        }
    }
}

核心问题分析 #

你遇到的歧义本质是：arglist和numeric_expression都依赖expression作为起始，但两者的出现场景完全不同——arglist不会孤立存在，它一定是在特定上下文里触发的（比如函数调用的(和)之间），而numeric_expression是独立的表达式结构。你的当前代码没有区分上下文，导致无法判断解析路径。

具体解决方案 #

递归下降解析器消除这类歧义的核心是利用上下文触发+有限向前看，下面是分步实现思路：

1. 基于上下文触发parseArgList()

首先重构你的语法调用逻辑：arglist只有在特定场景下才会被调用，比如当你解析到identifier之后跟着(时，就知道接下来要解析参数列表，而不是表达式。

举个例子，如果你有函数调用的语法（哪怕你没写出来，arglist的存在必然伴随这类结构），你可以在解析identifier后添加判断：

AST parsePrimaryExpr() {
    if (token.getCodes() == Lexer.CODES.NULL_LITERAL) {
        // 解析null字面量
        AST node = new NullAST();
        token = getNextToken();
        return node;
    } else if (token.getCodes() == Lexer.CODES.IDENTIFIER) {
        IdentifierAST idNode = new IdentifierAST(token.getValue());
        token = getNextToken();
        // 向前看一个token：如果是左括号，说明是函数调用，需要解析arglist
        if (token != null && token.getCodes() == Lexer.CODES.LPAREN) {
            token = getNextToken();
            List<AST> args = parseArgList();
            if (args == null) {
                return null;
            }
            // 检查右括号
            if (token == null || token.getCodes() != Lexer.CODES.RPAREN) {
                return null;
            }
            token = getNextToken();
            return new FunctionCallAST(idNode, args);
        }
        return idNode;
    } else if (token.getCodes() == Lexer.CODES.UNARY_OP) {
        // 解析前缀一元运算符（比如-、++、--）
        OpAST op = new UnaryOpAST(token.getValue());
        token = getNextToken();
        AST expr = parseExpr();
        return expr == null ? null : new NumericAST<>(expr, op, false);
    }
    return null;
}

2. 重构parseExpr()消除循环调用

你当前的parseNumericExpr()调用了parseExpr()，而parseExpr()又会尝试调用parseNumericExpr()，这会导致无限递归。我们可以把表达式解析拆分为主表达式解析和表达式尾部（运算符链）解析：

AST parseExpr() {
    AST primary = parsePrimaryExpr();
    if (primary == null) {
        return null;
    }
    // 处理后续的运算符（二元、后置一元）
    return parseExprTail(primary);
}

AST parseExprTail(AST leftExpr) {
    if (token == null) {
        return leftExpr;
    }
    // 处理后置一元运算符（++、--）
    if (token.getCodes() == Lexer.CODES.UNARY_OP) {
        OpAST op = new UnaryOpAST(token.getValue());
        token = getNextToken();
        return parseExprTail(new NumericAST<>(leftExpr, op, true));
    }
    // 处理二元运算符（+、-、*等）
    else if (token.getCodes() == Lexer.CODES.BIN_OP) {
        OpAST op = new BinaryOpAST(token.getValue());
        token = getNextToken();
        AST rightExpr = parsePrimaryExpr();
        if (rightExpr == null) {
            return null;
        }
        NumericAST<OpAST> binaryNode = new NumericAST<>(leftExpr, op, rightExpr);
        // 继续处理后续的运算符（比如a+b+c的情况）
        return parseExprTail(binaryNode);
    }
    // 没有更多运算符，返回当前节点
    return leftExpr;
}

3. 实现parseArgList()

现在parseArgList()可以安全地调用parseExpr()，因为它只会在函数调用的上下文里被触发，不会和numeric_expression的解析混淆：

List<AST> parseArgList() {
    List<AST> args = new ArrayList<>();
    // 解析第一个参数表达式
    AST firstArg = parseExpr();
    if (firstArg != null) {
        args.add(firstArg);
        // 处理后续的参数（用逗号分隔）
        while (token != null && token.getCodes() == Lexer.CODES.COMMA) {
            token = getNextToken();
            AST nextArg = parseExpr();
            if (nextArg == null) {
                return null;
            }
            args.add(nextArg);
        }
    }
    return args;
}

4. 优化checkSemi()的使用

你当前在parseNumericExpr()里检查分号的逻辑不太合理——分号是语句的结束符，不是表达式的一部分。应该把分号检查移到上层的语句解析方法中，比如：

AST parseStatement() {
    AST expr = parseExpr();
    if (expr == null) {
        return null;
    }
    // 语句必须以分号结尾
    if (token == null || token.getCodes() != Lexer.CODES.SEMICOLON) {
        return null;
    }
    token = getNextToken();
    return new ExpressionStatementAST(expr);
}

这样调整后，表达式可以在不需要分号的上下文（比如函数参数）中正常解析，不会因为缺少分号返回null。

内容的提问来源于stack exchange，提问作者Dhyey Shah