> And it gets more complex when there's a bunch of state that requires you to save the stack frame in your explicit stack.
You are incorrect about tail recursion (look at continuation-passing style; it transforms any program to tail recursive form) but you are getting at the core of the issue here. The issue is either:
* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.
* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.
In other words, you can shift memory usage from the stack to the heap, but if a client can give you an unbounded amount of memory consuming work you are screwed either way. Ultimately the problem has nothing to do with recursion.
CPS transforms all programs into tail calls, not tail recursive. It buys you TCE in trivially tail recursive functions but does not magically transform something that needs to preserve state across recursion into something that is stateless.
But you're right, that's what I'm getting at. Recursion is an inherent semantic and whether you make the stack explicit or implicit doesn't get rid of memory allocation problems. I said in another comment that stack allocation is still dynamic memory management, it's just something many people take for granted.
You are incorrect about tail recursion (look at continuation-passing style; it transforms any program to tail recursive form) but you are getting at the core of the issue here. The issue is either:
* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.
* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.
In other words, you can shift memory usage from the stack to the heap, but if a client can give you an unbounded amount of memory consuming work you are screwed either way. Ultimately the problem has nothing to do with recursion.