|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.11.2010, 20:57 | #1 |
Пользователь
Регистрация: 04.03.2008
Сообщений: 16
|
Regexp на чистом С++
Надо реализовать простое regexp на чистом С++ (без сторонних либ), но желательно чтобы с возможностью последующего расширения. Какой способ лучше? Конечный автомат или с помощью функций типа strstr?
Формат такой:*- любое количество любых символов, ? - один некий символ Типа: *some??ing*_*sp????l* Последний раз редактировалось 1datr; 05.11.2010 в 21:11. |
05.11.2010, 21:44 | #2 |
Great Code Monkey
Форумчанин
Регистрация: 09.08.2007
Сообщений: 533
|
Конечные автоматы безусловно спасут отца русской демократии)
Тут выбор немного в другом. По регулярному выражению можно построить как детерминированный, так и недетерминированный конечный автомат. Если один и тот же автомат должен проверять на допустимость большое число цепочек, то дешевле построить сразу ДКА (есть такой алгоритм построения) и моделировать его. Скажем, если пользователь делает fa.setRegExp(expr), а потом кучу fa.isAcceptable(s1), fa.isAcceptable(s2), ... - то лучше ДКА. Естественно, после построения ДКА нужно минимизировать количество его возможных состояний. Если же нужно проверять небольшое число - достаточно моделирования НКА. Это в случае вызовов fa.isAcceptable(regexp1, s1), fa.isAcceptable(regexp2, s2), ... НКА из регулярного выражения строится по алгоритму Томпсона, но чтобы его можно было проще реализовать, перед его вызовом стоит привести регулярное выражение к постфиксной форме и явно добавить оператор конкатенации. А если пользователь дурак и вызывает fa.isAcceptable(regexp, s1), fa.isAcceptable(regexp, s2), ... то можно это отследить и неявно преобразовать НКА в ДКА. Если вверху все сложно и вопросы производительности тебе не сдались, то берешь любой: хоть НКА, хоть ДКА, хоть приведенный, хоть нет) В общем, используй КА) Просто, очень расширяемо, удобно и хорошо для отладки. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
как исключить слова RegExp | kroŧ | Общие вопросы Delphi | 0 | 24.10.2010 18:40 |
Дисассемблировал прогу на чистом API... | Олвин | Win Api | 2 | 11.04.2010 22:01 |
Компиляция в чистом QT | JoberLord | Qt и кроссплатформенное программирование С/С++ | 7 | 08.04.2010 10:09 |
C++ Builder RegExp | Namolem | Помощь студентам | 1 | 19.01.2010 23:13 |
выделить из строки (regexp) | NieL | Общие вопросы Delphi | 2 | 23.06.2009 08:21 |