C++ Run-time Preempting Stack-Overflows

Question

I'm trying to write a library which can parse end user files to be used for adding some simple user generated content into a project and I want to try and make the library as flexible as possible. I use recursion for the tokenisation process of 'objects' which goes through a chain of four functions but I am conflicted with how to handle the potential situation of an end user going nested object happy. I know I can set a hard limit on how many times the program can recurse but I would like to make it as flexible as possible. Is there any way that I can calculate the (maximum - 1) number of times that this process can execute so that I can preempt a stack overflow error and return an error or something to be handled?

Answer 1

Is there any way that I can calculate the (maximum - 1) number of times that this [recursive] process can execute ...

No. It's not even guaranteed that each stack frame in the call chain is the same size.

Transforming a recursive implementation to an iterative one is fairly simple and really well-defined: you just

1. replace the implicit call stack (and function call operation) with an explicit state container, such as std::stack<State>
2. instead of a recursive call, you push the new call's State onto your stack, and continue the loop
3. instead of being called, the loop starts by popping the current State off the stack, and processes that, which may require pushing another new State on there if you would previously have made another recursive call

Alternatively, you can just split your current recursive descent parser into a tokenizer and LALR (or similar) parser, which are both iterative in the first place. You can generate these with Flex and Bison (Lex/Yacc), for example.