Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
end;
' + ' : begin
{обработать символ операции +}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать}
rcAddState(mtNone, #0, nil, NewFinalState, StartStateAtom);
{начальное состояние всего подвыражения регулярного выражения будет начальным состоянием элемента}
Result := StartStateAtom;
end;
else
Result := StartStateAtom;
end; {case}
end;
При выполнении ноля или одного замыкания (операции "?") нужно создать конечное состояние элементарного выражения, к которому применяется операция, и начальное состояние всего конечного автомата. Эти новые состояния связаны между собой, как показано на рис. 10.5.
При выполнении ноля или более замыканий (операции "*") задача еще проще: нужно создать только конечное состояние для элемента. Оно становится начальным состоянием всего выражения. При этом виртуальное конечное состояние является конечным состоянием выражения.
При выполнении одного или более замыканий (операции "+") задача почти столь же проста. Потребуется создать конечное состояние для элемента и связать его с начальным состоянием элемента (которое является также начальным состоянием выражения). При этом виртуальное конечное состояние снова является конечным состоянием выражения.
Теперь осталось написать код только для выполнения операции конкатенации. На рисунке 10.6 эта операция выглядит просто: конечное состояние первого подвыражения становится начальным состоянием второго, и эти подвыражения связаны одно с другим. На практике не все так просто. Конечное состояние первого выражения является виртуальным конечным состоянием, причем не существует никакой гарантии, что оно будет совпадать с начальным состоянием следующего выражения (в этом случае они были бы автоматически связаны). Нет, вместо этого необходимо создать конечное состояние первого выражения и связать его с начальным состоянием второго выражения. Код решения этой последней задачи, включая создание заключительного конечного состояния, приведен в листинге 10.12.
На данный момент мы успешно связали аспекты синтаксического анализа и компиляции, что позволяет принять регулярное выражение и выполнить его синтаксический анализ с целью генерации скомпилированной таблицы переходов. На этапе компиляции программа определит и сохранит начальное состояние полного конечного 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;
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. Это значение будет индексом текущего символа в строке, сопоставление с которой выполняется.
