Your task is to implement a recursive descent parser to recognize and evaluate s

Question

Your task is to implement a recursive descent parser to recognize and evaluate simple expressions.

You will start with the program pluto1.py and extend it to a Pluto 2.0 version that will include support for boolean expressions and comparison operators.

Pluto 2.0 will be based on the following grammar:

<command> -> <bool_expr>

<bool_expr> -> <bool_term> {OR <bool_term>}

<bool_term> -> <not_factor> {AND <not_factor>}

<not_factor> -> {NOT} <bool_factor>

<bool_factor> -> BOOL | LPAREN <bool_expr> RPAREN | <comparison>

<comparison> -> <arith_expr> [COMP_OP <arith_expr>]

<arith_expr> -> <term> {ADD_OP <term>}

<term> -> <factor> {MULT_OP <factor>}

<factor>-> LPAREN <arith_expr> RPAREN | FLOAT | INT

You will also have to define and accept tokens to represent the boolean values 'True' and 'False', the boolean operators 'and', 'or' and 'not' and the comparison operators '<', '>', '<=', '>=', '==', '!=':

BOOL: 'True' or 'False'

AND: 'and'

OR: 'or'

NOT: 'not'

COMP_OP: '<', '>', '<=', '>=', '==', '!='

Here are some test cases. More tests are provided in the grading rubric. Please feel free to add your own.

Pluto 2.0>>>8.5 > 6 and 8 + 3 == 11 and 72 <=100 and 5 != 2+6 and 100 >= 20 or 4 < 2

True

Pluto 2.0>>>not not not True

False

Pluto 2.0>>>9 * 4 + 4 > 17

True

Pluto 2.0>>>not(8/2 > 3.14) or 7 < 10 and 10 < 1

False

Pluto 2.0>>> 8 * 2.0 == 16

True

Pluto 2.0>>>7 + 6 * 2 != 15

True

Pluto 2.0>>>8 + 9 != > 10
Parser error
Expected: NUMBER
Got: >
line 1 position 9

Pluto 2.0>>>True or True and False

True

Pluto 2.0>>>(True or True) and False

False

Pluto 2.0>>>not True or True

True

Pluto 2.0>>>not (True or True)

False

HINTS:

The operator module includes the functions corresponding to the comparison operators: lt, gt, eq, ne, le, ge

If we add the import statement:

from operator import lt, gt, eq, ne, le, ge

then instead of:

result = a < b

we can write:

result = lt(a, b)

Make sure you add these comparison operators and their corresponding functions to the SUPPORTED_OPERATORS dictionary.

Make sure you always call match to advance to the next token. If the parser is generating an error that does not make sense, it is very likely that there is a missing call to match.

pluto1.py

Homework 2 Grading Rubric Ratings Pts Criteria The additional tokens are defined correctly and recognized by the Full No Marks Marks 5.0 pts Scanner 5.0 pts 0.0 pts view longer description Boolean expressions are evaluated correctly with the precedence Full No Marks Marks 4.0 pts described in the grammar 4.0 pts 0.0 pts view longer description Full No Comparisons return the correct result Marks Marks 6.0 pts view longer description 6.0 pts 0.0 pts Full No The not operator is implemented correctly Marks Marks 2.0 pts view longer description 2.0 pts 0.0 pts Full No Error handling Marks Marks 4.0 pts view longer description 4.0 pts 0.0 pts Total Points: 21.0

Explanation / Answer

static ExpNode expressionTree() throws ParseError scan associate degree expression from the present line of input and
// come associate degree expression tree representing the expression.
TextIO.skipBlanks();
mathematician negative; // True if there's a number one sign.
negative = false;
if (TextIO.peek() == '-')
ExpNode exp; // The expression tree for the expression.
exp = termTree(); // begin with a tree for 1st term.
if (negative) single minus operator to the term we've
// simply scan.
exp = new UnaryMinusNode(exp);
}
TextIO.skipBlanks();
whereas ( TextIO.peek() == '+' || TextIO.peek() == '-' ) {
// scan ensuing term and mix it with the
// previous terms into a much bigger expression tree.
char op = TextIO.getAnyChar();
ExpNode nextTerm = termTree();
// produce a tree that applies the binary operator
// to the previous tree and therefore the term we have a tendency to simply scan.
exp = new BinOpNode(op, exp, nextTerm);
TextIO.skipBlanks();
}
come exp;
} // finish expressionTree()

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.