МОСКОВСЬКИЙ ДЕРЖАВНИЙ інженерно-фізичний інститут
(технічний університет)
Кафедра 22
Пояснювальна записка до
КУРСОВИЙ РОБОТІ
на тему:
"Синтаксичний аналіз мови НОРМА. Розбір описів"
студента групи К9-02а
Жучкова Олександра Вікторовича
Науковий керівник:
Комісія:
Оцінка:
Москва 1996р.
1. ВСТУП
Завдання, отримане мною на УІР і КП в даному семестрі булопродовженням групової роботи, що почалася в попередніх семестрах, іполягало в наступному:
. вивчити розділ описів мовних конструкцій Норми;
. розробити структури даних і алгоритми для розбору описів мови програмування Норма, з урахуванням специфіки мови, а так само зручності написання функцій, необхідних для подальшої роботи транслятора;
. написати функції розбору розділу описів;
. написати деякі робочі функції оперують з областями
2. Загальний опис мови Норма
Мова програмування Норма є декларативним (непроцедурного)мовою і призначений для специфікації чисельних методів розв'язання задачматематичної фізики. Спочатку він був орієнтований на вирішення завданьматематичної фізики різницевим методами, однак може бути використанийдля вирішення більш широкого класу обчислювальних завдань.
Головна ідея, покладена в основу мови Норма, полягає в тому, щоотримані фахівцем у процесі розв'язання прикладної задачі розрахунковіформули майже безпосередньо використовуються для введення в обчислювальнусистему і проведення рахунку. Таким чином, мова Норма дає прикладногоматематику можливість сформулювати своє завдання у звичних для ньоготермінах. Запис на мові Норма - це, по суті, сувора записчисельних методів розв'язання математичної задачі, запис ще не алгоритмів,а просто розрахункових формул і решті необхідної інформації.
Відзначимо, що в записі на Нормі не потрібно ніякої інформації пропорядку рахунку, способи організації обчислювальних (циклічних) процесів.
Порядок пропозицій мови може бути довільним - інформаційнівзаємозв'язку будуть виявлені і враховані при організації процесу рахункутранслятором. Ця можливість, звичайно, збільшує трудомісткість іскладність при компіляції тексту програми, але розробники мовисвідомо пішли на це, щоб зробити дану мову зручним длявикористання широким колом фахівців-математиків, що мають невеликийдосвід роботи на комп'ютері.
Вибір рівня мови Норма визначає характерну його рису - в цьомумові немає необхідності вводити такі поняття, як оператор присвоювання іможливість перепрісваіванія значень (типу х: = х +1) і оператори переходу.
Наявність таких понять в традиційних мовах програмування пояснюєтьсянеобхідністю формулювання конкретного алгоритму з урахуванням питаньекономії і розподілу пам'яті, порядку виконання операторів і т. п.
Побічний ефект у мові Норма відсутня за визначенням. Зрозуміло, щобагато хто з цих питань з'являються знову на етапі синтезу робочоїпрограми. Однак, тут вони вирішуються автоматично за суворими правилами,гарантує правильність синтезується програми.
непроцедурного мови Норма дозволяє подолати ще одну трудність,пов'язану з розпаралелюванням алгоритму за рахунку на ЕОМ, що допускаютьсуміщення операцій. Відомі методи розпаралелювання послідовнихалгоритмів засновані на виявленні, при деяких обмеженнях, частиналгоритму, які можна виконувати незалежно, відповідно до заданогокритерієм паралелізму - асинхронні обчислення, синхронні і т.п. Однак,виявлення взаємозв'язків у вже сформованому послідовному алгоритміє неприродною і важким завданням, тому що аналізованаформулювання, як правило, насичена надлишковими взаємозв'язками (типувведення робочих змінних, конкретні способи організації циклів і т.п.). Взагалі кажучи, ні звідки не випливає, що послідовний алгоритмтреба транслювати в паралельний, а не визначати паралельний відразу понепроцедурного запису.
Ці властивості, і деякі інші обмеження, дозволяють суворообгрунтувати розв'язність синтезу вихідний програми, тому що в доситьзагальній постановці рішення цього завдання призводить до значних математичнимтруднощів - вона може виявитися NP-повної, або взагалі нерозв'язною. Зіншого боку, дослідження, пов'язані з розробкою і застосуванням мови
Норма показують, що наявні обмеження прийнятним з практичної точкизору.
3 Структура транслятора з мови Норма.
Транслятор з мови Норма відразу проектувався як багатопрохідним. Наперший проході на вхід лексичного аналізатора надходить текст вихідноїпрограми (див. додаток 1), який перетворюється в послідовностілексем, об'єднані в кванти *. Паралельно відбувається початкове заповненнятаблиць імен і констант, після цього ці таблиці з хеш-структурперетворюються в масиви. Це робиться для максимального звільненняоперативної пам'яті перед наступними проходами, а також для прискореннядоступу, тому що далі йде дуже інтенсивний звернення до цих таблиць. Надругому проході відбувається сортування цих квантів за певними правилами.
Відсортувати список квантів надходить на наступному проході на вхідсинтаксичного аналізатора, який розбирає опису мовнихконструкцій, оператори введення, оператори виведення, оператори присвоювання іт.д. У результаті роботи сінаксіческого аналізатора заповнюються безлічробочих таблиць: областей, умов і т.п. На наступному проході за данимитаблиць відбувається визначення інформаційних залежностей міжоператорами, визначається порядок обчислення. Далі, щоб не сильно пов'язанихкомпонентів методом знаходження гіперплоскостей відбувається розпаралелюванняокремих фрагметов програми. Після чого генерується вихідна фортран -програма.
Для забезпечення доступу до верхньої пам'яті, а також для можливогосвопінгу практично всі операції з оперативною пам'яттю здійснюються звикористанням бібліотеки функцій менеджера пам'яті, написаної співробітникамиінституту прикладної математики.
4 Опис і рішення задачі.
4.1 Постановка завдання.
У програмі, написаній на мові Норма можуть зустрічатися наступніспецифічні об'єкти:
. параметри областей, які визначають у неявному вигляді межі діапазонів при описі областей;
. індекси областей, які задають як би імена різним кордінатним напрямками в областях.
. індекси розподілу, що служать для відображення двох індексних напрямків індексного простору області завдання на матрицю процесорних елементів (ПЕ) розподіленої системи;
. індексні конструкції, що служать для скорочення запису складних індексних виразів;
. зовнішні функції і розділи;
. області;
. скалярні величини і величини на області
(синтаксис дивись додаток 2).
Як видно з перерахованого вище, найбільш важливим та інформативнимоб'єктом є опис області. Дійсна, і індекси і параметриобласті є лише допоміжними поняттями, що роблять описуобластей більш легким для читання або більш гнучкими. Для величин, визначенихна області, їх області є тим безліччю, на якому вони існують.
Поняття області введено в мові Норма для представлення поняття індексногопростору. Область - це сукупність цілочисельних наборів (i1 ,..., in),n> 0, ij> 0, j = 1 ,..., n, кожен з яких задає координати точки n-мірногоіндексного простору. З кожним напрямом (віссю координат) n-мірногопростору завдання зв'язується унікальне ім'я - ім'я-індексу (ім'я осікоординат індексного простору). Слід зазначити, що областьвизначає значення координат точок індексного простору, а не значеннярозрахункових величин в цих точках. Так само слід відзначити те, що всібезлічі повинні бути кінцеві, тому що звичайно простір пам'яті ЕОМ, нащо будуть надалі відображатися величини на області.
Розробники мови Норма на підставі досвіду, накопиченого ними прирішенні задач обчислювальної математики, вирішили, що для вирішеннябільшості задач подібного класу достатньо ввести наступнірізновиди областей:
. прямокутні;
. діагональні;
. умовні.
У світлі вищесказаного перед нами (групою розробників) постало завданнянапсанія транслятора з мови Норма з використанням інструментальнихзасобів мови програмування Сі та бібліотеки функцій роботи з оперативноюпам'яттю. Переді мною було поставлено завдання:
. розробка структур для зберігання даних, отриманих в результаті розбору описів областей;
. розробка алгоритмів і написання функцій розбору описів;
. розробка алгоритмів для написання функцій перетину областей
4.2 Рішення завдання. Вибір структури даних
Проаналізувавши відмінності і схожість тієї інформації, яку необхіднозберігати для кожного різновиду області, мною, при узгодженні зрозробниками мови і моїми колегами, були обрані наступніструктури. (дивися додаток 4).
По-перше, головна таблиця областей (далі просто таблиця областей), вякої для всіх областей зберігається кількість напрямів (мірністьбезлічі), по кожному напрямку ім'я індексу та значення лівої і правоїкордонів, тип області, ключ для пошуку детальної інформації в іншихтаблицях. Вирішено було ввести чотири типи області: прямокутна - вонахарактерна тим, що проекцією на будь-яку двовимірну систему координат будепрямокутник; діагональна - це область, межі якої за деякиминапрямками можуть бути прямі під кутом 45 (до осі; позитивно-умовні --це частина батьківського області, на якій логічне вираження, що задаєцю область буде видавати значення правда; негативно-умовні - це теж, що і позитивно-умовні, тільки логічне вираження видаватимезначення брехня. Вийшло так, що таблиця областей вийшла неоднорідною, такяк можуть існувати області з різною кількістю напрямків. Зберігатицю таблицю в масиві з розміром полів, розраховані на максимальноможливу кількість напрямів, я вважав нераціональним. Буларозглянуто можливість реалізації зберігання на списках, але ця можливістьмною теж була відкинута, тому що вийшов би список з великимкількістю дрібних елементів, що ускладнило б роботу менеджера пам'яті
(якому на кожен такий елемент довелося б заводити робочі структури,що теж використовувало б пам'ять), а також збільшило б час роботи.
Тому було вирішено зберігати ці таблиці в одному великому буфері і матиспеціальні функції, що дозволяють проводити запис і читання з цьогобуфера. Цей спосіб економний у використанні пам'яті (мало порожньогопростору), зручний менеджеру пам'яті (працює з одним блоком),досить швидкий доступ. Тим більше, що подібний механізм був ранішереалізований моїм колегою під час роботи з таблицею імен на етапі лексичногоаналізу, і він погодився реалізувати ці функції.
По-друге, таблиця діагональних областей, де зберігається детальнаінформація, що дозволяє повністю охарактеризувати діагональну область, асаме: кількість діагональних площин, по кожній діагональноїплощині імена індексів і константи перетину діагоналей із віссю,визначеної за першим індексом. Наприклад, якщо індекси батьківського областізнаходяться в межах 1 (i (10 1 (j (5, а умова має вигляд i 5
1 c1
1 10 ii
Так як виходить схожа з таблицею областей живопис, а саме, записив таблиці діагональних областей можуть мати різну довжину, вирішено буловикористати той же механізм зберігання інформації.
По-третє, таблиця умовних областей, в якій зберігається номерпозитивно-умовної області, негативно-умовної області, батьківськоїобласті, ключ для пошуку умови в таблиці умов. Так як поля даноїтаблиці однорідні, то вона легко зберігається в структурі масиву. В основномудана таблиця була заведена з метою збереження зв'язку позитивно-інегативно-умовних областях, що мають загальну батьківську область. Цезгодом полегшує проведення таких операцій, як перетин надумовними областями.
По-четверте, на основі механізму, що використовувався для зберіганнятаблиці областей, була створена таблиця умов, у якій зберігаютьсялогічні вирази, задані при описі умовних областей.
4.3 Розробка алгоритмів і реалізація функцій розбору описів областей
У мові розрізняється опис області - це іменована умовна,прямокутна або діагональна область, і використання області --синтаксично це ім'я-області або опис області без імені. Областівикористовуються в описах величин, визначених на області, при завданніобласті обчислення в операторах ASSUME, в опису вхідних або вихіднихвеличин, при завданні областей фактичних параметрів у викликах розділів абофункцій, у функціях редукції.
Щоб врахувати ці два випадки при описі області без імені я вирішивзаводити нові імена в таблиці імен і ототожнювати їх з цими областями.
Для цього будується розширення вже існуючої таблиці імен. При розборімною був використовувався метод прямого аналізу. Розбір здійснюєтьсяпослідовним сканування ланцюжка лексем зліва направо. По ходусканування відбувається перевірки як синтаксичних конструкцій, так і низкисемантичних правил, при цьому відбувається поступове накопичення в робочихструктурах інформації про об'єкт, яка у разі успішного закінченнярозбору заноситься до таблиці загального призначення. Розбір опису областіздійснює функція razb_obl (див. додаток 3). Функція, шляхом знаходження
"Унікальних" лексем або їх сполучень, викликає для розбору кожноїрізновиди області свою функцію (наприклад, razb_multobl розбираєопис багатовимірної області). Потім кожна окрема функція розбираєопис своєї області і при успішному закінченні заповнює потрібні таблиці
(областей, діагональних областей і т.д.), а також таблицю імен. У разіневдалого розбору видається повідомлення про помилку.
4.4 Розробка алгоритмів для фукции роботи з областями
Крім завдання обчислюваного простору для величини на області,поняття та опис області використовуються в Нормі в багатьох місцях. Наприклад,в операторах FOR ASSUME або в операторах введення та виведення. Дуже частонеобхідно здійснити над областями перевірку, чи є їх перетинпорожнім безліччю чи ні. Наприклад, при визначенні інформаційнихзалежностей між опреаторамі і визначенням порядку вичіслеій. У даномуприкладі необхідно встановити чи дає перетин необхідної області Sтребі
FOR B ASSUME X = F (Z, Y [i +1, j ]...)
Sтреб
FOR C ASSUME Y = F (P, K [i-1, j ]...)області З порожня множина. Якщо дає, то дані оператори не пов'язані міжсобою, інакше другий оператор необхідно обчислити раніше першим.
Перетин областей я планую проводити таким чином. Для випадкупрямокутних областей необхідно по кожному напрямку порівняти верхні інижні межі індексів. Для діагональних областей крім порівняннядіапазонів індексів необхідно аналогічним чином порівнювати діагональнідіапазони. Якщо ми маємо справу з умовними областями то необхіднорозглядати два випадки. Перший - це коли дві ці області мають спільного
(нехай не найближчого) з батьків. Тоді необхідно знайти першого такогобатька і від нього провести перевірку, які ще предки, позитивно чинегативно-умовні, знаходяться на шляху від цього батька до данихобластям, і якщо є деякі розбіжності, то перетин порожньо, інакше немає. Це можнапроіллюстіровать за допомогою представлення умовних областей у вигляді бінарногодерева, де в один бік йдуть позитивно-умовні області,
| а в іншу негативно-умовні. На малюнку |
| перетин двох темно зафарбованих областей не |
| порожньо, а перетинання темно і світло зафарбованих |
| - Порожньо. Інший випадок виникає, якщо області |
| не мають жодного спільного предка (хоча такий |
| випадок дуже дивний в сенсі логіки програми). |
| Тоді ми можемо перевірити на перетин самих |
| першу предків цих областей (вони є |
| прямокутними). Якщо вони не перетинаються, то і |
| умовні не перетинаються, інакше ми вважаємо, що |
| вони можуть перетнутися. |
Крім перетину областей часто потрібно знайти об'єднання. Цюзавдання аналітичними методами вирішити дуже складно, тому плануєтьсяреалізувати її методом перебору
5. ВИСНОВОК
У результаті проведеної роботи мною були досягнуті наступні целі:
. розроблені сновном структури для зберігання даних, отриманих в результаті розбору описів областей;
. розроблені алгоритми і написані функції розбору описів областей;
. розроблені алгоритми для написання функцій перетину областей
Деякі функції знаходиться на стадії доопрацювання і налагодження. Завершенняроботи над ними планується в наступному семестрі. Завдання на УІР і КПвиконав практично повністю.
Список літератури:
А.Н. Андріанов, К.Н. Ефімкін, І.Б. Задихайло, Н.В. Поддерюгіна "Мова
Норма "
А. Н. Андрианов, К. М. Ефімкін, І. Б. Задихайло" непроцедурного мова Нормаі методи його реалізації "
А. Б. Бугера" Реалізація математичних функцій мови Норма длярозподілених висіслітельних систем "
Ф. Льюїс" Теоретичні основи проектування компіляторів "
* Квант - семантично закінчений фрагмент тексту програми (наприклад,опис області)
