Maximum Recursion exceeded

Question

I have an error, that stated:

    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
  File "derpAgain.py", line 14, in parse
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
  File "derpAgain.py", line 13, in parse
    if tokens[0] == "+":
RuntimeError: maximum recursion depth exceeded in comparison

I have no idea why I got that error. I double checked, see nothing wrong with it.

from derp_node import *

def parse(tokens, i = 0):
    """parse: tuple(String) * int -> (Node, int)
    From an infix stream of tokens, and the current index into the
    token stream, construct and return the tree, as a collection of Nodes, 
    that represent the expression.

    NOTE:  YOU ARE NOT ALLOWED TO MUTATE 'tokens' (e.g. pop())!!!  YOU
        MUST USE 'i' TO GET THE CURRENT TOKEN OUT OF 'tokens'
    """
    #t = tokens.pop(0)
    if tokens[0] == "+":
        return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "-":
        return mkSubstractNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "*":
        return mkMultiplyNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "//":
        return mkDivideNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif (tokens.pop(0).isdigit()):
        return mkLiteralNode(int(tokens.pop(0)))
    else:
        return mkVariableNode(tokens.pop(0))

def infix(node):
    """infix: Node -> String | TypeError
    Perform an inorder traversal of the node and return a string that
    represents the infix expression."""
    if isinstance(node, MultiplyNode):
        return "(" + infix(node.left) + " * " + infix(node.right) + ")"
    elif isinstance(node, DivideNode):
        return "(" + infix(node.left) + " // " + infix(node.right) + ")"
    elif isinstance(node, AddNode):
        return "(" + infix(node.left) + " + " + infix(node.right) + ")"
    elif isinstance(node, SubtractNode):
        return "(" + infix(node.left) + " - " + infix(node.right) + ")"
    elif isinstance(node, LiteralNode):
        return str(node.val)
    else:
        return node.name

def evaluate(node, symTbl):
    """evaluate: Node * dict(key=String, value=int) -> int | TypeError
    Given the expression at the node, return the integer result of evaluating
    the node.
    Precondition: all variable names must exist in symTbl"""
    if isinstance(node, MultiplyNode):
        return evaluate(node.left, symTbl) * evaluate(node.right, symTbl)
    elif isinstance(node, DivideNode):
        return evaluate(node.left, symTbl) // evaluate(node.right, symTbl)
    elif isinstance(node, AddNode):
        return evaluate(node.left, symTbl) + evaluate(node.right, symTbl)
    elif isinstance(node, SubtractNode):
        return evaluate(node.left, symTbl) - evaluate(node.right, symTbl)
    elif isinstance(node, VariableNode):
        for var in symTbl:
            if var == node.name:
                return symTbl[var]
    else:
        return node.val

def main():
    """main: None -> None
    The main program prompts for the symbol table file, and a prefix
    expression.  It produces the infix expression, and the integer result of
    evaluating the expression"""

    print("Hello Herp, welcome to Derp v1.0 :)")

    inFile = input("Herp, enter symbol table file: ")

    # STUDENT: CONSTRUCT AND DISPLAY THE SYMBOL TABLE HERE
    fileOpen = open(inFile)
    symTbl = {}

    for line in fileOpen:
        lineStrip = line.split()
        symTbl[lineStrip[0]] = int(lineStrip[1])

    for var in sorted(symTbl):
        print("Name: " + var + " => " + str(symTbl[var]))

    print("Herp, enter prefix expressions, e.g.: + 10 20 (RETURN to quit)...")

    # input loop prompts for prefix expressions and produces infix version
    # along with its evaluation
    while True:
        prefixExp = input("derp> ")
        if prefixExp == "":
            break

        prefix = prefixExp.split()
        root = parse(prefix)
        print("Derping the infix expression: " + infix(root))

        print("Derping the evaluation: " + str(evaluate(root, symTbl)))

    print("Goodbye Herp :(")

if __name__ == "__main__":
    main()

When I opened up the program. It will show this output:

Hello Herp, welcome to Derp v1.0 :)
Herp, enter symbol table file: vars.txt
Name: x => 10
Name: y => 20
Name: z => 30
Herp, enter prefix expressions, e.g.: + 10 20 (RETURN to quit)...
derp> - 10 20
Derping the infix expression: 10
Derping the evaluation: None
derp> + 10 * x y
Then the error has started...

Vars.txt:

x 10
y 20
z 30

Sidenote: if you guys are curious what it is in derp_node.py, I am not going to post it here, however, I posted it on pastebin so this page don't look huge. http://pastebin.com/MXuc8Shc Any help would be great! Thank you. Hope I provided enough information, so you guys have an idea, what I am doing.

Answer 1

If you get to a token '+' it starts an infinite loop:

if tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif (tokens.pop(0).isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))
else:
    return mkVariableNode(tokens.pop(0))

you only check the '+' token and only pop if token is not '+'. I hope that helps

I would use:

aux = tokens.pop(0)
if aux == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "-":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "*":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "/":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif (aux.isdigit()):
    return mkLiteralNode(int(aux))
else:
    return mkVariableNode(aux)

Answer 2

Let's take a look at what happens when you call parse(tokens, i) and tokens[0] == '+'. The body of parse will try to execute:

return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))

Executing this statement requires evaluating parse(tokens, i+1), and as tokens[0] is still '+' within the recursive call, you'll get another call to parse, and another, and this will never end. I think what you want to do is test tokens[i] == '+', not tokens[0], or maybe change parse(tokens, i+1) to parse(tokens[1:], i+1) (Why do you even have i when you're not using it?)

Answer 3

You keep passing the same reference to tokens.

tokens[0] will ALWAYS be '+' if you don't increment which character you're referring to, meaning that the recursive calls to parse() will continue forever.

Also, why do you have 4 if/elif branches that all check/call the exact same thing?

Also, the .pop() method actually changes the underlying list, so your if tokens.pop().isdigit() is actually removing the last element in tokens. This might be want you want to do in the first if as well.

Answer 4

You still have some calls to pop, and calling pop in your conditional is especially bad, since you mutate the list when you are not even sure if the condition applies or not:

elif (tokens.pop(0).isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))

should be:

elif (tokens[0].isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))