Бакнелл Джулиан М.
Шрифт:
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.
При выполнении ноля или более замыканий (операции "*") задача еще проще: нужно создать только конечное состояние для элемента. Оно становится начальным состоянием всего выражения. При этом виртуальное конечное состояние является конечным состоянием выражения.