michurin Jul 9 2009 at 09:53

Осторожно! Регекспы!

4 min

8.8K

Abnormal programming*

+145

Comments 86

adaptun Jul 9 2009 at 10:11

Ну это классика, кто сказал не помню:
«Если у вас есть проблема, и вы решили с ней разобраться с помощью регэкспов, то теперь у вас две проблемы».

maniac Jul 9 2009 at 10:55

про источник: regex.info/blog/2006-09-15/247

adaptun Jul 9 2009 at 14:25

Спасибо, интересный рассказ.

nekt Jul 9 2009 at 10:27

Я люблю регулярные выражения. Будучи однажды написанными, они обретают собственный разум. Иногда они даже разговаривают со мной.

anonimizer_me Jul 9 2009 at 12:12

Будучи однажды написанными, они становятся не понятными через неделю :)

DmitriKadykov Jul 9 2009 at 14:47

Если их хорошо комментировать и грамотно форматировать то не факт.

seleko Jul 9 2009 at 15:25

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

anonimizer_me Jul 9 2009 at 16:19

Видимо у вас своё восприятие регулярок :)

Goodkat Jul 9 2009 at 13:54

начать им отвечать — фатальная ошибка программиста

maxshopen Jul 9 2009 at 15:17

думаю это не ошибка, это уже диагноз :)

khizhaster Jul 9 2009 at 10:28

Единожды осилив и влившись в регекспы уже не сможешь себе отказать в удовольствии накропать 30-40 символов визуальной белиберды ;-) Ясное дело для простых задач это нонсенс.

kzn Jul 9 2009 at 10:38

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

michurin Jul 9 2009 at 10:42

Надо подумать… вы наверно правы относительно "(?1)". А про Тьюринга прокатит только с "(??{...})"… Спасибо. Задумался.

angeleyes Jul 9 2009 at 12:20

Кажется, контекстно-свободный язык тоже не получить. en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages

Хотя я тоже не уверен в деталях, regex-ами с памятью особо не пользовался.

kzn Jul 9 2009 at 10:40

Ну и регулярные выражения регулярным выражениям рознь. Их в общем-то несколько диалектов.
Начиная от POSIX и заканчивая Perl.

kex Jul 9 2009 at 10:43

kex Jul 9 2009 at 10:51

farm2.static.flickr.com/1372/1128067974_9985a11078.jpg

Mithgol Jul 9 2009 at 11:00

А вот первоисточник: www.xkcd.com/208/

glorybox Jul 9 2009 at 11:14

у меня такая футболка:)

trak Jul 9 2009 at 10:45

Меня лично в регулярных выражения раздражает от факт, что Oracle их поддерживает не полностью и как-то через одно место.

beetleinweb Jul 9 2009 at 12:11

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

qmax Jul 11 2009 at 07:59

вот он, результат анти-регулярного мышления! :)

beetleinweb Jul 11 2009 at 13:10

В подобных случаях я обычно вспоминаю анекдот:
Всплывает бегемот. На носу у него сидит лягушка. Она оглядывается и говорит:
— Чувствую же, что-то плавать мешает. И точно — бегемот к жопе прилип!

С одной стороны, умозаключение лягушки абсурдно. А с другой, это результат здорового эгоизма (ну может быть чуток слишком здоровенного :) ). Каждый человек в какой-то мере — центр собственной вселенной. И это естественно, а значит — не безобразно :) Если не злоупотреблять.

Иногда надо напоминать немного забывшимся (и себе, в т.ч.), что, мол, «ты не пуп земли». Но напоминать мягко. Ибо пусть бросит в меня минус тот, кто сам без греха :)

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

XuMiX Jul 9 2009 at 10:52

>panic: regfree data code 'Ъ' during global destruction.
Perl — ТруЪ

XuMiX Jul 9 2009 at 10:57

НЛО, забери мой комент отсюда, ну пожааааалуста)

XuMiX Jul 9 2009 at 10:53

>panic: regfree data code 'Ъ' during global destruction
Perl — труЪ язык:))

tangro Jul 9 2009 at 10:56

И все же совсем без них тоже грустно. Я вот, как С++ разработчик, очень жду следующую сишку (ну, которая, с++0х или как там её) в том числе из-за встроенных регепсов. (Я знаю про сторонние библиотеки и «можно ж самому написать» — но это не тоже самое, что native-поддержка фичи).

Kirk Jul 9 2009 at 12:05

Я думаю в некоторых случаях простой перебор строки будет работать намного быстрее чем регулярное выражение в C++. (Это заметно только при многократном использовании, например при написании парсера, который парсит огромное кол-во информации, проверено на своем опыте).

P.S. Но поддержка регепсов еще никому не вредила.

Q2W Jul 9 2009 at 10:59

> Теперь программист не может быть уверен, что его «регулярное выражение» будет
> использовать конечный объём памяти. Или не зациклится.

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

#!/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);

vgrichina Jul 9 2009 at 13:48

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

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

jerom Jul 9 2009 at 19:29

Если уж использовать циклы и не думать про производительность, то: $_=$s1; tr/()[]{}//cd;1 while s/|\[]|{}//g; print /^$/;

KorP Jul 9 2009 at 11:11

«Года четыре назад, я был на собеседовании в одной крупной компании»…
я тут пару месяцев назад был на собеседовании, где попросили написать строковый калькулятор с использование регулярных выражений…

сейчас активно «тренируюсь» с регуляркой, парся логи и сайты, но правда не с Перлом

в общем спасибо, было интересно

Inversion Jul 9 2009 at 11:16

У Вас все оба из описанных заблуждений — какая-то крайность. Никогда так не думал о регекспах.

bolk Jul 9 2009 at 11:24

Собеседование было вообще унылым чуть-более,-чем-полностью, но окончательно меня добил вопрос: «Напишите регулярное выражение, проверяющее правильность расстановки скобок.» (То есть отсутствие ситуаций "{<}>".)

Регулярка, о которой вас спрашивали, должна выглядеть как-то так:

$ ( ( (?>[^()]+) | (?R) )* ) $

тут описан рекурсивный случай для круглых скобок.

bolk Jul 9 2009 at 12:39

Расскажите за что минус.

Hellbot Jul 9 2009 at 15:39

А объяснить как оно работает? :)

bolk Jul 9 2009 at 15:52

Я сейчас на семинаре, поэтому кратенько.

(?R) — это и есть рекурсия, в этом месте как бы подставляется ещё раз весь шаблон целиком

(?>[^()]+) | — это условия прекращения рекурсии, означает «впереди не встречаются скобки».

Т.е. рекурси идёт в себя, пока не кончаются скобки. Остальное, вроде, не надо объяснять?

UFO landed and left these words here

AntonShcherbinin Jul 10 2009 at 15:11

О! Я и не подозревал, что есть ещё одна категория людей, кому могут быт полезны мои статьи. Теперь буду рекомендовать их всем, кто страдает бессонницей!
Как говорится, «буквально абзацев 5 — и здоровый храп вам гарантирован» :))

mrjj Jul 9 2009 at 11:36

Скажите, я один такой, кому достаточно просто написать регэксп (ну допустим парсер-выдиралка определенных данных из html), но сходу сложно понять что делает чужой?

youlose Jul 9 2009 at 12:03

Я молчу про решения типа:
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 действительно очень удобно работать с регулярными выражениями, но это не значит что пользоваться ими надо везде где только можно. И если у кого-то что-то не получаеться, это не значит что рег-экспы надо выкинуть на помойку, это очень удобный и сильный инструмент в руках опытного человека.

Biga Jul 9 2009 at 13:36

if ($a !~//) — не удовлетворяет никакой строке. Может быть, вы имели в виду /^$/ (а точнее, /\A\z/)?

youlose Jul 9 2009 at 14:59

Да, вы правы, поторопился я.
В этой части автор прав, ибо с выражением /^$/ регулярные выражения отрабатывают медленее ( /\A\z/ ещё дольше обрабатывается).
Но, всё равно это не true-Perl-way и им, я думаю, мало кто пользуется, ибо можно использовать более простую конструкцию:

if ($a) { print 'non empty'; }

TMTOWTDI =)

beliyadm Jul 9 2009 at 12:14

>>Заданный вопрос сродни вопросу: «Какова сумма углов треугольника, если его стороны равны 1, 2 и 50 сантиметров». Он выдаёт полное незнание предмета.

Сумма углов треугольника разве не всегда 180 градусов?

michurin Jul 9 2009 at 12:17

ну… если человек считает, что у треугольника могут быть такие стороны, то не известно, что он думает про углы :-)
я как раз хотел привести пример безумного вопроса :-)

beliyadm Jul 9 2009 at 12:30

ох уж эти безумные треугольники ))
Давайте ваш безумный пример!

michurin Jul 9 2009 at 12:31

это он и был :-)))

angeleyes Jul 9 2009 at 12:35

Просто попробуйте линейкой нарисовать треугольник с сторонам 1, 2 и 50 см. Потом почитайте про неравенство треугольника. :)

beliyadm Jul 9 2009 at 12:47

понял уже, сразу не обратил внимание на размерность :)

Alkor Jul 9 2009 at 12:38

А если это не в Евклидовом пространстве=))

michurin Jul 9 2009 at 12:41

Вот это путь перл. Если регулярные выражения что-то не могут, то мы встроим в них механизм нерегулярности :-) Ничего святого нету :-))))

q_styler Jul 9 2009 at 14:35

Тогда и сумма углов какой угодно может быть )

Kotter Jul 9 2009 at 12:35

habrahabr.ru/blogs/zadachki/24278/ ;)

bolk Jul 9 2009 at 12:39

Не всегда. Она 180 градусов только на плоскости.

jetserge Jul 9 2009 at 12:44

А разве через 3 точки может проходить больше одной плоскости? )

bolk Jul 9 2009 at 12:47

jetserge Jul 9 2009 at 12:54

Изящно )))) сферический треугольник.

qmax Jul 11 2009 at 08:05

в вакууме…

Pacifist Jul 9 2009 at 13:12

Арбуза захотелось…

ustrel Jul 9 2009 at 21:07

Перейдем в n-мерное пространство?)

beliyadm Jul 9 2009 at 12:47

если это неевклидово пространство — то может

sse Jul 9 2009 at 12:57

Напомнило теорему, про что, что через 3 точки на плоскости можно провести прямую: «Через любые три точки на плоскости можно провести прямую достаточной толщины».

FloppyFormator Jul 9 2009 at 13:08

Только если он есть.

ksurent Jul 9 2009 at 12:39

В циклах регулярные выражения надо использовать или с модификатором o, или выносить их выше в qr//. Я не оправдываю такое использование, как у вас в примере, а просто, к слову.

michurin Jul 9 2009 at 12:45

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

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%          --

Bambr Jul 9 2009 at 15:54

Насколько я помню, модификатор «о» пригодится только если у Вас регулярка зависит от переменных. Если же она такая, как у автора, то соберется один раз в любом случае.

romy4 Jul 9 2009 at 14:34

всё, что можно не гемороясь решить без регекспов лучше решать без регекспов

Pilat Jul 9 2009 at 15:42

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

Что читается лучше — substr($a, -20, 10) eq «aaaaaaaaaa»; или $a=~/a{10}.{10}$/;? Наверно, последнее, значит и при отладке, и при поддержке займёт меньше времени и работать будет надёжней.

Bambr Jul 9 2009 at 15:57

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

Pilat Jul 9 2009 at 16:02

Это правильно, но это и так очевидно. Но не настолько регекспы страшны, как написал автор топика.

galaxy Jul 9 2009 at 18:02

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

Ну-ну. Скажите еще что /a+b/ сможет проконтролировать только конечное число символов «a», потому что де автомат конечный. _{(нет, в реальности бесконечностей не бывает, но там причины немного другие — ресурсы)}
Конечный автомат все-таки характеризуется конечным числом состояний, а не объемом информации на входе.

michurin Jul 9 2009 at 18:11

оно не запаминает количество знаков «а».
напишите регексп который матчит строки вида «aabb», «aaaabbbb»,… то есть сколько-то-а+столько-же-b?
такое выражение у вас не получится (без рекурсии) потому, что оно должно считать и помнить количество знако «а», а не факт присутствия одного-или-более «а».

galaxy Jul 9 2009 at 18:51

У Вас как-то внимание сакцентировано на противопоставлении «конечный-бесконечный», что истинные причины такой невозможности неочевидны. Вложенные скобочные выражения — нерегулярный язык, и описать его настоящими регулярными выражениями нельзя — я бы написал примерно так, но воля Ваша.

angeleyes Jul 9 2009 at 19:39

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

А в вашей версии, факт нерегулярности языка «вложенные скобочки» неочевиден.

Как-то так.

galaxy Jul 9 2009 at 20:06

Можно по-разному доказывать, например, опираясь на определения:

galaxy Jul 9 2009 at 20:12

ч0ртов хабр!
en.wikipedia.org/wiki/Regular_grammar
en.wikipedia.org/wiki/Context-free_grammar

Правила вложенных скобок — это правила контекстно-свободной грамматики.
В статье все-таки это никак не объяснено. Неспециалиста в формальных грамматиках (меня, например) это может ввести в заблуждение.

angeleyes Jul 10 2009 at 05:48

Я понимаю, но определения тоже могут ввести в заблуждение неспециалиста. Я пытался оправдать акцент на «бесконечный-конечный».

michurin Jul 9 2009 at 21:09

Хорошо, не надо бесконечности. Напишите такой регексп для строк не дилнее 80 символов :-)

galaxy Jul 9 2009 at 21:22

Не искушайте :)

/^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}$/

Хороший пример задачи которую богопротивно решать регэкспами.

michurin Jul 9 2009 at 22:15

сами написали или помогал кто? ,-))))

galaxy Jul 9 2009 at 22:31

Питон помог ;)

zantor Oct 15 2009 at 12:53

А ведь можно и так:

perl -le "my ($a, $i) = ('aaabbb', 0); 1 while ((length $a >= ++$i * 2) && ($a !~ /^(a{$i}b{$i})$/)); print $1;"

qmax Jul 11 2009 at 08:09

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

developer Sep 15 2009 at 10:39

В PCRE эта возможность так и не включена.

Cуществует конструкция вида ?R

meettya Nov 20 2009 at 02:47

хм.
Ну что можно сказать — при всей своей ухватистости микроскопы сильно проигрывают молоткам.
Просто на минутку нужно представить ЧТО делает // и что делает substr.
«Регулярка» == машина регулярных выражений. Это подъязык, с выполнением выражения в подпроцессе. Это дорого, но умно.
Substr == выкусыватель подстроки (с возможностью замены). Он дешев но туп. Он не сможет найти 3 буквы «а» идущие где-то в конце строки.

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

Kcop Oct 10 2016 at 02:27

Лучше поздно, чем никогда! (с)

Просмотрел бегло коментарии, но решения на {<}> так и не нашел.
По идее вот так должно работать. С рекурсией, да.

^(                       
   (?:                   
    [^{}\<\>] |
    \{(?1)\} | 
    \<(?1)\>
  )
  *+
)$

ссылка на исходник