Трансляция распознающих конечных автоматов

Лабораторная работа №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.

Пример работы программы: