Кажется, что это огромный источник путаницы для начинающих, пишущих регулярные выражения, может вызвать скрытые проблемы с производительностью, и, казалось бы, типичный вариант использования не будет жадным.
Это только по устаревшим причинам (так было сначала сделано, и каждая реализация копирует это), или для этого есть причина?
Часть ответа может включать происхождение RE в практических вычислениях. Первоначально они были теоретической концепцией из теории автоматов и теории формального языка до Кен Томпсон сам написал настоящую реализацию и использовал ее в qed и ed( 1).
Первоначальная версия имела только жадный синтаксис, поэтому не было даже решения.
/x*/ может соответствовать или x, или xxx (и т. д.). Такое выражение определяет обычный язык, включающий строки , x и xxx. Обратите внимание, что здесь ничего не говорится о том, как искать совпадения в тексте; только когда вы применяете теорию, вы начинаете заботиться о жадности.
- person Nate C-K; 16.02.2010
В случае производительности ленивые квантификаторы не всегда быстрее из-за поиска с возвратом: http://blog.stevenlevithan.com/archives/greedy-lazy-performance
Что касается фактического дизайна, я, честно говоря, не могу сказать, почему квантификаторы по умолчанию жадные, но мне интересно, какой управляющий символ использовался бы, чтобы сделать квантификатор жадным, а не ленивым. Я не думаю, что ? обрезал бы его :-)
Возможная причина: Механизму регулярных выражений нужно много возвращаться, если он не жадный.
Что ж, важно, чтобы компьютеры вели себя предсказуемо, когда это возможно. Таким образом, правильное поведение должно следовать простому правилу, например, жадному сопоставлению, чтобы, по крайней мере, опытные программисты могли предсказать результат фрагмента кода.
Что касается того, должен ли типичный вариант использования быть нежадным, как насчет следующего: предположим, у меня есть файл с такими записями, как foo1909, bar3939, baz3331, и я просто хочу извлечь эти числа. Кажется достаточно естественным написать (\d*) в качестве регулярного выражения для этого.
Вы можете сказать, что так же просто написать (\d*)\D или что-то еще, но в основном всегда так, что программист может быть более явным и менее двусмысленным. Поскольку мы хотели, чтобы поведение по умолчанию было на 100% предсказуемым и тривиальным для расчета в уме, мне это кажется разумным.
Настоящей проблемой здесь является оператор замыкания Клини (звезда); для всего остального в регулярном выражении самое длинное совпадение совпадает с самым коротким совпадением.
Когда вы думаете об этом в этих терминах, вы понимаете, что более современные инструменты понимают, что вам нужны оба. Я опаздываю, поэтому могу привести только два примера:
И ksh, и bash обеспечивают формы "наибольшего совпадения" и "кратчайшего совпадения" для большинства специальных операторов, изменяющих переменные.
Регулярные выражения Lua включают * для самого длинного совпадения замыкания Клини и - для кратчайшего совпадения замыкания Клини. Это всегда кусает меня, когда я забываю избежать буквального знака -.
Было бы интересно вернуться к оригинальной работе Клини и посмотреть, не повлияло ли это на ранние инструменты на самое длинное совпадение.
/foo|foobar/ и целевую строку blahfoobarblah, математически чистое регулярное выражение всегда будет соответствовать foobar, в то время как регулярное выражение NFA, полученное из Perl, будет соответствовать foo.
- person Alan Moore; 17.02.2010
казалось бы, типичный вариант использования не будет жадным.
Я хочу прояснить, что это неправильно, если только «типичный вариант использования» не означает взлом HTML.
Простой пример — лексические анализаторы для языков программирования. Вы просто не хотите
foo = 42
интерпретируется как 3 переменные, за которыми следует знак равенства, за которым следуют 2 числа. Наоборот, обычно вы ожидаете, что ваш синтаксический анализатор будет рассматривать максимально длинные совпадения.
До появления HTML мы, старшие, десятилетиями жили с жадными регулярными выражениями, и у нас это прекрасно получалось. Даже сегодня я не использую нежадные в 99% случаев, по общему признанию, потому что мне лень смотреть синтаксис, но также и потому, что редко бывают случаи, когда вы не можете просто написать хорошо завершенный жадный. Например, чтобы сопоставить строку:
"(\\"|[^"])*"
/\*((?!\*/).)*\*/. Против /\*.*?\*/. Чем больше вы добавляете разделителей, тем хуже, потому что вам приходится отрицать их все. Жадный работает для большинства случаев использования, потому что эти проблемы возникают нечасто, но утверждение, что это приносит пользу лексическому анализу, или иным образом неверно...
- person TrisT; 21.06.2021
