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

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

Рисунок 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, 1TDExtractFields: list is nil1); 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; • t .

begin
aList.Add('1);
end;
else
CurField := Ch;
State : = ScanField;
end;
end;
ScanField : begin
if (Ch= ') then begin
aList.Add(CurField);
Cur Field := 1 ' ;
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, 1TDExtractFields'])); {если текущее поле не пусто, добавить его в список} if (CurField <> ' •) then aList.Add(CurField);
end;

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

Использование конечного автомата: синтаксический анализ || Оглавление || Детерминированные и недетерминированные конечные автоматы


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



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс