Match a^n b^n c^n (e.g. “aaabbbccc”) using regular expressions (PCRE)

44
votes

It is a well known fact that modern regular expression implementations (most notably PCRE) have little in common with the original notion of regular grammars. For example you can parse the classical example of a context-free grammar {anbn; n>0} (e.g. aaabbb) using this regex (demo):

~^(a(?1)?b)$~

My question is: How far can you go? Is it also possible to parse the context-sensitive grammar {anbncn;n>0} (e.g. aaabbbccc) using PCRE?

4
phpregexpcre
What the heck do (?R) and ~ do? What is wrong with preg_match('a*b*c*',...)? – Chriszuma
First of all, PHP regexes need delimiters. That's what the ~ is for. Second of all, abc* matches acccccccccc – NullUserException
@Chriszuma: The ~ are just delimiters (you could use / and many other characters as well). The (?R) signifies recursion. It means "put the whole regular expression in here again". – NikiC
That's correct about a*b*c* matching acccccccccccc, but I don't see what's wrong with a+b+c+. – Justin Morgan
Wait, I understand now. The tricky part is that n has to be the same for each group, correct? So if there are 5 as, then there have to be exactly 5 each of b and c. No, I know that's not possible without recursion, and if you can do it even with recursion, then I certainly don't know how. – Justin Morgan

4 Answers

35
votes

Inspired by NullUserExceptions answer (which he already deleted as it failed for one case) I think I have found a solution myself:

$regex = '~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x';

var_dump(preg_match($regex, 'aabbcc'));    // 1
var_dump(preg_match($regex, 'aaabbbccc')); // 1
var_dump(preg_match($regex, 'aaabbbcc'));  // 0
var_dump(preg_match($regex, 'aaaccc'));    // 0
var_dump(preg_match($regex, 'aabcc'));     // 0
var_dump(preg_match($regex, 'abbcc'));     // 0

Try it yourself: http://codepad.viper-7.com/1erq9v

Explanation

If you consider the regex without the positive lookahead assertion (the (?=...) part), you have this:

~^a+(b(?-1)?c)$~

This does nothing more than check that there's an arbitrary number of as, followed by an equal number of bs and cs.

This doesn't yet satisfy our grammar, because the number of as must be the same, too. We can ensure that by checking that the number of as equals the number of bs. And this is what the expression in the lookahead assertion does: (a(?-1)?b)c. The c is necessary so we don't only match a part of the bs.

Conclusion

I think this impressively shows that modern regex is not only capable of parsing non-regular grammars, but can even parse non-context-free grammars. Hopefully this will lay to rest the endless parroting of "you can't do X with regex because X isn't regular"

11
votes

Here is an alternative solution using balancing groups with .NET regex:

^(?'a'a)+(?'b-a'b)+(?(a)(?!))(?'c-b'c)+(?(b)(?!))$

Not PCRE, but may be of interest.

Example at: http://ideone.com/szhuE

Edit: Added the missing balancing check for the group a, and an online example.

11
votes

My question is: How far can you go?

In the interests of not creating code that is an unreadable morass of punctuation, I'm going to risk the downvotes and answer a different, though very much related, question: how far should you go?

Regular expression parsers are a brilliant thing to have in your toolkit but they are not the be all and end all of programming. The ability to write parsers in a readable manner is also a brilliant thing to have in your toolkit.

Regular expressions should be used right up to the point where they start making your code hard to understand. Beyond that, their value is dubious at best, damaging at worst. For this specific case, rather than using something like the hideous:

~^(?=(a(?-1)?b)c)a+(b(?-1)?c)$~x

(with apologies to NikiC), which the vast majority of people trying to maintain it are either going to have to replace totally or spend substantial time reading up on and understanding, you may want to consider something like a non-RE, "proper-parser" solution (pseudo-code):

# Match "aa...abb...bcc...c" where:
# - same character count for each letter; and
# - character count is one or more.

def matchABC (string str):
    # Init string index and character counts.
    index = 0
    dim count['a'..'c'] = 0

    # Process each character in turn.
    for ch in 'a'..'c':
        # Count each character in the subsequence.
        while index < len(str) and str[index] == ch:
            count[ch]++
            index++

    # Failure conditions.
    if index != len(str):        return false # did not finish string.
    if count['a'] < 1:           return false # too few a characters.
    if count['a'] != count['b']: return false # inequality a and b count.
    if count['a'] != count['c']: return false # inequality a and c count.

    # Otherwise, it was okay.
    return true

This will be far easier to maintain in the future. I always like to suggest to people that they should assume those coming after them (who have to maintain the code they write) are psychopaths who know where you live - in my case, that may be half right, I have no idea where you live :-)

Unless you have a real need for regular expressions of this kind (and sometimes there are good reasons, such as performance in interpreted languages), you should optimise for readability first.

3
votes

Qtax Trick

A solution that wasn't mentioned:

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

See what matches and fails in the regex demo.

This uses self-referencing groups (an idea @Qtax used on his vertical regex).