442
правки
Изменения
→Построение НКА
'''state''' s
stackp = stack
'''for''' i = 1 0 '''to''' postfix.length - 1
'''switch'''(postfix[i])
'''defaul'''t: <span style="color:#008000">// символ</span>
Теперь когда мы построили НКА, нужно научиться ходить по нему. Будем сохранять посещенные состояния в массиве.
'''struct''' List:
'''state''' **s
'''int''' n
Обход будет использовать два списка: <tex>\mathrm{cList}</tex> набор состояний, в которых уже находится, и <tex>\mathrm{nList}</tex> набор состояний в которых НКА будет после обработки текущего символа. Цикл исполнения инициализирует <tex>\mathrm{cList}</tex> стартовым состоянием и пошагово проходит.
'''fun''' match('''state''' *start, '''char''' *s): '''int''' '''List''' *cList, *nList, *t '''cList''' = startList(start, &l1) '''nList''' = &l2
'''for''' ( ; *s, s++)
step(cList, *s, nList)
Если список последних вершин содержит терминальную вершину, то строка распознана.
'''fun''' isMatch('''List''' *l): '''int'''
'''int''' i
'''for''' (i = 0; i < '''to''' l.n ->n; i++)1 '''if''' (l->.s[i] == matchState)
'''return''' 1
'''return''' 0
<tex>\mathrm{addState}</tex> добавляет состояние в список, но только если их ещё не было в нем.
'''fun''' addState('''LisList'''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> создает начальный список состояний и добавляет туда стартовое состояние.
'''fun''' startList('''state''' *s, '''List''' *l): '''List*'''
listid++
l->n = 0
<tex>\mathrm{step}</tex> вычисляет по символу, использую список текущих состояний <tex>\mathrm{cList}</tex> следующий список <tex>\mathrm{nList}</tex>.
'''fun''' step('''List''' *client, '''int''' c, '''List''' *nList)
'''int''' i
'''state''' *s
listid++
nList->.n = 0 '''for''' (i = 0; i < '''to''' cList.n ->n; i++)1 s = cList->.s[i] '''if''' (s->.c == c) addState(nList, s->.out)
=== Дополнительные возможности регулярных выражений ===
