Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 28 (всего у книги 36 страниц)
Существует три этапа использования регулярного выражения. На первом регулярное выражение разбивается на составляющие его лексемы, на втором они преобразуются форму, пригодную для установки соответствия (компиляция регулярного выражения) и на заключительном этапе скомпилированная форма регулярного выражения используется для собственно установки соответствия со строками. Этот материал изложен в данной главе потому, что скомпилированная форма регулярного выражения реализуется в виде NFA-автомата.
Синтаксический анализ регулярных выражений
Последовательно рассмотрим три упомянутых выше этапа. В первую очередь необходимо решить проблему синтаксического анализа данной строки регулярного выражения. Целью этого процесса является простая проверка того, что строка регулярного выражения соответствует синтаксису, определенному грамматическими правилами.
Так как же, располагая определением грамматических правил и регулярным выражением, можно выполнить считывание символов строки и проверить регулярное выражение в целом на предмет соответствия грамматическим правилам? Проще всего создать для этого нисходящий синтаксический анализатор (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 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Ххххх. Однако, поскольку никакого метасимвола выполнения конкатенации не существует, приходится прибегнуть к другому средству.
Рассмотрим проблему более внимательно. Предположим, что мы выполняем синтаксический анализ регулярного выражения "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, содержит конструкции, имеющие наибольшее значение.
Первый пример – конечный автомат, выполняющий распознавание отдельного символа алфавита. Второй пример столь же прост: он представляет собой конечный автомат, выполняющий распознавание любого символа алфавита (другими словами, это операция "."). Четвертая конструкция служит иллюстрацией того, как выполняется конкатенация (одного выражения, за которым следует второе). При этом мы просто объединяем начальное состояние второго подвыражения с конечным состоянием первого. Следующей показана конструкция, выполняющая дизъюнкцию. Мы создаем новое начальное состояние и получаем два возможных бесплатных перехода, по одному для каждого из подвыражений. Конечное состояние первого подвыражения объединяется с конечным состоянием второго подвыражения, и это последнее состояние становится конечным состоянием всего выражения. Следующий конечный автомат реализует операцию "?": в данном случае мы создаем новое начальное состояние с двумя ветвями е;
первая выполняет соединение с начальным состоянием подвыражения, а вторая – с его конечным состоянием. Это конечное состояние является конечным состоянием всего выражения. Вероятно, наиболее сложными конструкциями являются конечные автоматы для выполнения операций "+" и "*".
Рисунок 10.6. Конечные NFA-автоматы выполнения операций в регулярных выражениях
Если вы взглянете на рис. 10.6, то наверняка обратите внимание на ряд интересных свойств. В некоторых конструкциях для создания конечных автоматов определены и используются дополнительные состояния, но это делается вполне определенным образом: для каждого состояния существует один или два перехода из него, причем оба являются бесплатными. Это обусловлено веской причиной – в результате кодирование существенно упрощается.
Рассмотрим простой пример: регулярное выражение "(а|b)*bc" (повторенный ноль или более раз символ а или b, за которым следуют символы b и с). Используя описанные конструкции, можно шаг за шагом состроить конечный NFA-автомат для этого регулярного выражения. Последовательность действий показана на рис. 10.7. Обратите внимание, что на каждом шаге мы получаем конечный NFA-автомат с одним начальным и одним конечным состоянием, причем из каждого нового создаваемого состояния возможно не более двух переходов.
Рисунок 10.7. Пошаговое построение конечного NFA-автомата
Благодаря используемому методу конструирования, можно создать очень простое табличное представление каждого состояния. Каждое состояние будет представлено записью в массиве таких записей (номер состояния является индексом записи в массиве). Запись каждого состояния будет состоять из чего-либо для сравнения и двух номеров состояний для следующего состояния (NextStatel, NextState2). «Что-либо для сравнения» – это шаблон символов, с которым нужно устанавливать соответствие. Им может быть ветвь е, реальный символ, символ операции означающий соответствие с любым символом, класс символов (т.е. набор символов, один из которых должен совпадать с входным символом) или класс символов с отрицанием (входной символ не может быть частью набора, с которым устанавливается соответствие). Будучи построенным, этот массив известен под названием таблицы переходов (trAnsition table). В ней представлены все переходы из одного состояния в другое.
Используя заключительную блок-схему NFA-автомата, показанную на рис. 10.7, можно вручную построить таблицу переходов для регулярного выражения "(a|b)*bc". Результат приведен в таблице 10.1. Мы начинаем с состояния 0 и осуществляем переходы, выполняя сравнение с каждым символом во входной строке, пока не достигнем состояния 7. Реализация алгоритма установки соответствия, использующего подобную таблицу переходов, должна быть очень простой.
Таблица 10.1. Таблица переходов для выражения (a|b)*bc
Теперь, когда мы научились графически представлять NFA-автомат для конкретного регулярного выражения и узнали, что этот конечный NFA-автомат может быть представлен простой таблицей переходов, необходимо объединить оба алгоритма в анализаторе регулярных выражений, чтобы он мог выполнять непосредственную компиляцию таблицы состояний. После этого можно будет приступить к рассмотрению заключительной задачи – сопоставлению строк за счет использования таблицы переходов.
Прежде всего, необходимо выбрать способ представления таблицы состояний. Наиболее очевидный выбор – использование класса TtdRecordList, описанного в главе 2. Этот класс позволяет при необходимости увеличивать размер внутреннего массива. При этом заранее не нужно определять, сколько состояний может существовать для данного регулярного выражения.
В качестве подсказки будем использовать отдельные конструктивные блоки, показанные на рис. 10.6. Простейшим является выражение, которое распознает отдельный символ. Как видно из первой части рисунка 10.6, нам требуется начальное состояние, в котором будет выполняться распознавание символа, и которое будет иметь единственную связь с конечным состоянием (каждый из этих элементов будет также требоваться). Создадим простую подпрограмму, которая будет создавать новое состояние (как запись) и дописывать его в таблицу переходов. Код реализации этого простого метода приведен в листинге 10.7. Как видите, он принимает тип соответствия, символ, указатель на класс символов и две связи с другими состояниями. Конечно, не все из этих параметров будут требоваться для каждого создаваемого состояния. Но проще использовать один метод, который может создавать любой тип записи состояния, нежели целый набор таких методов, по одному для каждого возможного типа состояния.
Листинг 10.7. Добавление нового состояния в таблицу состояний
function TtdRegexEngine.rcAddState( aMatchType : TtdNFAMatchType;
aChar : AnsiChar; aCharClass : PtdCharSet;
aNextStatel: integer; aNextState2: integer): integer;
var
StateData : TNFAState;
begin
{определить поля в записи состояния}
if (aNextStatel = NewFinalState) then
StateData.sdNextState1 := succ(FTable.Count) else
StateData.sdNextState1 := aNextStatel;
StateData.sdNextState2 := aNextState2;
StateData.sdMatchType := aMatchType;
if (aMatchType = mtChar) then
StateData.sdChar := aChar else
if (aMatchType = mtClass) or (aMatchType = mtNegClass) then
StateData.sdClass := aCharClass;
{добавить новое состояние}
Result := FTable.Count;
FTable.Add(@StateData);
end;
При взгляде на первую часть рисунка 10.6 кажется, что для этой простой подпрограммы распознавания символа нужно создать два новых состояния. В действительности же можно ограничиться созданием только одного – начального состояния – и принять, что конечным состоянием будет следующее состояние, которое требуется добавить в список. Будем считать его «виртуальным» конечным состоянием. Если бы этот подход удалось применить в каждой из подпрограмм синтаксического анализа, можно было бы избавиться от необходимости создания конечного состояния, эквивалентного начальному состоянию другого подвыражения. Поэтому с этого момента будем считать, что все подпрограммы синтаксического анализа будут возвращать свое начальное состояние, и что конечное состояние, если оно действительно существует, будет номером индекса следующего состояния, которое необходимо добавить в таблицу переходов.
Из листинга 10.7 видно, что в действительности при передаче номера специального состояния NewFinalState в качестве номера следующего состояния мы определяем ссылку на индекс следующего элемента, который должен быть добавлен в таблицу переходов. Конечно, этот элемент еще не существует, но мы предполагаем, что он будет существовать, или что произойдет что-либо еще, позволяющее определить новую ссылку.
Код реализации метода распознавания отдельного символа приведен в листинге 10.8. Снова обратившись к листингу 10.5, обратите внимание на то, как был изменен первоначальный метод синтаксического анализа символа. Во-первых, мы больше не генерируем никаких исключений или сообщений об ошибках. Вместо этого мы возвращаем номер специального состояния ErrorState. Мы также отслеживаем код ошибки для каждой происходящей ошибки. Если какие-либо ошибки отсутствуют, новое состояние добавляется в таблицу переходов и возвращается как результат выполнения функции. Естественно, это состояние является начальным состоянием данного выражения. В действительности эта подпрограмма – метод класса машины обработки регулярных выражений.
Листинг 10.8. Синтаксический анализ отдельного символа и добавление его состояния
function TtdRegexEngine.rcParseChar : integer;
var
Ch : AnsiChar;
begin
{если встречается конец строки, это является ошибкой}
if (FPosn^ = #0) then begin
Result := ErrorState;
FErrorCode := recSuddenEnd;
Exit;
end;
{если текущий символ – один из метасимволов, это ошибка}
if FPosn^ in Metacharacters then begin
Result := ErrorState;
FErrorCode := recMetaChar;
Exit;
end;
{в противном случае состояние, соответствующее символу, добавляется в таблицу состояний}
{.. если он является отмененным символом: вместо него нужно извлечь следующий символ}
if (FPosn^ = '') then
inc(FPosn);
Ch := FPosn^;
Result := rcAddState(mtChar, Ch, nil, NewFinalState, UnusedState);
inc(FPosn);
end;
Это было достаточно просто, поэтому давайте рассмотрим другой, более сложный метод, который выполняет синтаксический анализ элемента. Первый случай – выражение заключенное в круглые скобки, – во многом подобен рассмотренному ранее: для него не нужно добавлять никакие новые состояния. Второй случай – класс символов или класс символов с отрицанием – определенно.нуждается в новом конечном автомате. Синтаксический анализ класса символов выполняется так же, как ранее (при этом он обрабатывается как набор диапазонов, каждый из которых может быть отдельным символом или двумя символами, разделенными дефисом). Однако на этот раз нужно записывать символы в класс. Для этого мы используем набор символов, распределенный в куче. Последним шагом является добавление в таблицу переходов нового состояния, которое распознает данный класс, подобно тому, как это было сделано для подпрограммы распознавания символов. Для заключительного случая, кроме уже рассмотренного конечного автомата для распознавания отдельного символа требуется конечный автомат для обработки символа операции «любой символ», т.е. точки ("."). Реализация этого конечного автомата достаточно проста: необходимо создать новое состояние, которое соответствует любому символу. Полный листинг подпрограммы синтаксического анализа элемента приведен в листинге 10.9. Как и в предыдущем случае, начальное состояние для этих выражений возвращается в качестве результата функции, а конечное состояние является виртуальным конечным состоянием.
Листинг 10.9. Синтаксический анализ <элемента> и вспомогательных компонентов
function TtdRegexEngine.rcParseAtom : integer;
var
MatchType : TtdNFAMatchType;
CharClass : PtdCharSet;
begin
case FPosn^ of
'(' : begin
{обработка открывающей круглой скобки}
inc(FPosn);
{синтаксический анализ всего регулярного выражения, заключенного в круглые скобки}
Result := rcParseExpr;
if (Result = ErrorState) then
Exit;
{если текущий символ не является закрывающей круглой скобкой, имеет место ошибка}
if (FPosn^ <> ')') then begin
FErrorCode := recNoCloseParen;
Result := ErrorState;
Exit;
end;
{обработка закрывающей круглой скобки}
inc(FPosn);
end;
'[':
begin
{обработка открывающей квадратной скобки}
inc(FPosn);
{если первый символ класса – ' ^' то класс является классом с отрицанием, в противном случае это обычный класс}
if (FPosn^ = '^') then begin
inc(FPosn);
MatchType := mtNegClass;
end
else begin
MatchType :=mtClass;
end;
{выделить набор символов класса и выполнить синтаксический анализ класса символов; в результате возврат будет выполнен либо в случае сшибки, либо при обнаружении закрывающей квадратной скобки}
New(CharClass);
CharClass^ := [];
if not rcParseCharClass (CharClass) then begin
Dispose(CharClass);
Result := ErrorState;
Exit;
end;
{обработка закрывающей квадратной скобки}
inc(FPosn);
{добавить новое состояние для класса символов}
Result := rcAddState(MatchType, #0, CharClass, NewFinalState, UnusedState);
end;
'.':
begin
{обработка метасимвола точки}
inc(FPosn);
{добавить новое состояние для лексемы 'любой символ'}
Result := rcAddState(mtAnyChar, #0, nil,
NewFinalState, UnusedState);
end;
else
{в противном случае – выполнить синтаксический анализ отдельного символа}
Result := rcParseChar;
end; {case}
end;
До сих пор мы создавали состояния без каких-либо ссылок состояний друг на друга. Но если вы обратитесь к блок-схеме конечного NFA-автомата для операции п|", то увидите, что, в конце концов, некоторые состояния приходится объединять друг с другом. Необходимо сохранить начальные состояния для каждого подвыражения и нужно создать новое начальное состояние, которое будет связано бесплатными связями с каждым из этих двух состояний. Заключительное состояние первого подвыражения должно быть связано с заключительным состоянием второго подвыражения, которое после этого становится конечным состоянием выражения дизъюнкции.
Однако это сопряжено с небольшой проблемой. Заключительное состояние для первого выражения не существует. Поэтому его нужно создать, но это следует сделать осторожно, чтобы остальные состояния не стали ошибочно указывать на него.
Естественно, прежде всего, необходимо выполнить синтаксический анализ исходного <члена>. Мы получим начальное состояние (поэтому сохраним его в переменной). При этом известно, что конечное состояние является виртуальным конечным состоянием, следующим непосредственно за концом списка. Если следующим символом является " |", это свидетельствует о выполнении синтаксического анализа дизъюнктивной конструкции и о необходимости синтаксического анализа следующего <выражения>. Именно здесь нужно проявить повышенную осторожность. Перво-наперво, мы создаем состояние для конечного состояния этого исходного <члена>. В данный момент, нас не волнует, на какие состояния указывают его связи. Вскоре они будут исправлены. Создание этого конечного состояния означает также, что любые состояния в <члене>, указывающие на виртуальное конечное состояние, фактически будут указывать на состояние, которое мы только что сделали реальным. Теперь нужно создать начальное состояние дизъюнкции. Нам известна одна из связей (исходный <член> ), но еще не известна вторая. В конце концов, синтаксический анализ второго < выражения> еще не был выполнен. Теперь мы можем его выполнить. Мы получим начальное состояние, которое используем для исправления второй связи в начальном состоянии дизъюнкции. Новое виртуальное конечное состояние может быть использовано для создания связи, исходящей из конечного состояния исходного <члена>.
В результате выполнения всех этих манипуляций нам пришлось создать два новых состояния (первое является начальным состоянием для дизъюнкции, а второе -конечным состоянием исходного <члена> ). При этом мы проявили достаточную осмотрительность, чтобы виртуальное конечное состояние второго < выражения> было виртуальным конечным состоянием всей операции дизъюнкции. Код реализации этого конечного автомата приведен в листинге 10.10 (обратите внимание, что был создан еще один метод, который определяет связи для состояния после его создания).
Листинг 10.10. Синтаксический анализ операции "|"
function TtdRegexEngine.rcSetState(aState : integer;
aNextStatel: integer;
aNextState2: integer): integer;
var
StateData : PNFAState;
begin
{извлечь запись состояния и изменить информацию о переходе}
StateData := PNFAState(FTable[aState])/ StateData^.sdNextState1 := aNextStatel/ StateData^.sdNextState2 := aNextState2;
Result := aState;
end;
fmiction TtdRegexEngine.rcParseExpr : integer;
var
StartStatel : integer;
StartState2 : integer;
EndState1 : integer;
OverallStartState : integer;
begin
{предположим, что имеет место наихудший случай}
Result ErrorState;
{выполнить синтаксический анализ исходного члена}
StartStatel := rcParseTerm;
if (StartStatel = ErrorState) then
Exit;
{если текущий символ является *не* символом вертикальной черты, дизъюнкция отсутствует, поэтому начальное состояние исходного члена необходимо вернуть в качестве текущего начального состояния}
if (FPosn^ <> '|') then
Result := StartStatel {в противном случае необходимо выполнить синтаксический анализ второго выражения и объединить их в таблице переходов}
