Истинное могущество регулярных выражений

Как частый посетитель тэга PHP на StackOverflow, я очень часто встречаю вопросы о том, как распарсить какие-то конкретные аспекты HTML, используя регулярные выражения. Самый распространённый ответ на это:

«Ты не можешь парсить HTML с помощью регулярных выражений, потому что HTML не является регулярным. Используй XML парсер, и будет тебе счастье»

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

Что же на самом деле означает «регулярный»?

В контексте теории формальных языков что-то называется «регулярным», когда оно имеет грамматику, в которой любое правило вывода имеет одну из следующих форм:

B -> a
B -> aC
B -> ε

Здесь символ -> можно прочесть как «левая часть может быть заменена правой частью». Т.е. первое правило будет звучать так: "B можно заменить a", второе — "B можно заменить aC", а третье — "B можно заменить пустой строкой" (ε — символ пустой строки).

Но что такое B, C и a? Условлено, что буквами в верхнем регистре обозначают так называемые «нетерминалы» (non-terminals) — символы, которые можно разобрать на составляющие, — а буквами в нижнем регистре обозначают «терминалы» (terminals) — символы, которые нельзя разбить дальше.

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

N -> 0
N -> 1
N -> 2
N -> 3
N -> 4
N -> 5
N -> 6
N -> 7
N -> 8
N -> 9
N -> 0N
N -> 1N
N -> 2N
N -> 3N
N -> 4N
N -> 5N
N -> 6N
N -> 7N
N -> 8N
N -> 9N

Эта грамматика говорит о том, что:

Натуральное число (N) - это
... одна из цифр от 0 до 9
или
... одна из цифр от 0 до 9, за которой следует другое натуральное число (N)

В этом примере цифры от 0 до 9 будут терминалами (поскольку их нельзя разбить на составляющие), а N будет единственным нетерминалом (поскольку его можно разделять дальше).

Если вы ещё раз посмотрите на правила и сравните их с определением регулярных грамматических форм выше, то увидите, что они отвечают заданным критериям: первые десять правил — форме B -> a, а вторые десять — форме B -> aC. Следовательно, грамматика для натуральных чисел — регулярная.

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

И тут на сцену выходят регулярные выражения: грамматика выше эквивалентна регэкспу [0-9]+ (который чертовски проще). И преобразование такого типа можно применить к любой регулярной грамматике: каждая из них имеет соответствующее регулярное выражение, описывающее все допустимые для неё строки.

Что могут описывать регулярные выражения

Итак, возникает закономерный вопрос: регулярные выражения могут описывать только регулярные грамматики, или они способны на большее? Ответом на него будет и да, и нет.

Регулярные выражения в смысле формальных грамматик могут (по определению) описывать только регулярные грамматики и ничего более.

Но когда программисты говорят о «регулярных выражениях», они не подразумевают формальные грамматики. Они говорят о производных регулярных выражениях, реализованных в их языках программирования. И эти реализации регэкспов весьма поверхностно связаны с изначальным понятием регулярности.

Любая современная разновидность регэкспов может описывать гораздо больше, чем просто регулярные языки. Уточнение того, насколько больше, — тема дальнейшего повествования.

Для сохранения простоты, я сфокусируюсь только на PCRE-реализации регэкспов. Просто потому, что я знаю её лучше всего (поскольку она используется в PHP). Множество прочих реализаций весьма с ней схожи, поэтому большую часть нижеизложенного можно применить и к ним тоже.

Иерархия языков

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



Как видите, она делит формальные языки на четыре типа: регулярные языки (тип 3) — наименее мощные, за которыми следуют контекстно-свободные языки (тип 2), контекстно-зависимые языки (тип 1) и, наконец, всемогущие неограниченные языки (тип 0).

Иерархия Хомского — контейнерная, поэтому маленькие коробочки на картинке полностью заключены в большие коробки. Т.е. любой регулярный язык является также контекстно-свободным (но не наоборот!).

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

(Напоминание: когда я говорю «регулярные выражения», я подразумеваю их в программистском смысле, а не в смысле теории формальных языков).

Описание контекстно-свободных языков

Ответ на вопрос выше: да, возможно!

Рассмотрим классический пример контекстно-свободной грамматики {a^n b^n, n>0}, который означает «Число символов a, за которым следует такое же число символов b». (PCRE) регэксп для этого языка будет:

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

Это регулярное выражение очень простое: (?1) ссылается на первую подмаску — (a(?1)?b). Поэтому в принципе можно заменить (?1) подмасками, формируя таким образом рекурсивную зависимость:

/^(a(?1)?b)$/
/^(a(a(?1)?b)?b)$/
/^(a(a(a(?1)?b)?b)?b)$/
/^(a(a(a(a(?1)?b)?b)?b)?b)$/
# and so on

Из приведённых выше соображений должно быть ясно, что это выражение способно описать любую строку с одинаковым количеством a и b.

Следовательно, регулярные выражения способны описывать как минимум некоторые не регулярные, контекстно-свободные грамматики. Но могут ли они описать их все? Чтобы ответить на этот вопрос, посмотрим прежде на определение контекстно-свободных грамматик.

В контекстно-свободной грамматике все правила вывода имеют вид:

A -> β

Здесь A — снова нетерминальный символ, а β — произвольная строка из терминалов и нетерминалов. Таким образом, каждое правило контекстно-свободной грамматики имеет нетерминал в левой части и строку из произвольных символов справа.

В качестве примера рассмотрим следующую грамматику:

function_declaration -> T_FUNCTION is_ref T_STRING '(' parameter_list ')' '{' inner_statement_list '}'

is_ref -> '&'
is_ref -> ε

parameter_list -> non_empty_parameter_list
parameter_list -> ε

non_empty_parameter_list -> parameter
non_empty_parameter_list -> non_empty_parameter_list ',' parameter

// ... ... ...

Это отрывок из PHP-грамматики (всего лишь несколько простых правил). Синтаксис немного отличается от того, что мы использовали раньше, но его можно легко понять. Один из аспектов, который стоит отметить, состоит в том, что имена T_SOMETHING здесь также являются терминальными символами. Такие символы обычно называют токенами, они кодируют собой более абстрактные понятия. Например, T_FUNCTION представляет из себя ключевое слово function, а T_STRING — токен-метка (подобно getUserById или some_other_name).

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

Возвращаясь к актуальному вопросу: так могут ли регулярные выражения связывать все контекстно-свободные грамматики? Снова ответ: да!

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

/
    (?(DEFINE)
        (?<addr_spec> (?&local_part) @ (?&domain) )
        (?<local_part> (?&dot_atom) | (?&quoted_string) | (?&obs_local_part) )
        (?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) )
        (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dtext) )* (?&FWS)? \] (?&CFWS)? )
        (?<dtext> [\x21-\x5a] | [\x5e-\x7e] | (?&obs_dtext) )
        (?<quoted_pair> \\ (?: (?&VCHAR) | (?&WSP) ) | (?&obs_qp) )
        (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)? )
        (?<dot_atom_text> (?&atext) (?: \. (?&atext) )* )
        (?<atext> [a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+ )
        (?<atom> (?&CFWS)? (?&atext) (?&CFWS)? )
        (?<word> (?&atom) | (?&quoted_string) )
        (?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? )
        (?<qcontent> (?&qtext) | (?&quoted_pair) )
        (?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) )

        # comments and whitespace
        (?<FWS> (?: (?&WSP)* \r\n )? (?&WSP)+ | (?&obs_FWS) )
        (?<CFWS> (?: (?&FWS)? (?&comment) )+ (?&FWS)? | (?&FWS) )
        (?<comment> \( (?: (?&FWS)? (?&ccontent) )* (?&FWS)? \) )
        (?<ccontent> (?&ctext) | (?&quoted_pair) | (?&comment) )
        (?<ctext> [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&obs_ctext) )

        # obsolete tokens
        (?<obs_domain> (?&atom) (?: \. (?&atom) )* )
        (?<obs_local_part> (?&word) (?: \. (?&word) )* )
        (?<obs_dtext> (?&obs_NO_WS_CTL) | (?&quoted_pair) )
        (?<obs_qp> \\ (?: \x00 | (?&obs_NO_WS_CTL) | \n | \r ) )
        (?<obs_FWS> (?&WSP)+ (?: \r\n (?&WSP)+ )* )
        (?<obs_ctext> (?&obs_NO_WS_CTL) )
        (?<obs_qtext> (?&obs_NO_WS_CTL) )
        (?<obs_NO_WS_CTL> [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f )

        # character class definitions
        (?<VCHAR> [\x21-\x7E] )
        (?<WSP> [ \t] )
    )
    ^(?&addr_spec)$
/x

То, что вы видите выше — это регулярное выражение для описания e-mail адреса с помощью RFC 5322. Оно построено с помощью простого преобразования БНФ-правил из RFC в нотацию, которую понимает PCRE.

Синтаксис чрезвычайно прост: все определения правил оборачиваются в DEFINE-утверждение, которое в основном означает, что все эти правила не должны непосредственно чему-то соответствовать, их достаточно просто декларировать. Только часть ^(?&addr_spec)$ в самом конце определяет, что же в конце-концов тут описывается.

Определения правил, вообщем-то, не настоящие «правила», а скорее подмаски. В первом примере (a(?1)?b) 1 ссылалась на первую подмаску. Со множеством подмасок такого рода именование непрактично, поэтому им даются понятные имена. Так что (?<xyz> ...) определяет шаблон с именем xyz. (?&xyz) — ссылка на него.

Обратите так же внимание на следующий факт: регулярное выражение выше использует x-модификатор. Он инструктирует движок игнорировать пробелы и придерживаться #-стиля комментариев. Таким образом вы можете лучше отформатировать свой регэксп, чтобы другие люди могли нормально его понять. (В отличии от этого регэкспа RFC 822 для e-mail адреса...)

Таким образом, приведённый выше синтаксис позволяет просто отобразить грамматику на регулярное выражение:

A -> B C
A -> C D
// becomes
(?<A> (?&B) (?&C)
| (?&C) (?&D)
)

Единственная загвоздка в том, что регулярные выражения не поддерживают левостороннюю рекурсию. Т.е., если взять приведённое выше определение списка параметров:

non_empty_parameter_list -> parameter
non_empty_parameter_list -> non_empty_parameter_list ',' parameter

Вы не сможете в точности конвертировать его в основанный на грамматике регэксп. Следующее не сработает:

(?<non_empty_parameter_list>
(?&parameter)
| (?&non_empty_parameter_list) , (?&parameter)
)

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

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

non_empty_parameter_list -> parameter
non_empty_parameter_list -> parameter ',' non_empty_parameter_list

Теперь должно быть абсолютно ясно, что регулярные выражения способны описывать любой контекстно-свободный язык (и, следовательно, почти все языки, с которыми сталкиваются программисты). Единственная проблема: несмотря на то, что регулярные выражения могут описывать контекстно-свободные грамматики, они обычно не могут разбирать их. Разбор подразумевает преобразование какой-либо строки в абстрактное синтаксическое дерево. Для этого невозможно использовать регулярные выражения, по крайней мере PCRE (хотя, конечно, в Perl'e, где есть возможность вставлять произвольный код в регулярное выражение, вы можете практически всё...).

Тем не менее, приведённый выше DEFINE-регэксп оказался очень для меня полезным. В конце концов, обычно вам не нужна полная поддержка парсинга, вы хотите просто описать что-то (например, e-mail адрес) или извлечь небольшие кусочки данных (а не строить целое дерево разбора). Большую часть сложных задач по обработке можно сделать намного проще с использованием грамматик на основе регэкспов :)

А сейчас позвольте мне снова заострить внимание на том, о чём я мимоходом упоминал ранее: синтаксически корректный HTML — контекстно-свободен. Следовательно, вы можете описывать его, используя регулярные выражения, в противовес распространённому мнению. Просто не забывайте о двух вещах: во-первых, большая часть HTML, с которым вы сталкиваетесь, не синтаксически корректная (обычно, она даже не является закрытой). И во-вторых, только то, что вы можете, не означает, что вы должны. Вы можете писать свой софт на Brainfuck, однако существуют причины, почему вы этого не делаете, верно?

Моё мнение по теме таково: где бы вы не нуждались в общей HTML-обработке, используйте DOM-библиотеку на свой вкус. Она правильно обработает некорректный HTML и примет на себя всю тяжесть разбора. С другой стороны, если вы имеете дело со специфическими случаями, то быстрые регулярные выражения часто наилучший выход. И я должен признаться: хотя я обычно говорю людям не разбирать HTML с помощью регулярных выражений, сам я, как известно, делаю это частенько. Просто потому, что часто сталкиваюсь со специфическими ситуациями, когда использовать регэкспы элементарно проще.

Контекстно-зависимые грамматики

Теперь, когда мы подробно рассмотрели контекстно-свободные языки, давайте поднимемся вверх на ещё одну ступеньку в иерархии Хомского: к контекстно-зависимым языкам.

Для них структурные правила будут иметь следующую форму:

αAβ → αγβ

Эта смесь символов поначалу выглядит достаточно сложной, но на самом деле тут всё просто. Ядро по-прежнему представляет собой шаблон A → γ, который мы определили для контекстно-свободных грамматик. К нему просто добавились α и β в обе стороны. Эти двое формируют собой контекст (что также дало имя данному классу грамматик). Итак, A теперь можно заменить на γ только если она имеет α слева и β справа.

Чтобы сделать изложенное более понятным, попробуем интерпретировать следующие правила:

a b A -> a b c
a B c -> a Q H c
H B -> H C

По-русски это будет звучать так:

Заменить `A` на `c`, но только в том случае, если у него имеется `a b` слева.
Заменить `B` на `Q H`, но только в том случае, если у него имеется `a` слева и `c` справа.
Заменить `B` на `C`, но только если у него есть `H` слева.

Контекстно-зависимые языки — это то, что вы редко встретите в «нормальном» программировании. Они более важны в области обработки естественных языков (поскольку естественные языки определённо не являются контекстно-свободными. Слова имеют различное значение в зависимости от контекста). Но даже люди, занимающиеся обработкой естественных языков, работают с так называемыми «мягко контекстно-зависимыми языками», поскольку для моделирования их достаточно, а разбор происходит намного быстрее.

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

У неукорачивающих грамматик каждое правило вывода имеет форму α ->β, где α и β — произвольные строки символов с единственным ограничением: число символов справа должно быть не меньше, чем число символов слева. Формально это выражается формулой |α| <= |β|, где |x| обозначает длину строки символов.

Итак, неукорачивающие грамматики допускают любые правила до тех пор, пока они не начинают укорачивать входную строку. Т.е. A B C -> H Q будет недействительным правилом, поскольку его левая часть содержит три символа, а правая — всего два. Следовательно, это правило будет укорачивающим. С другой стороны, обратное правило H Q -> A B C подойдёт, поскольку у него справа больше символов, чем слева, что удлиняет строку.

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

Чтобы получить понятие, почему обе грамматики имеют одинаковую выразительную силу, посмотрите на следующий пример преобразований:

// неукорачивающая грамматика
A B -> C D
// может быть преобразована в следующую контекстно-зависимую грамматику
A B -> A X
A X -> Y X
Y X -> Y D
Y D -> C D

Ладно, вернёмся к регулярным выражениям. Могут ли они так же описывать и контекстно-зависимые языки?

На этот раз я не смогу вам дать определённого ответа. Конечно, они могут описывать некоторые контекстно-зависимые языки, но я понятия не имею, могут ли они описывать их все.

В качестве примера контекстно-зависимого языка, который можно легко описать, используя регэкспы, возьмём модификацию контекстно-свободного языка {a^n b^n, n>0}, о котором мы говорили выше. Когда вы измените его на {a^n b^n c^n, n>0}, т.е. некоторое количество a предшествует такому же количеству b и c, то он станет контекстно-зависимым.

PCRE-регэксп для этого языка следующий:

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

Если игнорировать утверждение (?=...), то у нас слева останется только a+(b(?-1)?c). Оно проверяет, что за произвольным количеством a следует такое же количество b и c. (?-1) — относительная ссылка на подмаску, означающая «последняя определённая подмаска». В данном случае это (b(?-1)?c).

Новая сущность для нас — это (?=...). Она называется «условное выражение нулевой ширины» и проверяет, что следующий за ним текст описывается маской, но сама проверка осуществляется его подвыражением. Таким образом, происходит проверка на соответствие обоим шаблонам одновременно. Часть a+(b(?-1)?с) проверяет, что количество b и c одинаковое, а (a(?-1)?b)c — что количество a и b одинаковое. Обе маски вместе обеспечивают подтверждение, что все три символа содержатся в одинаковом количестве.

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

αAβ → αγβ

можно преобразовать в следующее DEFINE-правило регэкспов:

(?<A> (?<= α ) γ (?= β ) )

Это тоже самое, что сказать, что A — это γ, но только в том случае, когда она имеет α слева и β справа от себя.

Глядя на вышеизложенное, вы можете подумать, что теперь сможете легко конвертировать контекстно-зависимую грамматику в регулярное выражение, но на самом деле это не так. Причина в том, что ретроспективное утверждение ((?<= ... )) имеет одно существенное ограничение: оно должно быть фиксированной длины. Это означает, что длина текста, описываемого утверждением, должна быть известна заранее. Т.е. вы можете написать (?<= a(bc|cd) ), но вы не можете написать (?<= ab+). В первом случае утверждение связывает точно три символа при любых вариантах и, следовательно, имеет фиксированную длину. Во втором случае утверждение может связать ab, abb, abbbb и т.д. Все они имеют различную длину, и движок не знает, когда ему следует начинать сопоставлять их. Так что они попросту запрещены.

Это серьёзный удар по лёгкости преобразования контекстно-зависимых грамматик в регэкспы. Практически все такие грамматики требуют переменной ширины для ретроспективных утверждений.

Но факт невозможности прямого преобразования контекстно-зависимой грамматики в регэксп сам по себе не означает, что регулярные выражения на могут описывать их все. Например, приведённый выше язык {a^n b^n c^n, n>0} тоже имеет грамматику, которая требует ретроспективного утверждения переменной ширины. Может быть, что-то подобное возможно и для других контекстно-зависимых грамматик. Я честно не знаю.

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

Неограниченные грамматики

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

Мало что можно сказать о неограниченных грамматиках, поскольку они, эээ, неограниченные. Их правила вывода имеют форму α -> β, где α и β — строки символов без ограничений вообще.

Поэтому неограниченные грамматики просто убирают часть «неукорачивающие» из неукорачивающих грамматик. Следовательно, для них A B C -> H Q будет допустимым правилом, хотя ранее оно таковым не являлось.

Насколько в точности сильны неограниченные грамматики? Настолько, что сильнее их не бывает: они Тьюринг-полны. Существует даже «язык программирования», основанный на неограниченных грамматиках: Thue. Поскольку он Тьюринг-полный, то может делать всё, на что способны остальные языки программирования.

Одним из следствий Тьюринг-полноты является то, что проблема проверки на принадлежность определённой строки некоторой грамматике в общем случае неразрешима.

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

Но сейчас, поскольку мы заговорили о Тьюринг-полноте, перейдём к следующему моменту:

Регулярные выражения с обратными ссылками являются NP-полными

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

Т.е. содержащие вот такой очень простой регэксп:

/^(.+)\1$/

(.+) и \1 описывают один и тот же произвольный текст. В общем случае \n означает «что-то там, описываемое n-ой подмаской». Т.е. если (.+) описывает foo, то \1 будет так же описывать foo и ничего более. Следовательно, выражение (.+)\1 означает «некий текст, за которым следует его же копия».

То, что этот регэксп описывает, называется «языком копий» и является ещё одним типичным примером контекстно-зависимых языков.

Аналогичным образом вы можете описать с помощью обратных ссылок прочие примеры грамматик, приведённые выше:

# {a^n b^n, n>0} (context-free)
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
# {a^n b^n c^n, n>0} (context-sensitive)
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x

Объяснение того, как это работает, выходит за рамки данной статьи, но вы можете прочитать об этом прекрасный топик на StackOverflow.

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

Что означает «NP-полная»? NP-полнота — это один из классов в теории сложности вычислений для решения задач, в который впадают многие «тяжёлые» проблемы. Примерами NP-полных задач являются задача коммивояжера (TSP), задача выполнимости булевых формул (SAT) и задача о ранце (BKP).

Другое важное условие для того, чтобы называть задачу NP-полной, это возможность свести к ней любую другую NP-задачу. Таким образом, все NP-полные задачи в основном взаимозаменяемы. Если найдёте быстрое решение одной из них, то вы будете иметь быстрое решение для них всех.

Так что если кто-то найдёт быстрое решение для NP-полной задачи, то практически все сложные вычислительные задачи человечества будут решены одним махом. Что, как мы знаем, будет означать конец цивилизации.

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

3-CNF SAT расшифровывается как «Задача выполнимости булевых формул в 3-конъюнктивной нормальной форме» и достаточно проста для понимания. Имеется булева формула следующего вида:

(!$a || $b || $d)
&& ( $a || !$c || $d)
&& ( $a || !$b || !$d)
&& ( $b || !$c || !$d)
&& (!$a || $c || !$d)
&& ( $a || $b || $c)
&& (!$a || !$b || !$c)

Она состоит из ряда условий, разделённых операторами И. Каждое из этих условий состоит из трёх переменных (или их отрицаний), разделённых операторами ИЛИ. 3-CNF SAT спрашивает: существует ли решение у этой булевой формулы (например, истина)?

Приведённую выше булеву формулу можно преобразовать в следующее регулярное выражение:

<?php
$regex = '/^
    (x?)(x?)(x?)(x?) .* ;
    (?: x\1 | \2  | \4  ),
    (?: \1  | x\3 | \4  ),
    (?: \1  | x\2 | x\4 ),
    (?: \2  | x\3 | x\4 ),
    (?: x\1 | \3  | x\4 ),
    (?: \1  | \2  | \3  ),
    (?: x\1 | x\2 | x\3 ),
$/x';
$string = 'xxxx;x,x,x,x,x,x,x,';
var_dump(preg_match($regex, $string, $matches));
var_dump($matches);

Если вы запустите этот код, то получите следующий результат $matches:

array(5) {
[0]=> string(19) "xxxx;x,x,x,x,x,x,x,"
[1]=> string(1) "x"
[2]=> string(1) "x"
[3]=> string(0) ""
[4]=> string(0) ""
}

Это означает, что приведённая выше формула выполняется, если $a = true, $b = true, $c = false и $d = false.

Регулярное выражение использует очень простой трюк: для любых трёх условий строка содержит x, который должен быть описан. Так что если у вас есть что-то вроде (?: \1 | x\3 | \4 ) в регэкспе, то строка может быть описана только если \1 — это x (истина), или \3 — пустая строка (ложь), или \4 — это x (истина).

Теперь дело за движком. Он проверяет различные пути для связывания строки до тех пор, пока или решение не будет найдено, или он не сдастся.

Подводя итог

Поскольку статья получилась несколько длинноватой, то вот краткое изложение основных пунктов:

• Регулярные выражения, используемые программистами, имеют очень мало общего с оригинальным понятием регулярности в контексте теории формальных языков.
• Регулярные выражения (как минимум PCRE) могут описывать все контекстно-свободные языки. В том числе и синтаксически корректный HTML, и вообще практически все прочие языки программирования.
• Регулярные выражения способны описывать как минимум некоторые контекстно-зависимые языки.
• Описание регулярными выражениями NP полно. Так что вы можете решить любую другую NP задачу, используя регулярные выражения.

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

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

Вот и всё.

От переводчика: возможные замечания по поводу перевода, пожалуйста, пишите в личку. Я буду за них очень признательна.