Граф - программа
Cтраница 2
В маршрутах исполнения программы, содержащих участки, не проверенные тестированием, наиболее возможно искажение результатов вследствие невыявленных ошибок. Предположим, что до тестирования вероятность ошибки в / - и дуге графа программы, входящей в / - и маршрут, равна цц. Пусть, кроме того, вероятность ошибки в / - и дуге в первом приближении не зависит от ошибок в остальных дугах графа программы. [16]
В реальных условиях конкретное исполнение программы происходит по одному из всех возможных Мг маршрутов. Выбор маршрута определяется обрабатываемыми данными, которые влияют на направление ветвления в вершинах графа программы. [17]
Для задачи ПАСС стационарность разметки обеспечивается непрерывностью функции разметки, интерпретирующей схему анализа. Однако, как уже подчеркивалось, задачи анализа на верхней и нижней полуструктурах свойств графа программы принципиально различны. [18]
 |
Схема средств автоматизации отладки программ в статике. [19] |
Программа изображается абстрактно в виде ориентированного графа, каждая вершина которого соответствует некоторому множеству операторов, а каждая ориентированная дуга обозначает возможную передачу управления от одной вершины к другой. Если каждая вершина обозначает один оператор или группу последовательно выполняемых операторов, то графовая модель программы называется графом программы. [20]
Автоматические машинно-независимые методы оптимизации можно разделить на локальные и глобальные. Локальная оптимизация проводится в пределах оператора ( линейного участка программы), а для глобальной оптимизации требуются построение графа программы и организация его просмотра по тем или иным признакам, именам переменных, подвыражениям. Оптимизация на линейном участке реализуется существенно проще, однако при этом возникает задача выявления таких участков. [21]
Так как из каждой вершины графа, соответствующей арифметическому оператору, исходит только одна дуга, то нетрудно убедиться, что каждой комбинации соответствует строго определенная последовательность дуг графа программы. Упорядоченную таким образом последовательность дуг, когда конец каждой дуги совпадает с началом следующей, будем называть путем графа программы. При этом всегда будем полагать, что всякий путь начинается в начальном элементе множества X, а оканчивается либо в том же элементе, либо в конечном элементе этого множества. [22]
Граф программы - это циклический ориентированный граф G ( X, U), вершины которого х представляют различные шаги программы. Вершины связаны дугами и, представляющими разветвления и циклы в программе. Граф программы содержит одну начальную вершину Xi, предшествующую всем остальным вершинам графа и не имеющую входящих дуг, и одну конечную вершину хх, которая следует за всеми остальными вершинами и не имеет исходящих дуг. [23]
Представим структуру управления программы в виде направленного графа, в котором каждая вершина Nt ( il, ) соответствует некоторому программному модулю, а дуга ( Ni, NJ) - возможной передаче управления от V ( к NJ. Можно считать, что граф программы имеет единственную входную / Vb единственную выходную Л и две дополнительные вершины, соответствующие корректному С и ошибочному F выходным результатам. [24]
Из указанных свойств получаем правило: вероятности использования всех вершин графа программы, заключенных между двумя вершинами с разветвлением программы, например Ah и Ah 1, одинаковы и равны вероятности ph использования вершины Ah. Поэтому при подсчете вероятностей использования вершин графа программы основную роль играют вероятности использования вершин с разветвлением программы и вероятности перехода, приписываемые дугам графа, исходящим из этих вершин. Это свойство позволяет заменить граф программы его конденсатом. [25]
Эффективность отладки определяется вероятностью наличия оставшихся ошибок в модуле в зависимости от затрат на создание тестов, исполнение программ и анализ данных тестирования. Для упрощения анализа можно предположить, что значения длительности и сложности вычислений на дугах графов программ одинаковы и невелики. При этих предположениях сложность теста, проверяющего каждый t - й маршрут в первом приближении, пропорциональна количеству дуг графа программы, входящих в этот маршрут, или количеству условий fj, которые необходимо задать в тесте. [26]
Для двухместной операции присваивания логика масштабирования та же, что и для операции типа сложения, но масштабированию может подвергаться только один операнд - правая часть оператора присваивания. Метод, при котором масштаб левых частей не задается описаниями, а определяется по результирующему масштабу правой части - выражению, применять нецелесообразно, так как при этом методе предполагается, что оператор присваивания значения масштабированной переменной помещен ранее всех операторов, использующих эту переменную. Это условие выполняется при структурном программировании, но в общем случае для его контроля требуется построение графа программы. [27]
В маршрутах исполнения программы, содержащих участки, не проверенные тестированием, наиболее возможно искажение результатов вследствие невыявленных ошибок. Предположим, что до тестирования вероятность ошибки в / - и дуге графа программы, входящей в / - и маршрут, равна цц. Пусть, кроме того, вероятность ошибки в / - и дуге в первом приближении не зависит от ошибок в остальных дугах графа программы. [28]
Оптимизация чисткой цикла производится / путем вынесения из цикла операторов или выражений, не зависящих от параметра цикла. Этим достигается экономия времени счета, поскольку - вынесенное - выражение вычисляется только эдил раз. При наличии вложенных циклов выражения и операторы выносятся за максимальный внешний цикл, если выражение не зависит ( непосредственно или через переменные) от параметров всех внутренних циклов. Реализация чистки цикла может быть достигнута с помощью построения графа программы и прослеживания по нему всех выражений для выявления их зависимости от параметров циклов. В принципе, эта задача средствами входного языка может быть решена программистом, определяющим целесообразность вынесения за цикл тех или иных выражений. [29]
Эффективность отладки определяется вероятностью наличия оставшихся ошибок в модуле в зависимости от затрат на создание тестов, исполнение программ и анализ данных тестирования. Для упрощения анализа можно предположить, что значения длительности и сложности вычислений на дугах графов программ одинаковы и невелики. При этих предположениях сложность теста, проверяющего каждый t - й маршрут в первом приближении, пропорциональна количеству дуг графа программы, входящих в этот маршрут, или количеству условий fj, которые необходимо задать в тесте. [30]
Страницы: 1 2 3