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

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

42 голосов
/ 15 сентября 2011

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

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

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

Ответы [ 4 ]

33 голосов
/ 15 сентября 2011

Вдохновленный ответом 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)$~

Это не более чем проверка того, что существует произвольное число a с, за которым следует равное число b с и c с.

Это еще не удовлетворяет нашей грамматике, потому что число a также должно быть одинаковым. Мы можем убедиться в этом, проверив, что число a s равно числу b s. И это то, что делает выражение в утверждении lookahead: (a(?-1)?b)c. c необходим, поэтому мы не совпадаем только с частью b s.

Заключение

Я думаю, что это впечатляюще показывает, что современное регулярное выражение не только способно анализировать нерегулярные грамматики, но даже может анализировать неконтекстно-свободные грамматики. Надеюсь, это положит конец бесконечному попугайству: «Вы не можете делать X с регулярным выражением, потому что X не обычный»

11 голосов
/ 20 сентября 2011

Мой вопрос: как далеко вы можете зайти?

В интересах не создавать код, который является нечитаемой болваной пунктуации, я рискну понизить число голосов и ответитьдругой, хотя и очень связанный вопрос: как далеко должен пройти?

Синтаксические анализаторы регулярных выражений - это блестящий , который нужно иметь вВаш инструментарий, но они не все, и конец всего программирования.* Способность писать синтаксические анализаторы в удобочитаемом виде - также блестящая вещь в вашем наборе инструментов.

Регулярные выражения должны использоваться вплоть до того момента, когда они начнут усложнять ваш код.Понимаю.Кроме того, их ценность в лучшем случае сомнительна, а в худшем - губительна.Для этого конкретного случая, вместо того, чтобы использовать что-то вроде отвратительного: 

~^(?=(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

Это будет далеколегче поддерживать в будущем.Я всегда хотел бы предложить людям, чтобы они считали, что те, кто идет за ними (которые должны поддерживать код, который они пишут), являются психопатами, которые знают, где вы живете - в моем случае, это может быть наполовину верно, японятия не имею, где вы живете: -)

Если у вас нет реальной потребности в регулярных выражениях такого рода (а иногда есть веские причины, такие как производительность в интерпретируемых языках), выследует оптимизировать для читаемость сначала.

10 голосов
/ 15 сентября 2011

Вот альтернативное решение, использующее балансировочные группы с .NET regex: 

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

Не PCRE, но может представлять интерес.

Пример по адресу: http://ideone.com/szhuE

Редактировать : Добавлена ​​недостающая проверка балансировки для группы a и онлайн-пример.

2 голосов
/ 29 июля 2014

Уловка Qtax

Решение, которое не было упомянуто: 

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

Посмотрите, что совпадает и не удается в демонстрация регулярных выражений .

При этом используются группы, ссылающиеся на себя (идея @Qtax используется для его вертикальное регулярное выражение ).

...