Errors on Recursive Descent Parsing Java

Question

I am working on this java program, which is a recursive descent parser. The output provided below does not contain any syntax errors, however the program printing an error message. The program should print "SUCCESS: ..." but is printing "ERROR: ..." instead. Here is my code:

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
    }
}

Here is the input txt file (Each line is one token):

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

Thank you.

Answer 1

This is not rocket-science, but your code is completely wrong. It does not validate the schema of the file. It's easier to give you a working solution to make you realise the way of solving this task, than explain problems in your code.

I am not sure that my solution is 100% correct, but it works well for you input example.

public class Parser {

    public static void main(String... args) throws IOException {
        String file = "input1.txt";

        try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
            boolean valid = isDocumentValid(() -> {
                try {
                    return reader.readLine();
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            });

            if (valid)
                System.out.println("SUCCESS: the code has been successfully parsed.");
            else
                System.err.println("ERROR: the code contains a syntax mistake.");
        }
    }

    /**
     * <pre>
     * {
     *  &lt;key&gt:&lt;value&gt;;
     *  &lt;key&gt:&lt;value&gt;;
     * }
     * $
     * </pre>
     *
     * <pre>
     * {
     *  &lt;key&gt:&lt;value&gt;;
     *  &lt;key&gt:&lt;value&gt;;
     * }
     * $
     * </pre>
     */
    private static boolean isDocumentValid(Supplier<String> nextToken) {
        String token = nextToken.get();

        if (token == null)
            return true;    // empty document is valid document
        if (!"{".equals(token))
            return false;   // document should start with '{'

        while (true) {
            token = nextToken.get();

            if ("}".equals(token))
                break;
            if (!isStatementValid(token, nextToken))
                return false;
        }

        return "$".equals(nextToken.get()) && nextToken.get() == null;
    }

    private static boolean isStatementValid(String token, Supplier<String> nextToken) {
        if (!":".equals(nextToken.get()))
            return false;   // statement's key and statement's value should be separated with ':'
        if ("compute".equals(token))
            return isComputeStatementValid(":", nextToken, false);
        if ("call".equals(token))
            return isCallStatementValid(":", nextToken, false);
        return false;   // unknown statement's key
    }

    /**
     * Valid <tt>compute</tt> statements are:
     * <ul>
     * <li><tt>compute:id=num</tt></li>
     * <li><tt>compute:id=id+id</tt></li>
     * </ul>
     */
    private static boolean isComputeStatementValid(String prvToken, Supplier<String> nextToken, boolean afterEqual) {
        String token = nextToken.get();

        if (afterEqual) {
            if ("id".equals(token) || "num".equals(token))
                return ("=".equals(prvToken) || "+".equals(prvToken) || "-".equals(prvToken))
                        && isComputeStatementValid(token, nextToken, true);
            if ("+".equals(token) || "-".equals(token))
                return ("id".equals(prvToken) || "num".equals(prvToken))
                        && isComputeStatementValid(token, nextToken, true);
            return ("id".equals(prvToken) || "num".equals(prvToken)) && ";".equals(token);
        }

        return "id".equals(token) || "num".equals(token)
               ? ":".equals(prvToken) && isComputeStatementValid(token, nextToken, false)
               : "=".equals(token) && isComputeStatementValid(token, nextToken, true);
    }

    /**
     * Valid <tt>call</tt> statements are:
     * <ul>
     * <li><tt>call:id(id,num,id)</tt></li>
     * </ul>
     */
    private static boolean isCallStatementValid(String prvToken, Supplier<String> nextToken, boolean withinBrackets) {
        String token = nextToken.get();

        if (withinBrackets) {
            if ("id".equals(token) || "num".equals(token))
                return ("(".equals(prvToken) || ",".equals(prvToken)) && isCallStatementValid(token, nextToken, true);
            if (",".equals(token))
                return ("id".equals(prvToken) || "num".equals(prvToken))
                        && isCallStatementValid(token, nextToken, true);
            return ")".equals(token) && ("id".equals(prvToken) || "num".equals(prvToken))
                    && ";".equals(nextToken.get());
        }

        return ("id".equals(token) || "num".equals(token))
               ? ":".equals(prvToken) && isCallStatementValid(token, nextToken, false)
               : "(".equals(token) && isCallStatementValid(token, nextToken, true);
    }

}

P.S. My advice to you. Run this code in the debugger mode and go throught the whole logic. I think you get the main idea of the solution.