You could even implement this with a loop instead of a recursive call, to avoid running out of stack. Please note that memorization is a simple trick to solve

You could even implement this with a loop instead of a recursive call, to avoid running out of stack. Please note that memorization is a simple trick to solve a lot of parsing problems. I developed an intepretting parser, that basically does back-tracking, which is sped-up with memorization. Because the core interpretter is relatively small (fits in primary cache), it performs quite well. You simply give it a very natural looking grammar, with some annotations, and it builds you an abstract parse tree. I also implemented an unparser, which can be used to produce nicely formatted output for each abstract parse tree (just using the same grammar, with some annotations about where to insert line breaks and indentation). For more details see https://github.com/FransFaase/IParse https://github.com/FransFaase/IParse