lpeg code translate to lpeg re

Posted by Albert Chan on Sat 20 Jan 2018 08:12 PM — 65 posts, 223,241 views.

Albert Chan Sat 20 Jan 2018 08:12 PM #0

i enjoyed lpeg tutorial: http://www.gammon.com.au/lpeg
however, i am puzzled about the lpeg re examples

how to translate lpeg upto function example in lpeg re ?
what is the lpeg re equivalent to lpeg p1 - p2 ?

Albert Chan Sat 20 Jan 2018 10:18 PM #1

to make my lpeg re questions more concrete, I was unable to
translate lua pattern "(.*)and(.*)" using lpeg re:

local C, P = lpeg.C, lpeg.P

-- my attempt for lua pettern "(.+)and(.*)"
local lpeg_pat = C((P(1) - 'and')^1) * 'and' * C(P(1)^0)
local re_pat = re.compile "{ (. ! 'and')* . } 'and' {.*}"

-- lua pattern "(.*)and(.*)
lpeg_pat = C((P(1) - 'and')^0) 'and' * C(P(1)^0)

-- what is lpeg re equivalent code ?

Nick Gammon Australia Forum Administrator Sat 20 Jan 2018 10:32 PM #2

It looks like you have to reverse the order. This works:


require "re"
target = "foo and bar"
local re_pat = re.compile "{ (!'and' .)*} 'and' {.*}"
print (lpeg.match (re_pat, target))

Output:


foo   bar

The pattern is basically saying:


{       <-- start of capture
(       <-- start of group
!'and'  <-- assert not matching 'and' without consuming input
.       <-- consume one character
)       <-- end of group
*       <-- match zero or more of the preceding
}       <-- end of capture
'and'   <-- consume the 'and'
{.*}    <-- capture rest of input

Nick Gammon Australia Forum Administrator Sat 20 Jan 2018 10:39 PM #3

I don't see how to implement "upto" in re, since I can't see how to pass arguments to functions.

Albert Chan Sat 20 Jan 2018 11:24 PM #4

your solution of reversing the order is very nice !

you should consider put this trick to the tutorial,
to complement the lpeg upto function example.

with this insight, can i assert the following ?

P(1) - 'and' == -P('and') * 1 == re.compile "! 'and' ."

or, to generalize

P(1) - (P'and' + 'or' + 'not')
== -(P'and' + 'or' + 'not') * 1
== re.compile "!('and' / 'or' / 'not') ."

Nick Gammon Australia Forum Administrator Sat 20 Jan 2018 11:48 PM #5

Yes, I think you are right, although you still need to repeat that pattern. So 'upto' could be written:


function upto (what)
  return C((-P(what) * P(1))^1) * P(what)
end -- upto

Instead of:


function upto (what)
  return C((P(1) - P(what))^1) * P(what)
end -- upto

Those two versions also do capturing, which you can remove by deleting the 'C' character.

I'll try to add this to the LPEG web page explanation.

Albert Chan Sun 21 Jan 2018 12:31 AM #6

FYI, both versions of upto generate exactly the same parse tree code

Great thanks to Sean Conner, who actually recompile a debug lpeg
version to go thru the parse tree code. He also get your reversed
order answer (trial and error with the debug parse tree)

his response is in lua mailing list jan 20, 2018 5:54pm

Albert Chan Sun 21 Jan 2018 01:34 AM #7

Also noticed lpeg upto trick cannot translate lua pattern "(.*)and(.*)"

re.compile "{(! 'and' .)*} 'and' {.*}" correspond to lua pattern "(.-)and(.*)",
the non-greedy pattern.

your lpeg tutorial 2 examples return the same match only because
words are separated by spaces: %a+ is greedy, function upto is NOT.

:-(

Nick Gammon Australia Forum Administrator Sun 21 Jan 2018 01:39 AM #8

What are you expecting?


require "re"
target = "foo and bar"

print "====="

local re_pat = re.compile "{ (!'and' .)*} 'and' {.*}"
print (lpeg.match (re_pat, target))

print "---"

print (string.match (target, "(.*)and(.*)"))
print (string.match (target, "(.-)and(.*)"))

Output is:


=====
foo   bar
---
foo   bar
foo   bar

That looks the same to me. For what input do you expect a difference, and what do you expect that difference to be?

Nick Gammon Australia Forum Administrator Sun 21 Jan 2018 01:43 AM #9

Maybe here:


target = "foo and bar and whatever"

Output:


=====
foo   bar and whatever
---
foo and bar   whatever
foo   bar and whatever

So yes, it looks non-greedy.

Nick Gammon Australia Forum Administrator Sun 21 Jan 2018 03:10 AM #10

I worked it out with this grammar:


target = "foo and bar and whatever"

c = re.compile [[
   parse     <- {| {noDelim} lastDelim |}  -- look for all up to the last delimiter followed by the last part
   delim     <- 'and'                      -- our delimiter
   noDelim   <- (!lastDelim .)*            -- zero or more characters without the last delimiter
   lastDelim <- delim {(!delim .)*} !.     -- the delimiter without any more delimiters and then end of subject
]]

result = lpeg.match (c, target)

for k, v in ipairs (result) do
  print (k, v)
end -- for

Output:


1 foo and bar
2  whatever

Albert Chan Sun 21 Jan 2018 04:50 AM #11

i have a simpler and faster lpeg re (about 2x speed), but the
last 'and' is appended to front string

pat = re.compile "{g <- . g / 'and'} {.*}"

= pat:match("this and that and this and more")
this and that and this and
more

anyway to remove the last "and" ?

Nick Gammon Australia Forum Administrator Sun 21 Jan 2018 05:48 AM #12

By my measurements, yours is not 2x faster. In some cases it is slightly faster. Arguably, if it isn't providing the results you want, then the speed doesn't matter. You could always remove the trailing "and" with a string.sub, but that would take time. I made up a test bed:


require "re"
require "tprint"

c = re.compile [[
   parse     <- {| {noDelim} lastDelim |}  -- look for all up to the last delimiter followed by the last part
   delim     <- 'and'                      -- our delimiter
   noDelim   <- (!lastDelim .)*            -- zero or more characters without the last delimiter
   lastDelim <- delim {(!delim .)*} !.     -- the delimiter without any more delimiters and then end of subject
]]

pat = re.compile "{| {g <- . g / 'and'} {.*} |}"  -- Albert Chan pattern

function showResults (result, start, finish)
  if not result then
    print ("no match")
  else
    tprint (result)
  end -- if
  print (string.format ("Time taken = %0.3f us", (finish - start) * 1e6))
end -- showResults 

function test (which)

  print (string.rep ("=", 20))
  print ("Testing:", which)

  print (string.rep ("-", 10))
  print "Nick"

  start = utils.timer ()
  result = lpeg.match (c, which)
  finish = utils.timer ()

  showResults (result, start, finish)

  print (string.rep ("-", 10))
  print "Albert"

  start = utils.timer ()
  result = lpeg.match (pat, which)
  finish = utils.timer ()

  showResults (result, start, finish)

end -- test

tests = {
 "foo and bar and whatever",
 "foo and bar",
 "XandY",
 "foo",
 "Xand",
 "andY",
 "and",
 "",
}

for _, v in ipairs (tests) do
  test (v)
end -- for

You will notice that the very case you were interested in (multiple instances of the word "and") your expression is almost 4 times as slow.


====================
Testing: foo and bar and whatever
----------
Nick
1="foo and bar "
2=" whatever"
Time taken = 11.733 us
----------
Albert
1="foo and bar and"
2=" whatever"
Time taken = 43.302 us
====================
Testing: foo and bar
----------
Nick
1="foo "
2=" bar"
Time taken = 5.029 us
----------
Albert
1="foo and"
2=" bar"
Time taken = 4.749 us
====================
Testing: XandY
----------
Nick
1="X"
2="Y"
Time taken = 4.749 us
----------
Albert
1="Xand"
2="Y"
Time taken = 4.749 us
====================
Testing: foo
----------
Nick
no match
Time taken = 3.073 us
----------
Albert
no match
Time taken = 2.794 us
====================
Testing: Xand
----------
Nick
1="X"
2=""
Time taken = 4.470 us
----------
Albert
1="Xand"
2=""
Time taken = 5.867 us
====================
Testing: andY
----------
Nick
1=""
2="Y"
Time taken = 4.749 us
----------
Albert
1="and"
2="Y"
Time taken = 4.470 us
====================
Testing: and
----------
Nick
1=""
2=""
Time taken = 5.029 us
----------
Albert
1="and"
2=""
Time taken = 4.470 us
====================
Testing: 
----------
Nick
no match
Time taken = 3.073 us
----------
Albert
no match
Time taken = 3.073 us

I took the compile part out of the timing, because you should really only do that once, and the speed you are really interested in is execution speed (that is, match speed).

Having said all that, your pattern looks nice and elegant. :)

Albert Chan Sun 21 Jan 2018 06:11 AM #13

my mistake.
i was comparing my pattern vs yours
but mine does multiple returns, while yours was saved in table

i am new with lpeg ...
how to convert your re pattern to do multiple returns ?

Nick Gammon Australia Forum Administrator Sun 21 Jan 2018 06:29 AM #14

See my "parse" line above. You put the pattern inside these symbols:


{| pattern |}

Or to not do that, remove those symbols.

Albert Chan Sun 21 Jan 2018 07:02 AM #15

redoing your benchmark on my machine, my version is slightly faster.
I guess it depends on many factors, machine setups ...

i now have lpeg re pattern that return without the extra "and"

lpeg re pattern :


"{ g <- . g / &'and' } 'and' {.*}"

Albert Chan Sun 21 Jan 2018 01:37 PM #16

To summarize what I have learn so far, upto function have 2 versions:


local C, P, V = lpeg.C, lpeg.P, lpeg.V

function upto_first(what)            -- non-greedy version
  return C( (-P(what) * 1)^0 ) * P(what)
end

function upto_last(what)             -- greedy version
  return C {1 * V(1) + #P(what)} * P(what)
end

Albert Chan Sun 21 Jan 2018 05:26 PM #17

this is a response to reply #3: lpeg upto version in lpeg re:


function upto(what)    -- non-greedy match
  return string.format( [[ {(! %q .)*} %q ]], what, what)
end

pat = re.compile( upto('and') .. "{.*}" )


= pat:match("this and that and whatever")
this
that and whatever

Albert Chan Mon 22 Jan 2018 01:33 AM #18

discovered a way to combine reply #16 2 upto functions as one:


function upto(what, greedy)
    local t1, t2 = #P(what), 1 * V(1)
    if greedy then t1, t2 = t2, t1 end
    return C {t1 + t2} * P(what)
end

function all() return C(P(1)^0) end


text = 'this or that of whatever'

= (upto('and', false) * all()):match(text)    -- lua pattern "(.-)and(.*)
this
that and whatever

= (upto('and', true) * all()):match(text)     -- lua pattern "(.*)and(.*)
this and that
whatever

Albert Chan Mon 22 Jan 2018 04:00 PM #19

My previous upto have problem with long strings in greedy mode.

= upto('and', true):match( ('*and'):rep(50) )
backtrack stack overflow (current limit is 400)
...

Is this a lpeg bug ? only handle max string length of 199 ?
Above example only need 3 backtracks !

below is same upto function that avoid backtrack overflow:


function upto(what, greedy)
    what = P(what)
    local head = 1 - what
    if greedy then head = what * -(head^0 * -1) + head^1 end
    return C(head^0) * what
end

Nick Gammon Australia Forum Administrator Mon 22 Jan 2018 09:15 PM #20

See LPEG reference

Quote:

lpeg.setmaxstack (max)

Sets a limit for the size of the backtrack stack used by LPeg to track calls and choices. (The default limit is 400.) Most well-written patterns need little backtrack levels and therefore you seldom need to change this limit; before changing it you should try to rewrite your pattern to avoid the need for extra space. Nevertheless, a few useful patterns may overflow. Also, with recursive grammars, subjects with deep recursion may also need larger limits.

You have a recursing grammar, so this can be an issue for you.

Albert Chan Mon 22 Jan 2018 10:05 PM #21

retry recursive upto_last with bigger stack indeed solve the problem

lpeg.setmaxstack(201 * 2) -- max string length 200 ???

= upto_last('and'):match( ('*and'):rep(50) )
*and*and*and ...

Albert Chan Tue 23 Jan 2018 03:15 PM #22

the benchmark numbers in reply 12 might be flawed

my re pattern looks for 'and' from end-of-string, whereas your re grammar start from the beginning.
The timings will be affected by location of last 'and'

you might want to try benchmark with this non-backtract pattern:
(this new re pattern is fast and can handle long strings)


pat = re.compile "{g <- &('and' (!'and' .)* !.) / .g} 'and' {.*}"

= pat:match "this and that and whatever"
this and that
whatever

Nick Gammon Australia Forum Administrator Tue 23 Jan 2018 10:29 PM #23

I added a table capture ( "{| ... |}" ) to your pattern to I could check more accurately what the matches were. For the first match (with the two "and"s) your pattern is still slower. Perhaps if you post exactly how you are timing yours?


====================
Testing: foo and bar and whatever
----------
Nick
1="foo and bar "
2=" whatever"
Time taken = 11.454 us
----------
Albert
1="foo and bar "
2=" whatever"
Time taken = 43.860 us
====================
Testing: foo and bar
----------
Nick
1="foo "
2=" bar"
Time taken = 5.029 us
----------
Albert
1="foo "
2=" bar"
Time taken = 4.749 us
====================
Testing: XandY
----------
Nick
1="X"
2="Y"
Time taken = 4.749 us
----------
Albert
1="X"
2="Y"
Time taken = 5.587 us
====================
Testing: foo
----------
Nick
no match
Time taken = 3.073 us
----------
Albert
no match
Time taken = 3.632 us
====================
Testing: Xand
----------
Nick
1="X"
2=""
Time taken = 4.749 us
----------
Albert
1="X"
2=""
Time taken = 4.470 us
====================
Testing: andY
----------
Nick
1=""
2="Y"
Time taken = 5.029 us
----------
Albert
1=""
2="Y"
Time taken = 6.425 us
====================
Testing: and
----------
Nick
1=""
2=""
Time taken = 4.470 us
----------
Albert
1=""
2=""
Time taken = 4.749 us
====================
Testing: 
----------
Nick
no match
Time taken = 3.073 us
----------
Albert
no match
Time taken = 3.352 us

I tried averaging out the results over 20 trials, and removing the table capture. This time I get somewhat faster results:


====================
Testing: foo and bar and whatever
----------
Nick
foo and bar 
 whatever
Time taken = 1.355 us
----------
Albert
foo and bar 
 whatever
Time taken = 2.500 us
====================
Testing: foo and bar
----------
Nick
foo 
 bar
Time taken = 0.726 us
----------
Albert
foo 
 bar
Time taken = 0.629 us
====================
Testing: XandY
----------
Nick
X
Y
Time taken = 0.615 us
----------
Albert
X
Y
Time taken = 0.545 us
====================
Testing: foo
----------
Nick
no match
Time taken = 0.461 us
----------
Albert
no match
Time taken = 0.405 us
====================
Testing: Xand
----------
Nick
X

Time taken = 0.601 us
----------
Albert
X

Time taken = 0.531 us
====================
Testing: andY
----------
Nick

Y
Time taken = 0.629 us
----------
Albert

Y
Time taken = 0.573 us
====================
Testing: and
----------
Nick


Time taken = 0.824 us
----------
Albert


Time taken = 1.257 us
====================
Testing: 
----------
Nick
no match
Time taken = 0.475 us
----------
Albert
no match
Time taken = 0.405 us

(Time is average time).

Code to reproduce:


require "re"
require "tprint"
local ITERATIONS = 20
local result1, result2

print (string.rep ("*", 80))

c = re.compile [[
   parse     <- {noDelim} lastDelim  -- look for all up to the last delimiter followed by the last part
   delim     <- 'and'                      -- our delimiter
   noDelim   <- (!lastDelim .)*            -- zero or more characters without the last delimiter
   lastDelim <- delim {(!delim .)*} !.     -- the delimiter without any more delimiters and then end of subject
]]

pat = re.compile "{g <- &('and' (!'and' .)* !.) / .g} 'and' {.*}"  -- Albert Chan pattern

function showResults (result1, result2, start, finish)
  if not result1 then
    print ("no match")
  else
    if type (result1) == 'table' then
      tprint (result1)
    else
      print (result1)
      print (result2)
    end -- if
  end -- if
  print (string.format ("Time taken = %0.3f us", ((finish - start) / ITERATIONS) * 1e6))
end -- showResults 

function test (which)

  print (string.rep ("=", 20))
  print ("Testing:", which)

  print (string.rep ("-", 10))
  print "Nick"

  start = utils.timer ()
  for i = 1, ITERATIONS do
    result1, result2 = lpeg.match (c, which)
  end  -- for
  finish = utils.timer ()

  showResults (result1, result2, start, finish)

  print (string.rep ("-", 10))
  print "Albert"

  start = utils.timer ()
  for i = 1, ITERATIONS do
    result1, result2 = lpeg.match (pat, which)
  end -- for
  finish = utils.timer ()

  showResults (result1, result2, start, finish)

end -- test

tests = {
 "foo and bar and whatever",
 "foo and bar",
 "XandY",
 "foo",
 "Xand",
 "andY",
 "and",
 "",
}

for _, v in ipairs (tests) do
  test (v)
end -- for

Albert Chan Tue 23 Jan 2018 11:27 PM #24

This was unexpected. Multiple returns benchmark suggest both patterns are similar.

my machine is pentium 3 866Mhz, WinXP, luajit 1.1.8, lpeg 1.0.1


"foo and bar and whatever"
                        my pentium        your machine
iterations              1 million            20
time in us           Albert   Nick       Albert    Nick
return tables         14.4    15.9        43.9     11.5
return value           6.7     8.2         2.5      1.4
cost of table          7.7     7.7        41.4     10.1

i have since discovered a version without lookahead,
but for your really short string test, the timings is likely worse.
Algorithmetically this is faster, but there is an extra split call


pat = re.compile(
   "(g <- 'and' / .g)+ => split",
   { split = function(s,i) return true, s:sub(1, i-4), s:sub(i) end }
)

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 01:05 AM #25

Good questions. I've modified the test to summarize results.

With 100 iterations, and my test first:


Test                               Nick   Albert
------------------------------------------------
foo and bar and whatever          0.933    1.011
foo and bar                       0.629    0.548
XandY                             0.799    0.494
foo                               0.363    0.341
Xand                              0.673    0.886
andY                              0.503    0.615
and                               0.483    0.455
                                  0.413    0.467

And your test first:


Test                             Albert     Nick
------------------------------------------------
foo and bar and whatever          1.109    0.914
foo and bar                       0.556    0.626
XandY                             0.489    0.525
foo                               0.352    0.369
Xand                              0.478    0.511
andY                              0.478    0.520
and                               0.472    0.503
                                  0.338    0.344

Overall it seems faster the more iterations in testing, however it seems that for the ones where my grammar is faster, it is still faster, and vice-versa.

The differences seem less over more iterations.

With your newest version without lookahead:


Test                               Nick   Albert
------------------------------------------------
foo and bar and whatever          0.967    1.193
foo and bar                       0.584    0.765
XandY                             0.489    0.701
foo                               0.369    0.346
Xand                              0.106    0.735
andY                              0.517    1.137
and                               0.508    0.729
                                  0.508    0.335

I suspect the differences may be in how you are testing. Are you using MUSHclient or running a test using a standalone program? If you are using C or C++ with a more modern compiler than what I have, that might alter the results.

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 01:05 AM #26

I see you are using luajit which in itself will probably give somewhat different results to me because of the way it works.

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 01:10 AM #27

Testing with a longer string:


string.rep ("c", 1000) .. " and " .. string.rep ("a", 1000) .. " and " .. string.rep ("b", 1000)

I get timings:


Nick: 49.353   Albert: 22.584

Yours seems better for longer strings.

Albert Chan Wed 24 Jan 2018 02:13 AM #28

My re patterns with split does no lookahead, but has a bigger big O constant
Bypassing lpeg match-time-capture overhead might make it faster:


do
    local sub, match = string.sub, lpeg.match
    local pat = re.compile "(g <- 'and' / .g)+"
    function split_last_and(text)
        local i = match(pat, text)
        if i==nil then return nil end
        return sub(text, 1, i-4), sub(text, i)
    end
end

= split_last_and "this and that and whatever"
this and that
whatever

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 04:21 AM #29

I'm curious to know how your grammar works so well without overflowing the recursion stack. I have to assume that the grammar:


(g <- 'and' / . g)+

... does tail-recursion so that effectively turns the recursion into an iteration. Do you agree?

(In other words, the right-recursion into g can be replaced by a tail call, which simply goes to the start of g without adding to the call stack).

In assembler the equivalent would be:


foo     equ  *   # start of foo
# do stuff, and under certain conditions:
        jsr foo  # call foo again
        ret      # leave foo

This can be replaced by:


foo     equ  *   # start of foo
# do stuff, and under certain conditions:
        jmp foo  # call foo again

The first version adds to the call stack for each recursion, the second version does not, but is functionally equivalent.

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 04:27 AM #30

Albert Chan said:

My re patterns with split does no lookahead, but has a bigger big O constant
Bypassing lpeg match-time-capture overhead might make it faster:

...

Yes, but then you may as well do a greedy string.match. :)

It's also faster:


Test                        string.match   Albert
------------------------------------------------
foo and bar and whatever          0.528    1.288
foo and bar                       0.338    0.830
XandY                             0.279    0.863
foo                               0.170    0.344
Xand                              0.243    0.696
andY                              0.246    0.696
and                               0.226    0.665
                                  0.120    0.313
cccccccccccc ... bbbbbbbbbbbb    98.661  112.866

That final test string was:


 string.rep ("c", 5000) .. " and " .. string.rep ("a", 5000) .. " and " .. string.rep ("b", 5000)

Albert Chan Wed 24 Jan 2018 05:12 AM #31

"(g <- 'and' / . g)+" is tail recursive. It just advance the position.

my guess is after last 'and', it will recurse to end-of-string, then FAIL.
So it will return position of last 'and' (or nil if there was no 'and' anywhere)

it does no backtrack, thus no need to worry backtrack overflow limit.
(as far as i know, i am still a newbie ...)

"g <- . g / 'and'" is much more elegant to describe greedy match.
On average it need only to backtrack half the string length.
The top pattern, however, ALWAYS need to examine the whole string.
Your benchmark suggested lua might do greedy matches by backtacking.

Sadly lpeg 1.0.1 have this backtrack overflow limit problem.
And worse, its performance is very bad for long string even if no overflow.

you are correct that string.match is much faster for simple matching.
All of my code is for learning lpeg re, since many claimed that lpeg
can do everything lua pattern can do.

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 05:28 AM #32

Quote:

it does no backtrack, thus no need to worry backtrack overflow limit.

It must backtrack. In order to know it has the last "and" it therefore has to overshoot it and look for another one.

Therefore the loop finally fails when you get to ". g" where "g" does not end in "and" and therefore it has to backtrack to the last pattern (g) which had an "and" in it.

In other words, it matches either "and" or ". g". If g doesn't have an "and" in it then it would therefore need to be ". ." which would not be true at the end of the subject.

Therefore at end of subject, it has to backtrack to the last g which had an "and" thus that match is:


<some stuff>and

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 05:49 AM #33

To put it another way, say the string is:


"foo and " .. string.rep ("a", 1000)

The only way the match can know that there is not a final "and" is to check the entire string. Thus it has to backtrack to the last one it found.

Albert Chan Wed 24 Jan 2018 06:18 AM #34

you may be right about the 1 backtracking back to last valid g.

my original re pattern "{ g <- .g / &'and' } 'and' {.*}" fail with string
length of only 200. From what I've read, Roberto refer this as
non-blind greedy repetition. My guess is since every backtrack is
non-blind, it must be saved, thus filling the backtrack stack.

my newer re pattern "(g <- 'and' / .g)+" might be so-called blind ?
it will only need 1 backtrack after a FAIL, since previous g is valid
He named this restricted backtracking.

say, the string has 2 'and', at pos (after 'and') 10, 20

backtrack stack = [10] -> [20] (replace 10 instead of growing stack)

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 06:39 AM #35

I think the important thing is that your later pattern does right-recursion which can be turned into tail recursion, thus avoiding overflowing the stack.

Albert Chan Wed 24 Jan 2018 02:10 PM #36

Here is another re pattern that does NOT use recursive grammar.
It has similar performance as my split version (no lookahead)

Without recursive grammar, backtrack overhead may be smaller.
I optimize it furthur by not directly matching 'and'


pat = re.compile( 
      "((!'and' .)* ...)+ -> drop3 {.*}",
      { drop3 = function(s) return string.sub(s, 1, -4) end }
)

Nick Gammon Australia Forum Administrator Wed 24 Jan 2018 11:25 PM #37

Instead of "..." you could use ".^3".

Albert Chan Wed 24 Jan 2018 11:41 PM #38

just think of a faster lpeg re string (if not start with 'a', cannot be 'and')

"((!'and' . [^a]*)* .^3 )+ -> drop3 {.*}"

or, in recursive grammar (fastest for my luajit setup)

"(g <- 'and' / . [^a]* g)+ -> drop3 {.*}"

Albert Chan Thu 25 Jan 2018 02:05 AM #39

some questions answered with a debug version of lpeg.dll:

RE: "(g <- 'and' / .g)+" effect on backtrack stack
-- it is tail call with jmp, will not overflow backtrack stack

RE: "(g <- .g / &'and')"
-- as expected, it recursive, filling backtrack stacks
-- the pcode is very short 14 lines vs above 26 lines
-- there is a instruction "behind 3" to not consume the 'and'',
--> will be nice if i can use behind 3 instead of drop3 function.

RE: efficiency of ... vs .^3
-- both generate: lpeg.P(1) * 1 * 1 == lpeg.P(3)

Albert Chan Thu 25 Jan 2018 02:12 PM #40

this match_nd version "remove" all a's, and match only 'nd':

"( [^a]*.'a'* (g <- 'nd' / .  [^a]*.'a'* g)+ ) -> drop3 {.*}"

Albert Chan Fri 26 Jan 2018 04:36 PM #41

without recursive grammar (and no helper function!), this is VERY efficient:
i introduce &. to undo the last and, "lookahead" without wasting time


"{ [^a]* (!'and'.)* (.^3 [^a]* (!'and'.)* &.)* } .^3 {.*}"

doing the same benchmark in reply 24, this take 5.0 us per iteration.
my old lookahead (which validate only 1 char advance) take 6.7 us

Nick Gammon Australia Forum Administrator Fri 26 Jan 2018 09:40 PM #42

Yes, but you will wonder in a year's time when you review your code why you did it that way. :)

I tend to find with LPEG and RE that if I come back to my examples after a few months (as I did in this thread) that it takes the brain a little while to remember what all those symbols mean, and how some of the more obscure constructions work.

Having said that, I'm working on improving my post about LPEG to explain some of the ideas you introduced, like the grammar to match "this and that and whatever".

Nick Gammon Australia Forum Administrator Sat 27 Jan 2018 12:27 AM #43

One of the things that troubled me with "drop3" was you would have to adjust that every time you changed the word "and" to something else. With this pattern you can avoid that:


pat = re.compile( 
      "{ (g <-  { 'and' }  / . g)+ } -> drop {.*}",
       { drop = function(s, cap) return s:sub (1, -#cap -1) end } )

By putting a capture around our delimiter ('and') we can then determine its length inside the function and trim that many characters from the capture.

Nick Gammon Australia Forum Administrator Sat 27 Jan 2018 12:33 AM #44

So now you can match multiple delimiters with a single "drop" function, like this:


require "re"

target = "this fubar that grand canyon whatever"

pat = re.compile( [[
       { (g <-  { 'fubar' }         / . g)+ } -> drop 
       { (g <-  { 'grand canyon' }  / . g)+ } -> drop 
       {.*}
       ]],
       { drop = function(s, cap) 
                return s:sub (1, -#cap -1) 
                end } )

print (lpeg.match (pat, target))

Output:


this   that   whatever

Nick Gammon Australia Forum Administrator Sat 27 Jan 2018 12:37 AM #45

Interestingly, in the above example, the delimiters are not returned as captures (which may well be a good thing). However you can get them like this:


require "re"

target = "this fubar that grand canyon whatever"

pat = re.compile( [[
       {|  -- table capture
       { (g <-  { 'fubar' }         / . g)+ } -> drop 
       { (g <-  { 'grand canyon' }  / . g)+ } -> drop 
       {.*}  -- rest of line
       |}  -- end table capture
       ]],
       { drop = function(s, cap) 
                return s:sub (1, -#cap -1), cap  -- trim first capture, return second capture
                end } )

t = lpeg.match (pat, target)
for k, v in ipairs (t) do
  print (k, v)
end -- for

This prints:


1 this 
2 fubar
3  that 
4 grand canyon
5  whatever

Albert Chan Sat 27 Jan 2018 01:45 AM #46

To make above even more general, you may want to use
last capture, instead of second capture to drop characters.


function drop(s, ...)
  local last = select(select('#', ...), ...)
  return s:sub(1, #s - #last), last
end

pat = re.compile( "{(g<- {%A+}/ .g)+} -> drop", {drop=drop})

= pat:match "this-is--a----test"
this-is--a
----

Nick Gammon Australia Forum Administrator Sat 27 Jan 2018 01:51 AM #47

Would it necessarily be the last capture?

Albert Chan Sat 27 Jan 2018 02:13 AM #48

i read somewhere that the order of capture is the same as the number of open paranthesis count.
(or braces in lpeg re case)

if that is true, last capture is the last argument in drop

Albert Chan Sat 27 Jan 2018 05:31 AM #49

I patched lpeg, so now lpeg.B(-n) = n unconditional backtracks

For convenience, re pattern %b = lpeg.B(-1)
I can now do true greedy match and still tail recursive.


pat = re.compile "{.* %b^3 (g <- &'and' / %b g)}"

All my previous code were using multiple non-greedy match to
simulate a greedy match. This re pattern does true greedy match.

For long strings, it beat string.match in performance !
(correction: only if 'and' is close to end-of-string)

:-)

Albert Chan Sat 27 Jan 2018 09:47 PM #50

The drop function idea is very nice !
Lua string.match have a tough time doing greedy match ON the separator %A+


t = "this-is--a----test"
= string.match(t, "^(.*)(%A+)%a*$")      -- (.*) too greedy
this-is--a---
-

Lua string library can do it, but in multiple steps, slower and ugly.

lpeg has the nice property of adjusting how greedy we wanted.


pat = re.compile("{(g <- {%A+}/ .g)+} -> drop", {drop=drop})

Nick Gammon Australia Forum Administrator Sun 28 Jan 2018 04:06 AM #51

You can achieve that with a frontier pattern however:


a, b = string.match(t, "^(.*)(%f[%A]%A+%f[^%A])%a*$")
print (a)
print (b)

Results:


this-is--a
----

The frontier pattern asserts a change from "not in set" to "in set". Thus we detect the first hyphen. The inverse frontier pattern asserts the end of the hyphens.

Albert Chan Sun 28 Jan 2018 12:54 PM #52

wow, lua has %f pattern ?
It almost reached lpeg drop version performance !
With a tiny change, lua pattern even beat lpeg (again !)


benchmark: "this-is--a----test" -> "this-is--a", "----"

time(us)  match function  pattern
5.66      string.match    "(.*)%f[%A](%A+)"
7.20      string.match    "^(.*)(%f[%A]%A+%f[%a])%a*$"

6.57      lpeg.match      "{(g <- {%A+} / %a+ g)+} -> drop ", {drop = drop}

Sadly, lua %f is undocumented and buggy (on luajit 1.1.8 anyway)
= string.match("----whatever", "(.*)%f[%A](%A+)")
nil

Nick Gammon Australia Forum Administrator Sun 28 Jan 2018 08:57 PM #53

I've documented it here: http://www.gammon.com.au/scripts/doc.php?lua=string.find

And here: https://www.gammon.com.au/forum/?id=6034&reply=3#reply3

And here: https://www.gammon.com.au/forum/?id=6034&reply=8#reply8

Quote:

Sadly, lua %f is undocumented and buggy (on luajit 1.1.8 anyway)
= string.match("----whatever", "(.*)%f[%A](%A+)")
nil

I think this is behaving as intended. Looking at the source, a pattern match is doing this:


      previous = (s == ms->src_init) ? '\0' : *(s-1);
      if (matchbracketclass(uchar(previous), p, ep-1) ||
         !matchbracketclass(uchar(*s), p, ep-1)) return NULL;

In other words, it is testing for previously not "in set" to "in set" now.

Also, the first line says that if we are at the start of the subject then we replace the previous character (which doesn't exist) with 0x00.

So since you specified %f[%A] then "not in set" would be an alphabetic character. And 0x00 is not alphabetic, thus it fails that test.

If you turn the logic around then it works:


print (string.match("whatever----", "(.*)%f[%a](%a+)"))  --> "whatever"

Now we are looking for a transition to a letter from "not a letter" and 0x00 is not a letter.

Nick Gammon Australia Forum Administrator Sun 28 Jan 2018 09:04 PM #54

You can make your pattern work by allowing for the 0x00:


print (string.match("----whatever", "(.*)%f[^%a%z](%A+)"))

Rather than using [%A] I used [^%a%z] which will allow for the 0x00 character.

Albert Chan Sun 28 Jan 2018 09:21 PM #55

%f[^%a%z] trick work !
Parsing above class range takes time, however, killing performance.
maybe pre-built class ranges ?

= lpeg.pcode( re.compile "[^%a\x00]" ) -- with my patched lpeg
[]
00: set [\x01-\x40\x5b-\x60\x7b-\xff] --> just cut and paste
09: end

benchmark: "this-is--a----test" -> "this-is--a", "----"

time(us)  match function  pattern
4.65      string.match    "(.*)%f[\x01-\x40\x5b-\x60\x7b-\xff](%A+)"
6.67      string.match    "(.*)%f[^%a%z](%A+)"
8.26      string.match    "^(.*)(%f[^%a%z]%A+%f[%a])%a*$"

6.57      lpeg.match      "{(g <- {%A+} / %a+ g)+} -> drop ", {drop = drop}

Albert Chan Thu 08 Feb 2018 06:58 PM #56

I discovered a lpeg re pattern that beat string.match, even with pre-built frontier pattern class

The trick is to use frontier pattern idea in lpeg (backtrack before %A+)

benchmark: "this-is--a----test" -> "this-is--a", "----"

3.63       pat = re.compile "{ %a* (%A+ %a* &%A)* } {%A+}"

the same idea can be use for previous "(.*)and(.*), without drop function


pat = re.compile("{ >&%z (%z >&%z)* } %z {.*}", {z='and'})

note: ">&'and' " is shorthand for "(g <- &'and' / .[^a]* g)"

Nick Gammon Australia Forum Administrator Fri 09 Feb 2018 02:53 AM #57


pat = re.compile("{ >&%z (%z >&%z)* } %z {.*}", {z='and'})

That doesn't compile for me. The symbol ">" is not defined in the re documentation.

Albert Chan Fri 09 Feb 2018 03:03 AM #58

'>' is just a shorthand for the grammar (g <- patt / . [^head-chars-of-patt]* g)

it need a search and replace (see notes in reply 56)

Albert Chan Fri 09 Feb 2018 06:37 PM #59

above code (reply 57) will compile with my patched lpeg, which does the expansion automatically.

i just posted the source in github (comment welcome)

https://github.com/achan001/LPeg-anywhere

Albert Chan Sun 11 Feb 2018 04:38 PM #60

Just wanted to show a faster and more controlled way to do gsub in re

unlike string.gsub, re.gsub replaces all matches,
that means re.gsub cannot do this:

t = 'this and that and whatever'

=string.gsub(t, 't%w*', string.upper, 2)
THIS and THAT and whatever

here is a lpeg re pattern that will:

sub2 = re.compile("{~ (>('t'%w*) -> upper)^-2 .* ~}", {upper=string.upper})

=sub2:match(t)
THIS and THAT and whatever

I used my patched '>' matching prefix, above literally translate to this:

sub2 = re.compile("{~ (g <- ('t'%w*) -> upper / .[^t]* g)^-2 .* ~}", {upper=string.upper})

Albert Chan Sun 11 Feb 2018 07:11 PM #61

On second thought, re.gsub can do limited replacements using helper function

function upto(rep, n)
    local f = rep
    if type(f) ~= 'function' then f = function() return rep end end
    return function (s)
        if n <= 0 then return end   -- no replace
        n = n - 1
        return f(s)
    end
end

= re.gsub(t, "'t'%w*", upto(string.upper, 2))
THIS and THAT and whatever

Albert Chan Mon 12 Feb 2018 07:25 PM #62

Above function upto() for demonstration only
there are many problems with it ...

upto generated function cannot be memoized in re.gsub
even if it can, generated function is "dead" after n replacements.

And, because it returned function, back reference will not work

= re.gsub(t, "%w+", "(%0)")
(this) (and) (that) (and) (whatever)

= re.gsub(t, "%w+", upto("(%0)", 1)) -- this failed to recognize %0
(%0) and that and whatever

-- this gsub style will handle it all

= re.match(t, "{~ (g <- %w+ -> '(%0)' / .%W* g)? .* ~}")
(this) and that and whatever

Albert Chan Wed 14 Feb 2018 01:46 AM #63

my previous lpeg re pattern for greedy search may fail if the pattern is repeated
(I learn this from http://www.inf.puc-rio.br/~roberto/docs/peg.pdf, page 11)

-- greedy search for 'xuxu', my old way will not work
= re.match( 'xuxuxui', "(g <- 'xuxu' / .g)+")
5

-- with known pattern, we can change the search:
= re.match('xuxuxui', "(g <- 'xu'^+2 / .g)+ ")
7

However, it maybe hard to recognize a repeated pattern, say %a%u
And, how to change the search ? Is %a%u+ correct ?

This is Roberto's solution to repeat sub-patterns problem
(the published pattern is flawed, it had * instead of +, which return 1 for no match)

= re.match( 'xuxuxui', "(g <- &'xuxu' . / .g)+")
4

returned position is 1 pass last occurence, but is correct
final position = 4 - 1 + fixedlen('xuxu') = 3 + 4 = 7

I have an improvement to his pattern, without the position arithmetic
(note: the loop never check first position, but it is ok)

= re.match( 'xuxuxui', "(. (g <- &'xuxu' / .g))* 'xuxu' ") 
7

Albert Chan Wed 14 Feb 2018 02:20 PM #64

what I learned so far to translate lua pattern "(.*)" .. z .. "(.*)" to lpeg re:
Note: pattern using my patched lpeg: https://github.com/achan001/LPeg-anywhere

this work with all z, even with repeated sub-patterns, say 'andand' (1)

pat1 = re.compile("{(. >&%z)*} %z {.*}", {z=z})

if text is short (short enough not to overflow backtack stack), we can do true greedy

pat2 = re.compile("{g <- .g / &%z} %z {.*}", {z=z})

my patched lpeg can optimize above and use less backtrack stack (2)

pat3 = re.compile("{g <- .[^%z]* g / &%z} %z {.*}", {z=z})

it can even turn into a tail call, without worrying about stack (3)

pat4 = re.compile("{.* %b <&%z} %z {.*}", {z=z})

it does not have to match from end-of-string (4)

pat5 = re.compile("{(>%z)* %b <&%z} %z {.*}", {z=z})

(1) '>' is for forward match: >%pat == (g <- %pat / . [^%pat]* g)
(2) with my patched lpeg: [^%pat] == non-head-chars of %pat
(3) '<' is for backward match: <%pat == (g <- %pat / %b g)
(4) the loop (>%z)* move just beyond the correct position