Perl-compatible regular expression optimizer

Optimizes perl-compatible regular expressions.

The general syntax for running the program is: regex-opt <regexp>

Example:
regex-opt 'xaz|xbz|xcz'
x[a-c]z

Try running regex-opt on Abigail's 7 kilobyte URL regexp. The result should be about 5 kilobytes long.

• * (repeat 0-inf)
• + (repeat 1-inf)
• ? (repeat 0-1)
• {n} (repeat n)
• {n,} (repeat n-inf)
• {n,m} (repeat n-m)
• . (accept any char except \n)
• [a-z] (character sets)
• [^a-z] (inverse character sets)
• [[:alpha:]] (character classes)
• \s (and other character classes and escapes)
• x|y (alternatives)
• (?:x|y) (non-capturing grouping)
• *? (non-greedy repeat)

• ^ (match string-begin)
• $ (match string-end)
• () (capturing is converted to noncapturing)
• Any (? -command that is not mentioned in supported syntax
• Unicode-specific markup

• Character set optimization: [A-Zabcdefgh-yz0-9%] becomes [[:alnum:]%]
• Alternate characters: y|[yp]|[zx] becomes [px-z]
• Counting: aaa* and aa+ become a{2,} and (a?){3} becomes a{0,3}
• Combining: abcde|xycde becomes (?:ab|xy)cde
• Parenthesis reduction: ((abc)) becomes abc, (xx|yy)|zz becomes xx|yy|zz
• Compression: xyzyzxyzyz becomes (?:x(?:yz){2}){2}
  • This might not be always a good thing.
• Choice counting: a+|aa+ becomes a+, (b|) becomes b?, dxxxxb|dxxxb|dxxb|dxb becomes dx{1,4}b

• Combining counts:
  • a?|b? should become (?:a|b)?, now becomes a?|b?
• Redundancy removal (removal of alternatives that are subsets of other alternatives):
  • xfooy|x[a-q]+y should become x[a-q]+y, now becomes x(?:foo|[a-q]+)y

Help in solving these shortcomings would be welcome.

regex-opt has been written by Joel Yliluoma, a.k.a. Bisqwit,
and is distributed under the terms of the General Public License (GPL).

For compiling you need the following GNU tools: g++, make.

Downloading help

• Do not download everything - you only need one file (newest version for your platform)!
• Do not use download accelerators or you will be banned from this server before your download is complete!

Date (Y-md-Hi) acc        Size Name                
2007-0227-1646 r--       27855 regex-opt-1.2.2.tar.bz2
2007-0227-1646 r--       29041 regex-opt-1.2.2.tar.gz
2007-0227-1646 r--        1093 patch-regex-opt-1.2.1-1.2.2.bz2
2007-0227-1646 r--         985 patch-regex-opt-1.2.1-1.2.2.gz
2007-0221-1727 r--       27830 regex-opt-1.2.1.tar.bz2
2007-0221-1727 r--       28995 regex-opt-1.2.1.tar.gz
2007-0221-1727 r--        4617 patch-regex-opt-1.2.0-1.2.1.bz2
2007-0221-1727 r--        4546 patch-regex-opt-1.2.0-1.2.1.gz
2006-0117-0047 r--       27194 regex-opt-1.2.0.tar.bz2
2006-0117-0047 r--       28323 regex-opt-1.2.0.tar.gz
2006-0117-0047 r--       12255 patch-regex-opt-1.1.1-1.2.0.bz2
2006-0117-0047 r--       17105 patch-regex-opt-1.1.1-1.2.0.gz
2006-0116-2359 r--       27106 regex-opt-1.1.1.tar.bz2
2006-0116-2359 r--       28160 regex-opt-1.1.1.tar.gz
2006-0116-2359 r--        8769 patch-regex-opt-1.1.0-1.1.1.bz2
2006-0116-2359 r--        8835 patch-regex-opt-1.1.0-1.1.1.gz
2005-1025-1531 r--       23442 regex-opt-1.1.0.tar.bz2
2005-1025-1531 r--       23942 regex-opt-1.1.0.tar.gz
2005-1025-1531 r--        2247 patch-regex-opt-1.0.0-1.1.0.bz2
2005-1025-1531 r--        2061 patch-regex-opt-1.0.0-1.1.0.gz
2004-0712-2034 r--       23287 regex-opt-1.0.0.tar.bz2

← Back to the source directory index at Bisqwit's homepage