Не являются ли регулярные регулярные выражения регулярными выражениями?

Question

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

Какие особенности современных регулярных выражений не являются регулярными? Примеры были бы полезны.

Answer 1

Первое, что приходит на ум обратные_связи:

(\w*)\s\1 

(соответствует группе символов слова, за которым следует пробел, а затем та же группа ранее совпадающая) например: hello hello матчи, hello world Безразлично» т.

Эта конструкция не является регулярной (то есть: не может быть сгенерирована regular grammar).

---

Еще одна особенность поддерживается Perl Compatible RegExp (PCRE), которая не является регулярным рекурсивные модели:

\((a*|(?R))*\) 

Это может быть использовано, чтобы соответствовать любой комбинации сбалансированных скобок и «а» с (от wikipedia))

Answer 2

Детерминированный или недетерминированный конечный автомат распознает только регулярные языки, которые описываются регулярными выражениями. Определение регулярного выражения прост. Пусть S быть алфавитом. Затем пустое множество, пустая строка и каждый элемент S являются регулярными выражениями (более S). Пусть u и v являются регулярными выражениями. Тогда объединение (у | v), конкатенация (уф) и закрытие (у *) из у и v являются регулярными выражениями над S. Это определение легко распространяется на регулярные языки. Никакое другое выражение не является регулярным выражением. Как отмечалось, некоторые обратные ссылки являются примером. Страницы Википедии на регулярных языках и выражениях являются хорошими ссылками.

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

{а^я Ь^I: я < = 0}

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

Answer 3

Несколько примеров:

• Регулярные выражения поддержки группировки. Например. в Ruby: /my (group)/.match("my group")[1] выведет «группу». для хранения чего-либо в группе требуется внешнее хранилище, которого нет у конечного автомата.
• Многие языки, например. C#, захват поддержки, т. Е. Что каждое совпадение будет записано в стеке - например, шаблон (?<MYGROUP>.)* может выполнять несколько захватов «.». в той же группе.
• Группировка используется для обратного вызова, как указано пользователем NullUserException выше. Для обратного реферирования требуется один или несколько внешних стеков с силой push-down-automaton (вы должны иметь возможность нажимать что-то на стек и заглядывать или всплывать после этого.
• Некоторые двигатели имеют возможность отдельного нажатия и выталкивания внешнего стеки и проверка того, пуст ли пуст. В .NET на самом деле (?<MYGROUP>test) толкает стек, а (?<-MYGROUP>) создает стек.
• Некоторые двигатели, такие как движок .NET, имеют сбалансированную концепцию группировки, где внешний стек может быть как нажат, так и выставляется одновременно. Сбалансированный синтаксис группировки - (?<FIRSTGROUP-LASTGROUP>), который выталкивает LASTGROUP и выталкивает захват с индекса LASTGROUP в стек FIRSTGROUP. Фактически это можно использовать для сопоставления бесконечно вложенных конструкций, которые, безусловно, выходят за пределы конечного автомата п. существуют

Возможно другие хорошие примеры :-) Если вы дополнительно interessted в некоторых деталях реализации внешних стеков в сочетании с Regex-х и сбалансированной группировки и, следовательно, более высокого порядка, чем автоматов конечных автоматов, я однажды написал две короткие статьи на этом (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx и http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

Во всяком случае - finitieness или нет - я blieve что сила, этот дополнительный материал приносит регулярных языков велик :-)

Br. Morten