Project DescriptionIn this project, you will implement recursive descent parser discussed in the class.Add the following method to Num class.static Num evaluateExp(String expr): parse/evaluate the...

Hello, I need help with this assignment. It has to be implemented using Java.


Project Description In this project, you will implement recursive descent parser discussed in the class. Add the following method to Num class. static Num evaluateExp(String expr): parse/evaluate the given expression and return the resulting number. You need to implement the recursive descent parser discussed in the class. Assume that the grammar is the same as the one we discussed in the class. If the given string is not valid, i.e, not a string that can be generated by the grammar, the method should throw an exception. The operands and operators in the input string may or may not be separated by empty space. For example, both “(3+4) * 5” and “(3 + 4) *5" are valid inputs. The numbers in the expression can be of arbitrary length. Use Num. If there are '-" and/or '/' operators in the expression, throw unsupported operator exception. Use StringBuilder to tokenize the input string, as strings are immutable in Java. The following methods are optional. « static String toPostfix(String expr): Implement shunting yard algorithm « static Num evaluatePostfix(String[] expr): Evaluate an expression in postfix and return the resulting number. PowerPoint Presentation Applications of Queues and Stacks Sridhar Alagar Shunting Yard Algorithm • Infix notation: humans understand well • Postfix notation: expression can be unambiguously evaluated • Shunting yard algorithm: convert exp. in infix to postfix CS 6301 IDSA 2 Shunting Yard: Example CS 6301 IDSA 3 Input 3+4*5/(2+1)^2 Output (queue) Stack Current token is operand add to output queue Shunting Yard: Example CS 6301 IDSA 4 Input +4*5/(2+1)^2 Output (queue) 3 Stack Current token is operator stack is empty push to stack Shunting Yard: Example CS 6301 IDSA 5 Input 4*5/(2+1)^2 Output (queue) 3 + Stack Current token is operand add to output queue Shunting Yard: Example CS 6301 IDSA 6 Input *5/(2+1)^2 Output (queue) 34 + Stack Current token is operator top of stack has lower precedence op push token Shunting Yard: Example CS 6301 IDSA 7 Input 5/(2+1)^2 Output (queue) 34 * + Stack Current token is operand add to output queue Shunting Yard: Example CS 6301 IDSA 8 Input /(2+1)^2 Output (queue) 345 * + Stack Current token is operator top of stack has equal precedence op but left associative pop to output queue Shunting Yard: Example CS 6301 IDSA 9 Input /(2+1)^2 Output (queue) 345* + Stack Current token is operator top of stack has lower precedence op push token Shunting Yard: Example CS 6301 IDSA 10 Input (2+1)^2 Output (queue) 345* / + Stack Current token is ‘(‘ push token Shunting Yard: Example CS 6301 IDSA 11 Input 2+1)^2 Output (queue) 345* ( / + Stack Current token is operand add to output queue Shunting Yard: Example CS 6301 IDSA 12 Input +1)^2 Output (queue) 345*2 ( / + Stack Current token is operator top of stack is ‘(‘ push token Shunting Yard: Example CS 6301 IDSA 13 Input 1)^2 Output (queue) 345*2 + ( / + Stack Current token is operand add it to output queue Shunting Yard: Example CS 6301 IDSA 14 Input )^2 Output (queue) 345*21 + ( / + Stack Current token is ‘)’ pop stack to output till top == ‘(‘ pop ‘(‘ and discard discard token Shunting Yard: Example CS 6301 IDSA 15 Input ^2 Output (queue) 345*21+ / + Stack Current token is operator top of stack has lower precedence op push token Shunting Yard: Example CS 6301 IDSA 16 Input 2 Output (queue) 345*21+ ^ / + Stack Current token is operand add to output queue Shunting Yard: Example CS 6301 IDSA 17 InputOutput (queue) 345*21+2 ^ / + Stack No more tokens pop stack to output till empty Shunting Yard: Example CS 6301 IDSA 18 Input 3+4*5/(2+1)^2 Output (queue) 345*21+2^/+ Stack Shunting Yard Algorithm 19 while next token t not null { if t is an operand add to output queue else if t is an operator while (stack top has higher precedence or equal precedence but left associative) pop stack to output queue push t else if t is ‘(‘ push t else if t is ‘)’ while stack top is not ‘(‘ pop stack top to output queue pop and discard // if not ‘(‘, error } // end while pop the remaining operators from stack to output Recursive Descent Parser • What does a parser do? • Given grammar G, and string s. • Does s belong to the language generated by G? • Parser for G will verify, and if so, construct a derivation tree or evaluate it. CS 6301 IDSA 20 Parser CS 6301 IDSA 21 Tokenizer Parser Back end of compiler input string tokens AST Grammar for Arithmetic Expression 22 E -> E addop T | T T -> T multop F | F F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 Few Observations about the grammar: E is the start symbol has terminal and non-terminal symbols lhs has only non-terminal symbols production rules on rhs Goal: Write a parser for this grammar. Derivation Tree for a given input 23 E -> E addop T | T T -> T multop F | F F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 Input = 3+4*2 How to write a parser for the grammar? 24 E -> E addop T | T T -> T multop F | F F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 One method for every non-terminal For every non-terminal in the production rule (rhs) its method is invoked Terminal on the rhs leads to consuming/evaluating the token Is there a problem with the left recursion in the grammar? Avoid left recursion 25 E -> E addop T | T T -> T multop F | F F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 E -> T {addop T}* T -> F {multop F}* F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 Parser for evaluating an arithmetic exp. • Input to the parser: tokens – Queue • Output is evaluated value of the input • Every method for non-terminal returns a integer value CS 6301 IDSA 26 Method to evaluate E 27 int evalE(Queue qt){ int val1 = evalT(qt); while((qt.peek().equals(“+”) || (qt.peek().equals(“-”)){ String oper = qt.remove(); int val2 = evalT(qt); if(oper.equals(“+”)) val1 += val2; else val1 -= val2 } return val1; } E -> T {addop T}* T -> F {multop F}* F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 Method to evaluate T 28 int evalT(Queue qt){ int val1 = evalF(qt); while((qt.peek().equals(“*”) || (qt.peek().equals(“/”)){ String oper = qt.remove(); int val2 = evalF(qt); if(oper.equals(“*”)) val1 *= val2; else val1 /= val2 } return val1; } E -> T {addop T}* T -> F {multop F}* F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 Method to evaluate F 29 int evalF(Queue qt){ if((qt.peek().equals(“(”){ String oper = qt.remove(); int val = evalE(qt); oper = qt.remove(); //”)” } else { String num = qt.remove(); val = Integer.parseInt(num); } return val; } E -> T {addop T}* T -> F {multop F}* F -> (E) | num addop -> +|- multop -> *|/ num -> digit num | digit digit -> 0|1|…|9 References https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Recursive_descent_parser CS 6301 IDSA 30 https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Recursive_descent_parser Slide 1: Applications of Queues and Stacks Slide 2: Shunting Yard Algorithm Slide 3: Shunting Yard: Example Slide 4: Shunting Yard: Example Slide 5: Shunting Yard: Example Slide 6: Shunting Yard: Example Slide 7: Shunting Yard: Example Slide 8: Shunting Yard: Example Slide 9: Shunting Yard: Example Slide 10: Shunting Yard: Example Slide 11: Shunting Yard: Example Slide 12: Shunting Yard: Example Slide 13: Shunting Yard: Example Slide 14: Shunting Yard: Example Slide 15: Shunting Yard: Example Slide 16: Shunting Yard: Example Slide 17: Shunting Yard: Example Slide 18: Shunting Yard: Example Slide 19: Shunting Yard Algorithm Slide 20: Recursive Descent Parser Slide 21: Parser Slide 22: Grammar for Arithmetic Expression Slide 23: Derivation Tree for a given input Slide 24: How to write a parser for the grammar? Slide 25: Avoid left recursion Slide 26: Parser for evaluating an arithmetic exp. Slide 27: Method to evaluate E Slide 28: Method to evaluate T Slide 29: Method to evaluate F Slide 30: References