Regexp на чистом С++

[1datr]

Надо реализовать простое regexp на чистом С++ (без сторонних либ), но желательно чтобы с возможностью последующего расширения. Какой способ лучше? Конечный автомат или с помощью функций типа strstr?
Формат такой:*- любое количество любых символов, ? - один некий символ
Типа: *some??ing*_*sp????l*

[still_alive]

Конечные автоматы безусловно спасут отца русской демократии)

Тут выбор немного в другом.
По регулярному выражению можно построить как детерминированный, так и недетерминированный конечный автомат. Если один и тот же автомат должен проверять на допустимость большое число цепочек, то дешевле построить сразу ДКА (есть такой алгоритм построения) и моделировать его. Скажем, если пользователь делает 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), ... то можно это отследить и неявно преобразовать НКА в ДКА.

Если вверху все сложно и вопросы производительности тебе не сдались, то берешь любой: хоть НКА, хоть ДКА, хоть приведенный, хоть нет)

В общем, используй КА) Просто, очень расширяемо, удобно и хорошо для отладки.