kleptos ([info]_kleptos_) wrote,
@ 2008-02-29 05:34:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Current music:Thief: The Dark Soundtrack - Track23

omg, backtracking
re.match(‘a?’*20 + ‘a’*20, ‘a’*20)

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


(Post a new comment)


[info]kolloid
2008-02-29 08:17 am UTC (link)
"Регулярные выражения" Фридла читал? awk и grep используют другой механизм реализации регекспов.

(Reply to this)(Thread)

[info]_kleptos_
2008-02-29 10:06 am UTC (link)
счас читаю это, а потом наверное буду асиливать статью Томпсона от 68, где он описал правильный алгоритм.

(Reply to this)(Parent)(Thread)

[info]kolloid
2008-02-29 10:10 am UTC (link)
Проблема не в том, что Larry Wall не знал нужного алгоритма, а в том, что алгоритм, применяющийся в grep и awk, имеет серьезные ограничения.

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

(Reply to this)(Parent)(Thread)

[info]_kleptos_
2008-02-29 11:04 am UTC (link)
ммм, а какие, просвети.
\1 не считаеться, это вообще не фича регулярного языка.

(Reply to this)(Parent)(Thread)

[info]kolloid
2008-02-29 11:16 am UTC (link)
Но обратные ссылки -- нужная фича, хотя она и делает регулярные выражения нерегулярными.
По Фридлу:
  • сохранение текста в круглых скобках
  • позиционная проверка и другие сложные проверки с нулевой длиной совпадения
  • минимальные квантификаторы
  • захватывающие квантификаторы и атомарная группировка

Как минимум первыми тремя фичами я пользуюсь регулярно. :)

(Reply to this)(Parent)(Thread)

[info]kolloid
2008-02-29 11:21 am UTC (link)
Это то, что поддерживается Perl и Python, но не поддерживется grep и awk.

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

(Reply to this)(Parent)(Thread)

[info]kolloid
2008-02-29 11:26 am UTC (link)
Я -- слепой. :) На следующей же странице, написано, что GNU awk и GNU grep умеют переключать алгоритмы в зависимости от регекспа, а в tcl используется гибридный алгоритм, комбинирующией достоинства обоих, но пока он недоступен в виде отдельной библиотеки, которую можно было бы использовать в других языках.

(Reply to this)(Parent)

[info]_kleptos_
2008-02-29 11:53 am UTC (link)
Ну да, без non-greedy конечно сложно.
В остальном я лично предпочитаю обходиться минимум регексов, чем проще, тем лучше.

Меня пока эти штуки волную в разрезе лексического анализа, а там вполне можно и без них.

(Reply to this)(Parent)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…