"""
 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)