52704.fb2 Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 184

Фундаментальные алгоритмы и структуры данных в Delphi - читать онлайн бесплатно полную версию книги . Страница 184

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