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

O. S Kuropiatnyk; B. M Yakovenko

doi:10.15802/stp2021/245666

Authors

O. S. Kuropiatnyk Dnipro National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0003-2286-884X
B. M. Yakovenko Dnipro National University of Railway Transport named after Academician V. Lazaryan, Ukraine https://orcid.org/0000-0001-6174-0027

DOI:

https://doi.org/10.15802/stp2021/245666

Keywords:

constructive-synthesizing modelling, constructor; graph representation of the text, constructor, graph representation of the text, program control graph, algorithm, algorithm correspondence

Abstract

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 conversion 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 method 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.

References

Ivutin, A. N., & Troshina, A. G. (2019). Petri-net based method of parallel programs formal verification. Vestnik of Ryazan State Radio Engineering University, 70, 15-26. DOI: https://doi.org/10.21667/1995-4565-2019-70-15-26 (in Russian)

Kondratyev, D., Maryasov, I., & Nepomniaschy, V. (2018). The Automation of C Program Verification by Symbolic Method of Loop Invariants Elimination. Modeling and Analysis of Information Systems, 25(5), 491-505. DOI: https://doi.org/10.18255/1818-1015-2018-5-491-505 (in Russian)

Cormen, Th., Leiserson, Ch., Rivest, R., & Stein, C. (2005). Introduction to Algorithms. Moscow: Vilyams. (in Russian)

Malyshev, Ye. V., & Smelov, V. V. (2018). Plagiarism detecting algorithms for software code. Proceedings of BSTU, 1(206), 135-138. (in Russian)

Nikitin, V. D., & Ivanov, A. P. (2018). Development of Methods for Assessing the Similarity of Algorithms Based on Graph Models. Magyar Tudományos Journal, 23, 36-41. (in Russian)

Sarwar, S., Qayyum, Z. Ul., Safyan, M., Iqbal, M., & Mahmood, Y. (2019). Graphs Resemblance based Soft-ware Birthmarks through Data Mining for Piracy Control. Proceedings of the Institute for System Pro-gramming of the RAS, 31(2), 171-186. DOI: https://doi.org/10.15514/ispras-2019-31(2)-12 (in Russian)

Shynkarenko, V. I., & Kuropiatnyk, О. S. (2017). Plagiarism detection problems and analysis software tools for its solve. Science and Transport Progress, 1(67), 131-142. DOI: https://doi.org/10.15802/stp2017/94034 (in Russian)

Khaled, F., & H. Al-Tamimi, M. S. (2021). Plagiarism Detection Methods and Tools: An Overview. Iraqi Journal of Science, 62(8), 2771-2783. DOI: https://doi.org/10.24996/ijs.2021.62.8.30 (in English)

Kulkarni, S., Govilkar, S., & Amin, D. (2021). Analysis of Plagiarism Detection Tools and Methods. SSRN Elec-tronic Journal, 1, 1-7. DOI: https://doi.org/10.2139/ssrn.3869091 (in English)

Kuropiatnyk, O., & Shynkarenko, V. (2020). Text Borrowings Detection System for Natural Language Struc-tured Digital Documents. In COLINS 2020. Computational Linguistics and Intelligent Systems. Proceedings of the 4th International Conference on Computational Linguistics and Intelligent Systems (COLINS 2020) (Vol. 2604, pp. 294-305). Lviv, Ukraine. (in Ukrainian)

Pandit, A. A., & Toksha, G. (2019). Review of Plagiarism Detection Technique in Source Code. In Algorithms for Intelligent Systems. (pp. 393-405). DOI: https://doi.org/10.1007/978-981-15-0633-8_38

Programforyou: redaktor blok-skhem. Retrieved from https://programforyou.ru/block-diagram-redactor (in Russian)

Shynkarenko, V. I., & Ilman, V. M. (2014). Constructive-Synthesizing Structures and Their Grammatical Inter-pretations. i. Generalized Formal Constructive-Synthesizing Structure. Cybernetics and Systems Analysis, 50(5), 655-662. DOI: https://doi.org/10.1007/s10559-014-9655-z (in English)

Shynkarenko, V. I., & Ilman, V. M. (2014). Constructive-Synthesizing Structures and Their Grammatical Inter-pretations. II. Refining Transformations*. Cybernetics and Systems Analysis, 50(6), 829-841. DOI: https://doi.org/10.1007/s10559-014-9674-9 (in English)