very-simple-parser.py

tokenized_string = "2 + 3 * 4".split()

# parsing arithmetic expressions with + and *
# A parser returns (parsed_thing, new_index) on success.

def fail(): raise Exception("failed to parse")

def is_num(x):
    try: int(x)
    except ValueError: return False
    else: return True

def parse_expr(tokens, i):
    print("parse_expr(%s)" % tokens[i:])
    if i >= len(tokens): fail()

    if is_num(tokens[i]):
        value = int(tokens[i])
        new_i = i+1

    if tokens[i] == '(':
        value, new_i = parse_expr(tokens, i+1)
        if tokens[new_i] != ')': fail()
        new_i += 1

    rest = parse_infix_expr(tokens, new_i, value)
    if rest is None: return value, new_i
    return rest

# returns (parsed_thing, new_index) on success
# returns None on failure
def parse_infix_expr(tokens, i, left_arg):
    print("parse_infix_expr(%s, %s)" % (tokens[i:], left_arg))
    if i >= len(tokens): return None

    if tokens[i] == '+':
        right_arg, new_i = parse_expr(tokens, i+1)
        return left_arg + right_arg, new_i

    if tokens[i] == '*':
        if i+1 >= len(tokens): fail()

        if is_num(tokens[i+1]):
            right_arg = int(tokens[i+1])
            new_i = i+2
        elif tokens[i+1] == '(':
            right_arg, new_i = parse_expr(tokens,i+2)
            if tokens[new_i] != ')': fail()
            new_i += 1
        else: fail()

        value = left_arg * right_arg
        print('multiplied: %s * %s = %s' % (left_arg, right_arg, value))
        rest = parse_infix_expr(tokens, new_i, value)
        if rest is None: return value, new_i
        return rest

    return None

print("loaded parser.py")