Как преобразовать регулярное выражение "x {m, n}" в NFA?

Question

Регулярное выражение x{m, n} соответствует от m до n повторений предыдущего x, пытаясь сопоставить максимально возможное количество.

У меня есть наивное решение, но количество узлови ребра зависят от m и n, что недопустимо, когда n велико.

Итак, есть ли эффективный способ преобразовать регулярное выражение в NFA ?

Answer 1

К сожалению, НФА не очень хорошо «считаются».По сути, вам придется вручную расширять свое регулярное выражение до того, с чем может справиться конструкция Томпсона.например,

m{2,5} -> mm(m(m(m)?)?)?

Найдите функцию SimplifyRepeat здесь , чтобы увидеть реализацию Google.См. эту страницу для получения дополнительной информации о применении регулярных выражений на практике.