regex - Matching a^n b^n c^n for n > 0 with PCRE

How would you match a^n b^n c^n for n > 0 with PCRE?

The following cases should match:

abc
aabbcc
aaabbbccc

The following cases should not match:

abbc
aabbc
aabbbccc

Here's what I've "tried"; /^(a(?1)?b)$/gmx but this matches a^n b^n for n > 0:

ab

aabb
aaabbb

Online demo

Note: This question is the same as this one with the change in language.

Answer

Qtax trick

(The mighty self-referencing capturing group)

^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1\2$

This solution is also named "The Qtax trick" because it uses the same technique as from "vertical" regex matching in an ASCII "image" by Qtax.

---

The problem in question burns down to a need to assert that three groups are matched of the same length. As a simplified version, to match:

xyz

Where x, y and z are really just subpatterns with a variable with matching length n of a, b and c. With an expression that uses lookaheads with self-referencing capturing groups, a character we specify is added to each repetition of the lookahead, which can effectively be used to "count":

aaabbbccc
 ^  ^  ^

This is achieved by the following:

• (?:a…)+ A character of subpattern a is matched. With (?=a*, we skip directly to the "counter".


• (\1?+b) Capturing group (\1) effectively consumes whatever has previously been matched, if it is there, and uses a possessive match which does not permit backtracking, and the match fails if the counter goes out of sync - That is, there has been more of subpatterns b than subpattern a. On the first iteration, this is absent, and nothing is matched. Then, a character of subpattern b is matched. It is added to the capturing group, effectively "counting" one of b in the group. With b*, we skip directly to the next "counter".


• (\2?+c) Capturing group (\2) effectively consumes whatever has previously been matched just like the above. Because this additional character capture works just like the previous group, characters are allowed to sync up in length within these character groups. Assuming continuous sequences of a..b..c..:

_{(Excuse my art.)}

First iteration:

| The first 'a' is matched by the 'a' in '^(?:a…)'.
| The pointer is stuck after it as we begin the lookahead.
v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
 ^^^   |^^^       ^
skipped| skipped  Matched by c in (\2?+c);
by a*  | by b*         \2 was "nothing",

       |               now it is "c".
       Matched by b
       in (\1?+b).
     \1 was "nothing", now it is "b".

Second iteration:

 | The second 'a' is matched by the 'a' in '^(?:a…)'.
 | The pointer is stuck after it as we begin the lookahead.

 v,- Matcher pointer
aaaa...bbbbbbbb...cccc...
       /|^^^      |^
eaten by| skipped |Matched by c in (\2?+c);
\1?+    | by b*   |     '\2' was "nothing",
  ^^    |      \2?+     now it is "cc".
 skipped|
 by a*  \ Matched by b
          in (\1?+b).
          '\1' was "nothing", now it is "bb".

As the three groups discussed above "consumes" one of each of a, b, c respectively, they are matched in round-robin style and "counted" by the (?:a…)+, (\1?+b) and (\2?+c) groups respectively. With the additional anchoring and capturing what we started, we can assert that we match xyz (Representing each group above) where x, y and z are an, bn and cn respectively.

---

As a bonus, to "count" more, one can do this:

Pattern: ^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1{3}\2$
Matches: abbbc

aabbbbbbcc
aaabbbbbbbbbccc

Pattern: ^(?:a(?=a*(\1?+bbb)b*(\2?+c)))+\1\2$
Matches: abbbc
aabbbbbbcc
aaabbbbbbbbbccc