POSIX BRE / ERE compliant parsers

[tgross35]

Hello,

I would like to suggest adding POSIX Basic Regular Expression (BRE) and Extended Regular Expression (ERE) support, possibly via modules e.g. regex::RegexBRE.

The main reason for this is for compatibility with coreutils functions:

• awk: only supports ERE
• sed: supports BRE (default) or ERE (with -E)
• grep: supports BRE and ERE, and sometimes PCRE (but inconsistently, it's not POSIX)

I understand that the use case for this is somewhat narrow and thus perhaps out of the scope of this library. Just wanted to at least bring it up before working on my own implementation, in case there is a need.

The implementation for this could likely just be a basic wrapper that validates the supplied data is POSIX-compliant and performs token substitutions in-place to enable parsing via the default regex engine.

Reference on the syntax: https://en.wikibooks.org/wiki/Regular_Expressions

[BurntSushi]

Yeah this is definitely out of scope, sorry. I'm pretty sure this has been discussed before, although I can't find an issue for it.

The implementation for this could likely just be a basic wrapper that validates the supplied data is POSIX-compliant and performs token substitutions in-place to enable parsing via the default regex engine.

Nope. Doesn't work. A BRE/ERE parser isn't enough to make them POSIX compatible. You also need a POSIX compatible regex engine to go along with them. For example, POSIX regexes use "leftmost longest" semantics where, for example, sam|samwise will match samwise, but this regex engine (and other PCRE-like regex engines) will match sam. The differences don't end there. BREs have backreferences. The resolution of submatches is different (and notoriously difficult to get right). Then there's the handling of non-greedy matches (if at all) and locale support.

With that said, I do think it would be interesting to make regex-syntax support BRE/ERE parsing at least. There's likely quite a bit of common ground. Folks would still need to build their own BRE/ERE regex engine, but they at least wouldn't need to start by writing their own parser. With that said... Writing a BRE/ERE regex engine is probably an order of magnitude more work than writing the parser, so I'm not sure it would really be that beneficial. That is, if you really need a Rust BRE/ERE regex engine, I'm definitely never going to be able to give that to you, so you'd have to write that piece. And if you're writing that piece, it's not a whole lot of extra work to write the parser, relatively speaking.

In theory I might be willing to support a BRE/ERE syntax mode (but definitely one that isn't supported by the regex engine itself), but I'd want to see at least the following:

1. A good use case for why this is needed. You mention "compatibility with coreutils functions," but you actually list programs, not functions. It's not clear what use a regex parser in Rust would be for them. Are you talking about a Rust re-implementation of those programs? If so, a regex parser is really the least of your worries (as noted above).
2. A proposal for how to implement these new supported syntaxes in a way that is not too invasive and doesn't overly complicate the code.
3. A strategy for how we'll check that the syntax supported is indeed POSIX compatible. That is, I'd want to hear about the testing strategy for this.

[tgross35]

Thanks for the quick response and for the insight. Admittedly I didn't realize that there would likely be a lack of compatibility with the engine, which means a lot more work than I originally was thinking. Something that simply reformats a string for the regular engine and gets "close enough" to perfect POSIX is probably suitable for my use case, but of course it wouldn't be acceptable here if there are engine differences (didn't know about that, thanks for the information).

I know there had been some discussion on https://github.com/uutils about sed and awk, so maybe when those roll around it this will be worth re-investigating.

I'll close this since it seems very much blue sky now