Parser.java

/*
Class:       CS 4308 Section 03
Term:        Fall 2021
Name:       Faith Swetnam
Instructor:   Sharon Perry
Project:     Deliverable 2 Parser
Updated: 11/14/2021
 */

import java.io.File;
import java.util.ArrayList;

public class Parser {
    private static ArrayList<Node> nodes = new ArrayList<Node>();         //stores all nodes produced
    private static ArrayList<Integer> opcodes = new ArrayList<Integer>(); //stores opcodes to be compared against
    private static ArrayList<Error> errors = new ArrayList<Error>();      //stores Errors generated
    private static ArrayList<Token> tokens = new ArrayList<Token>();      //stores tokens generated by the scanner
    private static ArrayList<Token.TokenType> words = new ArrayList<Token.TokenType>(); //stores reserved words/keywords
    private static ArrayList<Token.TokenType> ops = new ArrayList<Token.TokenType>(); //stores valid operations
    private static Token nextToken;                                     //stores the current token being processed
    private static Token prevToken;                                     //stores the previous token processed
    private static Node rootNode = null;                                //stores the root node of the AST
    private static Node currNode = new Node();                          //stores the current AST node
    private static Node prevNode = new Node();                          //stores the parent of the current AST node
    private static int tokenCount = 0;                                  //stores the current index of the token arraylist
    private static boolean errorOccurred = false;                       //stores whether an Error has been generated

    //fills the opcodes arraylist with integer opcodes
    private static void fillOpcodes(){
        opcodes.add(0);opcodes.add(1);opcodes.add(2);opcodes.add(99);opcodes.add(1000);opcodes.add(1001);
        opcodes.add(1002);opcodes.add(1003);opcodes.add(1004);opcodes.add(1005);opcodes.add(1006);opcodes.add(1007);
        opcodes.add(1008);opcodes.add(1009);opcodes.add(2000);opcodes.add(2001);opcodes.add(2002);opcodes.add(2003);
        opcodes.add(2004); opcodes.add(2005);opcodes.add(2006);opcodes.add(2007);opcodes.add(2008);opcodes.add(2009);
        opcodes.add(2010);opcodes.add(2011);opcodes.add(2012);opcodes.add(2013);
    }

    //fills the words arraylist with TokenType reserved words and keywords
    private static void fillWords(){
        words.add(Token.TokenType.WHILE);words.add(Token.TokenType.ELSE);words.add(Token.TokenType.DO);
        words.add(Token.TokenType.IF);words.add(Token.TokenType.PRINT);words.add(Token.TokenType.THEN);
        words.add(Token.TokenType.END);words.add(Token.TokenType.EOF);words.add(Token.TokenType.THEN);
        words.add(Token.TokenType.L_PAREN);words.add(Token.TokenType.R_PAREN);words.add(Token.TokenType.FUNCT);
    }

    //ADDED for INTERPRETER
    private static void fillOperations(){
        ops.add(Token.TokenType.ADD_OP);ops.add(Token.TokenType.SUB_OP); ops.add(Token.TokenType.MUL_OP);
        ops.add(Token.TokenType.DIV_OP);
    }

    //checks all the opcodes for validity
    private static void checkOpcodes(){
        for(Token t: tokens){
            //if opcode is not valid
            if(!opcodes.contains(t.getType().opcode)){
                //generate an error
                createError("incorrect opcode", "Opcode: " + String.valueOf(t.getType().opcode), t.getLine());
            }
        }
    }

    //generates an error object, adds it to errors arraylist, and sets errorOccurred to true
    //takes in an error message, the value that threw the error, and the line it occurred on
    private static void createError(String msg, String value, int line){
        Error e = new Error(msg, value, line);
        errors.add(e);
        errorOccurred = true;
    }

    //gets the next token from tokens arraylist
    private static void getToken(){
        try {
            if(nextToken != null){
                prevToken = nextToken;
            }
            nextToken = tokens.get(tokenCount);
            tokenCount++;
            if(nextToken.getType() == Token.TokenType.ERROR){
                createError("scanner error", nextToken.getLexeme(), nextToken.getLine());
                return;
            }
        } catch (IndexOutOfBoundsException e){
            createError("index out of bounds", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
    }

    //creates a node object and adds it to the parent's children arraylist
    private static void createNode(Token token, Node root, Node parent, String grammar){
        //if the root has not been initialized
        if(rootNode == null){
            rootNode = new Node(token, grammar);
            currNode = rootNode;
            nodes.add(rootNode);
        //find the parent to assign the node to
        } else {
            if (root == parent) {
                prevNode = currNode;
                currNode = new Node(token, root, grammar);
                root.addChild(currNode);
                nodes.add(currNode);
                return;
            } else {
                int len = root.getChildren().size();
                for (int i = 0; i < len; i++) {
                        createNode(token, root.getChildren().get(i), parent, grammar);
                }
            }
        }
    }

    //prints the AST
    //specifically prints all Node objects in nodes and each of their children
    private static void printTree(){
        if(rootNode == null) {
            return;
        } else {
            for(Node node: nodes){
                if(node.getChildren().isEmpty()){
                    System.out.println(node.getGrammar());
                } else {
                    System.out.print(node.getGrammar() + " -> ");
                    for(Node child: node.getChildren()){
                        System.out.print(child.getGrammar() + " ");
                    }
                }
                System.out.println();
            }
        }
    }

    //prints the AST
    //specifically prints all Node objects in nodes and each of their children
    public static void printTree(Node root, ArrayList<Node> nodes){
        if(root == null) {
            return;
        } else {
            for(Node node: nodes){
                if(node.getChildren().isEmpty()){
                    System.out.println(node.getGrammar());
                } else {
                    System.out.print(node.getGrammar() + " -> ");
                    for(Node child: node.getChildren()){
                        System.out.print(child.getGrammar() + " ");
                    }
                }
                System.out.println();
            }
        }
    }

    //main driver function of the parser
    // <program> -> function id() <block> end
    private static void parse(){
        getToken();     //get first token
        createNode(nextToken, null, null, "<program>");
        if(nextToken.getType() == Token.TokenType.FUNCT){
            getToken();                     //process "function" keyword
            if(nextToken.getType() != Token.TokenType.LETTER){
                createError("function identifier expected", nextToken.getLexeme(), nextToken.getLine());
                return;
            } else {
                currNode.addToken(nextToken);
                getToken();     //process function identifier
                if(nextToken.getType() != Token.TokenType.L_PAREN){
                    createError("( expected", nextToken.getLexeme(), nextToken.getLine());
                    return;
                } else {
                    currNode.addToken(nextToken);
                    getToken();     //process (
                    if(nextToken.getType() != Token.TokenType.R_PAREN){
                        createError(") expected", nextToken.getLexeme(), nextToken.getLine());
                        return;
                    } else {
                        currNode.addToken(nextToken);
                        getToken();     //process )
                    }
                }
            }
        } else {
            createError("function expected", nextToken.getLexeme(), nextToken.getLine());
            return;
        }

        //while the program hasn't ended, and the TokenType of nextToken isn't NULL or ERROR...
        while(nextToken.getType() != Token.TokenType.EOF && nextToken.getType() != Token.TokenType.ERROR
                && nextToken.getType() != Token.TokenType.NULL){
            block(rootNode);
            if(errorOccurred){
                break;
            }
            //if the program hasn't ended, and the TokenType of nextToken isn't NULL or ERROR get the next Token
            if(nextToken.getType() != Token.TokenType.EOF && nextToken.getType() != Token.TokenType.ERROR
                    && nextToken.getType() != Token.TokenType.NULL)
                getToken();

        }

        //if the program has ended add a new node to the end of tree (add to rootNode)
        // grammar changed for D3 to be end of file
        if(nextToken.getType() == Token.TokenType.EOF && !errorOccurred){
            createNode(nextToken, rootNode, rootNode, "end of file");
        } else {
            //if "end" keyword is not encountered
            createError("EOF expected", nextToken.getLexeme(), nextToken.getLine());
        }
    }

    //block
    //takes in the parent Node(essentially the function that called it...)
    // <block> -> <statement> | <statement> <block>
    private static void block(Node parent) {
        //if the program hasn't ended, and the TokenType of nextToken isn't NULL, ERROR, or END...
        if (nextToken.getType() != Token.TokenType.EOF && nextToken.getType() != Token.TokenType.ERROR
                && nextToken.getType() != Token.TokenType.NULL && nextToken.getType() != Token.TokenType.END) {
            //create a block Node and call statement function
            createNode(nextToken, rootNode, parent, "<block>");
            Node blockNode = currNode;
            statement(blockNode);
        }
    }

    //statement expression
    //takes in its parent Node
    // <statement> -> <if_statement> | <assignment_statement> | <while_statement> | <print_statement> | <repeat_statement>
    private static void statement(Node parent){
        //create a statement Node
        createNode(nextToken, rootNode, parent, "<statement>");
        Node statementNode = currNode;
        //if the program hasn't ended, and the TokenType of nextToken isn't NULL, ERROR, or END...
        if(nextToken.getType() != Token.TokenType.EOF && nextToken.getType() != Token.TokenType.ERROR
                && nextToken.getType() != Token.TokenType.NULL && nextToken.getType() != Token.TokenType.END){
            switch(nextToken.getType()){
                case LETTER:
                    assignState(statementNode);
                    break;
                case IF:
                    ifState(statementNode);
                    break;
                case WHILE:
                    whileState(statementNode);
                    break;
                case PRINT:
                    printState(statementNode);
                    break;
                case REPEAT:
                    repeatState(statementNode);
                    break;
                default:
                    createError("unexpected statement", nextToken.getLexeme(), nextToken.getLine());
                    break;
            }
        }
    }

    //statement
    //takes in parent Node
    // <assignment_statement> -> id <assignment_operator> <arithmetic_expression>
    private static void assignState(Node parent){
        //create assignment_statement Node
        createNode(nextToken, rootNode, parent, "<assignment_statement>");
        Node assignNode = currNode;
        // add id to assignment_statement Node as a new Node
        // if it is a character identifier (length=1)
        if(nextToken.getType() == Token.TokenType.LETTER && nextToken.getLexeme().length() == 1
                && !words.contains(nextToken.getType())) {
            assignNode.addChild(new Node(nextToken, assignNode, "id"));
            getToken();
        } else {
            createError("identifier expected", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
        arithOp(assignNode); //calls artihOp() to process expression and operator
    }

    //if statement
    //takes in parent Node
    // <if_statement> -> if <boolean_expression> then <block> else <block> end
    private static void ifState(Node parent){
        //create if_statement Node
        createNode(nextToken, rootNode, parent, "<if_statement>");
        Node ifNode = currNode;
        //add 'if' keyword as new Node to ifNode
        ifNode.addChild(new Node(nextToken, ifNode, "if"));
        getToken(); //process 'if'
        boolExpr(ifNode); //boolExpr() call
        getToken(); //process end of boolEpr() and first block
        block(ifNode); //first block()
        if(nextToken.getType() == Token.TokenType.ELSE){
            //add 'else' keyword as new Node to ifNode
            ifNode.addChild(new Node(nextToken, ifNode, "else"));
            getToken(); //process 'else'
            block(ifNode); //second block
            if(nextToken.getType() == Token.TokenType.END){
                //add 'end' keyword as new Node to ifNode
                ifNode.addChild(new Node(nextToken, ifNode, "end"));
                getToken(); //process 'end'
            } else {
                createError("end expected", nextToken.getLexeme(), nextToken.getLine());
                return;
            }
        } else {
            createError("else expected", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
    }

    //while statement
    //takes in parent Node
    // <while_statement> -> while <boolean_expression> do <block> end
    private static void whileState(Node parent){
        //create while_statement Node
        createNode(nextToken, rootNode, parent, "<while_statement>");
        Node whileNode = currNode;
        //add 'while' keyword as new Node to whileNode
        whileNode.addChild(new Node(nextToken, whileNode, "while"));
        getToken(); //process 'while'
        boolExpr(whileNode); //boolExpr() call
        getToken(); //process end of boolExpr() to get block 1
        block(whileNode); //block() call
        getToken(); // process end of block
        if(nextToken.getType() == Token.TokenType.END){
            //add 'end' keyword as new Node to whileNode
            whileNode.addChild(new Node(nextToken, whileNode, "end"));
        } else {
            createError("end expected", nextToken.getLexeme(), nextToken.getLine());
        }
    }


    //repeat statement
    //takes in parent Node
    // <repeat_statement> -> repeat <block> until <boolean_expression>
    private static void repeatState(Node parent){
        //create repeat_statement node
        createNode(nextToken, rootNode, parent, "<repeat_statement>");
        Node repeatNode = currNode;
        //add 'repeat' keyword as new Node to repeatNode
        repeatNode.addChild(new Node(nextToken, repeatNode, "repeat"));
        getToken(); //process 'repeat'
        block(repeatNode); //block() call
        getToken(); //process end of block
        if (nextToken.getType() == Token.TokenType.UNTIL) {
            //add 'until' keyword as new Node to repeatNode
            repeatNode.addChild(new Node(nextToken, repeatNode, "until"));
            getToken(); //process until
            boolExpr(repeatNode); //boolExpr() call
            return;
        } else {
            createError("until expected", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
    }


    //boolean expression
    //takes in parent Node
    // <boolean_expression> -> <arithmetic_expression> <relative_op> <arithmetic_expression>
    private static void boolExpr(Node parent){
        //create repeat Node
        createNode(nextToken, rootNode, parent, "<boolean_expression>");
        Node boolNode = currNode;
        //check next Token is first argument
        if(nextToken.getType() == Token.TokenType.LETTER || nextToken.getType() == Token.TokenType.DIGIT){
            arithExpr(boolNode); //call arithExpr() for first argument
            getToken(); //process end of arithmetic_expression
            //check next Token is operation
            if(!words.contains(nextToken.getType())){
                relOp(boolNode); //call relOp
                getToken(); // process operation
                //check next Token is second argument
                if(nextToken.getType() == Token.TokenType.LETTER || nextToken.getType() == Token.TokenType.DIGIT){
                    arithExpr(boolNode); //call second arithmetic_expression
                } else {
                    createError("unexpected argument", nextToken.getLexeme(), nextToken.getLine());
                    return;
                }
            } else {
                createError("unexpected operation", nextToken.getLexeme(), nextToken.getLine());
                return;
            }
        } else {
            createError("unexpected argument", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
    }

    //relative operations
    //takes in parent Node
    // <relative_operation> -> le_operator | lt_operator | ge_operator | gt_operator | eq_operator | ne_operator
    private static void relOp(Node parent){
        //create relative_operation Node
        createNode(nextToken, rootNode, parent, "<relative_op>");
        Node relNode = currNode;
        //switch statement determines which operatio nextToken is and adds it as a new child Node to relative_operation Node
        switch(nextToken.getType()){
            case LE_OP:
                currNode.addChild(new Node(nextToken, relNode, "le_operator"));
                break;
            case LT_OP:
                currNode.addChild(new Node(nextToken, relNode, "lt_operator"));
                break;
            case GE_OP:
                currNode.addChild(new Node(nextToken, relNode, "ge_operator"));
                break;
            case GT_OP:
                currNode.addChild(new Node(nextToken, relNode, "gt_operator"));
                break;
            case EQ_OP:
                currNode.addChild(new Node(nextToken, relNode, "eq_operator"));
                break;
            case NE_OP:
                currNode.addChild(new Node(nextToken, relNode, "ne_operator"));
                break;
            //if nextToken is not an operation an Error is generated
            default:
                createError("unexpected operation", nextToken.getLexeme(), nextToken.getLine());
                break;
        }
    }

    //arithmetic_operation
    //takes in parent Node
    // <arith_op> -> add_operator | sub_operator | mul_operator | div_operator
    // I also added the assignment_operator and the addition_assignment operator
    private static void arithOp(Node parent){
        switch(nextToken.getType()){
            case ASSIGN_OP:
                parent.addChild(new Node(nextToken, parent, "assignment_operator"));
                getToken();
                if(nextToken.getType() == Token.TokenType.DIGIT || nextToken.getType() == Token.TokenType.LETTER){
                    arithExpr(parent);
                } else {
                    createError("identifier or literal_integer expected", nextToken.getLexeme(), nextToken.getLine());
                }
                break;
            case AE_OP:
                parent.addChild(new Node(nextToken, parent, "addition_assignment"));
                getToken();
                if(nextToken.getType() == Token.TokenType.DIGIT || nextToken.getType() == Token.TokenType.LETTER){
                    arithExpr(parent);
                } else {
                    createError("identifier or literal_integer expected", nextToken.getLexeme(), nextToken.getLine());
                }
                break;
            case DIV_OP:
                parent.addChild(new Node(nextToken, parent, "division_operator"));
                getToken();
                break;
            case MUL_OP:
                parent.addChild(new Node(nextToken, parent, "multiplication_operator"));
                getToken();
                break;
            case ADD_OP:
                parent.addChild(new Node(nextToken, parent, "addition_operator"));
                getToken();
                break;
            case SUB_OP:
                parent.addChild(new Node(nextToken, parent, "subtraction_operator"));
                getToken();
                break;
            default:
                createError("unexpected operation", nextToken.getLexeme(), nextToken.getLine());
                break;
        }
    }

    //arithmetic_expression
    //takes in parent Node
    // <arithmetic_expression> -> <id> | <literal_integer> | <arithmetic_expression> <arithmetic_op> <arithmetic_expression>
    private static void arithExpr(Node parent){
        //create arithmetic_expression Node
        createNode(nextToken, rootNode, parent, "<arithmetic_expression>");
        Node arithNode = currNode;
        prevToken = nextToken;
        //switch statement determines the type of nextToken
        switch(nextToken.getType()){
            case LETTER:
                arithNode.addChild(new Node(nextToken, arithNode, "id"));
                break;
            case DIGIT:
                arithNode.addChild(new Node(nextToken, arithNode, "literal_integer"));
                break;
        }
        getToken();
        //if the nextToken after first arithmetic expression is an operation
        if(ops.contains(nextToken.getType())){
            //process arithmetic operation
            arithOp(arithNode);
            if(nextToken.getType() == Token.TokenType.DIGIT || nextToken.getType() == Token.TokenType.LETTER){
                arithExpr(arithNode);
                getToken();
            } else {
                createError("identifier or literal_integer expected", nextToken.getLexeme(), nextToken.getLine());
            }
        }
            nextToken = prevToken;
            tokenCount--;
    }

    //print statement
    //takes in parent Node
    // <print_statement> -> print ( <arithmetic_expression> )
    private static void printState(Node parent){
        //create print Node
        createNode(nextToken, rootNode, parent, "<print_statement>");
        Node printNode = currNode;
        //add print keyword as new Node to printNode
        printNode.addChild(new Node(nextToken, printNode, "print"));
        getToken(); // process print
        if(nextToken.getType() == Token.TokenType.L_PAREN){
            //add ( as new Node to printNode
            printNode.addChild(new Node(nextToken, printNode, "("));
            getToken(); // process (
            arithExpr(printNode); //arithExpr() call
            getToken(); // process end of arithExpr()
            if(nextToken.getType() == Token.TokenType.R_PAREN){
                //add ) as new Node to printNode
                printNode.addChild(new Node(nextToken, printNode, ")"));
                getToken(); //process )
                return;
            } else {
                createError(") expected", nextToken.getLexeme(), nextToken.getLine());
                return;
            }
        } else {
            createError("( expected", nextToken.getLexeme(), nextToken.getLine());
            return;
        }
    }

    //NEW METHOD
    //call parser - designed for the interpreter
    //callable main
    public static Node getRootNode(File f){
        fillOpcodes();
        checkOpcodes();
        fillWords();
        fillOperations();
        tokens = LexicalAnalyzer.getTokenList(f);
        if(tokens != null){
            parse();

            if(errorOccurred){
                for(Error e: errors){
                    e.printError();
                }
            } else {
                return rootNode;
            }
        }
        return null;
    }

    public static ArrayList<Node> getNodes(){
        return nodes;
    }

    public static void main(String args[]){
        fillOpcodes(); //fill opcodes ArrayList
        checkOpcodes(); //ensure all Token's opcodes are valid
        fillWords(); //fill words ArrayList
        fillOperations();
        File f = new File("src/Julia-Files/Test1.jl");
        //get tokens for file
        tokens = LexicalAnalyzer.getTokenList(f);
        parse();
        //if errorOccurred printError otherwise printTree
        if(errorOccurred){
            errors.get(0).printError();
        } else
            printTree();
    }

}