lpeg.B(-n) patch for uncondtional backtrack

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

lpeg.B(-n) patch for uncondtional backtrack

Albert Chan
I did a patch that use B(-n) for the behind n instruction (no matching)
NOTE: %b == lpeg.B(-1) == lpeg.pcode behind 1

Example: capture chars in groups of 3's

pat = re.compile "({...} %b%b)+"
= pat:match "<a href="tel:123456789" x-apple-data-detectors="true" x-apple-data-detectors-result="0">123456789"
123     234     345     456     567     678     789

Example: lua patten "(.*)and(.*)"

pat = re.compile "{(g <- 'and' / . [^a]* g)+ %b%b%b} ... {.*}"

Above example, but does TRUE greedy match (stop on first match)
The re pattern is tail recursive. No backtrack stack overflow !
For long string, this is faster than lua string.match !

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

lpeg error system check for infinite recursion, i trick it by using .%b%b instead of %b
If anyone know how to fix it, please let me know

----
Follwing is the patches if anyone interested (4 files, total 5 lines)

>diff lpeg\lptree.c lpeg-1.0.1\lptree.c
430d429
<       tree->u.n = n;                        // possibly lpeg.B(-n)
689d687
<   if (sib1(tree)->tag == TNot) n = sib1(tree)->u.n;

>diff lpeg\lpcode.c lpeg-1.0.1\lpcode.c
661d661
<   if (sib1(tree)->tag != TNot)        // lpeg.B(-n) = behind n

>diff lpeg\lpprint.c lpeg-1.0.1\lpprint.c
185d184
<       if (sib1(tree)->tag != TNot)    // lpeg.B(-n) = behind n

>diff lpeg\re.lua lpeg-1.0.1\re.lua
23c27,28
< local Predef = { nl = m.P"\n", b = m.B(-1) }
---
> local Predef = { nl = m.P"\n" }