Изменения

<tex>\mathrm{list1}</tex> создает новый список указателей состоящий из одного указателя <tex>\mathrm{outp}</tex>. <tex>\mathrm{append}</tex> конкатенирует два списка указателей, возвращая результат. <tex>\mathrm{patch}</tex> связывает повисшую стрелку в списке <tex>\mathrm{l}</tex> с состоянием <tex>\mathrm{s}</tex>.

Используя данные примитивы и стек фрагментов можно реализовать построение НКА.

'''char''' *p;

'''frag''' stack[1000], *stackp, e1, e2, e;

patch(e.out, matchState);

'''return''' e.start;

Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.

Обход будет использовать два списка: <tex>\mathrm{cList}</tex> набор состояний, в которых уже находится, и <tex>\mathrm{nList}</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует <tex>\mathrm{cList}</tex> стартовым состоянием и пошагово проходит.

'''int''' match('''state''' *start, '''char''' *s)

'''List''' *cList, *nList, *t;

'''cList''' = startList(start, &l1);

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>, и меняет их на каждом шаге.

'''int''' isMatch('''List''' *l)

'''int''' i;

'''for''' (i = 0; i < l->n; i++)

'''return''' 1;

'''return''' 0;

<tex>\mathrm{addState}</tex> добавляет состояние в список, но только если их ещё не было в нем.

'''void''' addState('''Lis'''t *l, '''state''' *s)

'''if''' (s == NULL || s->lastlist == listid)

'''return''';

addState(l, s->out1);

'''return''';

l->s[l->n++] = s;

<tex>\mathrm{startList}</tex> создает начальный список состояний и добавляет туда стартовое состояние.

'''List*''' startList('''state''' *s, '''List''' *l)

listid++;

l->n = 0;

addState(l, s);

'''return''' l;

<tex>\mathrm{step}</tex> вычисляет по символу, использую список текущих состояний <tex>\mathrm{cList}</tex> следующий список <tex>\mathrm{nList}</tex>.

'''void''' step('''List''' *client, '''int''' c, '''List''' *nList)

'''int''' i;

'''state''' *s;

listid++;

nList->n = 0;

s = cList->s[i];

'''if''' (s->c == c)

addState(nList, s->out);

=== Дополнительные возможности регулярных выражений ===