Re: lpeg could infer the validity of this grammar.

On Sun, Dec 14, 2014 at 10:56 PM, Sean Conner <sean@conman.org> wrote:

LPeg is a Lua implementation of Parsing Expresson Grammars, which are
*NOT* (I repeat, *NOT*) the same as LR() or LL() parsers. There's a bit
more information about this on the Wikipedia:

http://en.wikipedia.org/wiki/Parsing_expression_grammar#Indirect_left_recursion

-spc

Absolutely correct, now, let's focus.

The lpeg engine has to detect potential left recursion, and reject it.

How does it do this?

It looks at a call to "patt", and sees whether another call to "patt" can be reached without consuming any input. We check the rules, one at a time, to assure that the second "patt" call either consumes or fails before it reaches a third.

The only type of capture which can modify this *logic* in a way that *still prevents infinite loops* is #patt, and only under this deterministic circumstance: If we have a pattern 'token', a looping pattern "expr", and a calling pattern "factor", then if factor looks like "factor = #token * expr" and expr looks like "expr = token + factor", we're okay.

Specifically, any #patt encountered before a potential left-recursion should be followed to see if a later call to `patt` is encountered. This must happen before the cursor moves, and before the recursive call to the "factor" type rule.

Think of #patt as a promise to the grammar compiler that 'patt' will be encountered. The compiler may statically confirm that this happens. Currently, it treats #patt as any other pattern that doesn't consume input, but in fact, it adds a new constraint which may be propagated.

One more time: I am making a logical claim about an algorithm. I would like to see demonstration code, and I'll tell you if the algorithm would say "cannot loop infinitely" or "might loop infinitely". I am especially interested in grammars for which these categories cannot be assigned: I haven't proven that it's impossible, because I don't have the time, but I suspect it is.