Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл

Теперь рассмотрим NFA-автомат. На рис. 10.3 показан NFA-автомат, который может преобразовывать строку, содержащую число в десятичном формате, в двоичное значение. При взгляде на этот рисунок у читателей может возникнуть вопрос, что представляют собой переходы, обозначенные странным символом е. Это -бесплатные, или свободные переходы, которые можно выполнить без использования текущего символа или лексемы. Так, например, от начала лексемы A к следующей лексеме В можно перейти, используя знак "+", знак "-" или просто выполнив это переход (бесплатный переход). Эти свободные переходы - отличительная особенность недетерминированных конечных автоматов.

Рисунок 10.3. NFA-автомат для проверки, является ли строка числом

Воспользуемся этим рисунком для проверки таких строк, как "1", "1.23", "+.7", "-12". Как видите, верхняя ветвь служит для обработки целочисленных значений (не содержащих десятичной точки). Средняя ветвь выполняет обработку строк, которые состоят, по меньшей мере, из одной цифры, предшествующей десятичной точке, но которые могут и не иметь цифр, следующих за точкой. Нижняя ветвь предназначена для обработки строк, которые могут не содержать ни одной цифры перед десятичной точкой, но обязательно должны содержать хотя бы одну цифру после нее. Если немного подумать, становится понятно, что этот конечный автомат не сможет воспринимать самостоятельно вводимую десятичную точку.

Однако одна проблема остается нерешенной: хотя конечный автомат воспримет строку "1.2", как он "узнает", что нужно выполнять среднюю ветвь? Более того, может возникать более принципиальный вопрос: зачем вообще связываться с NFA-автоматом? Весь алгоритм кажется слишком сложным. Поэтому, почему бы не ограничиться применением DFA-автомата?

В действительности на второй вопрос проще ответить, чем на первый. NFA -естественные конечные автоматы для вычисления регулярных выражений. Разобравшись в использовании NFA-автоматов, мы проходим более половины пути к конечной цели этой главы - к возможности сопоставления строки с регулярным выражением.

Вернемся к первому вопросу: откуда NFA-автомат знает, что для строки "1.2" необходимо выполнять среднюю ветвь алгоритма? Естественно, автомат этого не знает. Существует несколько способов обработки строки с помощью подобного конечного автомата. И простейшим для описания является алгоритм проб и ошибок. В качестве вспомогательного мы используем еще один алгоритм - алгоритм с отходом (backtracking algorithm).

Обратите внимание, что нас интересует определение только одного пути конечного автомата, воспринимающего строку. Могут существовать и другие, но перечисление их всех интереса для нас не представляет.

Посмотрим, как работает этот алгоритм, проследив, что происходит при попытке ввода строки "12.34".

Работа алгоритма начинается с состояния A. Первой лексемой является "1". Мы не можем выполнить ни переход "+" в состояние В, ни переход "-". Поэтому мы выполняем свободный переход (связь е). В результате автомат оказывается в состоянии В с той же лексемой "1". Теперь у нас имеются две возможности: выполнить переход в состояние С или в состояние D, поглощая при этом лексему. Выберем первую возможность. Прежде чем выполнить переход, отметим, что именно мы собираемся сделать, чтобы в случае неудачи не повторять ошибку. Итак, мы выполняем переход в состояние С, поглощая при этом лексему. Мы получаем вторую лексему, "2". Пока все достаточно просто. Автомат остается в том же состоянии и использует лексему.

Мы получаем следующую лексему ".". Теперь возможные переходы вообще отсутствуют. Мы оказались в тупике. Возможные переходы отсутствуют, но имеется лексема, которую нужно обработать. Именно здесь выступает на сцену алгоритм с отходом. Просмотрев свои заметки, мы замечаем, что в состоянии В был сделан выбор, при котором была предпринята попытка использования лексемы "1". Вероятно, этот выбор был ошибочным, поэтому мы осуществляем отход, чтобы найти правильное решение. Мы сбрасываем конечный автомат обратно в состояние В, а значение входной строки - в значение лексемы "1". Поскольку выбор первой возможности привел к проблеме, мы проверяем вторую возможность: переход в состояние D. Мы выполняем этот переход, поглощая лексему "1". Следующая лексема - "2". Мы используем ее и остаемся в состоянии D. Следующая лексема - ".": она обусловливает переход в состояние Е, которое фактически поглощает следующие две цифры. Входная строка исчерпана и NFA-автомат находится в конечном состоянии. Поэтому можно сказать, что NFA-автомат воспринимает строку "12.34".

При преобразовании этого конечного автомата в код потребуется решить несколько проблем.

Во-первых, мы больше не располагаем простым циклом For для циклической обработки символов в строке. В случае применения детерминированного автомата каждый считываемый из входной строки символ вызывал переход (даже если это переход в то же самое состояние) и отсутствовала какая-либо возможность отхода или возврата к уже посещенному символу. В случае применения недетерминированного конечного автомата мы заменяем цикл For циклом While и при необходимости обеспечиваем увеличение переменной индекса строки.

Во-вторых, в некоторых состояниях мы не можем использовать применительно к входному символу простой оператор Case или If. Нам приходится иметь дело с множеством "вариантов перехода". Некоторые из них будут немедленно отбрасываться, поскольку текущий символ не соответствует условию перехода. Другие будут приняты, причем некоторые из них будут отброшены на более позднем этапе, а какой-то вариант будет использован. А пока просто пронумеруем возможные переходы и поочередно их выполним. Для этого будем использовать целочисленную переменную.

Теперь нужно рассмотреть последний фрагмент кода: реализацию собственно алгоритма с отходом. При каждом выборе допустимого перехода (сравните его с отбрасыванием перехода из-за того, что текущий символ не соответствует условиям перехода) необходимо сохранить информацию о конкретном выполненном переходе. Тогда, при необходимости выполнить отход к тому же состоянию с тем же самым входным символом, можно легко выбрать следующий переход и проверить его. Конечно, выбор вариантов переходов может требоваться в любом состоянии. Поэтому нужно записать их все, чтобы их можно было выполнить в обратном порядке. Отход выполняется в состояние, предшествовавшее последнему сделанному выбору. Иначе говоря, следует воспользоваться структурой типа "последним вошел, первым вышел", т.е. стеком. Применим один из стеков, которые были реализованы в главе 3.

Что же нужно сохранять в стеке? Разумеется, в нем необходимо сохранять состояние, в котором был сделан выбор, номер выполненного перехода (чтобы для проверки можно было выбрать следующий переход) и, наконец, индекс символа, для которого был осуществлен выбор. Используя эти три информационных элемента, можно легко вернуть конечный автомат к предшествующему состоянию, чтобы можно было выбрать следующий, и, возможно, более удачный вариант перехода.

Код реализации NFA-автомата для анализа десятичных чисел приведен в листинге 10.3. Этот конечный автомат будет поглощать строку в момент, когда строка исчерпана, а автомат находится в конечном состоянии. Автомат не примет строку, если строка исчерпана, а состояние отличается от конечного, или если в данном состоянии текущий символ не удовлетворяет условиям перехода. Во второй ситуации должно выполняться также следующее условие: стек отхода должен быть пуст.

Листинг 10.3. Проверка того, что строка является числом, с помощью NFA-автомата

type

TnfaState = ( StartScanning, {состояние A на рисунке}

ScannedSign, {состояние B на рисунке}

ScanInteger, {состояние C на рисунке}

ScanLeadDigits, {состояние D на рисунке}

ScannedDecPoint, {состояние E на рисунке}

ScanLeadDecPoint, {состояние F на рисунке}

ScanDecimalDigits); {состояние G на рисунке}

PnfaChoice = ^TnfaChoice;

Tnf aChoice = packed record

chInx : integer;

chMove : integer;

chState : TnfaState;

end;

procedure DisposeChoice(aData : pointer);

far;

begin

if (aData <> nil) then

Dispose(PnfaChoice(aData));

end;

procedure PushChoice( aStack : TtdStack;

aInx : integer;

aMove : integer;

aState : TnfaState);

var

Choice : PnfaChoice;

begin

New(Choice);

Choice^.chInx := aInx;

Choice^.chMove := aMove;

Choice^.chState := aState;

aStack.Push(Choice);

end;

procedure PopChoice(aStack : TtdStack;

var aInx : integer;

var aMove : integer;

var aState : TnfaState);

var

Choice : PnfaChoice;

begin

Choice := PnfaChoice(aStack.Pop);

aInx := Choice^.chInx;

aMove := Choice^.chMove;

aState := Choice^.chState;

Dispose(Choice);

end;

function IsValidNumberNFA(const S : string): boolean;

var

StrInx: integer;

State : TnfaState;

Ch : AnsiChar;

Move : integer;

ChoiceStack : TtdStack;

begin

{предположим, что число является недопустимым}

Result :- false;

{инициализировать стек вариантов}

ChoiceStack := TtdStack.Create(DisposeChoice);

try

{подготовиться к сканированию}

Move := 0;

StrInx := Instate := StartScanning;

{считывание всех символов строки}