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-автомата для операции п|", то увидите, что, в конце концов, некоторые состояния приходится объединять друг с другом. Необходимо сохранить начальные состояния для каждого подвыражения и нужно создать новое начальное состояние, которое будет связано бесплатными связями с каждым из этих двух состояний. Заключительное состояние первого подвыражения должно быть связано с заключительным состоянием второго подвыражения, которое после этого становится конечным состоянием выражения дизъюнкции.
Однако это сопряжено с небольшой проблемой. Заключительное состояние для первого выражения не существует. Поэтому его нужно создать, но это следует сделать осторожно, чтобы остальные состояния не стали ошибочно указывать на него.
Естественно, прежде всего, необходимо выполнить синтаксический анализ исходного <члена>. Мы получим начальное состояние (поэтому сохраним его в переменной). При этом известно, что конечное состояние является виртуальным конечным состоянием, следующим непосредственно за концом списка. Если следующим символом является " |", это свидетельствует о выполнении синтаксического анализа дизъюнктивной конструкции и о необходимости синтаксического анализа следующего <выражения>. Именно здесь нужно проявить повышенную осторожность. Перво-наперво, мы создаем состояние для конечного состояния этого исходного <члена>. В данный момент, нас не волнует, на какие состояния указывают его связи. Вскоре они будут исправлены. Создание этого конечного состояния означает также, что любые состояния в <члене>, указывающие на виртуальное конечное состояние, фактически будут указывать на состояние, которое мы только что сделали реальным. Теперь нужно создать начальное состояние дизъюнкции. Нам известна одна из связей (исходный <член> ), но еще не известна вторая. В конце концов, синтаксический анализ второго < выражения> еще не был выполнен. Теперь мы можем его выполнить. Мы получим начальное состояние, которое используем для исправления второй связи в начальном состоянии дизъюнкции. Новое виртуальное конечное состояние может быть использовано для создания связи, исходящей из конечного состояния исходного <члена>.