They do indeed - thanks for the reply. I'll add his papers to my reading list.
Okhotin has a parser generator on his homepage: http://users.utu.fi/aleokh. I haven't looked at it, though, and it seems to have very little documentation. Cheers, Colin 2009/12/28 Robin Lee Powell <rlpow...@digitalkingdom.org>: > 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 > _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
