Colin Fleming <colin.mailingl...@gmail.com> writes: > So my idea would be to implement the parser using a Thompson-style NFA > instead of the normal recursive descent. > > For ordered choice all branches would be explored simultaneously. > > So parsing would then simply be a single forward scan over the input, > trading memory (and implementation complexity) for backtracking.
Sounds like using GLR to parse a boolean grammar: Okhotin, Alexander. __LR Parsing for Boolean Grammars.__ Developments in Language Theory 2005: 362-373. http://www.springerlink.com/content/pm0qjcv1xrch2pjm/ A parser for boolean grammars can parse any PEG (but the converse is not true) by encoding A/B as (~B & A)|B. I conjecture that it parses in linear time, but haven't gotten around to working out the proof in full detail. > One nice property is that it only consumes memory "on demand" - it > will only use memory when required to disambiguate. Yes, that is a very nice property of GLR parsers. - a _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
