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

Кодирование метода 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

rpParseCharRange;

if (FPosn^ <> ']') then

rpParseCharClass;

end;

procedure TtdRegexParser.rpParseCharRange;

begin

rpParseCCChar;

if (FPosn^ = '-') then begin

inc(FPosn);

writeln ('-—range to—-');

rpParseCCChar;

end;

end;

procedure TtdRegexParser.rpParseExpr;

begin

rpParseTerm;

if (FPosn^ = '|' ) then begin

inc(FPosn);

writeln('alternation');

rpParseExpr;

end;

end;

procedure TtdRegexParser.rpParseFactor;

begin

rpParseAtom;

case FPosn^ of

'?' : begin

inc(FPosn);

writeln(' zero or one');

end;

'*' : begin

inc(FPosn);

writeln(' zero or more');

end;

'+' : begin

inc(FPosn);

writeln(' one or more');

end;

end; {case}

end;

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

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