Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл

Правила представления регулярных выражений, с которыми мы будем работать, показаны на рис. 10.5. Они записаны в стандартной форме BNF (Backu;

Naur Form - форма Бэкуса-Наура, БНФ). "::=" означает "определено как", а "|" означает "ИЛИ". Следовательно, первая строка означает следующее: <выражение> является либо <членом>, либо <членом>, за которым следует символ вертикальной черты, а за ним - еще одно <выражение>. Вторая строка означает: <член> - это либо <коэффициент>, либо <коэффициент> за которым следует <член>, и т.д. Это определение грамматических правил (они называются "грамматическими", поскольку определяют язык. Если обратиться к справочной системе Delphi, в ней можно найти грамматические правила языка Object Pascal. Они определены таким же образом.) может использоваться для генерирования подпрограммы вычисления регулярного выражения. Вскоре мы увидим, как это делается. А пока примите к сведению, что определение грамматических правил может использоваться для быстрой проверки того, что данное регулярное выражение является правильным.

Вероятно, лучше привести несколько примеров регулярных выражений. Это поможет понять их применение.

Рис.10.5.Грамматические правила составления регулярных выражений, представленные в форме БНФ

Это регулярное выражение соответствует имени идентификатора в языке Pascal. Первое заключенное в квадратные скобки подвыражение - класс символов, из определения которого следует, что первым символом строки, для которой будет устанавливаться соответствие, должна быть буква, прописная или строчная, или символ подчеркивания. Второе заключенное в квадратные скобки подвыражение - еще один класс символов, совпадающий с первым, за исключением того, что в него добавлены цифры. Этот шаблон может повторяться ноль или более раз (что определено символом * в конце регулярного выражения). Таким образом, этому регулярному выражению соответствует буква или символ подчеркивания, за которой следует ноль или более букв, символов подчеркивания или цифр.

(+|-)?[0-9]+(.[0-9]+)?

Это регулярное выражение соответствует представлению целого числа или числа с плавающей точкой в языке Pascal. Оно означает необязательный знак, одну или более цифр и необязательную дробную часть. Дробная часть состоит из десятичной точки, за которой следует одна или более цифр. Если дробная часть отсутствует, число является целым. Если она присутствует, число является числом с плавающей точкой.

{[^}]*}

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

Использование регулярных выражений

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

Синтаксический анализ регулярных выражений

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

Так как же, располагая определением грамматических правил и регулярным выражением, можно выполнить считывание символов строки и проверить регулярное выражение в целом на предмет соответствия грамматическим правилам? Проще всего создать для этого нисходящий синтаксический анализатор (top-down parser), который иногда еще называют рекурсивным нисходящим синтаксическим анализатором (recursive descent parser). При условии, что грамматические правила четко определены, эта задача достаточно проста.

При выполнении нисходящего синтаксического анализа каждая продукция (production) в грамматическом правиле становится отдельной подпрограммой. (продукция - это одно из определений грамматики, т.е. одна из строк, содержащих символ операции "::=".) Преобразуем первую продукцию грамматики (определяющую < выражение> ) в метод ParseExpr.

Что же должен делать метод ParseExpr? Продукция утверждает, что < выражение> - это либо отдельный <член>, либо <член>, за которым следует символ вертикальной черты, а за ним еще один <член>. Предположим, что существует метод ParseTerm, который выполняет синтаксический анализ <члена>. В любом случае, прежде всего, необходимо вызвать эту подпрограмму для выполнения синтаксического анализа <члена>. Если после возврата из нее текущим символом является символ вертикальной черты, необходимо продолжить и рекурсивно вызвать подпрограмму ParseExpr, чтобы выполнить синтаксический анализ следующего выражениях Это все, что касается подпрограммы ParseExpr.

На некоторое время оставим без внимания реализацию метода ParseTerm (вскоре станет понятно, почему) и рассмотрим метод ParseFactor, выполняющий синтаксический анализ коэффициентах Как и в предыдущем случае, код достаточно прост. Вначале необходимо выполнить синтаксический анализ < элемента> путем вызова метода ParseAtom, а затем выполнить проверку на наличие одного из трех метасимволов: "*", "+" или "?". {Метасимвол - это символ, имеющий специальное значение с точки зрения грамматических правил - например, звездочка, знак плюса, круглые скобки и т.п. Другие символы не имеют никакого специального значения.}

Кодирование метода ParseAtom достаточно тривиально. Элемент может быть < символом> или точкой;

открывающей круглой скобкой, за которой следуют < выражение> и закрывающая круглая скобка;

открывающей квадратной скобкой, за которой следуют < класс символов> и закрывающая квадратная скобка;

открывающей квадратной скобкой, за которой следуют символ "А", <класс символов> и закрывающая квадратная скобка. Именно эту форму мы и реализуем в коде. Остальные методы, реализующие другие продукции, столь же просты. Обратите внимание, что в этих методах реальную проверку выполняет метод самого нижнего уровня. Например, метод ParseAtom будет проверять наличие закрывающей круглой скобки после того, как в результате синтаксического анализа обнаружены открывающая круглая скобка и <выражение>. Метод PacseChar удостоверяется, что текущий символ не является метасимволом. И так далее. Код, созданный в соответствии с приведенными рассуждениями, можно найти в листинге 10.5.

Листинг 10.5. Программа синтаксического анализа регулярных выражений type

TtdRegexParser = class private

FRegexStr : string;

{$IFDEF Delphi1}

FRegexStrZ: PAnsiChar;

{$ENDIF}

FPosn : PAnsiChar;

protected

procedure rpParseAtom;

procedure rpParseCCChar;

procedure rpParseChar;

procedure rpParseCharClass;

procedure rpParseCharRange;

procedure rpParseExpr;

procedure rpParseFactor;

procedure rpParseTerm;

public

constructor Create(const aRegexStr : string);

destructor Destroy; override;

function Parse(var aErrorPos : integer): boolean;

end;

constructor TtdRegexParser.Create(const aRegexStr : string);

begin

inherited Create;

FRegexStr := aRegexStr;

{$IFDEF Delphi1}

FRegexStrZ := StrAlloc(succ( length (aRegexStr)));

StrPCopy(FRegexStrZ, aRegexStr);

{$ENDIF}

end;

destructor TtdRegexParser.Destroy;

begin

{$IFDEF Delphi1}

StrDispose(FRegexStrZ);

{$ENDIF}

inherited Destroy;

end;

function TtdRegexParser.Parse(var aErrorPos : integer): boolean;

begin

Result := true;

aErrorPos := 0;

{$IFDEF Delphi1}

FPosn := FRegexStrZ;

{$ELSE}

FPosn := PAnsiChar (FRegexStr);

{$ENDIF}

try

rpParseExpr;

if (FPosn^ <> #0) then begin

Result := false;

{$IFDEF Delphi1}

aErrorPos := FPosn - FRegexStrZ + 1;

{$ELSE}

aErrorPos := FPosn - PAnsiChar(FRegexStr) + 1;

{$ENDIF}

end;

except on E: Exception do

begin

Result false;

{$IFDEF Delphi1}

aErrorPos := FPosn - FRegexStrZ + 1;

{$ELSE}

aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1;

{$ENDIF}

end;

end;

end;

procedure TtdRegexParser.rpParseAtom;

begin

case FPosn^ of

'(' : begin

inc(FPosn);

writeln (' Open paren');

rpParseExpr;

if (FPosn^ <> ')') then

raise Exception.Create('Regex error: expecting a closing parenthesis');

inc(FPosn);

writeln (' close paren');

end;

'[' : begin

inc(FPosn);

if (FPosn^ = 'A') then begin

inc(FPosn);

writeln('negated char class');

rpParseCharClass;

end

else begin

writeln('normal char class');

rpParseCharClass;

end;

inc(FPosn);

end;

'.' : begin

inc(FPosn);

writeln (' any character');

end;

else

rpParseChar;

end; {case}

end;

procedure TtdRegexParser.rpParseCCChar;

begin

if (FPosn^ = #0) then

raise Exception.Create('Regex error: expecting a normal character, found null terminator');

if FPosn^ in [']', '-'] then

raise Exception.Create('Regex error: expecting a normal character, found a metacharacter');

if (FPosn^ = '') then begin

inc(FPosn);

writeln(' escaped ccchar ', FPosn^ );

inc(FPosn);

end

else begin

writeln('ccchar ', FPosn^ );

inc(FPosn);

end;

end;

procedure TtdRegexParser.rpParseChar;

begin