Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка транслюючої граматики і поудова скінченого автомату для опису змінних типу однонапрямленого списку
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2003
Тип роботи:
Інші
Предмет:
Системи автоматизованого проектування ЗВТ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Інститут комп‘ютерних наук та інформаційних технологій
Кафедра САПР
Пояснювальна записка
до курсової роботи
з дисципліни “Лінгвістичне забезпечення систем автоматизованого проектування ”
на тему : “Розробка транслюючої граматики і поудова скінченого автомату для опису змінних типу однонапрямленого списку”
Міністерство освіти та науки України
/назва вищого учбового закладу/
Кафедра ”САПР”
Дисципліна: ”Лінгвістичне забезпечення САПР”
Спеціальність: ”САПР”
Курс ІIІ, Група Н-33, Семестр VI
Завдання
на курсовий проект ( роботу) студента
Андреєва Дениса Геннадійовича
/прізвище, ім'я, по - батькові/
1.Тема проекту /роботи/: Розробка транслюючої граматики і поудова скінченого автомату для опису змінних типу однонапрямленого списку.
_________________________________________________________________
2. Термін здачі студентом закінченого проекту /роботи/__________________
3. Вихідні дані для проекту /роботи/__________________________________
_________________________________________________________________
_________________________________________________________________
4. Зміст розрахунково-пояснювальної записки /перелік питань, які підлягають розробці/__________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
5. Перелік графічного матеріалу / з точним зазначенням обов'язкових креслень/__________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
6. Дата видачі завдання______________________________________________
Календарний план
№ п/п
Назва етапів курсової роботи
Термін виконан-ня етапів роботи
Приміт-ки
1
Отримання індивідуального завдання
8.03.02
2
Пошук необхідної літератури
9.03 – 12.04
3
Пошук необхідної інформації в мережі Intenet
13.04 – 17.04
4
Обробка відповідної літератури
17.04 – 28.04
5
Написання протрами
5.05-15.05
6
Написання теоретичної частини курсової роботи
15.05 – 5.06
7
Висновки по курсовій роботі
8.06.02
8
Остаточна перевірка, закінчення курсової роботи
10.06.02
Зміст.
1.
Завдання на курсову роботу
2
2.
Календарний план
3
3.
Анотація
5
4.
Специфікація
6
5.
Вступ
7
6.
Теоретична частина
8
а)скінчений автомат
8
б)опис і обгрунтування вибраного алгоритму
10
в)блок-схема вибраного алгоритму
11
г)обгрунтування вибору алгоритмічної мови
12
7.
Практична частина
13
а)опис і користування програмою
13
б)опис програмної реалізаціїї
17
8.
Висновок
25
9.
Список використаної літератури
26
10.
Додаток
27
Анотація
Андреєв Д.Г., “Розробка транслюючої граматики і поудова скінченого автомату для опису змінних типу однонапрямленого списку”. Курсова робота. – НУ “Львівська політехніка”, каф. САПР, дисципліна “Лінгвістичне забезпечення систем автоматизованого проектування ”, 2003р.
Курсова робота складається з 32 сторінок, 1 таблиці, 1 додатка. В даній курсовій роботі розроблено транслюючу граматику та побудовно скінченй автомат для опису змінних типу однонапрямленого списку.
Специфікація.
СА - скінчений автомат
СР- скінчений розпізнавачї
КП- керуючий пристрій
PC – Персональний ком’пютер
Вступ.
Лінгвістичне забезпечення – це сукупність мов, які використовуються в САПР для представлення задач про проектовані об’єкти, процеси і засоби проектування, якими обмінюється користувач з ЕОМ і між собою в процесі проектуванні. За ГОСТ-ом 2351.0-79 поняття лінгвістичне забезпечення САПР трактується як сукупність мов, термінів і визначень необхідних для виконання автоматизованого проектування.
Мови програмування – це мови управління пристроями та периферією. Мови програмування використовуються для запису програм. Вибір конкретної мови програмування, яка максимально підходить для розвитку певної задачі може стати серйозною проблемою не тільки для програміста –початківця, але й для спеціаліста, що володіє достатнім досвідом програмування. Не зважаючи на велику кількість мов програмування розробка та реалізація певних мов продовжується по мірі розширення застосування обчислюваної техніки і поглиблення розуміння суті програмування. Імпульсом до створення нових мов програмування є не стільки бажання дослідників покращити існуючі, але й намагання потужних організацій представити певні мови програмування орієнтованих на розв’язок задач певного класу до створення самих мов.
Мови програмування є мовами штучними з строго визначеними синтаксисом та семантикою, тому вони не допускають вільного тлумачення конструкцій, на відміну від природних мов. Головною класифікаційною ознакою мов є приналежність до одного із сформованих на сьогоднішній день стилю програмування.
Теоретична частина.
Під автоматом розуміють деяку мат. модель, властивості і поведінку якої можна вивчити і яку можна імітувати на ЕОМ.
Скінченим автоматом називають простішу модель з теорії алгоритмів, яка служить керуючим пристроєм для всіх інших моделей алгоритмів. Скінченим називають автомат у якому мн-на внутр-х станів, мн-на вхідних значень і мн-на вихідних значень є скінченими множинами.
Скінчені автомати використовуються при побудові компіляторів завдяки властивостям :
Скінчений автомат (далі СА) може виконувати ряд простих задач в компіляції (лексичний блок майже завжди будується на основі СА).
Т.Я. при моделюванні СА на PC обробка першого вхідної стрічки потребує невеликої к-ті операцій (одже пр-ма виконується швидко).
Моделювання СА потребує скінченого об’єму пам’яті, що спрощує проблеми пов’язані із використанням памя’ті.
Існує ряд теорем і алгоритмів, що дозволяють модифікувати і спрощувати СА.
СА переважно використовують як скінчені рзпізнавачі (далі СР).
СР- це модель пристрою із скінченим числом станів, що відрізняють правильно утворені ланцюги символів від неправильних.
СР можна зобразити :
Вхідна стрічка:
П
Р
А
В
И
Л
Ь
Н
А
С
Т
Р
І
Ч
К
А
-|
Вхідну стрічку можна розглядати як послідовність комірок, причому кожна комірка містить тільки один символ із символів вхідного алфавіту. Прчому крайню праву і ліву комірки можуть займати прикінцеві символи(маркери), але маркер може бути в стрічці тільки з одного боку.
Вхідна головка в кожен момент часу читає одну вхідну комірку пам’яті.
За один крок вхідна головка може :
Зсунутись на одну комірку вліво.
Залишитись на місці.
Зсунутись на одну комірку вправо.
Ядром розпізнавача є керуючий пристрій (далі КП).
КП представляє собою скінчену множину станів, разом з відображенням того, як ці стани міняються у відповідності із біжучим вхідним символом і поточною інф-ю добутою з пам’яті. КП також визначає в яку сторону зсунути вхідну головку та яку інф-ю помістити у робочу пам’ять.
Розпізнавач працюючи проробляє деяку послідовність кроків (тактів).
Такт складається :
Вхідна головка зсувається на одну комірку вліво/вправо, або залишається у вихідному стані.
В пам’ять заноситься деяка інф-я.
Змінюється стан керуючого пристрою.
Роботу СР можна відобразити в термінах зміни конфігурації :
Стан КП .
Вміст вх. стрічки і положення головки.
Вміст пам’яті.
СА характеризується :
Скінчена множина станів (Q).
Скінчений вх-й алфавіт. (()
Множина переходів (().
Початковий стан (S).
Множина прикінцевих станів (F).
Недоліком СА є те, що вони можуть вирішувати лише ті задачі, які потребують скінченого об’му пам’яті.
В даній курсовій роботі поставлена задача за допомогою СА-автомата розробити програму для обробки транслюючої граматики та змінних типу однонапрямленого списку. За допомогою СА порграма перевіряє вхідну граматику, та якщо вона є допустима створює та редагує список в динамічній пам’яті. Даний алгоритм є найбільш приємлимий т.я. для своєї реалізації потребує нескладного алгоритмічного рішення, та застосування невеликих ресурсів часу та пам’яті.
Блок-схема.
Ні
Системні вимоги програми
IBM 80x80
1M RAM
Ос Windows 3.1; Dos 7.0
Дане завдання реалізоване на мові високого рівня С++, т.я. дана мова є найбільш гнучкою та простою у використанні порівняно із більшістю інших алгоритмічних мов.
Практична частина.
Після запуску програми на єкрані дисплею з’являється повідомлення :
На яке потрібно ввести відповідні граматичні послідовності слів.
А саме :
Do
While
For
If
Else
switch
addaftedo
addaftewhile
Addaftefor
addafteif
addafteelse
addafteswitch
addbeforedo
addbeforewhile
addbeforefor
addbeforeif
addbeforeelse
addbeforeswitch
deldo
delwhile
delfor
adelif
delelse
delswitch
exit
----------------
---------------
-------------
----------------
-------------------
Табл.1
Ці слова можна вводити в довільній кількості та послідовності.
Введені слова перевіряються за допомогою СА, та якщо послідовність слів введена невірно, то виводиться повідомлення повторного вводу :
При введені вірної послідовності слів створюється динамічний однонапрямлений список в кожному вузлі якого зберігається відповідне слово. Після чого виводиться запрошення на редагування динамічного списку.
Наприклад :
Якщо ввести символ ‘N’, то виконання програми припинеться. При вводі символа
‘Y’ – буде запропоновано ввести керуючі слова, для редагування списку :
addafte<1> <2>(замість <1> та <2> має бути одне з слів Табл.1, ) – цей оператор вставляе в динамічний список слово <2> після слова <1>.
addbefore<1> <2>(замість <1> та <2> має бути одне з слів Табл.1, ) – цей оператор вставляе в динамічний список слово <2> перед словом <1>.
del<1> (замість <1> має бути одне з слів Табл.1, ) – цей оператор видаляє в динамічному списку слово <1>.
exit – оператор виходу з програми.
Якщо синтаксис операторів вірний то буде виконана відповідна дія, виведено на дисплей відредагований список та запропоновано подальшу роботу :
Вихід з програми відбувається за допомогою оператора EXIT або символа ‘N’ натиснутого під час виводу повідомлення редагування.
Реалізація даної програми здійснена за допомогою спеціально розробленого для цієї цілі скінченого автомату, що має вигляд :
(
D
O
W
H
I
L
E
F
R
S
T
C
A
X
B
1
2
E
2
E
2
D
2
3
E
2
E
E
2
E
E
0
2
3
F
4
3
E
3
3
F
E
E
E
E
E
5
E
0
3
4
4
E
E
4
1
1
4
E
4
E
E
E
E
E
0
4
E
E
E
E
5
5
F
5
F
E
3
E
3
E
6
0
5
E
6
E
E
6
E
F
E
E
E
6
E
E
E
E
0
6
E
E
E
E
E
E
4
E
7
E
F
7
E
E
E
0
7
E
E
E
F
E
E
1
E
E
E
E
E
E
E
E
0
F
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
1
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
0
Даний сінчений автомат використовується для перевірки граматики зарезервованих (допустимих) слів з таблиці 1.
Програмно СА реалізовано у вигляді матрці виду :
char matr[8][15]={
{'d','o','w','h','i','l','e','f','r','s','t','c','a','x','b'},
{'2','E','2','E','2','E','2','3','E','2','E','E','2','E','E'},
{'3','F','4','3','E','3','3','F','E','E','E','E','E','5','E'},
{'4','4','E','E','4','1','1','4','E','4','E','E','E','E','E'},
{'E','E','E','E','5','5','F','5','F','E','3','E','3','E','6'},
{'E','6','E','E','6','E','F','E','E','E','6','E','E','E','E'},
{'E','E','E','E','E','E','4','E','7','E','F','7','E','E','E'},
{'E','E','E','F','E','E','1','E','E','E','E','E','E','E','E'}};
Після виводу стрічки запрошення на ввод даних :
cout<<"Enter the data"<<endl<<">>";
програма зчитує вводимий рядок в стрічку буфер :
cin.getline(str,150);
та за допомогою нескладного циклу розбиває цю стрічку на слова попутно проводячи лексичну перевірку за допомогою СА :
beg=new node;// виділяєм пам’ять для збереження структури
node* p=beg;// налаштовуєм вказівник P на початок списку
for(int i=0;str[i];i++)
{
if((str[i]==' ')&&(f))
{
dat[l]='\0';
l=0;
k='1';
strcpy(p->elem,dat);
node* pn=new node;
p->next=pn;
p=pn;
continue;
}
f=false;
for(int j=0;j<15;j++)
if(str[i]==matr[0][j])
{
if(k=='F'){fex=false;break;}
k=matr[k-48][j];
if(k=='E'){fex=false;break;}
if(k=='F')f=true;
dat[l++]=str[i];
break;
}
if(!fex)break;
}
Під час виконання циклу після успішної перевірки біжучого слова із вхідної стрічки виділяється динамічна пям’ять достатнього розміру для збереження стректури (одного вузла списку) виду :
struct node
{
char elem[26];// поле зберігання слова
struct node* next;// вказівник на наступний елемент списку
};
Після перевірки стрічки та формування динамічного списку на екрані з’являється запрошення на редагування динамічного однонапрямленого списку :
cout<<"Wish to edit a line (y/n) ? ";
якщо відповідь задовільна то відбувається читання слів у буферні стрічки :
char data[16]={'0'};
string func;
cin>>func;
cin.get();
cin.getline(data,16);
та відбувається перевірка зчитаних слів на відповідність до синтаксису, за допомогою нашого СА.
Перше слово містить назву команди яку треба виконати та її перший операнд, а друге слово містить другий операнд команди.
Перевірка першого слова :
for(int i=0;func[i]!='\0';i++)
{
if((str[i]==' ')&&(f)) k='1';continue;
f=false;
for(int j=0;j<15;j++)
if(func[i]==matr[0][j])
{
if(k=='F')fex=false;break;
k=matr[k-48][j];
if(k=='E')fex=false;break;
if(k=='F')f=true;
break;
}
if(!fex)break;
}
if(!f){cout<<"string Error!"<<endl;continue;}
Перевірка другого :
for(i=0;data[i];i++)
{
if((str[i]==' ')&&(f)) k='1';continue;
f=false;
for(int j=0;j<15;j++)
if(data[i]==matr[0][j])
{
if(k=='F'){cout<<"Error!"<<endl;fex=false;break;}
k=matr[k-48][j];
if(k=='E'){cout<<"Error!"<<endl;fex=false;break;}
if(k=='F')f=true;
break;
}
if(!fex)break;
}
Якщо перевірки виконались успішно, то далі відбувається розбиття першого вхідного слова func на складові частини за допомогою циклів, та матриці m :
for(int s=0;s<25;s++)
{
kk=func.rfind(m[s][0]);//повертає індекс останнього входження
//пістроки m[s][0] у строку func
if(kk>0)break;
}
if(func=="exit")exit(0);
for(int j=0;j<kk;j++)tt[j]=func[j];// записуєм в буфер tt виділене слово
tt[j++]='\0';
Матриця m має вигляд :
String m[][7]={{"addaftedo"},{"addaftewhile"},{"addafteif"},{"addafteelse"},
{"addafteswitch"},{"addaftefor"},{"addbeforedo"},{"addbeforewhile"},
{"addbeforeif"},{"addbeforeelse"},{"addbeforeswitch"},{"addbeforefof"},
{"deldo"},{"delwhile"},{"delif"},{"delelse"},{"delswitch"},{"delfor"},
{"do"},{"while"},{"if"},{"else"},{"switch"},{"for"},{"exit"}};
За допомогою цієї матриці вдбувається розбиття буферного слова func надві складові частини у вищє вказаних циклах.
Після виділення з буферу func назви керуючої команди (перша частина слова func), та одного з операндів функції редагування (друга частина слова func) відбувається вибір та виконання виявленої керуючої команди шляхом виклику відповідної функції :
for(int g=0;g<24;g++)
{
int h=-1;
h=func.rfind(m[g][0]);
if(h>0)
{ char t[16];
for(int j=0,e=h;func[e];e++,j++)t[j]=func[e];
t[j++]='\0';
func[h]='\0';
int ch;
char a1[10];
for(int i=0;func[i];i++)a1[i]=func[i];
a1[i++]='\0';
if(!strcmp(a1,"addafte"))ch=1;
if(!strcmp(a1,"addbefore"))ch=2;
if(!strcmp(a1,"del"))ch=3;
switch(ch)
{
case 1:addafte(t,data);f=true;break;//перехід на
case 2:addbefore(t,data);f=true;break;//відповідну
case 3:del(t);f=true;break;//команду редагування
default :cout<<"Error!!!";
}
}
if(f)break;
}
Функції редагування (addafte(),addbefore(),del()) працюють із динамічною пам’ятю
проводячи редагування динамічного списку.
Функція addafte(S,S1) проводить вставку аргументу S1 після аргументу S :
void addafte(char* s,char*s1)
{
node* p=beg;
do// цикл пошуку аргументу S у списку
{
if(!strcmp(p->elem,s))//якщо елемент найдено то утворити новий вузол
{ //та відредагувати зв’язки між вузлами
node *new_e=new node;
strcpy(new_e->elem,s1);
new_e->next=p->next;
p->next=new_e;
break;
}
else p=p->next;
}
while(p!=NULL);
p=beg; cout<<endl<<"The new list :"<<endl;
do// цикл роздруку нового списку
{
cout<<p->elem<<" ";
p=p->next;
}
while(p!=NULL);
cout<<endl;
};
Функція addbefore(char*s,char*s1) проводить вставку аргументу S1 перед аргументом S :
void addbefore(char* s,char*s1)
{
node* p=beg;
node* pp=p;
do// цикл пошуку аргументу S у списку
{
if(!strcmp(p->elem,s))))//якщо елемент найдено то утворити новий
{ //вузол та відредагувати зв’язки між вузлами
node *new_e=new node;
strcpy(new_e->elem,s1);
new_e->next=p;
if(p!=beg) pp->next=new_e;
else beg=new_e;
break;
}
else {pp=p; p=p->next;pp->next=p;}
}
while(p!=NULL);
p=beg;cout<<endl<<"The new list :"<<endl;
do// цикл роздруку нового списку
{
cout<<p->elem<<" ";
p=p->next;
}
while(p!=NULL);
cout<<endl;
};
Функція del(char* s) проводить видалення аргументу S із списку :
void del(char* s)
{ node* p=beg;
node* pp=p;
if(beg==NULL){cout<<"The list is empty";exit(0);}
if(beg->next==NULL)//перевірим чи не пустий список
{
if(!strcmp(s,beg->elem)){cout<<"The list is empty"<<endl;delete beg;exit(0);}
else {cout<<"Such element in the list is not present !!"<<endl;}
}
do//цикл пошуку аргументу S у списку
{
if(!strcmp(p->elem,s))//якщо знайшли то переадресовуєм зв’язки і
{ //видаляєм вузол
if(p!=beg){pp->next=p->next;delete p;}
else {beg=p->next;delete p;}
break;
}
else {pp=p;p=p->next;pp->next=p;}
}
while(p!=NULL);
p=beg;cout<<endl<<"The new list :"<<endl;
do// цикл роздруку нового списку
{
cout<<p->elem<<" ";
p=p->next;
}
while(p!=NULL);
cout<<endl;
};
Висновок.
В процесі виконання курсової роботи було розглянуто основні принципи дії скінчених автоматів, та будови розпізнавачів на їх основі .
Кінцевим результатом виконання курсової роботи стала програма що використовує спеціалізовану граматику та скінчений автомат для опису змінних типу однонапрямленого списку.
При написанні даної курсової роботи були використані наступні технічні та програмні засоби:
Intel Celeron 1Gh
128M – SDRAM
OS Windows 98ME
Wisual C++ 6.0
Список використаної літератури.
Грис Д. Конструирование компиляторов для цифровых вычислительных машин - М.: Мир, 1975.
Корсакова Н.В., Пятлина Е.О. Фильчаков В.В. Структуры данных - Л.: ЛИАП, 1986.
Бржезовский А.В., Корсакова Н.В., Фильчаков В.В. Лексический и синтаксический анализ. Формальные языки и грамматики - Л.: ЛИАП, 1990.
Курс лекції з дисципліни „Лінгвістичне забезпечення САПР”.
Додаток
Текст програми :
#include<iostream>
#include<string>
using namespace std;
struct node
{
char elem[26];
struct node* next;
};
void addafte(char* s,char*s1);
void addbefore(char* s,char*s1);
void del(char* s);
node* beg;
void main(void)
{
char matr[8][15]={
{'d','o','w','h','i','l','e','f','r','s','t','c','a','x','b'},
{'2','E','2','E','2','E','2','3','E','2','E','E','2','E','E'},
{'3','F','4','3','E','3','3','F','E','E','E','E','E','5','E'},
{'4','4','E','E','4','1','1','4','E','4','E','E','E','E','E'},
{'E','E','E','E','5','5','F','5','F','E','3','E','3','E','6'},
{'E','6','E','E','6','E','F','E','E','E','6','E','E','E','E'},
{'E','E','E','E','E','E','4','E','7','E','F','7','E','E','E'},
{'E','E','E','F','E','E','1','E','E','E','E','E','E','E','E'}};
bool f=false,fex=true;;
char k='1';
char str[150];
do
{
cout<<"Enter the data"<<endl<<">>";
cin.getline(str,150);
char dat[26]={'0'};
int l=0;
beg=new node;
node* p=beg;
for(int i=0;str[i];i++)
{
if((str[i]==' ')&&(f))
{
dat[l]='\0';
l=0;
k='1';
strcpy(p->elem,dat);
node* pn=new node;
p->next=pn;
p=pn;
continue;
}
f=false;
for(int j=0;j<15;j++)
if(str[i]==matr[0][j])
{
if(k=='F'){fex=false;break;}
k=matr[k-48][j];
if(k=='E'){fex=false;break;}
if(k=='F')f=true;
dat[l++]=str[i];
break;
}
if(!fex)break;
}
dat[l]='\0';
if(k=='F')
{
strcpy(p->elem,dat);
p->next=NULL;
}
else cout<<"Error!"<<endl;
fex=true;k='1';
}
while(f!=true);
string func;
do
{
cout<<"Wish to edit a line (y/n) ? ";
char s;
while((cin>>s)&&(!strchr("yYnN",s)))
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора