raise EtdStateException. Create (FmtLoadStr (tdeStateMisMatchQuote,

Лабораторная работа №1.

Конечные автоматы

В отличие от большинства алгоритмов, конечные автоматы - это технологии, призванные облегчать разработку других алгоритмов. Они служат средством достижения конечной цели - реализации алгоритма. Тем не менее, как будет показано, они обладают рядом интересных особенностей. В основном мы будем рассматривать конечные автоматы, которые реализуют алгоритмы синтаксического анализа (parsing algorithm). Синтаксический анализ означает считывание строки (или текстового файла) и разбиение последовательностей символов на отдельные лексемы. Конечный автомат, который выполняет синтаксический анализ, обычно называют синтаксическим анализатором (parser).

 

Использование конечного автомата: синтаксический анализ

Чтобы лучше понять весь процесс, рассмотрим пример. Предположим, что требуется разработать алгоритм, который должен извлекать отдельные слова из строки текста. Извлекаемые слова будут помещаться в список строк. Более того, желательно, чтобы внутри строки текст, заключенный в кавычки, воспринимался как одно слово. Т.е., если имеется строка:

Не said, "State machines?"

процедура должна игнорировать знаки препинания и пробелы и возвращать следующее:

Не

said

"State machines?"

Обратите внимание, что пробел и вопросительный знак внутри заключенного в кавычки текста остались без изменений.

Простейший способ реализации этого конкретного алгоритма - использование конечного автомата. Конечный автомат (state machine) - это система (обычно цифровая), которая переходит из одного состояния в другое в соответствии с принимаемыми ею входными данными (сигналами). Смена состояний называется переходом (transition). Конечный автомат можно представить специальной блок-схемой. Блок схема рассматриваемого алгоритма показана на рис. 1.

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

После перехода в состояние В считывание символов продолжается в нем до тех пор, пока не будет считан символ закрывающей двойной кавычки. В этот момент происходит переход обратно в состояние А.

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

 

 

 

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

 

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

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

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

Считывание ‘H’;сохранение состояния A; слово = ‘H’

Считывание ‘e’;сохранение состояния A; слово = ‘He’

Считывание ‘ ’;переход в состояние C; вывод слова ‘He’, очистка слова

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

Считывание ‘a’;сохранение состояния A; слово = ‘sa’

Считывание ‘i’;сохранение состояния A; слово = ‘sai’

Считывание ‘d’;сохранение состояния A; слово = ‘said’

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

Считывание ‘ ’;сохранение состояния C

Считывание ‘”’;переход в состояние B; слово = ‘”’

Считывание ‘S’;сохранение состояния B; слово = ‘”S’

… и т.д. …

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

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

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

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

Код реализации конечного автомата, показанного на рис. 1, приведен в листинге 1. Обратите внимание, что было решено назвать состояния не абстрактно А, В и С, как на рисунке, а с использованием описательных имен ScanNormal, ScanQuoted и ScanPunctuation (соответственно, СчитываниеОбычных Символов, СчитываниеКавычек и СчитываниеЗнаковПрелинания).

 

Листинг 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

Ch := S[Inx] ;

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

case State of

ScanNormal :

begin

if (Ch = ‘”’) then begin

if (CurWord <>’ ’) then

aLi st.Add(CurWord);

CurWord : = ‘”’ ;

State := ScanQuoted;

end

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

if (CurWord <> ‘ ’) then begin

aLi st.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, генерируется исключение.

 

function TDPosCh(aCh : ANsiChar; const S : string) : integer;

var

i : integer;

begin

Result := 0;

for i := 1 to length(S) do

if (S[i] = aCh) then begin

Result := i;

Exit;

end;

end;

 

 

Задание. Используя процедуру TDExtractWords создать и отладить консольное приложение, реализующее рассмотренный алгоритм.

 

 

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

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

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

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

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

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

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

 

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