**** Your task is to implement a recursive descent parser to recognize and evalu

Question

****

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

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.

Pluto 1.0 code:

Explanation / Answer

def command(): """ ::= """ result = arith_expr() if not parse_error: # no parsing error if token: # if there are more tokens error('END OF COMMAND OR OPERATOR') else: print(result) def arith_expr(): """ ::= { ADD_OP } """ result = term() while token and token.type == 'ADD_OP': operation = SUPPORTED_OPERATORS[token.value] match() # match the operator operand = term() # evaluate the operand if not parse_error: result = operation(result, operand) return result def term(): """ ::= {MULT_OP } """ result = factor() while token and token.type == 'MULT_OP': operation = SUPPORTED_OPERATORS[token.value] match() # match the operator operand = factor() # evaluate the operand if not parse_error: result = operation(result, operand) return result def factor(): """ ::= LPAREN RPAREN | FLOAT | INT """ if token and token.type == 'LPAREN': match() result = arith_expr() if token and token.type == 'RPAREN': match() return result else: error(')') elif token and (token.type == 'FLOAT' or token.type == 'INT'): result = token.value match() return result else: error('NUMBER') def match(): """ Get the next token """ global token token = lexer.token() def error(expected): """ Print an error message when an unexpected token is encountered, sets a global parse_error variable. :param expected: (string) '(' or 'NUMBER' or or ')' or anything else... :return: None """ global parse_error if not parse_error: parse_error = True print('Parser error') print("Expected:", expected) if token: print('Got: ', token.value) print('line', token.lineno, 'position', token.lexpos) def main(): global token global lexer global parse_error # Build the lexer lexer = lex.lex() # Prompt for a command more_input = True while more_input: input_command = input("Pluto 1.0>>>") if input_command == 'q': more_input = False print('Bye for now') elif input_command: parse_error = False # Send the command to the lexer lexer.input(input_command) token = lexer.token() # Get the first token in a global variable command() if __name__ == '__main__': main()

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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