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

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

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

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

Не said, "State machines?"

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

Не

said

"State machines?"

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

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

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

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

С другой стороны, если был выполнен переход в состояние С, считывание символов продолжается в этом состоянии до тех пор, пока не произойдет одно из двух: либо не будет выполнено считывание символа двойной кавычки, в результате чего произойдет переход в состояние В, либо не будет выполнено считывание символа, который не является ни двойной кавычкой, ни пробелом, ни знаком препинания, в результате чего будет осуществлен переход в состояние 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. Длина извлекаемого слова не может превышать это значение.)

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

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

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

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

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

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

Оглавление книги