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

Бакнелл Джулиан М.

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;

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

Однако вместо того, чтобы их удалять, мы просто их пропустим. Соответствующий алгоритм достаточно прост: необходимо выполнить считывание всех состояний. Для каждого состояния необходимо следовать по ссылке, указанной в его поле NextStatel. Если она устанавливает связь с одним из фиктивных состояний, связь нужно заменить связью NextStatel фиктивного состояния. Это же потребуется выполнить для связи NextState2 каждого состояния, если она существует. Код выполнения этой итерационной процедуры приведен в листинге 10.13.

Листинг 10.13. Оптимизация фиктивных состояний

procedure TtdRegexEngine.rcLevel1Optimize;

var

i : integer;

Walker : PNFAState;

begin

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

{циклически обработать все записи состояний, кроме последней}

for i := 0 to (FTable.Count - 2) do

begin {получить данное состояние}

with PNFAState (FTable [ i ])^ do

begin

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

Walker := PNFAState(FTable[sdNextState1]);

while (Walker^.sdMatchType = mtNone) and

(Walker^.sdNextState2 = UnusedState) do

begin

sdNextState1 := Walker^.sdNextState1;

Walker := PNFAState(FTable[sdNextState1]);

end;

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

if (sdNextState2 <> UnusedState) then begin

Walker := PNFAState(FTable[sdNextState2]);

while (Walker^.sdMatchType = mtNone) and

(Walker^.sdNextState2 = UnusedState) do

begin

sdNextState2 := Walker^.sdNextState1;

Walker := PNFAState(FTable[sdNextState2]);

end;

end;

end;

end;

end;

Сопоставление строк с регулярными выражениями

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