Алгоритм побудови графу потоку керування за текстом програми мовою С

Abstract

UK: Актуальність. Робота присвячена проблемі автоматизованої побудови графу потоку керування за текстом програми мовою С, що є важливим етапом структурного тестування вбудованих систем. Мета роботи – створення алгоритму побудови графу потоку керування за текстом програми, що має високу швидкість роботи та дозволяє подальше застосування існуючими засобами автоматизованого тестування. Метод. Запропоновано алгоритм побудови графу потоку керування за текстом програми мовою С, який здійснює попередню обробку вхідного тексту програми шляхом видалення коментарів та порожніх рядків, визначає кількість вершин та ребер графу потоку керування на основі синтаксичного аналізу тексту програм, а також формує, заповнює та зберігає матрицю інцидентності в окремому текстовому файлі, що дозволяє подальше використання засобами тестування, які у якості вхідних даних приймають граф потоку керування, окрім того, текстовий файл може використовуватись засобами для графічного представлення графу потоку керування. Результати. Розроблено програмний модуль, що реалізує запропонований алгоритм, який використано при проведенні експериментів з дослідження залежності часу побудови графу потоку керування від кількості рядків тексту програми. Висновки. Проведені експерименти підтвердили працездатність запропонованого алгоритму та розробленого на його основі програмного модуля, довели придатність результатів роботи алгоритму, що дозволяє рекомендувати його для подальшого застосування засобами автоматизованого тестування для зменшення часових витрат на тестування вбудованого програмного забезпечення. EN: Actuality. The work considers the problem of automated construction of the control flow graph using the text of a program written in C. The graph construction is an important step in the structural testing of embedded systems. Objective. The work is aimed at creation of a fast algorithm for constructing the control flow graph from a source code. Such an automatically generated graph can be used by existing tools for automated testing. Method. We propose an algorithm for constructing the control flow graph from the program written in C language, which preprocesses the source code of the program by removing comments and blank lines, determines the number of vertices and edges of the control flow graph by means of program text syntactic analysis, and then formats, fills and stores the incidence matrix in a separate text file. This file can be passed as input data for some existing automated testing tools. Moreover, the content of the text file can be visualized by existing tools for graphic representation of graphs. Results. We’ve developed a software module that implements the proposed algorithm. The module can be used for experiments aimed at studying the dependence of the control flow graph’s time construction on the amount of lines in a source code. Conclusions. The conducted experiments confirmed the operability of the proposed algorithm and the software module developed on its basis. The results have proved the applicability of the algorithm, thus it can be recommended for further use together with automated testing tools to reduce the time required for testing of embedded software.