On Thu, Mar 19, 2009 at 01:28:47PM +0000, Tim Goodwin wrote: > But I don't think the language x ^ n is expressible in a PEG.
*blink* text <- "A"* Perhaps I'm missing something about what you mean by "the language x ^ n"? > Incidentally, Wikipedia says that "parsers that use recursive > descent with backup may require exponential time." Can this really > be true?) It seems intuitively the case to me: if the parser matches all of the input but the last symbol, has to backtrack all the way to the root, tries something else and matches all of the input but the last symbol, has to backtrack to the root to try something else, etc. -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?" -- http://shorl.com/tydruhedufogre 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
