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

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

Листинг 10.12. Синтаксический анализ конкатенации

function TtdRegexEngine.rcParseTerm : integer;

var

StartState2 : integer;

EndState1 : integer;

begin

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

Result := rcParseFactor;

if (Result = ErrorState) then

Exit;

if (FPosn^ = '(') or (FPosn^ = '[') or (FPosn^ = '.') or

((FPosn^ <> #0) and not (FPosn^ in Metacharacters)) then begin

{конечное состояние исходного коэффициента еще не существует (хотя член и содержит состояние, которое указывает на него), поэтому его нужно создать}

EndState1 := rcAddState(mtNone, #0, nil, UnusedState, UnusedState);

{выполнить синтаксический анализ следующего члена}

StartState2 := rcParseTerm;

if (StartState2 = ErrorState) then begin

Result := ErrorState;

Exit;

end;

{объединить первый коэффициент со вторым членом}

rcSetState(EndState1, StartState2, UnusedState);

end;

end;

Естественно, состояния с единственным переходом для выхода приводят к нерациональной трате времени. Поэтому необходимо выполнить оптимизацию, исключив их из таблицы переходов. Такие состояния называются фиктивными.

Однако вместо того, чтобы их удалять, мы просто их пропустим. Соответствующий алгоритм достаточно прост: необходимо выполнить считывание всех состояний. Для каждого состояния необходимо следовать по ссылке, указанной в его поле NextStatel. Если она устанавливает связь с одним из фиктивных состояний, связь нужно заменить связью NextStatel фиктивного состояния. Это же потребуется выполнить для связи NextState2 каждого состояния, если она существует. Код выполнения этой итерационной процедуры приведен в листинге 10.13.

Листинг 10.13. Оптимизация фиктивных состояний

procedure TtdRegexEngine.rcLevel1Optimize;

var

i : integer;

Walker : PNFAState;

begin

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

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

for i := 0 to (FTable.Count - 2) do

begin {получить данное состояние}

with PNFAState (FTable [ i ])^ do

begin

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

Walker := PNFAState(FTable[sdNextState1]);

while (Walker^.sdMatchType = mtNone) and

(Walker^.sdNextState2 = UnusedState) do

begin

sdNextState1 := Walker^.sdNextState1;

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

FList.List^[FTail] := pointer(aValue);

inc(FTail);

if (FTail = FList.Count) then

FTail := 0;

if (FTail = FHead) then

idGrow;

end;

procedure TtdIntDeque.idGrow;

var

OldCount : integer;

i, j : integer;

begin

{увеличить размер списка на 50%}

OldCount := FList.Count;

FList.Count := (OldCount * 3) div 2;

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

if (FHead= 0) then

FTail := OldCount else begin

j := FList.Count;

for i := pred(OldCount) downto FHead do

begin

dec(j);

FList.List^[j] := FList.List^[i] end;

FHead := j;

end;

end;

function TtdIntDeque.IsEmpty : boolean;

begin

Result := FHead = FTail;

end;

procedure TtdIntDeque.Push(aValue : integer);

begin

if (FHead = 0) then

FHead := FList.Count;