Реклама:

Для контроля корректности структуры программы может применяться эффективный метод с использованием матрицы достижимости [50]. С целью построения эффективной по вычислительной трудоемкости процедуры получения матрицы достижимости применяется списковая форма задания графа. Алгоритм построения матрицы на основе моделирования процесса движения по графу программы состоит в следующем. В соответствии со списком связей последовательно выбираются вершины графа, начиная с начальной. Очередная вершина становится как бы источником, от которого дальше распространяется волна При прохождении волны по графу отмечаются н заносятся в матрицу достижимости все достигнутые вершины. Вершины, достигнутые волной ранее, из дальнейшего рассмотрения в качестве источников исключаются Последнее условие обеспечивает однократное прохождение циклических участков графа и достижение всех возможных вершин по кратчайшим маршрутам. Условие окончания процесса соответствует тому, что среди множества вершин, достигнутых волной на очередном шаге, нет нн одной вершины, которую волна не достигла бы. Таким образом, процесс построения матрицы достижимости для одной вершины связан с однократным просмотром всех вершин графа анализируемой программы.

При использовании матрицы достижимости задача нахождения лишних участков сводится к определению множества вершин, которые не достижимы из начальных вершин. Условие принадлежности какой-либо вершины к числу тупиковых вершин состоит в недостижимости из нее ии одной конечной вершины. Выделение связных компонент, образованных лншннмн или тупиковыми вершинами, состоит в нахождении в матрице достижимости мажорирующих столбцов [50]. Выделение лишних и тупиковых циклических участков определяется путем сопоставления строк матрицы достижимости. Номера строк матрицы достижимости.

диагональные элементы которых равны I, образуют циклы. Циклическая компонента графа программы является лишней, если значения образующих ее элементов в строке начальной вершины равны нулю, и тупиковой, если значения образующих ее элементов в столбце конечной вершины равны нулю.

Средства контроля заннси и чтения переменных. Контроль записи и чтения переменных без исполнения программы включает две задачи (рис. 3.16): построение диагностической модели программы с учетом информационных связей и просмотр модели с целью выявления недопустимых сочетаний операций считывания и записи иелнчин. Схема структурных связей в виде направленного графа программы используется как база для однозначного представления на модели программы информационных связей между операторами. Для этого данные об управляющих связях каждого оператора дополняются списками операций считывания

Липаев В. В. Тестирование программ.

Рис. 3.16. Схема контроля записи н чтения переменных и записи переменных. Для проверки корректности использования памяти необходимо установить реализованную при выполнении операций в программе последовательность записи и чтения каждой переменной и последовательность обращения к устройствам ЭВМ.

Диагностическая модель программы отражает статические информационные связи с подробностью, позволяющей по каждой операции записи и считывания указывать имя величины и имя регистра, который используется для хранения ее значения. При этом структурные связи должны быть представлены с детальностью, обеспечивающей однозначное описание порядка исполнения операций записи н считывания. Это приводит к тому, что размер моделей контролируемых программ, встречающихся на практике, оказывается большим.


⇐ Предыдущая страница| |Следующая страница ⇒