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

Так как же, располагая определением грамматических правил и регулярным выражением, можно выполнить считывание символов строки и проверить регулярное выражение в целом на предмет соответствия грамматическим правилам? Проще всего создать для этого нисходящий синтаксический анализатор (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 Delphil) 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 Delphil)
FRegexStrZ := StrAlloc(succ( length (aRegexStr))) ; StrPCopy(FRegexStrZ, aRegexStr); {$ENDIF) end;
destructor TtdRegexParser.Destroy;
begin
{$IFDEF Delphil) StrDispose(FRegexStrZ); {$ENDIF)
inherited Destroy;
end;
function TtdRegexParser. Parse (var aErrorPos : integer) : boolean;
begin
Result := true;
aErrorPos := 0; {$IFDEF Delphil) FPosn := FRegexStrZ; {$ELSE)
FPosn : = PAnsiChar (FRegexStr);

{$ENDIF) try

rpParseExpr;
if (FPosnA <> #0) then begin
Result := false; {$IFDEF Delphi 1}
aErrorPos := FPosn - FRegexStrZ + 1; {$ELSE}
aErrorPos := FPosn - PAnsiChar(FRegexStr) + 1;
{$ENDIF] end;
except on E: Exception do begin
Result false;
{$IFDEF Delphi 1}
aErrorPos := FPosn - FRegexStrZ + 1; {$ELSE)
aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1; {$ENDIF) end;
end;
end;
procedure TtdRegexParser. rpParseAtom;
begin case FPosnA of 1 (' : begin
inc(FPosn);
writeln (1 Open paren') ;
rpParseExpr;

if (FPosnA <> ')') then raise Exception.Create('Regex error: expecting a closing

parenthesis1) ; inc(FPosn);
writeln (' close paren1) ;
end; 1 [' : begin
inc(FPosn);
if (FPosnA » 1A') then begin
inc(FPosn);
writeln('negated char class');
rpParseCharClass;
end
else begin
writeln('normal char class');
rpParseCharClass ;
end;
inc(FPosn);
end;
'.1 : begin
inc(FPosn);
writeln (1 any character1);
end;
else
rpParseChar;
end;{case} end;

procedure TtdRegexParser.rpParseCCChar; begin if (FPosnA = #0) then raise Exception. Create (

'Regex error: expecting a normal character, found null terminator') ; if FPosnA in [' ]', ' -' ] then raise Exception. Create (

'Regex error: expecting a normal character, found a metacharacter') ; if (FPosnA = 'V ) then begin inc(FPosn);
writeln (' escaped ccchar ', FPosnA) ; inc(FPosn);
end
else begin
writeln('ccchar ', FPosnA);
inc(FPosn);
end;
end;

procedure TtdRegexParser. rpParseChar; begin if (FPosnA = #0) then raise Exception. Create (

'Regex error: expecting a normal character, found null terminator') ; if FPosnA in Metacharacters then raise Exception. Create (

'Regex error: expecting a normal character, found a metacharacter' ) ; if (FPosnA = ' \') then begin inc(FPosn);
writeln (' escaped char ', FPosnA) ; inc(FPosn);
end
else begin
writeln('char ', FPosnA);
inc(FPosn);
end;
end;
procedure TtdRegexParser. rpParseCharClass;
begin
rpParseCharRange;
if (FPosnA о 4 ') then rpParseCharClass;
end;
procedure TtdRegexParser.rpParseCharRange;
begin
rpParseCCChar;
if (FPosnA = '-') then begin inc(FPosn);
writeln (1 -range to-1) ; rpParseCCChar;
end;
end;
procedure TtdRegexParser. rpParseExpr;
begin
rpParseTerm;
if (FPosnA = 1 Г ) then begin
inc(FPosn);
writeln('alternation');
rpParseExpr;
end;
end;
procedure TtdRegexParser. rpParseFactor;
begin rpParseAtom;
case FPosnA of '?1 : begin
inc(FPosn);
writeln(1 zero or one');
end; 1 *' : begin
inc(FPosn);
writeln(1 zero or more');
end; ' + ' : begin
inc(FPosn);
writeln(1 one or more');
end;
end;{case} end;
Полный исходный код класса TtdRegexParser можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRegex.pas;

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

Нам осталось только рассмотреть реализацию метода РагзеТегт. По сравнению с уже реализованными методами эта реализация несколько сложнее. Проблема состоит в том, что согласно формулировке продукции, <илен> является либо <коэффициентом>, либо <коэффициентом>, за которым следует еще один <член> (т.е. имеет место конкатенация). Не существует никакой операции, типа знака плюса или чего-то подобного, которая бы связывала два элемента. Если бы такая операция существовала, метод РагаеТепп можно было бы реализовать так же, как были реализованы остальные методы РагвеХхххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.

Рассмотрим проблему более внимательно. Предположим, что мы выполняем синтаксический анализ регулярного выражения паЬп. Его нужно было бы проанализировать в качестве <выражения>, что означает анализ в качестве <члена>, затем <коэффициента>, затем <элемента>, а затем <символа>. В результате была бы выполнена обработка фрагмента "а". Затем грамматический разбор был бы продолжен, пока снова не было бы достигнуто определение <члена>, в котором говорится, что за первым <коэффициентом> может следовать еще один <член>. Продолжая анализ продукции, мы идентифицируем фрагмент "Ь" как <символ>, и на этом выполнение задачи завершается.

Все сказанное звучит достаточно просто. Так в чем же трудность? Выполним эти же действия для выражения "(а)п. На этот раз синтаксический анализ продукций выполняется до тех пор, пока не будет достигнуто определение, согласно которому <элемент> может состоять из "(и, за которой следует <выражение>, а за ним ")п. Таким образом, обработка "С завершается и снова начинается с синтаксического анализа верхней грамматической конструкции - <выражения>. Снова выполним нисходящий анализ: <выражение>, затем <член>, затем <коэффициент>, затем <элемент> и, наконец, <символ>. В результате выполняется обработка фрагмента "а". Снова возвращаясь к началу, мы встречаем альтернативное определение продукции <член>. Так почему бы на этот раз нам не обратиться к альтернативной ветви и не попытаться выполнить синтаксический анализ конкатенации?

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

Этот процесс называют разрывом грамматического правша (breaking the grammar). Мы должны предположить, что если в данном случае конкатенация имеет место, текущий символ будет служить начальным символом олементах Иначе говоря, если текущий символ - w.w, n(n, или обычный символ, мы должны выполнить синтаксический анализ еще одного <члена>. Если же нет - мы считаем, что конкатенация отсутствует, и осуществляем выход из метода ParseTerm. Для определения того, что нужно делать с продукцией <член> (продукцией "более высокого" уровня), мы используем информацию продукции <элемент> (продукции "более низкого" уровня). Излишне повторять, что необходимость в таком подходе возникает только по причине отсутствия метасимвола конкатенации.

Код двух последних методов класса синтаксического анализатора регулярных выражений: метода ParseTerm и интерфейсного метода Parse показан в листинге 10.6.

Листинг 10.6. Методы ParseTerm и Parse

procedure TtdRegexParser. rpParseTerm;
begin rpParseFactor ; if (FPosnA - ' (') or (FPosnA - ' [ *) or (FPosnA - ' . 1) or
((FPosnA <> #0) and not (FPosnA in Metacharacters)) then rpParseTerm;
end;
function TtdRegexParser.Parse(var aErrorPos : integer) : boolean;
begin
Result := true;
aErrorPos := 0; {$IFDEF Delphi 1} FPosn :== FRegexStrZ; {$ELSE}
FPosn : = PAnsiChar(FRegexStr); {$ENDIF)
try
rpParseExpr;
if (FPosnA о #0) then begin
Result := false; {$IFDEF Delphi 1}
aErrorPos : = FPosn - FRegexStrZ + 1 ; {$ELSE}
aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1;
{$END1F} end;
except on E: Exception do begin
Result := false;
{$IFDEF Delphi 1}
aErrorPos : = FPosn - FRegexStrZ + 1 ; {$ELSE)
aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1; {$ENDIF) end;
end;
end;

Итак, мы научились выполнять синтаксический анализ регулярного выражения. Теперь мы может принять строку и вернуть информацию о том, образует ли она допустимое регулярное выражение.

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


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



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс