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

В данном случае состояние В не является поглощающим состоянием. Что это означает на практике? Если в момент, когда входная строка исчерпана, конечный автомат находится в состоянии В, это означает, что был считан первый символ двойной кавычки, но не второй. Т.е. конечный автомат считывает строку, содержащую текст с непарным символом двойной кавычки. В зависимости от строгости алгоритма, эта ситуация может считаться ошибкой либо просто игнорироваться. В алгоритме, изображенном на рис. 10.1, она считается ошибкой.

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

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

Код реализации конечного автомата, показанного на рис. 10.1, приведен в листинге 10.1 (полный исходный код можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas). Обратите внимание, что было решено назвать состояния не абстрактно А, В и С, как на рисунке, а с использованием описательных имен ScanNormal, ScanQuoted и ScanPunctuation (соответственно, СчитываниеОбычныхСимволов, СчитываниеКавычек и СчитываниеЗнаковПрепинания).

Листинг 10.1. Извлечение слов из строки

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

type

TStates = (ScanNormal, ScanQuoted, ScanPunctuation);

const

WordDelim= ' !<>[]{}(),./?;:-+=*&';

var

State : TStates;

Inx : integer;

Ch : char;

CurWord : string;

begin

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

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

aList.Clear;

State := ScanNormal;

CurWord := '';

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

for Inx := 1 to length(S) do

begin

{get the next character}

Ch := S[Inx];

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

case State of

ScanNormal : begin

if (Ch = '"') then begin

if (CurWord <> '') then

aList.Add(CurWord);

CurWord := '';

State := ScanQuoted;

end

else

if (TDPosCh(Ch, WordDelim) <> 0) then begin

if (CurWord <> '') then begin

aList.Add(CurWord);

CurWord := '''';

end;

State := ScanPunctuation;

end else

CurWord := CurWord + Ch;

end;

ScanQuoted : begin

CurWord := CurWord + Ch;

if (Ch = '"') then begin

aList.Add(CurWord);

CurWord := '';

State := ScanNormal;

end;

end;

ScanPunctuation : begin

if (Ch = '''') then begin

CurWord := '''';

State := ScanQuoted;

end

else

if (TDPosCh(Ch, WordDelim) = 0) then begin

CurWord := Ch;

State := ScanNormal;

end end;

end;

end;

{если по достижении конца строки текущим состоянием является ScanQuoted, это означает несоответствие символа двойной кавычки}

if (State = ScanQuoted) then

raise EtdStateException.Create(FmtLoadStr (tdeStateMisMatchQuote,

[UnitName, 'TDExtractWords']));

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

if (CurWord <> '') then

aList.Add(CurWord);

end;

Код извлекает символ из входной строки, а затем входит в оператор Case, который переключает текущее состояние. Для каждого состояния предусмотрены операторы If, которые реализуют соответствующие действия и переходы в зависимости от значения текущего символа. В конце кода, если завершение программы происходит в состоянии ScanQuoted, генерируется исключение.

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

Этот код работает неэффективно в 32-разрядной среде Delphi. Код строит текущее слово посимвольно, используя строковую операцию +. Для длинных строк этот метод крайне неэффективен, поскольку операция вынуждена периодически перераспределять область памяти, в которой хранится строка, для размещения дополнительных символов. Первоначально строка пуста. Затем в нее добавляется первый символ. Поскольку пустая строка является нулевым указателем, под нее выделяется определенный объем памяти (в лучшем случае 8 байт), и строка изменяется, чтобы указывать на него. Символ добавляется в строку. После того, как в нее будет добавлено еще семь символов, выделенный под строку объем памяти должен быть перераспределен, чтобы в нее можно было поместить еще один символ. Еще одна причина низкой эффективности программы связана с операцией добавления символа. Компилятор генерирует код, обеспечивающий преобразование символа во временную односимвольную строку, а затем объединяет эти строки. Понятно, что преобразование символа в длинную строку требует выделения дополнительного объема памяти.

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