TRE on github

by Ville Laurikari on January 15, 2013

You can find it here. It’s been there a while, but probably no-one has noticed:

The repo has been migrated from the old repo in Darcs.

Pull requests are welcome.

{ 1 comment… read it below or add one }

1 Karthik Jayaraman May 26, 2014 at 01:46


I have developed a proof of concept regular expression engine that is able to handle back-references, sub-match grouping and lookaround operators without backtracking. The engine is based on a Thompson NFA algorithm with some modifications to allow for back-references and sub-matches and has been tested successfully against a large number of the test cases that Perl has made available. I’ve seen descriptions in a number of places that suggest that backreferences cannot be implemented without backtracking so any feedback on this engine would be greatly appreciated.

The code and (some) documentation can be accessed at GitHub .

The engine was designed as a proof of concept to mimic most of the features of the java.util.regex API in a non-backtracking implementation. It currently handles most major features of the java regex engine except lazy quantifiers and UNICODE.

Appreciate your time in looking at this. It would be great to hear your thoughts if you find this interesting.



Leave a Comment

You can use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="">

Previous post: