RE2 Engine

[anatoly techtonik]

Всем привет,

Помнится 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.

[cta...@gmail.com]

привет

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

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

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

[Igor Russkih]

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

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

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

Я чего вообще решил написать? Google выложил C++ версию библиотеки для
работы с регекспами [1].

Эти преимущества достигаются за счёт того, что движок RE2 построен на
основе теории автоматов [4] в противоположность традиционным

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

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

Это ссылки на группы в самом РВ - \1 \2 и т. д.
В HRC повсеместно используются.
generalized assertions - это похоже look-ahead/look-backward - тоже в колорере не редкость..
 

Так вот мне интересно.
На каком принципе построен движок Colorer?

Может ли RE2 решить проблемы с вылетами и переполнением стека?
Насколько быстрее или медленее движок RE2, Colorer и PCRE?

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

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

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

 

Насколько трудно сделать движки взаимозаменяемыми?
Выживет ли Colorer без  backreferences и generalized assertions?

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