Clone wiki

cl-string-match / Regular expressions in Common Lisp

Regular expressions engines in Common Lisp. A Survey

There are several different libraries implementing regular expression engines in Common Lisp. Some of them are listed on Cliki and below we survey them:

  • CL-PPCRE by Edi Weitz -- the golden standard of regex engine implementations for Common Lisp
  • cl-irregsexp or GitHub mirror claims to be a very fast alternative to CL-PPCRE though has a weird syntax and API.
  • CLAWK originally developed by by Michael Parker is an AWK programming language embedded into Common Lisp. It has a regexp engine of its own that is hosted in a separate repository.
  • motion-grammar-kit by Golems.org has a regex engine developed by Neil T. Dantam of the Georgia Tech Humanoid Robotics Lab under Direction of Prof. Mike Stilman that uses a number of finite-automation algorithms to handle regular expressions. However the regex and FA implementations here are not really aimed at text processing or pattern matching, but at general symbolic analysis -- i.e., it is not assumed that the terminal symbol alphabet consists of characters, and various set operations are implemented on the regular languages.
  • bitap-regexp by Paul-Virak Khuong implementing a Bitap-based regular expressions engine on top of a Thompsons NFA (described here)
  • lispbuilder-regex is a part of LispBuilder project and is derived from the CLAWK/regex engined originally developed by Michael Parker.
  • com.informatimago.common-lisp.regexp by Pascal J. Bourguignon is a part of a bigger com.informatimago package. Was intended to be a strict implementation of the POSIX Perl Compatible Regular expressions, however is not yet complete according to the ASD file.
  • RE by Jeffrey Massung is a simple Lua-style backtracking regexp engine implementation for LispWorks. A portable version is a part of this library (see pre.lisp in CL-STRING-MATCH sources or API reference)
  • regex by David McClain features a DFA and NFA finite state automata regexp implementation in Lisp and a CSV format file reader
  • slime/nregex was written Lawrence E. Freil in 1992 as an attempt to create a Lisp implementation of regular expressions without external dependencies. In 2007 Helmut Eller removed all dependencies on nregex from the SLIME/SWANK but the nregex is still distributed along with SLIME.

Summary

Name Ql NFA
CL-PPCRE Quickdocs No
cl-irregsexp Quickdocs ?
CLAWK/regex Quickdocs ?
motion-grammar-kit No Yes
bitap-regexp No Yes
lispbuilder-regex Yes ?
com.informatimago.common-lisp.regexp Yes ?
RE Quickdocs¹ No
regex No Yes
slime/nregex No No
  • Ql is it Quicklisp:quickload-able?
  • NFA is it a finite-state automation (Thomspon NFA) or a backtracking perl-style regexp engine?
  • ¹ Portable RE included in cl-string-match.

Utilities

  • recursive-regex by Russ Tyndall, Nathan Bird and Ryan Davis of Acceleration.Net. Integrates with CL-PPCRE to make named regex groups dispatch to custom matcher functions, which can recursively call another regex in the context of the original regex. It can then return a (parse) tree of results.

See also

If you think this page is incomplete and you want to add something, file a ticket or edit it!

Don't miss Cliki:

Return to Home or Resources.

Updated