Хорошо известно, что современные реализации регулярных выражений (в первую очередь PCRE) имеют мало общего с оригинальным понятием регулярных грамматик . Например, вы можете разобрать классический пример контекстно-свободной грамматики {a n b n ; n> 0} (например, aaabbb ) с использованием этого регулярного выражения ( demo ):
~^(a(?1)?b)$~
Мой вопрос: как далеко вы можете пойти? Можно ли также проанализировать контекстно-зависимую грамматику {a n b n c n ; n> 0} (например, aaabbbccc ) с помощью PCRE?
Вдохновленный ответом NullUserExceptions (который он уже удалил, поскольку он не удался для одного случая), я думаю, что нашел решение самостоятельно:
$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
Попробуйте сами: http://codepad.viper-7.com/1erq9v
Если вы рассматриваете регулярное выражение без положительного утверждения (часть (?=...) ), у вас есть следующее:
~^a+(b(?-1)?c)$~
Это не более чем проверка того, что существует произвольное число s, за которым следует равное количество b s и c s.
Это еще не удовлетворяет нашей грамматике, потому что число s должно быть одинаковым. Мы можем гарантировать, что, проверяя, что число a s равно числу b s. И это то, что делает выражение в предложении lookahead: (a(?-1)?b)c . c необходимо, чтобы мы не только соответствовали части b s.
Я думаю, что это впечатляюще показывает, что современное регулярное выражение не только способно анализировать нерегулярные грамматики, но даже может анализировать неконтекстно-свободные грамматики. Надеюсь, это заложит конец бесконечному поглаживанию «вы не можете делать X с регулярным выражением, потому что X не является регулярным»
Мой вопрос: как далеко вы можете пойти?
В интересах не создания кода, который является нечитаемым болотом пунктуации, я собираюсь рискнуть downvotes и ответить на другой, хотя и очень близкий, вопрос: как далеко вы должны идти?
Регуляторы регулярных выражений – это блестящая вещь, которая есть в вашем наборе инструментов, но они не все и заканчивают все программирование. Возможность писать парсеры в удобочитаемой манере также является блестящей вещью в вашем наборе инструментов.
Регулярные выражения следует использовать вплоть до того момента, когда они начинают понимать, что ваш код трудно понять. Кроме того, их ценность в лучшем случае сомнительна, что в худшем случае наносит ущерб. Для этого конкретного случая, вместо того, чтобы использовать что-то вроде отвратительного:
~^(?=(a(?-1)?b)c)a+(b(?-1)?c)$~x
(с извинениями перед NikiC), которые подавляющее большинство людей, пытающихся сохранить его, либо должны полностью заменить, либо потратить значительное время на чтение и понимание, вы можете рассмотреть что-то вроде не-RE, парсер "(псевдокод):
# 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
Это будет намного легче поддерживать в будущем. Я всегда хотел бы предложить людям, чтобы они предполагали, что те, кто идет за ними (кто должен поддерживать код, который они пишут), являются психопатами, которые знают, где вы живете, – в моем случае это может быть наполовину правильно, я понятия не имею, где вы живете 🙂
Если у вас нет реальной потребности в регулярных выражениях такого рода (а иногда есть веские причины, такие как производительность в интерпретируемых языках), вы должны сначала оптимизировать чтение .
Вот альтернативное решение, использующее балансировочные группы с .NET regex:
^(?'a'a)+(?'b-a'b)+(?(a)(?!))(?'c-b'c)+(?(b)(?!))$
Не PCRE, но может представлять интерес.
Пример: http://ideone.com/szhuE
Изменить : добавлена отсутствующая проверка балансировки для группы a и онлайн-пример.
Решение, которое не упоминалось:
^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1\2$
Посмотрите, какие совпадения и неудачи в демо-версии regex .
Это использует группы саморегуляции (идея @Qtax используется для его вертикального регулярного выражения ).