не могли бы вы подсказать алгоритм преобразования любого регулярного выражения в конечный автомат. Например, алгоритм, анализирующий регулярное выражение и соответствующим образом добавляющий состояния в fsm? Любая ссылка или более глубокая идея?
Я пишу это с помощью Python
Спасибо и привет
Используйте Введение в теорию вычислений Майкла Сипсера. Глава 1 дает подробные алгоритмы преобразования регулярного выражения в детерминированный или недетерминированный автомат с конечным числом состояний (DFA или NFA) в контексте доказательства их эквивалентности (DFA, NFA и регулярное выражение могут соответствовать точно тем же классам). струн).
Общая идея такова: вы конвертируете регулярное выражение в NFA, что можно сделать довольно просто (* — это цикл, | и диапазоны символов — точки ветвления). Затем вы конвертируете NFA в (гораздо больший) DFA, который включает создание одного состояния DFA для каждого набора альтернативных состояний NFA. DFA имеет не более того количества состояний, которое соответствует мощности набора состояний NFA (например, NFA с 3 состояниями может быть преобразован в DFA с не более чем 2 ^ 3 = 8 состояниями) и может распознавать любую целевую строку без возврата. . Подробности читайте в книге.
re.compile? Вы хотите сами переписать механизм регулярных выражений? - person Bruce schedule 11.07.2012re.DEBUG. - person JBernardo schedule 11.07.2012