Regex ведет себя лениво, должно быть жадным

Я думал, что по умолчанию мой Regex будет демонстрировать нужное мне жадное поведение, но в следующем коде этого нет:

 Regex keywords = new Regex(@"in|int|into|internal|interface");
 var targets = keywords.ToString().Split('|');
 foreach (string t in targets)
    {
    Match match = keywords.Match(t);
    Console.WriteLine("Matched {0,-9} with {1}", t, match.Value);
    }

Выход:

Matched in        with in
Matched int       with in
Matched into      with in
Matched internal  with in
Matched interface with in

Теперь я понимаю, что мог бы заставить его работать для этого небольшого примера, если бы просто отсортировал ключевые слова по длине по убыванию, но

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

Итак, мой вопрос: почему это лень и как мне это исправить?


regex greedy regex-greedy non-greedy alternation
person Stomp    schedule 07.03.2010    source источник
comment
Я не уверен, что ваше фактическое использование более сложное, но если приведенный выше пример на самом деле то, что вы делаете, я думаю, вам было бы в тысячу раз лучше перебирать список слов в поисках совпадений с помощью метода IndexOf. Если регулярное выражение просто содержит кучу слов в чередовании, производительность, вероятно, будет отстойной.   -  person Josh    schedule 07.03.2010
comment
@Josh - Нет, пример упрощен. Фактическое приложение читает языковые файлы для создания лексеров и парсеров грамматики. Я просто немного заржавел в своих регулярных выражениях; моя проблема кажется такой очевидной сейчас!   -  person Stomp    schedule 07.03.2010
comment
@Josh: Механизмы регулярных выражений могут выполнять множество оптимизаций для таких случаев, включая отбрасывание многих проверок после несоответствия общему префиксу. Например, если первый символ не i, ни одна из ветвей, начинающихся с i, не будет проверена. Не уверен, что движок .NET делает это, но я был бы удивлен, если бы это было не так.   -  person Max Shawabkeh    schedule 07.03.2010
comment
@Max, он создает переходы состояний, чтобы ускорить его сопоставление. Если .Net хорошо сравнивается с другими давно зарекомендовавшими себя и хорошо усовершенствованными механизмами регулярных выражений, это предмет споров из того, что я собрал. Но он действительно работает лучше, чем IndexOf. (Я запускал оба цикла на работе, чтобы доказать, почему коллеги должны использовать регулярное выражение вместо IndexOf... в зависимости от того, что сопоставляется, вы можете получить порядки увеличения скорости.)   -  person Jason D    schedule 07.03.2010

Ответы (3)


arrow_upward
12
arrow_downward

Ленивость и жадность относятся только к квантификаторам (?, *, +, {min,max}). Чередования всегда совпадают по порядку и пробуют первое возможное совпадение.

person Max Shawabkeh    schedule 07.03.2010
comment
Нет вариантов, кроме повторного заказа? Хммм... Думаю, я мог бы изменить порядок на лету, чтобы сохранить определение в алфавитном порядке... - person Stomp; 07.03.2010
comment
@Stomp: Да, это можно сделать. Держите список в программе в алфавитном порядке, и непосредственно перед его применением вы можете отсортировать его по длине. - person codaddict; 07.03.2010

arrow_upward
6
arrow_downward

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

new Regex(@"\b(in|int|into|internal|interface)\b");

"\b" говорит о соответствии границам слов и соответствует нулевой ширине. Это поведение зависит от локали, но в целом это означает наличие пробелов и пунктуации. Будучи совпадением нулевой ширины, оно не будет содержать символ, из-за которого механизм регулярных выражений обнаружил границу слова.

person Jason D    schedule 07.03.2010
comment
Добавление \b вызовет желаемое поведение, но вы ошибаетесь в том, как это работает. \b — это утверждение нулевой ширины, такое как ^, $ и обходные пути; вместо соответствия символу он соответствует воображаемому промежутку до или после символа. Начало или конец строки автоматически является границей слова, если первый или последний символ (соответственно) является символом слова, поэтому ваше второе регулярное выражение является просто более подробной версией первого. - person Alan Moore; 07.03.2010
comment
@ Алан, я попытался выполнить код, и ты явно прав. Мне нужно дважды проверить код на работе, чтобы увидеть, что мы там делаем... Возможно, мы используем \W, а не \b. Я знаю, что мы получали какие-то символы, не являющиеся словами, в похожей ситуации, когда я знаю, что у нас были какие-то причудливые группы для захвата полудня. Что касается чувствительности к локали, это будет иметь место, поскольку границы слов будут определяться по-разному в зависимости от роли знаков препинания. - person Jason D; 07.03.2010
comment
@ Алан, я изменил свой ответ, чтобы отразить ваши отзывы. - person Jason D; 07.03.2010

arrow_upward
3
arrow_downward

Согласно RegularExpressions.info, регулярными выражениями являются нетерпеливый. Таким образом, когда он проходит через ваше выражение, он останавливается на первом достоверном совпадении.

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

person Jeras    schedule 07.03.2010
comment
@Jeras - Спасибо за ссылки! Я искал в MSDN и, должно быть, пропустил, что он с нетерпением искал первое совпадение. - person Stomp; 07.03.2010