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

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

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

function TtdRegexEngine.rcSetState(aState : integer;

aNextStateclass="underline" 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;

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

StartStateAtom := rcParseAtom;

if (StartStateAtom = ErrorState) then

Exit;

{проверить на наличие операции замыкания}

case FPosn^ of

' ?' : begin

{обработать символ операции ?}

inc(FPosn);

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

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

UnusedState, UnusedState);

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

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

StartStateAtom, EndStateAtom);

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

rcSetState(EndStateAtom, FTable.Count, UnusedState);

end;

' *' : begin

{обработать символ операции *}

inc(FPosn);

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