конечный автомат

введение

Я хочу рассказать об очень интересном и полезном для меня алгоритме. Это конечный автомат. Подробнее, в заумном стиле читайте на википедии конечный автомат

А своими словами... Конечный автомат это гибкий алгоритм для обработки строки с разнообразными данными. Он очень удобен для синтаксического разбора.
В этой статье я покажу мой способ реализации, с некоторыми хитростями.

этот алгоритм, более приближен к конкретной задаче, чем регулярные выражение. Кстати, я не удевлюсь, если узнаю, что в библиотеке pcre или подобных есть и даже не один конечный автомат. Так что этот алгоритм лежит в основе регулярных выражений.

Здесь я показываю набросок кода для обработки строки, просто чтобы вы поняли принцып. Но с темже успехом можно обрабатывать массив или сигналы с порта.





основа

У нас есть строка, например html-тег. Её нужно разобрать и проанализировать. Но в этой строке несколько разных элементов.

Код:


dim s as string
s = "<a href="http://example.com" target=_blank>example.com</a>"


И так как же это проанализировать? Причём желательно всё разом и максимально универсальным и понятным способом?


состояние

У конечного автомата может быть несколько состояний. Их количество закладываеться изначально и ограничено.

Удобнее всего задавать описание с помощью перечесления.

Код:


enum parse_automat
reading_text ' читаем текст между тегами
reading_nametag ' читаем имя тега
waiting_attribname ' ожидаем имя атрибута
reading_attribname ' читаем имя атрибута
waiting_attribdelimeter ' ожидаем разделитель имени и значения атрибута
waiting_attribvalue ' ожидаем значение атрибута
reading_attribvalue ' читаем значение атрибута
reading_quote ' читаем значение атрибута в кавычках
end enum
dim q as parse_automat


Переменная q содержит состояние нашего автомата. Все состояния перечислены. Изначално q = reading_text - это не нужно выставлять.



выбор действия в зависимости от состояния

Вот каркас нашего анализатора. Это стандартная конструкция.

Код:


dim i as uinteger
for i = 1 to len(s)

' действие в зависимости от состояния
select case q
case reading_text ' читаем текст между тегами

case reading_nametag ' читаем имя тега

case waiting_attribname ' ожидаем имя атрибута

case reading_attribname ' читаем имя атрибута

case waiting_attribdelimeter ' ожидаем разделитель имени и значения атрибута

case waiting_attribvalue ' ожидаем значение атрибута

case reading_attribvalue ' читаем значение атрибута

case reading_quote ' читаем значение атрибута в кавычках

end select
next


Если вы заметили, то я просто скопировал содержимое enum parse_automat, внутрь цыкла, и добавил словаcase.
Но в последствии будет легко добавить новые состояния.
Я не рекомендую использовать числовые значения, т.к. это в последствии создаст вам лишнии проблемы.

В зависимости от состояния автомата, будет выполняться один из блоков.
Первым блоком будет выполняться код после case reading_text.



анализ строки

Для анализа нам собственнно нужно взять символ из строки, а в последствии мы будем его анализировать.
Цикл поможет нам пробежаться по всей строке от начала до конца.

Код:


dim oneChar  as string * 1
for i = 1 to len(s)

' берём один символ
oneChar = mid(s, i, 1)

select case q
case reading_text ' читаем текст между тегами

' здесь действия для анализа текста


end select
next


переключение состояния

И так, мы читаем текст и ждём начала тега. После чего состояние автомата должно измениться.
Нам нужно анализировать прочитаный символ. Тут уже всё зависит от вашей задачи. А я возьму опять select case{/i].

Код:


case reading_text ' читаем текст между тегами


' действия в зависимости от символа
select case oneChar
case "<" ' начинаеться тег

' покажем прочитанный текст
print "text: '" & text & "'"

' сбросим буфер
text = ""

' и переключимся в состояния чтения имени тега
q = reading_tagname


case else ' прочие символы

' заносим текст в буфер
text += oneChar

end select



Блок после [i]case reading_text будет обрабатываться пока состояние автомата, q = reading_text.
Иначе будут обрабатываться другие блоки. А изменить состояние было очень просто. Например мы переключились в состояние чтение имени тега

Код:


q = reading_tagname


И соответственно теперь будем применять совсем другие правила к символу.

Код:


case reading_nametag ' читаем имя тега

' действие в зависимости от символа
select case oneChar
case " " ' пробел

case ">" ' тег закрываеться
print "tag name: '" & tagname & "'"
tagname = ""

'  предполагаеться что дальше будет имя атрибута
q = waiting_attribname

case else ' имя тега

print "tag name: '" & tagname & "'"
tagname = ""

' возвращаемся к чтению текста
q = reading_text

' добавляем имя в буфер
tagname += oneChar

end select


В этом примере, в зависимости от символа, мы переключаемся в другие состояния.
Если тег закрываеться, то будем опять читать текст.
Если имя закончилось, но тег не закрылся, то переходим в состояние ожидания атрибута.


откат

Это уже чисто моё извращение. Я бы не сказал, что этот приём относиться к допустимым. Это именно грязная шутка. Но она порой оказываеться гораздо удобнее чем все другие варианты.

Суть заключаеться в том, что при анализе символа в каком-то состоянии мы можем наткнуться на начало другого элемента.
А теперь спрашиваеться, удобно ли нам проводить в одном состоянии анализ двух элементов?
А может быть нам вообще придёться копировать и дублировать код?
Нет. Я пожелал от такого несчастья избавиться.
Вся работа по одному элементу должна выполняться в своём собственном состоянии.

Наш предыдущий пример, со строкой html_тегов не очень хорошо подходит, по этому возьму другую задачку. Пусть это будет разбор паттерна.
И так, у нас есть состояния:

Код:


enum parse_automat
reading_text
reading_simbolclass
reading_submask
waiting_qantor
reading_qantor
reading_numqantor
end enum


В состояниях
reading_text
reading_simbolclass
reading_submask
waiting_qantor
мы можем наткнуться на символы квантора или числового квантора. Но ведь для анализа квантора есть два отдельных состояния. Причём прочитанный символ важен. А заносить его в буферы и пр, не очень-то подходит. Вот и делаем откат на один символ назад, со сменой состояния.

case reading_text
select case oneChar
case "?", "*", "+", "." ' символ квантора
i -= 1 ' один символ назад
q = reading_qantor ' переключаемся в состояние обработки квантора

case "{" ' начало числового квантора
i -= 1 ' один символ назад
q = reading_numqantor ' переходим в состояние чтение числового квантора

case else ' читаем текст
end select
[/code]

И во всех остальных состояниях делаем тоже самое. Изменили состояние на нужное и откатились на один символ назад.
Теперь, при следующем заходе, символ будет обработан уже в соответствующем состоянии.

Код:


case reading_qantor
case "?"
q = reading_text

case "*"

case "+"

case else
q = reading_text
i -= 1
end select


остатки сладки

Есть такая кухонная премудрость. Но и в некоторых случаях не стоит о ней забывать.
Дело в том, что иногда строка может закончиться неожиданно.
Собственно это явление не относиться к конечным автоматом, а просто замечание по жизни. Но при создании автомата обрабатывающего строку учитывайте возможность остатка данных.

И так, вот очень наглядный пример. Нужно разбить строку на части, по символу ",".

Код:


s = "a1,b2,c3"

for i = 1 to len(s)
if oneChar = "." then
' элемент закончился, выводим его и очищаем буфер
print text
text = ""

else
' добавляем в буфер элемент
text += oneChar

end if
next


Но на выходе мы получим всего два элемента, а не три.
[qote]
a1
b2
[/quote]

Это произошло потому, что на конце строки нет символа ","
А значит элемент остался в буфере необработанным.
Добавляем в конец нашего кода, сразу после цыкла

Код:


' если буфер не пуст, то вывести его содержимое
if text <> "" then
print text
end if


Вот так вот. Теперь всё будет выведено. Для конечного автомата, можете считать, что это ещё одно состояние.



заключение

Я показал интересный и полезный алгоритм. Лично я его довольно часто использую.
Пример взят не с потолка, а реален. Хотя приведённый код сильно урезан и упрощён. Так что думайте, оптимизируйте и выбирайте удобный вам вариант. Их число совсем не конечно.

Eric-S пишет:Для анализа нам собственнно нужно взять символ из строки, а в последствии мы будем его анализировать. Цикл поможет нам пробежаться по всей строке от начала до конца.

Код:


dim oneChar  as string


Мне кажется, что выделять для одного символа строку динамической длины неразумно. Лучше сделать так:

Код:


dim oneChar as string * 1


Думаю, что получится быстрее и компактнее. И уж точно - понятнее А что бы было ещё понятнее, лучше создать тип CHAR:

Код:


type char as string * 1
dim oneChar as char


Да, да. Обсолютно справедливо замечено.
Но... Как я уже отметил это просто демо код. В оригинале я беру символ из строки указателем и помещаю его код в числовую переменную.

Код:


dim l as uinteger = len(*s) - 1
dim oneChar as uinteger
for i = 0 to l
oneChar = s[i]

select case onechar
case asc("<")

case asc(" ")

end select
next


Хотя... Опять же это не оригинал... Но уже более приближен.
Для строк я использую свой тип. См пакет fb plus.

Да и коды символов для сравнения, не asc("<") а просто 60.

И вообще тип string, мне для текста не нравиться. Он трудно жуёт кирилицу. Подходит только для английских текстов, бинарных опираций... Слишком много и безконтрольно копируеться. И вообще, я от него стараюсь отказаться.

Если работать именно с текстом, то пой тип mstring больше подходит. Хотя и требует от программера больше усидчивости и понимания процесса.

И вообще пример с

Код:


dim oneChar as string


Заметен, но это мелочи.
У меня в примере есть более грубая операция, которая будет конкретно всё тормозить.

Код:


text += oneChar


Я настоятельно не рекомендую так делать. Это конечно же наглядно. На маленьких строках незаметно. Но когда строки будут большие, то получиться жутко.
Опять же написал такое, чтобы было понятно. Но на практике советую использовать опять же указатели или смещения.

Например с тем же текстом.
Мы можем отметить в переменной extBegin начало текста, а в переменной textLength - длину нужного фрагмента. В прочем последнюю можно будет и вычислить вычтя из текущей позиции, позицию начала. А потом распечатать текст так

Код:


print mid(s, textBegin, textLength )


Но если бы я стал это всё вставлять в примеры... То вы бы все запутались! И я заодно с вами. В некоторых местах использую похожие вычисления, но мне приходиться их долго тестировать, т.к. очень легко допустить ошибку.
А в других местах, я просто заношу всё в список фрагментов и не парюсь с вычислениями.