CODEWITHSUNDEEP
javaparsingrecursioncastingrecursive-descent
Janno Ramos
Janno Ramos

Reputation: 65

Recursive Descent Parser - ClassCastException

I have a Recursive Descent Parser project, and I earlier posted a problem that I was having regarding stack overflow error. I have been able to fix that issue, however it is now returning a ClassCastException.

From a main SWING GUI form, I pass input string then build it into a linked list of Strings. I then pass it to the parser.java. The error says:

java.lang.ClassCastException: java.lang.String cannot be cast to compilerfinalproject.Token

Here are some example inputs:

  1. 1+2+3
  2. (1+2)-(3+4)
  3. (1+2+3)*4

Below is my tokenizer code.

import java.util.LinkedList;

public class Tokenizer {

    Tokenizer () {} // EMPTY CONSTRUCTOR FOR INSTANTIATION AT CompilerFinal.java

    Tokenizer(String expression) { // CONSTRUCTOR FOR CALLING FROM LOCAL Tokenize METHOD
        this.expression = expression.toCharArray(); // SET EXPRESSION TO TOKENIZE
        this.pos = 0; // INITIALIZE AT INDEX 0
    }

    int pos; // STRING INDEX DECLARATION
    char[] expression; // EXPRESSION DECLARATION
    LinkedList <String> tokens = new LinkedList<>(); // ARRAYLIST FOR ALL TOKENS

    enum tokenClass {PLUS, MINUS, MULTIPLY, DIVIDE, EXPONENT, NUMBER, IDENTIFIER, OPEN, CLOSE, NEGATIVE, DEFAULT} // TOKEN CLASSES (DEFAULT FOR INITIALIZATION PURPOSES ONLY)

    class Lexeme { // EACH LEXEME HAS TOKEN CLASS AND TOKEN VALUE
        String tokenClass, token;
        Lexeme(String tokenClass, String token) {
            this.tokenClass = tokenClass;
            this.token = token;
        }
    }

    Lexeme getToken() { // METHOD TO GET TOKENS
        StringBuilder token = new StringBuilder(); // BUILDS TOKEN PER CHARACTER
        boolean endOfToken = false; // FLAG WHETHER TO END TOKEN
        tokenClass type = tokenClass.DEFAULT; // DEFAULT VALUE FOR TOKENCLASS
        while (!endOfToken && hasMoreTokens()) // LOOP UNTIL A TOKEN IS COMPLETED
        {
            while(expression[pos] == ' ') // SKIP ALL LEADING SPACES
                pos++;
            switch (expression[pos]) 
            {
                case '+': 
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.PLUS; // SET TOKEN CLASS AS OPERATOR
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case '-':
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.MINUS; // SET TOKEN CLASS AS OPERATOR
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case '*':
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.MULTIPLY; // SET TOKEN CLASS AS OPERATOR
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case '/':
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.DIVIDE; // SET TOKEN CLASS AS OPERATOR
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case '^':
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.EXPONENT; // SET TOKEN CLASS AS OPERATOR
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case '(': // OPEN PARENTHESES
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.OPEN; // SET TOKEN CLASS AS OPEN
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case ')': // CLOSE PARENTHESES
                    if(type != tokenClass.NUMBER && type != tokenClass.IDENTIFIER) 
                    {
                        type = tokenClass.CLOSE; // SET TOKEN CLASS AS CLOSE
                        token.append(expression[pos]);
                        pos++;
                    }
                    endOfToken = true; // END TOKEN IMMEDIATELY
                    break;

                case ' ': // SKIP WHITESPACE
                    endOfToken = true;
                    pos++;
                    break;

                default: 
                    if(Character.isDigit(expression[pos]) || expression[pos] == '.') // FOR NUMBERS AND DECIMAL POINTS
                    {
                        token.append(expression[pos]);
                        type = tokenClass.NUMBER; // SET TOKENCLASS AS NUMBER
                    }
                    else if(Character.isAlphabetic(expression[pos])) // FOR IDENTIFIERS
                    {
                        token.append(expression[pos]);
                        type = tokenClass.IDENTIFIER;
                    }
                    pos++; // NO END TOKEN TO TAKE INTO ACCOUNT MULTIPLE DIGIT NUMBERS
                    break;
            }
        }
        return new Lexeme(type.name().toLowerCase(), token.toString());
    }

    boolean hasMoreTokens() { // CONDITION CHECKING
        return pos < expression.length;
    }

    public LinkedList tokenize (String expression) { // CALLED FROM CompilerFinal.java TO GET TOKENS IN ARRAYLIST
        Tokenizer tokenizer = new Tokenizer(expression); // INSTANTIATE
        while (tokenizer.hasMoreTokens())  // GETTING ALL TOKENS
        {
            Lexeme nextToken = tokenizer.getToken();
            tokens.add(nextToken.token);
        }
        return tokens;
    }

    public String getLexeme (String expression) // CALLED FROM CompilerFinal.java FOR DISPLAYING IN GUI FORM
    {
        StringBuilder lexemeList = new StringBuilder();
        Tokenizer tokenizer = new Tokenizer(expression); // INSTANTIATE
        lexemeList.append("LEXEMES:\n");
        while (tokenizer.hasMoreTokens())  // GETTING ALL TOKENS
        {
            Lexeme nextToken = tokenizer.getToken();
            lexemeList.append(nextToken.token).append("\t").append(nextToken.tokenClass).append("\n");
        }
        return lexemeList.toString();
    }

}

Below is my parser code. I have included the grammar I used in the comments. 

import java.util.LinkedList;

class Token {
    public static final int PLUS = 0;
    public static final int MINUS = 1;
    public static final int MULTIPLY = 2;
    public static final int DIVIDE = 3;
    public static final int EXPONENT = 4;
    public static final int NUMBER = 5;
    public static final int IDENTIFIER = 6;
    public static final int OPEN = 7;
    public static final int CLOSE = 8;
    //public static final int NEGATIVE = 7;

    public final int token; // FIELDS TO HOLD DATA PER TOKEN
    public final String sequence;

    public Token (int token, String sequence) {
        super();
        this.token = token;
        this.sequence = sequence;
    }
}

public class Parser {

    private Token next; // POINTER FOR NEXT TOKEN
    private final LinkedList<Token> tokens; // LIST OF TOKENS PRODUCED BY TOKENIZER
    private int counter = 0;

    public Parser(LinkedList tokens) 
    {
        this.tokens = (LinkedList<Token>) tokens.clone(); // GET LINKEDLIST
        this.tokens.getFirst(); // ASSIGNS FIRST ELEMENT OF LINKEDLIST
    }


    //////// START OF PARSING METHODS ////////

    /*
        GRAMMAR:
        E -> TE' | TE''
        E' -> +E | e
        E'' -> -E | e

        T -> FT' | FT''
        T' -> *T | e
        T'' -> /T | e

        F -> (E) | -F | "NUMBER" | "IDENTIFIER"
    */

    public boolean Parse ()
    {
        return E(); // INVOKE START SYMBOL
    }

    private boolean term (int token) // GETS NEXT TOKEN
    {
        boolean flag = false;

        if(next.token == token)
            flag = true;

        counter++; // INCREMENT COUNTER

        if(counter < tokens.size()) // POINT TO NEXT TOKEN
            next = tokens.get(counter);

        return flag;
    }

    ///////// START OF LIST OF PRODUCTIONS /////////

    //////// E -> TE' | TE'' ////////

    private boolean E()
    {
        return E1() || E2();
    }

    private boolean E1 ()
    {
        // E -> TE'

        int flag = counter;
        boolean result = true;

        if(!( T() && E_P() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean E2 ()
    {
        // E -> TE''

        int flag = counter;
        boolean result = true;

        if(!( T() && E_PP() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }


    //////// E' -> +E | e ////////

    private boolean E_P()
    {
        return E_P1() || E_P2();
    }

    private boolean E_P1()
    {
        // E' -> +E

        int flag = counter;
        boolean result = true;

        if(!( term(Token.PLUS) && E() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean E_P2()
    {
        // E' -> e

        return true;
    }


    //////// E'' -> -E | e ////////

    private boolean E_PP()
    {
        return E_PP1() || E_PP2();
    }

    private boolean E_PP1()
    {
        // E'' -> -E

        int flag = counter;
        boolean result = true;

        if(!( term(Token.MINUS) && E() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean E_PP2()
    {
        // E'' -> e

        return true;
    }


    //////// T -> FT' | FT'' ////////

    private boolean T()
    {
        return T1() || T2();
    }

    private boolean T1()
    {
        // T -> FT'

        int flag = counter;
        boolean result = true;

        if(!( F() && T_P() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean T2()
    {
        // T -> FT''
        int flag = counter;
        boolean result = true;

        if(!( F() && T_PP() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }


    //////// T' -> *T | e ////////

    private boolean T_P()
    {
        return T_P1() || T_P2();
    }

    private boolean T_P1()
    {
        // T' -> *T

        int flag = counter;
        boolean result = true;

        if(!( term(Token.MULTIPLY) && T() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean T_P2()
    {
        // T' -> e

        return true;
    }


    //////// T'' -> /T | e ////////

    private boolean T_PP()
    {
        return T_PP1() || T_PP2();
    }

    private boolean T_PP1()
    {
        // T'' -> /T

        int flag = counter;
        boolean result = true;

        if(!( term(Token.DIVIDE) && T() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean T_PP2()
    {
        // T'' -> e

        return true;
    }


    //////// F -> (E) | -F | "NUMBER" | "IDENTIFIER" ////////

    private boolean F()
    {
        return F1() || F2() || F3() || F4();
    }

    private boolean F1()
    {
        // F -> (E)

        int flag = counter;
        boolean result = true;

        if(!( term(Token.OPEN) && T() && term(Token.CLOSE) ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean F2()
    {
        // F -> -F

        int flag = counter;
        boolean result = true;

        if(!( term(Token.MINUS) && F() ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean F3()
    {
        // F -> NUMBER

        int flag = counter;
        boolean result = true;

        if(!( term(Token.NUMBER) ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }

    private boolean F4()
    {
        // F -> NUMBER

        int flag = counter;
        boolean result = true;

        if(!( term(Token.IDENTIFIER) ))
        {
            counter = flag; // BACKTRACK

            if(counter < tokens.size()) // POINT TO PREVIOUS TOKEN
                next = tokens.get(counter);

            result = false;
        }
        return result;
    }
}

Upvotes: 0

Views: 291

Answers (1)

Radiodef
Radiodef

Reputation: 37875

First thing, change this:

public LinkedList tokenize (String expression) {...}

to this:

public LinkedList<String> tokenize (String expression) {...}

And change this:

public Parser(LinkedList tokens) {...}

to this:

public Parser(LinkedList<Token> tokens) {...}

LinkedList (without a generic part) is called a raw type and facilitates an unchecked conversion. If there are more places where you use raw types, they also need to be changed. Removing all raw types from your code will almost certainly lead you to the error.

I strongly suspect you have code essentially like this:

Tokenizer t = ...;

// passing LinkedList<String> as a LinkedList<Token>
Parser p = new Parser(t.tokenize(...));

In other words you have skipped a step where you need to convert Strings to Tokens.

Upvotes: 1

Related Questions