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. Длина извлекаемого слова не может превышать это значение.)
• Необходимо поддерживать переменную 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