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
esulting 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
e 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 a
itrary 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
esulting number.
PowerPoint Presentation
Applications of Queues
and Stacks
Sridhar Alaga
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
Cu
ent token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 4
Input
+4*5/(2+1)^2
Output (queue)
3
Stack
Cu
ent token is operato
stack is empty
push to stack
Shunting Yard: Example
CS 6301 IDSA 5
Input
4*5/(2+1)^2
Output (queue)
3
+
Stack
Cu
ent token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 6
Input
*5/(2+1)^2
Output (queue)
34
+
Stack
Cu
ent token is operato
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
Cu
ent token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 8
Input
(2+1)^2
Output (queue)
345
*
+
Stack
Cu
ent token is operato
top of stack has equal precedence op
ut left associative
pop to output queue
Shunting Yard: Example
CS 6301 IDSA 9
Input
(2+1)^2
Output (queue)
345*
+
Stack
Cu
ent token is operato
top of stack has lower precedence op
push token
Shunting Yard: Example
CS 6301 IDSA 10
Input
(2+1)^2
Output (queue)
345*
+
Stack
Cu
ent token is ‘(‘
push token
Shunting Yard: Example
CS 6301 IDSA 11
Input
2+1)^2
Output (queue)
345*
(
+
Stack
Cu
ent token is operand
add to output queue
Shunting Yard: Example
CS 6301 IDSA 12
Input
+1)^2
Output (queue)
345*2
(
+
Stack
Cu
ent token is operato
top of stack is ‘(‘
push token
Shunting Yard: Example
CS 6301 IDSA 13
Input
1)^2
Output (queue)
345*2
+
(
+
Stack
Cu
ent token is operand
add it to output queue
Shunting Yard: Example
CS 6301 IDSA 14
Input
)^2
Output (queue)
345*21
+
(
+
Stack
Cu
ent 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
Cu
ent token is operato
top of stack has lower precedence op
push token
Shunting Yard: Example
CS 6301 IDSA 16
Input
2
Output (queue)
345*21+
^
+
Stack
Cu
ent 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 operato
while (stack top has higher precedence o
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 ‘(‘, e
o
}
end while
pop the remaining operators from stack to output
Recursive Descent Parse
• 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
Parse
CS 6301 IDSA 21
Tokenizer Parse
Back end of
compile
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
ule (rhs) its method is invoked
Terminal on the rhs leads to
consuming/evaluating the token
Is there a problem with the left
ecursion 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
}
eturn 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
}
eturn 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);
}
eturn 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_parse
CS 6301 IDSA 30
https:
en.wikipedia.org/wiki/Shunting-yard_algorithm
https:
en.wikipedia.org/wiki/Recursive_descent_parse
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 Parse
Slide 21: Parse
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