ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ. Звіт з Лiнгвiстичне забезпечення САПР. Робота № 531336

ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

ТГВ

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2020

Тип роботи:

Звіт

Предмет:

Лiнгвiстичне забезпечення САПР

Група:

КН

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт з виконання Лабораторної роботи №1 на тему: ВНУТРІШНІ ФОРМИ ПОДАНННЯ ВХІДНОЇ ПРОГРАМИ з курсу: «Лінгвістичне забезпечення САПР» 1. МЕТА РОБОТИ Закріпити навики одержання бездужкового польського запису, використовуючи метод Дейкстри і бінарні дерева. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Для оптимізації процесу компіляції первісна текстова програма перекладається у деяку внутрішню форму, зручнішу для подальшої машинної обробки. Проміжна програма виробляється синтаксичним аналізатором і відображає структуру первинної програми. У той самий час оператори проміжної програми розміщуються в тому випадку, в якому вони повинні виконуватись. Найрозповсюдженішими формами подання вхідної програми є: 1) Бездужковий запис (польський запис); 2) Тетради; 3) Тріади; 4) Зв’язані спискові структури; 5) Зображаючі дерева. ЗАПИС БЕЗДУЖКОВИЙ. АЛГОРИТМ ДЕЙКСТРИ. Запис бездужковий – подання виразу, при якому порядок виконання операцій визначається її контекстом і позицією у формулі. Існують два види бездужкових записів: прямий, або префікс ний і інверсний, або постфікс ний. Для автоматизованих обчислень найзручніше використовувати постфікс ний запис бездужковий. Відомо декілька методів отримання пост фіксовано польського запису. Найефективніший є алгоритм Дейкстри. Цей метод базується на використанні стека для збереження знаків операцій. Кожному обмежувачу, який входить у вираз, присвоюється пріоритет. Для знаків операцій пріоритет зростає в порядку, зворотному до старшинства операцій. Алгоритмічні і логічні вирази розглядаються як вхідна стрічка символів зліва направо. Операнди переписуються у вихідну стрічку, а знаки операцій поміщають у стек операцій. Якщо пріоритет вхідного знака операцій дорівнює нулю або більший від пріоритету знака, який є на вершині стека, то новий знак додається до вершини стека. В протилежному випадку із стека «виштовхується» і переписується у вихідні стрічці знак, що розташований у вершині, а також наступні за ним знаки з пріоритетом більшим або таким, що дорівнює пріоритету вхідного знака. Після цього вхідний знак додається до вершини стека. Обмежувачі Пріоритет ( [ if 0 = ) then else 1 2 3 ^ 4 ] 5 > ≥ = ≤ ≠ < 6 + - 7 * / ÷ @ 8 ? 9 Деякі особливості має й робота з дужкам. Відкриваючі дужки мають нульовий пріоритет, просто записуються у вершину стеку і не виштовхують жодного знака. Виштовхувати відкриваючу дужку може тільки закриваюча. Закриваюча дужка має пріоритет один, який не перевищує пріоритету будь-якої операції. Поява закриваючої дужки викликає виштовхування усіх знаків операцій до найближчої дужки. В стек закриваюча дужка не записується і у вихідну стрічку не переноситься. Відкриваюча і закриваюча дужки взаємно знищується. ФОРМУВАННЯ БЕЗДУЖКОВОГО ЗАПИСУ ЗА ДОПОМОГОЮ БІНАРНОГО ДЕРЕВА. Арифметичний вираз можна подати у вигляді дерева. Вузли дерева відповідають операціям, а гілки – операндам. Ліва гілка, яка виходить з вузла, відповідає лівому операнду., права – правому. Операціям, які виконуються раніше, відповідають нижче розміщені вузли. Верхній вузол – корінь дерева відповідає операція, яка виконується останньою. На рис. 2. показано дерево виразу: . Рис. 2. Обхід дерева для одержання постфіксного польського запису . Якщо, почавши з нижнього листка крайньої лівої гілки дерева, обійти усі листки і вузли дерева, так щоб гілки розглядались зліва направо, а вузол розглядався після обходу усіх гілок, що з нього виходять, то послідовність перегляду вузлів і листків дасть постфіксний польський запис. На рис. 3. показано дерево виразу і порядок обходу для одержання префіксного польського запису. Рис. 3. Обхід бінарного дерева для одержання префіксного польського запису . Якщо, почавши з верхнього вузла, обійти усі вузли і листки дерева, так щоб верхній вузол розглядався раніше ніж нижній, і одразу після розгляду вузла проглядалися зліва направо гілки, які з нього виходять, то отримаємо префікс ний польський запис. 3. ВИКОНАННЯ РОБОТИ ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Варіант №17 Скласти програму, яка за допомогою бінарного дерева перетворить у постфіксний польський запис вираз ТЕКСТ ПРОГРАМИ НА С. #include <stdio.h> #include <string.h> #include <graphics.h> #include <conio.h> char prefixNotation[100]={0}, postfixNotation[100]={0}; char priors[6][2] = { {'+',3}, {'-',3}, {'*',4}, {'/',4}, {'<',2}, {'o',1}}; char OVERPRIORITY = 6; int radius=17; char getPriority(char oper){ for(int i=0; i<6;i++){ if(oper==priors[i][0]) return priors[i][1]; } return OVERPRIORITY; } void parse(char *code, int x, int y, int l) { // 1)only 1 element if(strlen(code)==1){ setcolor(7); pieslice(x,y,0,360,radius); setcolor(3); outtextxy(x-5,y-5,code); prefixNotation[strlen(prefixNotation)] = code[0]; postfixNotation[strlen(postfixNotation)] = code[0]; return; } // 2)some string // n-element number, prior-element priority int n=0, prior= OVERPRIORITY; for(int i=0; i<strlen(code); i++){ if(code[i]=='('){ int k=1; while(k!=0){ i++; if(code[i]==')'){ k--; }else if(code[i]=='('){ k++; } } continue; } if(getPriority(code[i])<prior){ //printf("Operator %c - priority - %d",code[i], getPriority(code[i])); n=i; prior = getPriority(code[i]); } } // 2.1) into handles (code) and not unarniy if(prior == OVERPRIORITY){ *(code+strlen(code)-1)=0; parse(code+1, x, y, l); return; } // 2.2) found operator prefixNotation[strlen(prefixNotation)] = code[n]; char elem[2] ={0}; elem[0] = code[n]; *(code+n)=0; setcolor(7); line(x,y,x-l,y+50); line(x,y,x+l,y+50); pieslice(x,y,0,360,radius); parse(code, x-l, y+50, l*0.5); parse(code+n+1, x+l, y+50, l*0.5); setcolor(3); outtextxy(x-5,y-5,elem); postfixNotation[strlen(postfixNotation)] = elem[0]; return; } void main(){ clrscr(); char code[100]={0}; printf("--Vvedit vuraz-->\n"); gets(code); int gd=DETECT, gm; initgraph(&gd, &gm, "c:\\tc3\\bgi " ); printf("\n %s",code); parse(code, (640/2), 30, 150); // printf("\n Prefix: "); // printf(prefixNotation); printf("\n Postfix: "); printf(postfixNotation); getch(); } Обхід бінарного дерева для одержання постфіксний польський запис . 4. ВИСНОВОК На цій лабораторній роботі, я вивчив і закріпити навики одержання бездужкового польського запису, використовуючи метод бінарні дерева. Написав програма, яка за принципом бінарного дерева перетворює вираз у постфіксний польський запис . Переконався, що вона працює і виводить коректний результат.

Звіт Лiнгвiстичне забезпечення САПР

horuktaras

17.07.2020 15:47

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись