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

2





Лабораторная работа №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: // входное состояние

      case S[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.

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