Я реализую синтаксический анализатор регулярных выражений с нуля, создавая NFA из регулярного выражения, а затем DFA из NFA. Проблема в том, что DFA может только сказать, когда вычисление принимается. Если регулярное выражение — «n*», а строка для сопоставления — «cannot», DFA перейдет в состояние сбоя после того, как увидит c, поэтому я опускаю первый символ спереди, «annot», затем «nnot». В этот момент он видит n и переходит в конечное состояние и просто возвращает одиночное n, поэтому я сказал ему продолжать попытки, пока следующий символ не выведет его из конечного состояния. однако, когда он заканчивается, он снова удаляет первый символ, поэтому он будет «не» и будет соответствовать «n», но мне не нужны последующие совпадения, я хочу только «nn». Я не знаю, как это возможно.
Как разобрать входную строку на совпадения с DFA
Ответы (1)
Вот простой, но, возможно, не оптимальный алгоритм. Мы пытаемся найти привязанное совпадение в каждой последующей точке строки, запуская DFA, начиная с этой точки. Когда DFA запускается, мы записываем последнюю точку в строке, где DFA находился в состоянии принятия. Когда мы в конце концов достигаем конца строки или точки, в которой DFA больше не может продвигаться вперед, мы можем вернуть совпадение, если мы прошли через состояние принятия; другими словами, если мы сохранили принимающую позицию, которая будет концом матча. В противном случае мы возвращаемся к следующей исходной позиции и продолжаем.
(Примечание: в обоих приведенных ниже алгоритмах псевдокода предполагается, что переменная, содержащая строковый индекс, может иметь значение Undefined. В практической реализации это значение может быть, например, -1.)
В псевдокоде:
Set <start> to 0
Repeat A:
Initialise the DFA state the starting state.
Set <scan> to <start>
Set <accepted> to Undefined
Repeat B:
If there is a character at <scan> and
the DFA has a transition on that character:
Advance the DFA to the indicated next state
Increment <scan>
If the DFA is now in an accepting state, set <accepted> to <scan>
Continue Loop B
Otherwise, the DFA cannot advance:
If <accepted> is still Undefined:
Increment <start> and continue Loop A
Otherwise, <accepted> has a value:
Return a match from <scan> to <accepted> (semi-inclusive)
Проблема с вышеприведенным алгоритмом заключается в том, что цикл B может выполняться произвольное количество раз, прежде чем произойдет сбой и возврат к следующей начальной позиции. Таким образом, в худшем случае время поиска будет квадратичным относительно длины строки. Это произойдет, например, с шаблоном a*b и строкой, состоящей из большого количества a.
Альтернативой является параллельное выполнение нескольких DFA. Каждый DFA соответствует другой начальной точке шаблона. Мы сканируем строку линейно; в каждой позиции мы можем создать новый DFA, соответствующий этой позиции, состояние которой является начальным состоянием.
Важно отметить, что не каждая начальная точка имеет DFA, потому что нет необходимости хранить два DFA с одним и тем же состоянием. Поскольку поиск ведется по первому совпадению в строке, если два DFA имеют одно и то же состояние, правдоподобным совпадением будет только тот, у которого более ранняя начальная точка. Кроме того, как только какой-либо DFA достигает состояния принятия, больше нет необходимости сохранять какой-либо DFA, начальная точка которого наступает позже, а это означает, что как только какой-либо DFA достигает состояния принятия, мы больше не добавляем новые DFA в сканирование.
Поскольку количество активных DFA не превышает количества состояний в DFA, этот алгоритм работает за O(NM), где N — длина строки, а M — количество состояний в DFA. На практике количество активных DFA обычно намного меньше количества состояний (если только состояний не очень мало).
Тем не менее, патологические наихудшие случаи все еще существуют, потому что трансформация NFADFA может экспоненциально увеличивать количество состояний. Экспоненциального взрыва можно избежать, используя набор NFA вместо DFA. Удобно упростить переходы НКА, используя -свободные НКА, либо выполнив -замыкание на автомате Томпсона, либо построив автомат Глушкова. Использование автомата Глушкова гарантирует, что количество состояний не превышает длину шаблона.
В псевдокоде:
Initialise a vector <v> of <index, state> pairs. Initially the vector
is empty, and its maximum size is the number of states. This vector is
always kept in increasing order by index.
Initialise another vector <active> of string indices, one for each state.
Initially all the elements in <active> are Undefined. This vector records
the most recent index at which some Automaton was in each state.
Initialise <match> to a pair of index positions, both undefined. This
will record the best match found so far.
For each position <scan> in the string:
If <match> has not yet been set:
Append {<scan>, <start_state>} to <v>.
If <v> is empty:
Return <match> if it has been set, or otherwise
return a failure indication.
Copy <v> to <v'> and empty <v>. (It's possible to recycle <v>,
but it's easier to write the pseudocode with a copy.)
For each pair {<i>, <q>} in <v'>:
If <i> is greater than the starting index in <match>:
Terminate this loop and continue with the outer loop.
If there is no transition from state <q> on the symbol at <scan>:
Continue with the next pair.
Otherwise, there is a transition to <q'> (if using NFAs, do this for each transition):
If the index in <active> corresponding to <q'> has already
been set to <scan>:
Continue with the next pair.
Otherwise, <q'> is not yet in <v>:
Append the pair {<i>, <q'>} at the end of <v>.
Set the the index in <active> at <q'> to <scan>.
If <q'> is an accepting state:
Set <match> to {<i>, <scan>}.
