This looks really great! For casual parsing and data extraction in particular, having a parser generator which does not restrict its users to a particular non-c

This looks really great! For casual parsing and data extraction in particular, having a parser generator which does not restrict its users to a particular non-compositional subset of its input grammar (e.g. LL, LR, etc.) is a must, since it does not require the user to understand the particular parsing technique in order to use it. Visibly pushdown languages seem powerful enough to be able to express many practical data formats. Shameless plug: I saw that you have based the parse tree construction on Dube and Feeley's two-pass algorithm which in its second phase builds a parse tree from a "journal" generated by a DFA in the first recognition phase. This works well, but as you point out, it uses memory linear in the input string for the journal. While the parse tree must of course still be built and kept in memory, the size of the auxiliary journal can actually be limited to what is semantically required by the ambiguity of the input grammar - in many cases, the bound is O(1). We have written a couple of papers about such a streaming parsing algorithm which you might find interesting for inspiration: [1] Optimally Streaming Greedy Regular Expression Parsing. https://utr.dk/pubs/files/grathwohl2014-0-paper.pdf https://utr.dk/pubs/files/grathwohl2014-0-paper.pdf [2] Kleenex: Compiling Nondeterministic Transducers to Deterministic Streaming Transducers. https://utr.dk/pubs/files/grathwohl2016-0-paper.pdf https://utr.dk/pubs/files/grathwohl2016-0-paper.pdf We never got around to extending the technique to more powerful formalisms such as visibly pushdown languages, although I believe that should be possible.