Изменения
→Построение НКА
'''frag''' stack[1000], *stackp, e1, e2, e
'''state''' *s
stackp = stack;
'''for''' (p = postfix; *p; p++)
'''switch'''(*p)
Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.
'''struct''' List:
Обход будет использовать два списка: <tex>\mathrm{cList}</tex> набор состояний, в которых уже находится, и <tex>\mathrm{nList}</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует <tex>\mathrm{cList}</tex> стартовым состоянием и пошагово проходит.
'''intfun''' match('''state''' *start, '''char''' *s): '''int''' '''List''' *cList, *nList, *t '''cList''' = startList(start, &l1) '''nList''' = &l2; '''for''' ( ; *s, s++) step(cList, *s, nList) t = cList; cList = nList; nList = t
'''return''' isMatch(cList)
Чтобы избежать преаллокаций на каждой итерации цикла, <tex>\mathrm{match}</tex> использует два преаллоцированных списка <tex>\mathrm{l1}</tex> и <tex>\mathrm{l2}</tex> как <tex>\mathrm{cList}</tex> и <tex>\mathrm{nList}</tex>, и меняет их на каждом шаге.
'''fun''' addState('''Lis'''t *l, '''state''' *s):
'''if''' (s == NULL || s->lastlist == listid)
'''return'''; s->lastlist = listid;
'''if'''(s->c == split)
addState(l, s->out); addState(l, s->out1); '''return'''; l->s[l->n++] = s;
<tex>\mathrm{startList}</tex> создает начальный список состояний и добавляет туда стартовое состояние.
'''List*fun''' startList('''state''' *s, '''List''' *l): '''List*''' listid++; l->n = 0; addState(l, s); '''return''' l;
<tex>\mathrm{step}</tex> вычисляет по символу, использую список текущих состояний <tex>\mathrm{cList}</tex> следующий список <tex>\mathrm{nList}</tex>.
'''voidfun''' step('''List''' *client, '''int''' c, '''List''' *nList) '''int''' i; '''state''' *s; listid++; nList->n = 0;
'''for''' (i = 0; i < cList->n; i++)
=== Дополнительные возможности регулярных выражений ===
