On Sun, Dec 27, 2009 at 10:44:00PM -0800, Adam Megacz wrote: > > 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.
Huh; Boolean Grammars look kinda neat; any actual compiler generators for them? -Robin -- They say: "The first AIs will be built by the military as weapons." And I'm thinking: "Does it even occur to you to try for something other than the default outcome?" See http://shrunklink.com/cdiz http://www.digitalkingdom.org/~rlpowell/ *** http://www.lojban.org/ _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
