Лабораторная работа №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.
Пример работы программы:
Другие работы по теме:
Балансовые модели экономического роста
Министерство образования Российской Федерации Санкт-Петербургский государственный инжененрно-экономический университет институт туризма и гостиничного хозяйства
Торговые автоматы
Торговый автомат – монетное устройство для продажи товаров. Автоматы принимают монеты с помощью монетоприемника и купюры посредством купюроприемника.
Порядок расчета налога на игорный бизнес
Если игровой стол имеет более одного игрового поля, то ставка налога по данному игровому столу должна быть увеличена кратно количеству игровых полей. Расчет при установлении новых объектов. Расчет при выбытии объектов.
Налогообложение 2 Расчет суммы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО – ЭКОНОМИЧЕСКИЙ ИНСТИТУТ КОНТРОЛЬНАЯ РАБОТА ПО НАЛОГАМ И НАЛОГООБЛОЖЕНИЮ
Игра Жизнь и компьютерное представление о мире и Боге
Игра "Жизнь" и "компьютерное" представление о мире и Боге 1. Введение В статье излагается спекулятивная гипотеза о материи, пространстве, времени и Боге, навеянная бурным развитием компьютерной техники за последние 20 лет. Отправной точкой служит одна сравнительно новая математическая теория, а именно теория клеточных автоматов (cellular automata).
Автоматы с магазинной памятью
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
Автоматы с магазинной памятью
Автоматы и преобразователи с магазинной памятью играют важную роль при построении автоматно-лингвистических моделей различного назначения, связанных с использованием бесконтекстных (контекстно-свободных) языков. В частности, такие устройства используются в большинстве работающих программ для синтаксического анализа программ, написанных на различных языках программирования, которые во многих случаях можно рассматривать как бесконтекстные.
6Выбор коммутационно защитной аппаратуры
Выбор аппаратуры защиты производится с учётом следующих требований: - номинальный ток Iн и номинальное напряжение Uн автоматов должно соответствовать расчётному току и напряжению;
Абстрактный синтез конечного автомата
СОДЕРЖАНИЕ Введение 1. Абстрактный синтез конечного автомата 1.1 Формирование алфавитного оператора 1.2 Приведение оператора к автоматному виду 1.3 Построение графа переходов абстрактного автомата
Метод конечных разностей
Ознакомление с аналоговым и дискретным вариантами реализации фильтра. Определение конечных разностей первого и второго порядков функции. Программная реализация и график исследуемой функции. Рекуррентное соотношение для вычисления сглаженного значения.
Абстрактный синтез конечного автомата
Формирование алфавитного оператора. Приведение оператора к автоматному виду. Построение графа переходов абстрактного автомата. Кодирование состояний, входных и выходных сигналов. Формирование функций возбуждения и выходных сигналов структурного автомата.
Автомат
Слово "автомат" в переводе с древнегреческого языка означает "самодействующий". Человечеству самодействующие устройства известны с древнейших времен. Еще в эпоху фараонов в Египте были созданы механизмы, которые "сами" открывали двери храмов.
Международный Дом Молитвы
Введение 1 Молитвенная комната 2 Другие проекты МДМ 3 Интересные факты Список литературы Введение Международный Дом Молитвы (англ. The International House of Prayer (IHOP-KC)) — это неохаризматическая христианская организация, базирующаяся в Канзас Сити, штат Миссури. Была основана 7 мая 1999 года Майклом Биклем и 20 ходатаями[1].
Василенко, Владимир Павлович
Введение 1 Биография 2 Творчество 2.1 Роли в театре 2.2 Роли в кино Список литературы Введение Владимир Павлович Василенко (26 октября 1951 года) — советский и российский актёр театра и кино.
Скотт, Дана Стюарт
Да́на Стю́арт Скотт (англ. Dana Stewart Scott , р. 1932) — американский учёный в области математики и информатики. Исследования Скотта связанны с теорией моделей, теорией автоматов, модальной и интуиционистской логиками, конструктивной математикой и связью между логикой и теорией категорий.
Хани, Крис
Крис Хани (коса Chris Hani, 28 июня 1942 — 10 апреля 1993) — южноафриканский революционер, генеральный секретарь Коммунистической партии ЮАР, член Национального исполкома АНК, начальник штаба Умконто ве сизве.
Трансляция, компиляция, интерпретация, линкование
Технология программирования задач для операторных и функциональных языков программирования, разработка алгоритма и отладка программы. Трансляция исходного текста, компоновка программы, ее выполнение с целью определения логических ошибок и тестирование.
Лисп-реализация конечных автоматов
Понятие и свойства конечного автомата, его назначение и сферы применения. порядок разработки специальной функции, реализующей конечный автомат. Способы описания данной функции, обоснование выбора одного из них. Программная реализация решения задачи.
Синтез операционных автоматов
Министерство образования Российской Федерации Саратовский государственный технический университет Синтез операционных автоматов лабораторная работа по курсу “Организация ЭВМ и систем”
Парсер на РНР - это возможно
Парсер на РНР - это возможно! Антон Калмыков В данной коротенькой статье я хочу продемонстрировать, что РНР может очень хорошо справляться с функцией синтаксического разбора выражений. Для тех, кто никогда не касался данной тематики, я думаю, статья будет так же интересна, поскольку в ней мы рассмотрим метод программирования в виде конечных автоматов.
Синтаксический разбор строк и конечные автоматы
Синтаксический разбор строк и конечные автоматы Андрей Боровский В этой статье речь пойдет о том, как анализировать информацию, переданную в виде последовательности символов (строку) и выделять из нее значимые элементы. Мы рассмотрим сравнительно простые ситуации, с которыми программистам приходится сталкиваться при решении самых разных задач: разбор выражений с простой синтаксической структурой, но с довольно свободными правилами записи.
Игорный бизнес в России
охватывает казино, игорные залы, павильоны игровых автоматов и букмекерские конторы. Игорный бизнес в стране до 2006 года регулировался лишь местным законодательством.
Айзерман Марк Аронович
АЙЗЕРМАН Марк Аронович (1913-92), российский ученый в области теории управления, представитель первого поколения кибернетиков в нашей стране, доктор технических наук.
Гаврилов Михаил Александрович
Гаврилов Михаил Александрович (1903-79), российский ученый, стоявший у истоков информатики в нашей стране, в частности технической кибернетики, теории автоматов и теории ЭВМ, член-корреспондент АН СССР (1964)
Бонгард Михаил Моисеевич
Бонгард Михаил Моисеевич (1924-71), российский ученый в области кибернетики, физиологии зрения и психологии мышления, один из создателей теории узнавания.
Глушков Виктор Михайлович
Глушков Виктор Михайлович (1923-82), российский и украинский математик и кибернетик, основатель Института кибернетики АН Украины, академик АН Украины (1961) и АН СССР (1964).
Эзоп и электричество
Электрическими, называют пожары, возникающие от использования неисправных защитных автоматов, тех, что стоят на вводе в каждую квартиру. Они предназначены для предохранения вашей “энергосистемы” от повреждений в проводке и приборах.