Как реализовать регулярное выражение NFA с диапазонами символов?

Question

Когда вы читаете такие посты, как Regex: NFA and Thompson's algorithm все выглядит довольно просто, пока вы не поймете, в реальной жизни вам не только прямые символы, такие как «7» или «B», но также:

[A-Z] 
[^_] 
. 

а именно классы символов (или диапазоны). И, таким образом, мой вопрос - как построить NFA с использованием диапазонов символов? Использование метасимволов типа «не А», «что-нибудь еще», а затем вычисление перекрывающихся диапазонов? Это приведет к использованию древовидной структуры при использовании финального автомата вместо таблицы.

Обновление:, пожалуйста, предположите нетривиальный размер (>> 256) алфавита.

Я спрашиваю о NFA, но позже я хотел бы конвертировать NFA в DFA.

Answer 1

Самый простой подход был бы:

1. Использование сегментов в качестве меток для переходов в обоих НКА и ДКА. Например, диапазон [a-z] будет представлен как сегмент [97, 122]; одиночный символ 'a' станет [97,97]; и любой символ ». будет [minCode, maxCode].

2. Каждый отрицательный диапазон [^ a-z] приведет к переходу двух состояний из состояния перехода в следующее состояние. В этом примере должны быть созданы два перехода [minCode, 96] и [123, maxCode].

3. Если диапазон представлен перечислением всех возможных символов [abcz], необходимо создать либо переход на символ, либо код первой группы символов в диапазоны, чтобы оптимизировать количество переходов. Таким образом, [abcz] станет [a-c]|z. Таким образом, два перехода вместо четырех.

Этого должно быть достаточно для NFA. Однако классический power set construction для преобразования NFA в DFA не будет работать, если есть переходы с пересекающимися диапазонами символов. Для решения этой проблемы требуется только один дополнительный шаг обобщения. После создания набора всех введенных символов в нашем случае это будет набор сегментов, он должен быть преобразован в набор непересекающихся сегментов. Это можно сделать во времени O (n * Log (n)), где n - количество сегментов в наборе с использованием приоритетного эквиэлегана (PQ), в котором сегменты упорядочены левой компонентой. Пример:

Procedure DISJOIN: 
    Input <- [97, 99] [97, 100] [98, 108] 
    Output -> [97, 97] [98, 99], [100, 100], [101, 108] 

Шаг 2. Чтобы создать новые переходы из «установленного состояния» алгоритм должен быть изменен следующим образом:

for each symbol in DISJOIN(input symbols) 
    S <- empty set of symbols 
    T <- empty "set state" 
    for each state in "set state" 
     for each transition in state.transitions 
     I <- intersection(symbol, transition.label) 
     if (I is not empty) 
     { 
      Add I to the set S 
      Add transition.To to the T 
     }  

    for each segement from DISJOIN(S) 
     Create transition from "set state" to T 

Чтобы ускорить согласование при поиске перехода и ввода символ C, переходы на состояние могут быть отсортированы по сегментам и бинарным поискам.