Трансляция распознающих конечных автоматов
Лабораторная работа №7
Трансляция распознающих конечных автоматов
Цель работы: исследование методов эффективной трансляции распознающих автоматов конечных автоматов и R-графов для синтаксического разбора регулярных грамматик.
Задание: определить и реализовать КА удовлетворяющий следующим условиям. G(L) порождает все возможные вещественные числа а также все возможные арифметические выражения состоящие из этих чисел и знаков операций “+, -, *, /” и скобок ” ( ) ”. Допустимо произвольное количество цифр в числе как до точки, так и после неё, а также впереди идущих пробелов.
Схема КА:
Start – начальное состояние;
InDigit – прочитана цифра;
AfterDigit – прочитан разделитель после цифры;
InOp – прочитан символ арифметической операции;
InLPrnt – прочитана открывающая скобка;
InRPrnt – прочитана закрывающая скобка.
InThk – прочитана точка.
d – цифры 0..9
p – знак точки
o – Операции + - * /
t – Знаки пробела
L – Левая скобка
R – Правая скобка
Код программы:
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
var res:integer;
input: string;
function CheckMath(const S : String) : Integer;
type
TState = (Start, InDigit, AfterDigit, InOp, InLPrnt, InRPrnt, Inthk);
{
* Start – начальное состояние;
* InDigit – прочитана цифра;
* AfterDigit – прочитан разделитель после цифры;
* InOp – прочитан символ арифметической операции;
* InLPrnt – прочитана открывающая скобка;
* InRPrnt – прочитана закрывающая скобка.
}
const
resLPrntMissing = -1;
resRPrntMissing = -2;
var
State : TState;
i, ParCount, Numbthk : Integer;
begin
Result := 0;
ParCount := 0; // счетчик скобок
State := Start;
for i := 1 to Length(S) do
case State of
Start: // входное состояние
caseS[i] of
' ': ; // состояние не меняется
'0'..'9' : State := InDigit;
'-' : State := InOp; // символ '-' перед числом или скобкой
'(' :
begin
Inc(ParCount);
State := InLPrnt;
end;
else
begin
// Синтаксическая ошибка
Result := i;
Exit;
end;
end;
InDigit:
case S[i] of
'0'..'9' : ; // состояние не меняется
'+', '-', '*', '/' : State := InOp;
'.': State := Inthk;
')' :
begin
Dec(ParCount);
State := InRPrnt;
end;
' ' : State := AfterDigit;
else
begin
Result := i;
Exit;
end;
end;
Inthk:
case S[i] of
'0'..'9' : Inc(Numbthk); // состояние не меняется
'+', '-', '*', '/' :
If Numbthk > 0 then
begin
State := InOp;
Numbthk :=0;
end
else
begin
Result := i;
Exit;
end;
')' :
If Numbthk > 0 then
begin
Dec(ParCount);
State := InRPrnt;
end else
begin
Result := i;
Exit;
end;
' ' : ;
else
begin
Result := i;
Exit;
end;
end;
AfterDigit:
case S[i] of
' ' : ;
'+', '-', '*', '/' : State := InOp;
'.' : State := Inthk;
')' :
begin
Dec(ParCount);
State := InRPrnt;
end;
else
begin
Result := i;
Exit;
end;
end;
InOp :
case S[i] of
' ' : ;
'0'..'9' : State := InDigit;
'(' :
begin
Inc(ParCount);
State := InLPrnt;
end;
else
begin
Result := i;
Exit;
end;
end;
InLPrnt:
case S[i] of
'0'..'9' : State := InDigit;
'-' : State := InOp;
'(' : Inc(ParCount);
' ' : ;
else
begin
Result := i;
Exit;
end;
end;
InRPrnt:
case S[i] of
'+', '-', '*', '/','.' : State := InOp;
')' : Dec(ParCount);
' ' : ;
else
begin
Result := i;
Exit;
end;
end;
end; // case State of
if State in [InLPrnt, InOp] then //Недопустимые состояния
Result := Length(S);
if ParCount > 0 then Result := resRPrntMissing else
if ParCount < 0 then Result := resLPrntMissing;
end;
Begin
writeln(' Vvedite stroku dlya analiza');
read(input);
res := CheckMath(input);
case res of
0: writeln('Vhodnaya posledovatelnost verna');
-1, -2: writeln('Ne xvataet skobki');
else
begin
writeln('oshibka v simvole ', res);
end;
end;
Readln;
Readln;
End.
Пример работы программы:
