5 ms·

I must have missed this class. How does one convert a recursive descent parser into an iterative one?

• pmg101 1y ago
  https://news.ycombinator.com/item?id=44837949 https://news.ycombinator.com/item?id=44837949
• jandrese 1y ago
  By making your own stack and using loops.
• kylec 1y ago
  You can do it by managing your own stack, but I would argue that doing so makes the algorithm LESS easy to scan and has its own sets of problems.
• electroly 1y ago
  Same way as any other algorithm: with an explicit heap-allocated stack. I have a naive parser where I built operator precedence into the grammar as nested productions instead of using an algorithm like shunting yard. An input of ((((((1)))))) blew the stack. Converted it to an explicit stack and it was fine; deep for the call stack was not deep for my own heap-allocated stack. Nasty code, though--I think this serves as one of the counterexamples to the idea that the recursive code gets simpler when turning it into iteration. The original OP was talking more specifically about tail recursion, which a recursive descent parser won't be.
  • bjoli 1y ago
    There are many languages out there that can grow the stack these days. If you have a language that can do tail recursion, it is really a very neat complement. In lisps it means being able to write a list building function in a direct consing way, and still being faster than the TCP-way.
• Jtsummers 1y ago
  Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner. In tail recursive algorithms, there is no stack, it's just a straight loop. def foo(state, acc): # if acc is needed if base-condition(state): return acc return foo(next(state), f(state, acc)) Is simply: def foo(state): acc = initial while not base-condition(state): acc = f(state, acc) state = next(state) return acc If it's not tail recursive you introduce a stack, for instance a DFS on a binary tree: def search(node, val): if node is None: return False # empty tree, only need this check once stack = [node] while stack: n = stack.pop() if n.val == val: return True if n.right: stack.push(n.right) if n.left: stack.push(n.left) return False Note the insertion order is reversed from the recursive calls in a typical DFS. We want left to be searched first and then its children and then we "recur" back to right and deal with its children, so we need to push right into the stack first and then left. When you have multiple mutually recursive functions (as is likely the case in a recursive descent parser) then things become more complicated, but it's still feasible.
  • LegionMammal978 1y ago
    Sometimes the messy translation into an explicit stack and dispatch loop is necessary, if you want to pause the calculation, serialize the current state, and reconstitute it later. (E.g., if you want to add disk-saved checkpoints, a frequent hassle in some of my projects.) Coroutines can get you the equivalent of pausing and resuming for a recursive routine, but I'm not aware of any language that lets you serialize the call stack.
    • Jtsummers 1y ago
      > I'm not aware of any language that lets you serialize a whole call stack. That's basically what continuations provide. Scheme, SML, and others provide them.
      • LegionMammal978 1y ago
        Continuations allow an inactive call stack to sit around in memory. But do any of those languages let you save a continuation to a file and resume it in a different execution of the program, without massive contortions to the code? That's what I mean by serialization.