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

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

Во-первых, мы больше не располагаем простым циклом 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;

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

while StrInx <= length(S) do

begin

{извлечь текущий символ}

Ch := S[StrInx];

{обработать в зависимости от состояния}

case State of

StartScanning : begin

case Move of

0 : {переход к ScannedSign по ветви +}

begin

if (Ch = '+') then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedSign;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

1 : {переход к ScannedSign по ветви -}

begin

if (Ch = '-') then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedSign;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

2 : {бесплатный переход к ScannedSign}

begin

PushChoice(ChoiceStack, StrInx, Move, State);

State ScannedSign;

Move := 0;

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScannedSign : begin

case Move of

0 : {переход x Scanlnteger с использованием цифры}

begin

if TDIsDigit(Ch) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := Scanlnteger;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

1 : {переход к ScanLeadDigits с использованием цифры}

begin

if TDIsDigit (Ch) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScanLeadDigits;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

2 : {переход к ScanLeadDigits с использованием десятичного разделителя}

begin

if (Ch = DecimalSeparator) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScanLeadDecPoint;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

Scanlnteger : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanLeadDigits : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else

inc(Move);

end;

1 : {переход к ScanDecPoint с использованием десятичного разделителя}

begin

if (Ch = DecimalSeparator) then begin

PushChoice(ChoiceStack, StrInx, Move, State);

State := ScannedDecPoint;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScannedDecPoint : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then

inc(StrInx) else inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanLeadDecPoint : begin

case Move of

0 : {переход к ScanDecPoint с использованием цифры}

begin

if TDIsDigit(Ch) then begin

PushChoice(Choicestack, StrInx, Move, State);

State := ScanDecimalDigits;

Move := 0;

inc(StrInx);

end else

inc(Move);

end;

else

{для этого состояния допустимые переходы отсутствуют}

Move := -1;

end;

end;

ScanDecimalDigits : begin

case Move of

0 : {сохранить данное состояние для текущей цифры}

begin

if TDIsDigit(Ch) then