Proposal: regular expression package

[yj-qin]

We need a simple and compact regular expression package that supports the POSIX’s Extended Regular Expressions syntax (Maybe extend to PCRE syntax in the future). This package needs to be able to compile a regular expression and use it to match or replace given strings.

Consideration:
Which style of the regular expression engine should we implement? There are two main styles: backtracking and automata. The backtracking style is used by popular languages like Java, Python, and JavaScript. This style allows for more features but can result in bad performance in some cases. The automata style is used by Rust's regex crate and Go's regex std. While it may not allow for certain features that rely on backtracking, it can match regex in linear time.

References:

• Regular Expression Matching Can Be Simple And Fast
• Regular Expression Matching: the Virtual Machine Approach
• POSIX Extended Regular Expressions
• Rust's regex crate
• Go's regex lib