Re: lpeg could infer the validity of this grammar.

[Sean Conner <sean@...>]

It was thus said that the Great Sam Putman once stated:
> On Sun, Dec 14, 2014 at 1:50 PM, Sam Putman <atmanistan@gmail.com> wrote:
> > On Sun, Dec 14, 2014 at 12:56 PM, Dirk Laurie <dirk.laurie@gmail.com>
> > wrote:
> >> 2014-12-14 21:39 GMT+02:00 Sam Putman <atmanistan@gmail.com>:
> >>
> >> > expr = token + ( V"group" + V"factor" + V"term")
> >> -- semicolon needed here
> >> > group = P"(" * V"expr"^0 * P")";
> >> > factor = #token * V"expr" * (P"*" + P"/") * V"expr";
> >>
> >> > This program fails with "rule 'expr' may be left recursive".
> >>
> >> If `expr` is not `token` or `group`, it tries `factor`.
> >> The rule for `factor` invokes V"expr" before any
> >> input has been consumed.
> >
> > I do understand the cause for the failure to infer. The grammar is valid,
> > but not valid lpeg, as lpeg stands.
>
> To elaborate, I understand that #token returns the empty string, and it
> isn't always safe to call "expr" within "expr". When hand-writing recursive
> descent, it's nice when possible to do a few tokens of lookahead to ensure
> completion, then recur. This grammar attempts to mimic that idiom.

  The rules I use for this type of thing look like:

re = require "re" -- it's still part of LPeg.
		  -- and I find it easier to follow the grammar

parser = re.compile [[
        expr    <- term   (termop   term)*
        term    <- factor (factorop factor)*
        factor  <- number / open expr close

        space           <- %s*
        number          <- space {'-'^-1 [0-9]^+1} space
        termop          <- space {[+-]} space
        factorop        <- space {[*/]} space
        open            <- space '('    space
        close           <- space ')'    space

]]

  It should be straightforward to translate this to LPeg (seeing how re can
do that).

  -spc