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

После ознакомления с этой конкретной конструкцией создание конечных автоматов для операций замыкания ("*", и+" и сложности не представляет. Важно только создавать состояния в правильном порядке. Рассмотрим код, приведенный в листинге 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);

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

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

NewFinalState, StartStateAtom);

end;

' + ' : begin

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

inc(FPosn);

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

rcAddState(mtNone, #0, nil, NewFinalState, StartStateAtom);

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

Result := StartStateAtom;

end;

else

Result := StartStateAtom;

end; {case}

end;

При выполнении ноля или одного замыкания (операции "?") нужно создать конечное состояние элементарного выражения, к которому применяется операция, и начальное состояние всего конечного автомата. Эти новые состояния связаны между собой, как показано на рис. 10.5.

При выполнении ноля или более замыканий (операции "*") задача еще проще: нужно создать только конечное состояние для элемента. Оно становится начальным состоянием всего выражения. При этом виртуальное конечное состояние является конечным состоянием выражения.

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

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

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

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

Листинг 10.12. Синтаксический анализ конкатенации

function TtdRegexEngine.rcParseTerm : integer;

var

StartState2 : integer;

EndState1 : integer;

begin

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

Result := rcParseFactor;

if (Result = ErrorState) then

Exit;

if (FPosn^ = '(') or (FPosn^ = '[') or (FPosn^ = '.') or

((FPosn^ <> #0) and not (FPosn^ in Metacharacters)) then begin

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

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

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

StartState2 := rcParseTerm;

if (StartState2 = ErrorState) then begin

Result := ErrorState;

Exit;

end;

{объединить первый коэффициент со вторым членом}

rcSetState(EndState1, StartState2, UnusedState);

end;

end;