Всем привет,

Помнится Colorer вылетал на очень длинных строках. В трекере
SourceForge было много примеров кода - diff, SQL - там ещё что-то.
Игорь упоминал, что это из-за проблем со стеком или из-за парсинга
регекспов. Напомните плз., это уже пофиксили, или нет?

Я чего вообще решил написать? Google выложил C++ версию библиотеки для
работы с регекспами [1].
* thread-friendly
* linear search time
* small fixed C++ stack

Эти преимущества достигаются за счёт того, что движок RE2 построен на
основе теории автоматов [4] в противоположность традиционным
библиотекам с обратным поиском (backtracking engine) в Perl, Python,
PHP etc. Разработчикам также пришлось выбросить обратные ссылки
(backreferences) и generalized assertions (что бы это не значило).

Так вот мне интересно.
На каком принципе построен движок Colorer?
Может ли RE2 решить проблемы с вылетами и переполнением стека?
Насколько быстрее или медленее движок RE2, Colorer и PCRE?
Насколько трудно сделать движки взаимозаменяемыми?
Выживет ли Colorer без  backreferences и generalized assertions?

Синтаксис вполне себе совместим с Colorer. См. [2] и [3]
Есть ещё упоминания движка irregexp, если backreferences всё же необходимы.

[1] http://code.google.com/p/re2/
[2] http://code.google.com/p/re2/wiki/Syntax
[3] http://colorer.sourceforge.net/hrc-ref/#hrcre
[4] http://ru.wikipedia.org/wiki/Теория_автоматов
[5] http://en.wikipedia.org/wiki/Regexp#Implementations_and_running_times
[6] http://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html

--
anatoly t.

привет

нет, это не пофиксено. на длинных строках ( в зависимости от языка, от
1000и более символов в строке) идет переполнение стека.
про остальное не скажу...

--
С уважением,
 Ctapmex                          mailto:ctap...@gmail.com

Все правильно, ничего не пофикшено.

Но здесь две баги, которые стоит различать: переполнение стека из за движка
РВ, и переполнение же - но из за движка парсера схем (основного парсера). Он
тоже на рекурсии написан.

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

обратные ссылки (backreferences) и generalized assertions (что бы это не

В HRC повсеместно используются.
generalized assertions - это похоже look-ahead/look-backward - тоже в
колорере не редкость..

Может ли RE2 решить проблемы с вылетами и переполнением стека?
Движок колорера довольно прост, но не думаю что быстр.
В PCRE на сколько я знаю куча целевых оптимизаций под конкретные операторы -
в том числе из за этого он относительно быстр.

Но опять же - быстрота в РВ - понятие относительное. Каждый движок заточен
под свое. Если использовать кучу расширений а ля perl/pcre -
детерменированностью и не пахнет, а значит в теории для любого такого движка
можно придумать РВ на котором он будет работать очень медленно..

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

В случае колорера - сложно. Куча спец-операторов именно colorer-specific.
Т.е. в любом случае беря другой движок, придется его дотачивать подо все
колореровские операторы. И после этого не факт что будет полная
совместимость.
В общем работа кропотливая, и не факт что увенчается успехом. Более того,
проблемы вылетов целиком она не решит... Останутся переполнения основного
парсера (хотя это довольно редкий случай)...