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

Что же должен делать метод 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

if (FPosn^ = #0) then

raise Exception.Create(

'Regex error: expecting a normal character, found null terminator');

if FPosn^ in Metacharacters then

raise Exception.Create(

'Regex error: expecting a normal character, found a metacharacter' );

if (FPosn^ = '\') then begin

inc(FPosn);

writeln (' escaped char ', FPosn^ );

inc(FPosn);

end

else begin

writeln('char ', FPosn^ );

inc(FPosn);

end;

end;

procedure TtdRegexParser.rpParseCharClass;

begin