Почему в Regexp есть метод тайм-аута, хотя теоретически его быть не должно?

Это теоретический вопрос по информатике (теория вычислений).

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

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

Под RegExps я подразумеваю классы сопоставления шаблонов регулярных выражений на основных языках; JavaScript, С# и т. д.

Являются ли обычные регулярные выражения («регулярные выражения») не эквивалентными регулярным выражениям в теории автоматов (т.е. регулярным языкам)?

См. примеры: Как сделать Я отключаю операции Regex, чтобы предотвратить зависание в .NET 4.5? и Шаблон регулярных выражений Катастрофический возврат .

Если соответствие регулярного выражения требует обратного отслеживания, это означает, что они не эквивалентны регулярным выражениям.

Если языки, захваченные «Regexp», не являются обычными языками, то почему исторически (из какой необходимости) они были расширены?

Если для полученного DFA потребуется огромный набор состояний?


regex dfa regular-language computation-theory
person Sohail Si    schedule 30.08.2019    source источник
comment
Обычно сопоставление выполняется быстро, но в некоторых случаях с определенными регулярными выражениями и длинным вводом это может быть очень медленным.   -  person Barmar    schedule 30.08.2019
comment
Это не дубликат этого вопроса. Это теоретический вопрос.   -  person Sohail Si    schedule 30.08.2019
comment
Тогда ему не место в переполнении стека, посвященном практическим проблемам программирования. Теоретические вопросы относятся к разделу Информатика. Кроме того, математика обычных языков относится к математике.   -  person Barmar    schedule 30.08.2019
comment
Объекты RegExp имеют больше возможностей, чем DFA. Все, что может сделать DFA, — это принять/отклонить. Но объекты RegExp также сообщают о перехватах. Восстановление захватов требует больше работы.   -  person Raymond Chen    schedule 30.08.2019
comment
Восстановление захватов не должно занимать так много времени, как выполняется совпадение (принятие/отклонение).   -  person Sohail Si    schedule 30.08.2019
comment
Я подозреваю две возможные причины: 1. потому что строка может быть любой подстрокой, т.е. когда она не окружена /^ и $/ . 2. Потому что пространство состояний (количество состояний результирующего DFA) может легко стать чрезвычайно большим.   -  person Sohail Si    schedule 30.08.2019
comment
@Barmar Хорошо, но теоретики могут не знать деталей общих (Perl и т. Д.) Классов RegExp.   -  person Sohail Si    schedule 30.08.2019
comment
Этот вопрос связан с: stackoverflow.com/ вопросов/8132412/ Однако он не задает этот вопрос (о различии классов).   -  person Sohail Si    schedule 30.08.2019
comment
Ваш вопрос не о Perl, вы пометили его nsregularexpression из библиотеки Apple, используемой для Objective C и Swift.   -  person Barmar    schedule 30.08.2019
comment
@Barmar Пожалуйста, перечитайте вопрос и снимите с него отметку. Это не имеет ничего общего с перенаправленным вопросом (пример может быть полезен, но он задает другой вопрос).   -  person Sohail Si    schedule 30.08.2019
comment
На самом деле, я не думаю, что тайм-ауты характерны для большинства реализаций регулярных выражений. Насколько я знаю, в PHP или Python нет тайм-аута.   -  person Barmar    schedule 30.08.2019
comment
Но смысл остается, причина, по которой вам нужен тайм-аут, заключается в том, что некоторые регулярные выражения вызывают катастрофический возврат.   -  person Barmar    schedule 30.08.2019
comment
Кроме того, современные регулярные выражения, такие как PCRE, не эквивалентны DFA.   -  person Barmar    schedule 30.08.2019

Ответы (3)


arrow_upward
0
arrow_downward

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

person Bohemian♦    schedule 30.08.2019
comment
Эта ссылка, кажется, объясняет причину, которая является ответом на мой вопрос. Однако в вашем ответе об этом не упоминается. - person Sohail Si; 06.09.2019
comment
Я знаю (и это было упомянуто в вопросе), что это может быть дорого в вычислительном отношении. Я хотел знать, почему, то есть какая особенность RegExps вызывает это, несмотря на то, что они претендуют на роль RE, то есть несмотря на то, что RegExp разделяет свое имя с регулярными выражениями в классической теории вычислений. - person Sohail Si; 06.09.2019

arrow_upward
0
arrow_downward

Поскольку регулярные выражения не эквивалентны регулярным выражениям в теории автоматов.

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

person YOGO    schedule 30.08.2019
comment
Вот такой ответ мне нужен. Однако верно ли приведенное выше утверждение? - person Sohail Si; 06.09.2019
comment
Но какие дополнительные функциональные возможности делают их не-RE (как в теории автоматов)? - person Sohail Si; 06.09.2019
comment
Без этого ответ неполный. - person Sohail Si; 06.09.2019
comment
Правильный ответ взять бумагу или книгу CS. Есть определенные регулярные выражения, которые можно преобразовать, но, например, (A*)B\1, пока я не знаю, нельзя преобразовать в регулярное выражение в теории автоматов. Проверьте этот короткий текст: rexegg.com/regex-vs-regular-expression.html. - person YOGO; 06.09.2019
comment
en.wikipedia.org/wiki/ - person YOGO; 06.09.2019

arrow_upward
-1
arrow_downward

(по какой необходимости) они были расширены?

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

person Kaz    schedule 30.08.2019