Walker := PNFAState(FTable[sdNextState1]);
end;
{выполнить проход по цепочке, указанной вторым следующим состоянием, и разорвать связи с состояниями, которые являются простыми одиночными бесплатными переходами}
if (sdNextState2 <> UnusedState) then begin
Walker := PNFAState(FTable[sdNextState2]);
while (Walker^.sdMatchType = mtNone) and
(Walker^.sdNextState2 = UnusedState) do
begin
sdNextState2 := Walker^.sdNextState1;
Walker := PNFAState(FTable[sdNextState2]);
end;
end;
end;
end;
end;
Пора решить заключительную часть задачи использования регулярных выражений - выполнить сопоставление с ними строк. Вместо того чтобы использовать уже рассмотренный алгоритм обратной трассировки, мы применим другой алгоритм. Используя входную строку, мы выполним обход конечного NFA-автомата (т.е. таблицы переходов), при этом одновременно отслеживая все возможные пути через конечный автомат. Со временем символы в строке будут исчерпаны, причем к этой точке будет вести один или более путей, либо возможных путей обработки строки больше не останется.
Однако для реализации этого алгоритма потребуется реализация очереди с двусторонним доступом (deque). Очередь с двусторонним доступом - это двусторонняя очередь, в которой постановку в очередь и исключение из очереди можно выполнять с любого конца. Нам потребуется возможность постановки элементов в конец очереди и их заталкивания в начало и из начала очереди (иначе говоря, исключение элементов из очереди должно выполняться только из ее начала и никогда из ее конца). Элементы, которые нужно будет ставить в очередь, представляют собой целочисленные значения (фактически, номера состояний). Код реализации этой простой очереди с двусторонним доступом показан в листинге 10.14 (его также можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDIntDeq.pas).
Листинг 10.14. Класс очереди целочисленных значений с двусторонним доступом type
TtdIntDeque = class private
FList : TList;
FHead : integer;
FTail : integer;
protected procedure idGrow;
procedure idError(aErrorCode : integer;
const aMethodName : TtdNameString);
public
constructor Create(aCapacity : integer);
destructor Destroy; override;
function IsEmpty : boolean;
procedure Enqueue(aValue : integer);
procedure Push(aValue : integer);
function Pop : integer;
end;
constructor TtdIntDeque.Create(aCapacity : integer);
begin
inherited Create;
FList := TList.Create;
FList.Count := aCapacity;
{для облегчения задачи пользователя очереди с двусторонним доступом поместить указатели начала и конца очереди в ее середину - вероятно, это более эффективно}
FHead := aCapacity div 2;
FTail := FHead;
end;
destructor TtdIntDeque.Destroy;
begin
FList.Free;
inherited Destroy;
end
procedure TtdIntDeque.Enqueue(aValue : integer);
begin