Сопоставьте a ^ n b ^ n c ^ 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?

Ответы

Ответ 1

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

Объяснение

Если вы рассматриваете регулярное выражение без положительного утверждения lookahead (часть (?=...)), у вас есть следующее:

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

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

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

Заключение

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

Ответ 2

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

В интересах не создания кода, который является нечитаемым болотом пунктуации, я собираюсь рискнуть 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

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

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

Ответ 3

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

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

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

Пример: http://ideone.com/szhuE

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