Название: Трансляция распознающих конечных автоматов
Вид работы: лабораторная работа
Рубрика: Информатика
Размер файла: 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};
-
Синтез операционных автоматов
Министерство образования Российской Федерации Саратовский государственный технический университет Синтез операционных автоматов лабораторная работа по курсу “Организация ЭВМ и систем”
-
Программа построения грамматики для конечного автомата
Введение Электронные средства связи это техника передачи информации из одного места в другое в виде электрических сигналов, посылаемых по проводам, кабелю, оптоволоконным линиям или вообще без направляющих линий. Направленная передача по проводам обычно осуществляется из одной конкретной точки в другую, как, например, в телефонии или телеграфии.