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

Question

Предположим, у меня есть язык регулярных выражений, поддерживающий литералы, классы положительных и отрицательных символов, упорядоченное чередование и жадные квантификаторы. ?, *, а также +, (По сути, это подмножество PCRE без обратных ссылок, проверочных утверждений или некоторых других причудливых битов.) Есть ли добавление несжатых кванторов ??, *?, а также +? увеличить выразительную силу этого формализма?

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

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

Answer 1

Когда вы говорите "Regex", вы ссылаетесь на несколько приемов - это не просто проблема основной теории. Рассмотрим вопрос "соответствует ли эта строка моему заданному регулярному выражению?" Для такого вопроса понятие "жадный" - это просто деталь реализации - если вы используете одну из распространенных (но неэффективных) реализаций обратного отслеживания, это может повлиять на производительность, но не на вывод. Точно так же вопрос "содержит ли эта строка совпадение?" не зависит от жадных и не жадных квантификаторов. Этот первый тип регулярных выражений связан с абстрактным понятием принадлежности к множеству: определением языка соответствующих строк.

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

Обычно, когда вы говорите о силе формализма регулярных выражений, вы говорите о первом мире, в котором компьютер отвечает простым да или нет. Об этом легко говорить, потому что спецификация понятна. Когда вы говорите о "жадном" и "не жадном" квантификаторе, вы говорите о "втором мире" - на практике много использовали, но со спецификацией, которая в основном выросла без особого планирования для решения реальных проблем и является стандартом благодаря обратной совместимости, Этот второй мир решает совершенно другие проблемы, и мне не ясно, что здесь означает "выразительная сила". Конечно, нежадный может быть практичным; и это своего рода точка зрения...

Нежадные квантификаторы ничего не делают для первого типа выразительности, и они делают для второго, хотя не совсем понятно, что означает здесь "выразительная сила".