Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Сопоставление строк с регулярными выражениями

Сопоставление строк с регулярными выражениями

Пора решить заключительную часть задачи использования регулярных выражений - выполнить сопоставление с ними строк. Вместо того чтобы использовать уже рассмотренный алгоритм обратной трассировки, мы применим другой алгоритм. Используя входную строку, мы выполним обход конечного 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;

dec(FHead);

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

if (FTail = FHead) then

idGrow;

end;

function TtdIntDeque.Pop : integer;

begin

if FHead = FTail then

idError(tdeDequeIsEmpty, 'Pop');

Result := integer(FList.List^[FHead]);

inc(FHead);

if (FHead = FList.Count) then

FHead := 0;

end;

Алгоритм работает следующим образом. Поставим значение -1 в очередь с двусторонним доступом. Это специальное значение, которое указывает о необходимости выполнить считывание входной строки по одному элементу. Теперь поставим в очередь с двусторонним доступом номер исходного состояния. Установим целочисленное значение равным 0. Это значение будет индексом текущего символа в строке, сопоставление с которой выполняется.

После того, как подготовка закончена, мы входим в цикл. На каждом этапе выполнения цикла выполняется одно и то же действие: выталкивание верхнего значения из очереди. Если этим значением является -1 (как, естественно, это будет вначале), мы увеличиваем индекс текущего символа и извлекаем этот символ из сопоставляемой строки. Снова поставим значение -1 в очередь, чтобы знать, когда нужно выполнить считывание следующего символа. Если это значение не -1, оно должно быть реальным номером состояния. Взглянем на запись состояния в таблице переходов. Если текущий входной символ соответствует шаблону символов этого состояния, значение NextStatel состояния нужно поставить в очередь. Понятно, что если шаблоном символов состояния был е, символ не соответствовал шаблону. В этом случае в очередь с двусторонним доступом мы заталкиваем значение NextStatel, а затем значение NextState2.

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

Общий результат применения этого алгоритма состоит в том, что в очередь с двусторонним доступом помещается значение "извлечь следующий символ" (-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

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

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

Deque.Free;

end;

end;

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

Поэтому представим два новых символа операций регулярных выражений: символы операций привязки "^" и "$". Знак вставки "^" означает, что любое соответствие должно иметь место только с начала строки. Знак доллара "$" означает, что совпадение должно происходить на всем пути до самого конца строки. Так, например, регулярное выражение "^function" означает "совпадение со словом function с начала строки", a "^end.$" означает, что вся строка должна состоять из символов е, n, d и точки. Она не должна содержать никаких других символов. Символы ^ и $ могут присутствовать, соответственно, только в начале и конце регулярного выражения. Они не могут находиться ни в какой другой позиции.

Это обусловливает небольшое изменение определенных нами грамматических правил. Изменение не очень велико, но, как мы видели, корректная формулировка грамматических правил существенно упрощает создание кода. Код реализации нового правила и соответствующего метода синтаксического анализа приведен в листинге 10.16. Естественно, интерфейсный метод Parse также изменен, чтобы вызывать именно его, а не первоначальный метод.

Листинг 10.16. Использование операций привязки

{<anchorexpr> ::= <expr> | '^' <ехрr> | <expr> '$' | '^' <ехрr> '$'}

function TtdRegexEngine.rcParseAnchorExpr : integer;

begin

{проверить на наличие начального символа '^'}

if (FPosn^ = '^') then begin

FAnchorStart :=true;

inc(FPosn);

end;

{выполнить синтаксический анализ выражения}

Result := rcParseExpr;

{в случае успеха необходимо выполнить проверку на наличие конечного символа '$'}

if (Result <> ErrorState) then begin

if (FPosn^ = '$') then begin

FAnchorEnd := true;

inc(FPosn);

end;

end;

end;

Теперь код выполнения сопоставления строк можно изменить для сопоставления как целых строк, так и подстрок. Если регулярное выражение начинается с символа "А", нужно просто попытаться становить соответствие строки, начиная с первого символа. Если нет, необходимо попытаться установить соответствие с каждой из подстрок, образованных из исходной строки. Код метода MatchString, в котором принимается это решение, приведен в листинге 10.17.

Листинг 10.17. Метод MatchString

function TtdRegexEngine.MatchString(const S : string): integer;

var

i : integer;

ErrorPos : integer;

ErrorCode : TtdRegexError;

begin

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

if (FTable.Count = 0) then begin

if not Parse (ErrorPos, ErrorCode) then

rcError(tdeRegexParseError, 'MatchString', ErrorPos);

end;

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

Result := 0;

if (S <> '') then

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

if FAnchorStart then begin

if rcMatchSubString(S, 1) then

Result := 1;

end

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

else begin

for i := 1 to length(S) do

if rcMatchSubString (S, i) then begin

Result := i;

Break;

end;

end;

end;

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

Полный исходный код класса TtdRegexEngine можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRegex.pas.

Оглавление книги