Почему регулярные выражения по умолчанию жадные?
Это также происходит со строками:
>>> s = b = 'somestr'
>>> s == b, s is b, id(s), id(b)
(True, True, 4555519392, 4555519392)
Теперь все кажется прекрасным.
>>> s = 'somestr'
>>> b = 'somestr'
>>> s == b, s is b, id(s), id(b)
(True, True, 4555519392, 4555519392)
Это тоже ожидается.
>>> s1 = b1 = 'somestrdaasd ad ad asd as dasddsg,dlfg ,;dflg, dfg a'
>>> s1 == b1, s1 is b1, id(s1), id(b1)
(True, True, 4555308080, 4555308080)
>>> s1 = 'somestrdaasd ad ad asd as dasddsg,dlfg ,;dflg, dfg a'
>>> b1 = 'somestrdaasd ad ad asd as dasddsg,dlfg ,;dflg, dfg a'
>>> s1 == b1, s1 is b1, id(s1), id(b1)
(True, False, 4555308176, 4555308272)
Теперь это неожиданным.
5 ответов
Истерический Райзенс
Отчасти ответ может касаться происхождения RE в практических вычислениях. Первоначально они были теоретической концепцией из теории автоматов и теории формального языка , пока сам Кен Томпсон не написал реальную реализацию и не использовал их в qed и ed ( 1) .
В исходной версии был только жадный синтаксис, поэтому даже решения не было принято.
Настоящей проблемой здесь является оператор замыкания Клине (звезда); для всего остального в регулярном выражении самое длинное совпадение совпадает с самым коротким.
Когда вы думаете об этом в таких терминах, вы понимаете, что более современные инструменты понимают, что вам нужно и то, и другое. Я поздно встаю, поэтому могу вспомнить только два примера:
И
ksh, иbashпредоставляют "самое длинное соответствие" и "самое короткое соответствие" форм большинства специальных операторов, изменяющих переменные.Регулярные выражения Lua включают
*для самого длинного замыкания Клеена и-для самого короткого замыкания Клеена. Этот вариант всегда кусает меня, когда я забываю убрать буквальный знак-.
Было бы интересно вернуться к оригинальной работе Клине и посмотреть, могло ли это повлиять на ранние инструменты в направлении самого длинного соответствия.
Возможная причина: Механизм regex должен часто возвращаться назад, если он не жадный.
Ну, важно, чтобы компьютеры вели себя предсказуемо, когда это возможно. Поэтому правильное поведение должно следовать простому правилу, например, жадному подбору, чтобы хотя бы опытные программисты могли предсказать результат работы куска кода.
Что касается того, должен ли типичный случай использования быть не жадным, то как насчет следующего: предположим, у меня есть файл с записями типа foo1909, bar3939, baz3331, и я просто хочу извлечь эти числа. Кажется достаточно естественным написать (\d*) в качестве регулярного выражения для этого.
Вы можете сказать, что так же легко написать (\d*)\D или что-то еще, но в основном всегда программист может быть более явным и менее двусмысленным. Поскольку мы хотели получить поведение по умолчанию, которое было бы на 100% предсказуемым и тривиально вычисляемым в голове, это кажется мне разумным.
В случае производительности, ленивые квантификаторы не всегда быстрее из-за отката: http://blog.stevenlevithan.com/archives/greedy-lazy-performance
Что касается дизайна, я не могу сказать, почему квантификаторы по умолчанию жадные, но мне интересно, какой управляющий символ можно было бы использовать, чтобы сделать квантификатор жадным, а не ленивым. Я не думаю, что ? подойдет для этого :-)