Инкрементное соответствие регулярному выражению - PullRequest
Новая
       19

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

0 голосов
/ 31 января 2019

Проблема: программе необходимо прочитать из входного потока символов и сопоставить ввод с предопределенным списком шаблонов регулярных выражений.Программа должна сообщить о совпадении, как только оно будет найдено (сообщить обо всех, если их несколько), или сообщить об ошибке после того, как весь поток будет использован без какого-либо совпадения.Ввод может происходить не сразу, поэтому всякий раз, когда программа вызывает read во входном потоке, можно прочитать ноль, один или несколько символов.

Тривиальным решением будет буферизация всех символов, которые былипрочитайте до сих пор и попробуйте сопоставить его с целой группой шаблонов регулярных выражений.Но это не очень эффективно.Соответствие регулярному выражению по сути является состоянием, поэтому должен быть метод без буферизации входных данных.В идеале существует однопроходное решение, использующее технику, аналогичную Aho-Corasick, для сопоставления простых строк.Я искал существующие библиотеки, но не нашел ни одной, способной на такое последовательное сопоставление регулярных выражений.Какие библиотеки или алгоритмы могут помочь (предпочтительнее библиотеки C, C ++, Python или Perl)?

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

Не дубликат этого: Соответствие инкрементному шаблону (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()
...