В настоящее время я изучаю проблему регулярных выражений, которые могут выполняться в экспоненциальное время при сопоставлении с определенным вводом, например, как (a*)*, так и (a|a)* потенциально демонстрируют 'катастрофический поиск с возвратом' при сопоставлении со строкой aaaaab — для каждой дополнительной буквы 'a' в совпадающей строке время, необходимое для попытки сопоставления строки, удваивается. Это имеет место только в том случае, если движок использует подход с возвратом / NFA, пытаясь попробовать все возможные ветви в дереве до сбоя, например, используемый в PCRE.
Мой вопрос: почему (a?)* не уязвим? Основываясь на моем понимании возврата, в строке «aaaab» должно происходить то же, что и в случае с (a|a)*. Если мы создадим NFA, используя стандартную конструкцию NFA Томпсона, то, конечно, для каждого эпсилон-перехода машина должна будет продолжать принимать их и возвращаться назад так же, как в случае двух a? Например (опуская некоторые шаги и где @ заменяет эпсилон):
"aaaa" соответствует, но не может соответствовать "b", ошибка (возврат)
"aaaa@" соответствует, ошибка "b" (возврат)
соответствует "aaa@a", ошибка "b" (возврат) )
"aaa@a@" соответствует, "b" не соответствует (возврат)
...
"@a@a@a@a@" соответствует, "b" не соответствует (возврат)
пробовать все возможные комбинации эпсилонов и а, что наверняка приводит к экспоненциальному взрыву маршрутов?
Было бы разумно удалить эпсилон-переходы из NFA, но я считаю, что это приведет к удалению всего недетерминизма из шаблона (a*)*. Это определенно уязвимо, поэтому я не совсем уверен, что происходит!
Заранее большое спасибо!
Редактировать: Qtax указал, что эпсилоны не могут по-прежнему присутствовать, когда NFA проходится с традиционным возвратом, иначе (@)* будет пытаться соответствовать вечно. Итак, какая реализация NFA может привести к тому, что (a*)* и (a|a)* будут экспоненциальными, а (a?)* — нет? Это суть вопроса на самом деле.
(a*)*(т. е. неоптимизированных движках),(a?)*кажется нормальным — почему?! - person Jarmex schedule 27.08.2012a, а затем пустую строку для каждого повторения), тогда регулярное выражение никогда не потерпит неудачу, поскольку вы можете повторять()*неопределенно. - person Qtax schedule 27.08.2012()*. Мне трудно понять, как оптимизируются существующие реализации, чтобы этого не произошло. Очень наивная реализация простого построения NFA с помощью конструкции Томпсона (электронные ходы и все такое), а затем попытка вернуться через нее никогда не завершится по()*причине, которую вы упомянули, так что же они делают, что приводит к успеху(a?)*, но(a*)*терпеть неудачу? Это не может быть так просто, как полное удаление электронных ходов, поскольку я считаю, что это имеет побочный эффект, заставляя(a*)*быть детерминированным. - person Jarmex schedule 27.08.2012^(a*)*$и^(a?)*$. Пример команды (победа):perl -Mre=debug -e "'aaab' =~ /^(a?)*$/"- person Qtax schedule 27.08.2012