regex backtracking entire word

Question

I have a string that is a list of key value pairs that looks like:

Key=key1,Value=value1 Key=key2,Value=value2

Some of my values have braces around them, so I could have something like:

Key=key1,Value={"a":"b"}, Key=key2,Value=value2, Key=key3,Value={"c":{"d":"e"}}

I want to create a regex to match just the values that are in braces. The regex I currently have is {[^=]*} , and that works if none of the values have = in them.

This will break it:

Key=key1,Value={"a=":"b"}, Key=key2,Value=value2, Key=key3,Value={"c":{"d":"e"}}

I tried changing my regex to be {[^(Key=)]*} , but that did not match it.

If I can assume Key= is the start of a new key and will not appear in regex values, how can I modify my regex to match this?

Answer 1

The problem with your current regex is that you can't peform negations with strings inside a character class. It's a character class. So this won't work as you would expect: {[^(Key=)]*} - it matches any string that contains characters that are not (, K, e, y =, ), zero or more times, but you want it to match any strings that are not Key= instead.

You can use a different approach with recursion to accomplish what you need:

{(([^{}]|(?R))*)}

Demo

Answer 2

Forget regex. Accomplishing what you want to do with a regex is going to be error prone and unreliable. You're always going to have little edge cases that you can't really handle well with a regex.

What you really need is a context free grammar. Use pyparsing.

>>> from pyparsing import OneOrMore, Regex, Optional
>>> pairListParser = OneOrMore(u'Key=' + Regex(u'[^,]+') + u',Value=' + Regex(u'[^, ]+') + Optional(Regex(u',? ')))
>>> x = u'Key=key1,Value={"a=":"b"}, Key=key2,Value=value2, Key=key3,Value={"c":{"d":"e"}}'
>>> pairListParser.parseString(x, parseAll=True)
([u'Key=', u'key1', u',Value=', u'{"a=":"b"}', u', ', u'Key=', u'key2', u',Value=', u'value2', u', ', u'Key=', u'key3', u',Value=', u'{"c":{"d":"e"}}'], {}

Note that in the example above, I assumed that keys cannot contain a comma (,) and that values cannot contain a comma (,) or a space (). I did so for simplicity, but with pyparsing, you can rework the parser to allow for those cases. It's just a matter of doing the work to figure it out, whereas with regex, it is mathematically impossible to parse it if those restrictions don't apply.

Then you just need to pull out the results.

>>> parsedX = pairListParser.parseString(x, parseAll=True)
>>> parsedXIter = iter(i for i in parsedX if i not in (u'Key=', u',Value=', u', '))
>>> result = dict(zip(parsedXIter, parsedXIter))
>>> result
{u'key3': u'{"c":{"d":"e"}}', u'key2': u'value2', u'key1': u'{"a=":"b"}'}

(There are probably better ways to pull out the results, but this was quick and dirty. Noteably, pyparsing has capabilities that let you discard certain elements or transform the results while it parses.)

Once you have the results in a dict, you can do whatever you want with the values:

for k, v in result.items():
     m = re.match(u'^{(.+)}$', v)
     if m:
         print(m.groups())

I imagine it would be better to parse them as JSON or something like that, but the point is now you've cut off all the stuff around the value and can work with just the value in isolation.

Answer 3

Simply use the regex below

Value=({[^{}]*(?1)?})

Demo: https://regex101.com/r/pJ8lO9/2

Explanation:

You need a CFG, and you can get a CFG solution using regex(in terms of programming)

For further reading about this claim please check: How can we match a^n b^n with Java regex? and https://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

As this pattern needs to match balanced curly bracket, which forms:

a^n b^n

And as n is arbitrary, regex(in terms of maths) cannot solve this. We need a CFG. And the regex(in terms of programming) solution for this is:

(a(?1)?b) 

This is a recursive pattern. '(?1)' recurses first capturing group: '(a(?1)?b)'. And the '?' is to avoid infinite recursion. '(a(?1)b)' would recurse infinitely. So '(?1)' has two options, '(a(?1)?b)', or empty. In CFG notation, it's represented as:

(?1) -> a(?1)b | ε 

Back to our solution. 'a' repsesents '{' and 'b' represents '}', so

({(?1)?})

and we need to put values inside brackets:

({[^{}]*(?1)?})

and decorating it with 'Value='

Value=({[^{}]*(?1)?})