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

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Ххххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.

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

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

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