Referat.me

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

Вид работы: лабораторная работа

Рубрика: Информатика

Размер файла: 60.44 Kb

Скачать файл: referat.me-131797.docx

Краткое описание работы: Лабораторная работа №7 Трансляция распознающих конечных автоматов Цель работы: исследование методов эффективной трансляции распознающих автоматов конечных автоматов и R-графов для синтаксического разбора регулярных грамматик.

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

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

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

Похожие работы

  • Лексический и синтаксический анализатор языка высокого уровня

    Государственное образовательное учреждение высшего профессионального образования Кубанский государственный технологический университет (КубГТУ)

  • Построение отдельных фаз компиляции

    № докум. Изм. Лист Лист Подпись Дата Введение Компилятор – программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.

  • Парсер на РНР - это возможно

    Парсер на РНР - это возможно! Антон Калмыков В данной коротенькой статье я хочу продемонстрировать, что РНР может очень хорошо справляться с функцией синтаксического разбора выражений. Для тех, кто никогда не касался данной тематики, я думаю, статья будет так же интересна, поскольку в ней мы рассмотрим метод программирования в виде конечных автоматов.

  • Эффективное использование STL и шаблонов

    Эффективное использование STL и шаблонов Сергей Сацкий Введение С помощью конечных автоматов (далее просто автомат) можно успешно решать обширный класс задач. Это обстоятельство подмечено давно, поэтому в литературе по проектированию программного обеспечения часто приводятся рассуждения на тему применения автоматов ([2], [5], [8]).

  • Синтаксический разбор строк и конечные автоматы

    Синтаксический разбор строк и конечные автоматы Андрей Боровский В этой статье речь пойдет о том, как анализировать информацию, переданную в виде последовательности символов (строку) и выделять из нее значимые элементы. Мы рассмотрим сравнительно простые ситуации, с которыми программистам приходится сталкиваться при решении самых разных задач: разбор выражений с простой синтаксической структурой, но с довольно свободными правилами записи.

  • Компьютерные вирусы и антивирусные программы 3

    Реферат на тему: «Компьютерные вирусы и антивирусные программы» Компьютерные вирусы не зря так названы – их сходство с «живыми» вирусами поражает. Они так же распространяются, живут, действуют, так же умирают. Разница лишь в том, что в качестве мишени выступают не люди и не животные, а компьютеры. Контактируя между собой посредством дискет, компакт дисков, локальных сетей, Интернет и других средств «общения», они, как и человек, заражают друг друга.

  • Синтез комбинацонных схем и конечных автоматов, сети Петри

    Государственный комитет. Российской Федерации по высшему образованию. Кубанский государственный технологический университет. Кафедра. Пояснительная ЗАПИСКА. к курсовой работе по предмету математические основы теории систем тема курсовой работы.

  • Разработка конечного цифрового аппарата

    ЛИСТ ЗАДАНИЯ Изначальные данные: 1. Задан конечный цифровой автомат аналитическим методом следующими параметрами: 1) Множество букв входного алфавита: A= {0, 1};

  • Синтез операционных автоматов

    Министерство образования Российской Федерации Саратовский государственный технический университет Синтез операционных автоматов лабораторная работа по курсу “Организация ЭВМ и систем”

  • Программа построения грамматики для конечного автомата

    Введение Электронные средства связи это техника передачи информации из одного места в другое в виде электрических сигналов, посылаемых по проводам, кабелю, оптоволоконным линиям или вообще без направляющих линий. Направленная передача по проводам обычно осуществляется из одной конкретной точки в другую, как, например, в телефонии или телеграфии.