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

Рисунок 10.2. Конечный автомат синтаксического анализа строки в формате CSV

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

Преобразование блок-схемы конечного автомата в код столь же простая задача, как и в предыдущем примере. Код реализации приведен в листинге 10.2.

Листинг 10.2. Синтаксический анализ строки CSV

procedure TDExtractFields(const S : string; aList : TStrings);

type

TStates = (FieldStart, ScanField, ScanQuoted, EndQuoted, GotError);

var

State : TStates;

Inx : integer;

Ch : char;

CurField: string;

begin

{инициализация путем очистки списка строк и начало работы в состоянии FieldStart}

Assert(aList <> nil, 'TDExtractFields: list is nil');

aList.Clear;

State := FieldStart;

CurField := ''

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

for Inx := 1 to length(S) do

begin

{получение следующего символа}

Ch := S[Inx];

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

case State of

FieldStart :

begin

case Ch of

'"' :

begin

State := ScanQuoted;

end;

',' :

begin

aList.Add('');

end;

else

CurField := Ch;

State := ScanField;

end;

end;

ScanField : begin

if (Ch= ',') then begin

aList.Add(CurField);

CurField := '';

State := FieldStart;

end else

CurField := CurField + Ch;

end;

ScanQuoted : begin

if (Ch= '"') then

State := EndQuoted else

CurField := CurField + Ch;

end;

EndQuoted : begin

if (Ch = ',') then begin

aList.Add(CurField);

CurField := '';

State := FieldStart;

end else

State := GotError;

end;

GotError : begin

raise EtdStateException.Create( FmtLoadStr (tdeStateBadCSV,

[UnitName, 'TDExtractFields']));

end;

end;

end;

{нахождение в состоянии ScanQuoted или GotError на момент окончания строки свидетельствует о наличии проблемы, связанной с закрывающей кавычкой}

if (State = ScanQuoted) or (State = GotError) then

raise EtdStateException.Create(FmtLoadStr (tdeStateBadCSV,

[UnitName, 'TDExtractFields']));

{если текущее поле не пусто, добавить его в список}

if (CurField <> '') then

aList.Add(CurField);

end;

Исходный код TDExtractFields можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas.

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

И еще один новый термин - детерминированный (deterministic). Взгляните на конечный автомат, представленный на рис. 10.2. Независимо от текущего состояния и от того, каким будет следующий символ, точно известно, в какое состояние должен быть выполнен переход. Все переходы полностью определены. Этот конечный автомат является детерминированным. В процессе его работы не требуется делать какие-либо предположения или осуществлять выбор. Например, если бы двойная кавычка была получена во время нахождения в состоянии FieldStart, потребовалось бы выполнить переход в состояние ScanQuoted.

Рисунки 10.1 и 10.2 служат примерами детерминированных конечных машин состояний (deterministic finite state machines - DFSM), или детерминированных конечных автоматов (deterministic finite automata - DFA). Противоположными им являются конечные автоматы, в ряде состояниях которых требуется осуществлять какой-либо выбор. При использовании конечного автомата этого типа приходится решать, нужно ли для данного конкретного символа выполнять переход в состояние X или в состояние Y. Как можно догадаться, реализация конечного автомата такого вида требует несколько более сложного кода. Не удивительно, что эти конечные автоматы называются недетерминированными конечными машинами состояний (non-deterministic finite state machines - NDFSM), или недетерминированными конечными автоматами (deterministic finite automata - NFA).

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