Міжнародний інститут інженерно-фізичний інститут                      (Технічний університет)           -------------------------------------------------- ------                              Кафедра 22                        Пояснювальна записка до                            КУРСОВИЙ РОБОТІ            на тему                     "Робота з таблицями загального користування                         на етапі лексичного аналізу мови Норма "                                   студента групи К7-02а                                            Жучкова Олександра Вікторовича    Науковий керівник:    Комісія:    Оцінка:                                Москва 1995р.                                1. ВСТУП         Завдання, отримане мною на УІР і КП в даному семестрі складалося   в наступному:         - Ознайомитися з мовою програмування Норма і вивчити його; - Вивчити структуру транслятора з мови програмування Норма;         - Ознайомлення з мовою пограммірованія РЕФА;         - Розробити структуру даних для реалізації роботи з таблицями   загального користування;         - Написати функції роботи стабліцамі.                    2. Загальний опис мови Норма         Мова програмування Норма є декларативним (непроцедурного)  мовою і призначений для специфікації чисельних методів розв'язання задач  математичної фізики. Спочатку він був орієнтований на вирішення завдань  математичної фізики різницевим методами, однак може бути використаний  для вирішення більш широкого класу обчислювальних завдань.         Типовий процес вирішення завдання з області математичної фізики  складається з наступних етапів.         1. Постановка завдання. Виходом цього етапу є звичайно система  диференціальних рівнянь, що описують завдання.         2. Вибір просторово-часової сітки і дискретизація рівнянь з  допомогою одного з різницевих методів.         3. Вибір методу розв'язання дискретних рівнянь. У результаті виходять  формули (співвідношення), опісивающійе необхідні обчислення у вузлах сітки.         4. Програмування отриманих формул на деякій мові, яка  забезпечує рішення задачі на обчислювальній машині.         Головна ідея, покладена в основу мови Норма, полягає в тому,  що отримані фахівцем у процесі розв'язання прикладної задачі розрахункові  формули майже безпосередньо використовуються для введення в обчислювальну систему  і проведення счета.Такім чином, мова Норма дає прикладного математику  можливість сформулювати своє завдання у звичних для нього термінах.         Організація процесу обчислень з урахуванням архітектури ЕОМ (можливостей  паралельної, векторної обробки і т. п.) - зто завдання транслятора з мови  Норма.         Істотним фактом є можливість реалізації однієї програми   мовою Норма різними обчислювальними процесами. Саме розробка   алгоритму з характеристиками, близькими до оптимальних і ефективно   враховують особливості конкретних ЕОМ, є найбільш вузьким місцем   створення високоякісного програмного забезпечення.         Запис на мові Норма - це, по суті, сувора запис чисельних   методів вирішення математичної задачі, запис ще не алгоритмів, а просто   розрахункових формул і решті необхідної інформації, яку необхідно   знати, щоб написати програму для ЕОМ.         Відзначимо, що в записі на Нормі не потрібно ніякої інформації про   порядку рахунку, способи організації обчислювальних (циклічних) процесів.   Порядок пропозицій мови може бути довільним - інформаційні   взаємозв'язку будуть виявлені і враховані при організації процесу рахунку   транслятором.         Вибір рівня мови Норма визначає характерну його рису - в цьому   мові немає необхідності вводити такі поняття, як оператор присвоювання і   можливість перепрісваіванія значень (типу х: = х +1) і оператори переходу.   Наявність таких понять в традиційних мовах програмування пояснюється   необхідністю формулювання конкретного алгоритму з урахуванням питань   економії і розподілу пам'яті, порядку виконання операторів і т. п.   Побічний ефект у мові Норма відсутня за визначенням.         Зрозуміло, що багато хто з цих питань з'являються знову на етапі синтезу   робочої програми. Однак, тут вони вирішуються автоматично за суворими   правилами, що гарантує правильність синтезується програми.         Непроцедурного мови Норма дозволяє подолати ще одну трудність,   пов'язану з розпаралелюванням алгоритму за рахунку на ЕОМ, що допускають   суміщення операцій. Відомі методи розпаралелювання послідовних   алгоритмів засновані на виявленні, при деяких обмеженнях, частин   алгоритму, які можна виконувати незалежно, відповідно до заданого   критерієм паралелізму - асинхронні обчислення, синхронні і т.п. Однак,   виявлення взаємозв'язків у вже сформованому послідовному алгоритмі   є неприродною і важким завданням, тому що аналізована   формулювання, як правило, насичена надлишковими взаємозв'язками (типу введення   робочих змінних для економії пам'яті, конкретні способи організації   циклів і т. п.). Взагалі кажучи, ні звідки не випливає, що послідовний   алгоритм треба транслювати в паралельний, а не визначати паралельний   відразу по непроцедурного запису.         Ці властивості, і деякі інші обмеження, дозволяють суворо   обгрунтувати розв'язність синтезу вихідний програми, тому що в досить   загальній постановці рішення цього завдання призводить до значних математичним   труднощів - вона може виявитися NP-повної або взагалі нерозв'язною. З   іншого боку, дослідження, пов'язані з розробкою і застосуванням мови   Норма показують, що наявні обмеження прийнятним з практичної точки   зору.                 3 Структура транслятора з мови Норма.         Транслятор з мови програмування Норма вже написаний на мові рефа.  І хоча мова программіорванія Рефаїл Весма зручний для обробки символьної  інформації, транслятор написаний на цій мові дуже не економно використовує  ресурси обчислювальної машини, а саме оперативну пам'ять, що найчастіше  правильно написану програми неможливо оттрансліровать з брак  оперативної пам'яті. Тому було вирішено перевести транслятор з мови  програмування Норма на мову програмування Сі, який був обраний за  наступних причин:         - Мова Сі дозволяє набагато більш ефективно використовувати ресурси  обчислювальної машини;         - Мова Сі універсальний і зручний для вирішення завдань системного  програмування - розробці трансляторів, операційних систем, екранних  інтерфейсів, інструментальних засобів;         - Розробниками мови Норма вже написаний інтерфейс на мові Сі,  дозволяє закінчені частини транслятора, написані на Рефале, замінювати на  закінчені частини транслятора, написані на Сі, для налагодження транслятора.         У процесі трансляції, вирішуються як традиційні завдання - лексичний  синтаксичний, семантичний аналіз, генерація вихідний програми, так і  завдання, що визначаються специфікою мови Норма: організація обчислень по  непроцедурного опису завдання з виявленням можливого паралелізму  обчислень, семантичний контроль можливості організації обчислень з урахуванням  можливостей вихідного мови та архітектури комп'ютера. Вихідними язикомі можуть  бути мови Фортран ВП орієнтований на багатопроцесорний варіант ЕОМ ЄС-1191  і Фортран JNS. Трансляція проводиться кожного розділу, що входить до Норма  програму, проводиться автономно: для кожного розділу або ж видається програма  на вихідному мовою, або, якщо були виявлені синтаксичні або семантичні  помилки, видається повідомлення про помилку, після чого здійснюється перехід до  трансляції чергового розділу. Транслятор з мови програмування має наступну структуру:   Вхід:   _______________ __________________________ ________________________  | початковий текст | | Лексичний аналіз | | Синтаксичний аналіз |  | програми + | -> | (Виділення лексем, | | і частково семантичний |  | опції командного | | гуппріровка лексем, | -> | аналіз описів і | ->  | рядка | | початкове заповнення | | операторів |   ---------------- | Таблиць імен і констант) | | (заповнення всіх Абліцов) |                         ------------------------- -------------------------      ________ ________________ _________     | Табл. | --- | | | Табл. | --     | | | | Менежер ПАМ'ЯТІ | | множин | |     | | | |________________| | І т.п. | |     | | | | | |     | | | | | |     |_______| | |_________| |       ---------| |_________|                                                                   Вихід:      __________________ ______________ ___________ ___________     | Побудова графа | | Органінізація | | Генерація | | Текст |  -> | інформаційних | -> | паралельних | -> | Фортран-| -> | програми |     | залежностей опе-| | обчислень | | програми | | на Фортране |     | ратора програми | -------------- ----------- -----------      ------------------   На вхід лексичного аналізатора надходить текст вихідної программи.На вихід   - Відсортований (за описами, операторам і ітерація) список лексем,   початково заповнення таблиці імен і констант. Далі цей список надходить на   вхід синтаксичного аналізатора, де відбувається розбір конструкцій-описів,   операторів, ітерацій і заповнюються таблиці імен, констант, множин, описи   операторів і ін Перед початком етапу синтаксичного аналізу, длямаксімальной   очищення пам'яті відбувається конвертація початкових таблиць імен і констант. Ці   таблиці надходять на вхід наступного етапу, де відбувається побудова графа   інформаційних залежностей, який використовується на следуещем етапі при   визначення порядку обчислень і поділ на паралельні гілки, що не залежать   один від одного. На виході отримуємо внутрішні коди. Внутрішні коди надходять   на вхід кодогенераціі. Виходом кодогенераціі є програма на мові   Фортран.         Для забезпечення доступу до верхньої пам'яті, а також для можливого свопінгу   всі операції з оперативною пам'яттю здійснюються з використанням бібліотеки   функцій менеджера пам'яті, написаної співробітниками інституту прикладної   математики.                       4 Опис і рішення задачі.         4.1 Постановка завдання.         У світлі вищесказаного перед нами (групою розробників) постало завдання   напсанія транслятора з мови Норма з використанням інструментальних засобів   мови програмування Сі та бібліотеки функцій роботи з операівной пам'яттю.   Переді нами (двома розробниками) було поставлено завдання написання функцій   роботи з таблицями імен і констант.         4.2 Рішення завдання.         Для початкового заповнення таблиць імен і констант були обрані хеш-таблиці.   При цьому ми програвали у використанні оперативної пам'яті, але вигравали у   часу (в порівнянні з "деревами"). Враховуючи підвищені вимоги до   використання пам'яті нами було рпінято рішення після закінчення етапу лексичного   аналізу (тобто після того, як завершиться попереднє заповнення таблиць імен   і констант і нам буде вточності відомо кількість ідентифікаторів і констант   використовуються в транслюється програмі) провести конвертацію пошукової частини   хеш-таблиць у безперервні масиви фіксованої довжини. При цьому ми збільшуємо   обшее час трансляції за рахунок часу конвертації, але виграємо у використанні   оперативної пам'яті за рахунок зменшення числа інформаційних полів (в хеш-таблиці   сушествует поле містить код ідентифікатора (константи), який є   ключем цього ідентифікатора (константи) в подальшій роботі транслятора, в   масиве роль ключа буде грати змішання зтого елемента від початку масиву --   індекс масиву), а так само за рахунок звільнення неісопльзуемих учасков в   хеш-таблиці (у будь-хеш-таблиці з за випадковості процесу хешування   з'являються невикористані області приблизно 30% від величини всій таблиці).   Плюсом також є умьшеніе часу пошуку по ключу. У масиве ця операція   еквавалентна взяття індексу від масиву. У хеш-таблиці поік набагато довше.         4.3 Вибір структури даних 3. ВИСНОВОК У результаті проведеної роботи мною були досягнуті следуюющіе цілі: - Ознайомилася і вивчила непроцедурного мова програмування Норма, призначений для запису чисельних методів розв'язання задач математичної фізики різницевим методами; - Вивчила структуру транслятора з мови програмування Норма; - Ознайомилася з методами лексичного аналізу; - Вивчила структуру лексичного аналізатора; - Розробила структуру даних своєї частини завдання для реалізації лексичного аналізатора; -написала функцію, на вхід якої надходить список лексем, а на виході отримуємо список списків. Елементом цього списку списків є список лексем, який являє собою одну пропозицію програми, написаної на Нормі, закінчується крапкою. Тобто ця функція "ріже" надходить на вхід список лексем по точках, а на виході отримуємо список пропозицій, кожне з яких закінчується крапкою і представляється списком лексем. Програма знаходиться на стадії розробки. Завершення роботи планується в наступному семестрі. Завдання на УІР і КП виконала повністю. Список літератури: А.Н. Андріанов, К.Н. Ефімкін, І.Б. Задихайло, Н.В. Поддерюгіна "Мова Норма" А.Н. Андріанов, К.Н. Ефімкін, І.Б. Задихайло "непроцедурного мова Норма і методи його реалізації" А.Б. Бугера "Реалізація математичних функцій мови Норма для розподілених висіслітельних систем" Додаток 1.