This is a fork original LPeg library. It contains unstable modifications. If you search for original library, see this page.
This fork contains some experimental optimizations to the original LPeg library. It's a drop-in replacement and does not change pattern semantics, it just optimize them, on demand. The optimization ratio can be huge (hundreds of times faster in most favorable cases).
The optimizations provided are focused on cases where a pattern has a lot
of alternatives, for instance P'foo' + P'bar' + P'baz' + .... The vanilla
implementation would place a checkpoint a the beginning of the string and test
each pattern until it fails, rewind to the start of string and try next
pattern.
When you have hundreds or thousands of alternatives, it is very inefficient
(but it was not the intended use after all). This repository contains a
collection of patches to transform patterns into more efficient forms by
applying some rules pretty munch like the
Aho-Corasick algorithm.
For instance, the previous example is more efficient as
(P'ba' * (P'r' + P'z')) + P'foo'. By merging the common prefix, LPeg virtual
machine can narrow string matching munch faster.
There is also some optimization to the LPeg VM diriectly: the ITestVector
has been added to test all alternatives in one go for the current character
rather than each alternative separately.
This is currently a work in progress and is considered unstable. If you find a bug, or if optimization changes your pattern semantics an any way: please send a bug report.
If you're interested in details about this work, you may want to read these blog articles about the design and results of these optimizations.
Optimizations are not enabled by default, you have to do it manually by calling
the :optimize method.
local m = require"lpeg"
-- build pattern normally
p = (m.P'aaa' + m.P'bbb' + m.P'acc' + m.P'ddd')
-- now optimize it
opt_p = p:optimize()
print(opt_p:match 'acc')
The returned pattern is a regular LPeg pattern, that can still be used to build larger patterns (optimizations will be kept).
The optimize() method takes an optional integer argument to set the limit of
optimization passes. The default limit (500) is more than enough for most
patterns, but huge ones needs up to thousands of passes to be fully optimized.
This can be quite long. the optimizer still needs to be... optimized !