Бакнелл Джулиан М.
Шрифт:
Подпрограмма сопоставления приведена в листинге 10.15. Она была создана в качестве метода машины обработки регулярных выражений. Ей передается строка, с которой должно быть выполнено сопоставление, и значение индекса. Значение индекса указывает позицию в строке, начиная с которой предположительно должно начинаться совпадение. Это позволяет использовать регулярное выражение для сопоставления с любой частью строки, а не со всей строкой, как делалось в приведенных простых примерах конечных автоматов. Метод будет возвращать значение true, если таблица переходов регулярного выражения соответствует строке, начиная с данной позиции.
Листинг 10.15. Сопоставление подстрок с таблицей переходов
function TtdRegexEngine.rcMatchSubString(const S : string;
StartPosn : integer): boolean;
var
Ch : AnsiChar;
State : integer;
Deque : TtdIntDeque;
StrInx : integer;
begin
{предположить, что сопоставление будет неудачным}
Result := false;
{создать очередь с двусторонним доступом}
Deque := TtdIntDeque.Create(64);
try
{поставить в очередь специальное значение, означающее начало сканирования}
Deque.Enqueue(MustScan);
{поставить в очередь первое состояние}
Deque.Enqueue(FStartState);
{подготовить индекс строки}
StrInx := StartPosn - 1;
{выполнять цикл до тех пор, пока очередь не будет пуста, или пока строка не закончится}
while (StrInx <= length (S)) and not Deque.IsEmpty do
begin {вытолкнуть верхнее состояние из очереди}
State := Deque.Pop;
{вначале выполнить обработку состояния "необходимо выполнить сканирование "}
if (State = MustScan) then begin
{если очередь пуста, вполне вероятно, что задача выполнена, поскольку не осталось никаких состояний для обработки новых символов}
if not Deque.IsEmpty then begin
{если строка не закончилась, нужно извлечь символ и снова поставить в очередь состояние "необходимо выполнить сканирование"}
inc(StrInx);
if (StrInx <= length(S)) then begin
Ch := S[StrInx];
Deque.Enqueue(MustScan);
end;
end;
end
{в противном случае необходимо обработать состояние}
else with PNFAState (FTable [ State ])^ do
begin
case sdMatchType of
mtNone : begin
{для бесплатных переходов необходимо заталкивать в очередь следующие состояния}
Deque.Push(sdNextState2);
Deque.Push(sdNextState1);
end;
mtAnyChar : begin
{для сопоставления с любым символом необходимо поставить в очередь следующее состояние}
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
{в случае достижения конечного состояния строка соответствует регулярному выражению, если регулярное выражение не содержало никакого символа привязки или достигнут конец строки}