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

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

Deque.Enqueue(sdNextState1);

end;

mtChar : begin

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

if (Ch = sdChar) then

Deque.Enqueue(sdNextState1);

end;

mtClass : begin

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

if (Ch in sdClass^ ) then

Deque.Enqueue(sdNextState1);

end;

mtNegClass : begin

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

if not (Ch in sdClass^ ) then

Deque.Enqueue(sdNextState1);

end;

mtTerminal : begin

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

if (not FAnchorEnd) or (StrInx > length(S)) then begin

Result := true;

Exit;

end;

end;

end;

end;

end;

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

while not Deque.IsEmpty do

begin

State := Deque.Pop;

with PNFAState (FTable [ State ])^ do

begin

case sdMatchType of

mtNone : begin

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

Deque.Push(sdNextState2);

Deque.Push(sdNextState1);

end;

mtTerminal : begin

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

if (not FAnchorEnd) or (StrInx > length(S)) then begin

Result := true;

Exit;

end;

end;

end; {case}

end;

end;

finally

Deque.Free;

end;

end;

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

Поэтому представим два новых символа операций регулярных выражений: символы операций привязки "^" и "$". Знак вставки "^" означает, что любое соответствие должно иметь место только с начала строки. Знак доллара "$" означает, что совпадение должно происходить на всем пути до самого конца строки. Так, например, регулярное выражение "^function" означает "совпадение со словом function с начала строки", a "^end.$" означает, что вся строка должна состоять из символов е, n, d и точки. Она не должна содержать никаких других символов. Символы ^ и $ могут присутствовать, соответственно, только в начале и конце регулярного выражения. Они не могут находиться ни в какой другой позиции.

Это обусловливает небольшое изменение определенных нами грамматических правил. Изменение не очень велико, но, как мы видели, корректная формулировка грамматических правил существенно упрощает создание кода. Код реализации нового правила и соответствующего метода синтаксического анализа приведен в листинге 10.16. Естественно, интерфейсный метод Parse также изменен, чтобы вызывать именно его, а не первоначальный метод.

Листинг 10.16. Использование операций привязки

{ ::= | '^' <ехрr> | '$' | '^' <ехрr> '$'}

function TtdRegexEngine.rcParseAnchorExpr : integer;

begin

{проверить на наличие начального символа '^'}

if (FPosn^ = '^') then begin

FAnchorStart :=true;

inc(FPosn);

end;

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

Result := rcParseExpr;

{в случае успеха необходимо выполнить проверку на наличие конечного символа '$'}

if (Result <> ErrorState) then begin

if (FPosn^ = '$') then begin

FAnchorEnd := true;

inc(FPosn);

end;

end;

end;

Теперь код выполнения сопоставления строк можно изменить для сопоставления как целых строк, так и подстрок. Если регулярное выражение начинается с символа "А", нужно просто попытаться становить соответствие строки, начиная с первого символа. Если нет, необходимо попытаться установить соответствие с каждой из подстрок, образованных из исходной строки. Код метода MatchString, в котором принимается это решение, приведен в листинге 10.17.

Листинг 10.17. Метод MatchString

function TtdRegexEngine.MatchString(const S : string): integer;

var

i : integer;

ErrorPos : integer;

ErrorCode : TtdRegexError;

begin

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

if (FTable.Count = 0) then begin

if not Parse (ErrorPos, ErrorCode) then

rcError(tdeRegexParseError, 'MatchString', ErrorPos);

end;

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

Result := 0;

if (S <> '') then

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

if FAnchorStart then begin

if rcMatchSubString(S, 1) then

Result := 1;

end