Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Листинг 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 {в противном случае необходимо выполнить синтаксический анализ второго выражения и объединить их в таблице переходов}
else begin
{обработать символ вертикальной черты}
inc(FPosn);
{конечное состояние исходного члена еще не существует (хотя член и содержит состояние, которое указывает на него), поэтому его нужно создать}
EndState1 := rcAddState(mtNone, #0, nil, UnusedState, UnusedState);
{для конструкции ИЛИ требуется новое начальное состояние: оно будет указывать на исходный член и на второе выражение, синтаксический анализ которого будет выполняться следующим}
OverallStartState := rcAddState(mtNone, #0, nil,
UnusedState, UnusedState);
{выполнить синтаксический анализ следующего выражения}
StartState2 := rcParseExpr;
if (StartState2 = ErrorState) then
Exit;
{изменить состояние, определенное для всего выражения, чтобы вторая связь указывала на начало второго выражения}
Result := rcSetState(OverallStartState, StartStatel, StartState2);
{определить конечное состояние исходного члена, чтобы оно указывало на результирующее конечное состояние, определенное для второго выражения и всего выражения в целом}
rcSetState(EndState1, FTable.Count, UnusedState);
end;
end;
После ознакомления с этой конкретной конструкцией создание конечных автоматов для операций замыкания ("*", и+" и сложности не представляет. Важно только создавать состояния в правильном порядке. Рассмотрим код, приведенный в листинге 10.11.
Листинг 10.11. Синтаксический анализ операций замыкания
function TtdRegexEngine.rcParseFactor : integer;
var
StartStateAtom : integer;
EndStateAtom : integer;
begin
{предположим худшее}
Result := ErrorState;
{вначале выполнить синтаксический анализ элемента}
StartStateAtom := rcParseAtom;
if (StartStateAtom = ErrorState) then
Exit;
{проверить на наличие операции замыкания}
case FPosn^ of
' ?' : begin
{обработать символ операции ?}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать}
EndStateAtom := rcAddState(mtNone, #0, nil,
UnusedState, UnusedState);
{создать новое начальное состояние для всего регулярного выражения}
Result := rcAddState(mtNone, #0, nil,
StartStateAtom, EndStateAtom);
{обеспечить, чтобы новое конечное состояние указывало на следующее еще не использованное состояние}
rcSetState(EndStateAtom, FTable.Count, UnusedState);
end;
' *' : begin
{обработать символ операции *}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать; оно будет начальным состоянием всего подвыражения регулярного выражения}
Result := rcAddState(mtNone, #0, nil,
NewFinalState, StartStateAtom);
end;
' + ' : begin
{обработать символ операции +}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать}
rcAddState(mtNone, #0, nil, NewFinalState, StartStateAtom);
{начальное состояние всего подвыражения регулярного выражения будет начальным состоянием элемента}
Result := StartStateAtom;
end;
else
Result := StartStateAtom;
end; {case}
end;
При выполнении ноля или одного замыкания (операции "?") нужно создать конечное состояние элементарного выражения, к которому применяется операция, и начальное состояние всего конечного автомата. Эти новые состояния связаны между собой, как показано на рис. 10.5.
При выполнении ноля или более замыканий (операции "*") задача еще проще: нужно создать только конечное состояние для элемента. Оно становится начальным состоянием всего выражения. При этом виртуальное конечное состояние является конечным состоянием выражения.
При выполнении одного или более замыканий (операции "+") задача почти столь же проста. Потребуется создать конечное состояние для элемента и связать его с начальным состоянием элемента (которое является также начальным состоянием выражения). При этом виртуальное конечное состояние снова является конечным состоянием выражения.
