Is it possible to write JSON parser without using recursion ?

Question

Is it possible to write JSON parser without using recursion ? If it is, what approach would you suggest ?

Answer 1

Please someone correct me if I wrong, but isn't it possible to reproduce any recursive code with an equivalent iterative implementation?

This question describes this quite nicely: http://stackoverflow.com/questions/616416/is-it-possible-to-remove-recursion-from-this-function

Answer 2

I agree with James - any recursive code can theoretically be implemented using an iterative approach. The stack method described on the referred link is a valid option. The alternative is that you can hard-code to n depth, with the obvious risk of then being limited to said depth.

Without knowing more about the environment and constraints under which you are trying to run your JSON handling code, it's difficult to say which approach is the best fit. Some things to consider:

• Recursive code is usually simpler to follow if you can manage (and compatible with 99% of examples in almost any language out there for processing JSON)
• Iterative code using fixed depth can be "more efficient" insofar as it doesn't require as much use of the stack, but doesn't scale well to n-depth scenarios
• Stack based code can handle n-depth scenarios, but may not be as intuitive to other programmers

Also, it is possible to linear-ize a tree structure (which the object graph of a JSON is implicitly, assuming array-only can have a virtual root of "array"). This allows a flat-stream processing approach. If you go a step further and inject artificial tokens such as DOWN and UP it can be highly legible. This is something which comes up in compiler design and language analysis, but maybe helpful as a concept here.