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 in PYTHON!

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.

Explanation / Answer

NUM = r'(?Pd+)' PLUS = r'(?P+)' MINUS = r'(?P-)' TIMES = r'(?P*)' DIVIDE = r'(?P/)' LPAREN = r'(?P()' RPAREN = r'(?P))' WS = r'(?Ps+)' master_pattern = re.compile('|'.join((NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS))) Token = collections.namedtuple('Token', ['type', 'value']) def generate_tokens(pattern, text): scanner = pattern.scanner(text) for m in iter(scanner.match, None): token = Token(m.lastgroup, m.group()) if token.type != 'WS': yield token class ExpressionEvaluator: ''' Implementation of a recursive descent parser. Each method implement a single grammar rule. It walks from left to right over grammar rule. It either consume the rule a generate a syntax error Use the ._accept() method to test and accept look ahead token. Use the ._expect() method to exactly match and discard the next token on the input. or raise a SyntaxError if it doesn't match ''' def parse(self, text): self.tokens = generate_tokens(master_pattern, text) self.current_token = None self.next_token = None self._advance() # expr is the top level grammar. So we invoke that first. # it will invoke other function to consume tokens according to grammar rule. return self.expr() def _advance(self): self.current_token, self.next_token = self.next_token, next(self.tokens, None) def _accept(self, token_type): # if there is next token and token type matches if self.next_token and self.next_token.type == token_type: self._advance() return True else: return False def _expect(self, token_type): if not self._accept(token_type): raise SyntaxError('Expected ' + token_type) def expr(self): ''' expression ::= term { ( +|-) term } * ''' # it first expect a term according to grammar rule expr_value = self.term() # then if it's either + or -, we try to consume the right side # # If it's not + or -, then it is treated as no right side while self._accept('PLUS') or self._accept('MINUS'): # get the operation, + or - op = self.current_token.type right = self.term() if op == 'PLUS': expr_value += right elif op == 'MINUS': expr_value -= right else: raise SyntaxError('Should not arrive here ' + op) return expr_value def term(self): ''' term ::= factor { ('*'|'/') factor } * ''' # it first expect a factor term_value = self.factor() # then if it's either * or /, we try to consume the right side # # If it's not + or -, then it is treated as no right side while self._accept('TIMES') or self._accept('DIVIDE'): op = self.current_token.type if op == 'TIMES': term_value *= self.factor() elif op == 'DIVIDE': term_value /= self.factor() else: raise SyntaxError('Should not arrive here ' + op) return term_value def factor(self): ''' factor ::= NUM | (expr) ''' # it can be a number if self._accept('NUM'): return int(self.current_token.value) # or (expr) elif self._accept('LPAREN'): # we consumed ( in previous _accept # # then we try to evaluate the expr, and store the value expr_value = self.expr() # then it should be ), otherwise raise an exception self._expect('RPAREN') # return the previous saved value return expr_value else: raise SyntaxError('Expect NUMBER or LPAREN') e = ExpressionEvaluator() print('parse 2'.ljust(just_len), e.parse('2')) print('parse 2 + 3'.ljust(just_len), e.parse('2 + 3')) print('parse 2 + 3 * 4'.ljust(just_len), e.parse('2 + 3 * 4')) print('parse (2 + 3) * 4'.ljust(just_len), e.parse('(2 + 3) * 4'))

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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