Изменения

Перейти к: навигация, поиск

Автоматы в современном мире

24 байта убрано, 23:26, 14 марта 2018
Построение НКА
'''struct''' state:
'''int''' c
'''state''' *out '''state''' *out1
'''int''' lastlist
Каждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа c.
Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция <tex>\mathrm{re2post}</tex>, которая переписывает инфиксную форму регулярного выражения <tex>``a(bb)+a"</tex> в эквивалентную постфиксную вида <tex>``abb.+.a."</tex> (<tex>.</tex> используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
'''struct''' frag:
'''state''' *start '''ptrList''' *out
<tex>\mathrm{start}</tex> указывает на стартовое состояние фрагмента, а <tex>\mathrm{out}</tex> {{---}} лист указателей на <tex>\mathrm{state*}</tex> указатели, которые ещё не соединены.
Некоторые полезные функции для управления списком указателей:
'''fun''' *list1('''state''' **outp): '''ptrList''' '''fun''' *append('''ptrList''' *l1, '''ptrList''' *l2): '''ptrList'''
'''fun''' 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>.
'''fun''' post2nfa('''char''' *postfix): '''state*'''
'''char''' *p
'''frag''' stack[1000], *stackp, e1, e2, e '''state''' *s
stackp = stack
'''for''' (p = postfix; *p; p++)
'''defaul'''t: <span style="color:#008000">// символ</span>
s = state(*p, NULL, NULL)
push(frag(s, list1(&s->.out))
'''break'''
'''case''' '.': <span style="color:#008000">// конкатенация</span>
e = stack.pop()
s = state(Split, e.start, NULL)
push(frag(s, append(e.out, list1(&s->.out1))))
'''break'''
'''case''' '*': <span style="color:#008000">// ноль или больше</span>
s = state(Split, e.start, NULL)
patch(e.out, s)
push(frag(s, list1(&s->.out1)))
'''break'''
'''case''' '+': <span style="color:#008000">// один или больше</span>
s = state(Split, e.start, NULL)
patch(e.out, s)
stack.push(frag(e.start, list1(&s->.out1)))
'''break'''
e = stack.pop()
442
правки

Навигация