lpeg functions

Posted by Albert Chan on Mon 29 Jan 2018 02:04 AM — 27 posts, 102,805 views.

Albert Chan Mon 29 Jan 2018 02:04 AM #0

lpeg manual mentioned P(true) and P(false). why are these needed ?

x true = x
true x = x

so P(true) will always be optimized away.

At first, I thought P(false) is to retain captures, then switched to alternative.

(lpeg codes A with captures ...) * P(false) + (lpeg codes B ...)

But it does not. All the captures are gone.

Above just optimized to (lpeb codes B ...)

The only reason lpeg does not do this optimization is due to its
match-time-capture function.

I cannot think of 1 case where P(boolean) is needed.

May that were the reason lpeg re doesn't have them as variables.

Nick Gammon Australia Forum Administrator Mon 29 Jan 2018 03:56 AM #1

The only way I can explain that is from the LPEG documentation:

Quote:

patt1 * patt2

Returns a pattern that matches patt1 and then matches patt2, starting where patt1 finished. The identity element for this operation is the pattern lpeg.P(true), which always succeeds.

Note the reference to "the identity element for this operation". With that as a clue, and looking up identity elements, eg.

Algebraic patterns — Identity element

It appears that, useful or not, lpeg.P(true) and lpeg.P(false) are useful in situation where you may (sometimes) want to make something that always succeeds. Perhaps you are writing a function to combine THIS and THAT, and sometimes THAT needs to always match. Being able to return lpeg.P (true) gives you a useful pattern that you can use in that case.

Nick Gammon Australia Forum Administrator Mon 29 Jan 2018 04:11 AM #2

As an analogy, say we had this Lua code:


a = b * 1

Now you might say that multiplying by one (the identity operation) is not particularly useful. However what about:


a = b * foo ()

Where 'foo' is a function that returns a number, and sometimes that number is 1.

Now it is useful for the writer of the function 'foo' to have a way of expressing "identity operation" (ie. do nothing, or "always succeed").

Conversely you might it want to fail in which case you return zero. And the equivalent to that in LPEG would be lpeg.P (false).

Nick Gammon Australia Forum Administrator Mon 29 Jan 2018 04:22 AM #3

Maybe this is a good example, I'm not sure.

I want to match "foo" or "bar" or nothing at all followed by "nick". So:


lpeg.match (C ((P"foo" + P"bar" + P(true))) * "nick", "foonick")

That matches foo OR bar OR (true) and then checks for nick.

Results:


foonick  --> captures "foo"
barnick  --> captures "bar"
nick     --> captures ""
others   --> fail

Albert Chan Mon 29 Jan 2018 10:48 AM #4

since above pattern, literally translated to lpeg re:

"{ 'foo' / 'bar' / '' }"

lpeg.re do have lpeg.P(true) as variable ... it is ''
P(true) will be optimized away anyway, so above is same as

"{ 'foo' / 'bar' / }"

To push my understanding a bit furthur ...

expr ^ 0 == P { expr * V(1) + P(true) }

However, with current lpeg implementation, RHS is less efficient

Tried push even furthur to represent P(false) as lpeg re !''

The pcode are different, but they are equivalent, since not true == false

Albert Chan Mon 29 Jan 2018 12:22 PM #5

Just wanted to share how to use lpeg.P(function)

this was one of my lpeg re pattern for regex "(.*)and(.*)", using =>


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

Redo above using lpeg.P(function). Just search and replace "=> " to "%"


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

The split function will implicitly cast as lpeg.P object. Although unnecessary, we can rewrite split explicitly


{split = lpeg.P( function(s, i) return s:sub(1, i-4), s:sub(i) end )}

Albert Chan Tue 30 Jan 2018 01:28 PM #6

Found a real use for P(true) in re.lua


local function mult (p, n)
  local np = mm.P(true)
  while n >= 1 do
    if n%2 >= 1 then np = np * p end
    p = p * p
    n = n/2
  end
  return np
end

So, mult(p, 0) return P(true), which will optimized away

function name mult is misleading, it should be named re_pow

P.S.
I recently patched lpeg.B so it can move back from current position (upto 255 bytes)
%b = lpeg.B(-1) = move back 1 byte

To optimize %b ^ n to lpeg.B(-n), all I need is 1 line above P(true)


if p == Predef.b then return mm.B(-n) end

Albert Chan Tue 30 Jan 2018 03:00 PM #7

snippet from re.lua:


local m = require"lpeg"

-- 'm' will be used to parse expressions, and 'mm' will be used to
-- create expressions; that is, 're' runs on 'm', creating patterns
-- on 'mm'
local mm = m

why the need for both m and mm ?

Albert Chan Tue 30 Jan 2018 06:52 PM #8

Tried to understand meaning of lpeg.B(-patt) (hint, it is not -lpeg.B(patt))

... it is lpeg.P(-patt) !

lpeg.B(-patt) does nothing, except to make its argument a lpeg object

Worse, this is just based on my informal tests, it might do something nasty !

The best I can say, lpeg.B(-patt) is undefined

Nick Gammon Australia Forum Administrator Tue 30 Jan 2018 10:15 PM #9

Not sure. Both of these match:


print (lpeg.match (P(3) * B(-P('foo')) * 'bar', 'foobar'))  --> 7
print (lpeg.match (P(3) * B( P('foo')) * 'bar', 'foobar'))  --> 7

Nick Gammon Australia Forum Administrator Tue 30 Jan 2018 10:18 PM #10

Albert Chan said:

why the need for both m and mm ?

Not sure, unless it is for documentation.

Albert Chan Tue 30 Jan 2018 11:31 PM #11

both of your examples confirm my finding: B(-patt) = P(-patt), which is silly.

foo, bar, foobar, = P'foo', P'bar', P'foobar'

-- B match back characters: (foo == "foo")
= (3 * B(foo) * bar):match "foobar" => 7

-- B is actually P, matching: (foo ~= "bar")
= (3 * P(-foo) * bar):match "foobar" => 7
= (3 * B(-foo) * bar):match "foobar" => 7

both return the same position, but doing different things ... try these:

= (3 * B( foobar) * bar):match "foobar" => nil
= (3 * B(-foobar) * bar):match "foobar" => 7

-> these are undefined behavior, can change in the future
-> NEVER use negation argument for lpeg.B

Albert Chan Wed 31 Jan 2018 12:10 AM #12

find a bug in re.lua


pat = re.compile "[^a]^2"  -- ok
pat = re.compile "[a]^2"   -- bad
.\re.lua: attempt to perform arithmetic on local 'p' (a string value)

Albert Chan Wed 31 Jan 2018 02:15 AM #13

Above class range bug turns out to be an example of using P(false) !
There are many ways to fix the bug:

1. P(false) way
make sure more than 1 items -> P(false) + item = P(item)
-> so add a m.Cc(false) * in front of item
-> this guaranteed folding run at least once.

2. complement (likely more efficient)
since complement function always run, return c == '^' and any - p or m.P(p)
-> this also guaranteed class range is lpeg object

3. patch mult(p, n) (somewhat patchy ...)
all other suffixes ^+n ^-n ? * + use lpeg __pow function, which convert p to lpeg object implicitly.
-> add 1 line in mult(p,n) : p = m.P(p)

Nick Gammon Australia Forum Administrator Wed 31 Jan 2018 04:03 AM #14

Albert Chan said:

The best I can say, lpeg.B(-patt) is undefined

I think I can explain what is happening, possibly it's a bug.

Try this:


print (lpeg.match (P(3) * B( -P('foo')) * 3, 'foobar'))  --> 7
print (lpeg.match (P(3) * B( -P('foo')) * 3, 'foofoo'))  --> nil

In other words, the B(-P'foo') contains an assertion (not a match) (B(P'foo') would be a match) and since it doesn't consume any characters the lpeg.B does not move backwards any characters.

If you print the tree for:


P(3) * B( P('foo')) * 3

You get:


seq
  any
  seq
    any
    seq
      any
      seq
        behind 3
          seq
            char 'f'
            seq
              char 'o'
              char 'o'
        seq
          any
          seq
            any
            any

You will notice that the lpeg.B generates "behind 3" because it knows it has to go back the length of 'foo' (and then try matching).

However this:


P(3) * B( -P('foo')) * 3

Generates:


seq
  any
  seq
    any
    seq
      any
      seq
        behind 0
          not
            seq
              char 'f'
              seq
                char 'o'
                char 'o'
        seq
          any
          seq
            any
            any

Now it generates "behind 0" (so it is matching the current position, not 3 back) and checking if that equals 'foo' (and then negating the result).

I'm not sure if this is a bug or not. You could argue that an assertion like -P'foo' should not backtrack because it doesn't move the position of the match pointer.

Judging by the generated opcodes, "behind 3" just moves the current pointer backwards, and as the documentation says:

Quote:

Pattern patt must match only strings with some fixed length ...

That means that, if it matches, then the pointer is guaranteed to be back where it started (by consuming input). And since assertions don't consume input, the pointer is not moved backwards.

Albert Chan Wed 31 Jan 2018 04:27 AM #15

Reading the source, it does not do any kind of analysis you did.
When it see the -, len(patt) = 0, thus generate behind 0
(which will optimized away in generated pcode)

In other words, it never expected a minus in the first place.

To understand it better, it is better to breakup the logic


let behind(n) = move back n bytes
let len(patt) = bytes the pattern need for a match

B(patt) = behind(len(patt)) * P(patt)

so B is an assertion, without consuming any charcters.

With above formula, B(-patt) = P(-patt), which is what we observed
But it is not based on any logical reasoning.

Logically, the sign should be pulled out, B(-patt) = -B(patt)
(preceded by not this pattern == not preceded by this pattern)

P.S.
I just improved on my lpeg.B patch, now lpeg.B(-patt) = behind(len(patt)).
In other words, it move back without matching.

Albert Chan Wed 31 Jan 2018 01:59 PM #16

parsing B(-patt) is confusing

Example: patt = -P('and') * P(1), What is B(patt) ?

I thought it assert not preceded by 'and' and not end-of-line ... I were wrong

lpeg currently set len of pattern assertion = 0
-> len(patt) = 0 + 1 = 1
-> it added a behind 1

the problem is, this might not be what the user expected.
since B(patt) = behind(len) * P(patt), and len == 1, P(1) always optimized away

So, write it without assertions inside patt, it is easier to read: -(B'a' * 'nd')

Nick Gammon Australia Forum Administrator Wed 31 Jan 2018 11:15 PM #17

My impression is that it simply moves the current position back a fixed number of characters and then matches on what you provide. I can't off-hand think of good uses for it, but perhaps if you were parsing a source file, and were looking for quotes, you would want to accept:

But not:

\"

So you might look for something like:


P'"' * B('\')

That is a quote, provided it does not have a backslash before it.

Nick Gammon Australia Forum Administrator Wed 31 Jan 2018 11:16 PM #18

Of course that is wrong, that would give only quotes with a backslash before them. Hmmm.

Albert Chan Thu 01 Feb 2018 12:00 AM #19

Beside validation like above, it may be used to optimize search

note: i added '@' prefix in re.lua to call lpeg.B

t = 'everytime everywhere everything'

pat1 = re.compile "g <- 'everything' / . [^e]* g"
pat2 = re.compile "g <- 'g' @'everything' / . [^g]* g"

since 'g' is rarer than 'e', pat2 is more efficient than pat1

Albert Chan Fri 02 Feb 2018 12:15 AM #20

just learned lpeg can do search from the end of string

-- Example I got from lpeg tutorial

target = "You see 666 dogs and a cat"

= lpeg.match(P'cat', target, -3)
25

Nick Gammon Australia Forum Administrator Fri 02 Feb 2018 03:03 AM #21

That is mentioned here: http://gammon.com.au/lpeg

Search for "anywhere".

Albert Chan Fri 02 Feb 2018 06:07 PM #22

this example is from lpeg re reference page, how does it work ?

Both parenthesis are needed ... why ?


rev = re.compile[[ R <- (!.) -> '' / ({.} R) -> '%2%1' ]]
print(rev:match"0123456789")   --> 9876543210

Above causes backtrack stack overflow for long string (which means pattern is not tail recursive)

Below is a tail recursive pattern using my B patched version, {~ ~} simply concatenate all captures


rev = re.compile ".* {~ (@{.} %b)* ~}"

Albert Chan Sat 03 Feb 2018 05:30 PM #23

Finally figured out why (!.) cannot be written as plain !.

I had expected the lpeg precedence unary minus above divide:

(-P(1)) / func == -P(1) / func

But re.lua did not put ! precedence above ->

re pattern "!. -> func" == "! (. -> func)" == "!." (likely a bug, func optimized away)


= lpeg.pcode( re.compile("!. -> func", {func=func}) )
[1 = function ]
00 testany -> 3
02 fail
03 end

Nick Gammon Australia Forum Administrator Sat 03 Feb 2018 08:50 PM #24

The documentation at http://www.inf.puc-rio.br/~roberto/lpeg/re.html shows that

->

is higher in precedence than

Albert Chan Sat 03 Feb 2018 09:11 PM #25

I do not understand what " (!.) -> '' " mean, so I tried without " -> '' "

=re.match("123456789", " R <- (!.) / ({.} R) -> '%2%1' ")
invalid capture index (2)

-- what if '' is 1 ?
=re.match("123456789", " R <- (!.) -> 1 / ({.} R) -> '%2%1' ")
987654321

Albert Chan Mon 19 Feb 2018 07:54 PM #26

I mentioned re.lua mult(p, n) in reply 6.
Turns out, this function is unnecessary, since lpeg have mult functionality built-in (n >= 0)

p^n = mult(p,n) * p^0

just a few lines patch to lptree.c lp_star() simplify everything.
https://github.com/achan001/LPeg-anywhere/blob/master/lptree.c

Removed mult function !
--> new function re.pow, just to supply the third argument true, for true power
--> re.pow(p,n) = p * p ... * p (n times)

function re.pow(p, n) return mt.__pow(p, n, true) end