Сопоставьте a^n b^n c^n (например, "aaabbbcc"), используя регулярные выражения (PCRE)

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

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

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

Author: NikiC, 2011-09-15
Source

4 answers

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

Это не более чем проверка наличия произвольного числа as, за которым следует равное число из bs и cs.

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

Заключение

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

 32
Author: NikiC, 2011-09-19 13:15:37

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

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

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

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

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

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

# 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

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

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

 11
Author: paxdiablo, 2013-03-28 00:55:18

Вот альтернативное решение, использующее балансирующие группы с помощью.СЕТЕВОЕ регулярное выражение:

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

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

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

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

 10
Author: Qtax, 2011-09-15 17:46:21

Трюк с Qtax

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

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

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

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

 2
Author: zx81, 2017-05-23 11:45:39