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

Благодаря используемому методу конструирования, можно создать очень простое табличное представление каждого состояния. Каждое состояние будет представлено записью в массиве таких записей (номер состояния является индексом записи в массиве). Запись каждого состояния будет состоять из чего-либо для сравнения и двух номеров состояний для следующего состояния (NextStatel, NextState2). "Что-либо для сравнения" - это шаблон символов, с которым нужно устанавливать соответствие. Им может быть ветвь е, реальный символ, символ операции означающий соответствие с любым символом, класс символов (т.е. набор символов, один из которых должен совпадать с входным символом) или класс символов с отрицанием (входной символ не может быть частью набора, с которым устанавливается соответствие). Будучи построенным, этот массив известен под названием таблицы переходов (trAnsition table). В ней представлены все переходы из одного состояния в другое.

Используя заключительную блок-схему NFA-автомата, показанную на рис. 10.7, можно вручную построить таблицу переходов для регулярного выражения "(a|b)*bc". Результат приведен в таблице 10.1. Мы начинаем с состояния 0 и осуществляем переходы, выполняя сравнение с каждым символом во входной строке, пока не достигнем состояния 7. Реализация алгоритма установки соответствия, использующего подобную таблицу переходов, должна быть очень простой.

Таблица 10.1. Таблица переходов для выражения (a|b)*bc

Теперь, когда мы научились графически представлять NFA-автомат для конкретного регулярного выражения и узнали, что этот конечный NFA-автомат может быть представлен простой таблицей переходов, необходимо объединить оба алгоритма в анализаторе регулярных выражений, чтобы он мог выполнять непосредственную компиляцию таблицы состояний. После этого можно будет приступить к рассмотрению заключительной задачи - сопоставлению строк за счет использования таблицы переходов.

Прежде всего, необходимо выбрать способ представления таблицы состояний. Наиболее очевидный выбор - использование класса TtdRecordList, описанного в главе 2. Этот класс позволяет при необходимости увеличивать размер внутреннего массива. При этом заранее не нужно определять, сколько состояний может существовать для данного регулярного выражения.

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

Листинг 10.7. Добавление нового состояния в таблицу состояний

function TtdRegexEngine.rcAddState( aMatchType : TtdNFAMatchType;

aChar : AnsiChar; aCharClass : PtdCharSet;

aNextStatel: integer; aNextState2: integer): integer;

var

StateData : TNFAState;

begin

{определить поля в записи состояния}

if (aNextStatel = NewFinalState) then

StateData.sdNextState1 := succ(FTable.Count) else

StateData.sdNextState1 := aNextStatel;

StateData.sdNextState2 := aNextState2;

StateData.sdMatchType := aMatchType;

if (aMatchType = mtChar) then

StateData.sdChar := aChar else

if (aMatchType = mtClass) or (aMatchType = mtNegClass) then

StateData.sdClass := aCharClass;

{добавить новое состояние}

Result := FTable.Count;

FTable.Add(@StateData);

end;

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