Визначення відповідності тексту алгоритму програми на основі конструктивно-продукційної моделі графа керування
Loading...
Date
2021
Journal Title
Journal ISSN
Volume Title
Publisher
Дніпровський національний університет залізничного транспорту імені академіка В. Лазаряна, Дніпро
Abstract
UK: Мета. Основною метою статті є розробка та програмна реалізація методу визначення відповідності тексту алгоритму програми, представленого у вигляді блок-схеми. Методика. Для зіставлення тексту програми та блок-схеми побудовано математичну модель їх перетворювачів у графове представлення з використанням апарату конструктивно-продукційного моделювання та його методів: спеціалізації, конкретизації, інтерпретації та реалізації. Графове представлення (графи) тексту будується з урахуванням операторів керування, блок-схеми – за json-файлом, що містить опис елементів схеми та їх зв’язків. Для порівняння графів застосовано метод пошуку в ширину з підрахунком кількості однакових вершин. Для програмної реалізації розробленого методу й моделей була застосована технологія об’єктно-орієнтованого програмування та CASE-технології, в основі яких лежить уніфікована мова моделювання UML. Результати. Запропоновано метод, що дозволяє представити текст та блок-схему програми в єдиному форматі орієнтованого графа (графа керування) та виконати оцінку їх відповідності за кількістю однакових вершин. Для його формалізації та автоматизованого використання розроблено конструктивно-продукційні моделі перетворювачів вхідних даних. На основі моделей та методу створено програмний додаток. Наукова новизна. Отримали подальший розвиток методи конструктивно-продукційного моделювання в задачах обробки текстів, написаних штучними мовами. Побудована система конструкторів, що виконує перетворення тексту програм мовою С++ у граф керування. Практична значимість. Результати роботи мають значення для розв’язання таких задач, як зіставлення текстів програм із метою виявлення запозичень, визначення відповідності алгоритмів програм їх програмним реалізаціям із метою поліпшення навичок кодування. Графове представлення, яке продукує розроблена система конструкторів, може бути застосоване для дослідження впливу оптимізації та рефакторингу коду на складність програм із використанням метрик МакКейба.
EN: Purpose.The main article purpose is to develop and implement the method for identifying the correspondence between the text and the program algorithm represented in the form of a flowchart. As part of the method work con-version of the input data in the graph representation is performed by means of constructive-synthesizing modelling. Methodology. To compare the program text and flowchart, we constructed a mathematical model for converting the program code into a graphical representation on the basis of control structures. To build the model, the apparatus of constructive-synthesizing modeling and its methods were used: specialization, concretization, interpretation and implementation. The graph representation of the text is created taking into account the control operators; the flowcharts are created using a json file containing the description of the diagram elements and their links. To compare the graphs we use the breadth-first search algorithm with the number of identical vertices being counted. To obtain the software implementation of the developed method and models we used the technology of object-oriented programming and CASE-technologies, which are based on the unified modeling language UML. Findings A meth-od is proposed to present the text and the flowchart of the program in a uniform format of the directed graph (control graph) and to evaluate their correspondence by the number of identical vertices. For its formalization and automated usage, we developed constructive-synthesizing models of input data transformers. The program application was developed based on the models and the method. Originality. The methods of constructive-synthesizing modeling in the tasks of processing texts written in artificial languages were further developed. We developed the system of constructors, which transforms text program in C++ into a control graph. Practical value. The results are significant for solving such tasks as assembling program texts for borrowings detection, determining the correspondence of the program algorithms and their software implementations to improve coding skills. The graph representation produced by the developed system of constructors can be used for investigation of influence of optimization and code refactoring on the program complexity using McCabe's metrics.
EN: Purpose.The main article purpose is to develop and implement the method for identifying the correspondence between the text and the program algorithm represented in the form of a flowchart. As part of the method work con-version of the input data in the graph representation is performed by means of constructive-synthesizing modelling. Methodology. To compare the program text and flowchart, we constructed a mathematical model for converting the program code into a graphical representation on the basis of control structures. To build the model, the apparatus of constructive-synthesizing modeling and its methods were used: specialization, concretization, interpretation and implementation. The graph representation of the text is created taking into account the control operators; the flowcharts are created using a json file containing the description of the diagram elements and their links. To compare the graphs we use the breadth-first search algorithm with the number of identical vertices being counted. To obtain the software implementation of the developed method and models we used the technology of object-oriented programming and CASE-technologies, which are based on the unified modeling language UML. Findings A meth-od is proposed to present the text and the flowchart of the program in a uniform format of the directed graph (control graph) and to evaluate their correspondence by the number of identical vertices. For its formalization and automated usage, we developed constructive-synthesizing models of input data transformers. The program application was developed based on the models and the method. Originality. The methods of constructive-synthesizing modeling in the tasks of processing texts written in artificial languages were further developed. We developed the system of constructors, which transforms text program in C++ into a control graph. Practical value. The results are significant for solving such tasks as assembling program texts for borrowings detection, determining the correspondence of the program algorithms and their software implementations to improve coding skills. The graph representation produced by the developed system of constructors can be used for investigation of influence of optimization and code refactoring on the program complexity using McCabe's metrics.
Description
О. Куроп’ятник: ORCID 0000-0003-2286-884X; Б. Яковенко: ORCID 0000-0001-6174-0027
Keywords
конструктивно-продукційне моделювання, конструктор, графове представлення тексту, граф керування програми, алгоритм, відповідність алгоритму, constructive-synthesizing modelling, constructor, graph representation of the text, program control graph, algorithm, algorithm correspondence, КІТ
Citation
Куроп’ятник О. С., Яковенко Б. М. Визначення відповідності тексту алгоритму програми на основі конструктивно-продукційної моделі графакерування. Наука та прогрес транспорту. 2021. № 4 (94). С. 12–24. DOI: 10.15802/stp2021/245666.