Почему регулярные выражения по умолчанию жадные?

Question

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

Это просто по унаследованным причинам (это было так, как это было сначала, и каждая реализация копирует это), или есть причина для этого?

Answer 1

Истерические изюминки

---

Часть ответа может касаться происхождения RE в практических вычислениях. Первоначально они были теоретической концепцией от теории автоматов и теории формального языка до Сам Кен Томпсон написал реальную реализацию и использовал их в qed и ed 1) .

Оригинальная версия имела только жадный синтаксис, и поэтому не было даже решения принять.

Answer 2

В случае производительности ленивые квантификаторы не всегда быстрее из-за возврата: http://blog.stevenlevithan.com/archives/greedy-lazy-performance

Что касается фактического дизайна, я, честно говоря, не могу сказать, почему квантификаторы являются жадными по умолчанию, но мне интересно, какой управляющий символ был бы использован для того, чтобы сделать квантификатор жадным, а не ленивым. Я не думаю, что ? сократил бы это: -)

Answer 3

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

Answer 4

Настоящая проблема здесь - оператор замыкания Клини (звезда); для всего остального в регулярном выражении самое длинное совпадение совпадает с самым коротким совпадением.

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

• И ksh, и bash предоставляют формы "наибольшее совпадение" и"кратчайшее совпадение" большинства специальных операторов изменения переменных.

• Регулярные выражения Lua включают * для наибольшего совпадения замыкания Клини и - для кратчайшего совпадения замыкания Клини. Этот всегда кусает меня, когда я забываю избежать буквального знака -.

Было бы интересно вернуться к первоначальной работе Клини и посмотреть, не повлияло ли это на ранние инструменты для достижения наибольшего совпадения.

Answer 5

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

Что касается того, должен ли типичный вариант использования быть нежадным, как насчет следующего: предположим, у меня есть файл с записями, такими как foo1909, bar3939, baz3331, и я просто хочу извлечь эти числа. Кажется достаточно естественным написать (\ d *) как регулярное выражение для этого.

Вы можете сказать, что это так же легко написать (\ d *) \ D или что-то еще, но в основном всегда так, что программист может быть более явным и менее двусмысленным. Поскольку мы хотели, чтобы поведение по умолчанию было предсказуемым на 100% и тривиальным для вычисления по голове, мне кажется разумным.

Answer 6

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

Я хочу пояснить, что это неправильно, если «типичный вариант использования» не означает HTML-хакерство.

Простой пример - лексические анализаторы для языков программирования. Вы просто не хотите

foo = 42

интерпретируется как 3 переменные, за которыми следует знак равенства, за которым следуют 2 числа. Напротив, , как правило, , вы ожидаете, что ваш синтаксический анализатор рассмотрит максимально длинные совпадения.

До появления HTML мы, старшие, десятилетиями жили с жадными регулярными выражениями, и у нас все было хорошо. Даже сегодня я не использую не жадные в 99% всех случаев, по общему признанию, потому что я слишком ленив, чтобы искать синтаксис, но также и потому, что редко бывают случаи, когда нельзя просто написать хорошо завершенный жадный. Например, чтобы соответствовать строке:

"(\\"|[^"])*"