Эффективный парсинг на С/С++

Доброго времени суток ув. форумчане!

Мне поручили разработать парсер на С/С++, с целью поиска определенных кейвордов в плайнтексте (ASCII).
Подскажите пожалуйста, как сделать поиск более эффективным, присоветуйте где можно ознакомиться с сырцами (не сложными) на эту тему.

Заранее благодарен,
Алекс

 

регулярки
boost.spirit

 

Для истинных ценителей искусства - boost.xpressive

 

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

За помощь - СПАСИБО!

 

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

 

alexparser

Так а зачем что-то писать, если все уже написано? Или это по учебе?

 

alexparser

Идея на самом деле достаточно неопределённа. Можно использовать регекспы, можно использовать генераторы парсеров/лексеров. Можно написать и совсем-совсем вручную. Если делать вручную то опять же подходы могут быть несколько различны -- можно просто разбивать текст на токены, и каждый токен искать в словаре. Вероятно это не самый быстрый способ. Можно написать относительно простой конечный автомат и приложить к нему граф переключений между состояниями созданный из словаря -- здесь самой любопытной задачей будет создание такого графа. Я думаю что такой конечный автомат будет побыстрее. И думаю, что ещё быстрее придумать сложно.
Тема сия обширна настолько, что Кнут уже давненько грозится выпустить отдельный том своей эпопеи TAOCP, посвящённый именно трансляторам. И я даже не знаю, что посоветовать. Если задача просто написать маленький парсер и забыть про это, то почитай просто про конечные автоматы. Если же ты хочешь действительно разобраться с теорией, то http://en.wikipedia.org/wiki/Lexical_analysis http://en.wikipedia.org/wiki/Parser вот тебе две ссылки, с которых можно начать.
_DEN_

Ой не всё... Далеко не всё. Скажем про регекспы говорят так:
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
И думается мне, что говорят не случайно, есть объективные причины для этого высказывания.

 

r90

Старая шутка, не имеющая никакого отношения к тем, кто действительно умеет пользоваться регекспами.

Опять же, есть Boost.Xpressive. Для тех кто не в теме - Xpressive это Regex в степени Regex.

 

Да, тему полностью не раскрыл, формулирую требования к задачке:
- быстрый поиск выражений по словарю, выражение == переменное кол. слов (прим. выражение = слово1+слово2+слово3), где условие поиска истенно если в выражении совпали все слова
- словарь очевидно должен быть оптимизирован в древообразную структуру
- в поиске могут использоваться примитивные регекспы
- [самое интересное] код (прасер) должен вкомпиляться в основную программу, т.е. парсер в виде отдельной либы ны подходит
- мультиплатформенность, как минимум win/linux/*nix/mac, 32/64 bit

*я откинул кодировки, реестры, это в общем-то тоже вопрос

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

Спасибо!

 

И снова здравствуйте. STL + Boost покроет все твои потребности.

 

alexparser

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

 

Да ладно!

Обычный, я бы даже сказал, банальный FSM! В "Книге Дракона" ( http://ru.wikipedia.org/wiki/Компиляторы:_принципы,_технологии_и_инструменты ) отлично разжевана теория его построения "вручную" ( как НКА, так и ДКА ).

Вот еще ссылка ( http://swtch.com/~rsc/regexp/regexp1.html ). Тут чел хвастается еще и скоростью обработки, даже графики приводит ( акромя того, что строит автомат на лету ).

 

Damon

?

 

Я про "спец ВМ" (С).
Нет там ничего специального, все тривиально...

Видимо, немного неудачно фразу из контекста выдрал.

 

Damon

а, так вам это слово не понравилось? а в чем тут разница между "специально" и "тривиально"?
например, тот регексп, что описан у кокса (не помню его родословную (я о ре)) и заюзан в плане (подробностей не помню), достаточно руган за малофункциональность и малую расширяемость. поюзайте его - поймете о чем я.

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

короче, я не понял о чем вы кроме как назвать ребеночка. топик не о названиях, вроде, не?

 

qqwe

Вы правы, топик не о названиях. Просто когда заходит разговор о ВМ, возникает стойкое ощущение чего-то тормозного, что Вы косвенно и подтвердили:

Чем, ИМХО, вводите народ в заблуждение. Что я и постарался исправить.

Тем неменее его, лично мне, хватит, пусть и не за глаза. Фактически его возможности совпадают с grep'ом, а им я постоянно пользуюсь по жизни. Нехватает только "^,[,]", не думаю, что добавить сие будет существенной проблемой. Зато работать должен шустро, в силу своей простоты.

PCRE -- тот еще монстр. Я так и не осилил его синтаксис. Никогда не возникало надобности в его наворотах.

Вообще, сдается, что создатели PCRE, пытаются объять необъятное.
Поправте, если ошибаюсь, но согласно "Хопкрофт Д, Мотвани Р, Ульман Д. Введение в теорию автоматов, языков и вычислений" (стр. 100):

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

Что же касается ВМ/неВМ, тривиально/специально, это проблемы не автомата или регулярного выражения, а конкретной реализации. Как пример реализации автомата мне понравилась идея "State Machine — новый паттерн объектно-ориентированного проектирования " ( http://www.softcraft.ru/auto/switch/statemachine/index.shtml ). Реализуется элементарно, работает шустро.

Т.ч. по теме все, "вроде, не?" (С)

 

Если регулярки по скорости не подходят тогда наверное вначале сюда:
http://ru.wikipedia.org/wiki/Список_алгоритмов

 

Damon

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

насчет быстрого, хоть и бедного ре - тут зависит от задачи. лично мне того ре не хватало.
кстати, гдето я видел и даже валяется в запасниках реализация ре в в виде своего рода препроцессора. те, генерящего компилируемый С-сорец по ре-шаблону. бедноватый по возможностям, а по скрости.. впрочем, я с ним не разбирался. может вы руку приложите и дополните фукционал? ахо-ульман под мышку и вперед?

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

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

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

скачал, глянул. много буков. класс/жаба. есть сомнение, что оно будет работать шустро.
нельзя ли в 2х словах в чем там соль и почему вы ждете от него прибавки в скорости работы? щас нет времени вникать.

 

qqwe

Под мышку лучше коврик, а не толстенный том Ахо-Ульмана! Не удобно по такой подставке мышкой елозить -- рука быстро уставать будет.
Реализация "ре" в "виде препроцессора" по Ахо-Ульману называется Lex ( GNU вариант -- flex ), предназначен для написания лексических анализаторов. На входе правила (читай "ре"), на выходе си'шный код. Т.ч. у меня в запасниках тоже есть.

А если абстрагироваться от явы? И немного по фантазировать? Переложить код на С++? Работать будет шустрее... Но остается одна заковырка -- при каждом переходе из состояния в состояние вызывается new и новое состояние размещается в куче, что наверняка жрет кучу времени. Вот бы выделить сразу память и размещать новое состояние там же где было предыдущее. Как ни странно, но это осуществимо, более того, состояния этого ДКА можно разместить в стеке (наверное, самой быстрой памяти, в отличии от кучи). Идея, собственно, описана в "C++. Библиотека программиста" Элджера Дж. (стр. 197):

Мне не улыбалось выделять кусок памяти в 4кило ( так сказать, "с запасом" ) и я немного доработал этот вариант:

Код (Text):

1. int main( )
2. {
3.     union {
4.         char a1[ sizeof( Event1 ) ];
5.         char a2[ sizeof( Event2 ) ];
6.     } event_m;
7.  
8.     union {
9.         char a1[ sizeof( IFSMState ) ];
10.         char a2[ sizeof( FSMConcreteState1 ) ];
11.         char a3[ sizeof( FSMConcreteState2 ) ];
12.         char a4[ sizeof( FSMConcreteState3 ) ];
13.         char a5[ sizeof( FSMConcreteState4 ) ];
14.     } fsm_m;
15.  
16.     IFSMState& fsm = *( new( &fsm_m ) FSMConcreteState1() );
17.  
18.     Event1* event1 = 0;
19.     Event2* event2 = 0;
20.  
21.     event1 = new( &event_m ) Event1;
22.     std::cout << fsm( *event1 ) << std::endl;
23.  
24.     event2 = new( &event_m ) Event2;
25.     std::cout << fsm( *event2 ) << std::endl;
26.  
27.     event1 = new( &event_m ) Event1;
28.     std::cout << fsm( *event1 ) << std::endl;
29.  
30.     event2 = new( &event_m ) Event2;
31.     std::cout << fsm( *event2 ) << std::endl;
32.  
33.     event1 = new( &event_m ) Event1;
34.     std::cout << fsm( *event1 ) << std::endl;
35.  
36.     return 0;
37. }

Собственно представлен детерминированный автомат на 4-ре состояния с парой входов. Можно его немного проанализировать (по затратам процессорного времени).
Базовый класс выглядит сл. образом:

Код (Text):

1. class IFSMState
2. {
3. public:
4.     static void* operator new( unsigned int size, void* space ) { return space; }
5.     static void  operator delete( void* space, unsigned int size )      { }
6.  
7.     virtual int operator() ( Event1& event ) = 0;
8.     virtual int operator() ( Event2& event ) = 0;
9. };

Конкретное состояние выглядит так:

Код (Text):

1. class FSMConcreteState1: public IFSMState
2. {
3. public:
4.     virtual int operator() ( Event1& event );
5.     virtual int operator() ( Event2& event );
6. };
7.  
8. int FSMConcreteState1::operator ()( Event1& event )
9. {
10.     new( this ) FSMConcreteState3( );
11.  
12.     return 1;
13. }
14.  
15. int FSMConcreteState1::operator ()( Event2& event )
16. {
17.     new( this ) FSMConcreteState2( );
18.  
19.     return 2;
20. }

Что мы с этого имеем? Память при каждом чихе не выделяется, new ничего не делает, только вызывает конструктор "состояния", который инициализирует VTable... Таким образом затраты процессорного времени на переключение контекста ничтожны и будут определяться в основном, пользовательским кодом, который никто не мешает вставить до вызова "new( this ) FSMConcreteStateXXX( );".

Да что Вы так к ВМ привязались? Идея фикс?
Согласно Ахо-Ульману, для реализации "ре", достаточно просто конечного автомата. ВМ, там вообще избыточна. Таким образом моя мысля проста -- ВМ в данном случае равносильна стрельбе из пушки по воробьям, вобщем, как я уже сказал -- костыль.

Впрочем, согласно википедии:

Таким образом ВМ равносильна Машине Тьюринга, и опять же, согласно Ахо-Ульману, МТ может распознвать даже больший класс языков чем автомат с магазинной памятью. Возможно это одна из причин, почему PCRE ее использует (они уже далеко ушли от "классического" варианта регэкспов!), на ряду с кэшированием результата компиляции (для ускорения работы с "ре").

Повторю еще раз свою мысль: ВМ для работы с "классическими" регэкспами нафиг не нужна! И сам код, реализующий автомат получается простым и прозрачным. Впрочем, навертеть и тут можно, былобы желание...

 

Damon
Не понимаю я ваших терзаний.

Учите ассемблер. Самая быстрая память это регистры. И быстрее всего будет если все состояния записать в регистры. А Для парсера их легко разместить в 2 и нативный код будет ограничен только пропускной способностью памяти. А регулярки с ихними реализациями страдают просто букетами болезней. Начитаем от борьбы за кэш. В результате которых выше 250Мб/с не выдают. Картинки есть в ваших статьях.

Продолжая ВМ. Причем ВМ ВМу рознь. Так что ваши выводы не верны в корне.
Заканчивая ДКА которое не позволяет определить состояние-НКА которое вызвало завершение ДКА. В результате приходится использовать не эффективный НКА.