Cтраница 1
Граф хода выполнения программы, который не является сокращаемым, будем называть несокращаемым или несводимым. [1]
Алгоритм расчленения графа хода выполнения программы на интервалы состоит в следующем. [2]
Теорема 3.5. Пусть граф хода выполнения программы G - ( N, L, no) является сокращаемым. [3]
Лемма 3.5. Пусть граф хода выполнения программы G ( N, L, по) является несокращаемым. Тогда для него производный граф самого высокого порядка G ( k ] содержит не менее трех вершин. [4]
На рис. 3.5 показан граф хода выполнения программы G ( N, L, nQ) и последовательность его производных графов. [5]
Для этого каждую вершину графа хода выполнения программы и его производных графов необходимо снабжать признаком, позволяющим фиксировать выполнение фрагмента программы, представляемого этой вершиной, при прогоне каждого теста. Каждую вершину следует также снабжать счетчиком, позволяющим установить количество проходов через эту вершину в процессе тестирования. Понятно, что те вершины, которые содержат условный переход, должны быть снабжены двумя счетчиками. [6]
Основная проблема при формировании графа хода выполнения программы заключается в определении отношений следования для линейных участков, получаемых в процессе расчленения программы. Сложность решения этой задачи непосредственно зависит от исходно. Причиной этого ч является то, что в различных языках программирования имеются разные по числу и сложности средства явного и неявного управления последовательностью действий. [7]
Приведенный выше алгоритм формирования графа хода выполнения программ пригоден как для однопро-цедурных, так и. Это обеспечивается тем, что в алгоритме предусмотрена индикация начала и конца процедурных блоков. [8]
Теорема 3.3. Каждая вершина графа хода выполнения программы G ( N, L, n0) входит в состав только одного интервала этого графа. [9]
Анализ информационных связей производится в контексте графа хода выполнения программы. [10]
Теорема 3.4. Пусть I ( h) - интервал графа хода выполнения программы G ( N, L, n0) - Некоторая вершина rip N, n h может находиться в интервале I ( h), если только все ее непосредственные предшественники находятся в этом интервале. [11]
Такое упорядочение вершин устанавливает порядок определения множества К для вершин графа хода выполнения программы, так как каждая вершина будет иметь право на обработку только тогда, когда все ее предшественники уже обработаны. [12]
Если анализ информационных связей в однопроце-дурной программе производится в контексте графа хода выполнения программы, то для анализа межпроцедурных информационных связей необходимо определить кроме графа хода выполнения каждой процедуры, входящей в анализируемую программу, отношения вызовов, существующие между процедурами. [13]
Теорема 6.5. Алгоритм 6.3 справедлив и для анализа программ с несокращаемым графом хода выполнения программы. [14]
Следует заметить, что установление линейных участков, входящих в неявный цикл, не представляет какой-либо трудности, так как неявные циклы, аналогично явным, представляют собой интервалы графа хода выполнения программы или его производных графов. [15]