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

Естественно, прежде всего, необходимо выполнить синтаксический анализ исходного <���члена>. Мы получим начальное состояние (поэтому сохраним его в переменной). При этом известно, что конечное состояние является виртуальным конечным состоянием, следующим непосредственно за концом списка. Если следующим символом является " |", это свидетельствует о выполнении синтаксического анализа дизъюнктивной конструкции и о необходимости синтаксического анализа следующего <���выражения>. Именно здесь нужно проявить повышенную осторожность. Перво-наперво, мы создаем состояние для конечного состояния этого исходного <���члена>. В данный момент, нас не волнует, на какие состояния указывают его связи. Вскоре они будут исправлены. Создание этого конечного состояния означает также, что любые состояния в <���члене>, указывающие на виртуальное конечное состояние, фактически будут указывать на состояние, которое мы только что сделали реальным. Теперь нужно создать начальное состояние дизъюнкции. Нам известна одна из связей (исходный <���член> ), но еще не известна вторая. В конце концов, синтаксический анализ второго < выражения> еще не был выполнен. Теперь мы можем его выполнить. Мы получим начальное состояние, которое используем для исправления второй связи в начальном состоянии дизъюнкции. Новое виртуальное конечное состояние может быть использовано для создания связи, исходящей из конечного состояния исходного <���члена>.

В результате выполнения всех этих манипуляций нам пришлось создать два новых состояния (первое является начальным состоянием для дизъюнкции, а второе -конечным состоянием исходного <���члена> ). При этом мы проявили достаточную осмотрительность, чтобы виртуальное конечное состояние второго < выражения> было виртуальным конечным состоянием всей операции дизъюнкции. Код реализации этого конечного автомата приведен в листинге 10.10 (обратите внимание, что был создан еще один метод, который определяет связи для состояния после его создания).

Листинг 10.10. Синтаксический анализ операции "|"

function TtdRegexEngine.rcSetState(aState : integer;

aNextStatel: integer;

aNextState2: integer): integer;

var

StateData : PNFAState;

begin

{извлечь запись состояния и изменить информацию о переходе}

StateData := PNFAState(FTable[aState])/ StateData^.sdNextState1 := aNextStatel/ StateData^.sdNextState2 := aNextState2;

Result := aState;

end;

fmiction TtdRegexEngine.rcParseExpr : integer;

var

StartStatel : integer;

StartState2 : integer;

EndState1 : integer;

OverallStartState : integer;

begin

{предположим, что имеет место наихудший случай}

Result ErrorState;

{выполнить синтаксический анализ исходного члена}

StartStatel := rcParseTerm;

if (StartStatel = ErrorState) then

Exit;

{если текущий символ является *не* символом вертикальной черты, дизъюнкция отсутствует, поэтому начальное состояние исходного члена необходимо вернуть в качестве текущего начального состояния}

if (FPosn^ <> '|') then

Result := StartStatel {в противном случае необходимо выполнить синтаксический анализ второго выражения и объединить их в таблице переходов}

else begin

{обработать символ вертикальной черты}

inc(FPosn);

{конечное состояние исходного члена еще не существует (хотя член и содержит состояние, которое указывает на него), поэтому его нужно создать}

EndState1 := rcAddState(mtNone, #0, nil, UnusedState, UnusedState);

{для конструкции ИЛИ требуется новое начальное состояние: оно будет указывать на исходный член и на второе выражение, синтаксический анализ которого будет выполняться следующим}

OverallStartState := rcAddState(mtNone, #0, nil,

UnusedState, UnusedState);

{выполнить синтаксический анализ следующего выражения}

StartState2 := rcParseExpr;

if (StartState2 = ErrorState) then

Exit;

{изменить состояние, определенное для всего выражения, чтобы вторая связь указывала на начало второго выражения}

Result := rcSetState(OverallStartState, StartStatel, StartState2);

{определить конечное состояние исходного члена, чтобы оно указывало на результирующее конечное состояние, определенное для второго выражения и всего выражения в целом}

rcSetState(EndState1, FTable.Count, UnusedState);

end;

end;

После ознакомления с этой конкретной конструкцией создание конечных автоматов для операций замыкания ("*", и+" и сложности не представляет. Важно только создавать состояния в правильном порядке. Рассмотрим код, приведенный в листинге 10.11.

Листинг 10.11. Синтаксический анализ операций замыкания

function TtdRegexEngine.rcParseFactor : integer;

var

StartStateAtom : integer;

EndStateAtom : integer;

begin

{предположим худшее}

Result := ErrorState;

{вначале выполнить синтаксический анализ элемента}