Загрузка...
Учебная работа. Лабораторная работа: Трансляция распознающих конечных автоматов
Трансляция распознающих конечных автоматов
Цель работы: исследование способов действенной трансляции распознающих автоматов конечных автоматов и 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; // знакactiveXперед числом либо скобкой
‘(‘ :
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.
Пример работы программки:
]]>