""" rec_des_in_class.py the task : implement a recursive descent parser for this grammar in python expression ::= "(" expression operator expression ")" | number operator ::= "+" | "-" | "*" | "/" number ::= digit digit* digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" should turn this "(1+2)" into nodes : [parent, child1, child2, child3] ['expression', '(', ['expression', ['number', ['digit', '1']]], ['operator', '+'], ['expression', ['number', ['digit', '2']]], ')' ] """ class Lexer: def __init__(self, code): self.code = code self.index = 0 def pop(self): """ return next token, and move to next """ token = self.code[self.index] self.index += 1 return token def peek(self): """ return next token, don't change which one is next """ return self.code[self.index] # --- lexer test --- lex = Lexer("(1+2)") assert lex.peek() == '(', "OOPS - didn't get peek (" assert lex.peek() == '(', "OOPS - didn't get peek (" assert lex.pop() == '(', "OOPS - didn't get pop (" assert lex.pop() == '1', "OOPS - didn't get pop (" # --- parser --- def check(token, correct): assert token == correct, "OOPS - parse failed" def expression(lex): if lex.peek() == "(": left = lex.pop(); exp1 = expression(lex) op = operator(lex) exp2 = expression(lex) right = lex.pop(); check(right, ")") return ["expression", left, exp1, op, exp2, right] else: return ["expression", number(lex)] op_tokens = ("+" , "-" , "*" , "/") digit_tokens = ("0" , "1" , "2" , "3" , "4" , "5" , "6" , "7" , "8" , "9") def operator(lex): op = lex.pop() assert op in op_tokens, "OOPS - didn't find expected op" return ["operator", op] def number(lex): result = ["number", digit(lex)] while lex.peek() in digit_tokens: result.append(digit(lex)) # modify return result def digit(lex): token = lex.pop() assert token in digit_tokens, "OOPS - didn't find digit" return ["digit", token] # -------------------------- code = "(1+2)" print("code is ", code) lexer = Lexer("(1+2)") tree = expression(lexer) print("tree is ", tree)