Общий результат применения этого алгоритма состоит в том, что в очередь с двусторонним доступом помещается значение "извлечь следующий символ" (-1). "Слева" от него располагается набор состояний, с которым нам по-прежнему необходимо сравнить текущий символ (мы постоянно выталкиваем из очереди эти состояния и помещаем в нее те, которых можно достичь за счет выполнения бесплатного перехода). "Справа" от него находятся состояния, полученные из тех, которые уже соответствуют текущему символу. Переход к ним будет осуществляться сразу после выталкивания значения -1 из очереди и извлечения следующего символа. Как видите, алгоритм одновременно проверяет все пути обхода конечного NFA-автомата.
Подпрограмма сопоставления приведена в листинге 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
{для сопоставления с любым символом необходимо поставить в очередь следующее состояние}