Re: yet another pattern-matching library for Lua

[roberto@... (Roberto Ierusalimschy)]

> However, this seems like a bug:
> 
> >print( lpeg.match("wha&t", (GoodName) * lpeg.P(-1)) )
> false
> 
> >print( lpeg.match("wha&t", (BadName) * lpeg.P(-1)) )
> 6
> 
> >print( lpeg.match("wha&t", (GoodName + BadName) * lpeg.P(-1)) )
> false
> 
> ...I'm fairly new to the concept of parsing grammars, so I may have
> just misunderstood something, but shouldn't the third command get the
> same response as the second one, regardless of what the patterns are?

No. A (or "the") key concept in parsing grammars (that came from TDPLs)
is that is does only "limited backtracking" (or "local" backtracking).
That means that, once a choice succeeds, the machine does not backtrack
to change it if something ahead fails. In your example, I imagine that
"GoodName" matches some prefix of "wha&t" (probably the "wha" part).
So, the machine chooses "GoodName" and goes on. When -1 fails, it does
not backtrack for a previous choice, so the whole match fails.

On the other hand, if you write

>print( lpeg.match("wha&t", GoodName * lpeg.P(-1) + BadName * lpeg.P(-1)) )

the match will succeed. When the option "GoodName * -1" fails, the
machine does a local backtracking for the other option. (It is "local"
because it is an option for the same thing that fails, not a previous
option for something that already succeeded.)

The limited backtracking is not an arbitrary restriction; it is a key
component of the idea of PEGs.

-- Roberto