Размещено на http:www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ

ім. Г.Є. ПУХОВА

ЛЕВИЦЬКИЙ Вячеслав Георгійович

УДК 681.3.06

РОЗРОБКА ЛІНГВІСТИЧНОГО ЗАБЕЗПЕЧЕННЯ

СПЕЦІАЛІЗОВАНОЇ ПРОГРАМНОЇ СИСТЕМИ ЧИСЕЛЬНОГО АНАЛІЗУ

01.05.03 - Математичне та програмне забезпечення

обчислювальних машин і систем

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Київ - 2001



Дисертацією є рукопис.

Робота виконана в Житомирському інженерно-технологічному інституті Міністерства освіти і науки України.

Науковий керівник:

кандидат технічних наук, доцент Колодницький Микола Михайлович, Житомирський інженерно-технологічний інститут Міністерства освіти і науки України, доцент кафедри програмного забезпечення обчислювальної техніки.

Офіційні опоненти:

доктор технічних наук, професор Рогоза Валерій Станіславович, Національний технічний університет “Київський Політехнічний Інститут” Міністерства освіти і науки України, професор кафедри конструювання та виробництва електронно-обчислювальної апаратури;

кандидат фізико-математичних наук, старший науковий співробітник Тульчинський Вадим Григорович, Інститут Кібернетики ім. В.М. Глушкова НАН України, науковий співробітник відділу автоматизації програмування.

Провідна установа:

Інститут проблем математичних машин та систем НАН України, відділ інтелектуальних систем математичного моделювання складних об'єктів та процесів.

Захист відбудеться 14 червня 2001 р. о 14⁰⁰ годині на засіданні спеціалізованої вченої ради Д 26.185.01 в Інституті проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03680, м. Київ - 164, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03680, м. Київ - 164, вул. Генерала Наумова, 15.

Автореферат розісланий 4 травня 2001 р.

Вчений секретар

спеціалізованої вченої ради Д 26.185.01

кандидат технічних наук Е.П. Семагіна

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

На теперішній час розроблено вже досить великий арсенал програмних систем чисельного аналізу математичних задач [12]. Однак, їх функціональні можливості та темпи розвитку не повною мірою задовольняють всезростаючі вимоги, які висуває практика. В зв'язку з цим існує потреба у створенні нових подібних програмних засобів. Розробці такого нового програмного інструменту присвячені роботи [13-17], в яких було розглянуто актуальність створення та вимоги до прикладної програмної системи “DSR Open Lab 1.0”, призначеної для чисельного аналізу математичних задач, і орієнтованої, головним чином, на використання у навчальному процесі.

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

Тому розробка лінгвістичного забезпечення для програмної системи “DSR Open Lab 1.0”, призначеної для чисельного аналізу математичних задач, є безсумнівно актуальною темою та має велике прикладне значення.

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

Для досягнення вказаної мети були поставлені та вирішені наступні основні задачі:

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

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

Визначення спорідненості мов опису математичних структур та модифікація процедури синтаксичного аналізу предметно-орієнтованих мов з врахуванням їх спорідненості.

Створення програмного середовища генерації мовних процесорів для автоматизації розробки лінгвістичного забезпечення чисельного аналізу математичних задач. математичний транслятор лінгвістичний

Об'єктом дослідження є лінгвістичне забезпечення, яке включає в себе як предметно-орієнтовані мови, так і відповідні транслятори.

Предметом дослідження є мови опису математичних структур визначеного вигляду.

Методи дослідження. Дослідження та побудова лінгвістичного забезпечення чисельного аналізу математичних задач виконано на основі запропонованої методики побудови предметно-орієнтованих мов, що базується на розмежуванні функцій опису задачі між програмним графічним інтерфейсом і мовою та використанні графічного введення математичних формул. Для розробки модифікованої процедури синтаксичного аналізу споріднених мов опису використовувався математичний апарат теорії автоматів та теорії формальних мов. Автоматизація побудови лінгвістичного забезпечення проведена на основі концепції використання інструментального засобу компілятора компіляторів.

Наукова новизна одержаних результатів полягає в наступному:

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

розроблено мови опису визначеної множини математичних структур та реалізовано їх компілятори, побудовано математичні моделі мов опису у вигляді контекстно-вільних граматик, математичні моделі скінчених автоматів для лексичного розбору та автоматів з магазинною пам'яттю для синтаксичного розбору;

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

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

створено інструментальний засіб автоматизації розробки лінгвістичного забезпечення чисельного аналізу математичних задач -- програмне середовище генерації мовних процесорів “FancyCC 3.0”.

Достовірність отриманих результатів забезпечується використанням обгрунтованих методик, відповідністю результатів теоретичних розрахунків експериментальним даним, одержаним особисто, та практичним застосуванням в рамках програмної системи чисельного аналізу “DSR Open Lab 1.0” запропонованої методики побудови лінгвістичного забезпечення, розроблених предметно-орієнтованих мов опису математичних структур, відповідних трансляторів та програмних засобів автоматизації побудови лінгвістичного забезпечення.

Практичне значення одержаних результатів:

Розроблене лінгвістичне забезпечення є гнучким і потужним інструментом формулювання задач чисельного аналізу математичних структур та дозволяє реалізувати зручний інтерфейс з користувачем за допомогою предметно-орієнтованих мов в рамках програмної системи “DSR Open Lab 1.0”. Запропонована методика побудови лінгвістичного забезпечення дозволяє максимально спростити структуру текстового опису, звільнивши його від завдання виду аналізу та умов аналізу математичної структури. Це суттєво спрощує вивчення та використання користувачем програмної системи чисельного аналізу математичних задач.

Модифікація процедури синтаксичного аналізу споріднених мов є ефективним засобом технології розробки компіляторів мов, які використовуються в програмних системах чисельного аналізу математичних задач, та інших предметно-орієнтованих мов і мов програмування. Запропонований спосіб побудови трансляторів споріднених мов опису математичних структур за рахунок спільного підходу до аналізу синтаксису цих мов оптимізує як етап розробки підсистеми лінгвістичного забезпечення, так і етап виконання програми: дозволяє збільшити швидкість роботи підсистеми лінгвістичного забезпечення, зменшити сумарний розмір керуючих таблиць синтаксичного аналізу та відповідно скоротити програмний код, що їх обробляє. Даний підхід забезпечує відкритість для подальшого нарощування транслятора споріднених мов та дозволяє легко вносити зміни в існуючі мови з множини мов опису математичних структур.

Розроблене програмне середовище генерації мовних процесорів “FancyCC 3.0” є ефективним інструментальним засобом автоматизації розробки лінгвістичного забезпечення. Дане програмне середовище враховує спорідненість мов опису математичних структур, що дозволяє полегшити реалізацію відповідних трансляторів. Процедура розробки мовних процесорів в розглянутому програмному середовищі є спрощеною, що робить її більш зручною для використання, дозволяє прискорити як процес автоматизованої побудови компіляторів, так і освоєння даного програмного засобу новим користувачем, а також збільшити надійність роботи програмної системи. Використання програмного графічного інтерфейсу користувача для визначення задачі генерації трансляторів та реалізація принципу застосування однорідної предметно-орієнтованої мови визначення формальних граматик без використання фрагментів цільової мови програмування дозволяє полегшити розробку, відлагодження, супроводження та модифікацію проекту лінгвістичного забезпечення.

Особистий внесок здобувача. У публікаціях, написаних у співавторстві, здобувачеві належить: в роботі [1] -- побудова мови опису формальних граматик; в роботі [2] -- ідея використання узагальненої граматики та адаптуючих множин в процедурі організації синтаксичного аналізу споріднених мов; в роботі [10] -- визначення функціональності програмного середовища генерації мовних процесорів; в роботі [11] -- структура мов опису математичних задач; в роботі [12] -- огляд способів організації взаємодії з користувачем в програмних системах, призначених для вирішення математичних задач; в роботах [13-16] -- результати роботи та будова підсистеми лінгвістичного забезпечення; в роботі [17] -- застосування предметно-орієнтованої мови до опису дискретних груп та метод генерації груп за відповідним генетичним кодом.

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися на 3-й Міжнародній науково-практичній конференції “Сучасні технології в аерокосмічному комплексі” (Житомир, Україна, 1997); 21_й Міжнародній конференції ”Інтерфейси інформаційних технологій” (Пула, Хорватія, 1997); 1-й Міжнародній науково-практичній конференції з програмування “УкрПрог'98” (Київ, Україна, 1998); 1-й Міській міжвузівській науково-практичній конференції студентів та молодих вчених (Житомир, Україна, 1998); 4-й Міжнародній науково-практичній конференції “Сучасні технології в аерокосмічному комплексі” (Житомир, Україна, 1999); 4-й Міжнародній конференції “Азіатська конференція технологій в математиці” (Гуанджоу, Китай, 1999); 6-й Всеукраїнській конференції з автоматичного управління "Автоматика-99" (Харків, Україна, 1999); 1-й Національній науково-практичній конференції студентів та аспірантів “Системний аналіз та інформаційні технології” (Київ, Україна, 1999); 2-й Міській міжвузівській науково-практичній конференції студентів та молодих вчених (Житомир, Україна, 1999); 2-й Міжнародній науково-практичній конференції з програмування “УкрПрог'2000” (Київ, Україна, 2000); 5-й Міжнародній конференції “Азіатська конференція технологій в математиці” (Чіанг-Мей, Таїланд, 2000); 4-й Міжнародній конференції “Азіатський симпозіум з комп'ютерів в математиці” (Чіанг-Мей, Таїланд, 2000); 3-й Міській міжвузівській науково-практичній конференції студентів та молодих вчених (Житомир, Україна, 2000); 2-й Національній науково-практичній конференції студентів та аспірантів “Системний аналіз та інформаційні технології” (Київ, Україна, 2000).

Публікації. З теми дисертації надруковано 19 наукових праць, із них 10 - у фахових виданнях, 7 - у матеріалах конференцій, 2 - у тезах конференцій. Основний зміст роботи викладено в публікаціях [2, 4-6, 8-13].

Структура та обсяг роботи. Дисертація включає вступ, чотири спеціальні розділи, висновки, список використаних джерел та додатки, до яких винесені деталі реалізації предметно-орієнтованих мов опису математичних структур програмної системи “DSR Open Lab 1.0”. Матеріал дисертації викладений на 188 сторінках. Робота містить 36 малюнків. Бібліографічний список налічує 280 назв.



ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі сформульовано мету роботи, відображено наукову новизну, практичну цінність та достовірність результатів роботи. Стисло викладено зміст роботи за розділами.

В першому розділі зроблено огляд літературних джерел та матеріалів всесвітньої мережі Internet з теми дисертаційної роботи: розглянуто програмні засоби математичного моделювання та проаналізовано спосіб, в який вони взаємодіють з користувачем; розглянуто методи побудови трансляторів підсистеми лінгвістичного забезпечення та програмні інструменти генерації компіляторів. Встановлено, що існуючі програмні засоби розв'язування математичних задач незадовільно вирішують проблему реалізації інтерфейсу “людина-комп'ютер” в частині лінгвістичного забезпечення, зокрема, пропонують користувачам визначати умову задачі за допомогою мов, надмірно ускладнених з точки зору лексики, синтаксису та семантики. Показано, що використання існуючих середовищ автоматизованої розробки лінгвістичного забезпечення не відповідає вимогам архітектури сучасного програмного засобу математичного моделювання.

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

Основні програмні засоби для рішення математичних задач, реалізують принцип використання предметно-орієнтованих програмних середовищ і мов, схиляючись при цьому до надмірного ускладнення опису математичної задачі практично на всіх етапах: в частині лексики (велика кількість зарезервованих слів, зокрема, імен функцій), синтаксису (громіздкі конструкції, запозичені з універсальних мов програмування) та семантики (складні принципи типізації і т.д.). І хоча бажання мати універсальний засіб визначення проблеми, незмінний для всього циклу вирішення математичної задачі, гнучкий та потужний, є цілком виправданим, якщо згадати широту завдань та функціональність програмних засобів для рішення математичних задач, та все ж застосування предметно-орієнтованих мов, ускладнених до рівня мови програмування загального призначення (MATLAB, Mathematica, Maple V тощо) є прийомом небажаним, а в певних випадках (наприклад, для використання в навчальному процесі) й абсолютно неприпустимим з огляду на специфіку кінцевого користувача, який може, взагалі кажучи, і не мати необхідних навичок програмування.

Тому, побудова предметно-орієнтованих мов опису математичних задач програмної системи “DSR Open Lab 1.0” мала на меті модифікувати існуючі підходи до реалізації інтерфейсу людини та комп'ютера в сучасних прикладних системах чисельного аналізу, забезпечивши більш простий та прийнятний для непідготовленого користувача спосіб комунікації з програмним засобом за рахунок реалізації нової методики організації лінгвістичного забезпечення чисельного аналізу математичних задач -- методики, що базується на 1) нетрадиційному для математичного програмного забезпечення розмежуванні функцій опису задачі між програмним графічним інтерфейсом і мовою та 2) використанні графічного введення математичних формул.

Відмітимо, що “DSR Open Lab 1.0” відноситься до того ж класу програмного забезпечення, що й програми MATLAB, Maple V, Mathematica тощо (це, так зване, mathematical software). Це означає, що з допомогою згаданої програмної системи користувач може розв'язувати широке (але обмежене) коло математичних задач обчислювального характеру, попередньо завдавши тип математичної структури, вид та умови її аналізу, визначивши вигляд математичної структури з допомогою предметно-орієнтованої мови опису та виконавши ряд додаткових дій, які впливають на відображення результатів розрахунків.

Описані в даному розділі мови опису задач чисельного аналізу є результатом поєднання двох способів вирішення проблеми організації інтерфейсу з користувачем -- 1) застосування в програмній системі деякої предметно-орієнтованої мови, як гнучкого інструмента опису задачі, та 2) створення візуальних, графічних інтерфейсів -- на основі використання класифікації (типології) математичних моделей технічних систем. В основу типології математичних моделей, покладено поняття математичних структур, з базового набору яких можуть бути побудовані більш складні моделі. Причому, з кожною математичною структурою в даному випадку пов'язується множина обчислювальних задач, яка визначається змістом математичної структури. (Так, наприклад, для обчислювальних задач математичної структури “Алгебраїчні системи з однією бінарною операцією -- дискретні групи” список обчислювальних задач, власне, видів аналізу, буде вміщувати: операції з елементами групи -- обчислення ланцюжка, побудова групи за генетичним кодом, обчислення потужності групи, знаходження всіх підгруп, розклад групи за підгрупами, знаходження нормальної підгрупи та фактор-групи.)

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

Таким чином, першим етапом розв'язку задачі чисельного аналізу в “DSR Open Lab 1.0” стає визначення за допомогою програмного графічного інтерфейсу типу математичної структури, яку збирається аналізувати користувач, та набору видів аналізу, які допускає обрана математична структура. Відмітимо, що користувач застосовує готове дерево вибору, побудоване на етапі розробки програмного комплексу чисельного аналізу. Це виключає можливість такого роду помилок взаємодії людини та комп'ютера, які трактуються в інших математичних програмах як помилки синтаксису та семантики відповідних предметно-орієнтованих мов.

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

Етапи 4-6 допомагають користувачу за допомогою графічного інтерфейсу вибрати методи розв'язку задачі, сформулювати умови, специфічні для конкретної задачі, та вибрати вид представлення результатів чисельного аналізу. Останнім етапом розв'язку задачі чисельного аналізу є перегляд результатів у вигляді, визначеному на попередніх етапах.

Як видно з наведеного короткого опису роботи користувача в “DSR Open Lab 1.0”, завдяки запропонованому звуженню функціональності лінгвістичного забезпечення формулювання умови задачі чисельного аналізу суттєво спростилось. Це стало можливим завдяки перенесенню структурної складності інтерфейсу з етапу виконання на етап розробки програмної системи чисельного аналізу.

Дійсно, використання для опису задачі чисельного аналізу більш складної універсальної мови (як це і зроблено в існуючих математичних програмах MATLAB, Maple V, Mathematica тощо) спростило б реалізацію графічного інтерфейсу програмної системи, однак примусила б користувача вивчати складну лексику, синтаксис та семантику мови та збільшила б вірогідність помилок. На противагу до такого підходу, кропітка розробка розгалуженого дерева вибору, яке спрямовує роботу користувача за допомогою меню, екранних форм та інших об'єктів графічного інтерфейсу, дозволяє приховати загальну складність задачі опису математичної структури та реалізувати її на рівні програмної архітектури.

Згідно з запропонованим підходом до організації взаємодії людина-комп'ютер в галузі чисельного аналізу математичних задач, предметно-орієнтовані мови опису “DSR Open Lab 1.0” є повністю декларативними та надають виключно засоби визначення певного математичного об'єкту, що, звичайно, суттєво полегшує вивчення та застосування програмної системи. Таким чином, запропонований поділ функцій між мовами опису задач чисельного аналізу та рештою підсистем “DSR Open Lab 1.0”, що реалізують графічний інтерфейс з користувачем, дозволяє реалізувати прості та зрозумілі лексику, синтаксис і семантику мов у формі, звичній для користувача, -- загальноприйнятій математичній нотації.

Крім того, бажання забезпечити зручний інтерфейс з користувачем, не втративши при цьому гнучкості та виразності вхідної мови, змушує ввести такий додатковий етап обробки вхідного опису задачі, який приховував би від користувача різноманітність конструкцій мови, перетворюючи математичний запис задачі до формату предметно-орієнтованих мов опису задач чисельного аналізу. Для цього підсистема лінгвістичного забезпечення “DSR Open Lab 1.0” використовує модуль графічної побудови математичних виразів “DSR Equation Builder”. Внутрішні структури даних “DSR Equation Builder” після конвертації стають вхідними даними для компіляторів предметно-орієнтованих мов опису. Це дозволяє зробити опис математичної структури дворівневим. При цьому опис першого рівня формується користувачем за допомогою підсистеми графічного введення математичних формул і є суттєво наближеним до математичної нотації.

Розроблені предметно-орієнтовані мови програмної системи “DSR Open Lab 1.0” включають засоби опису таких математичних структур: скінчені множини, числові системи, функціональні відношення, дискретні групи, поліноми, векторний простір, системи лінійних алгебраїчних рівнянь, системи нелінійних алгебраїчних рівнянь, звичайні диференціальні рівняння, задачі оптимізації.

В третьому розділі дано визначення спорідненості предметно-орієнтованих мов опису задач чисельного аналізу, яка розуміється в значенні існування деяких спільних лінгвістичних об'єктів (набір символів алфавіту, певні лексеми, правила побудови виразів, структура речень та опису в цілому тощо). Розділ присвячено оптимізації етапу виконання програми та зменшенню витрат на розробку лінгвістичного забезпечення програмної системи за рахунок спільного підходу до аналізу синтаксису текстів мов опису.

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

На множині мов опису задач чисельного аналізу, розглянутій в другому розділі, в кожній мові є деякі спільні об'єкти (набір символів алфавіту, визначені лексеми, правила побудови виразів, структура речень і опису в цілому), але маються й істотні відмінності (як в алфавіті і лексиці, так і в припустимих синтаксичних конструкціях -- правилах розбору).

Кожна мова опису має власну своєрідну структуру, що утрудняє використання для опису різних математичних об'єктів однієї загальної складної мови. Крім того, створення єдиної складної мови, загальної для опису всіх видів математичних структур, навряд чи є доцільним з погляду майбутнього користувача такої мови. Зокрема, з погляду орієнтування прикладної програмної системи на використання в навчальному процесі, де основним користувачем є студент, створення складної мови опису є недоцільним.

В той же час існує подібність (спорідненість) синтаксису і семантики мов програмної системи. Цей факт підтверджується також і тим, що загальноприйнята нотація різних математичних структур часто є суттєво схожою як з точки зору синтаксису запису, так і з точки зору семантики. З огляду на спорідненість розглянутих мов, побудова множини незалежних трансляторів вносить певну надмірність у процедуру розробки та використання лінгвістичного забезпечення програмної системи. Складність предметно-орієнтованих мов, що повинні використовуватися в “DSR Open Lab 1.0”, загострює проблему пристосування теорії побудови компіляторів до конкретного випадку суттєво схожих мов. Якщо створення лінгвістичного забезпечення ще не викликає великих проблем при організації аналізу одного виду математичних моделей, то побудова трансляторів для десяти предметно-орієнтованих мов робить витрати на розробку неприйнятними, якщо врахувати можливість використання більш раціонального підходу до аналізу споріднених мов. Порівняно велика кількість правил підстановки та складна семантика кожної з мов викликає зрозуміле бажання уникнути дублювання процедур лексичного і синтаксичного розбору та генерації коду, врахувавши найкращим чином спорідненість розглянутих мов для досягнення максимальної ефективності при розробці лінгвістичного забезпечення в рамках єдиної програмної системи.

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

Розглянемо формалізовану процедуру побудови узагальненої граматики та адаптуючих множин і модифікації, що потрібно внести до деяких відомих алгоритмів однопрохідного синтаксичного аналізу без повернень та перетворення граматик для їх адаптації до аналізу споріднених мов. Вважаємо, що для вхідних граматик вже були застосовані відомі процедури усунення некорисних символів.

Алгоритм 1. Побудова узагальненої граматики.

Вхід. Граматики G₁ = (N₁, T₁, P₁, S), …, G_n = (N_n, T_n, P_n, S), що визначають мови L₁, …, L_n (тут N_i -- множина нетермінальних слів, T_i -- множина термінальних слів, P_i -- множина правил підстановки, S -- початковий символ).

Вихід. Узагальнена граматика G_c = (N_c, T_c, P_c, S) та адаптуючі множини a₁, …, a_s (s -- потужність множини правил підстановки P_c).

Метод.

Побудуємо Покладемо G_c = (N_c, T_c, P_c, S).

Для визначення адаптуючих множин a_j поставимо спочатку у відповідність елементам множини P_c елементи множини натуральних чисел. Тепер до множини a_j увійдуть натуральні числа -- номери вхідних граматик G₁, …, G_n, до складу множини правил підстановки яких входить j-те правило підстановки з множини P_c. Позначивши правило з номером j з множини P_c як p^j, маємо: a_j = {i | p^j  P_i}. Таким чином, отримаємо s адаптуючих множин (s -- потужність множини правил підстановки P_c) потужності від 1 до n.

Властивості узагальненої граматики, яка будується за алгоритмом 1, та властивості відповідної мови визначають леми 1 і 2 та теорема 1.

Лема 1. Якщо в граматиці G_i існує виведення , то в граматиці G_c також існує виведення.

Лема 2. Якщо в граматиці G_i існує виведення , то в граматиці G_c також існує виведення , яке здійснюється за допомогою правил підстановки, які належать до множини P_i  P_c.

Теорема 1. Якщо ланцюжок належить мові L_i, то він належить також мові L(G_c).

Зворотне до твердження теореми 1 в загальному випадку, звичайно, є невірним -- очевидно, може існувати такий ланцюжок виведень S ^* , в якому використовуються правила підстановки, що відносяться до P_с, але не до P_i. Таким чином, можна стверджувати, що мова L(G_c) вміщує всі ланцюжки, які належать мовам L₁, …, L_n, та множину ланцюжків (можливо, пусту), які не належать жодній з мов L₁, …, L_n.

Наведемо далі алгоритм, що дозволить, використовуючи узагальнену граматику, за відомим номером мови i за допомогою адаптуючих множин перевіряти належність вхідного ланцюжка до мови L_i. Для цього будемо використовувати поняття лівого та правого виведення, позначаючи їх, відповідно, _l та _r.

Алгоритм 2. Виведення ланцюжка в узагальненій граматиці.

Вхід. Узагальнена граматика G_c = (N_c, T_c, P_c, S), адаптуючі множини a₁, a_s, номер мови i, ланцюжок .

Вихід. “ТАК”, якщо ланцюжок належить мові L_i, “НІ” -- інакше.

Метод.

1) Якщо не існує виведення S  (S ), видати вихід “НІ” і зупинитися.

2) Інакше для кожного кроку виведення, що використовує правило підстановки з номером j (p^j) з множини P_c, виконувати таку процедуру:

а) якщо i  a_j, видати вихід “НІ” і зупинитися;

б) якщо був оброблений останній крок виведення виду  _l  ( _r ), видати вихід “ТАК” і зупинитися, інакше перейти до наступного кроку виведення (отримаємо інше значення номера правила підстановки j) і продовжити алгоритм з пункту a).

Доведенню коректності наведеного алгоритму 2 присвячена лема 3 та теорема 2.

Лема 3. Якщо граматика G_c -- однозначна, то граматики G₁, …, G_n також є однозначними.

Теорема 2. Якщо узагальнена граматика G_c є однозначною, то алгоритм 2 видає “ТАК” тоді і тільки тоді, коли   L_i (1 i n).

Для неоднозначної узагальненої граматики твердження щодо коректності алгоритму 2 в загальному випадку невірне.

Алгоритм 2 ілюструє головну ідею адаптації механізму визначення мов за допомогою граматик до випадку споріднених мов. Справді, використовуючи виведення, які продукують алгоритми, що моделюють детерміновані синтаксичні аналізатори (зверху вниз чи знизу вверх), алгоритм 2 дозволяє організувати синтаксичний аналіз текстів довільної мови з визначеної множини споріднених мов за допомогою єдиної узагальненої граматики.

Неважко побачити, що транслятор споріднених мов є відкритим для подальшого нарощування. Для того, щоб організувати аналіз текстів ще одної спорідненої мови, досить сформулювати для неї граматику в термінах правил підстановки узагальненої граматики, додаючи при необхідності нові правила, термінали і нетермінали, та перебудувати за алгоритмом 1 узагальнену граматику. Після цього, змінивши керуючу таблицю синтаксичного аналізу у відповідності з отриманою граматикою, одержимо парсер нової множини споріднених мов. За цією ж схемою можна легко внести зміни в існуючі мови з множини мов підсистеми лінгвістичного забезпечення.

В четвертому розділі розглянуто питання автоматизації розробки трансляторів мов опису задач чисельного аналізу.

Створення сучасних великих програмних систем призводить до того, що використання вже розроблених середовищ генераторів компіляторів не відповідає вимогам архітектури програмного засобу. Тому при розробці лінгвістичного забезпечення для спеціалізованої програмної системи чисельного аналізу “DSR Open Lab 1.0” виникла необхідність створення такого інструмен-тального засобу для автоматизованої побудови трансляторів, що дозволив би задовольнити специфічним вимогам одночасного використання багатьох предметно-орієнтованих мов у рамках одної програмної системи, забезпечив би зручний і нескладний графічний інтерфейс користувача та простоту способу опису предметно-орієнтованої мови користувача.

Для досягнення цієї мети було розроблено програмне середовище генерації мовних процесорів “FancyCC 3.0”, яке призначене для генерації компіляторів різноманітних предметно-орієнтованих мов та мов програмування, в тому числі й мов опису задач чисельного аналізу.

Поставлена перед програмою мета визначає дії, які повинен виконати генератор компіляторів:

1) аналіз визначення мов опису задач чисельного аналізу та формування проміжних структур даних;

2) аналіз проміжних структур даних та приведення їх до вигляду, зручного для застосування методів генерації компілятора;

3) синтез трансляторів заданих мов та формування відповідної документації.

Останній етап роботи інструментального засобу автоматизації розробки лінгвістичного забезпечення “FancyCC 3.0” враховує можливу спорідненість мов, компілятори для яких будуть згенеровані, та в разі необхідності застосовує обробку множини споріднених предметно-орієнтованих мов за допомогою процедури, яка обговорювалась в розділі 3. Така побудова процесу генерації компіляторів враховує можливість оптимізації розробки багатомовних програмних систем, що, як було показано в попередніх розділах даної роботи, має велике прикладне значення у випадку розробки лінгвістичного забезпечення чисельного аналізу. Це, в свою чергу, дозволило ефективно використати даний інструментальний засіб генерації компіляторів також під час розробки підсистеми лінгвістичного забезпечення програмної системи “DSR Open Lab 1.0”.

Викладені вимоги до програмного середовища генерації мовних процесорів “FancyCC 3.0” сформували структуру даного компілятора компіляторів. Його основними рисами є:

використання відомого методу побудови транслятора (надання розробнику універсального, тобто такого, що не залежить від конкретного вигляду мови, аналізатора та генератора керуючих таблиць синтаксичного аналізу) з пристосуванням його до випадку багатомовної системи лінгвістичного забезпечення:

підтримка бібліотеки класів для визначення синтаксичних та семантичних аспектів побудови трансляторів;

підтримка множинного наслідування об'єктів граматик та їх динамічного (під час виконання програми) зв'язування з об'єктами для лексичного та синтаксичного розбору;

об'єкт для синтаксичного розбору має можливість динамічного зв'язування з об'єктами для лексичного розбору;

транслятор споріднених мов є відкритим для подальшого нарощування.

реалізація сучасних ефективних алгоритмів теорії компіляції для перетворення граматик, лексичного і синтаксичного аналізу тощо:

використання формальних методів, які дозволяють адаптувати алгоритми конструювання трансляторів до випадку організації аналізу суттєво схожих мов.

підтримка зручного способу формулювання задачі генерації транслятора:

визначення мови користувача за допомогою синтаксичних діаграм з їх подальшою конвертацією в текстовий формат опису граматики;

формулювання опису формальної граматики в стилі, подібному до розширеної форми Бекуса-Наура;

підтримка подібного синтаксису та стиля визначення опису об'єктів для лексичного та синтаксичного розбору.

надання додаткових можливостей роботи з вхідними та вихідними даними:

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

розширене документування процесу створення транслятора;

можливість експорту вихідних документів у зовнішні формати.

Для того, щоб мати зручний та гнучкий інструмент опису мов, для яких повинні будуватись транслятори, була розроблена внутрішня мова компілятора компіляторів. Вона використовує синтаксично прості конструкції з мінімальним набором метасимволів та дозволяє в стилі розширеної форми Бекуса-Наура формулювати задачі генерації мовного процесору в звичному для даної предметної області вигляді. З метою збільшення зручності використання мови опису формальних граматик для текстового редактора програмної системи генерації мовних процесорів був реалізований синтаксично-залежний процес редагування. Чутливість редактора до синтаксису відображається як виділення різним кольором частин тексту опису мови користувача. Колір певного ланцюжка символів залежить від його класу, який визначається за допомогою детермінованого скінченого автомата K, граф переходів.

Як видно з графа, всі стани детермінованого скінченого автомата є заключними. Саме за останнім станом скінченого автомата визначається клас ланцюжка в синтаксичному підсвічуванні.

Позначення множин символів алфавіту скінченого автомата K розглянуто в табл. 1. Відзначимо, що для покращання продуктивності роботи автомата, його алфавіт співпадає з множиною символів ASCII, що надає можливість використовувати відповідний код символу як один із входів таблиці переходів.

Таблиця 1. Позначення множин символів алфавіту скінченого автомата K

Позначення	Множина символів
\0	`\0'
CR	повернення каретки (`\0A')
LF	переведення рядка (`\0D')
L	великі та малі латинські літери та знак підкреслення (_A-Za-z)
D	арабські цифри (0-9)
META	[ ] ( ) { } * + ~ | = ;
ASCII	множина ASCII без символу `\0' (`\x01' - `\xFF')
ORD	ASCII \ (CR LF L D META {-,>,',/})

Застосування розглянутого програмного середовища генерації мовних процесорів для розробки підсистеми мов опису задач чисельного аналізу програмної системи “DSR Open Lab 1.0” дозволяє стверджувати, що “FancyCC 3.0” є ефективним інструментальним засобом автоматизації розробки лінгвістичного забезпечення чисельного аналізу.



ВИСНОВКИ

1) Встановлено, що існуючі програмні засоби розв'язування математичних задач незадовільно вирішують проблему реалізації інтерфейсу “людина-комп'ютер” в частині лінгвістичного забезпечення, зокрема, пропонують користувачам визначати умову задачі за допомогою мов, надмірно ускладнених з точки зору лексики, синтаксису та семантики.

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

3) Реалізовано розмежування функцій опису задачі між програмним графічним інтерфейсом користувача та підсистемою лінгвістичного забезпечення на основі використання типології математичних моделей технічних систем. При цьому з предметно-орієнтованих мов вилучається функціональність визначення виду обчислювальної задачі:

а) завдання виду та умов аналізу математичної структури відбувається за допомогою графічного інтерфейсу програмної системи;

б) предметно-орієнтовані мови опису математичних структур є повністю декларативними та надають виключно засоби завдання математичного об'єкту;

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

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

5) Розроблено предметно-орієнтовані мови програмної системи “DSR Open Lab 1.0”, які включають засоби опису визначеного ряду математичних структур (скінчених множин, числових систем, функціональних відношень, дискретних групи, поліномів, векторного простору, систем лінійних алгебраїчних рівнянь, систем нелінійних алгебраїчних рівнянь, звичайних диференціальних рівнянь, задач оптимізації) та забезпечують простий та гнучкий інтерфейс програмної системи з користувачем.

6) Розвинуто принцип використання одного з двох існуючих варіантів розробки підсистеми лінгвістичного забезпечення програмної системи чисельного аналізу математичних задач: а) застосування єдиної великої універсальної мови опису та одного транслятора чи б) застосування декількох мов опису, краще пристосованих до завдання конкретної математичної структури, та множини незалежних трансляторів. Його перетворено на принцип, в основі якого лежить використання декількох спеціалізованих споріднених мов опису та єдиного транслятора, який здатний під час виконання програми пристосовуватися до розбору конкретної поточної мови.

7) Виявлено спорідненість мов опису математичних структур, тобто існування в них певної кількості спільних лінгвістичних об'єктів (символи алфавіту, лексеми, правила побудови виразів, структура речень та опису в цілому).

8) Розроблено модифіковану процедуру синтаксичного аналізу споріднених мов опису математичних структур. Доведена: а) коректність запропонованого підходу; б) перевага його над існуючим підходом на етапі розробки та на етапі виконання підсистеми лінгвістичного забезпечення; в) відкритість для подальшого нарощування модифікованого транслятора споріднених мов.

9) Показано, що використання існуючих середовищ автоматизованої розробки лінгвістичного забезпечення не відповідає вимогам архітектури сучасного програмного засобу чисельного аналізу математичних задач.

10) Розроблено ефективний інструментальний засіб автоматизації розробки лінгвістичного забезпечення чисельного аналізу математичних задач -- компілятор компіляторів “FancyCC 3.0”, який реалізує принципи:

а) спрощеної процедури розробки мовних процесорів з використанням графічного інтерфейсу користувача;

б) використання предметно-орієнтованої мови визначення формальних граматик, з якої вилучено фрагменти цільової мови програмування розробника трансляторів;

в) оптимізації одночасного використання множини споріднених мов опису математичних структур за рахунок модифікованої процедури синтаксичного аналізу.



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗДОБУВАЧА ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Колодницький М.М., Левицький В.Г., Рожик О.А. Автоматизація побу-дови компілятора мови опису математичних моделей динамічних систем. // Вісник ЖІТІ, 1996. - № 4. - С. 138-152.

Колодницкий Н.М., Левицкий В.Г. Применение формализма порождающих грамматик к анализу родственных языков // Кибернетика и системный анализ, 2001. - № 1. - С. 151-162.

Левицький В.Г. Базові класи “Стек”, “Хеш-таблиця” та ”Скінченний автомат” для програмного комплексу “Dsr Open Lab 1.0” // Вісник ЖІТІ, 1998 - № 8. - С. 277-282.

Левицький В.Г. Одна реалізація синтаксичного аналізу текстів споріднених мов за допомогою модифікованого алгоритму SLR(1)-розбору // Вісник ЖІТІ, 1999. - № 9. - С. 225-230.

Левицький В.Г. Реалізація системи описів та типізації в мовах визначення математичних моделей програмного комплексу “Dsr Open Lab 1.0” // Вісник ЖІТІ, 1999. - № 10. - С. 160-165.

Левицький В.Г. Мова визначення вхідних даних програмного середовища генерації мовних процесорів “FANCYCC 3.0” // Вісник ЖІТІ, 2000. - № 12 - С. 226-233.

Левицький В.Г. Спосіб автоматичної генерації детермінованих скінчених автоматів за текстовим описом без попередньої обробки регулярних виразів // Вісник ЖІТІ, 2000. - № 13. - С. 192-196.

Левицький В.Г. Опис мови користувача в програмному середовищi генерацiї мовних процесорiв // Вісник ЖІТІ, 2000. - № 14. - С. 190-197.

Левицький В.Г. Розробка мов опису задач математичного моделювання в програмному комплексі “Dsr Open Lab 1.0” // Вісник ЖІТІ, 2000. - № 15. - С. 195-202.

Колодницький М.М., Левицький В.Г. Сучасні інструментальні засоби автоматизованої побудови мовних процесорів // Проблемы программирования, спец. выпуск. - №1-2. - Материалы 2-й международной научн.-практ. конф. по программированию “УкрПрог'2000”, 23_26 травня 2000 р. - Київ, 2000. - С. 345 - 350.

Колодницький М.М., Левицький В.Г. Адаптивна організація лінгвістичного забезпечення програмного комплексу “DSR Open Lab 1.0” // Праці 1-ї міжн. наук.-практ. конф. з програмування “УкрПрог'98”, 2-4 вересня 1998 р. - Київ, 1998. - С. 145-155.

Колодницкий Н.М., Левицкий В.Г. Обзор основных программных средств для моделирования математических задач // САПР и графика, 1999. - № 10 - С. 56-65.

Kolodnytsky M., Kovalchuk A., Kuryata S., Levitsky V. The Mathematical Software Implementation for Computational Algebra and Number Theory // Computer Mathematics. Proceedings of the 4th Asian Symposium. Chiang Mai, Thailand, December 17-21, 2000. / Lecture Notes Series on Computing. Volume 8. - World Scientific, Singapore. - P. 291-294.

Kolodnytsky M., Kovalchuk A., Kuryata S., Levitsky V. "A Theory of Approximation of Functions" Courseware // ATCM 2000. Proceedings of the 5th Asian Technology Conference in Mathematics, December 17-21, 2000. Chiang Mai, Thailand. / Published by ATCM, Inc., USA. - P. 86-95.

Kolodnytsky M., Ivanitsky I., Kovalchuk A., Kuryata S., Levitsky V. "DSR Open Lab 1.0" -- software system for simulation // Proceedings of the 21st International Conference on Information Technology Interfaces, Pula, Chroatia, 1999. - P. 31.

Колодницький М.М., Рожик О.А., Левицький В.Г., Шкаленко С.П., Гладишев А.В. Програмний комплекс для моделювання динамічних систем “DSR LAB. 1.0” // Сучасні технології в аерокосмічному комплексі. Матеріали III Міжнародної наук.-практ. конференції, 9-11 вересня 1997 року. - Житомир: ЖIТІ, 1997.- С. 97-99.

Колодницький М.М., Левицький В.Г. Комп'ютерний лабораторний практикум з обчислювальних задач теорії дискретних груп // Сучасні технології в аерокосмічному комплексі. Матеріали IV Міжнародної наук.-практ. конференції, 7-9 вересня 1999 року. - Житомир: ЖIТІ, 1999. - С. 45-48.

Левицький В.Г. Автоматизація процесу конструювання трансляторів за допомогою інструментального засобу “FANCYCC 2.0” // Праці 2-ї національної науково-практичної конференції студентів та аспірантів “Системний аналіз та інформаційні технології”, 28-30 червня 2000 р. - Київ, 2000. - С. 164-167.

Левицький В.Г. Застосування формалізму породжуючих граматик до аналізу споріднених мов математичного моделювання складних систем // Праці 1-ї національної науково-практичної конференції студентів та аспірантів “Системний аналіз та інформаційні технології”, 28-29 червня 1999 р. - Київ, 1999. - С. 32-33.



АНОТАЦІЇ

Левицький В.Г. Розробка лінгвістичного забезпечення спеціалізованої програмної системи чисельного аналізу. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 -- “Математичне та програмне забезпечення обчислювальних машин і систем”. -- Інститут проблем моделювання в енергетиці НАН України, Київ, 2001.

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

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

Розроблена модифікована процедура синтаксичного аналізу мов опису задач чисельного аналізу та показана її перевага над існуючим підходом на етапі розробки та виконання програми.