And it gets more complex when there's a bunch of state that requires you to save the stack frame in your explicit stack.
If the language runtime has growable stacks you're just making the code more complex.
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.
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.
Altough, technically my "solution" would work for making it tail calls anyways, by replacing the looping part with tail calls. But I digrees
