3 ms·
He suggests pratt parsing as a production parser which, while unbelievably elegant, is recursive. Correctly recovering from a stack overflow (without leaking me
by zamalek 6y ago
He suggests pratt parsing as a production parser which, while unbelievably elegant, is recursive. Correctly recovering from a stack overflow (without leaking memory or resources) is, at best, a very hard problem worth researching in academia. Recursion is generally not production code, its usefulness does not extend much further than confusing university students.
That's the hidden benefit of parsers that use DFAs: they generally don't use recursion. They will parse something until you run out of memory, not stack space (which is at least 3 orders of magnitude smaller than the heap).
- ghusbands 6y agoIt's trivial to replace the stack usage with a data structure. I've written a number of extended-Pratt parsers that don't use the stack. Also, a significant number of successful parsers have used recursion. As long as you successfully handle stack overflow and only hit it on pathological inputs, it works reasonably well.
- zamalek 6y ago> It's trivial to replace the stack usage with a data structure. Interesting. Do you have any examples of that, reading the article actually had me thinking how that would be achieved.
- flashmozzg 6y agoYou could trivially (or rather, mechanically) emulate HW bounded stack with a heap-based stack collection (like std::stack).