基于指定BNF语法的Java递归下降解析器实现求助

核心思路 #

递归下降解析器的核心是每个BNF非终结符对应一个独立函数，函数负责匹配对应语法规则、处理token流，并完成语义动作（如表达式求值、变量存储）。实现时需要维护：

• 一个token流指针，跟踪当前待处理的token
• 符号表（用HashMap实现），存储变量名与对应的值

基础结构与工具方法 #

首先定义解析器类，包含token流、指针、符号表，以及基础的token操作方法：

import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class RecursiveDescentParser {
    private List<Token> tokens;
    private int currentTokenIndex;
    private Map<String, Integer> symbolTable;

    public RecursiveDescentParser(List<Token> tokens) {
        this.tokens = tokens;
        this.currentTokenIndex = 0;
        this.symbolTable = new HashMap<>();
    }

    // 获取当前未消费的token
    private Token peek() {
        return currentTokenIndex < tokens.size() ? tokens.get(currentTokenIndex) : null;
    }

    // 消费当前token，指针后移
    private Token consume() {
        return tokens.get(currentTokenIndex++);
    }

    // 检查当前token是否为指定类型，是则消费，否则抛出解析异常
    private void match(int expectedType) throws ParseException {
        Token token = peek();
        if (token == null || token.type != expectedType) {
            throw new ParseException(String.format("Expected token type %d, got %s", 
                expectedType, token != null ? token.type : "null"));
        }
        consume();
    }
}

同时定义解析异常类：

public class ParseException extends Exception {
    public ParseException(String message) {
        super(message);
    }
}

对应BNF规则的解析函数 #

1. <program> → <statements> #

作为入口，调用语句处理函数并检查解析完整性：

public void parse() throws ParseException {
    program();
    if (peek() != null) {
        throw new ParseException("Unexpected token after program end");
    }
}

private void program() throws ParseException {
    statements();
}

2. <statements> → <statement> | <statement> <semi_colon> <statements> #

处理单个语句，循环匹配分号分隔的后续语句：

private void statements() throws ParseException {
    statement();
    while (peek() != null && peek().type == TokenType.SEMI_COLON) {
        match(TokenType.SEMI_COLON);
        statement();
    }
}

3. <statement> → <ident> <assignment_op> <expression> #

匹配变量名、赋值运算符，计算表达式值并存入符号表：

private void statement() throws ParseException {
    Token identToken = peek();
    if (identToken == null || identToken.type != TokenType.IDENT) {
        throw new ParseException("Expected identifier in statement");
    }
    String varName = identToken.token_string;
    consume();

    match(TokenType.ASSIGN);
    int exprValue = expression();
    symbolTable.put(varName, exprValue);
}

4. <expression> → <term> <term_tail> #

调用项处理函数，再处理后续加减运算：

private int expression() throws ParseException {
    int value = term();
    return termTail(value);
}

// `<term_tail>` → `<add_op>` `<term>` `<term_tail>` | ε
private int termTail(int currentValue) throws ParseException {
    Token token = peek();
    while (token != null && (token.type == TokenType.PLUS || token.type == TokenType.MINUS)) {
        consume();
        int termValue = term();
        currentValue = token.type == TokenType.PLUS ? currentValue + termValue : currentValue - termValue;
        token = peek();
    }
    return currentValue;
}

5. <term> → <factor> <factor_tail> #

调用因子处理函数，再处理后续乘除运算：

private int term() throws ParseException {
    int value = factor();
    return factorTail(value);
}

// `<factor_tail>` → `<mult_op>` `<factor>` `<factor_tail>` | ε
private int factorTail(int currentValue) throws ParseException {
    Token token = peek();
    while (token != null && (token.type == TokenType.STAR || token.type == TokenType.SLASH)) {
        consume();
        int factorValue = factor();
        if (token.type == TokenType.STAR) {
            currentValue *= factorValue;
        } else {
            if (factorValue == 0) {
                throw new ParseException("Division by zero");
            }
            currentValue /= factorValue;
        }
        token = peek();
    }
    return currentValue;
}

6. <factor> → <left_paren> <expression> <right_paren> | <ident> | <const> #

处理括号表达式、变量引用或常量：

private int factor() throws ParseException {
    Token token = peek();
    if (token == null) {
        throw new ParseException("Unexpected end of input in factor");
    }

    int value;
    if (token.type == TokenType.LEFT_PAR) {
        consume();
        value = expression();
        match(TokenType.RIGHT_PAR);
    } else if (token.type == TokenType.IDENT) {
        String varName = token.token_string;
        consume();
        if (!symbolTable.containsKey(varName)) {
            throw new ParseException("Undefined variable: " + varName);
        }
        value = symbolTable.get(varName);
    } else if (token.type == TokenType.NUMBER) {
        value = (Integer) token.value;
        consume();
    } else {
        throw new ParseException("Unexpected token in factor: " + token.token_string);
    }
    return value;
}

测试示例 #

针对给定的测试输入，构造token流并验证解析结果：

public static void main(String[] args) {
    List<Token> tokens = List.of(
        new Token(TokenType.IDENT, "operator1", null),
        new Token(TokenType.ASSIGN, ":=", null),
        new Token(TokenType.NUMBER, "200", 200),
        new Token(TokenType.PLUS, "+", null),
        new Token(TokenType.NUMBER, "100", 100),
        new Token(TokenType.STAR, "*", null),
        new Token(TokenType.LEFT_PAR, "(", null),
        new Token(TokenType.NUMBER, "100", 100),
        new Token(TokenType.MINUS, "-", null),
        new Token(TokenType.NUMBER, "200", 200),
        new Token(TokenType.RIGHT_PAR, ")", null),
        new Token(TokenType.SEMI_COLON, ";", null),
        new Token(TokenType.IDENT, "operator2", null),
        new Token(TokenType.ASSIGN, ":=", null),
        new Token(TokenType.IDENT, "operator1", null),
        new Token(TokenType.PLUS, "+", null),
        new Token(TokenType.NUMBER, "300", 300)
    );

    RecursiveDescentParser parser = new RecursiveDescentParser(tokens);
    try {
        parser.parse();
        System.out.println("operator1 = " + parser.symbolTable.get("operator1")); // 输出：-9800
        System.out.println("operator2 = " + parser.symbolTable.get("operator2")); // 输出：-9500
    } catch (ParseException e) {
        e.printStackTrace();
    }
}

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