Geek Answers Handbook

Do extended regular expressions support backreferences?

Wikipedia says extended regular expressions "drop backlink support," so you must use the "main" regular expression mode to enable them. However, a number of implementations seem to support backreferences for extended regular expressions. For example, with gcc 4.6 on Ubuntu Precise they are supported. FreeBSD implementations seem to only support them in native mode.

Boost says (and seems to agree with Wikipedia) that backlinks are not supported for extended regular expressions, but Boost :: Regex adds them as an extension.

Is this just a partially defined part of the standard that is interpreted differently with each implementation?

+8
c regex posix
source share
3 answers

As others have already pointed out, it is clear that POSIX ERE does not support backlinks.

The rationale given in the basic specifications of OpenGroup Issue 7 for not adding backreferences to the ERE is given as:

It has been suggested that in addition to interval expressions, backreferences ('\ n') should also be added to the ERE. This has been rejected by standard developers as they can reduce consensus.

Quote from: Justification: Basic Definitions: Extended Regular Expressions

The main reason for this restriction is to allow the conversion of POSIX EES to deterministic finite state machines (DFAs), and indeed, the initial implementation of ERE on Unix was done as a DFA. Using DFA allows you to guarantee performance. Matching patterns with (unlimited) backlinks is an NP-hard problem and possibly even an NP-complete problem. Consensus in the POSIX standards committee would never have been achieved if ERE backlinks were proposed, because it would force all companies using the original Unix implementation to change their code to a non-deterministic implementation and abandon their performance guarantees, and some of these The companies were members of the committee.

It was also noted that backlinks in RE are not intuitive for either users or developers, and indeed, they caused extreme confusion more often than now. See, for example, the examples given in RE-Interpretation: The Dark Corners

NOTE. backlinks in REs do not match subpattern references in lookup text in tools like sed.

+5
source share

According to the IEEE / Open Group standard, Extended Regular Expressions do not support backreferences (section 9.5.1), although several real-world implementations do.

+4
source share

According to the POSIX.1-2008 standard, only basic regular expressions support backreferences. Section 9.3.6 describes how they work in the BRE. The extended regular expressions section does not mention them at all, and the lexical grammar conventions in section 9.5.1 say that backreference tokens apply only to BREs.

+1
source share

More articles:


All Articles