Re: Matching a fixed number of repetitions in LPeG
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Matching a fixed number of repetitions in LPeG
- From: Roberto Ierusalimschy <roberto@...>
- Date: 2012年6月19日 17:02:05 -0300
> On Tue, Jun 19, 2012 at 8:21 PM, Patrick Donnelly <batrick@batbytes.com> wrote:
> > I think you're overthinking this (you shouldn't need match-time captures). Try:
> >
> > function power (patt, n)
> > local p = lpeg.P(true)
> > for i = 1, n do
> > p = p * patt
> > end
> > return p
> > end
>
> An LPEG pattern is a sequence of instructions for a special virtual
> machine. Your approach of doing powers results in much longer
> programs, whereas the match-time capture approach doesn't. For trivial
> patterns, the LPEG optimiser might be able to turn these longer
> programs into short ones, but program length will become an issue for
> high powers of non-trivial patterns.
I guess we can use grammars to avoid both those long programs and
match-time captures. The following code should do the trick. (Obs:
not hard tested; a better implementation could choose to use plain
repetitions for small n's.)
---------------------------------------------------------
local lpeg = require 'lpeg'
local function aux_power (n, t)
local name = "p" .. n
if n == 1 then
return name
else
local m = aux_power(math.floor(n/2), t)
m = lpeg.V(m)
t[name] = m * m
if n % 2 ~= 0 then
t[name] = lpeg.V("p1") * t[name]
end
end
return name
end
function power (p, n)
local a = {p1 = lpeg.P(p)}
a[1] = aux_power(n, a)
return lpeg.P(a)
end
print(power('x', 1000):match(string.rep('x', 100000)))
print(power(lpeg.R'09', 101):match(string.rep('123', 400)))
---------------------------------------------------------
-- Roberto