Каковы теоретические последствия неограниченного просмотра назад?

Большинство языков допускают просмотр назад с фиксированной или конечной длиной. Заметным исключением является .NET, который позволяет использовать оператор *.

Однако регулярные выражения .NET уже могут распознавать сбалансированные круглые скобки с использованием именованного захвата, который не является обычным языком. Регулярные выражения по-прежнему регулярны с * в ретроспективе? Также приветствуются расширенные ответы на подвыражения, отличные от * (например, дополнительный поиск!).

tl; dr: регулярные ли регулярные выражения с * в ретроспективе?


.net regex regular-language theory finite-automata
person Zachary Vance    schedule 28.07.2010    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Я верю, что ответ здесь: Влияет ли поиск назад на то, какие языки могут быть сопоставлены регулярными выражениями? можно расширить, чтобы доказать, что добавление * в поиске назад (или даже вложение таких просмотров назад и вперед) не влияет на «регулярность» выражений. Хотя я больше не думал об этом.

Надеюсь, это поможет!

person Community    schedule 02.08.2010

arrow_upward
0
arrow_downward

Неограниченный просмотр назад в .NET - это просто усовершенствование и без того нерегулярной функции: фиксированный, конечный или бесконечный просмотр назад не имеет места в обычной грамматике. Так же как и предварительные просмотры, группы захвата, обратные ссылки, неохотные квантификаторы, притяжательные кванторы, атомарные группы, условные выражения, границы слов, якоря ...

Если бы нам пришлось ограничиться теоретически чистыми регулярными выражениями, 99,9% текущих пользователей регулярных выражений не использовали бы их. Спрашивать, является ли функция «обычной», - пустая трата времени; это полезно? Это все, что имеет значение.

person Alan Moore    schedule 29.07.2010
comment
-1 Многие из перечисленных вами функций (в том числе обзор) вполне обычны. Также называть этот вопрос пустой тратой дыхания - это а) грубо и б) неправильно, поскольку регулярность регулярного выражения имеет практические последствия: есть некоторые вещи, которые вы можете делать с регулярными регулярными выражениями, но не можете делать с нерегулярными регулярными выражениями. Например: найдите их пересечение. - person sepp2k; 29.07.2010
comment
Этих функций нет в традиционной формулировке регулярных выражений, но они по-прежнему являются регулярными. Для тех, кто прочитает этот вопрос в более позднее время: Lookaheads (бесконечная длина), неохотные кванторы, притяжательные кванторы, атомарные группы, границы слов и привязки являются регулярными. Группы захвата принципиально не важны. Обратные ссылки для заданных групп захвата нерегулярны. - person Zachary Vance; 29.07.2010

arrow_upward
0
arrow_downward

Регулярные выражения закрываются при пересечении. Добавьте новый символ & и перепишите ретроспективный просмотр назад: A (? ‹B) C как (?: AC &. * BC), и мы получим, что ретроспективный просмотр является обычным.

B может явно включать использование всего, что не выходит за пределы A / C. То есть ничего, кроме просмотра вперед. Что произойдет, если при просмотре назад можно использовать предварительный просмотр или наоборот? Начать работу по. * BC. Ты все еще в порядке.

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

person Zachary Vance    schedule 29.07.2010