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

Из листинга 10.7 видно, что в действительности при передаче номера специального состояния NewFinalState в качестве номера следующего состояния мы определяем ссылку на индекс следующего элемента, который должен быть добавлен в таблицу переходов. Конечно, этот элемент еще не существует, но мы предполагаем, что он будет существовать, или что произойдет что-либо еще, позволяющее определить новую ссылку.

Код реализации метода распознавания отдельного символа приведен в листинге 10.8. Снова обратившись к листингу 10.5, обратите внимание на то, как был изменен первоначальный метод синтаксического анализа символа. Во-первых, мы больше не генерируем никаких исключений или сообщений об ошибках. Вместо этого мы возвращаем номер специального состояния ErrorState. Мы также отслеживаем код ошибки для каждой происходящей ошибки. Если какие-либо ошибки отсутствуют, новое состояние добавляется в таблицу переходов и возвращается как результат выполнения функции. Естественно, это состояние является начальным состоянием данного выражения. В действительности эта подпрограмма - метод класса машины обработки регулярных выражений.

Листинг 10.8. Синтаксический анализ отдельного символа и добавление его состояния

function TtdRegexEngine.rcParseChar : integer;

var

Ch : AnsiChar;

begin

{если встречается конец строки, это является ошибкой}

if (FPosn^ = #0) then begin

Result := ErrorState;

FErrorCode := recSuddenEnd;

Exit;

end;

{если текущий символ - один из метасимволов, это ошибка}

if FPosn^ in Metacharacters then begin

Result := ErrorState;

FErrorCode := recMetaChar;

Exit;

end;

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

{.. если он является отмененным символом: вместо него нужно извлечь следующий символ}

if (FPosn^ = '\') then

inc(FPosn);

Ch := FPosn^;

Result := rcAddState(mtChar, Ch, nil, NewFinalState, UnusedState);

inc(FPosn);

end;

Это было достаточно просто, поэтому давайте рассмотрим другой, более сложный метод, который выполняет синтаксический анализ элемента. Первый случай - выражение заключенное в круглые скобки, - во многом подобен рассмотренному ранее: для него не нужно добавлять никакие новые состояния. Второй случай - класс символов или класс символов с отрицанием - определенно.нуждается в новом конечном автомате. Синтаксический анализ класса символов выполняется так же, как ранее (при этом он обрабатывается как набор диапазонов, каждый из которых может быть отдельным символом или двумя символами, разделенными дефисом). Однако на этот раз нужно записывать символы в класс. Для этого мы используем набор символов, распределенный в куче. Последним шагом является добавление в таблицу переходов нового состояния, которое распознает данный класс, подобно тому, как это было сделано для подпрограммы распознавания символов. Для заключительного случая, кроме уже рассмотренного конечного автомата для распознавания отдельного символа требуется конечный автомат для обработки символа операции "любой символ", т.е. точки ("."). Реализация этого конечного автомата достаточно проста: необходимо создать новое состояние, которое соответствует любому символу. Полный листинг подпрограммы синтаксического анализа элемента приведен в листинге 10.9. Как и в предыдущем случае, начальное состояние для этих выражений возвращается в качестве результата функции, а конечное состояние является виртуальным конечным состоянием.

Листинг 10.9. Синтаксический анализ <элемента> и вспомогательных компонентов

function TtdRegexEngine.rcParseAtom : integer;

var

MatchType : TtdNFAMatchType;

CharClass : PtdCharSet;

begin

case FPosn^ of

'(' : begin

{обработка открывающей круглой скобки}

inc(FPosn);

{синтаксический анализ всего регулярного выражения, заключенного в круглые скобки}

Result := rcParseExpr;

if (Result = ErrorState) then

Exit;

{если текущий символ не является закрывающей круглой скобкой, имеет место ошибка}

if (FPosn^ <> ')') then begin

FErrorCode := recNoCloseParen;

Result := ErrorState;

Exit;

end;

{обработка закрывающей круглой скобки}

inc(FPosn);

end;

'[':

begin

{обработка открывающей квадратной скобки}

inc(FPosn);

{если первый символ класса - ' ^' то класс является классом с отрицанием, в противном случае это обычный класс}

if (FPosn^ = '^') then begin

inc(FPosn);

MatchType := mtNegClass;

end

else begin

MatchType :=mtClass;

end;

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

New(CharClass);

CharClass^ := [];

if not rcParseCharClass (CharClass) then begin

Dispose(CharClass);

Result := ErrorState;

Exit;

end;

{обработка закрывающей квадратной скобки}

inc(FPosn);

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

Result := rcAddState(MatchType, #0, CharClass, NewFinalState, UnusedState);

end;

'.':

begin

{обработка метасимвола точки}

inc(FPosn);

{добавить новое состояние для лексемы 'любой символ'}

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

NewFinalState, UnusedState);

end;

else

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