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

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

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


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


Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:759
Символов:6209
Размер:12.13 Кб.