Re: Matching a fixed number of repetitions in LPeG

[Roberto Ierusalimschy <roberto@...>]

> 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