Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 86
Ну это классика, кто сказал не помню:
«Если у вас есть проблема, и вы решили с ней разобраться с помощью регэкспов, то теперь у вас две проблемы».
«Если у вас есть проблема, и вы решили с ней разобраться с помощью регэкспов, то теперь у вас две проблемы».
про источник: regex.info/blog/2006-09-15/247
Я люблю регулярные выражения. Будучи однажды написанными, они обретают собственный разум. Иногда они даже разговаривают со мной.
Единожды осилив и влившись в регекспы уже не сможешь себе отказать в удовольствии накропать 30-40 символов визуальной белиберды ;-) Ясное дело для простых задач это нонсенс.
Я не знаю деталей, но вряд ли уж сразу машину Тьюринга. Логичнее было бы подняться на один уровень вверх и получить контекстно-свободные языки (автоматы с очередями).
Надо подумать… вы наверно правы относительно "(?1)". А про Тьюринга прокатит только с "(??{...})"… Спасибо. Задумался.
Кажется, контекстно-свободный язык тоже не получить. en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages
Хотя я тоже не уверен в деталях, regex-ами с памятью особо не пользовался.
Хотя я тоже не уверен в деталях, regex-ами с памятью особо не пользовался.
Ну и регулярные выражения регулярным выражениям рознь. Их в общем-то несколько диалектов.
Начиная от POSIX и заканчивая Perl.
Начиная от POSIX и заканчивая Perl.
:)
farm2.static.flickr.com/1372/1128067974_9985a11078.jpg
А вот первоисточник: www.xkcd.com/208/
Меня лично в регулярных выражения раздражает от факт, что Oracle их поддерживает не полностью и как-то через одно место.
Гм. А может быть вас лично в Oracle раздражает тот факт, что регулярные выражения он поддерживает не полностью и как-то через одно место? Задумайтесь :)
вот он, результат анти-регулярного мышления! :)
В подобных случаях я обычно вспоминаю анекдот:
Всплывает бегемот. На носу у него сидит лягушка. Она оглядывается и говорит:
— Чувствую же, что-то плавать мешает. И точно — бегемот к жопе прилип!
С одной стороны, умозаключение лягушки абсурдно. А с другой, это результат здорового эгоизма (ну может быть чуток слишком здоровенного :) ). Каждый человек в какой-то мере — центр собственной вселенной. И это естественно, а значит — не безобразно :) Если не злоупотреблять.
Иногда надо напоминать немного забывшимся (и себе, в т.ч.), что, мол, «ты не пуп земли». Но напоминать мягко. Ибо пусть бросит в меня минус тот, кто сам без греха :)
Понятно ведь, что для trak Oracle гораздо ближе к центру его вселенной, чем какие-то регэкспы. Я лишь хотел обратить его внимание на тот факт, что существуют другие системы координат :)
Всплывает бегемот. На носу у него сидит лягушка. Она оглядывается и говорит:
— Чувствую же, что-то плавать мешает. И точно — бегемот к жопе прилип!
С одной стороны, умозаключение лягушки абсурдно. А с другой, это результат здорового эгоизма (ну может быть чуток слишком здоровенного :) ). Каждый человек в какой-то мере — центр собственной вселенной. И это естественно, а значит — не безобразно :) Если не злоупотреблять.
Иногда надо напоминать немного забывшимся (и себе, в т.ч.), что, мол, «ты не пуп земли». Но напоминать мягко. Ибо пусть бросит в меня минус тот, кто сам без греха :)
Понятно ведь, что для trak Oracle гораздо ближе к центру его вселенной, чем какие-то регэкспы. Я лишь хотел обратить его внимание на тот факт, что существуют другие системы координат :)
>panic: regfree data code 'Ъ' during global destruction.
Perl — ТруЪ
Perl — ТруЪ
>panic: regfree data code 'Ъ' during global destruction
Perl — труЪ язык:))
Perl — труЪ язык:))
И все же совсем без них тоже грустно. Я вот, как С++ разработчик, очень жду следующую сишку (ну, которая, с++0х или как там её) в том числе из-за встроенных регепсов. (Я знаю про сторонние библиотеки и «можно ж самому написать» — но это не тоже самое, что native-поддержка фичи).
Я думаю в некоторых случаях простой перебор строки будет работать намного быстрее чем регулярное выражение в C++. (Это заметно только при многократном использовании, например при написании парсера, который парсит огромное кол-во информации, проверено на своем опыте).
P.S. Но поддержка регепсов еще никому не вредила.
P.S. Но поддержка регепсов еще никому не вредила.
> Теперь программист не может быть уверен, что его «регулярное выражение» будет
> использовать конечный объём памяти. Или не зациклится.
Нижеприведённый исходник будет использовать конечное количество памяти и не зациклится.
Хоть в нём используется и не только регэксп, но программист применяя их всё ещё может быть уверенным в вышеперечисленных требованиях решая задачу подобную этой со скобками.
#!/usr/bin/perl
my $s1=«qwe(sdfs{asdfasdF)asdf}asd»;
my $s2=«asdf(cxzf{gtrrt}asdf)rewasdfasd»;
our %braces=(
'\(' => '\)',
'\{' => '\}',
'\[' => '\]',
'\',
);
our $brm=join('',keys(%braces),values(%braces));
sub checkBraces
{
my $s=shift;
my $found=1;
while($found)
{
$found=0;
while(my($l,$r)=each(%braces))
{
while($s=~s/$l[^$brm]*$r//)
{
$found=1;
}
}
}
if($s=~m/([$brm])/o){print «false! $1 in $s\n»; return 0;} else {print «OK!\n»; return 1;}
}
checkBraces($s1);
checkBraces($s2);
> использовать конечный объём памяти. Или не зациклится.
Нижеприведённый исходник будет использовать конечное количество памяти и не зациклится.
Хоть в нём используется и не только регэксп, но программист применяя их всё ещё может быть уверенным в вышеперечисленных требованиях решая задачу подобную этой со скобками.
#!/usr/bin/perl
my $s1=«qwe(sdfs{asdfasdF)asdf}asd»;
my $s2=«asdf(cxzf{gtrrt}asdf)rewasdfasd»;
our %braces=(
'\(' => '\)',
'\{' => '\}',
'\[' => '\]',
'\',
);
our $brm=join('',keys(%braces),values(%braces));
sub checkBraces
{
my $s=shift;
my $found=1;
while($found)
{
$found=0;
while(my($l,$r)=each(%braces))
{
while($s=~s/$l[^$brm]*$r//)
{
$found=1;
}
}
}
if($s=~m/([$brm])/o){print «false! $1 in $s\n»; return 0;} else {print «OK!\n»; return 1;}
}
checkBraces($s1);
checkBraces($s2);
Подобный пример показывает как не нужно решать эту задачу. Во-первых его довольно сложно читать, во вторых вычислительная сложность как минимум на степень больше чем нужно.
Естественый способ решения задачи на императивном языке — использовать стек. Работает за линейное время и память от количества символов в строке.
При этом будет достаточно всего одного прохода через каждый символ строки — один простой цикл.
В нем нужно все открывающие скобки ложить в стек, а когда встречается закрывающая — пробовать достать из стека соответствующую открывающую, если не получается значит скобки расставлены неправильно.
Естественый способ решения задачи на императивном языке — использовать стек. Работает за линейное время и память от количества символов в строке.
При этом будет достаточно всего одного прохода через каждый символ строки — один простой цикл.
В нем нужно все открывающие скобки ложить в стек, а когда встречается закрывающая — пробовать достать из стека соответствующую открывающую, если не получается значит скобки расставлены неправильно.
Если уж использовать циклы и не думать про производительность, то: $_=$s1; tr/()[]{}//cd;1 while s/\(\)|\[]|{}//g; print /^$/;
«Года четыре назад, я был на собеседовании в одной крупной компании»…
я тут пару месяцев назад был на собеседовании, где попросили написать строковый калькулятор с использование регулярных выражений…
сейчас активно «тренируюсь» с регуляркой, парся логи и сайты, но правда не с Перлом
в общем спасибо, было интересно
я тут пару месяцев назад был на собеседовании, где попросили написать строковый калькулятор с использование регулярных выражений…
сейчас активно «тренируюсь» с регуляркой, парся логи и сайты, но правда не с Перлом
в общем спасибо, было интересно
У Вас все оба из описанных заблуждений — какая-то крайность. Никогда так не думал о регекспах.
Собеседование было вообще унылым чуть-более,-чем-полностью, но окончательно меня добил вопрос: «Напишите регулярное выражение, проверяющее правильность расстановки скобок.» (То есть отсутствие ситуаций "{<}>".)
Регулярка, о которой вас спрашивали, должна выглядеть как-то так:
\( ( ( (?>[^()]+) | (?R) )* ) \)
тут описан рекурсивный случай для круглых скобок.
Расскажите за что минус.
А объяснить как оно работает? :)
Я сейчас на семинаре, поэтому кратенько.
(?R) — это и есть рекурсия, в этом месте как бы подставляется ещё раз весь шаблон целиком
(?>[^()]+) | — это условия прекращения рекурсии, означает «впереди не встречаются скобки».
Т.е. рекурси идёт в себя, пока не кончаются скобки. Остальное, вроде, не надо объяснять?
(?R) — это и есть рекурсия, в этом месте как бы подставляется ещё раз весь шаблон целиком
(?>[^()]+) | — это условия прекращения рекурсии, означает «впереди не встречаются скобки».
Т.е. рекурси идёт в себя, пока не кончаются скобки. Остальное, вроде, не надо объяснять?
Скажите, я один такой, кому достаточно просто написать регэксп (ну допустим парсер-выдиралка определенных данных из html), но сходу сложно понять что делает чужой?
Я молчу про решения типа:
очевидно оно менее эффективно, чем сравнение с пустой строкой:
Вообще то:
Результат:
Поясняю: проверка пустым регулярным выражением работает быстрее
по поводу второго лирического отступления:
— как часто в работе вам приходилось проверять наличие 10 букв 'а' в след за которыми идут 10 любых символов?
— да неочень часто честно говоря…
— как часто вы ищете слово или фразу в строке или тексте?
— частенько
Поэтому в языке python чаще у вас будет встречаться «оптимальное не самое красивое и удобное решение»
Вообще тут рассматриваються проблемы «говнокода» и почему-то в этом сразу стал виноват язык Perl.
Никто же не кричит особо что язык PHP или visual basic говно, только потому что там много говнокода (там низкий порог вхождения и действительно много говнокода).
В говнокоде виноваты программисты, а не язык программирования.
В Perl действительно очень удобно работать с регулярными выражениями, но это не значит что пользоваться ими надо везде где только можно. И если у кого-то что-то не получаеться, это не значит что рег-экспы надо выкинуть на помойку, это очень удобный и сильный инструмент в руках опытного человека.
if (/./) { print "not empty\n"; }
очевидно оно менее эффективно, чем сравнение с пустой строкой:
if ($_ ne "") { print "not empty\n"; }
Вообще то:
use strict;
use Benchmark qw(:all);
my $a='a'x100;
cmpthese(1_000_000, {
'regex' => sub { if ($a !~//) { my $b = 'b' x 100; }; },
'noregex' => sub { if ($a ne "") { my $b = 'b' x 100; }; },
});
Результат:
(warning: too few iterations for a reliable count)
Rate noregex regex
noregex 2500000/s -- -20%
regex 3125000/s 25% --
Поясняю: проверка пустым регулярным выражением работает быстрее
по поводу второго лирического отступления:
— как часто в работе вам приходилось проверять наличие 10 букв 'а' в след за которыми идут 10 любых символов?
— да неочень часто честно говоря…
— как часто вы ищете слово или фразу в строке или тексте?
— частенько
Поэтому в языке python чаще у вас будет встречаться «оптимальное не самое красивое и удобное решение»
Вообще тут рассматриваються проблемы «говнокода» и почему-то в этом сразу стал виноват язык Perl.
Никто же не кричит особо что язык PHP или visual basic говно, только потому что там много говнокода (там низкий порог вхождения и действительно много говнокода).
В говнокоде виноваты программисты, а не язык программирования.
В Perl действительно очень удобно работать с регулярными выражениями, но это не значит что пользоваться ими надо везде где только можно. И если у кого-то что-то не получаеться, это не значит что рег-экспы надо выкинуть на помойку, это очень удобный и сильный инструмент в руках опытного человека.
if ($a !~//) — не удовлетворяет никакой строке. Может быть, вы имели в виду /^$/ (а точнее, /\A\z/)?
Да, вы правы, поторопился я.
В этой части автор прав, ибо с выражением /^$/ регулярные выражения отрабатывают медленее ( /\A\z/ ещё дольше обрабатывается).
Но, всё равно это не true-Perl-way и им, я думаю, мало кто пользуется, ибо можно использовать более простую конструкцию:
TMTOWTDI =)
В этой части автор прав, ибо с выражением /^$/ регулярные выражения отрабатывают медленее ( /\A\z/ ещё дольше обрабатывается).
Но, всё равно это не true-Perl-way и им, я думаю, мало кто пользуется, ибо можно использовать более простую конструкцию:
if ($a) { print 'non empty'; }
TMTOWTDI =)
>>Заданный вопрос сродни вопросу: «Какова сумма углов треугольника, если его стороны равны 1, 2 и 50 сантиметров». Он выдаёт полное незнание предмета.
Сумма углов треугольника разве не всегда 180 градусов?
Сумма углов треугольника разве не всегда 180 градусов?
ну… если человек считает, что у треугольника могут быть такие стороны, то не известно, что он думает про углы :-)
я как раз хотел привести пример безумного вопроса :-)
я как раз хотел привести пример безумного вопроса :-)
Не всегда. Она 180 градусов только на плоскости.
Только если он есть.
В циклах регулярные выражения надо использовать или с модификатором o, или выносить их выше в qr//. Я не оправдываю такое использование, как у вас в примере, а просто, к слову.
В данном случае это не очень важно. Выражение работает на много медленней, чем компилится
my $a='a'x8000;
cmpthese(1000, {
'regex' => sub { $a=~/a{10}.{10}$/; },
'regex-o' => sub { $a=~/a{10}.{10}$/o; },
'noregex' => sub { substr($a, -20, 10) eq "aaaaaaaaaa"; },
});выдаётregex-o 428/s -- -0% -100% regex 430/s 0% -- -100% noregex 999999999999999872/s 233593749999999968% 232812499999999968% --
Насколько я помню, модификатор «о» пригодится только если у Вас регулярка зависит от переменных. Если же она такая, как у автора, то соберется один раз в любом случае.
всё, что можно не гемороясь решить без регекспов лучше решать без регекспов
Конечно, при миллионе итераций эффект замедления от регулярных выражений заметен, но на практике таких циклов не бывает, бывает чтение из базы и обработка — а это доли процента на регекспы от общего времени.
Что читается лучше — substr($a, -20, 10) eq «aaaaaaaaaa»; или $a=~/a{10}.{10}$/;? Наверно, последнее, значит и при отладке, и при поддержке займёт меньше времени и работать будет надёжней.
Что читается лучше — substr($a, -20, 10) eq «aaaaaaaaaa»; или $a=~/a{10}.{10}$/;? Наверно, последнее, значит и при отладке, и при поддержке займёт меньше времени и работать будет надёжней.
Регулярное выражение описывает конечный автомат. Если вам требуется проконтролировать бесконечное количество скобок, то конечный автомат вам не поможет.
Ну-ну. Скажите еще что
/a+b/ сможет проконтролировать только конечное число символов «a», потому что де автомат конечный. (нет, в реальности бесконечностей не бывает, но там причины немного другие — ресурсы)Конечный автомат все-таки характеризуется конечным числом состояний, а не объемом информации на входе.
оно не запаминает количество знаков «а».
напишите регексп который матчит строки вида «aabb», «aaaabbbb»,… то есть сколько-то-а+столько-же-b?
такое выражение у вас не получится (без рекурсии) потому, что оно должно считать и помнить количество знако «а», а не факт присутствия одного-или-более «а».
напишите регексп который матчит строки вида «aabb», «aaaabbbb»,… то есть сколько-то-а+столько-же-b?
такое выражение у вас не получится (без рекурсии) потому, что оно должно считать и помнить количество знако «а», а не факт присутствия одного-или-более «а».
У Вас как-то внимание сакцентировано на противопоставлении «конечный-бесконечный», что истинные причины такой невозможности неочевидны. Вложенные скобочные выражения — нерегулярный язык, и описать его настоящими регулярными выражениями нельзя — я бы написал примерно так, но воля Ваша.
Дело в том, что доказательство нерегулярности языка «вложенные скобочки» упирается в конечность количества состояний автомата. Ведь для запоминания любой текущей глубины вложений нужно одно состояние, а глубина вложений бесконечна, следовательно конечный автомат не подходит.
А в вашей версии, факт нерегулярности языка «вложенные скобочки» неочевиден.
Как-то так.
А в вашей версии, факт нерегулярности языка «вложенные скобочки» неочевиден.
Как-то так.
Можно по-разному доказывать, например, опираясь на определения:
ч0ртов хабр!
en.wikipedia.org/wiki/Regular_grammar
en.wikipedia.org/wiki/Context-free_grammar
Правила вложенных скобок — это правила контекстно-свободной грамматики.
В статье все-таки это никак не объяснено. Неспециалиста в формальных грамматиках (меня, например) это может ввести в заблуждение.
en.wikipedia.org/wiki/Regular_grammar
en.wikipedia.org/wiki/Context-free_grammar
Правила вложенных скобок — это правила контекстно-свободной грамматики.
В статье все-таки это никак не объяснено. Неспециалиста в формальных грамматиках (меня, например) это может ввести в заблуждение.
Хорошо, не надо бесконечности. Напишите такой регексп для строк не дилнее 80 символов :-)
Не искушайте :)
Хороший пример задачи которую богопротивно решать регэкспами.
/^ab|a{2}b{2}|a{3}b{3}|a{4}b{4}|a{5}b{5}|a{6}b{6}|a{7}b{7}|a{8}b{8}|a{9}b{9}|a{10}b{10}|
a{11}b{11}|a{12}b{12}|a{13}b{13}|a{14}b{14}|a{15}b{15}|a{16}b{16}|a{17}b{17}|a{18}b{18}|a{19}b{19}|a{20}b{20}|
a{21}b{21}|a{22}b{22}|a{23}b{23}|a{24}b{24}|a{25}b{25}|a{26}b{26}|a{27}b{27}|a{28}b{28}|a{29}b{29}|a{30}b{30}|
a{31}b{31}|a{32}b{32}|a{33}b{33}|a{34}b{34}|a{35}b{35}|a{36}b{36}|a{37}b{37}|a{38}b{38}|a{39}b{39}|a{40}b{40}|
a{41}b{41}|a{42}b{42}|a{43}b{43}|a{44}b{44}|a{45}b{45}|a{46}b{46}|a{47}b{47}|a{48}b{48}|a{49}b{49}|a{50}b{50}|
a{51}b{51}|a{52}b{52}|a{53}b{53}|a{54}b{54}|a{55}b{55}|a{56}b{56}|a{57}b{57}|a{58}b{58}|a{59}b{59}|a{60}b{60}|
a{61}b{61}|a{62}b{62}|a{63}b{63}|a{64}b{64}|a{65}b{65}|a{66}b{66}|a{67}b{67}|a{68}b{68}|a{69}b{69}|a{70}b{70}|
a{71}b{71}|a{72}b{72}|a{73}b{73}|a{74}b{74}|a{75}b{75}|a{76}b{76}|a{77}b{77}|a{78}b{78}|a{79}b{79}|a{80}b{80}$/
Хороший пример задачи которую богопротивно решать регэкспами.
я понял, чем отличается первое заблуждение от второго.
но почему они называются одинаково?
но почему они называются одинаково?
В PCRE эта возможность так и не включена.
Cуществует конструкция вида ?R
хм.
Ну что можно сказать — при всей своей ухватистости микроскопы сильно проигрывают молоткам.
Просто на минутку нужно представить ЧТО делает // и что делает substr.
«Регулярка» == машина регулярных выражений. Это подъязык, с выполнением выражения в подпроцессе. Это дорого, но умно.
Substr == выкусыватель подстроки (с возможностью замены). Он дешев но туп. Он не сможет найти 3 буквы «а» идущие где-то в конце строки.
Для каждой задачи существует оптимальный инструмент ее решения, но это же прописная истина.
Ровно как и то, что для каждой задачи существует подмножество оптимальных решений, зависящих от конкретизации условий. Выигрываем в силе — проигрываем в расстоянии. Выигрываем в охвате (универсальности) — проигрываем в скорости.
В общем — не понял, что Вы хотели сказать топиком.
Ну что можно сказать — при всей своей ухватистости микроскопы сильно проигрывают молоткам.
Просто на минутку нужно представить ЧТО делает // и что делает substr.
«Регулярка» == машина регулярных выражений. Это подъязык, с выполнением выражения в подпроцессе. Это дорого, но умно.
Substr == выкусыватель подстроки (с возможностью замены). Он дешев но туп. Он не сможет найти 3 буквы «а» идущие где-то в конце строки.
Для каждой задачи существует оптимальный инструмент ее решения, но это же прописная истина.
Ровно как и то, что для каждой задачи существует подмножество оптимальных решений, зависящих от конкретизации условий. Выигрываем в силе — проигрываем в расстоянии. Выигрываем в охвате (универсальности) — проигрываем в скорости.
В общем — не понял, что Вы хотели сказать топиком.
Лучше поздно, чем никогда! (с)
Просмотрел бегло коментарии, но решения на {<}> так и не нашел.
По идее вот так должно работать. С рекурсией, да.
ссылка на исходник
Просмотрел бегло коментарии, но решения на {<}> так и не нашел.
По идее вот так должно работать. С рекурсией, да.
^(
(?:
[^{}\<\>] |
\{(?1)\} |
\<(?1)\>
)
*+
)$
ссылка на исходник
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Осторожно! Регекспы!