регулярные выражения: жадность звёздочки

[jojahti]

Стоп, стоп, стоп я чё-то не понял. Звёздочка же жадный квантификатор. И она должна соответствовать самой длиннющей последовательности предшествующих ей символов ненулевой длины.

Но почему вот так оно выдаёт пустое вхождение в качестве совпадения?
"baaar".match(/a*/) #=> ""

Почему прошлый пример не выдаёт такой же результат?
"baaar".match(/aa*/) #=> "aaa"

И вообще помоему тут какая-то фигня, потому как в следующем примере оно походу тупо находит первое соответствие, а дальше по строке не ищет.
"baaaraaaaka"[/aa*/] #=> "aaa"

Разве регулярки так и должны работать? аааааааа!!

[drBatty]

jojahti
что это за ЯП?

Но почему вот так оно выдаёт пустое вхождение в качестве совпадения?
"baaar".match(/a*/) #=> ""

a* совпадает с ЛЮБЫМ числом символов. В том числе и с пустой строкой. Вот оно и нашла первое совпадение. Что вам не понравилось?

И вообще помоему тут какая-то фигня, потому как в следующем примере оно походу тупо находит первое соответствие, а дальше по строке не ищет.

а где написано, что должна искать?

[/dev/random]

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.

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

[SLEDopit]

Код: Выделить всё

 $ 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 и больше.

[drBatty]

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

угу. Хотя на самом дели ничего не выбирается. Просто сохраняется начало и конец совпадения. По умолчанию - первое совпадение. Но вот конец по умолчанию сохраняется последний. Потому получается самое длинное совпадение.

[jojahti]

Всё понятно, спасибо.
Блин, такой облом, везде кривость, даже в регекспах есть свои подводные камни.

И главное про их ограничения практически нигде не пишут.

[.Serj.]

Всё понятно, спасибо.
Блин, такой облом, везде кривость, даже в регекспах есть свои подводные камни.

И главное про их ограничения практически нигде не пишут.

Во-первых, это не баг, это фича ©

Во-вторых, man perlre, искать слово «greedy». Или читать «Mastering regular expressions» («Регулярные выражения»).

[drBatty]

Блин, такой облом, везде кривость, даже в регекспах есть свои подводные камни.

где-ж тут "камни"? В данном случае, вы придумали _как оно должно быть_, а получилось не так... Причина проста - так, как это работает по умолчанию - быстрее всего. Нежадная и/или глобальная звёздочка медленнее жадной и не глобальной.

Во-вторых, man perlre

man 3 regex
там попроще... А уж потом перловка, которая расширяет возможности POSIX-RE.

[jojahti]

drBatty

где-ж тут "камни"? В данном случае, вы придумали _как оно должно быть_, а получилось не так.

Я ожидал что будет красиво, логично и идеально.

Нежадная и/или глобальная звёздочка медленнее жадной и не глобальной.

Так, а вот с этого места поподробнее пазязя. Можно как-то сделать звёздочку жадной не в рамках самого раннего соответствия а по всему тексту?

P.S. и ещё до кучи, зверинец регекспов хорошо в этой книге описывается
Programming perl 3ed.

[drBatty]

Я ожидал что будет красиво, логично и идеально.

оно так и есть.

Так, а вот с этого места поподробнее пазязя. Можно как-то сделать звёздочку жадной не в рамках самого раннего соответствия а по всему тексту?

в перловке нет разве s///g ? ЕМНИП было.
но это не жадная звёздочка, а глобальная замена по всей строке. Очевидно, что поменять Over9000 совпадений более чем в 9000 раз дольше.

Что касается жадности, то тут ЕМНИП как раз проблема выбора - приходится возвращаться, что-бы найти минимально возможное совпадение. Это приводит иногда к квадратичной зависимости времени от длинны строки. Правда в простых выражениях разницы обычно нет. Беда в том, что
1) не такое уж и простое выражение Ф*? Ибо тут двухбайтовый символ, и на самом деле выражение нужно трактовать так
(0320 0244)*?
что уже не слишком и просто
2) на практике простые регулярки никому не нужны.

[QWERTYASDF]

Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?) Недавно выяснила, что одним из (популярных) доказательств (не)регулярности шаблона/грамматики, является "лемма о накачке. Мне интересно, насколько верно поняла.

Итак, в этой лемме сказано:

слово w языка L длины по меньшей мере m, (где m константа, называемая длиной накачки, зависит лишь от L) можно разделить на три подстроки, w=xyz, так что среднюю часть, y (непустую), можно повторить произвольное число раз (включая ноль, то есть удалить) и получить строку из L.

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

abcdecfgc

при поиске одной или нескольких подряд идущих "a", после которой (которых) идет произвольная последовательность символов, после чего идет "с" допустимо принять один из вариантов (заранее, естественно, не известных):

abcdecfgc
abcdec
abc

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

bcdecfg
bcde
b
и пустой строки

В противном случае, если например надо найти минимальное вхождение символов после "a" или некое их количество в зависимости от наличия где-нибудь в образце подстроки "dec", или какие-либо иные условия, подразумевающие возврат и повторное наложение шаблона, то такая задача не может решаться с помощью РВ.

?

[NickLion]

В противном случае, если например надо найти минимальное вхождение символов после "a"

Что-то я не понял, что имелось в виду. Можете подробнее раскрыть? Что значит минимальное вхождение символов после "а"?

некое их количество в зависимости от наличия где-нибудь в образце подстроки "dec"

Где должны быть "a", где "dec" и что ищем?

или какие-либо иные условия, подразумевающие возврат и повторное наложение шаблона, то такая задача не может решаться с помощью РВ.

Возвраты как раз в регулярках есть, иначе нельзя было бы найти /.*a+c/ в "aaabbbacbbbaaa".

[Bizdelnick]

Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?)

Позвольте я не буду комментировать ту упоротость, которой Вы начитались, а отвечу только на этот вопрос, ибо я всё ж таки не теоретик, а практик.
Во-первых, жадность квантификаторов в регулярных выражениях (по крайней мере в большинстве диалектов) отключается.
Во-вторых, правило "левый — длинный" (если я правильно понял, что Вы под этим подразумеваете) работает далеко не во всех реализациях регулярных выражений. POSIX-выражения, например, всегда ищут совпадение максимальной общей длины, даже если самый левый квантификатор будет не максимальным, а вот Perl-выражения действительно прежде всего удовлетворяют жадность самого левого квантификатора, в том числе в ущерб общей длине совпадения:

$

% echo abababbbb | grep -E --color '(ab)*a?(bb)*' abababbbb % echo abababbbb | grep -P --color '(ab)*a?(bb)*' abababbbb %

[QWERTYASDF]

NickLion

Спасибо за ответ. И извините - более четко сформулировать свой вопрос не могу, ибо в противном случае не нуждалась бы в ответах со стороны ☺

Афаик, "жадность" и правило "левый-длинный" являются ключевыми отличительными свойствами РВ (?)

Позвольте я не буду комментировать ту упоротость, которой Вы начитались, а отвечу только на этот вопрос, ибо я всё ж таки не теоретик, а практик.
Во-первых, жадность квантификаторов в регулярных выражениях (по крайней мере в большинстве диалектов) отключается.
Во-вторых, правило "левый — длинный" (если я правильно понял, что Вы под этим подразумеваете) работает далеко не во всех реализациях регулярных выражений. 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]

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

POSIX-выражения по определению стандартны, POSIX — это ведь стандарт. Просто разные движки регулярных выражений работают по-разному. Одни (в частности POSIX-совместимые и RE2) идут всегда только вперёд, запоминая по ходу все возможные совпадения; более короткие отбрасываются. Другие, в частности Perl, руководствуются правилом жадности левых квантификаторов, и только если с первого прохода совпадение не находится, возвращаются назад и отбирают у ближайшего (самого правого) квантификатора одно из совпадений (о чём, собственно, писал NickLion, только он не уточнил, что возвраты есть не везде). Если почитать Фридла, то можно узнать страшные аббревиатуры ДКА и НКА и даже их расшифровки, но в стоящую за ними математику он, к счастью, не вникает.
Разумеется, в обоих случаях находится самое левое совпадение.

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

А Вы заблуждаетесь? Прекращайте в таком случае.

Ну вот для Вас - чем отличаются "регулярные грамматики" от "нерегулярных"?

Не знаю. Только вчера в Вашем сообщении прочитал, что есть такие термины. Они правда означают что-то практически ценное?

[QWERTYASDF]

POSIX-выражения по определению стандартны, POSIX — это ведь стандарт.

Ну вот POSIX и подразумевала, говоря о стандарте.

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

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

Не знаю. Только вчера в Вашем сообщении прочитал, что есть такие термины. Они правда означают что-то практически ценное?

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

[/dev/random]

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

Строгое определение регулярных выражений даётся через определение упомянутых вами регулярных грамматик. Но если вы не хотите лезть в математические дебри, то удобнее просто описать, какие возможности ему соответствуют, а какие - нет.
В регулярном выражении допустимы:
* "" - пустая строка, обозначающая саму себя.
* "a" - простой символ, обозначающий сам себя.
* "AB" - конкатенация двух выражений
* "A|B" - два альтернативных друг другу выражения
* "A*" - 0 или более повторений выражения A (в разных повторениях оно может обозначать разный текст)

Все остальные возможности либо являются просто синтаксическим сахаром, сводимым к вышеупомянутым возможностям, либо запрещены в настоящих, соответствующих формальному определению, регулярных выражениях. Например, "[abc]" - то же, что "(a|b|c)", а "A?" - то же, что "(A|)". Это просто синтаксический сахар, и, соответственно, допустимо. А вот, например, обратные ссылки к вышеуказанным возможностям свести нельзя.

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

[Bizdelnick]

Нет, я не шучу.
Какой смысл разбираться, решаются ли определённые задачи с помощью РВ, которые РВ, или с помощью РВ, которые не РВ? Я худо-бедно представляю, как работают те и другие, поэтому для решения конкретной задачи в принципе могу выбрать что-то наиболее подходящее. Только мне этого как правило не приходится делать, потому что, во-первых, выбор доступных инструментов зачастую заранее ограничен (очень редко приходится что-то делать полностью с нуля), во-вторых, при выборе чаще определяющую роль играют другие факторы (поддержка юникода, переносимость и т. п), а в-третьих и главных, если возникают такие сложности с регулярками, скорее всего более эффективным будет решение без их применения.

[QWERTYASDF]

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

Вам - не знаю, может для общего развития в свободное от любых других, более приоритетных тем. А мне интересно т.к. я худо-бедно не представляю, но хотелось бы представлять.

[QWERTYASDF]

/dev/random
Т.е. даже POSIX-РВ не соответствуют формальному определению регулярных выражений т.к. имеют фигурные скобки и "+" (частный случай фигурных скобок)?...

[Bizdelnick]

QWERTYASDF
Эквивалент любого квантифакатора можно получить путём повтора выражения и использования ? и *. A+ соответствует AA*, A{2,3} — AAA? и т. п. Так иногда приходится делать, если можно использовать только базовый POSIX-синтаксис (без расширений GNU), хотя сие, конечно, довольно неудобно.

[QWERTYASDF]

Ох, стыдно Действительно...

[/dev/random]

Т.е. даже POSIX-РВ не соответствуют формальному определению регулярных выражений т.к. имеют фигурные скобки и "+" (частный случай фигурных скобок)?...

Про "{}" и "+" Bizdelnick уже ответил, но следует отметить, что _базовые_ POSIX RE, действительно, не соответствуют определению, из-за присутствия в них обратных ссылок. В _расширенных_ POSIX RE обратных ссылок нет (хотя утилиты GNU добавляют их и туда).