diff options
Diffstat (limited to 'src/Compiler/Parser.java')
| -rw-r--r-- | src/Compiler/Parser.java | 241 |
1 files changed, 223 insertions, 18 deletions
diff --git a/src/Compiler/Parser.java b/src/Compiler/Parser.java index ae2ed23..433035c 100644 --- a/src/Compiler/Parser.java +++ b/src/Compiler/Parser.java @@ -5,17 +5,27 @@ 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()){ @@ -28,32 +38,53 @@ public class Parser { } + /** + * 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); - } else if(matchAndAdvance(TokenType.FUNCTION)){ + + //Check for function or subroutine definition + } else if(matchAndAdvance(TokenType.FUNCTION)||matchAndAdvance(TokenType.SUBROUTINE)){ + String returntype=null; - if(matchAndAdvance(TokenType.INT)){ - returntype="int"; - } else if (matchAndAdvance(TokenType.REAL)){ - returntype="real"; - }else{ - throw error(getCurrentToken(), "Expected function return type"); + 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="real"; + }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)){ @@ -67,52 +98,85 @@ public class Parser { } while(matchAndAdvance(TokenType.COMMA)); matchOrError(TokenType.RIGHT_PAREN, "Expected ')'"); } - Statement block = blockStatement(true); + + 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(), "Expected program or function"); + 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(); } - //Clean up and reduce code mess + /** + * 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("real"); } 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{ @@ -120,12 +184,15 @@ public class Parser { return new Statement.VariableDeclaration(varName,"real"); } - //Could be improved significatly when verifiying length is a positive integer + //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"); } @@ -135,11 +202,13 @@ public class Parser { 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.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{ @@ -150,19 +219,31 @@ public class Parser { 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{ @@ -171,10 +252,18 @@ public class Parser { } } + /** + * 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"); } @@ -184,15 +273,22 @@ public class Parser { } 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"); @@ -203,13 +299,18 @@ public class Parser { return new Statement.PrintStatement(exprList); } - //Could be cleaned up to handle else statements better + /** + * 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); } @@ -220,12 +321,19 @@ public class Parser { 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(); @@ -239,7 +347,12 @@ public class Parser { } + /** + * 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"); @@ -248,18 +361,31 @@ public class Parser { 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); @@ -267,11 +393,19 @@ public class Parser { 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)){ @@ -282,6 +416,10 @@ public class Parser { 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(); @@ -298,8 +436,13 @@ public class Parser { 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(); @@ -308,8 +451,13 @@ public class Parser { 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(); @@ -318,8 +466,13 @@ public class Parser { return createdExpression; } + /** + * Method to parse a factor expression + * @return an expression of rank factor or lower + */ private Expression factor(){ Expression createdExpression = primary(); + //Check for multiplication or division expressions while (matchAndAdvance(TokenType.STAR)||matchAndAdvance(TokenType.SLASH)){ Token op = getPreviousToken(); Expression right = primary(); @@ -328,26 +481,36 @@ public class Parser { 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); @@ -356,7 +519,9 @@ public class Parser { 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(); @@ -369,24 +534,35 @@ public class Parser { 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; @@ -394,6 +570,12 @@ public class Parser { 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; @@ -401,23 +583,46 @@ public class Parser { 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(); |