Java递归下降解析器异常：输入合法却输出错误提示

我开发了一款Java递归下降解析器，输入文本确认没有语法错误，但程序未输出预期的SUCCESS: the code has been successfully parsed.，反而输出ERROR: the code contains a syntax mistake.。

原代码 #

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Main {

    private static BufferedReader reader;
    private static String token;

    public static void main(String[] args) {
        String inputFile = "input1.txt"; // Specify the input file name here

        try {
            reader = new BufferedReader(new FileReader(inputFile));
            token = getNextToken();
            if (parse()) {
                System.out.println("SUCCESS: the code has been successfully parsed.");
            } else {
                System.out.println("ERROR: the code contains a syntax mistake.");
            }
            reader.close();
        } catch (IOException e) {
            System.err.println("Error reading file: " + e.getMessage());
        }
    }

    private static String getNextToken() throws IOException {
        return reader.readLine(); // Read the next line from the file
    }

    private static boolean parse() throws IOException {
        if (!token.equals("{")) {
            return false; // Program should start with "{"
        }
        while (!token.equals("$")) {
            if (!token.equals("compute")) {
                return false; // Expecting "compute" token
            }
            if (!isValidComputeStatement()) {
                return false; // Invalid compute statement
            }
        }
        return true; // Parsing successful
    }

    private static boolean isValidComputeStatement() throws IOException {
        token = getNextToken(); // Move to the next token
        if (!token.equals(":")) {
            return false; // Expecting colon after "compute"
        }
        token = getNextToken(); // Move to the next token
        if (!isValidAssignmentStatement()) {
            return false; // Invalid assignment statement
        }
        return true; // Valid compute statement
    }

    private static boolean isValidAssignmentStatement() throws IOException {
        if (!token.equals("id")) {
            return false; // Expecting an identifier (variable name)
        }
        token = getNextToken(); // Move to the next token
        if (!token.equals("=")) {
            return false; // Expecting "=" after the identifier
        }
        token = getNextToken(); // Move to the next token
        if (!token.equals("num")) {
            return false; // Expecting a number after "="
        }
        token = getNextToken(); // Move to the next token
        if (!token.equals(";")) {
            return false; // Expecting ";" to terminate the statement
        }
        token = getNextToken(); // Move to the next token
        return true; // Valid assignment statement
    }
}

输入文件内容（每行一个token） #

{
compute
:
id
=
num
;
compute
:
id
=
num
;
compute
:
id
=
id
+
id
;
compute
:
id
=
id
-
id
;
call
:
id
(
id
,
num
,
id
)
;
}
$

问题根源 #

1. 语法规则不匹配输入：输入包含call语句，但原parse()方法只处理compute开头的语句，遇到call直接返回false。
2. 赋值语句规则过窄：原isValidAssignmentStatement()仅支持id = num;格式，无法识别id = id + id;这类带加减运算的表达式。
3. 终止逻辑错误：原循环以$为终止条件，但输入中}才是语句块的结束标记，循环会在遇到}时判定为非法token并返回false。

修复后的代码 #

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class Main {

    private static BufferedReader reader;
    private static String token;

    public static void main(String[] args) {
        String inputFile = "input1.txt";

        try {
            reader = new BufferedReader(new FileReader(inputFile));
            token = getNextToken();
            if (parse()) {
                System.out.println("SUCCESS: the code has been successfully parsed.");
            } else {
                System.out.println("ERROR: the code contains a syntax mistake.");
            }
            reader.close();
        } catch (IOException e) {
            System.err.println("Error reading file: " + e.getMessage());
        }
    }

    private static String getNextToken() throws IOException {
        String line;
        do {
            line = reader.readLine();
        } while (line != null && line.trim().isEmpty()); // 跳过空行
        return line;
    }

    private static boolean parse() throws IOException {
        if (!token.equals("{")) {
            return false;
        }
        token = getNextToken(); // 跳过{，获取下一个token
        while (!token.equals("}")) { // 循环处理直到遇到语句块结束符}
            if (token.equals("compute")) {
                if (!isValidComputeStatement()) {
                    return false;
                }
            } else if (token.equals("call")) {
                if (!isValidCallStatement()) {
                    return false;
                }
            } else {
                return false; // 未知语句类型
            }
        }
        token = getNextToken(); // 跳过}，检查结束符$
        return token.equals("$");
    }

    private static boolean isValidComputeStatement() throws IOException {
        token = getNextToken();
        if (!token.equals(":")) {
            return false;
        }
        token = getNextToken();
        return isValidAssignmentStatement();
    }

    private static boolean isValidAssignmentStatement() throws IOException {
        if (!token.equals("id")) {
            return false;
        }
        token = getNextToken();
        if (!token.equals("=")) {
            return false;
        }
        token = getNextToken();
        if (!isValidExpression()) {
            return false;
        }
        if (!token.equals(";")) {
            return false;
        }
        token = getNextToken();
        return true;
    }

    private static boolean isValidExpression() throws IOException {
        // 支持id或num作为表达式起始
        if (!token.equals("id") && !token.equals("num")) {
            return false;
        }
        token = getNextToken();
        // 处理加减运算符及后续操作数
        while (token.equals("+") || token.equals("-")) {
            token = getNextToken();
            if (!token.equals("id") && !token.equals("num")) {
                return false;
            }
            token = getNextToken();
        }
        return true;
    }

    private static boolean isValidCallStatement() throws IOException {
        token = getNextToken();
        if (!token.equals(":")) {
            return false;
        }
        token = getNextToken();
        if (!token.equals("id")) {
            return false;
        }
        token = getNextToken();
        if (!token.equals("(")) {
            return false;
        }
        token = getNextToken();
        // 处理参数列表
        if (!isValidArgument()) {
            return false;
        }
        while (token.equals(",")) {
            token = getNextToken();
            if (!isValidArgument()) {
                return false;
            }
        }
        if (!token.equals(")")) {
            return false;
        }
        token = getNextToken();
        if (!token.equals(";")) {
            return false;
        }
        token = getNextToken();
        return true;
    }

    private static boolean isValidArgument() throws IOException {
        boolean valid = token.equals("id") || token.equals("num");
        if (valid) {
            token = getNextToken();
        }
        return valid;
    }
}

关键修复说明 #

• 新增call语句处理：在parse()中加入call类型语句的判断，并实现isValidCallStatement()方法处理函数调用语法。
• 扩展表达式规则：新增isValidExpression()方法，支持带加减运算的表达式格式。
• 修正循环终止逻辑：将循环终止条件改为!token.equals("}")，先处理完所有语句直到语句块结束，再检查最后的$结束符。
• 空行处理优化：在getNextToken()中加入跳过空行的逻辑，避免输入空行导致解析错误。

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