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

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

• Для каждого добавляемого символа необходимо увеличивать значение CurInx и устанавливать значение CurWord [CurInx] равным символу.

• Когда требуется добавить текущее слово в список строк, необходимо снова вызвать метод SetLength, на этот раз передавая ему значение переменной CurInx. В результате длина строки будет устанавливаться равной количеству символов в строке. Затем значение CurInx необходимо переустановить равным нолю.

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

------------

Как видите, код обеспечивает успешную реализацию конечного автомата. Кроме того, его очень легко расширить. Например, предположим, что должно учитываться также использование одинарных кавычек. Добиться этого достаточно просто: нужно создать новое состояние D, работающее таким же образом, как состояние В, за исключением того, что при переходе в это состояние и из него должны использоваться одинарные, а не двойные кавычки. Применительно к написанию кода это означает выполнение простого копирования и вставки с целью дублирования функций состояния В в состоянии D.

Синтаксический анализ файлов с разделяющими запятыми

Часто встречающаяся задача - необходимость выполнить синтаксический анализ файлов с запятыми-разделителями. Файл с запятыми-разделителями представляет собой текстовый файл, описывающий таблицу записей. Каждая строка в файле является отдельной записью, а сами строки делятся на поля записей, разделяемые одно от другого запятыми. (Иногда эту организацию файла называют форматом CSV (comma-separated values - значения, разделяемые запятыми).) При решении этой задачи возникает ряд затруднений (как всегда!). Поле может быть окружено кавычками (в результате значение поля может содержать запятые). Поле может отсутствовать - в этом случае две запятые означают, что поля следуют одно за другим.

Ниже приведен пример строки текста в формате CSV. Julian,Bucknall,,43,"Author, and Columnist"

Эта строка содержит пять полей. Первые два поля содержат значения [Julian] и [Bucknall], третье поле не имеет значения, значение четвертого поля - [43], а пятого - [Author, and Columnist]. (В данном случае строковые значения заключены в квадратные скобки для показа того, что двойные кавычки в исходной строке отбрасываются.)

Будем считать, что конечной целью является создание подпрограммы, которая принимает строку и список строк, разбивает строку на отдельные поля и вставляет поля в список строк. Прежде чем приступить к созданию диаграммы конечного автомата, давайте сформулируем несколько правил в отношении допустимого формата строки CSV. Во-первых, все символы являются значащими, и единственные отбрасываемые символы - запятые (естественно, после того, как они были использованы для разбиения текста CSV) и двойные кавычки, в которые заключено значение поля. Более того, двойная кавычка имеет значение открывающей двойной кавычки, если она расположена за запятой (или является первым символом строки). В частности, например, это правило означает, что если бы в приведенном примере строки между запятой и открывающей двойной кавычкой имелся один пробел, подпрограмма разбила бы строку на шесть полей, двумя последними из которых были бы ["Author] и [and Columnist"]. Более того, если бы двойная кавычка была идентифицирована в качестве открывающей двойной кавычки, то следующая двойная кавычка закрывала бы значение поля, а следующим символом должна была бы быть запятая (или конец строки). В противном случае имеет место ошибка, и строка усекается.

Теперь можно нарисовать блок-схему конечного автомата. На рис. 10.2 отражены пять состояний. Начальное состояние названо FieldStart. Если следующий символ - двойная кавычка, выполняется переход в состояние ScanQuoted, в котором выполняется отбор символов до тех пор, пока не встретится следующая двойная кавычка и не будет выполнен переход в состояние EndQuoted. Если следующий символ - запятая, можно снова выполнить переход в состояние FieldStart. Если это не так, выполняется переход в состояние ошибки, и выполнение программы прекращается. Пребывая в состоянии FieldStart, мы также можем получить запятую (поле считается пустым). Или, если мы получаем символ, который не является запятой или двойной кавычкой, осуществляется переход в состояние ScanField. В этом состоянии выполняется ввод и накопление символов до тех пор, пока не будет получена запятая.

Рисунок 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).