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

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

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

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

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

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

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

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

procedure TtdRegexParser.rpParseTerm;

begin

rpParseFactor;

if (FPosn^ = '(') or (FPosn^ = '[') or (FPosn^ = '.') or

((FPosn^ <> #0) and not (FPosn^ in Metacharacters)) then

rpParseTerm;

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;

{$END1F}

end;

except on E: Exception do

begin

Result := false;

{$IFDEF Delphi1}

aErrorPos := FPosn - FRegexStrZ + 1;

{$ELSE}

aErrorPos := FPosn - PAnsiChar (FRegexStr) + 1;