Что НЕ может быть описано регулярным выражением PCRE?

Question

Что НЕ может быть описано регулярным выражением PCRE?

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

Первый пример, который мне пришёл в голову, — это соответствие строки вроде XOOXXXOOOOXXXXX..., Это будет строка, состоящая из чередующейся последовательности Xи Oгде каждая часть состоит только из символа X или же O длиннее, чем предыдущая последовательность другого символа.

Кто-нибудь может объяснить, каков формальный предел регулярного выражения? Я знаю, что это может быть довольно академический вопрос, но я любопытный человек 😉

редактировать
Поскольку я являюсь php-парнем, меня особенно интересует регулярное выражение, описываемое стандартом PCRE, как описано здесь: http://php.net/manual/en/reference.pcre.pattern.syntax.php
Я знаю, что PCRE допускает много вещей, которые не являются частью оригинальных регулярных выражений, таких как обратные ссылки.

Представление о сбалансированных скобках, кажется, является одним из примеров, который не может быть сопоставлен с регулярными выражениями в целом, но это Можно сопоставить с помощью PCRE (см. http://sandbox.onlinephpfunctions.com/code/fd12b580bb9ad7a19e226219d5146322a41c6e47 для живого примера):

$data = array('()', '(())', ')(', '(((()', '(((((((((())))))))))', '()()');
$regex = '/^((?:[^()]|\((?1)\))*+)$/';

foreach($data as $d) {
echo "$d matched by regex: " . (preg_match($regex, $d) ? 'yes' : 'no') . "\n";
}

1

computation-theory pcre php regex

Решение

Другие решения

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

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

Другим хорошим примером языка без контекста является HTML.

1

Источник

Accepted Answer

Первый пример, который мне пришёл в голову, — это соответствие строки вроде XOOXXXOOOOXXXXX..., Это будет строка, состоящая из чередующейся последовательности Xи Oгде каждая часть состоит только из символа X или же O длиннее, чем предыдущая последовательность другого символа.

Да, это можно сделать.

Чтобы сопоставить непустую последовательность х, за которой следует большее число о, мы можем использовать подход, аналогичный подходу регулярных выражений в сбалансированных скобках:
```
(x(?1)?o)o+
```
Чтобы сопоставить строку х и о, такую, что за любой последовательностью х следует более длинная последовательность о (за исключением, возможно, в самом конце), мы можем опираться на шаблон № 1:
```
^o*(?:(x(?1)?o)o+)*x*$
```
И, конечно же, нам также понадобится вариант шаблона № 2 с перевернутыми буквами x и o:
```
^x*(?:(o(?1)?x)x+)*o*$
```
Чтобы сопоставить строку х и о, которые удовлетворяют обоим вышеприведенным критериям, мы можем преобразовать шаблон № 2 в положительное предварительное утверждение и изменить нумерацию группы захвата в шаблоне № 3:
```
^(?=o*(?:(x(?1)?o)o+)*x*$)x*(?:(o(?2)?x)x+)*o*$
```

Что касается основного вопроса. , , Я уверен, что PCRE может соответствовать любому языку без контекста, так как поддержка (?n) вне из Nth-группа захвата означает, что вы можете в основном создать подпрограмму для каждого из ваших нетерминалов. Например, эта контекстно-свободная грамматика:

S → ATB
S → ε
T → CSD
T → EtF

можно записать как:

группа захвата № 1 (S) → (a(?2)b|)
группа захвата № 2 (T) → (c(?1)d|e(?2)f)

Чтобы собрать это в одно регулярное выражение, мы можем просто объединить их все, но добавив {0} ведь кроме начала нетерминально, а потом добавить ^ а также $:

^(a(?2)b|)(c(?1)d|e(?2)f){0}$

Но, как вы видели из своего первого примера, PCRE также могут соответствовать неконтекстно-свободным языкам. (Другой пример ^Nб^Nс^N, который является классическим примером неконтекстно-свободного языка. Вы можете сопоставить его с PCRE, комбинируя PCRE для ^Nб^Nс^м с PCRE для ^мб^Nс^N используя перспективное утверждение. Хотя пересечение двух регулярных языков обязательно является регулярным, пересечение двух контекстно-свободных языков не обязательно без контекста; но пересечение языков, определенных двумя PCRE Можно быть определенным PCRE.)

3