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

С другой стороны, если был выполнен переход в состояние С, считывание символов продолжается в этом состоянии до тех пор, пока не произойдет одно из двух: либо не будет выполнено считывание символа двойной кавычки, в результате чего произойдет переход в состояние В, либо не будет выполнено считывание символа, который не является ни двойной кавычкой, ни пробелом, ни знаком препинания, в результате чего будет осуществлен переход в состояние A.

Рисунок 10.1. Конечный автомат извлечения слов из строки

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

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

Переход в состояние А; очистка слова

Считывание ' H1; сохранение состояния А; слово = ' H'

Считывание 'e'; сохранение состояния А; слово = ' Не'

Считывание ' '; переход в состояние С; вывод слова 'Не', очистка слова

Считывание 's'; переход в состояние А; слово = ' s'

Считывание 'a'; сохранение состояния А; слово = ' sa'

Считывание 'i'; сохранение состояния А; слово - 'sai'

Считывание 'd';сохранение состояния А; слово = 'said'

Считывание ','; переход в состояние С; вывод слова 'said', очистка слова

Считывание ' '; сохранение состояния С

Считывание '"';переход в состояние А;слово = '"'

Считывание 'S';сохранение состояния В; слово = "'S'

и. т.д.

Однако, блок-схема конечного автомата, показанная на рис. 10.1, обладает еще одной особенностью, о которой еще ничего не было сказано. Состояния А и С обозначены двойными окружностями, в то время как состояние В - одинарной. По соглашению в диаграммах конечных автоматов двойные окружности используются для обозначения конечного состояния (называемого также состоянием останова (halt state) или поглощающим состоянием (accepting state)). Когда входная строка полностью считана, конечный автомат оказывается в особом состоянии (применительно к приведенному выше примеру строки заключительное состояние конечного автомата - состояние А). Если заключительное состояние является конечным, говорят что конечный автомат поглощает входную строку. Независимо от того, какие символы (или, точнее, лексемы (tokens)) были найдены во входной строке и какие при этом были осуществлены переходы, конечный автомат "понимает" строку. С другой стороны, если бы конечный автомат прекратил работу в незавершенном состоянии, строка не была бы принята (поглощена) и конечный автомат не понял бы ее.

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

• Вместо того чтобы установить значение переменной CurWord равным ' ', необходимо вызвать метод Set Length, чтобы заранее распределить память под строку. В зависимости от конкретных требований, следует выбрать приемлемое значение, определяющее длину слова в байтах. (Например, приемлемым значением может быть длина символа S. Длина извлекаемого слова не может превышать это значение.)