A recursive descent parser to recognize and evaluate simple expressions

general article writing

Description

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 a match to advance to the next token.  If the parser is generating an

the error that does not make sense, it is very likely that there is a missing call to match.


Related Questions in general article writing category