#regex
#регулярное выражение
Вопрос:
Мне было бы интересно узнать, какие алгоритмы используются для ее сопоставления и как они оптимизированы, потому что я полагаю, что некоторые регулярные выражения могут выдавать огромное количество возможных совпадений, которые могут вызвать серьезные проблемы в плохо отлаженном анализаторе регулярных выражений.
Кроме того, я недавно открыл для себя концепцию ReDoS, почему регулярные выражения, такие как (a|aa) или (a|a?) , вызывают проблемы?
РЕДАКТИРОВАТЬ: Я использовал их больше всего в C # и Python, так что это то, что было у меня в голове, когда я рассматривал вопрос. Я предполагаю, что Python написан на C, как и остальной интерпретатор, но я понятия не имею о C#
Комментарии:
1. Эти регулярные выражения выполняются медленно, потому что им приходится прибегать к обратному отслеживанию AFAIK
2. Можете ли вы добавить еще несколько тегов? О каком языке программирования вы говорите?
3. Пожалуйста, не публикуйте сокращенные URL-адреса без крайней необходимости.
4. Извините, расширение Chrome сделало это автоматически.
5. Статья в Википедии, на которую вы ссылаетесь, точно объясняет, почему эти конкретные регулярные выражения являются проблематичными, в том самом разделе, в котором они перечислены.
Ответ №1:
Я нахожу http://www.regular-expressions.info содержит действительно полезную информацию о регулярных выражениях.
Автор специально рассказывает о катастрофическом использовании регулярных выражений.
Ответ №2:
У Regex Buddy есть эта страница отладки, которая «предлагает вам уникальное представление внутри механизма регулярных выражений».
Комментарии:
1. Я забыл о Regex Buddy, это действительно аккуратная программа.
Ответ №3:
Существует два вида движка регулярных выражений: NFA и DFA. Я довольно устал, поэтому не решаюсь вдаваться в подробности по памяти. Вот страница, которая проходит через алгоритмы. Некоторые анализаторы будут работать лучше с плохо написанными выражениями. Хорошая книга на эту тему (которая стоит у меня на полке) — «Освоение регулярных выражений«.
Комментарии:
1. Это действительно интересное чтение, приветствую. Именно об этом я и думал.
2. На самом деле, у любого конечного автомата не будет проблем с любым регулярным выражением. Проблема заключается в рекурсивном возврате практически в любом движке, начиная с Perl, для обеспечения более продвинутых функций (в основном обратных ссылок). Кстати, статья, на которую вы ссылаетесь, конкретно объясняет это.