поиск соответствия строки регулярному выражению и конечные автоматы

Привтествую
В общем сабж. В регуляке требуется только поддержка "?" и "*"
Как реализовать алгоритм?

Конкретно нужно:
Какие взять состояния для автомата, что взять за входной сигнал саму строку, или строку регулярки???

 

Rustem
http://ru.wikipedia.org/wiki/Построение_синтаксического_анализатора_на_основе_автоматного_подхода

 

Блин, там опять теория, как её применить к конкретной задаче? Без внешних либ. На чистом С.
Дана строка char *s;
Дана регулярка char *pattern;
Надо: удовлетворяет ли строка регулярке.
Не прошу конкретного решения, подскажите как надо делать...

 

Rustem, а в чём конкретно трудности? Для ? и * там достаточно знать как работать с циклами, условиями и массивами. С чем проблемы в реализации?

 

есть переменная - state
есть входная буква - с

Код (Text):

1. while(c = get_c)
2. {
3.   switch(state)
4.   {
5.      case 1:
6.         if(c == 'a')  
7.             state =2;
8.      case 2:
9.        if(c == 'b')
10.              state = 1;
11.  }
12. }

типа по текущему состоянию и входному символу определяешь, куда идти дальше.
Если у тебя регулярка, я так понимаю, надо добавлять память к автомату, то есть запоминать предыдущие символы, иначе aaab и aab для a*b не различить.

ps. народ, извините пожалуйста за плохой вид сообщения, ничего не получается сделать.

 

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


код писать лениво. впрочем, когда-то помнится делал нечто подобное. но 100% не найду т.к. винт со старыми исходниками и доками ушел в небытие (

 

Rustem
то есть поиск по маске?

 

Код (Text):

1. BOOL PatternMatch(const char* s, const char* mask)
2. {
3.     const   char* cp=0;
4.     const   char* mp=0;
5.   for (; *s&&*mask!='*'; mask++,s++) if (*mask!=*s&&*mask!='?') return 0;
6.   for (;;) {
7.     if (!*s) { while (*mask=='*') mask++; return !*mask; }
8.     if (*mask=='*') { if (!*++mask) return 1; mp=mask; cp=s+1; continue; }
9.     if (*mask==*s||*mask=='?') { mask++, s++; continue; }
10.     mask=mp; s=cp++;
11.   }
12. }

Код взят с rsdn.ru

 

boost::regex?

 

В принципе можно и без автоматов, если это проще получается

Спасибо всем за ответы

 

Хорошая статья по теме : http://swtch.com/~rsc/regexp/regexp1.html

 

yGREK
Спасибо

 

Можно. Смотри исходный код FindFirstFileEx.

 

Просто еще интересно как это на автоматах делается