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

by

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”

More Related Contents:

  1. Matching Unicode letter characters in PCRE/PHP
  2. PHP regular expressions: No ending delimiter ‘^’ found in
  3. php regex to match outside of html tags
  4. “vertical” regex matching in an ASCII “image”
  5. PHP Regex: How to match \r and \n without using [\r\n]?
  6. Extra backslash needed in PHP regexp pattern
  7. What literal characters should be escaped in a regex?
  8. Tilde operator in Regular expressions
  9. RegEx BackReference to Match Different Values
  10. php regex word boundary matching in utf-8
  11. How do I match accented characters with PHP preg?
  12. PHP – How do I convert string number to number [closed]
  13. Regex pattern can't figure out
  14. preg_match(): Compilation failed: invalid range in character class at offset
  15. preg_match and UTF-8 in PHP
  16. “Unknown modifier ‘g’ in…” when using preg_match in PHP?
  17. Optional Whitespace Regex
  18. How to replace text URLs and exclude URLs in HTML tags?
  19. How to split a string by multiple delimiters in PHP?
  20. What Delimiter to use for preg_replace in PHP (replace working outside of PHP but not inside)
  21. Remove repeating character
  22. Codeigniter Routes regex – using dashes in controller/method names
  23. Replace only first match using preg_replace [duplicate]
  24. Remove accents without using iconv
  25. PCRE regular expression overlapping matches
  26. Remove all non-numeric characters from a string; [^0-9] doesn’t match as expected
  27. How to get Open Graph Protocol of a webpage by php?
  28. How to create clean url using .htaccess
  29. Regular expression preg_quote symbols are not detected
  30. Detecting a url using preg_match? without http:// in the string

Leave a Comment