Синтаксический аналіз мови НОРМА. 
Розбір описания

МОСКОВСЬКИЙ ДЕРЖАВНИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ.

(ТЕХНІЧНИЙ УНИВЕРСИТЕТ).

Кафедра 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(і (10 1(j (5, а умова має вигляд і < j то побудова запис у таблицю буде так: j j c2.

1 c1.

1 10 і i.

Оскільки виходить схожа з таблицею областей картина, саме, записи в таблиці діагональних областей може мати різну довжину, було вирішено використовувати хоча б механізм зберігання информации.

По-третє, таблиця умовних областей, у якій зберігається номер положительно-условной області, отрицательно-условной області, батьківської області, ключ на допомогу пошуку умови в таблиці умов. Оскільки поля даної таблиці однорідні, вона легко зберігається у структурі масиву. Здебільшого дана таблиця була заведена із метою збереження зв’язку позитивноі отрицательно-условных областях, що мають спільну батьківську область. Це згодом полегшує проведення таких операцій, як те що над умовними областями.

По-четверте, з урахуванням механізму, який використовувався для зберігання таблиці областей, було створено таблиця умов, у якій зберігаються логічні висловлювання, задані в описах умовних областей.

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 З ASSUME Y=F (P, K[i-1,j]. .) області З порожній безліч. Якщо дає, то дані оператори пов’язані між собою, інакше другий оператор необхідно обчислити раніше первого.

Перетин областей я планую проводити так. Для випадку прямокутних областей необхідно з напряму порівняти верхні і нижні кордону індексів. Для діагональних областей крім порівняння діапазонів індексів необхідно аналогічно порівнювати діагональні діапазони. Якщо ми маємо справу з умовними областями необхідно розглядати два випадку. Перший — це коли ці дві галузі мають загального (нехай не найближчого) батька. Тоді слід знайти першого такого батька від нього перевірити, які ще предки, позитивно чи отрицательно-условные, перебувають у шляху від рівня цього батька до даних областям, і є відмінності, то те що порожньо, інакше немає. Це можна проиллюстировать з допомогою уявлення умовних областей і в вигляді бінарного дерева, де у один бік йдуть положительно-условные области,.

|а до іншої отрицательно-условные. На малюнку | |те що двох темно зафарбованих областей ще не | |порожньо, а те що темно та ясно зафарбованих| |- порожньо. Інший випадок виникає, якщо області | |немає жодного загального предка (хоча такий | |випадок дуже дивний себто логіки програми).| |Тоді ми можемо перевірити перетнутися самих | |перших предків цих галузей (є | |прямокутними). Якщо вони самі не перетинаються, те й | |умовні не перетинаються, інакше ми вважаємо, що | |можуть перетнутися. |.

Крім перетину областей часто потрібно знайти об'єднання. Цю завдання аналітичними методами вирішити дуже складно, тому планується реалізувати її методом перебора.

5.

ЗАКЛЮЧЕНИЕ

.

Через війну зробленого мною досягнуто такі цели:

. розроблено сновные структури для зберігання даних, які є результатом розбору описів областей;

. розроблено алгоритми і написані функції розбору описів областей;

. розроблено алгоритми для написання функцій перетину областей.

Деякі функції перебуває в стадії доопрацювання й налагодження. Завершення роботи з них планується на наступному семестрі. Завдання УИР і КП виконав практично полностью.

О.Н. Андріанов, К. Н. Ефимкин, І.Б. Задыхайло, Н. В. Поддерюгина «Мова Норма «.

О.Н. Андріанов, К. Н. Ефимкин, І.Б. Задыхайло «Непроцедурный мову Норма і його реалізації «.

Г. Б. Бугеря «Реалізація математичних функцій мови Норма для розподілених высислительных систем «.

Ф.Льюис «Теоретичні основи проектування компіляторів» * Квант — семантично кінцевий фрагмент тексту программы (например, опис области).