регулярные выражения: жадность звёздочки
Модератор: Модераторы разделов
регулярные выражения: жадность звёздочки
Стоп, стоп, стоп я чё-то не понял. Звёздочка же жадный квантификатор. И она должна соответствовать самой длиннющей последовательности предшествующих ей символов ненулевой длины.
Но почему вот так оно выдаёт пустое вхождение в качестве совпадения?
"baaar".match(/a*/) #=> ""
Почему прошлый пример не выдаёт такой же результат?
"baaar".match(/aa*/) #=> "aaa"
И вообще помоему тут какая-то фигня, потому как в следующем примере оно походу тупо находит первое соответствие, а дальше по строке не ищет.
"baaaraaaaka"[/aa*/] #=> "aaa"
Разве регулярки так и должны работать? аааааааа!!
Но почему вот так оно выдаёт пустое вхождение в качестве совпадения?
"baaar".match(/a*/) #=> ""
Почему прошлый пример не выдаёт такой же результат?
"baaar".match(/aa*/) #=> "aaa"
И вообще помоему тут какая-то фигня, потому как в следующем примере оно походу тупо находит первое соответствие, а дальше по строке не ищет.
"baaaraaaaka"[/aa*/] #=> "aaa"
Разве регулярки так и должны работать? аааааааа!!
- drBatty
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
- Контактная информация:
Re: регулярные выражения: жадность звёздочки
jojahti
что это за ЯП?
a* совпадает с ЛЮБЫМ числом символов. В том числе и с пустой строкой. Вот оно и нашла первое совпадение. Что вам не понравилось?
а где написано, что должна искать?
что это за ЯП?
a* совпадает с ЛЮБЫМ числом символов. В том числе и с пустой строкой. Вот оно и нашла первое совпадение. Что вам не понравилось?
а где написано, что должна искать?
- /dev/random
- Администратор
- Сообщения: 5289
- ОС: Gentoo
Re: регулярные выражения: жадность звёздочки
(man 7 regex) писал(а):In the event that an RE could match more than one substring of a given string, the RE matches the one starting earliest in the string. If the RE could match more than one substring starting at that point, it matches the longest.
Перевожу и поясняю. Если регексп можно найти в нескольких местах строки, выбирается самое раннее. И уже из совпадений, начинающихся с этой точки, выбирается самое длинное. Ваш регексп означает "ноль или более символов а", и очевидно, что его можно найти в самом начале строки (ноль любых символов можно найти в любом месте). И уже из совпадений, идущих с самого начала строки, выбирается самое длинное (а оно единственное - пустое).
Re: регулярные выражения: жадность звёздочки
Код: Выделить всё
$ echo br | egrep -o "aa*"
$ echo bar | egrep -o "aa*"
a
$ echo baar | egrep -o "aa*"
aa
$ echo baaar | egrep -o "aa*"
aaa
$ echo baaaaaar | egrep -o "aa*"
aaaaaa
Ненулевая длина, обычно '+' был. '*' - 0 и больше.
UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity. © Dennis Ritchie
The more you believe you don't do mistakes, the more bugs are in your code.
The more you believe you don't do mistakes, the more bugs are in your code.
- drBatty
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
- Контактная информация:
Re: регулярные выражения: жадность звёздочки
/dev/random писал(а): ↑05.04.2011 15:37Если регексп можно найти в нескольких местах строки, выбирается самое раннее. И уже из совпадений, начинающихся с этой точки, выбирается самое длинное.
угу. Хотя на самом дели ничего не выбирается. Просто сохраняется начало и конец совпадения. По умолчанию - первое совпадение. Но вот конец по умолчанию сохраняется последний. Потому получается самое длинное совпадение.
Re: регулярные выражения: жадность звёздочки
Всё понятно, спасибо.
Блин, такой облом, везде кривость, даже в регекспах есть свои подводные камни.
И главное про их ограничения практически нигде не пишут.
Блин, такой облом, везде кривость, даже в регекспах есть свои подводные камни.
И главное про их ограничения практически нигде не пишут.
Re: регулярные выражения: жадность звёздочки
Во-первых, это не баг, это фича ©
Во-вторых, man perlre, искать слово «greedy». Или читать «Mastering regular expressions» («Регулярные выражения»).
- drBatty
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
- Контактная информация:
Re: регулярные выражения: жадность звёздочки
где-ж тут "камни"? В данном случае, вы придумали _как оно должно быть_, а получилось не так... Причина проста - так, как это работает по умолчанию - быстрее всего. Нежадная и/или глобальная звёздочка медленнее жадной и не глобальной.
man 3 regex
там попроще... А уж потом перловка, которая расширяет возможности POSIX-RE.
Re: регулярные выражения: жадность звёздочки
drBatty
Я ожидал что будет красиво, логично и идеально.
Так, а вот с этого места поподробнее пазязя. Можно как-то сделать звёздочку жадной не в рамках самого раннего соответствия а по всему тексту?
P.S. и ещё до кучи, зверинец регекспов хорошо в этой книге описывается
Programming perl 3ed.
где-ж тут "камни"? В данном случае, вы придумали _как оно должно быть_, а получилось не так.
Я ожидал что будет красиво, логично и идеально.
Нежадная и/или глобальная звёздочка медленнее жадной и не глобальной.
Так, а вот с этого места поподробнее пазязя. Можно как-то сделать звёздочку жадной не в рамках самого раннего соответствия а по всему тексту?
P.S. и ещё до кучи, зверинец регекспов хорошо в этой книге описывается
Programming perl 3ed.
- drBatty
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
- Контактная информация:
Re: регулярные выражения: жадность звёздочки
оно так и есть.
в перловке нет разве s///g ? ЕМНИП было.
но это не жадная звёздочка, а глобальная замена по всей строке. Очевидно, что поменять Over9000 совпадений более чем в 9000 раз дольше.
Что касается жадности, то тут ЕМНИП как раз проблема выбора - приходится возвращаться, что-бы найти минимально возможное совпадение. Это приводит иногда к квадратичной зависимости времени от длинны строки. Правда в простых выражениях разницы обычно нет. Беда в том, что
1) не такое уж и простое выражение Ф*? Ибо тут двухбайтовый символ, и на самом деле выражение нужно трактовать так
(0320 0244)*?
что уже не слишком и просто
2) на практике простые регулярки никому не нужны.
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?) Недавно выяснила, что одним из (популярных) доказательств (не)регулярности шаблона/грамматики, является "лемма о накачке. Мне интересно, насколько верно поняла.
Итак, в этой лемме сказано:
Как понимаю, это означает принципиальную допустимость выбирать из текстового образца с помощью атомарного шаблона (выражения) одно любое совпадение из их эквивалентного множества. Т.е. если в строке образца:
abcdecfgc
при поиске одной или нескольких подряд идущих "a", после которой (которых) идет произвольная последовательность символов, после чего идет "с" допустимо принять один из вариантов (заранее, естественно, не известных):
abcdecfgc
abcdec
abc
, то условия поиска удовлетворяют применению регулярных выражений, и грамматика текстового образца может быть регулярной. "Средняя часть y" повторяется в виде эквивалентных подстрок:
bcdecfg
bcde
b
и пустой строки
В противном случае, если например надо найти минимальное вхождение символов после "a" или некое их количество в зависимости от наличия где-нибудь в образце подстроки "dec", или какие-либо иные условия, подразумевающие возврат и повторное наложение шаблона, то такая задача не может решаться с помощью РВ.
?
Итак, в этой лемме сказано:
слово w языка L длины по меньшей мере m, (где m константа, называемая длиной накачки, зависит лишь от L) можно разделить на три подстроки, w=xyz, так что среднюю часть, y (непустую), можно повторить произвольное число раз (включая ноль, то есть удалить) и получить строку из L.
Как понимаю, это означает принципиальную допустимость выбирать из текстового образца с помощью атомарного шаблона (выражения) одно любое совпадение из их эквивалентного множества. Т.е. если в строке образца:
abcdecfgc
при поиске одной или нескольких подряд идущих "a", после которой (которых) идет произвольная последовательность символов, после чего идет "с" допустимо принять один из вариантов (заранее, естественно, не известных):
abcdecfgc
abcdec
abc
, то условия поиска удовлетворяют применению регулярных выражений, и грамматика текстового образца может быть регулярной. "Средняя часть y" повторяется в виде эквивалентных подстрок:
bcdecfg
bcde
b
и пустой строки
В противном случае, если например надо найти минимальное вхождение символов после "a" или некое их количество в зависимости от наличия где-нибудь в образце подстроки "dec", или какие-либо иные условия, подразумевающие возврат и повторное наложение шаблона, то такая задача не может решаться с помощью РВ.
?
Re: регулярные выражения: жадность звёздочки
QWERTYASDF писал(а): ↑28.04.2016 17:15В противном случае, если например надо найти минимальное вхождение символов после "a"
Что-то я не понял, что имелось в виду. Можете подробнее раскрыть? Что значит минимальное вхождение символов после "а"?
QWERTYASDF писал(а): ↑28.04.2016 17:15некое их количество в зависимости от наличия где-нибудь в образце подстроки "dec"
Где должны быть "a", где "dec" и что ищем?
QWERTYASDF писал(а): ↑28.04.2016 17:15или какие-либо иные условия, подразумевающие возврат и повторное наложение шаблона, то такая задача не может решаться с помощью РВ.
Возвраты как раз в регулярках есть, иначе нельзя было бы найти /.*a+c/ в "aaabbbacbbbaaa".
Спасибо сказали:
- Bizdelnick
- Модератор
- Сообщения: 20794
- Статус: nulla salus bello
- ОС: Debian GNU/Linux
Re: регулярные выражения: жадность звёздочки
QWERTYASDF писал(а): ↑28.04.2016 17:15Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?)
Позвольте я не буду комментировать ту упоротость, которой Вы начитались, а отвечу только на этот вопрос, ибо я всё ж таки не теоретик, а практик.
Во-первых, жадность квантификаторов в регулярных выражениях (по крайней мере в большинстве диалектов) отключается.
Во-вторых, правило "левый — длинный" (если я правильно понял, что Вы под этим подразумеваете) работает далеко не во всех реализациях регулярных выражений. POSIX-выражения, например, всегда ищут совпадение максимальной общей длины, даже если самый левый квантификатор будет не максимальным, а вот Perl-выражения действительно прежде всего удовлетворяют жадность самого левого квантификатора, в том числе в ущерб общей длине совпадения:
$
% echo abababbbb | grep -E --color '(ab)*a?(bb)*'
abababbbb
% echo abababbbb | grep -P --color '(ab)*a?(bb)*'
abababbbb
%
Пишите правильно:
в консоли вку́пе (с чем-либо) в общем вообще | в течение (часа) новичок нюанс по умолчанию | приемлемо проблема пробовать трафик |
Спасибо сказали:
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
NickLion
Спасибо за ответ. И извините - более четко сформулировать свой вопрос не могу, ибо в противном случае не нуждалась бы в ответах со стороны ☺
О той жадности, которая показана в Вашем примере, я и не думала..."Жадность" у меня ассоциировалась с "левый-длинный", где под последним подразумевала именно
Жаль, что Вы не пожелали прокомментировать в чем именно я заблуждаюсь в своем понимании и своих примерах регулярности языка/шаблона поиска, ради этого я собственно и обратилась сюда... Ну вот для Вас - чем отличаются "регулярные грамматики" от "нерегулярных"? Есть такие определения в разных вполне не упоротых источниках про регулярные выражения.
Спасибо за ответ. И извините - более четко сформулировать свой вопрос не могу, ибо в противном случае не нуждалась бы в ответах со стороны ☺
Bizdelnick писал(а): ↑28.04.2016 19:08QWERTYASDF писал(а): ↑28.04.2016 17:15Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?)
Позвольте я не буду комментировать ту упоротость, которой Вы начитались, а отвечу только на этот вопрос, ибо я всё ж таки не теоретик, а практик.
Во-первых, жадность квантификаторов в регулярных выражениях (по крайней мере в большинстве диалектов) отключается.
Во-вторых, правило "левый — длинный" (если я правильно понял, что Вы под этим подразумеваете) работает далеко не во всех реализациях регулярных выражений. POSIX-выражения, например, всегда ищут совпадение максимальной общей длины, даже если самый левый квантификатор будет не максимальным, а вот Perl-выражения действительно прежде всего удовлетворяют жадность самого левого квантификатора, в том числе в ущерб общей длине совпадения:$
% echo abababbbb | grep -E --color '(ab)*a?(bb)*' abababbbb % echo abababbbb | grep -P --color '(ab)*a?(bb)*' abababbbb %
О той жадности, которая показана в Вашем примере, я и не думала..."Жадность" у меня ассоциировалась с "левый-длинный", где под последним подразумевала именно
Т.е "стандартные" РВ ставят в больший приоритет именно степень близости к началу строки, а уж потом отбирают самое длинное совпадение:Если регексп можно найти в нескольких местах строки, выбирается самое раннее. И уже из совпадений, начинающихся с этой точки, выбирается самое длинное.
$
$echo abxaabxaaaaa | grep -E --color 'ab(xa)*a'
abxaabxaaaaa
Жаль, что Вы не пожелали прокомментировать в чем именно я заблуждаюсь в своем понимании и своих примерах регулярности языка/шаблона поиска, ради этого я собственно и обратилась сюда... Ну вот для Вас - чем отличаются "регулярные грамматики" от "нерегулярных"? Есть такие определения в разных вполне не упоротых источниках про регулярные выражения.
- Bizdelnick
- Модератор
- Сообщения: 20794
- Статус: nulla salus bello
- ОС: Debian GNU/Linux
Re: регулярные выражения: жадность звёздочки
QWERTYASDF писал(а): ↑29.04.2016 23:38"стандартные" РВ ставят в больший приоритет именно степень близости к началу строки, а уж потом отбирают самое длинное совпадение
POSIX-выражения по определению стандартны, POSIX — это ведь стандарт. Просто разные движки регулярных выражений работают по-разному. Одни (в частности POSIX-совместимые и RE2) идут всегда только вперёд, запоминая по ходу все возможные совпадения; более короткие отбрасываются. Другие, в частности Perl, руководствуются правилом жадности левых квантификаторов, и только если с первого прохода совпадение не находится, возвращаются назад и отбирают у ближайшего (самого правого) квантификатора одно из совпадений (о чём, собственно, писал NickLion, только он не уточнил, что возвраты есть не везде). Если почитать Фридла, то можно узнать страшные аббревиатуры ДКА и НКА и даже их расшифровки, но в стоящую за ними математику он, к счастью, не вникает.
Разумеется, в обоих случаях находится самое левое совпадение.
QWERTYASDF писал(а): ↑29.04.2016 23:38Жаль, что Вы не пожелали прокомментировать в чем именно я заблуждаюсь в своем понимании и своих примерах регулярности языка/шаблона поиска, ради этого я собственно и обратилась сюда...
А Вы заблуждаетесь? Прекращайте в таком случае.
QWERTYASDF писал(а): ↑29.04.2016 23:38Ну вот для Вас - чем отличаются "регулярные грамматики" от "нерегулярных"?
Не знаю. Только вчера в Вашем сообщении прочитал, что есть такие термины. Они правда означают что-то практически ценное?
Пишите правильно:
в консоли вку́пе (с чем-либо) в общем вообще | в течение (часа) новичок нюанс по умолчанию | приемлемо проблема пробовать трафик |
Спасибо сказали:
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
Bizdelnick писал(а): ↑30.04.2016 01:07POSIX-выражения по определению стандартны, POSIX — это ведь стандарт.
Ну вот POSIX и подразумевала, говоря о стандарте.
Bizdelnick писал(а): ↑30.04.2016 01:07Просто разные движки регулярных выражений работают по-разному.
Хорошо, тогда что такое вообще "регулярное выражение"? То, что это язык составления текстового шаблона для поиска некоего текста - очевидно и так. Но если чуть углубиться, то выясняется, что языков-диалектов этих довольно много, и что есть задачи поиска текста, которые решаются только несколькими из них, да еще и с изрядной долей непредсказуемости. Причем про такие задачи пишут, что они вообще не решаются РВ как таковыми, и те подходящие для их решения диалекты - это соответственно не РВ, если строго говорить. Вот мне и захотелось понять все-таки - что такое регулярные выражения.
Bizdelnick писал(а): ↑30.04.2016 01:07Не знаю. Только вчера в Вашем сообщении прочитал, что есть такие термины. Они правда означают что-то практически ценное?
Не знаю. В различных источниках, к которым обращалась по текущему вопросу и ранее по другим вопросам, упоминаются эти термины. Поэтому ухватилась за них, как за ключевые. И еще, мне кажется, что Вы шутите ☺
- /dev/random
- Администратор
- Сообщения: 5289
- ОС: Gentoo
Re: регулярные выражения: жадность звёздочки
QWERTYASDF писал(а): ↑30.04.2016 10:24Хорошо, тогда что такое вообще "регулярное выражение"? То, что это язык составления текстового шаблона для поиска некоего текста - очевидно и так. Но если чуть углубиться, то выясняется, что языков-диалектов этих довольно много, и что есть задачи поиска текста, которые решаются только несколькими из них, да еще и с изрядной долей непредсказуемости. Причем про такие задачи пишут, что они вообще не решаются РВ как таковыми, и те подходящие для их решения диалекты - это соответственно не РВ, если строго говорить. Вот мне и захотелось понять все-таки - что такое регулярные выражения.
Строгое определение регулярных выражений даётся через определение упомянутых вами регулярных грамматик. Но если вы не хотите лезть в математические дебри, то удобнее просто описать, какие возможности ему соответствуют, а какие - нет.
В регулярном выражении допустимы:
* "" - пустая строка, обозначающая саму себя.
* "a" - простой символ, обозначающий сам себя.
* "AB" - конкатенация двух выражений
* "A|B" - два альтернативных друг другу выражения
* "A*" - 0 или более повторений выражения A (в разных повторениях оно может обозначать разный текст)
Все остальные возможности либо являются просто синтаксическим сахаром, сводимым к вышеупомянутым возможностям, либо запрещены в настоящих, соответствующих формальному определению, регулярных выражениях. Например, "[abc]" - то же, что "(a|b|c)", а "A?" - то же, что "(A|)". Это просто синтаксический сахар, и, соответственно, допустимо. А вот, например, обратные ссылки к вышеуказанным возможностям свести нельзя.
Но на практике всё, что выглядит как регулярное выражение и крякает как регулярное выражение, называют уткойрегулярным выражением, даже если формально оно таковым не является.
Спасибо сказали:
- Bizdelnick
- Модератор
- Сообщения: 20794
- Статус: nulla salus bello
- ОС: Debian GNU/Linux
Re: регулярные выражения: жадность звёздочки
Нет, я не шучу.
Какой смысл разбираться, решаются ли определённые задачи с помощью РВ, которые РВ, или с помощью РВ, которые не РВ? Я худо-бедно представляю, как работают те и другие, поэтому для решения конкретной задачи в принципе могу выбрать что-то наиболее подходящее. Только мне этого как правило не приходится делать, потому что, во-первых, выбор доступных инструментов зачастую заранее ограничен (очень редко приходится что-то делать полностью с нуля), во-вторых, при выборе чаще определяющую роль играют другие факторы (поддержка юникода, переносимость и т. п), а в-третьих и главных, если возникают такие сложности с регулярками, скорее всего более эффективным будет решение без их применения.
Какой смысл разбираться, решаются ли определённые задачи с помощью РВ, которые РВ, или с помощью РВ, которые не РВ? Я худо-бедно представляю, как работают те и другие, поэтому для решения конкретной задачи в принципе могу выбрать что-то наиболее подходящее. Только мне этого как правило не приходится делать, потому что, во-первых, выбор доступных инструментов зачастую заранее ограничен (очень редко приходится что-то делать полностью с нуля), во-вторых, при выборе чаще определяющую роль играют другие факторы (поддержка юникода, переносимость и т. п), а в-третьих и главных, если возникают такие сложности с регулярками, скорее всего более эффективным будет решение без их применения.
Пишите правильно:
в консоли вку́пе (с чем-либо) в общем вообще | в течение (часа) новичок нюанс по умолчанию | приемлемо проблема пробовать трафик |
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
Bizdelnick писал(а): ↑30.04.2016 11:54Какой смысл разбираться, решаются ли определённые задачи с помощью РВ, которые РВ, или с помощью РВ, которые не РВ? Я худо-бедно представляю, как работают те и другие, поэтому для решения конкретной задачи в принципе могу выбрать что-то наиболее подходящее.
Вам - не знаю, может для общего развития в свободное от любых других, более приоритетных тем. А мне интересно т.к. я худо-бедно не представляю, но хотелось бы представлять.
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
/dev/random
Т.е. даже POSIX-РВ не соответствуют формальному определению регулярных выражений т.к. имеют фигурные скобки и "+" (частный случай фигурных скобок)?...
Т.е. даже POSIX-РВ не соответствуют формальному определению регулярных выражений т.к. имеют фигурные скобки и "+" (частный случай фигурных скобок)?...
- Bizdelnick
- Модератор
- Сообщения: 20794
- Статус: nulla salus bello
- ОС: Debian GNU/Linux
Re: регулярные выражения: жадность звёздочки
QWERTYASDF
Эквивалент любого квантифакатора можно получить путём повтора выражения и использования ? и *. A+ соответствует AA*, A{2,3} — AAA? и т. п. Так иногда приходится делать, если можно использовать только базовый POSIX-синтаксис (без расширений GNU), хотя сие, конечно, довольно неудобно.
Эквивалент любого квантифакатора можно получить путём повтора выражения и использования ? и *. A+ соответствует AA*, A{2,3} — AAA? и т. п. Так иногда приходится делать, если можно использовать только базовый POSIX-синтаксис (без расширений GNU), хотя сие, конечно, довольно неудобно.
Пишите правильно:
в консоли вку́пе (с чем-либо) в общем вообще | в течение (часа) новичок нюанс по умолчанию | приемлемо проблема пробовать трафик |
Спасибо сказали:
-
- Сообщения: 989
- Статус: Чайник со свистком
- ОС: GNU/Linux
Re: регулярные выражения: жадность звёздочки
Ох, стыдно Действительно...
- /dev/random
- Администратор
- Сообщения: 5289
- ОС: Gentoo
Re: регулярные выражения: жадность звёздочки
QWERTYASDF писал(а): ↑01.05.2016 11:13Т.е. даже POSIX-РВ не соответствуют формальному определению регулярных выражений т.к. имеют фигурные скобки и "+" (частный случай фигурных скобок)?...
Про "{}" и "+" Bizdelnick уже ответил, но следует отметить, что _базовые_ POSIX RE, действительно, не соответствуют определению, из-за присутствия в них обратных ссылок. В _расширенных_ POSIX RE обратных ссылок нет (хотя утилиты GNU добавляют их и туда).
Спасибо сказали: