Лабораторная работа: Трансляция распознающих конечных автоматов
Название: Трансляция распознающих конечных автоматов Раздел: Рефераты по информатике Тип: лабораторная работа |
Лабораторная работа №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. Пример работы программы: |