442
правки
Изменения
→Построение НКА
Каждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа c.
Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция <tex>\mathrm{re2post}</tex>, которая переписывает инфиксную форму регулярного выражения "<tex>``a(bb)+a" </tex> в эквивалентную постфиксную вида "<tex>``abb.+.a." </tex> (. используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
'''struct''' frag
{
'''ptrList''' *append('''ptrList''' *l1, '''ptrList''' *l2);
'''void''' patch('''ptrList''' *l, '''state''' *s);
<tex>\mathrm{list1}</tex> создает новый список указателей состоящий из одного указателя <tex>\mathrm{outp}</tex>. <tex>\mathrm{append}</tex> конкатенирует два списка указателей, возвращая результат. <tex>\mathrm{patch}</tex> связывает повисшую стрелку в списке '''<tex>\mathrm{l''' }</tex> с состоянием '''<tex>\mathrm{s'''}</tex>.
Используя данные примитивы и стек фрагментов можно реализовать построение НКА.
'''state*''' post2nfa('''char''' *postfix)
};
Обход будет использовать два списка: '''<tex>\mathrm{cList''' }</tex> набор состояний, в которых уже находится, и '''<tex>\mathrm{nList''' }</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует '''<tex>\mathrm{cList''' }</tex> стартовым состоянием и пошагово проходит.
'''int''' match('''state''' *start, '''char''' *s)
{
'''return''' isMatch(cList);
}
Чтобы избежать преаллокаций на каждой итерации цикла, match использует два преаллоцированных списка '''<tex>\mathrm{l1''' }</tex> и '''<tex>\mathrm{l2''' }</tex> как '''<tex>\mathrm{cList''' }</tex> и '''<tex>\mathrm{nList'''}</tex>, и меняет их на каждом шаге.
Если список последних вершин содержит терминальную вершину, то строка распознана.
}
'''void''' addState('''Lis'''t *l, '''state''' *s)
}
'''List*''' startList('''state''' *s, '''List''' *l)
}
'''void''' step('''List''' *client, '''int''' c, '''List''' *nList)
}
}
=== Дополнительные возможности регулярных выражений ===
