Курсова робота
Переглядів: 3847 Додано: 2013-03-07 Частина тексту
Мета курсової роботи – закріпити і розширити знання одержані при вивченні курсу “Проблемно-орієнтовані мови програмування”, а також розвинути навички і вміння ефективно застосовувати ПК для розв’язування прикладних задач.
Постановка задачі – розробити міні компілятор для перевірки правильності та обчислення арифметичних виразів використовуючи ефективні та швидкі методи обробки арифметичних виразів, та обмежену кількість машинних ресурсів.
АНОТАЦІЇ
Яворський Н. Б. „Розробка міні компілятора для перевірки правильності та обчислення арифметичних виразів”. Курсова робота. НУ “Львівська політехніка”, каф.: САПР, дисципліна: “Проблемно-орієнтовані мови програмування”, 2006.
Курсова робота складається з 40 сторінок, 7 таблиць, блок-схем, додатків.
В даній курсовій роботі було описано основні теоретичні відомості про мови програмування та їхні середовища. Розроблена блок-схема та алгоритм розв’язання поставленої задачі. Складено програму на алгоритмічній мові програмування С.
ЗМІСТ
МЕТА КУРСОВОЇ РОБОТИ ТА ПОСТАНОВКА ЗАДАЧІ
АНОТАЦІЇ
ЗМІСТ
ВСТУП
- ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ ПРО МОВИ ПРОГРАМУВАННЯ ТА ЇХ СЕРЕДОВИЩА
- АЛГОРИТМІЧНА МОВА ПРОГРАМУВАННЯ С
- СПИСКИ, СТЕКИ, ЧЕРГИ, КІЛЬЦЯ
- ДЕРЕВА
- ПОБУДОВА ЗВОРОТНОГО ПОЛЬСЬКОГО ЗАПИСУ
- КОДУВАННЯ СИМВОЛІВ
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
АНАЛІЗ ЗАДАЧІ 25
БЛОК – СХЕМА ПРОГРАМИ
- ЗАГАЛЬНИЙ ВИГЛЯД
- ОКРЕМО ПО ФУНКЦІЯХ
ТЕКСТ ПРОГРАМИ НА МОВІ С
ОПИС ПРОГРАМИ
РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАМИ
АНАЛІЗ РЕЗУЛЬТАТІВ ТА ВИСНОВКИ
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Потрібно змоделювати калькулятор, який обчислює арифметичні вирази. Вираз складається з чисел, дужок і знаків бінарних операцій: + , - , * , / . Перевірити правильність запису виразу, обчислити значення цього виразу.
Вхідні дані(вводяться з клавіатури): символьний рядок (довжиною до 255 символів), який містить арифметичний вираз із чисел, знаків операцій і круглих дужок.
Результуючі дані: число – значення виразу, або повідомлення про некоректність виразу.
АНАЛІЗ ЗАДАЧІ
Дану задачу потрібно розбити на дві частини, це перевірка правильності виразу і обчислення самого виразу.
Для ефективного обчислення виразів буде недостатньо простого підходу, бо переглядаючи вирази які містять багато дужок, в тому числі і вкладених —доведеться кілька разів переглядати одну і ту ж частину рядка, на що витрачається зайвий час. Для уникнення цієї проблеми використовується постфіксний (Польський) запис рядка.
Наступна проблема це використання пам’яті. Потрібно продумати розв’язок так щоб використовувати якнайменше машинних ресурсів, для цього використовуються списки та стеки.
Перша частина програми перевірятиме правильність виразів а саме: перевірка правильності розстановки дужок, співпадання кількості відкриваючих та закриваючих дужок та вирахування синтаксичних помилок на кшталт два знаки операцій підряд або наявність стороннього символу.
Для перевірки співпадання кількості відкриваючих та закриваючих дужок використовується стек в який при зустрічі відкриваючої дужки заноситься елемент, а при зустрічі відкриваючої – видаляється, в результаті посимвольного проходження рядка, якщо при спробі видалити елемент зі стека, виявиться що той пустий або після проходження рядка стек залишиться не порожній то дужки в виразі розставлені неправильно.
Для перевірки інших умов правильності достатньо використати звичайне порівняння сусідніх символів рядка.
Друга частина програми має за мету обчислити вираз, для цього він попередньо переписується в постфіксний (польський) запис для збільшення швидкодії обчислення та спрощення. Елементи польського запису по черзі заносяться в двозв’язний список яким пізніше легко оперувати при обчисленні, причому числа з виразу перетворюються за допомогою таблиці кодів ASCII з символів в машинні числа які підлягають обробці математичними операціями, алгоритм перетворення базується на почерговому перегляді кожного елемента рядка і в залежності яким він буде (цифра, знак чи дужка) над елементом проводяться відповідні операції (перетворення, запис в список).
При обробці списку виконується лише один його обхід, отримані дані обробляються та видаляються, результат заносяться назад в список (під час кожної обробки видаляється два елементи списку), обхід триває поки не залишиться один елемент який буде містити в собі кінцевий результат.
Для зручності деякі дії, які будуть неодноразово повторюватись (запис елементу в стек/список, його видалення…) розбиваються на окремі функції.
Програма не матиме обмежень по кількості вхідних даних (крім обмежень на довжину рядка), бо виділення пам’яті для зберігання чисел та знаків проводитиметься динамічно в процесі виконання програми. Також програма зможе швидко обчислювати вирази які містять багато дужок, оскільки ті будуть видалені і вираз проглядатиметься лише один раз.
Варто відмітити, що такий спосіб трансляції арифметичних виразів використовують багато компіляторів та вбудованих калькуляторів різних програм, оскільки він дає змогу швидко обраховувати довгі вирази з великою кількістю дужок.
Для порівняння можна протестувати вхідні результати в інших програмах з подібними алгоритмами обчислення виразів (наприклад MS Excel).
АНАЛІЗ РЕЗУЛЬТАТІВ ТА ВИСНОВКИ
В даній курсовій роботі було описано основні теоретичні відомості про мови програмування та їхні середовища. Розроблена блок-схема та алгоритм розв’язання поставленої задачі. Складено програму на алгоритмічній мові програмування С. Було поглиблено теоретичні знання по засобах проблемно-орієнтованих мов програмування. Розширено знання одержані при вивченні дисциплін основи програмування. Вивчено постфіксний (польський) запис арифметичних виразів.
При розв’язуванні поставленої задачі було використано складні та ефективні алгоритмічні методи які використовуються при побудові складних арифметичних задач орієнтованих на велику кількість вхідних даних та високу ефективність розв’язку задачі.
Було проведено аналіз використання машинних ресурсів при роботі програми.
Було проведено порівняльний аналіз результатів виконання програми з іншою, вже налагодженою програмою, результати виконання співпадають.
