path: root/src/Compiler/Parser.java

package Compiler;

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

/**
 * Class for parsing the source code, utilising the recursive descent parsing method
 */
public class Parser {
    private final List<Token> tokens;
    private int currentToken = 0;
    private final Map<String,String> definedVars = new HashMap<>();
    List<Statement> statements =  new ArrayList<>();

    /**
     * Constructor of a parser object
     * @param tokens the list of tokens representing the source code
     */
    Parser(List<Token> tokens){
        this.tokens=tokens;
    }

    /**
     * Method for parsing the list of tokens
     * @return A list of statements for the source code
     */
    List<Statement> parse(){
        try{
            while (!checkEOF()){
                statements.add(functionCalls());
            }
        }catch (Error e){
            return null;
        }
        return statements;
        
    }

    /**
     * Method to extracting the main function, or other functions
     * @return A statement for a function or main function
     */
    private Statement functionCalls(){

        //Check for main function definition
        if(matchAndAdvance(TokenType.PROGRAM)){
            matchOrError(TokenType.IDENTIFIER, "Expected program name");
            Token programname = getPreviousToken();
            Statement block = blockStatement(false);
            matchOrError(TokenType.PROGRAM,"Programs must end in 'program'");
            matchOrError(TokenType.IDENTIFIER,"Expected program name");

            //Check program names match
            if(!(getPreviousToken().text.equals(programname.text))){
                throw error(getPreviousToken(), "Program names do not match");
            }
            return new Statement.MainFunction(block);

        //Check for function or subroutine definition
        } else if(matchAndAdvance(TokenType.FUNCTION)||matchAndAdvance(TokenType.SUBROUTINE)){

            String returntype=null;
            boolean isfunction=false;
            //Get function return data type
            if(getPreviousToken().type==TokenType.FUNCTION){
                isfunction=true;
                if(matchAndAdvance(TokenType.INT)){
                    returntype="int";
                } else if (matchAndAdvance(TokenType.REAL)){
                    returntype="double";
                }else{
                    throw error(getCurrentToken(), "Expected function return type");
                }
            }

            matchOrError(TokenType.IDENTIFIER, "Expected function name");
            Token name = getPreviousToken();

            //Add function name to the list of defined values
            definedVars.put(name.text, "function");
            matchOrError(TokenType.LEFT_PAREN, "Expected '(");
            List<Expression> arguments=new ArrayList<>();
            List<String> types = new ArrayList<>();

            //Extract the arguments for the function
            if(!matchAndAdvance(TokenType.RIGHT_PAREN)){
                do{
                    if(matchAndAdvance(TokenType.INT)){
                        types.add("int");
                    } else if (matchAndAdvance(TokenType.REAL)){
                        types.add("double");
                    } else if (matchAndAdvance(TokenType.STRING)){
                        types.add("char*");
                    }
                    arguments.add(expression());
                } while(matchAndAdvance(TokenType.COMMA));
                matchOrError(TokenType.RIGHT_PAREN, "Expected ')'");
            }

            Statement block = blockStatement(isfunction);

            //Add the function declaration to the start of the list of statements
            statements.add(0,new Statement.FunctionDeclaration(name,types,returntype));
            return new Statement.Function(name,block,arguments,types,returntype);
        }
        throw error(getCurrentToken(), "Program must start with program or function");
    }

    /**
     * Method for extracting a single statement, excluding function definitions
     * @return any type of statement
     */
    private Statement statement(){
        //Check for variable definition
        if(checkToken(TokenType.INT)||checkToken(TokenType.REAL)||checkToken(TokenType.STRING)){
            return declaration();
        }

        //Check for print statement
        else if (matchAndAdvance(TokenType.PRINT)){
            return printStatement();

        //Check for if statement
        }else if (matchAndAdvance(TokenType.IF)){
            return ifStatement();

        //Check for do statement
        }else if (matchAndAdvance(TokenType.DO)){
            return doStatement();

        //Check for return statement
        }else if (matchAndAdvance(TokenType.RETURN)){
            return returnStatement();
        }

        //If no statement matches, assume an expression statement
        return expressionStatement();
    }


    /**
     * Method for parsing a variable definition
     * @return A variable definition statement
     */
    private Statement declaration(){
        //Check if the variable is an integer
        if (matchAndAdvance(TokenType.INT)){

            //Check for array declaration
            if(matchAndAdvance(TokenType.DIMENSION)){
                return arrayDeclaration("int");
            }

            matchOrError(TokenType.DEFINE, ":: Required for variable definition");
            matchOrError(TokenType.IDENTIFIER,"Expected variable name.");
            Token varName = getPreviousToken();

            //Ensure that a variable with the same name has not been defined
            if(definedVars.containsKey(varName.text)){
                throw error(varName, "Cannot define multiple variables with the same name");
            }else{
                definedVars.put(varName.text,"int");
                return new Statement.VariableDeclaration(varName,"int");
            }
        
        //Check if the variable is a real type
        } else if (matchAndAdvance(TokenType.REAL)){

            //Check for array declaration
            if(matchAndAdvance(TokenType.DIMENSION)){
                return arrayDeclaration("double");
            }
            matchOrError(TokenType.DEFINE, ":: Required for variable definition");
            matchOrError(TokenType.IDENTIFIER,"Expected variable name.");
            Token varName = getPreviousToken();

            //Ensure that a variable with the same name has not been defined
            if(definedVars.containsKey(varName.text)){
                throw error(varName, "Cannot define multiple variables with the same name");
            }else{
                definedVars.put(varName.text,"double");
                return new Statement.VariableDeclaration(varName,"double");
            }
        
        //Check if the variable is a string
        } else if (matchAndAdvance(TokenType.STRING)){
            //Extract the length of the string
            matchOrError(TokenType.LEFT_PAREN, "Length of string must be defined");
            matchOrError(TokenType.LEN, "Length of string must be defined");
            matchOrError(TokenType.EQUALS, "Length of string must be defined");
            Expression length = expression();

            //Ensure the length of the string is a positive integer
            if(!(length instanceof Expression.Literal)){
                throw error(getCurrentToken(),"String length must be a number");
            }
            if(!((Expression.Literal)length).type.equals("int")){
                throw error(getCurrentToken(),"String length must be a integer"); 
            }
            if((int)((Expression.Literal)length).value.value<1){
                throw error(getCurrentToken(),"String length must be greater then 0"); 
            }

            matchOrError(TokenType.RIGHT_PAREN, "Length of string must be defined");
            matchOrError(TokenType.DEFINE, ":: Required for variable definition");
            matchOrError(TokenType.IDENTIFIER,"Expected variable name.");
            Token varName = getPreviousToken();

            //Ensure that a variable with the same name has not been defined
            if(definedVars.containsKey(varName.text)){
                throw error(varName, "Cannot define multiple variables with the same name");
            }else{
                definedVars.put(varName.text,"string");
                return new Statement.StringDeclaration(varName,length);
            }
        }
        return null;
    }

    /**
     * Method to parse an array declaration
     * @param type The data type of the array
     * @return A statement representing the array declaration
     */
    private Statement arrayDeclaration(String type){
        matchOrError(TokenType.LEFT_PAREN,"Expected ')'");

        //Extract the size of the array
        List<Expression> dimensions = new ArrayList<>();
        Expression dimension = expression();
        dimensions.add(dimension);

        //Extract the size of each dimension of the array
        while(matchAndAdvance(TokenType.COMMA)){
            dimension = expression();
            dimensions.add(dimension);
        }

        matchOrError(TokenType.RIGHT_PAREN, "Expected ')'");
        matchOrError(TokenType.DEFINE, ":: Required for variable definition");
        matchOrError(TokenType.IDENTIFIER,"Expected variable name.");
        Token varName = getPreviousToken();

        //Ensure that a variable with the same name has not been defined
        if(definedVars.containsKey(varName.text)){
            throw error(varName, "Cannot define multiple variables with the same name");
        }else{
            definedVars.put(varName.text,"array");
            return new Statement.ArrayDeclaration(varName, type, dimensions);
        }
    }

    /**
     * Method for parsing a block of statements
     * @param isFunction whether the block is for a function and so must contain a return statement
     * @return a statement representing a block
     */
    private Statement blockStatement(boolean isFunction){
        boolean hasReturn=false;
        List<Statement> statements = new ArrayList<>();

        //Match statement until an end or else token has been reached
        while(!matchAndAdvance(TokenType.END)&&!checkToken(TokenType.ELSE)){
            //Ensure the end of the file has not been reached
            if(checkEOF()){
                throw error(getCurrentToken(),"end missing from block");
            }
            Statement statement = statement();
            if(statement.getStatmentType()=="return"){
                hasReturn=true;
            }
            statements.add(statement);
        }
        //Ensure that a function block contains a return statement
        if(isFunction&&!hasReturn){
            throw error(getPreviousToken(), "Function must contain a return statement");
        }
        return new Statement.BlockStatement(statements);
    }

    /**
     * Method for parsing a print statement
     * @return A print statement object
     */
    private Statement printStatement(){
        matchOrError(TokenType.STAR, "Syntax, print *, item1, item2...");
        List<Expression> exprList = new ArrayList<>();

        //Get the list of printed values
        while(matchAndAdvance(TokenType.COMMA)){
            if(checkEOF()){
                throw error(getCurrentToken(),"reached end of file");
            }
            Expression expr = expression();
            exprList.add(expr);
        }
        return new Statement.PrintStatement(exprList);
    }

    /**
     * Method for parsing an if statement
     * @return A statement representing an if statement
     */
    private Statement ifStatement(){
        Expression condition = expression();
        if(matchOrError(TokenType.THEN, "then expected after if statement")){
            //Extract if block
            Statement ifBlock = blockStatement(false);
            Statement elseBlock=null;
            
            //Extract else block if required
            if(matchAndAdvance(TokenType.ELSE)){
                elseBlock=blockStatement(false);
            }
            matchOrError(TokenType.IF, "If statements end with if");
            Statement ifstatement = new Statement.IfStatement(condition, ifBlock,elseBlock);
            return ifstatement;
        }
        return null;
    }

    /**
     * Method for parsing a do statement
     * @return A statement representing a do statement
     */
    private Statement doStatement(){
        //Check for do while statement
        if(matchAndAdvance(TokenType.WHILE)){
            return whileStatement();
        }
        Expression variable =expression();
        matchOrError(TokenType.EQUALS, "'=' missing");

        //Extract start, stop, and step variables
        Expression start = expression();
        matchOrError(TokenType.COMMA, " use ',' between values");
        Expression stop = expression();
        Expression step = null;
        if(matchAndAdvance(TokenType.COMMA)){
           step = expression();
        }
        Statement codeBlock = blockStatement(false);
        matchOrError(TokenType.DO, "Do statements end with do");
        return new Statement.DoStatement(variable, start, stop, step,codeBlock);

    }

    /**
     * Method to parse a do-while statement
     * @return a do-while statement object
     */
    private Statement whileStatement(){
        //Extract condition
        matchOrError(TokenType.LEFT_PAREN, " missing '(' for do statement condition");
        Expression condition = expression();
        matchOrError(TokenType.RIGHT_PAREN, " missing ')' for do  condition");
        Statement codeBlock = blockStatement(false);
        matchOrError(TokenType.DO, "Do while statements end with do");
        return new Statement.DoWhileStatement(condition,codeBlock);
    }

    /**
     * Method to parse a return statement
     * @return a return statement object
     */
    private Statement returnStatement(){
        Expression returnValue = expression();
        return new Statement.ReturnStatement(returnValue);
    }

    /**
     * Method to parse an expression statement
     * @return an expression statement object
     */
    private Statement expressionStatement(){
        Expression expression = assignment();
        return new Statement.ExpressionStatement(expression);
    }

    /**
     * Method to parse an assignment expression
     * @return an assignment expression object
     */
    private Expression assignment(){
        Expression variable = expression();
        //Check for an equals token
        if (matchAndAdvance(TokenType.EQUALS)){
            Expression assignedvalue = expression();
            return new Expression.AssignmentExpression(variable,assignedvalue);
        }
        return variable;
    }

    /**
     * Method to parse a non-assignment expression
     * @return an expression object
     */
    private Expression expression(){
        Expression createdExpression = equality();
        return createdExpression;
    }

    /**
     * Method to parse an equality comparison expression
     * @return an expression of rank equality or lower
     */
    private Expression equality(){
        Expression createdExpression = logical();
        while (matchAndAdvance(TokenType.EQUALITY)||matchAndAdvance(TokenType.NOT_EQUAL)){
            Token op = getPreviousToken();
            Expression right = logical();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    /**
     * Method to parse a logical expression
     * @return an expression of rank logical or lower 
     */
    private Expression logical(){
        if(matchAndAdvance(TokenType.NOT)){
            Token op = getPreviousToken();
            Expression right = comparison();
            Expression createdExpression = new Expression.Singular(op, right);
            return createdExpression;
        }
        Expression createdExpression = comparison();
        while (matchAndAdvance(TokenType.AND)||matchAndAdvance(TokenType.OR)){
            Token op = getPreviousToken();
            Expression right = comparison();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    /**
     * Method to parse a comparison expression
     * @return an expression of rank comparison or lower 
     */
    private Expression comparison(){
        Expression createdExpression = term();
        //Check for different types of comparison
        while (matchAndAdvance(TokenType.GREATER)||matchAndAdvance(TokenType.LESS)||matchAndAdvance(TokenType.GREATER_EQUAL)||matchAndAdvance(TokenType.LESS_EQUAL)){
            Token op = getPreviousToken();
            Expression right = term();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    /**
     * Method to parse a term expression
     * @return an expression of rank term or lower 
     */
    private Expression term(){
        Expression createdExpression = factor();
        //Check for addition or subtraction expression
        while (matchAndAdvance(TokenType.PLUS)||matchAndAdvance(TokenType.MINUS)){
            Token op = getPreviousToken();
            Expression right = factor();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    /**
     * Method to parse a factor expression
     * @return an expression of rank factor or lower 
     */
    private Expression factor(){
        Expression createdExpression = exponent();
        //Check for multiplication or division expressions
        while (matchAndAdvance(TokenType.STAR)||matchAndAdvance(TokenType.SLASH)){
            Token op = getPreviousToken();
            Expression right = exponent();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    private Expression exponent(){
        Expression createdExpression = primary();
        //Check for multiplication or division expressions
        while (matchAndAdvance(TokenType.EXPONENT)){
            Token op = getPreviousToken();
            Expression right = primary();
            createdExpression = new Expression.Binary(createdExpression, op, right);
        }
        return createdExpression;
    }

    /**
     * Method to parse a primary expression
     * @return a primary expression 
     */
    private Expression primary(){
        //Check for singular numbers
        if (matchAndAdvance(TokenType.NUMBER)){
            //Check number type
            if(getPreviousToken().value instanceof Integer){
                return new Expression.Literal(getPreviousToken(),"int");
            } else if(getPreviousToken().value instanceof Double){
                return new Expression.Literal(getPreviousToken(),"double");
            }
        }
        //Check for strings
        if (matchAndAdvance(TokenType.STRING)){
            return new Expression.Literal(getPreviousToken(), "string");
        }
        //Check for variable names
        if (matchAndAdvance(TokenType.IDENTIFIER)) {
            Token name= getPreviousToken();
            //Check for function calls or array assignments
            if(matchAndAdvance(TokenType.LEFT_PAREN)){
                //Parse array if array with same name has been previously defined
                if(definedVars.containsKey(name.text)){
                    if(definedVars.get(name.text).equals("array")){
                        List<Expression> positions = new ArrayList<>();
                        Expression position = expression();
                        positions.add(position);
                        //Parse array positions for each dimension
                        while(matchAndAdvance(TokenType.COMMA)){
                            position = expression();
                            positions.add(position);
                        }
                        matchOrError(TokenType.RIGHT_PAREN,"Expected ')'");
                        return new Expression.ArrayVariable(name, positions);
                    }
                }
                //If not previously declared, assume function call
                List<Token> arguments = new ArrayList<>();
                //Parse function call arguments
                do{
                    matchOrError(TokenType.IDENTIFIER, "Expected argument");
                    Token argumentValue = getPreviousToken();
                    if(definedVars.containsKey(argumentValue.text)){
                        arguments.add(argumentValue);
                    }else{
                        throw error(argumentValue, "Argument undefined");
                    }
                }while(matchAndAdvance(TokenType.COMMA));
                matchOrError(TokenType.RIGHT_PAREN, "Expected ')");
                return new Expression.FunctionCall(name, arguments);
            }
            //Parse single variable name
            return new Expression.Variable(getPreviousToken());
          }

        //Parse bracketed expressions
        if (matchAndAdvance(TokenType.LEFT_PAREN)){
            Expression expr = expression();
            matchOrError(TokenType.RIGHT_PAREN,"Expected ')'");
            return new Expression.BracketedExpression(expr);
        }
        //Throw an error if the expression was not recognised
        throw error(getCurrentToken(),"Unknown syntax error");
    }
    /**
     * Method to move ahead one token
     */
    private void advanceToken(){
        if (!checkEOF()) {
            currentToken++;
        };
    }
    
    /**
     * Method to compare the current token with a given token, and move ahead if a match is found
     * @param type the token type to compare against
     * @return if the match was successful
     */
    private boolean matchAndAdvance(TokenType type){
        //If the tokens are a match, advance ahead
        if (checkToken(type)) {
            advanceToken();
            return true;
        }
        return false;
    }

    /**
     * Method to check if the current token matches a given token, and throw an error if they do not match
     * @param type the token type to compare against
     * @param errorMessage the message to report if a match is not found
     * @return a boolean to say if a match was successful
     */
    private boolean matchOrError(TokenType type,String errorMessage){
        if (matchAndAdvance(type)){
            return true;
        }
        throw error(getCurrentToken(),errorMessage);
    }

    /**
     * Method to comapre the current token to a given token
     * @param type the token type to compare against
     * @return if the match was successful
     */
    private boolean checkToken(TokenType type){
        if (checkEOF()) return false;
        return getCurrentToken().type == type; 
    }

    /**
     * Method to check for the end of the file
     * @return if the end of the file has been reached
     */
    private boolean checkEOF(){
        return tokens.get(currentToken).type==TokenType.EOF;
    }
    
    /**
     * Method to get the current token
     * @return the token at the current position
     */
    private Token getCurrentToken(){
        return tokens.get(currentToken);
    }

    /**
     * Method to get the previous token
     * @return the previous token
     */
    private Token getPreviousToken(){
        return tokens.get(currentToken - 1);
    }

    /**
     * Method to report an error to the user during parsing
     * @param token the token the error was detected on
     * @param message the message to display to the user
     * @return An error object to stop parsing
     */
    private Error error(Token token, String message){
        Language.displayError(token ,message);
        return new Error();
    }


}