Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Лiнгвiстичне забезпечення САПР
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
Звіт
до Лабораторної роботи №3
на тему:
«ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ»
З курсу
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Ознайомлення з правилами побудови і застосування автоматів з магазинною пам’яттю.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Скінченні автомати можуть вирішувати тільки ті задачі, які потребують скінченного об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок, кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має «свою роль», тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною.
Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам'ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазину (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна поміщати в магазин і видаляти їх з нього по одному. При цьому видаляється завжди тільки верхній символ, тобто символ, який був поміщений у магазин останнім.
Коли інформація поміщається (записується) в магазин, кажуть, що вона «заштовхується», коли інформація видаляється з магазину – «виштовхується» з нього.
Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (скорочено МП-автомат). У ньому дуже просто поєднується пам'ять скінченного автомата і магазинна пам'ять.
Як і у випадку скінченного автомата, обробка скінченного ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок:
а) переходу у новий стан;
б) заштовхування символу у магазин;
в) виштовхування символу з магазину.
Кожний крок обробки задається множиною правил, які використовують інформацію трьох видів:
Стан;
Верхній символ магазина;
Біжучий вхідний символ.
Залежно від отриманої інформації керуючий пристрій обирає або перехід в новий стан, або вихід з процесу. Перехід складається з трьох типів операцій: над станом, над магазином і над входом.
Можливі такі операції:
1. Операції над магазином:
Заштовхнути в магазин відповідний символ;
Виштовхнути верхній символ з магазину;
Залишити магазин без змін.
2. Операції над станом:
Перейти в заданий стан.
3. Операції над входом:
Перейти до наступного вхідного символу і зробити його поточним;
Залишити цей вхідний символ поточним.
МП-автомат визначається такими характеристиками:
де – скінченна множина символів станів, які відображають усі можливі стани керуючого пристрою; - скінченний вхідний алфавіт; - скінченний алфавіт магазинних символів; - керуюча функція, яка кожній комбінації вхідного символу, магазинного символу, стану ставить у відповідність перехід у відповідний стан або вихід; - початковий стан керуючого пристрою; - початковий символ, який є в магазині в початковий момент; - множина прикінцевих станів.
МП-автомат називається розпізнавачем, якщо у нього є два виходи:
1. ДОПУСТИТИ;
2. ВІДКИНУТИ.
Ланцюжок символів вхідного алфавіту (включаючи кінцевий маркер) допускається розпізнавачем, якщо під дією цього ланцюжка автомат, який розпочав роботу у своєму початковому стані з початковим вмістом магазина, робить ряд переходів, які приводять до виходу «ДОПУСТИТИ». В протилежному випадку ланцюжок відкидається.
При описанні переходів МП-автомата позначатимемо дії автомата словами:
ЗАШТОВХНУТИ (А) – заштовхнути магазинний символ А у магазин;
ВИШТОВХНУТИ – виштовхнути верхній символ з магазина;
СТАН (S) – стан S;
ЗСУВ – зсунути вхідну головку на один символ;
ТРИМАТИ – тримати поточний вхідний символ до наступного кроку.
3. ВИКОНАННЯ РОБОТИ
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Варіант №17
Побудувати МП-розпізнавач і написати керуючу програму для таких ланцюжків символів:
ТЕКСТ ПРОГРАМИ .
Програма складається з двох файлів Magazine.cs, де розміщені методи, які обробляють сам магазин і файлу BasicClass.cs, де розміщений сам автомат.
Файл MagazineYura.cs
using System;
using System.Text;
namespace YuranamesNames
{
public class Magazine
{
public const byte SIZE = 20;
private char[] magazine = new char[SIZE];
private byte i, p;
//Constructor of magazineazine.
public Magazine()
{
p = 0;
magazine[0] = '^'; p++;
for (i = 1; i < SIZE - 1; i++)
{
magazine[i] = ' ';
}
}
//Funcion of pushing in the magazineazine.
public void push(char c) {
if (p == SIZE - 1)
{
Console.WriteLine("Magazyn povnyi.");
}
else
{
magazine[p] = c; p++;
}
}
//Function of pushing out the magazineazine.
public void pop()
{
p--;
magazine[p] = ' ';
}
//Printing the magazineazine.
public void printAllMagazine()
{
foreach (char c in magazine)
{
Console.Write("{0}", c);
}
}
//This function return the symbol on the head of magazineazine.
public char VverchMagazuny()
{
return magazine[p - 1];
}
}
}
Файл YuraClass.cs
using System;
using System.Text;
//My namespaces
using YuranamesNames;
namespace Lab03
{
class automatMP : Magazine
{
private byte s;
private int f;//F(0 - не допуск, 1 - допуск)
private string str;
public automatMP(string str) : base()
{
s = 1; f = -1;
this.str = str;
}
//Description of setteings.
public byte S
{
get { return s; }
set { s = value; }
}
public int F
{
get { return f; }
set { f = value; }
}
public string STR
{
get { return str; }
}//End - Description of setteings.
//Functions...
public void tablizaStanov()
{
switch (this.s)
{
case 1:
if (VverchMagazuny() == '^' && str[0] == '1')
{
push('A');
this.str = this.str.Remove(0, 1);
}
if (VverchMagazuny() == 'A' && str[0] == '1')
{
push('A');
this.str = this.str.Remove(0, 1);
}
else if (VverchMagazuny() == 'A' && str[0] == '0')
{
pop();
this.s = 2;
this.str = this.str.Remove(0, 1);
}
else { this.f = 0; }
break;
case 2:
if (VverchMagazuny() == 'A' && str[0] == '0')
{
pop();
this.str = this.str.Remove(0, 1);
}
else if (VverchMagazuny() == 'A' && str[0] == '1')
{
pop();
this.str = this.str.Remove(0, 1);
}
else if (VverchMagazuny() == '^' && str[0] == '-')
{
this.f = 1;
break;
}
else { this.f = 0; }
break;
}//End switch(S)
}
}
class Basic
{
static void Main(string[] args)
{
string str = "";
Console.Write("Vvedit strichky: ");
Console.WriteLine();
str = Console.ReadLine();
str = str + "-";
automatMP mp = new automatMP(str);
Console.WriteLine("Tvoya strichnka: {0}", str);
Console.WriteLine(" Magazyn * Stan * Vhidna strichka");
Console.WriteLine("****************************************************************");
mp.printAllMagazine();
Console.Write("$ {0} $ ", mp.S);
Console.Write(mp.STR);
Console.WriteLine();
for(int i =0; i<str.Length; i++) {
if (mp.F == 0) { break; }
else
{
mp.tablizaStanov();
Console.WriteLine("****************************************************************");
mp.printAllMagazine();
Console.Write("* {0} * ", mp.S);
Console.Write(mp.STR);
Console.WriteLine();
}
}//End - for(int i =0; i<str.Length; i++)
Console.WriteLine("****************************************************************");
if (mp.F == 1)
{
Console.WriteLine("Strichka dopuwchena.");
}
else
{
Console.WriteLine("Strichka ne dopuwchena.");
}
}//End - static void Main(string[] args)
}//End - class Basic
}
РЕЗУЛЬТАТ ВИКОНАННЯ ПРОГРАМИ
Enter input string:
1111111100001111
S1
0
1
A
Перехід в S2
Зашт A
-
-
Зашт А
-
S2
0
1
A
Вишт A
Вишт A
-
-
-
Допуск
4. ВИСНОВОК
На цій лабораторній роботі, я вивчив і закріпити навики побудови і застосування автоматів з магазинною пам’яттю. Написав управляючу програму для розпізнавання множини ланцюжків з нулів і одиниць. Переконався, що вона працює і виводить коректний результат.
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора