Инкрементное соответствие регулярному выражению
Проблема: программе необходимо читать из входного потока символов и сопоставлять ввод с предопределенным списком шаблонов регулярных выражений. Программа должна сообщить о совпадении, как только оно будет найдено (сообщить обо всех, если их несколько), или сообщить об ошибке после того, как весь поток будет использован без какого-либо совпадения. Ввод может происходить не сразу, поэтому всякий раз, когда программа вызывает read во входном потоке можно прочитать ноль, один или несколько символов.
Тривиальным решением будет буферизовать все символы, которые были прочитаны до сих пор, и попытаться сопоставить его со всей группой шаблонов регулярных выражений. Но это не очень эффективно. Соответствие регулярному выражению по сути является состоянием, поэтому должен быть метод без буферизации входных данных. В идеале существует однопроходное решение, использующее технику, аналогичную Aho-Corasick, для сравнения простых строк. Я искал существующие библиотеки, но не нашел ни одной, способной на такое последовательное сопоставление регулярных выражений. Какие библиотеки или алгоритмы могут помочь (предпочтительнее библиотеки C, C++, Python или Perl)?
Одно из существующих решений формирует огромный шаблон регулярных выражений, используя или небольшие шаблоны регулярных выражений. Но я не уверен, что это быстрее, чем повторять шаблоны небольших регулярных выражений. И это не инкрементное совпадение: каждое совпадение требует целого буферизованного ввода.
Не дубликат этого: инкрементное сопоставление с образцом (RegEx) в Java? Принятый ответ показывает направление, но не дает конкретного решения. Другие пользователи сообщили об очень большом объеме памяти, возникающем в результате слияния FSA, но в этом ответе не упоминается, как оптимизировать его, чтобы сделать его практичным.
Скелет Python, чтобы помочь сформулировать проблему:
regex_list = [ r'0+', r'1+', r'2+', r'3+' ]
class Matcher:
def match(self):
...
buffer += sys.stdin.read()
...
return ([ matched_regex, ... ], matched_token)
matcher = Matcher()
while True:
matched_regex_list, token = matcher.match()