Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
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Ххххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.
Рассмотрим проблему более внимательно. Предположим, что мы выполняем синтаксический анализ регулярного выражения "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;
{$ENDIF}
end;
end;
end;
Итак, мы научились выполнять синтаксический анализ регулярного выражения. Теперь мы может принять строку и вернуть информацию о том, образует ли она допустимое регулярное выражение.
Компиляция регулярных выражений
Следующий шаг состоит в создании NFA-автомата для регулярного выражения. Решение этой задачи мы начнем с создания блок-схемы конечного автомата выполнения регулярного выражения. Создание блок-схемы конечного автомата для конкретного регулярного выражения - достаточно простая задача. В общем случае правила языка утверждают, что регулярное выражение состоит из различных подвыражений (которые сами являются регулярными выражениями), скомпонованных или объединенных различными способами. Каждое подвыражение имеет единственное начальное состояние и единственное конечное состояние. И подобно тому, как это делается в конструкторе "Лего", эти простые строительные блоки собираются воедино, образуя все регулярное выражение. Блок-схема, приведенная на рис. 10.6, содержит конструкции, имеющие наибольшее значение.
Первый пример - конечный автомат, выполняющий распознавание отдельного символа алфавита. Второй пример столь же прост: он представляет собой конечный автомат, выполняющий распознавание любого символа алфавита (другими словами, это операция "."). Четвертая конструкция служит иллюстрацией того, как выполняется конкатенация (одного выражения, за которым следует второе). При этом мы просто объединяем начальное состояние второго подвыражения с конечным состоянием первого. Следующей показана конструкция, выполняющая дизъюнкцию. Мы создаем новое начальное состояние и получаем два возможных бесплатных перехода, по одному для каждого из подвыражений. Конечное состояние первого подвыражения объединяется с конечным состоянием второго подвыражения, и это последнее состояние становится конечным состоянием всего выражения. Следующий конечный автомат реализует операцию "?": в данном случае мы создаем новое начальное состояние с двумя ветвями е;
