открывающей квадратной скобкой, за которой следуют символ "А", <класс символов> и закрывающая квадратная скобка. Именно эту форму мы и реализуем в коде. Остальные методы, реализующие другие продукции, столь же просты. Обратите внимание, что в этих методах реальную проверку выполняет метод самого нижнего уровня. Например, метод 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-автомата, а второе - потому, что исключения не следует использовать для проверки, поскольку это слишком неэффективно. Тем не менее, этот код может служить иллюстрацией общей структуры упрощенного нисходящего синтаксического анализатора: вначале выполняется разработка грамматических правил, а затем достаточно простым образом они преобразуются в код.
Нам осталось только рассмотреть реализацию метода ParseTerm. По сравнению с уже реализованными методами эта реализация несколько сложнее. Проблема состоит в том, что согласно формулировке продукции, <член> является либо <коэффициентом>, либо <коэффициентом>, за которым следует еще один <член> (т.е. имеет место конкатенация). Не существует никакой операции, типа знака плюса или чего-то подобного, которая бы связывала два элемента. Если бы такая операция существовала, метод ParseTerm можно было бы реализовать так же, как были реализованы остальные методы ParseХхххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.