Matching the pattern representing regexp set

Question

This question is not related to variable length look-behind as it probably has a solution without negative look-behind.

In Python3, I am trying to match a pattern that is probably at the limit of what can be achieved with a regexp, but I still want to give it a try. I am actually trying to avoid using a parsing tool.

What I want to match is the pattern that indicate a regexp set. So the following would be matched.

[abc]
[1-9\n\t]
[ \t\]]
[\\\]]
[[\\\\\\\]]

The square brackets cannot be nested, by example in [[]], we want to match [[].

Although, since a \] indicate an escaped bracket, we need to skip those. But a pattern such as \\] must be accepted. The following would not be matched.

[\]
[\\\]
[abc\\\]

The rule ends up being match from [ to the first ] that is not preceded by an odd amount of \.

It seems negative lookbehind does not work because it must have fixed length.

Edit: An interesting solution was given by Wiktor Stribiżew

re.compile(r'\[[^]\\]*(?:\\.[^]\\]*)*\]')

Edit: Simpler version of the above by Rawing

r'\[(?:\\.|[^]\\])*\]'

Thank you, I am although trying to apply this to this specific problem. — Olivier Melançon, Dec 29 '17 at 15:59
See https://regex101.com/r/nmYOPJ/1/. The question has nothing to do with variable width lookbehind. Although, there may be edge cases, but then you may use https://regex101.com/r/nmYOPJ/2. — Wiktor Stribiżew, Dec 29 '17 at 16:17
Why are people closing this question. It took 10 minutes for us to realize it has nothing to do with lookbehind. — Olivier Melançon, Dec 29 '17 at 16:19
It is closed because you have not described the way to solve the issue in the question and made it unclear. Please edit the question to include the attempt at a working pattern. — Wiktor Stribiżew, Dec 29 '17 at 16:20
A (in my opinion) more readable version of Wiktor's regex: `\[(?:\\.|[^]\\])*\]` — Aran-Fey, Dec 29 '17 at 17:01
`\[(?:\\.|[^]\\])*\]` is "readable" but is much less efficient because it is not written with the unroll-the-loop principle in mind. `\[[^]\\]*(?:\\.[^]\\]*)*\]`, depending on the input, may be 10 times as fast. Regex should be as efficient as it can, otherwise, your "readable" version may cause slowdowns or even crashes. — Wiktor Stribiżew, Dec 29 '17 at 20:10

score 1 · Accepted Answer · answered Dec 29 '17 at 20:25

You may use

re.compile(r'\[[^]\\]*(?:\\.[^]\\]*)*]', re.DOTALL)

See the regex demo.

Details

\[ - a [ char
[^]\\]* - 0 or more chars other than ] and \
(?: - start of a non-capturing group matching a sequence of:
- \\. - a \ char followed with any char
- [^]\\]* - 0 or more chars other than ] and \
)* - zero or more repetitions of the patterns inside the non-capturing group
] - a ] char.

The regex follows the unroll-the-loop principle. Depending on the input it may work much, even 10+ times faster than the non-unrolled version, r'\[(?:\\.|[^]\\])*]', that is based on an infinitely quantified alternation group, causing lots of redundant backtracking steps.

Note that the regex above can fail when the initial [ is preceded with a backslash. In those cases, you will need

r'(?<!\\)(?:\\{2})*(\[[^]\\]*(?:\\.[^]\\]*)*])'

See this regex demo

The main difference here is (?<!\\)(?:\\{2})*, a (?<!\\) negative lookbehind that fails the match if the current position is preceded with a \ char, and (?:\\{2})* that matches 0+ repetitions of two literal backslashes. The rest of the pattern is enclosed with capturing parentheses, and when a match is found, you just need to access match.group(1) to get the right value.

Matching the pattern representing regexp set

1 Answers1