The grammar of Petri-object model visual programming language

Petri-object models solve the problem of replicating fragments of Petri nets with given parameters and constructing a model from a large number of elements. The developed visual programming language of Petri-object models gives a possibility to reduce the number of errors during a model construction...

Full description

Saved in:

Bibliographic Details
Date:	2022
Main Authors:	Dyfuchyn, А.J., Stetsenko, I.V., Zharikov, E.V.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2022
Subjects:	formal grammar visual programming stochastic Petri nets simulation UDC 004.43::004.94
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/477
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-477
record_format	ojs
resource_txt_mv	ppisoftskievua/c4/13f7063d8cbc260c4622b45ee63845c4.pdf
spelling	pp_isofts_kiev_ua-article-4772022-06-22T17:42:21Z The grammar of Petri-object model visual programming language Граматика мови візуального програмування Петрі-об’єктних моделей Dyfuchyn, А.J. Stetsenko, I.V. Zharikov, E.V. formal grammar; visual programming; stochastic Petri nets; simulation UDC 004.43::004.94 формальна граматика; візуальне програмування; стохастична мережа Петрі; імітаційне моделювання УДК 004.43::004.94 Petri-object models solve the problem of replicating fragments of Petri nets with given parameters and constructing a model from a large number of elements. The developed visual programming language of Petri-object models gives a possibility to reduce the number of errors during a model construction by automating the coding links between elements and graphical representation of a model. In addition to replicating Petri objects, the visual language implements replication of links between Petri objects. Formalization of the visual programming language grammar is presented in the form of production rules. A conclusion about grammar properties has been drawn.Prombles in programming 2021; 1: 82-94 Імітаційне моделювання широко використовується у дослідженні властивостей систем, пошуку оптимальних умов, прогнозування. Мережі Петрі є універсальним інструментом для формалізації дискретно-подійних систем. Недоліком мереж Петрі є зростання кількості візуальних елементів під час проєктування складних систем. Через нагромадження зв’язків та елементів перевага візуального сприйняття моделі зникає, модифікація параметрів моделі потребує значної кількості рутинних дій. Петрі-об’єктні моделі вирішують проблему тиражування фрагментів мереж Петрі з заданими параметрами та конструювання моделі системи з великої кількості елементів. Однак Петрі-об’єктна технологія не позбавляє необхідності зв’язування елементів моделі. Розроблена мова візуального програмування Петрі-об’єктних моделей дає можливість зменшити кількість помилок при конструюванні моделі за рахунок автоматизації кодування зв’язків між елементами моделі та графічного представлення моделі. Окрім тиражування Петрі-об’єктів, мова реалізує тиражування зв’язків між Петрі-об’єктами. За рахунок такого тиражування досягається також компактність візуального представлення для складних моделей. Реалізація введених понять у мові візуального програмування дає можливість швидко створювати та групувати елементи моделі. Алфавіт мови складається із графічних елементів, передбачених для конструювання Петрі-об’єктної моделі. Синтаксис мови визначений правилами конструювання виразів із послідовності символів алфавіту мови. Семантика мови програмування визначається правилами перетворення мовних виразів в обчислення. Формалізація граматики мови візуального програмування представлена у вигляді правил виведення та зроблені висновки про її властивості.Prombles in programming 2021; 4: 82-94 Інститут програмних систем НАН України 2022-02-07 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/477 10.15407/pp2021.04.082 PROBLEMS IN PROGRAMMING; No 4 (2021); 82-94 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2021); 82-94 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2021); 82-94 1727-4907 10.15407/pp2021.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/477/481 Copyright (c) 2022 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2022-06-22T17:42:21Z
collection	OJS
language	Ukrainian
topic	formal grammar visual programming stochastic Petri nets simulation UDC 004.43::004.94
spellingShingle	formal grammar visual programming stochastic Petri nets simulation UDC 004.43::004.94 Dyfuchyn, А.J. Stetsenko, I.V. Zharikov, E.V. The grammar of Petri-object model visual programming language
topic_facet	formal grammar visual programming stochastic Petri nets simulation UDC 004.43::004.94 формальна граматика візуальне програмування стохастична мережа Петрі імітаційне моделювання УДК 004.43::004.94
format	Article
author	Dyfuchyn, А.J. Stetsenko, I.V. Zharikov, E.V.
author_facet	Dyfuchyn, А.J. Stetsenko, I.V. Zharikov, E.V.
author_sort	Dyfuchyn, А.J.
title	The grammar of Petri-object model visual programming language
title_short	The grammar of Petri-object model visual programming language
title_full	The grammar of Petri-object model visual programming language
title_fullStr	The grammar of Petri-object model visual programming language
title_full_unstemmed	The grammar of Petri-object model visual programming language
title_sort	grammar of petri-object model visual programming language
title_alt	Граматика мови візуального програмування Петрі-об’єктних моделей
description	Petri-object models solve the problem of replicating fragments of Petri nets with given parameters and constructing a model from a large number of elements. The developed visual programming language of Petri-object models gives a possibility to reduce the number of errors during a model construction by automating the coding links between elements and graphical representation of a model. In addition to replicating Petri objects, the visual language implements replication of links between Petri objects. Formalization of the visual programming language grammar is presented in the form of production rules. A conclusion about grammar properties has been drawn.Prombles in programming 2021; 1: 82-94
publisher	Інститут програмних систем НАН України
publishDate	2022
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/477
work_keys_str_mv	AT dyfuchynaj thegrammarofpetriobjectmodelvisualprogramminglanguage AT stetsenkoiv thegrammarofpetriobjectmodelvisualprogramminglanguage AT zharikovev thegrammarofpetriobjectmodelvisualprogramminglanguage AT dyfuchynaj gramatikamovivízualʹnogoprogramuvannâpetríobêktnihmodelej AT stetsenkoiv gramatikamovivízualʹnogoprogramuvannâpetríobêktnihmodelej AT zharikovev gramatikamovivízualʹnogoprogramuvannâpetríobêktnihmodelej AT dyfuchynaj grammarofpetriobjectmodelvisualprogramminglanguage AT stetsenkoiv grammarofpetriobjectmodelvisualprogramminglanguage AT zharikovev grammarofpetriobjectmodelvisualprogramminglanguage
first_indexed	2025-07-17T09:40:43Z
last_indexed	2025-07-17T09:40:43Z
_version_	1838409088177799168
fulltext	82 Інструментальні засоби і середовища програмування Вступ Програмне забезпечення імітацій- ного моделювання – це широкий клас про- грамних продуктів, призначених для по- будови моделей, які відтворюють функці- онування систем. Моделі використовують для дослідження властивостей систем, пошуку оптимальних умов, прогнозуван- ня. Моделі, побудовані з використанням мереж Петрі, рекомендовані для проєкту- вання та аналізу програмного забезпечен- ня стандартом ISO/IEC 15909-1:2004 [1]. Перевагами такого використання є візуалі- зація, математично формалізований опис, покрокове відтворення обчислювального процесу. Застосування мереж Петрі для розробки алгоритмів і програмного за- безпечення з часом може втілитись у па- радгму програмування на мережах Петрі [2]. Отже, мережі Петрі як засіб побудови моделей надзвичайно важливі для розви- тку програмної інженерії. Недолік, з яким доводиться стикатись у розробці моделей мережами Петрі - це ускладнення сприй- няття та побудови моделі при зростан- ні складності системи, що моделюється (складність може бути оцінена кількістю елементарних подій). Через нагромаджен- ня зв’язків та елементів перевага візуаль- ного сприйняття моделі зникає, модифі- кація параметрів моделі потребує значної кількості рутинних дій. Тому розвиток ме- тодів, що спрощують і прискорюють роз- робку моделей на основі мереж Петрі є актуальним науковим завданням. Петрі-об’єктні моделі вирішують проблему тиражування фрагментів мереж Петрі з заданими параметрами та констру- ювання моделі системи з великої кількос- ті елементів. Якщо система складається із сотень однотипних вузлів, опис кожного з яких потребує 10 переходів, 20 позицій та 40 дуг, то в термінах звичайної мережі Петрі довелось би створювати 1000 пере- ходів, 2000 позицій, 4000 дуг та щонаймен- ше 100 дуг для зв’язування фрагментів між собою. В термінах Петрі-об’єктної моделі один раз розроблена мережа Петрі, що опи- сує функціонування одного вузла системи, використовується для створення 100 вузлів (із різними значеннями параметрів). Отже, розробка моделі значно спрощується і при- скорюється. Скорочується також обсяг гра- фічної інформації, яку потрібно зберігати для відтворення моделі. Широко відомий засіб для моделювання мережами Петрі СPNTools дає можливість використовува- ти фрагменти мережі Петрі повторно, про- те налагоджувати і вбудовувати фрагмент у модель доведеться для кожного фрагменту окремо. Звісно, такий спосіб спрощує ство- рення нового фрагменту мережі Петрі на основі вже існуючого, але не спрощує ство- рення множинних наборів типових фраг- ментів. По суті, уможливлюється копіюван- ня фрагментів і створення на їх основі но- вих, але не тиражування за заданим шабло- ном з заданими параметрами. Зберігатись у СPNTools будуть усі скопійовані фрагменти УДК 004.43::004.94 https://doi.org/10.15407pp2021.04.082 А.Ю. Дифучин, І.В. Стеценко, Е.В. Жаріков ГРАМАТИКА МОВИ ВІЗУАЛЬНОГО ПРОГРАМУВАННЯ ПЕТРІ-ОБ’ЄКТНИХ МОДЕЛЕЙ Петрі-об’єктні моделі вирішують проблему тиражування фрагментів мереж Петрі з заданими параме- трами та конструювання моделі системи з великої кількості елементів. Розроблена мова візуального програмування Петрі-об’єктних моделей дає можливість зменшити кількість помилок при конструю- ванні моделі за рахунок автоматизації кодування зв’язків між елементами моделі та графічного пред- ставлення моделі. Окрім тиражування Петрі-об’єктів, мова реалізує тиражування зв’язків між Петрі- об’єктами. Формалізація граматики мови візуального програмування представлена у вигляді правил виведення та зроблені висновки щодо її властивостей. Ключові слова: формальна граматика, візуальне програмування, стохастична мережа Петрі, імітаційне моделювання. © А.Ю. Дифучин, І.В. Стеценко, Е.В. Жаріков, 2021 ISSN 1727-4907. Проблеми програмування. 2021. № 4 83 Інструментальні засоби і середовища програмування як наново створені, отже, на відміну від Петрі-об’єктного підходу, скорочення обся- гів пам’яті на збереження фрагментів моде- лі не відбувається. Петрі-об’єктні моделі дають можли- вість створювати моделі засобами мереж Петрі там, де раніше вони призводили до надмірного ускладнення: моделювання роз- повсюдження комп’ютерних вірусів [3], передача повідомлень у телекомунікацій- них системах [4], моделювання алгоритмів паралельних обчислень [5]. Застосування Петрі-об’єктного підходу для моделюван- ня систем різного призначення показало ефективність цієї технології конструювання моделей, що поєднує переваги об’єктно- орієнтованого підходу та стохастичних мереж Петрі. Проте кодування зв’язків між елементами мережі Петрі є процесом, схильним до помилок. Відшукання поми- лок у структурі моделі безпосередньо в коді потребує концентрації уваги. Якщо модель містить опис двох десятків подій, із цим ще можна впоратись. При більшій кількос- ті подій процес розробки моделі настільки трудомісткий, що результати моделювання можуть не виправдати зусиль, витрачених на створення моделі. Рішення цієї проблеми можна шу- кати у двох напрямках: 1) автоматизація, інтелектуалізація чи інші способи запобі- гання та виявлення помилок безпосередньо в коді, 2) візуалізація зв’язків та моделі в цілому для поліпшення сприйняття моделі, що будується. Підходи, які використовують виключно візуальне представлення моделі, примушують програміста відкривати та мо- дифіковувати модель навіть зі зміною її па- раметрів. А якщо потрібна зміна водночас в кількох однотипних елементах, то доведеть- ся повторювати рутинну дію. Такі дії швид- ше виконати безпосередньо в коді (одночас- но потрібно забезпечити, щоб при відкритті моделі такі зміни потрапили у візуальне її представлення). Перевірити правильність зв’язків чи стану моделі в початковий мо- мент часу з використанням інтелектуальних підходів не є можливим, оскільки можливі (допустимі) послідовності подій, які відпо- відають задуму моделі, є надзвичайно ве- ликою множиною навіть для відносно про- стих моделей. Ідеальним вбачається рішення, коли програміст може застосовувати візуальне представлення і, водночас, використовува- ти кодоване представлення моделі. Проте перетворення візуального представлення моделі у кодоване відбувається, як правило, з втратою даних про розміщення графічних елементів. Тому перетворення з кодованого представлення моделі у візуальне її пред- ставлення потребує інтелектуальної оброб- ки інформації про взаємозв’язки елементів. Ускладнює таке перетворення той факт, що не існує однозначної відповідності між ко- дованим представленням та візуальним представленням моделі, оскільки одній мо- делі може відповідати кілька варіантів візу- ального представлення з різним розміщен- ням графічних об’єктів. Конфлікт між графічним представ- ленням і кодованим представленням моде- лі зникає, якщо припустити, що візуальне представлення є водночас кодованим пред- ставленням моделі. Візуальні мови програ- мування використовують графічні об’єкти як алфавіт мови. Отже структури, складені з таких об’єктів є фактично кодом для пред- ставлення моделі. Метою даного наукового досліджен- ня є зменшення складності процесу кон- струювання моделі дискретно-подійної системи за рахунок використання мови ві- зуального програмування Петрі-об’єктної моделі. 1. Формальні мови та засоби імітаційного моделювання дискретно-подійних систем Із появою формальних граматик з’явились машино-незалежні мови програ- мування. Першою мовою програмування, побудованою на основі формальної гра- матики, стала мова ALGOL [7]. Мова імі- таційного моделювання Simula, побудова- на на основі мови ALGOL, була задумана розробниками спочатку виключно як мова для цілей імітаційного моделювання дис- кретно-подійних систем, а стала першою об’єктно-орієнтованою мовою [6]. Її версія Simula 67 була написана вже як універсаль- на об’єктно-орієнтована мова програмуван- ня. Мовою Simula було написано провідне у свій час програмне забезпечення Arena. Ви- 84 Інструментальні засоби і середовища програмування користання блочних діаграм для побудови моделей і надзвичайно зручна розбудова іє- рархічних моделей – основні переваги цьо- го програмного забезпечення. Найбільш по- пулярне в наші дні програмне забезпечення з імітаційного моделювання Simio по суті є продовженням концепції Arena з розвину- тішиими засобами анімації, зокрема 3D, та можливостями завдання розкладів [8]. Вказані програмні засоби та багато інших (AnyLogic, VisualSim, Simul8) ґрунту- ються на описі дискретно-подійних систем у термінах блочних діаграм, що описують процес обробки об’єктів. Складні моделі зі специфічною взаємодією елементів важко вкласти у логіку спрацьовування достатньо обмеженого набору блоків, тому кількість блоків у бібліотеках постійно зростає, що негативно впливає на швидкість вивчення програмного забезпечення. Окрім того, ло- гіка блочних діаграм завжди спирається на опис процесу обробки об’єктів, водночас управління ресурсами для обробки обмеже- но тільки їх кількістю, місткістю та розкла- дом. Деякі з існуючих програмних продуктів (Simio, Simul8) визнали обмеженість блоч- ної побудови моделей і дають можливість розробникам створювати власні фрагменти коду і вбудовувати їх у моделі. Наприклад, Simio пропонує додавати написані на .NET фрагменти коду для передачі даних, опису специфічних алгоритмів вибору об’єктів з черг, опису серії експериментів [9]. Simula8 дає можливість додаткового опису функціо- нальності блоків мовою Visual Logic[10]. Іншим підходом до побудови симуля- ції є розробка формалізації у вигляді мере- жі Петрі і запуск універсального алгоритму імітації для побудованої мережі. Програм- не забезпечення CPNTools [11] використо- вує формалізацію опису моделі у вигляді ієрархічних розфарбованих мереж Петрі та функціональну мову CPN ML для опи- су даних, змінних та функцій. Мова CPN ML є розширенням мови функціонального програмування Standard ML. Використання функціональної мови програмування дає можливість CPNTools досягти необхідної гнучкості в побудові моделей, проте значно ускладнює сприйняття моделі з графічного представлення, оскільки, окрім графічних об’єктів та їхніх параметрів, опис моделі містить вирази-функції. Якщо CPN ґрун- тується на математичному формалізмі роз- фарбованих мереж Петрі, то при додаванні до опису моделі фрагментів коду функціо- нальною мовою математичний формалізм руйнується [12]. Отже, використання програмних за- собів імітаційного моделювання свідчить про переваги використання графічного представлення моделі, такі як наочність представлення, швидкість розробки, змен- шення кількості помилок у відтворенні структури. Водночас, забезпечити необхід- ну гнучкість розробки моделей не вдається без надання розробнику доступу до про- грамного коду моделі та/або надання до- зволу вбудовувати фрагменти програмного коду у код моделі. 2. Поняття мови візуального програмування Терміни «візуальне моделювання» та «візуальне програмування» суттєво від- різняються. Візуальне моделювання - це застосування графічних об’єктів для ство- рення моделей. У загальному випадку візу- альні моделі не призначені для обчислень. Наприклад, моделі UML використовують для опису програмного забезпечення, що проєктується. Візуальне програмування – це застосування графічних об’єктів для розробки програмного коду, який реалізує певний алгоритм обчислень. Відповідно, іс- нує суттєва різниця між мовою візуального моделювання та мовою візуального програ- мування. Мова візуального моделювання – це набір графічних об’єктів для представ- лення систем, об’єктів або понять, що про- єктуються або існують. Мова візуального програмування – це набір взаємопов’язаних графічних об’єктів (разом з чисельними параметрами), який однозначно може бути трансформований у програмний код. На відміну від природних мов, мови програмування є формальними, тобто поро- джуються формальними граматиками. Опис будь-якої формальної граматики складаєть- ся з алфавіту термінальних символів, алфа- віту нетермінальних символів, початкового символу граматики та правил виведення, що використовують для розпіз- навання на- борів символів. Алфавіти термінальних та 85 Інструментальні засоби і середовища програмування нетермінальних символів разом утворюють алфавіт мови. Граматика мови програму- вання породжує множини слів (виведені з термінальних символів за правилами ви- ведення), що можуть бути інтерпретовані (перетворені) в модель обчислень. Прикла- ди розробки формальних граматик, що орі- єнтовані на використання упорядкованих наборів символів, викладені у [13]. Мате- матична теорія формальних граматик ви- кладена у [14]. Формальне представлення граматики мови важливе для гарантування однозначності інтерпретації мовного вира- зу та однозначного перетворення його у ал- горитм (перелік інструкцій для обчислень), що запускається на виконання. Окрім алфавіту, неодмінними озна- ками формальної мови є синтаксис мови та її семантика. Синтаксис визначає дозво- лені конструкції мови, семантика - зміст цих конструкцій. Синтаксис визначає набір правил, за якими складаються мовні кон- струкції. Розбір мовного виразу, складеного за синтаксичними правилами, виконується компілятором мови у відповідності до пра- вил виведення (продукцій), що задані гра- матикою мови. Семантика – це зв’язок між синтаксисом мови та моделлю обчислення. Формальна семантика задається математич- ною моделлю, що описує обчислення у від- повідності до виразу, заданого мовою. Син- таксичні помилки виявляються автоматизо- вано під час компіляції програмного коду, а семантичні – під час виконання програми. Алфавіт мови візуального програ- мування – це набір графічних елементів, що виконують роль символів. У текстовій мові програмування слово (лексема) – це послідовність символів, утворене за прави- лами, що визначені синтаксисом мови. Роз- ташування символів у послідовності зліва направо означає фактично їх з’єднання, і це з’єднання інтерпретується граматикою (при розборі виразу). У візуальній мові, що використовує графічне представлен- ня для опису мовного виразу, на розташу- вання елементів у графічному просторі не накладається ніяких обмежень. Тобто по- слідовності символів у тому розумінні, як вони присутні у традиційних мовах програ- мування, відсутні. Натомість у графічному представленні встановлюються зв’язки між елементами. Наприклад, якщо кінець дуги співпадає з місцем розташування вершини графу, то елемент дуга поєднаний з елемен- том вершини. Якщо такі зв’язки можуть утворювати фрагменти, які однозначно ін- терпретуються, як лексеми мови, то графіч- не представлення може використовуватись для візуального представлення виразів про- грамного коду. У разі текстової мови програмуван- ня текст перетворюється в алгоритм ви- конання обчислень за правилами, визна- ченими семантикою мови. У мові візуаль- ного програмування зображення, складене з взаємопов’язаних графічних елементів, трансформується у змістові конструкції, що запускаються на обчислення. Опис графічного елементу може супроводжува- тись набором чисельних параметрів, що впливають на обчислення. Отже, виразом мови візуального програмування є набір взаємопов’язаних графічних об’єктів, що може бути запущений на обчислення. Граматика текстової мови породжує послідовності символів термінального ал- фавіту, виведених з початкового символу. Граматика мови візуального програмуван- ня має породжувати графічні зображення, утворені з графічних елементів, що склада- ють алфавіт термінальних символів мови. Далі на прикладі мови візуального програ- мування Петрі-об’єктних моделей, буде по- казано, що мова візуального програмування може бути визначена формальною грамати- кою так само, як і текстова мова програму- вання, за умови, що визначені зв’язки між графічними елементами. 2. Поняття Петрі-об’єктної моделі Петрі-об’єктний підхід до розробки імітаційних моделей дискретно-подійних систем комбінує переваги використання стохастичних мереж Петрі та об’єктно- орієнтованої технології для опису моделей. Стохастична мережа Петрі з багатоканаль- ними та конфліктними переходами визна- чена такими множинами елементів: позиції, переходи, дуги. Для зручності обробки гра- фічного представлення будемо розрізняти вхідні та вихідні дуги переходу. Запуск пе- реходу у мережах Петрі з часовими затрим- ками здійснюється у два кроки: вхід марке- 86 Інструментальні засоби і середовища програмування рів в перехід та вихід маркерів з переходу (після того, як сплинула часова затримка). Параметри, які визначені для елементів, представлені у таблиці 1. Петрі-об’єкт за визначенням, вве- деним у [15], є об’єктом суперкласу, який містить методи для відтворення динаміки об’єкта у відповідності до мережі Петрі, що зберігається у спеціально призначеному для цього полі. Створюючи об’єкт конструктор суперкласу використовує мережу Петрі та, можливо, набір параметрів, тому об’єкт можна представити виразом: , де o - Петрі-об’єкт, net - мережа Пе- трі, list - список параметрів. Петрі-об’єктна модель створюєть- ся з множини Петрі-об’єктів, динаміка яких взаємопов’язана через спільні по- зиції. Поєднання Петрі-об’єктів через спільні позиції гарантує, що динаміка моделі визначається мережею Петрі, яка є об’єднанням мереж Петрі-об’єктів [15]. Програмно спільні позиції реалізуються через присвоєння адрес пам’яті відповід- них об’єктів-позицій, що можна предста- вити наступним виразом: , де ou, ov – Петрі-об’єкти, які з’єднуються, o.net – мережа Петрі-об’єкта o, o.net.p – позиція мережі Петрі-об’єкта o. Усі пари спільних позицій двох Петрі- об’єктів, що утворюють з’єднання між ними, будемо називати конектором: . Модель утворюється з Петрі-об’єктів операцією агрегування (в термінах об’єктно- орієнтованої технології), тому модель мож- на представити наступним виразом: , Таблиця 1. Параметри елементів стохастичної мережі Петрі з багатоканальними та кон- фліктними переходами Назва елементу Параметр Тип значення Зміст параметру Позиція Кількість маркерів у позиції Ціле невід’ємне число Символізує виконання умови для запуску переходу. При достатній кількості маркерів у вхідних позиціях переходу, виконується умова входу маркерів в перехід. Перехід Часова затримка Дійсне невід’ємне число Затримка між входом та виходом маркерів з переходу, що реалізується в алгоритмі імітації очікуванням просування часу до відповідного значення модельного часу. Затримка відтворює виконання певних дій в реальній системі. Пріоритет Ціле число При вирішенні конфлікту переходи з найбільшим пріоритетом з рівною ймовірністю можуть здійснити свій запуск. Конфлікт переходів виникає, коли одночасно для більш, ніж одного переходу виконана умова входу маркерів в перехід. Вхідна дуга Кількість зв’язків Натуральне число Визначає кількість маркерів, що вилучаються при вході маркерів в перехід. Вхід маркерів в перехід здійснюється за умови, що в усіх вхідних позиціях переходу наявна кількість маркерів у кількості, зазначеній у кількості зв’язків відповідної вхідної дуги. Вихідна дуга Кількість зв’язків Натуральне число Визначає кількість маркерів, що додаються при виході маркерів з переходу. Вихід маркерів з переходу відбувається, коли сплине часова затримка, зазначена Запуск переходу здійснюється за умови, що в усі вихідні позиції переходу додаються маркери у кількості, залежно від кількості зв’язків відповідної вхідної дуги. 87 Інструментальні засоби і середовища програмування де m – модель, – символ опера- ції агрегування, oj – Петрі-об’єкти, які агре- гуються, m.net – мережа Петрі моделі, o.net – мережа Петрі-об’єкта o. Перетворення стану мережі Петрі всі- єї моделі, як доведено у [15], розпадається на перетворення стану мереж Петрі-об’єктів. Це збільшує швидкодію імітації, оскільки, по- перше, при відтворенні події відбуваються зміни тільки у відповідному Петрі-об’єкті, по- друге, пошук найближчої події відбувається переглядом стану усіх об’єктів моделі замість перегляду стану усіх переходів моделі. Оскільки при з’єднанні кількох Петрі-об’єктів утворюється знову мережа Петрі, а не структура більш високого рівня, то можуть бути введені операції над Петрі- об’єктами. Операція тиражування multiply означає, що мережа Петрі використовуєть- ся для створення групи Петрі-об’єктів. При цьому списки чисельних параметрів еле- ментів мережі Петрі можуть відрізнятись (окрім кількості маркерів у позиціях, які використовуються для з’єднання з іншими Петрі-об’єктами): , де g – група Петрі-об’єктів, net - ме- режа Петрі, що використовується для ство- рення групи об’єктів, - мно- жина списків параметрів, що застосовують- ся для створення мережі Петрі конкретного об’єкта, k – кількість створюваних об’єктів. З’єднання Петрі-об’єкта o з групою g Петрі-об’єктів за правилом, сформульо- ваним для пари Петрі-об’єктів, фактично тиражує зв’язок між Петрі-об’єктом o та кожним Петрі-об’єктом з групи g: . Об’єкти, взаємопов’язані між собою, можуть утворювати колекції , для яких мож- на здійснювати тиражування за наступними правилами: де f – група колекцій Петрі-об’єктів, objects - Петрі-об’єкти, що використовуєть- ся для створення колекції, connectors – ко- нектори між Петрі-об’єктами, k – кількість операцій тиражування колекції. Інші об’єкти можуть створювати з’єднання з групою колекцій : , де з’єднання встановлюється між Петрі-об’єктом o та групою Петрі-об’єктів gu з колекції. У [16] розглянуто застосування дво- рівневої структури графічного представлення Петрі-об’єктної моделі на прикладі моделі те- лекомунікаційної системи і визначені переваги використання мови візуального програмування. У наступному розділі статті для запропонованої мови даний опис у вигляді формальної грамати- ки та зроблено висновки про її властивості. 3. Граматика мови візуального програ- мування Петрі-об’єктних моделей Мова візуального програмування ви- значає набори графічних елементів (символів), що можуть бути перетворені на змістові кон- струкції Петрі-об’єктної моделі. Графічні еле- менти, передбачені для конструювання Петрі- об’єктної моделі, є символами мови. Набори елементів, які можуть бути перетворені на імітаційні моделі і запущені на виконання – це лексеми (слова) мови. Мережі Петрі-об’єктів – це лексеми в граматиці. Вирази мови – це фрагменти Петрі-об’єктної моделі. Введемо алфавіт термінальних сим- волів для опису мережі Петрі: p - позиція, t - перехід, a – дуга. Введемо алфавіт нетермі- нальних символів: E - комбінація терміналь- них символів, що задає одну вхідну дугу переходу, Q - комбінація термінальних сим- волів, що задає одну вихідну дугу переходу, N - комбінація кількох нетермінальних сим- волів E та Q, що може бути інтерпретована в мережу Петрі. Символом I позначимо по- чатковий символ граматики. Вважатимемо, 88 Інструментальні засоби і середовища програмування що дуга, яка поєднує елементи «позиція» та «перехід», визначає відношення «попере- дній – наступний» у послідовності симво- лів, що задає лексему мови програмування. Правила виведення граматики для введених символів представлені у таблиці 2. Прави- ла визначають, що усі набори символів ін- терпретуються як трійки нетермінальних елементів pat та tap. У найпримітивнішому випадку мережа Петрі складається з однієї позиції (без переходів). Мережа Петрі може містити позиції, які не з’єднані з перехода- ми (такі позиції зберігають інформацію про стан об’єкта, а зміни в такому стані можуть відбутись тільки в результаті подій, що від- буваються в інших Петрі-об’єктах). Для опису Петрі-об’єктної моделі до- повнимо алфавіт термінальних символів гра- матики такими символами: o - Петрі-об’єкт, g - група Петрі-об’єктів, f – група колекцій Петрі- об’єктів, s – позиція Петрі-об’єкта, що вико- ристовується для з’єднання з іншими Петрі- об’єктами, l – ототожнення позицій Петрі- об’єктів. Вважатимемо, що конектор, який поєднує Петрі-об’єкт з іншим Петрі-об’єктом, або Петрі-об’єкт з групою Петрі-об’єктів, ви- значає відношення «попередній-наступний» у послідовності символів, що задає лексему мови програмування. Доповнимо алфавіт нетермі- нальних символів граматики такими символа- ми: Z – комбінація символів, що визначає пару з’єднаних Петрі-об’єктів, Y - комбінація симво- лів, що визначає з’єднання Петрі-об’єкта з гру- пою Петрі-об’єктів, X - комбінація символів, що визначає з’єднання Петрі-об’єкта з групою колекцій, C - конектор Петрі-об’єктів, що скла- дається з кількох ототожнень позицій Петрі- об’єкта з позиціями іншого Петрі-об’єкта. Пра- вила виведення 7-12 граматики (для введених символів) представлені у таблиці 3. Таблиця 3. Правила виведення 7-12 граматики Правило Зміст правила Модель складається з трійок елементів, що визначають зв’язки між двома Петрі- об’єктами, між Петрі-об’єктом і групою Петрі- об’єктів, або групою колекцій Петрі-об’єктів та мереж Петрі для створення Петрі-об’єктів (див. правило 1) Трійка символів, що визначають зв’язок Петрі-об’єкта з групою Петрі-об’єктів. Ототожнення позицій, що вказані в конекторі, тиражуються для всіх Петрі- об’єктів групи. Допускається конструювання моделі з групи Петрі-об’єктів, що не мають зв’язків з іншими Петрі-об’єктами. Трійка символів, що визначають зв’язок Петрі-об’єкта з групою Петрі-об’єктів, що входить до складу колекції. Ототожнення позицій, що вказані в конекторі, тиражуються для всіх Петрі-об’єктів групи. Допускається конструювання моделі з групи колекцій Петрі-об’єктів, що не мають зв’язків з іншими Петрі-об’єктами. Трійка символів, що визначають зв’язок Петрі-об’єкта з іншим Петрі-об’єктом. Допускається конструювання моделі з одного Петрі-об’єкта, що не має зв’язків з іншими Петрі-об’єктами. Один Петрі-об’єкт, або група Петрі-об’єктів в моделі, або кілька Петрі-об’єктів без зв’язків, або кілька груп Петрі-об’єктів без зв’язків. Трійка символів, що визначають ототожнення позиції одного Петрі-об’єкта з позицією іншого Петрі-об’єкта. Конектор складається з одного або кількох ототожнювань позицій двох Петрі-об’єктів. Таблиця 2. Правила виведення 1-6 граматики (синтаксис мови) Правило Зміст правила Для визначення Петрі-об’єктів має бути визначена одна або кілька мереж Петрі. Якщо вказана вхідна дуга, то обов’язково має бути вихідна. Якщо вказана вихідна дуга, то обов’язково має бути вхідна. Може бути задано будь-скільки вхідних та вихідних дуг у довільному порядку. Трійка термінальних символів, що визначають вхідну дугу переходу Трійка термінальних символів, що визначають вихідну дугу переходу Одна або декілька позицій в мережі Петрі 89 Інструментальні засоби і середовища програмування Графічні зображення символів мови представлені у таблиці 4. Параметри елемен- тів, які представлені символами мови, мають у графічному представленні спеціально від- ведені поля. Параметр Name призначений для введення назви відповідного елементу. Q Вихідна дуга переходу (у позицію) N Фрагмент мережі Петрі, що складається з трьох вхідних дуг та трьох вихідних дуг: EEQEQQ. o Петрі-об’єкт із вказівниками на позиції, що можуть ви- користовуватись для з’єднання з іншими Петрі- об’єктами. s Вказівник на позицію Петрі-об’єкта, що використову- ється для з’єднання sls Ототожнення позиції Петрі-об’єкта з позицією іншого Петрі-об’єкта С Конектор Z Спрощене представлення Петрі-об’єкта та з’єднання двох Петрі-об’єктів g Група n Петрі-об’єктів, створених за однаковим шабло- ном Петрі-об’єкта з назвою Name 1…n Name Name Name placeName Name placeName placeName placeName k 1 pName pName р Графічне представ- лення символу Скорочене позначення символу Інтерпретація p Позиція мережі Петрі з кількістю маркерів k. t Перехід мережі Петрі з часовою затримкою d, зі зна- ченням пріоритету r (ширина прямокутника розрахову- ється за формулою , де – значення ши- рини, що відповідає пріоритету 1) a Дуга з кількістю зв’язків q. Значення q=1 є таким, що приймається за замовчуванням E Вхідна дуга переходу (з позиції) 1 q Name d Name k Таблиця 4 Графічне зображення символів алфавіту мови візуального програмування Петрі- об’єктних моделей 90 Інструментальні засоби і середовища програмування Y З’єднання Петрі-об’єкта з групою n об’єктів f Група n колекцій Петрі-об’єктів, створених за однако- вим шаблоном. По суті, фрагмент моделі тиражується у кількості n. X Група n колекцій Петрі-об’єктів, створених за однако- вим шаблоном. По суті, це фрагмент моделі, що тира- жується у кількості n. 1…n Name Name Name 1…n Name Name Name 1…n Name Правила виведення 1-12 визнача- ють граматику мови візуального програ- мування Петрі-об’єктних моделей. Наве- дена граматика є контекстно-вільною або граматикою типу 2 за ієрархією Хомсько- го, оскільки інтерпретація будь-якого не- термінального символу не залежить від символів, які його оточують. Приклад ви- ведення за визначеною граматикою (поро- дження виразу з застосуванням послідов- ності правил 7, 10, 12, 7, 8, 12, 1, 3, 5, 2, 4, 5, 1, 3, 5, 3, 4, 2, 4, 5): Виведення може бути також пред- ставлене у вигляді дерева виведення (рис. 1). Наведений ланцюжок відповідає Петрі-об’єктній моделі, що складається з двох Петрі-об’єктів одного типу та групи Петрі-об’єктів іншого типу. Мережа Пе- трі об’єктів першого типу складається з однієї вхідної дуги та двох вихідних дуг з відповідно визначеними для них позиція- ми та переходами, а мережа Петрі друго- го типу складається з двох вхідних дуг та двох вихідних дуг. Рис. 1. Дерево виведення для моделі, представленої мовою візуального про-грамування. При створенні елементів у графічно- му середовищі елементи одного типу збері- гаються в масиві у послідовності створення розробником моделі. Враховуючи однознач- ність послідовності елементів у масивах, очевидно, що існує тільки одне дерево виве- дення для будь-якого візуального представ- лення моделі. Оскільки існує тільки одне дерево виведення для візуального представ- 91 Інструментальні засоби і середовища програмування лення моделі, то введена граматика є одно- значною. Алгоритми пошуку непродуктив- них символів та недосяжних символів на- ведені у монографії [5]. Складаємо спи- сок нетермінальних символів, які можуть бути виведені з термінальних символів: E, Q, N, C, Y, I. Оскільки усі нетерміналь- ні символи алфавіту потрапили до цього списку, то непродуктивних (зайвих) сим- волів немає. Складаємо список нетермі- нальних символів, які можуть бути виве- дені з початкового символу: I, Z, Y, N, C, E, Q. Оскільки до списку потрапили усі не- термінальні символи граматики, то недо- сяжних символів у визначеній граматиці немає. Ланцюгових правил серед правил 1-11 немає. Отже, визначена граматика є приведеною. Форма Бекуса-Наура – це інший спосіб введення граматики, який вико- ристовують, коли символів надто багато і правил виведення відповідно теж бага- то. Очевидно, що правила граматики 1-11 можна описати у вигляді розширеної но- тації Бекуса-Наура. Петрі-об’єктна-модель, описана ві- зуальною мовою програмування, транс- формується в алгоритмічну мову і запус- кається на виконання алгоритмом імітації. Правила перетворення візуальної моделі у модель обчислень визначають семантику мови. 4. Приклад представлення моделі мовою візуального програмування Наведемо приклад розробки мо- делі з використанням розробленої мови візуального програмування. Побудуємо імітаційну модель, що відтворює оброб- ку запитів клієнт-серверним застосунком. Запити надходять від користувачів двох типів: «авторів» та «гостей». Кожний тип користувача має свою логіку роботи з клі- єнт-серверним застосунком. Користувачі- автори, на відміну від користувачів-гос- тей, можуть додавати та змінювати інфор- маційний контент. Загальною проблемою таких сис- тем може бути довготривала обробка за- питу через очікування доступу до бази даних та обробку даних серверним засто- сунком. Імітація системи на моделі може допомогти розробникам визначитися з параметрами обчислювальних ресурсів, які забезпечують прийнятне значення очі- кування відповіді на запит, та з вимогами до швидкодії окремих процесів обробки запитів. Фрагмент моделі, що містить об- робку запитів, які надходять від користу- вачів-гостей, представлений на рисунку 2. Мережа Server імітує обробку запитів на сервері. Оскільки запити надходять на пошук інформації або на перегляд, то ви- користовуються два Петрі-об’єкти, ство- рені з мережею Server, зі спільними пози- ціями-ресурсами Limit queue, Threads, DB access. Використання двох Петрі-об’єктів (замість одного) дозволяє відслідковува- ти обробку різних видів запитів окремо, а також використовувати в кожному фраг- менті часові затримки, характерні для об- робки відповідного запиту. Позиції мереж Петрі, що можуть використовуватись для з’єднання з інши- ми Петрі-об’єктами, утворюють список позицій-сокетів Петрі-об’єкта. Такі пози- ції позначені сірим кольором на зображен- ні мережі Петрі (див. рис. 2) та представ- лені у списку досутпних для з’єднання позицій у зображенні Петрі-об’єкта (див. рис. 3). Три з’єднаних Петрі-об’єкти User, Server, Server утворюють фрагмент мо- делі, що імітує обробку запитів одного користувача. Щоб створити 50 користу- вачів, побудований фрагмент тиражує- мо та з’єднуємо утворену групу колек- цій з Петрі-об’єктами Server конектором Server-Server. Модель, побудована з графічних елементів, перетворюється на обчислен- ня алгоритмом імітаційного моделюван- ня стохастичної мережі Петрі. Результати імітації Петрі-об’єктної моделі інформа- ційної системи наведені у публікації [17]. Висновки Розроблена формальна граматика мови візуального програмування Петрі- об’єктних моделей. Синтаксичні правила складання мовних виразів визначені прави- лами виведення (продукціями), з яких ви- пливає, що визначена граматика є контек- 92 Інструментальні засоби і середовища програмування Server Output Input Limit queue Threads DB access Server Output Input Limit queue Threads DB access User InputS1 OutputS1 InputS2 OutputS2 1…49 User Server Server User Server Server User 1 New task Waiting server InputS2 OutputS2 Index Show OutputS1 InputS1 User net Limit queue Output Input Seize queue Seize thread Threads 400 250 1 DB access Presentation Processing Server net Рис. 2. Фрагмент Петрі-об’єктної моделі інформаційної системи, розроблений мовою ві-зуального програмування стно-вільною і приведеною. Петрі-об’єктні моделі, породжені граматикою, можуть бути перетворені на обчислення, а саме за- пущені на виконання алгоритмом імітації. Семантика мови програмування визнача- ється правилами перетворення мовних ви- разів на обчислення. Поняття Петрі-об’єктної моделі роз- ширено поняттями групи об’єктів, колекції об’єктів та групи колекції об’єктів, що дає змогу здійснювати тиражування об’єктів та зв’язків між об’єктами. Реалізація введених понять у мові візуального програмування уможливлює швидке створення та групу- 93 Інструментальні засоби і середовища програмування вання елементів моделі, динаміка яких ви- значається однаковим набором подій. За рахунок такого тиражування досягається також компактність візуального представ- лення для складних моделей. Імітація побудованої моделі викону- ється алгоритмом імітаційного моделюван- ня Петрі-об’єктної моделі. References 1. ISO/IEC 15909-1:2004 Systems and software engineering — High-level Petri nets — Part 1: Concepts, defi nitions and graphical nota- tion. [Online] – Available from: https://www. iso.org/standard/38225.html, last accessed 2020/08/28. 2. Zaitsev D.A.(2014) Paradigm of Computa- tions on the Petri Nets, Automation and Re- mote Control, Vol. 75, No. 8, 1369–1383, https://doi.org/10.1134/S0005117914080025 3. Stetsenko I.V., Lytvynov V. (2020) Computer Virus Propagation Petri-Object Simulation. In: Palagin A., Anisimov A., Morozov A., Shkar- let S. (eds) Mathematical Modeling and Simu- lation of Systems. MODS 2019. Advances in Intelligent Systems and Computing, vol 1019, 103-112. Springer, Cham. https://doi. org/10.1007/978-3-030-25741-5_11 4. Shmeleva T.R., Stetsenko I.V. (2021) Mod- eling Unconditional Forwarding Decision Within Switching Lattice. In: Vorobiyenko P., Ilchenko M., Strelkovska I. (eds) Current Trends in Communication and Information Technologies. IPF 2020. Lecture Notes in Networks and Systems, vol 212, 171- 186. Springer, Cham. https://doi.org/10.1007/978- 3-030-76343-5_10 5. Stetsenko I.V., Pavlov A.A., Dyfuchyna O. (2021) Parallel algorithm development and test- ing using Petri-object simulation. International Journal of Parallel, Emergent and Distributed Systems. Taylor & Francis. 1-16. https://doi.or g/10.1080/17445760.2021.1955113 6. Dahl, O.-J., Myhrhaug, B., Nygaard, K. (1970). Simula information. Common base language. (Report). Norwegian Computing Center. [Online] – Available from: https://bibsys-k.userservices. exlibrisgroup.com/view/delivery/47BIBSYS_ UBO/12216823070002204 7. Johnson M., Zelenski J. Formal Grammars. (2012) [Online] – Available from: https:// web.stanford.edu/class/archive/cs/cs143/ cs143.1128/handouts/080%20Formal%20 Grammars.pdf 8. Prochaska, K., Thiesing R. M. Introduction to Simio. (2016). Proceedings of the 2016 Winter Simulation Conference T. M. K. Roeder, P. I. Frazier, R. Szechtman, E. Zhou, T. Huschka, and S. E. Chick, eds. 9. Simio. The future of Simulation, Growing with you. [Online] – Available from: https://www. simio.com/about-simio/why-simio/simio-is- the-future-of-simulation-software-growing- with-you.php 10. Simul8. Visual Logic Tutorial. [Online] – Available from: https://www.simul8.com/ support/help/doku.php?id=features:visual_ logic:tutorial 11. CPNTools. [Online] – Available from: http:// cpntools.org/, last accessed 2020/04/26. 12. Jensen, K., Kristensen L. M. (2015) Colored Petri nets: a graphical language for formal modeling and validation of concurrent sys- tems. Communications of the ACM 58(6), 61- 70. DOI: 10.1145/2663340 13. Формальні мови, граматики та автомати: Навчальний посібник/ Гавриленко С.Ю. – Харків: НТУ « ХПІ », 2021. – 133 с. 14. Формальні мови та автомати / підручник для студ спец. 124 Системний аналіз / І.Я.Спекторський, В.М.Статкевич; КПІ ім. Ігоря Сікорського. – Київ: КПІ ім. Ігоря Сікорського, 2019. – 167 с. 15. Стеценко И.В. (2011) Теоретические основы Петри-объектного моделирования систем. Математичні машини і системи, 136-148. 16. Stetsenko I.V., Dyfuchyn A. (2021) Petri-ob- ject Simulation Two Level Visual Program- ming Language. In: Palagin A., Anisimov A., Morozov A., Shkarlet S. (eds) Mathematical Modeling and Simulation of Systems. MODS 2020. Advances in Intelligent Systems and Computing, vol 1265. Springer, Cham. P. 266- 276. (Scopus) https://doi.org/10.1007/978-3- 030-58124-4_26 17. Stetsenko, I.V., Dyfuchyn, A.: Petri-object Simulation: Technique and Software. Infor- mation, Computing and Intelligent Systems 1, 51-59 (2020). https://doi.org/10.20535/2708- 4930.1.2020.216057 Одержано 18.11.2021 94 Інструментальні засоби і середовища програмування Про авторів: Дифучин Антон Юрійович, аспірант 4 року навчання кафедри інформатики та програмної інженерії НТУУ “КПІ імені Ігоря Сікорського”. Кількість наукових публікацій в українських виданнях – 3. Кількість наукових публікацій в іноземних виданнях – 3. Індекс Хірша – 1. https://orcid.org/0000-0002-1722-8840 Стеценко Інна Вячеславівна, доктор технічних наук, професор, професор кафедри інформатики та програмної інженерії НТУУ “КПІ імені Ігоря Сікорського”. Кількість наукових публікацій в українських виданнях – понад 100. Кількість наукових публікацій в іноземних виданнях – 12. Індекс Хірша – 2. http://orcid.org/ 0000-0002-4601-0058 Жаріков Едуард В’ячеславович, в.о. зав. кафедри інформатики та програмної інженерії НТУУ “КПІ імені Ігоря Сікорського”. Кількість наукових публікацій в україн- ських виданнях – понад 30. Кількість наукових публікацій в іноземних виданнях – 29. Індекс Хірша – 4. http://orcid.org/ 0000-0003-1811-9336 Місце роботи авторів: Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 03056, м. Київ, проспект Перемоги 37. Тел.: (044) 236-9651 e-mail: difuchin@gmail.com stiv.inna@gmail.com zharikov.edward@gmail.com

The grammar of Petri-object model visual programming language

Institution

Similar Items