Re: Match-time captures in lpeg

[Roberto Ierusalimschy <roberto@...>]

> However, I'm still a little unclear on the reasoning behind match-time
> captures. There is only one example (Lua long strings) in the
> documentation, and I've not found many others on the web. The code
> required to implement match-time captures is non-trivial, so I have to
> assume that it was worth the effort to implement, but I'm not entirely
> sure why.
> 
> It seems to me that the point of match-time captures is to allow
> matching of constructions which would not otherwise be expressible
> with a "pure" PEG. Is that fair? If so, then (1) why is this
> particular form of non-pure construct more useful than any other, and

This particular form of non-pure construct is quite generic. I would
say that it is the "most generic", as by calling a function the function
can do whatever it wants. So it is more useful in the sense that all
others (or most others, probably) can be written on top of it.


> (b) isn't this the same sort of compromise that led from regular
> expressions to the non-regular languages that we have today under that
> name? If it's not the case, then what is the reason for having
> match-time captures?

It is a compromisse, but not of the sort that happened with regular
expressions. Match-time captures is fairly generic, but it does
not change the basic interface between patterns (ordered choice +
restricted backtracking). For other patterns around it, it behaves
like any other pattern.


> Can anyone help me with a really strong motivating example of why Cmt
> is important enough to have earned its place as the one exceptional
> case in lpeg?

The motivation for match-time captures is "the extension to avoid
all other extensions". (For instance, it emcompasses back-references,
a common feature in pattern-matching tools.)


> (On a related note, are there any papers available on the theory of
> captures in PEGs? I found Roberto's papers on the implementation of
> lpeg fascinating to read, but they omit any serious discussion of
> captures. I'd love to have a similar reference which addressed the
> area of captures, from both a theoretical and an implementation point
> of view).

Not yet. I plan to write something...

-- Roberto