Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інтерпретатор арифметичних виразів заданого формату.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Проблемно-орієнтовані мови програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра: АСУ
Курсова робота
з курсу „Проблемно-орієнтоване програмування”
На тему: “Інтерпретатор арифметичних виразів заданого формату”
Львів
Зміст
План
Індивідуальне завдання.
Вступ.
2.1 Опис мови програмування Сі.
2.2 Опис мови програмування Pascal.
Існуючі методи реалізації інтерпретатора.
3.1 Польський запис.
3.2 Скінченні автомати.
3.3 Опис свого методу.
Програмна реалізація.
4.1 Текст програми.
4.2 Алгоритм програми.
4.3 Опис програми.
4.4 Результати роботи програми.
4.5 Довідка користувача по користуванні програмою.
Висновки.
Список використаної літератури.
1. Індивідуальне завдання.
Обґрунтувати і розробити програму „Інтерпретатора арифметичних виразів заданого формату” на мові Сі.
2. Вступ
2.1 Опис мови програмування Сі.
Сі - універсальна мова програмування. Вона розроблялась в тісному зв’язку з системою UNIX, однак не є прив’язаною до цієї операційною системою і може використовуватись у будь-яких операційних системах або машинах.
Сі - мова порівняно “низького рівня” У ній немає:
а)прямих операцій над такими об’єктами як множини, стрічки, списки і масиви;
б)операцій які маніпулюють з цілими масивами або строками, натомість використовуються структури;
в)засобів розподілу пам’яті окрім можливості визначення статичних змінних і стекового механізму при виділенні місця для локальних змінних функцій;
г)засобів вводу-виводу (READ, WRITE) і методів доступу до файлів;
все це механізми високого рівня, які в мові Сі реалізуються за допомогою функцій.
Мова Сі містить засоби лише послідовного управління ходом обчислень: не містить засобів мультипрограмування і паралельних процесів.
Основна філософія мови Сі ґрунтується на тому що програміст знає, що робить і явно вказує ці наміри. Тому мова Сі не є “строго типізованою” мовою. Крім того, рівень пріоритетності виконання деяких операторів не є загальноприйнятим, деякі синтаксичні конструкції вимагають покращення. Не звертаючи увагу на деякі недоліки, мова Сі є ефективною і виразною мовою, придатною для широкого кола задач.
Алфавіт мови Сі
Програма в мові Сі записується символами алфавіту, який містить:
1)великі і малі букви латинського алфавіту;
2)десяткові цифри від 0 до 9;
3)спеціальні символи: “,”, [,],(,),{,},+,-,/,%,\,;,:,?,<,>,+,-,|,^,&,*,#.
Із символів складаються базові елементи мови.
Правила запису імені змінної або іменованої константи (ідентифікатора):
Ідентифікатори складаються з букв, цифр і знаку підкреслення (“-”) (до складу ідентифікатора не може входити будь-який спеціальний символ).
Першим символом повинна бути буква. Не можна починати ідентифікатори із знаку підкреслення оскільки багато змінних бібліотечних програм починається саме з цього знаку.
Не можна плутати в ідентифікаторах великі і малі букви (Х і х - це два різні ідентифікатори). Здебільшого імена змінних набирають малими буквами, а іменовані константи - великими.
Ідентифікатори не можуть співпадати з ключовими словами мови Сі.
Довжина ідентифікатора: для зовнішніх імен не більше 6 символів; для внутрішніх - не більше 31 символу.
2.2 Типи і розміри даних
У мові Сі дані поділяються на 2 групи:
1)прості або скалярні;
2)складні або структуровані.
Для скалярних даних існують такі базові типи:
1) char - одиничний байт, що містить один символ;
2) int - ціле число;
3) float - число з плаваючою крапкою одиничної точності;
4)double - число з плаваючою крапкою подвійної тосності.
Для розширення базових типів використовуються кваліфікатори:
1) short - короткий; 2) long - довгий
Ці кваліфікатори застосовуються до цілого типу: short int (можна писати просто short) - короткий цілий. Наприклад, якщо ціле число типу int може займати в пам’яті машини або 16 біт або32 біти, то long займає 32 біти, а short - 16 біт.
Кваліфікатор long може розширювати тип double. Тип long double - числа з плаваючою крапкою підвищеної точності.
Кваліфікатор 1)signed - із знаком; 2)unsigned - без знака - використовуються до типу int i char. Якщо значенню char відводиться 8 біт, то unsigned приймає значення від 0 до 255, а signed від -128 до 127
У мові Сі не існує логічного або булевського типу, хоча логічні операції використовуються. Треба запам’ятати, що значенню “істина” відповідає “не нуль”, тобто будь-яке число, що не дорівнює нулю, а “не істина” - “нуль”.
Константи
Константи можуть бути тих самих типів що і змінні:
1) цілого: 1024
2) цілий довгий: 124727119L - останне літера L (або l);
3) беззнаковий довгий: 124727429UL - останні літери UL (або ul);
4) з плаваючою крапкою 7.1425;
5) в експоненціальній формі 0.742е-1;
6) символьні константи ‘X’,’L’,’0’.
Крім цього константи можуть бути представлені як вісімкове число, або як шістнадцяткове число;
7) вісімкове число 037 починається з цифри 0;
8) шістнадцяткове число 0Х1F - починається з 0Х.
Декларації
Всі змінні в програмі Сі повинні бути описані (задекларовані) до того як будуть використані. Деякі декларації можуть бути неявними. Декларація вказує тип і містить список одної або кількох змінних
int i,k,ms[20];
char C, cl;
Одночасно з декларацією змінних можлива і їх ініціалізація (задання початкового значення):
char ls=’0’;
іnt k,l,lk[20], I=1;
float eps=1. 0e-5.
До будь-якої змінної в декларації можна використати кваліфікатор const, тоді змінна перетворюється в константу, тобто її значення при виконанні програми не змінюється.
const int n=20;
const double l=2.71828182.
Структура програми
По аналогії з Паскалем і Фортраном програма на мові Сі складається з двох частин:
1) заголовка, 2)тіла програми.
Заголовок складається з директив препроцесора і імені функції. Тіло програми або функції являє собою набір операторів і міститься в фігурних дужках “{}”, що аналогічно оператором Веgin і end у Паскалі. Ознакою закінчення оператора є символ крапка з комою “;”.
В одному рядку може бути кілька операторів як і у Паскалі, але бажано дотримуватись правила “одна стрічка - один оператор” (як у Фортрані), тоді програма більш наглядна і легше читається.
Коментарі в мові СІ обмежуються символами /* і */.
Наведемо приклад простенької програми за допомогою якої вводимо з клавіатури символ, а на екран виводимо код цього символа.
# include<stdio.h> /* заголовок */
main()
{
char ch.
рrintf (введіть символ\n”); /*тіло функції}*/
scanf (“%с”, &ch);
printf(“\n код символу %C:%d)\n”,ch,ch);
}
Кожна програма на мові Сі складається з функцій. Функції в Сі подібні до підпрограм і функцій в Фортрані і до процедур і функцій в Паскалі. В наведеному прикладі це функція main () -основна програма пусті дужки при імені функції означають, що ніяких вхідних параметрів основна програма не потребує. Стрічка # include<stdio.h>вказує компілятору, що необхідно включити інформацію, яка міститься у файлі stdio.h - стандартна бібліотека вводу-виводу. Значок # означає, що це директива препроцесора. Значки “<>” означають, що це стандартні файли, якими комплектується компілятор Сі.
В наведеному прикладі функція main складається з 4 операторів.
char ch; - опис типу змінної ch.
рrintf (“введить символ \n”); - виклик бібліотечної функції виводу на друк.В дужках задається список виводу. В даному випадку друкується стрічка символів, що міститься в подвійних лапках.
введить символ
Значок \n - перехід на наступну стрічку. scanf (“%с”, &ch); - виклик бібліотечної фукнції форматного вводу.
Аргументами цієї функції є:
1)специфікатор формату: “%c”; 2)вказівник на змінну сh; &ch.
Слід пам’ятати, що для того щоб ввести за допомогою функції scanf якесь значення і присвоїти його змінній одного з основних типів, перед іменем змінної необхідно записати символ “&”(крім char).
Специфікатор формату відображає тип змінної, що виводиться на друк або вводиться з клавіатури.
Розрізняють такі специфікатори формату:
%d- десяткове ціле число:
%f - число з плаваючою крапкою, десятковий запис;
%e - число з плаваючою крапкою, експоненціальний запис;
%g - число з плаваючою крапкою або десятковий або експоненціальний запис аналогічно формату G у Фортрані. Використовується тільки при виводі змінних;
%c - один символ;
%s - строка символів;
%u - десяткове ціле без знаку;
%o - вісімкове ціле число без знаку;
%x - шістнадцяткове ціле число без знаку.
Четвертий оператор тіла програми
printf(“\n код символу ‘%с’:%d)\n”,ch,ch); виведе на екран повідомлення “код символу” тоді символ, який Ви набрали з клавіатури, в лапках, а тоді ціле число, що є кодом ASCII цього символа.
Операції
Умовно операції в мові Сі можна розбити на такі групи:
Операції аналогічні операціям в мові Паскаль і Фортран.
1)Арифметичні операції: унарні: +;-; бінарні +;-;*;/; (додавання, віднімання, множенні, ділення)
До операції ділення в сові Сі потрібно відноситись дуже уважно. Якщо обидва операнди цілого типу, то і результат буде цілого типу, тому S=2/5; в результаті виконання цього оператора S присвоїться 0, щоб одержати правильний результат необхідно щоб хоча б один операнд був дійсного типу, тобто S = 2.0 /5.0;
У мові Сі є ще одна бінарна операція % - знаходження залишку від ділення цілих чисел.
K=7% 2; - присвоїти змінній цілого типу К значення 1, оскільки 7:2=3 і 1 залишок. До змінних дійсного типу ця операція не застосовується.
2)Операції порівняння: >; >=; <; <=;
3)Операційні рівності: = = - рівне; != - не рівне
4)Логічні операції: ! - логічне “ні”; || - логічне “або”;
&& - логічне “і”.
Операції відсутні в мовах Паскаль і Фортран:
Інкрементні та декрементні операції.
Інкрементна операція ++ додає 1 до свого операнда.
Оператор n++; можна записати n=n+1;
Декриментна операція - - віднімає 1 від свого операнда. Розрізняють два види цих операцій:
1)префіксні ++n - змінна n збільшується на 1 до того, як використовується у виразі;
2)постфіксні n++ - змінна n збільшується на 1 після того, як її значення буде використано у виразі.
Для іллюстрації цих операцій виконайте таку програму
# include<stdio.h>}
main()
{
int a=1, b=1;
int aplus, plusb;
aplus=a++;
plusb=++b
рrintf (“a aplus b plusb”);
printf(“%3d%5d%5d%5d\n”, a, aplus, b, plusb);
}
В результаті виконання цієї програми одержимо: а aplus b plusb
2 1 2 2
Значення а збільшилось на 1 після того як виконалась операція присвоєння. Значення b спочатку збільшилось на 1, а тоді виконалась операція присвоєння.
Побітові операції
В мові Сі існує 6 операцій для роботи з бітами.
& - побітове “і”;
| - побітове “або”;
^ - побітове “виключаюче “або”;
~ - побітове “ні”;
>> - зсув вправо;
<< - зсув вліво.
& - побітове “і” - бінарна операція, що по розрядах порівнює два двійкові числа. Результат дорівнює 1, якщо обидва операнди рівні 1 у цьому розряді, тобто
10010011
00111101
_______
00010001
| - побітове “або”. Результат 1, якщо хоча б у одного операнда у цьому розряді 1, тобто
10010011
00111101
_______
10111111
^ - побітове “виключаюче “або” Для кожного розряда результат допівнює 1, якщо один з двох відповідних розрядів дорівнює 1, але не обидва одночасно.
10010011
00111101
_______
10101110
~ - побітове “ні” - унарна операція, яка заміняє кожну 1 на 0, а 0 на 1.
~(10010011)= =01101100
>> - зсув вправо - зсуває розряди лівого, операнда вправо на кількість позицій вказаних у правому операнді (10010011)<<2= =(00100100)
<< - зсув вліво - зсуває розряди лівого операнда вліво на кількість розрядів, що вказані в правому операнді: (10010011)>>2= =(01001100) позиції, які звільняються заповнюються нулями.
Операція
“?”:” Умовний оператор if у мові Сі можна замінити операцією виду
“?”:”
z=(a<b)?a:b;
Цей оператор відповідає оператору умовного переходу такого виду:
if(a<b)
z=a;
else
z=b;
Операція присвоєння.
У мовах Паскаль і Фортран такої операції не було. Було поняття “оператор присвоєння”. У мові Сі немає одностойкості у
застосуванні термінів “оператор” і операція. Так у [1,2] термін “оператор” застосовується і як поняття інструкція і як поняття “операція”, в [3,4] ці поняття розділені аналогічно мовами Паскаль і Фортран.
Операція присвоювання може мати такий вигляд:
<змінна>=<вираз>;
<змінна><знак операції>=<вираз>;
наприклад:
1)S=S+4
2)S+=4
У першому випадку операція присвоювання аналогічна оператору присвоювання у Паскалі і Фортрані, у другому - знак арифметичної операції виноситься за знак “=”;
В операції присвоювання можуть використовуватись такі операції:
+,-,*,/,%,<<,>>,&,|
Пріорітет і порядок виконання операцій.
В таблиці 2.1.1 приведено пріоритет і порядок виконання операцій
Таблиця 2.1.1.
Стандартні функції
Основні математичні функції описуються в файлі <math.h> і приводяться в таблиці 2.1.2.
Таблиця 2.1.2.
Перетворення типів
В операторах і виразах бажано використовати змінні і константи однакового типу. Якщо у виразі є змішування типів компілятор автоматично перетворить типи за такими правилами.
Якщо операція виконується над змінними різних типів, то оббидві змінні переводяться до “вищого” з двох типів.
Порядок типів від “вищого” до “нижчого” має такий вигляд:
а)double;
в)float;
г)long;
д)int;
е)short;
є)char.
Оператори
Будь-яка програма складається з послідовності операторів. Ознакою закінчення оператора є крапка з комою “;”. Так запис S=5 не є оператором, це просто вираз, а S=5; це вже оператор присвоювання. Аналогічно Паскалю у мові Сі розрізняють прості оператори і блоки.
Блок - це група операторів, що міститься у фігурних дужках, вони використовуються:
1)щоб згрупувати кілька логічно зв’язаних операторів в один;
2)як тіло функції;
3)для локалізації дії описів.
2.2. Опис мови програмування Pascal.
Алфавіт мови Паскаль складається :
Великі і малі літери латинського алфавіту від А до 2 і знак підкреслювання.
Арабські цифри від 0 до 9.
Прості спеціальні символи: + , - , * , / , : , ; , ‘ , {,} ,[,],^,(,), _ ,” .
Складені спеціальні символи '..', ':=','<>', '>=', '<='.
Службові (зарезервовані) слова.
Елементарними конструкціями мови Pascal є:
1) імена або ідентифікатори;
2)числа;
3)рядки.
Всі імена, які використовуються в програмі для означення різних об'єктів і конструкцій називаються ідентифікаторами. Розрізняють дві групи ідентифікаторів:
-стандартні ідентифікатори;
-ідентифікатори користувача;
Стандартні ідентифікатори для визначення заздалегідь означених розробником мови об'єктів.
Числа в мові Pascal записуються в десятковій системі числення. Вони можуть бути цілими і дійсними.
Цілі числа записуються набором цифр і в пам'яті машини представляються дискретно. Діапазон значень цілого числа залежить від кількості двійкових розрядів ЕОМ. Для шістнадцяти-розрядних ЕОМ лежать в межах -32768-32767. Числа дійсного типу мають дві форми запису:
1) з фіксованою крапкою;
2) з плаваючою крапкою.
Число з фіксованою крапкою записується у вигляді цілої та дробової частини, розділеної крапкою. Числа з плаваючою крапкою використовуються для запису як дуже великих так і дуже малих чисел. Десятковий порядок записується буквою Е.
Числа дійсного типу в пам'яті не представляються дискретно. Діапазон зміни дійсного числа залежить від класу ЕОМ і лежить в межах - 1О^38-1О^38.
Рядки — це послідовність символів, записаних між апострофами.
Константа - це значення, яке не змінюється в процесі виконання програми. Константи записуються або значеннями: 2.73, 5, або імена ми : Pi, EPS - іменовані константи. Константи можуть бути дійсного, цілого логічного і символьного типів. Якщо в програмі використовуються іменовані константи, то вони повинні бути описані в розділі визначення констант. Тип константи розпізнається компілятором автоматично по її значенню.
Змінні використовуються для запису значень, які міняються в процесі виконання програми. Вибір імені (ідентифікатора) змінної бажано узгоджувати з її змістом. В Паскалі розрізняють прості змінні і змінні з індексами. Прості змінні записуються своїми ідентифікаторами і можуть належати до різних типів: цілого, дійсного, символьного і логічного. Змінні з індексом - це елементи масиву, наприклад А[4], В[1]. Всі змінні, що використовуються в програмі повинні бути описані у розділі опису змінних VAR.
В мові Паскаль існує чотири стандартних простих типи:
REAL - дійсний;
INTEGER – цілий;
BOOLEAN- логічний;
CHAR - символьний.
Паскаль-програма складається з:
1) заголовка програми;
2) тіла програми.
Тіло програми містить два розділи:
1) розділ описів і декларацій;
2) розділ операторів.
Розділ операторів - це основний розділ програми, в якому відображається зміст поставленої задачі. Розділ операторів починається службовим словом BEGIN і закінчується словом END. Оператори розділяються символом ';': - крапка з комою. Паскаль-програма закінчується крапкою '.'. Крапка - це команда для компілятора, що вже можна компілювати програму, вона закінчена. В одному рядку Паскаль-програми може бути як один так і кілька операторів.
В залежносіті від типу операндів і типу результату розрізняють три групи операцій:
1) арифметичні операції;
2) операції порівняння;
3) логічні операції.
При виклику стандартної функції слід вказати її їм 'я і в дужках її аргумент. В Паскалі є такі стандартні функції:
ABS(X) – модуль Х;
SQR(X) – квадрат Х;
SIN(X) – синус Х;
COS(X) – косинус Х;
EXP(X) – експонента Х;
LN(X) – логарифм Х;;
SQRT(X) - корінь квадратний Х;
ARCTAN(X) – арктангенс Х;
TRANS(X) – ціла частина Х;
ROUND(X) – заокруглення Х;
ORD(X) – визначення коду символу;
CHR(X) – обернена операція;
3. Існуючі методи реалізації інтерпретатора.
3.1 Зворотна польська нотація. (Польський запис).
Інтерпретатор - це програма, яка як вхід допускає програму на вхідному язиці і у міру розпізнавання конструкцій вхідної мови реалізує їх, виводячи на виході результати обчислень, написані перед цим початковою програмою.
Однієї з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики. В зв'язку з цим одній з перших областей системного програмування сформувалося дослідження способів виразів. Тут були отримані численні результати, проте найбільше розповсюдження отримав метод трансляції за допомогою зворотного польського запису, який запропонував польський математик Я. Лукашевіч.
Приклад:
Хай був заданий простий арифметичний вираз вигляду:
(A+B)*(C+D)-E (1)
Представимо цей вираз у вигляді дерева, в якому вузлам відповідають операції, а гілкам - операнди. Побудову почнемо з кореня, як який вибирається операція, що виконується останньої. Лівій гілці відповідає лівий операнд операції, а правої гілки - правий. Дерево виразу (1) було показано на рис. 3.1.1.
-
/ \
/ \
* E
/ \
/ \
/ \
/ \
+ +
/ \ / \
/ \ / \
А B З D
рис. 3.1.1
Вчинимо обхід дерева, під яким розумітимемо формування рядка символів з символів вузлів і гілок дерева. Обхід робитимемо від най лівішої гілки управо і вузол переписувати у вихідний рядок тільки після розгляду всіх його гілок. Результат обходу дерева має вигляд:
AB+CD+*E- (2)
Характерні особливості виразу (2) полягають в проходженні символів операцій за символами операндів і у відсутності дужок. Такий запис називається зворотним польським записом.
Зворотний польський запис володіє рядом чудових властивостей, які перетворюють її на ідеальну проміжну мову при трансляції. По-перше, обчислення виразу, записаного в зворотному польському записі, може проводитися шляхом однократного перегляду, що є вельми зручним при генерації об'єктного коду програм, наприклад, обчислення виразу (2) може бути проведено так як показано у табл. 3.1.1.
Табл. 3.1.1
Тут r1, r2 - допоміжні змінні.
По-друге, отримання зворотного польського запису з початкового виразу може здійснюватися вельми просто на основі простого алгоритму, запропонованого Дейкстpой. Для цього вводиться поняття стекового пріоритету операцій (табл. 3.1.2):
Таблиця 3.1.2
Є видимим початковий рядок символів зліва направо, операнди переписуються у вихідний рядок, а знаки операцій заносяться в стек на основі наступних міркувань:
а) якщо стек порожній, то операція з вхідного рядка переписується в стек;
б) операція виштовхує із стека всі операції з великим або рівним пріоритетом у вихідний рядок;
в) якщо черговий символ з початкового рядка є відкриваюча дужка, то він проштовхується в стек;
г) закриваюча кругла дужка виштовхує всі операції із стека до найближчої відкриваючої дужки, самі дужки у вихідний рядок не переписуються, а знищують один одного.
Процес отримання зворотного польського запису виразу (1) схематично був представлений на рис. 3.1.3:
Мал. 3.1.3
3.2 Скінченні автомати.
В основі побудови компіляторів лежить теорія автоматів. Автомат - це не реально існуючий пристрій, а деяка математична модель, властивості і поведінку якої можна вивчити і яку можна імітувати на реальній ЕОМ.
Скінченний автомат - це найпростіша з моделей теорії автоматів.
Скінченним називається автомат, у якому множина внутрішніх станів і множина вхідних значень є скінченними множинами.
Скінченний розпізнавач - це модель пристрою із скінченним числом станів, які відрізняють правильно утворені ланцюжки символів від неправильних (недопустимих).
Вхідна стрічка - це послідовність комірок, кожна комірка містить тільки один символ Із скінченного вхідного алфавіту. Крайню ліву і крайню праву комірки можуть займати кінцеві . маркери.
Вхідна головка у кожний момент часу читає одну вхідну комірку.
Пам'ять розпізнавача - це будь-яке сховище інформації або даних. Оскільки алфавіт скінченний, то об'єм пам'яті скінченний.
Керуючий пристрій є ядром розпізнавача. Це програма, яка керує роботою (поведінкою) розпізнавана. Керуючий пристрій - це скінченна множина станів разом з відображенням, яке описує як змінюються стани відповідно до поточного вхідного символу та інформацією, добутою із пам'яті.
Роботу розпізнавача можна відобразити в термінах його конфігурації:
1. Стан керуючого пристрою;
2. Вміст вхідної стрічки і положення вхідної головки;
3. Вміст пам'яті.
Конфігурація е початковою, якшо керуючий пристрій знаходиться у заданому початковому стані, вхідна головка може читати крайній лівий символ у стрічці і пам'ять має наперед установлений вміст.
Конфігурація є кінцевою, якщо керуючий пристрій знаходиться в одному з наперед визначених множиною кінцевих станів, а вхідна головка може читати правий кінцевий маркер, або, в разі його відсутності, вона зійшла з правого кінця вхідної стрічки.
Формально скінченний розпізнавач визначається за п'ятьма характеристиками:
1. Скінченною множиною станів;
2. Скінченним вхідним алфавітом;
3. Множиною переходів, які відображають поведінку керуючого пристрою:
4. Початковим станом ;
5. Множиною кінцевих станів .
ПРИКЛАД ПОБУДОВИ СКІНЧЕННОГО АВТОМАТА
Прикладом скінченного автомата може бути контролер непарності "1" з ланцюжку символів, що складається з нулів і одиниць. Скінченний автомат буде допускати усі ланцюжки, які містять непарну кількість "І" і відкидати ті з них, які містять парну кількість "1".
Вхідним алфавітом 2 такого автомата буде множина {0,1}.
Множина станів О. буде складатись із двох станів ПАР і НЕПАР.
Початковим станом 8 буде стан ПАР.
При читанні наступного вхідного символу стан автомата змінюється. Новий його стан залежить від вхідного символу і поточного стану.
Один із зручних методів подання скінченного автомата є таблиця переходів. Правила побудови таблиці такі:
1. Стовпці помічено символами вхідного алфавіту.
2. Рядки помічено символами станів.
3. Елементи таблиці є символами нових станів, які визначаються вхідним символом і попереднім станом.
4. Перший рядок помічено символом початкового стану.
5. Рядки, які відповідають допускаючим станам, помічені справа одиницями: рядки, які відкидаються автоматом, помічаються справа нулями.
Для нашого автомата таблиця переходів показана на рис.2.
Крім табличного подання, скінченний автомат можна подати діаграмою (або графом) переходів.
НЕДЕТЕРМІНОВАНІ СКІНЧЕННІ АВТОМАТИ
Скінченний автомат, приклад якого наведено у попередньому розділі, належить до детермінованих скінченних автоматів.
Детермінованим називається скінченний автомат, у якого для кожної конфігурації існує тільки один наступний крок.
Недетермінованим називається скінченний автомат, у якого для кожної конфігурації існує скінченна множина можливих подальших кроків.
СПОСОБИ ПОДАННЯ СКІНЧЕННИХ АВТОМАТІВ НА ЕОМ
Розглянемо деякі проблеми, що пов'язані з реалізацією скінченного автомата як програми або підпрограми для обчислювальної машини.
. Найчастіше за допомогою скінченних автоматів вирішують задачі розпізнавання скінченної множини слів. Такі задачі називають проблемою "ідентифікації", оскільки дія компілятора залежить від ідентичності вхідного ланцюжка автомата деякому відповідному слову.
Щоб промоделювати скінченний автомат, необхідно якимось чином закодувати його вхідну множину символів. Крім того, необхідно запам'ятати стани модельованого автомата і таблицю переходів.
Скінченні автомати можна подати на ЕОМ у вигляді матриці переходів або у вигляді зв'язаної шнекової, структури.
Для подання скінченного автомата у вигляді спискової структури використовуються динамічні об'єкти типу однонаправленого списку, одне поле якого є вхідним символом, а інше -вказівником на список переходів до наступного стану. Перехід полягає в простій заміні вказівника списка переходів для поточного стану на одержаний .з таблиці вказівник списку переходів для наступного стану. Списки можуть бути лінійними І впорядкованими.
Скінченні автомати можуть вирішувати тільки ті задачі, які потребують-скінченного об'єму пам'яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних:вирааів виникає задача перевірки бачансу дужок, кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має свою "роль", тому використання скінченного -автомата для таких задач не прийнят не, оскільки множина станів може бути нескінченною.
Для вирішення цієї та багатьох інших проблем компіляції^ можуть використовуватись моделі потужніших автоматів. У них пам'ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один Із методів - це використання магазина (або стека). Основна особливість магазинної пам'яті полягає утому, шо символи можна поміщати у магазин І видаляти їх з нього по одному. При цьому видаляється завжди тільки верхній символ, тобто символ, який був поміщений у магазин останнім.
Коли інформація поміщається (записується) в магазин, кажуть, що вона "заштовхується", коли інформація видаляється з магазина - "виштовхується" з нього.
На дні магази на міститься спеціальний символ V, який відмічає "дно" магазина і називається - маркером дна. Він використовується тільки як мітка дна і ніколи не виштовхується з магазина.
На верху магазина міститься символ С (рис. 1,а). Символи розміщені у тому порядку, в якому вони поступали а магазин. Спочатку по ступив символ А, потім В, потім знову А і остан нім - символ С.
Якщо у магазин поступає символ О, то він вже стане верхнім (рис. 1,6). Якщо Із магазина ви штовхується символ С, то верхнім стане символ А (рис. І.в). І нарешті, якщо верхнім символом буде маркер дна, це означає, Ідо магазин порожній.
Однією з моделей автомата, з яких використовується магазинний принцип організації пам'яті, є автомат з магазинною пам'яттю (скорочено МП-автомат). У ньому дуже просто поєднується пам'ять скінченного автомата і магазинна пам'ять.
Як і у випадку скінченного автомата, обробка скінченного ланцюжка символів здійсню ється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам'яті може змінюватись за рахунок:
а) переходу у новий стан; б) заштовхування символу в магазин;
в) виштовхування символу з магазина.
Залежно від отриманої інформації керуючий пристрій обирає або перехід а новий стан, або вихід з процесу. Перехід складається з трьох типів операцій: над етапом, над магазином і над входом.
Для оптимізації процесу компіляції первісна текстова програма перекладається у деяку внутрішню форму, зручнішу для подальшої машинної обробки. Проміжна програма виробляється синтаксичним аналізатором і відображає структуру первісної програми. У той самий час оператори проміжної програми розмішуються в тому порядку, у якому вони повинні виконуватись.
Найрозповсюдженішими формами подання вхідної програми є:
1) Бездужковий закис (польський запис);
2) Тетради;
3) Тріади;
4) Зв'язані спискові структури;
5) Зображуючі дерева.
2.1. Запис бездужковий. Алгоритм Дейкстри
Запис бездужковий - подання виразу, при якому порядок виконання операцій визначається її контекстом і позицією у формулі.
Існують два види бездужкових записів: прямий, або префіксний і інверсний, або постфікс ний.
Для автоматизованих обчислень найзручніше використовувати постфіксний запис бездужковий.
Відомо декілька методів отримання постфіксного польського запису. Найефективнішим є алгоритм Дейкстри.
Цей метод базується на використанні стека для збереження знаків операцій.
Для знаків операцій пріоритет зростає в порядку, зворотному до старшинства операцій.
Алгоритмічні і логічні вирази розглядаються як вхідна стрічка символів зліва направо.
Операнди переписуються у вихідну стрічку, а знаки операцій поміщаються у стек операцій.
Якщо пріоритет вхідного знака операції дорівнює нулю або більший від пріоритету знака, який є на вер шині стека, то повий знак додається до вершини стека. В протилежному випадку із стека "виштовхується" і пе ретісується у вихідній стрічці знак, що розташований у вершині стека, а також наступні за ним злаки з пріоритетом більшим або таким, шо дорівнює пріоритету вхідного знака. Після цього вхідний знак додається до вершини стека.
Деякі особливості мас й робота з дужками. Відкриваючі дужки мають нульовий пріоритет, просто записуються у вершину стека і не виштовхують жодного знака. Виштовхувати відкриваючу дужку може тільки закриваюча. Закриваюча дужка має пріоритет І, який не перевищує пріоритету будь-якої операції. Поява закриваючої дужки викликат виштовхування усіх знаків операцій до найближчої дужки. В стек закриваюча дужка не записується і у вихідну стрічку не переноситься. Відкриваюча І закриваюча дужки взаємно знищуються.
Формування бездужкового запису за допомогою бінарного дерева
Арифметичний вираз можна подати у вигляді дерева. Вузли дерева відповідають операціям, а гілки — операндам. Ліва гілка, яка виходить з вузла, відповідає лівому операнду, права - правому. Операціям, які виконуються раніше, відповідають нижче розмішені вузли. Верхній вузол - корінь дерева відповідає операції, яка виконується останньою.
На рис.3.2.1. показане дерево виразу a+b*c-d/(a+b).
Мал. 3.2.1 abc*+dab+-.
2. Обхід бінарного дерева для одержання постфіксного польського запису
Якщо, почавши з нижнього листка крайньої лівої гілки дерева, обійти усі листки і вузли дерева, так щоб гілки розглядались зліва направо, а вузол розглядався після обходу усіх гілок, шо з нього виходять, то послідовність перегляду вузлів і листків дасть постфіксний польський запис.
Мал. 3.2.2 -+a*bc/d+ab.
Мал. 3.2.2. Обхід бінарного дерева для одержання префіксного польського запису. Якщо, почавши з верхнього вузла, обійти усі вузли і листки дерева, так щоб верхній вузол розглядався раніше ніж нижній, і одразу після розгляду вузла проглядалися зліва направо гілки, які з нього виходять, то отримаємо префіксний польський запис.
Опис свого методу.
Дивимося яка операція перша, якщо з вищим приорітетом то записуемо в одну змінну якщо з нищим то в іншу.
2. Шукаємо дужки.
Якщо знайшли, то переходимо до кроку 1.
Якщо не знайшли, то виконуємо операцію між двома змінними.
Обчислюємо і замінюємо на результуючу константу.
Виводимо результат.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора