Add some simple syntax to match against nested pairs of regexes

[IsaacOscar]

Bassically, a common thing I often do is want to match against nested groups of brackets, e.g. given the string hello ( a ( b ) c ) wo ( rl ) d (
I want the matches

( a ( b ) c ) 

And

( rl )

but not ( as that doesn't have a matching closing bracket.

now pcre2 is capable of doing that,
if we let BEGIN be the start regex (in this case \(), and END be the end regex (i.e. \)), then you can do that with the regex:

BEGIN(?J)(?<name>(?:(?!BEGIN|END).|BEGIN(?&name)END)*)END

(In the above name can be any name that is not a 'free variable' in BEGIN and END, i.e. the regex can be nested with the same name)
The above is quite long and verbose and took me a while to work out (and I've since forgotten how it works), so it would be nice to have a syntax for this.

For example the syntax could be:

(?/BEGIN/END)

So to match round brackets (?/\(/\)). To match round or curley brackets (e.g. { a ( b } )), you could write use (?/[(}]/[(}]).

Another example which I frequently use when processing LaTeX files is if you want to match against curly brackets but ignore those preceded by a backslash:

(?/(?<!\\)[{]/(?<!\\)[}])

The entire string { helo \{ world } will match.

[ltrzesniewski]

Actually, regex recursion is meant for handling that. You used it in your pattern, but it could be used in a simpler way (IMO) by not writing BEGIN and END multiple times. Here's an example:

(?(DEFINE)
  (?<name>
    \(
    (?>(?&name)|.)*?
    \)
  )
)
(?&name)

And if the recursion is the only thing you need in your pattern, you can simplify that to:

\(
(?>(?R)|.)*?
\)

[IsaacOscar]

Ooh that's a really useful website, thanks!
Sorry, I wrote my regex to be as general as possible, in particular your first regex above can't be used multiple times in the same pattern without changing name, even if you do add the (?J) option to it, I can't seem to use it twice but for different bracket types,
e.g.
((a)){{b}} matches if you use my version with BEGIN and END as \( and \) then again but with \{ and \}:
https://regex101.com/r/uI79O8/1

But it doesn't work with your version:
https://regex101.com/r/OogDmn/1

Your second regex isn't correct as it matches the entire string ()), whereas it.

Also, I didn't use (?< or *? in my regex, is there any particular reason you did?

[ltrzesniewski]

I can't seem to use it twice but for different bracket types

That would need two different expressions. This is why (?(DEFINE)) is great, as it lets you write more complex expressions easily:

(?(DEFINE)
  (?<parens>
    \(
    (?>(?&any)|.)*?
    \)
  )

  (?<braces>
    \{
    (?>(?&any)|.)*?
    \}
  )

  (?<any>
    (?&parens) | (?&braces)
  )
)
(?&any)

Your second regex isn't correct as it matches the entire string ())

If you mean it matches too much, it's because I added the s option to the regex and it matches with the ( in the first line.

Also, I didn't use (?< or *? in my regex, is there any particular reason you did?

To avoid unnecessary backtracking.

[zherczeg]

Note: next version of pcre2 will allow keeping capturing brackets after recursion.

[NWilson]

I'm thinking about this...

It's tough adding new regex syntax. There's a tremendous amount of inertia in the ecosystem, with so many regex engines, and we ideally want to avoid fracturing the syntax too much.

I think I'd be willing in principle to add new syntax... but only if there's a reasonable chance that some other implementation might pick it up in future. PCRE2 is strongest when it's ahead of the rest - but not going off in some different direction (which might cause problems for people who want to adopt it).

There's also quite a big cost to new syntax. The cost is payed by users, not by us developers!

You say:

The above is quite long and verbose and took me a while to work out (and I've since forgotten how it works), so it would be nice to have a syntax for this.

And that's really the problem. Each new syntax element is cryptic and hard to remember. If you (and I!!) struggle to remember existing syntax, then new syntax will need to be extremely, extremely useful.

---

Having said all that... matching backslashed-escaped elements, and matching balanced pairs of brackets, are some of the most common parsing tasks, and I run into these problems myself often.

My usual solution is to fall back to a for-loop, or imperative code. There's basically a complexity barrier that hits the "sweet spot" of regexes, and beyond a certain level, it simply becomes more comprehensible to do the parsing using code.

I'm still not sure where that leaves these sort of problems. It's nice to know that recursive regexes can match balanced brackets, but it's also something that's beyond what 95% of users would actually consider solving with a regex, in a typical month's work.

[IsaacOscar]

Thanks so much for considering this,

I've actually been using a version of this for quite some time: I have a fish script that translates regexes for me into the pattern I showed above.

The current version is this (in case anyone else finds it useful), but I keep changing it.
I have a regex <regex> function that takes a regex and translates it as follows:

1. If it sees a (*{}) in the string, it translates it to a regex that matches a sequence of single characters, or balanced {...} groups, where \{ and \} are not parsed as group delimiters (but \\{ is, etc.) The entire sequence is captured in a numbered group.
2. A (:*{}) is similar, but doesn't capture a group.
3. The { and } can be any single characters other than *, ?, +, so you can e.g. do (*()) to use round brackets. (No backslash escapes are supported).
4. The * can be replaced by other *, ?, or + quantifier sequences (e.g. (++{})) for a possessive quantifier). Personally i've never used anything other than * though. I haven't implemented support for the {n,m} quantifier syntax.
5. Things will break if you precede the syntax by a backslash, i.e. don't do \(*{}).

Note that unlike what I originally proposed in this issue, the (*{}) syntax does not actually match the enclosing brackets.
So (*{}) will match the empty string in foo{}, this is so you can do a search a replace to add things inside the group,
e.g. in fish, string replace -r (regex 'foo{(*{})}') 'foo{1 + $1 + 2}' '1 + foo{0}' will give you 1 + foo{1 + 0 + 2}.

The code has a lot of string collect calls, they just ensure fish doesn't split things into an array/list if they contain newlines.

function g  # Groups regexes to keep them isolated from other operators next to them
	string collect -- "(?:"$argv")"; end
function orr  # or's a bunch of regexes
	string join -- "|" $argv | string collect; end
function balanced -a syntax group recur # search for ($syntax<quantifiers><left><right>)
	# Character classes so the character is matched literally even if it's a special regex character
	set L "[\$2]"
	set R "[\$3]"
	# the \Q and \E, they're needed sadly (they don't show up in the output!, their interpreted by string replace)
	set BS '\Q(?<!\\\\)(?:\\\\{2})*\\\\\E' # Matches an odd number of backslash
	# The cat forces string replace to operate on stdin, I don't know what it's necessary
	cat | string replace -ar -- \
		"\Q($syntax\E([+*?]+)([^+*?])([^+*?])\)" \
		"($group"(g (orr (g $BS$L) (g $BS$R) "(?!"(orr $L $R)")." "$L($recur)$R"))"\$1)" |
	string collect; end

function regex
	if not string match -qr -- '\(\:?[+*?]+[^*?][^*?]\)' $argv[1] # Don't bother transforming stuff
		echo $argv[1] | string collect
	else
		# The ?J is needed if you use the no-capturing options more than once
		echo "(?J)$argv[1]" |
			balanced '' '' '?-1' |
			balanced ':' '?<B>' '?&B' |
			string collect; end; end

[zherczeg]

Recursions are very good to find balanced (start/end) constructs. Their only weakness - data cannot be escaped from recursions - is fixed in the next pcre2 release.