Intereting Posts
Финал: AJAX / jQuery / PHP Форма представления и модальная коробка открываются с успехом Apache: Как включить кеш браузера для test.json, который переписывает / генерируется через json.php? Почему это 'onClick disable = true; this.form.submit ();» работать на одной кнопке, но не на другой? Отправить параметр на сервер из приложения Android Временные метки Laravel для отображения миллисекунд Как проверить, есть ли запрос, поступающий с того же сервера или другого сервера? Joomla: получить группу пользователей с уровня доступа к странице с помощью PHP как я могу публиковать внешнюю форму с помощью PHP? MySQL: запрос таблицы лидеров со связками есть способ загрузить видео на youtube с помощью php Очистка / дезинфекция атрибутов xpath Разбирайте XML-файл с URL-адреса, используя php Как установить доступ по умолчанию для доступа к типу страницы в Silverstripe? Есть ли способ интегрировать OpenCV с PHP? Javascript, создающий имя пользователя с использованием входов

Сопоставьте a ^ nb ^ nc ^ n (например, «aaabbbccc») с использованием регулярных выражений (PCRE)

Хорошо известно, что современные реализации регулярных выражений (в первую очередь PCRE) имеют мало общего с оригинальным понятием регулярных грамматик . Например, вы можете разобрать классический пример контекстно-свободной грамматики {a n b n ; n> 0} (например, aaabbb ) с использованием этого регулярного выражения ( demo ):

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

Мой вопрос: как далеко вы можете пойти? Можно ли также проанализировать контекстно-зависимую грамматику {a n b n c n ; n> 0} (например, aaabbbccc ) с помощью PCRE?

Solutions Collecting From Web of "Сопоставьте a ^ nb ^ nc ^ n (например, «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 и онлайн-пример.

Qtax Trick

Решение, которое не упоминалось:

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

Посмотрите, какие совпадения и неудачи в демо-версии regex .

Это использует группы саморегуляции (идея @Qtax используется для его вертикального регулярного выражения ).