42719

Оценка характеристик программ на основе лексического анализа. Метрики

Лабораторная работа

Информатика, кибернетика и программирование

Наиболее ценным для практики является то что такая оценка может быть получена вручную на основе зрительного анализа текста программы либо автоматически с помощью специально разработанных программных анализаторов причем относительно несложных. Джилб предположил что логическая сложность должна являться значимым если не определяющим фактором для оценки стоимости программы на начальных этапах ее проектирования. Логическая сложность программы Джилб определяет как насыщенность программы условными операторами типа IFTHENELSE и...

Русский

2013-10-30

262.5 KB

79 чел.

Лабораторная работа № 2 Оценка характеристик программ на основе лексического анализа

Задание: Для любого приложения из лабораторной работы № 2 (часть 1) выполните оценку:

  1.  характеристик программы с помощью метрик Джилба и Чепина
  2.  Выполнить структурное тестирование

1. Метрики Джилба

1.1. Теоретическое введение

Достаточно практичными являются метрики программного обеспечения, предложенные Томасом Джилбом (Thomas Jilb) и также основанные на результатах анализа текстов программных продуктов.

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

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

Логическая сложность программы Джилб определяет как насыщенность программы условными операторами типа IF-THEN-ELSE и операторами цикла (при этом следует учитывать, что фактическая запись условий и циклов в разных языках программирования может быть представлена в разной форме при сохранении указанного смысла операторов). При этом вводятся следующие характеристики программного средства:

  •  CL - абсолютная сложность программы, характеризуемая количеством операторов условий;
  •  cl - относительная сложность программы, определяющая насыщенность программы операторами условия (т. е. относительная сложность программы cl вычисляется как отношение абсолютной сложности CL к общему числу операторов L).

Кроме указанных показателей, Джилб предложил применять следующие характеристики программы:

  •  количество операторов цикла Lloop;
  •  количество операторов условия LIF;
  •  число модулей или подсистем Lmod;
  •  отношение числа связей между модулями к числу модулей

                                                                          

         (1)

  •  отношение числа ненормальных выходов из множества операторов к общему числу операторов

       

         (2)

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

Отношение количества правильных данных ко всей совокупности данных приводится Джилбом в качестве меры точности (свободы от ошибок), поскольку он считает, что точность нужна как средство обеспечения надежности программы. Прецизионность определяется как мера того, насколько часто появляются ошибки, вызванные одинаковыми причинами. Джилб оценивает этот показатель дробью, в числителе которой указывается число фактических ошибок на входе, а в знаменателе - общее число наблюдаемых ошибок, причинами которых явились  ошибки на входе. Так, например, если одна ошибка вызывает в течение определенного периода времени появление 50 сообщений об ошибках, то прецизионность равна 0,02.

1.2.Пример:  Задача «Копирование элементов массива»

1.2.1 Задание

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

Используя данную функцию, требуется выполнить копирование положительных элементов двух исходных массивов А и В  в массив С.

Размер исходных массивов А и В ввести с клавиатуры. Массивы А и В заполняются случайными числами в диапазоне от -100 до 300ю

Сформированный массив С вывести на экраню

Для разработанного приложения определить значение метрик Джилба на основе лексического анализа исходного кода.

1.2.2 Реализация задания

Пример реализации приложения приведен в таблице 1

Таблица 1 - Пример реализации приложения для копирования элементов массива

Номер строки

Строка приложения

1

using System;

2

class Program

3

{

4

public static int[] Copy(int[] a)

5

{

6

int[] b = new int[a.Length];

7

int j = 0;

8

for (int i = 0; i < a.Length; i++)

9

{

10

  if (a[i] >= 0) { b[j] = a[i]; j++;}

11

}

12

return b;

13

}

14

15

public static void Zapoln(ref int[] a, Random g)

16

{

17

for (int i = 0; i < a.Length; i++)

18

{

19

a[i] = g.Next(-100, 300);

20

}

21

}

22

23

public static void Print(int[] a, string str, string str1)

24

{

25

Console.WriteLine(str);

26

for (int i = 0; i < a.Length; i++)

27

   {

28

    if (a[i] != 0) Console.Write(str, a[i]);

29

   }

30

Console.WriteLine();

31

}

32

33

static void Main(string[] args)

34

{

35

  int[] a, b, c, p;

36

  Random g = new Random();

37

  char r;

38

  do

39

  {

40

    Console.Clear();

41

    Console.WriteLine("Определите размер первого массива");

42

    a = new int[int.Parse(Console.ReadLine())];

43

    Console.WriteLine("Определите размер второго массива");

44

    b = new int[int.Parse(Console.ReadLine())];

45

    c = new int[a.Length + b.Length];

46

    Zapoln(ref a, g);

47

    Zapoln(ref b, g);

48

    Print(a, "{0,5}", "Первый исходный массив");

49

    Print(b, "{0,5}", "Второй исходный массив");

50

    p = Copy(a);

51

    Array.Copy(p, 0, c, 0, a.Length);

52

    p = Copy(b);

53

    Array.Copy(p, 0, c, a.Length, b.Length);

54

    Print(c, "{0,5}", "Результирующий массив");

55

    Console.WriteLine();

56

    Console.WriteLine("Выполнить повторение программы? Y/N");

57

    r = char.Parse(Console.ReadLine());

58

   } while (r == 'Y' || r == 'y');

59

}

60

}

В таблице 2  приведены операторы и операции, используемые в программе.

Таблица 2 – Словарь операторов и операций программы

П/п

Операторы, операции

Номера строк

Количество повторений

1

using

1

1

2

class

2

1

3

public static…

4,15,23,23

4

4

int[]

4,6,15,23,35

5

5

new

6,36,42,44,45

5

6

int

7,8,15,17,26

5

7

string

23,23

2

8

char

37

1

9

Random

15,36

2

10

.Length

17,6,8,26,45,45,51,53

8

11

.Next

19

1

12

Console.WriteLine()

25,30,41,43,55,56

6

13

Console.Write()

28

1

14

Console.ReadLine()

42,44,57

3

15

for ()

8,17,26

3

16

do{} while ()

38-58

1

17

if

10,28

2

18

Console.Clear()

40

1

19

Zapoln()

46,47

2

20

.Parse

42,44,57

3

21

Print()

48,49,54

3

22

Copy()

50,52

2

23

Array.Copy()

51,53

2

24

=

6,7,8,10,17,19,26,36,42,44,45, 50,52,57

14

25

>=

10

1

26

!=

28

1

27

= =

58,58

2

28

<

8,17,26

3

29

++

8,10,17,26

4

30

return

12

1

31

[ ]

4,4,6,6,10,10,10,15,19,23,28,28, 35, 42,44,45

16

32

()

4,8,10,15,17,19,23,25,26,28,

28, 30,33,36,40,41,42,42,43,44, 44,46,47,48,49,50,51,52,53,54, 55,56,57,58

35

33

{}

3(60),5(13),9(11),16(21),18(20), 24(31),27(29),34(59),39(58),10, 48,49,54

13

34

,

15,19,23,23,28,35,35,35,46,47, 48,48,49,49,51,51,51,51,53,53,53, 53,54,54,54

25

35

;

1,6,7,8,8,10,10,12,17,17,19,25,26, 26,38,30,35,36,37,40,41,42,43,44, 45,46,47,48,49,50,51,52,53,54,55, 56, 57,58

38

36

.

6,8,17,19,26,28,30,40,41,42,42,43, 44,44,45,45,46,47,48,49,50,51,51, 52,53,53,53,54,55,56,57,57

32

37

int[…]

6,42,44,45

4

38

Random()

36

1

39

“ ”

41,43,48,48,49,49,54,56

8

40

‘ ‘

58,58

2

                                                         Всего

263

Определим значения характеристик  LIF, LLoop, Lmod, f, L, Cl и cl.

Значение характеристики  LIF определяется количеством используемых в программе операторов if . В представленном решении их два (см. таблицу 2, пункт 17).

Значение характеристики  LLoop определяется количеством используемых в программе циклов. В исходном тексте данной программы содержится четыре цикла: три оператора for и один do … while (см. таблицу 2, пункт 15 и 16).

Значение характеристики  Lmod определяется количеством используемых в программе модулей в решении. В представленном решении используется четыре программных модуля, каждый из которых оперделяется следующими строками:

  •  static void Main().См. таблицу 1, строка 33;
  •  public static int[] Copy(int[] a).См. таблицу 1, строка 4;
  •  public static void Zapoln(ref int[] a, Random g). См. таблицу 1, строка 15;
  •  public static void Print(int[] a, string str, string str1) См. таблицу 1, строка 23;

Общее количество операторов условия 6, из них 2 оператора if и четыре оператора цикла. Общее число всех используемых операторов L=263 (см. таблицу 2).

Таким образом:

CL=6 – абсолютная сложность программы;

Cl=CL/L=6/263=0?0228.

Количество связей между модулями Nsv равно трем – по одной связи между основным и каждым из дополнительных модулей. Одношение числа связей к числу модулей определяется следующим образом:

Из полученных результатов анализа текста программы следует, что исходный код имеет невысокую сложность, так как на 263 оператора текста приходится всего лишь 6 операторов условий. Общее число программных модулей решения также невелико (4 модуля), что подтверждает низкий уровень сложности программы.

2 Метрика Чепина

2.1. Теоретическое введение

Мерой сложности понимания программ на основе входных и выходных данных является метрика Н. Чепина (Ned Chapin). Смысл метода, который предложил Чепин, состоит в оценке информационной прочности отдельно взятого программного модуля на основе результатов анализа характера использования переменных, входящих в состав списка ввода и вывода.

Существует несколько модификаций метрики Чепина. Рассмотрим наиболее простой, но с точки зрения практического использования достаточно эффективный вариант этой метрики.

Все множество переменных, составляющих список ввода-вывода, разбивается на четыре функциональные группы:

  •  Р - вводимые переменные для расчетов и для обеспечения вывода. Примером такой переменной может служить используемая в программах лексического анализатора переменная, содержащая строку исходного текста программы - в этом случае сама переменная не модифицируется, а применяется только как контейнер для исходной информации;
  •  М - модифицируемые, или создаваемые внутри программы, переменные. К таким переменным относится большинство традиционно применяемых переменных, декларируемых в программных модулях;
  •  С - переменные, участвующие в управлении работой программного модуля (управляющие переменные). Такие переменные предназначены для передачи управления, изменения логики вычислительных процессов и т. д.;
  •  T - не используемые в программе (так называемые паразитные) переменные. Такие переменные не принимают непосредственного участия в реализации процесса обработки информации, ради которого написана анализируемая программа, однако они заявлены в программном модуле. Такие переменные могут использоваться для выполнения промежуточных действий и не играют принципиальной роли в решении основной задачи.

В качестве особенности применения данной метрики следует назвать необходимость учета каждой переменной в каждой функциональной группе, поскольку каждая переменная может выполнять одновременно несколько функций.

Исходное выражение для определения метрики Чепина записывается в следующем виде:

                 Q =a1*P+a2*M + a3*C + a4*T                   (3)

где a1, a2, a3 и a4 ,    - весовые коэффициенты.

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

  •  a1 = 1;
  •  a2 = 2;
  •  a4 = 0,5;

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

С учетом весовых коэффициентов расчетное выражение метрики Чепина приобретает следующий вид:

Q = P+2*M + 3*C + 0,5*T.

Следует отметить, что метрика сложности программы Чепина также основана на анализе исходных текстов программ, что обеспечивает единый подход к автоматизации их расчета и может быть рассчитана с использованием специально разработанного программного анализатора.

2.2. Пример:  «Простые числа в матрице»

Дана целочисленная матрица размером N*M. Вычислить и записать в одномерный массив количество простых чисел в каждом столбце матрицы. Размерность матрицы задается с клавиатуры, заполнение матрицы осуществляется посредством датчика случайных чисел. Разработать программу для решения задачи. На основе лексического анализа исходного текста программы определить значение метрики Чепина.

2.2.1 Реализация программы

Текст программы для реализации возможного алгоритма решения поставленной задачи представлен в таблице 3.

Таблица 3- Текст программы

Номера строк

Строки программы

1

using System;

2

namespace chapin

3

{

4

class Program

5

{

6

static void Main(string[] args)

7

{

8

   int n, m;

9

10

  int[,] a;

11

  int[] b;

12

  ConsoleKeyInfo клавиша;

13

   int i, j, k, d;

14

  bool p = false;

15

  Random g;

16

  do

17

  {

18

    Console.Clear();

19

    Console.Write("Введите количество строк");

20

    n = int.Parse(Console.ReadLine());

21

    Console.Write("Введите количество столбцов");

22

 m = int.Parse(Console.ReadLine());

23

     g = new Random();

24

     a = new int[n, m];

25

     for (i = 0; i < n; i++)

26

        for (j = 0; j < m; j++)

27

        {

28

          a[i,j] = g.Next(0,101);

29

        }

30

31

     Console.WriteLine("\nИсходная матрица");

32

    for (i = 0; i < n; i++, Console.WriteLine())

33

      for (j = 0; j < m; j++)

34

        Console.Write("{0,8:d}", a[i, j]);

35

    b = new int[m];

36

37

    for (j = 0; j < m; j++)

38

    {

39

      for (i = k = 0; i < n; i++)

40

      {

41

        p = true;

42

           for (d = 2; d < a[i, j]; d++)

42

            if (a[i, j] % d == 0) p = false;

44

45

46

           if (p) k++;

47

               b[j] = k;

48

       }

49

            }

50

51

52

    Console.WriteLine("\nКоличество простых чисел");

53

   for (i = 0; i < b.Length; i++)

54

      Console.Write("{0,8:d}", b[i]);

55

56

    Console.WriteLine("\nДля выхода нажмите клавишу ESC");

57

   клавиша = Console.ReadKey(true);

58

} while (клавиша.Key != ConsoleKey.Escape);

59

}

60

}

61

}

2.2.2 Оценка характеристик программы

Выполним оценку качества программы с помощью метрики Чепина, которая позволяет оценить меру трудности понимания программы на основе входных и выходных данных. Все множество переменных, составляющих список ввода-вывода, разбивается на четыре функциональные группы:

  •  Р - вводимые переменные для расчетов и для обеспечения вывода;
  •  М - модифицируемые, создаваемые внутри программы переменные;
  •  С - переменные, участвующие в управлении работой программного модуля (управляющие переменные);
  •  T - не используемые в программе переменные.

В таблице 4 приведен  анализ  исходного текста программы

Таблица 4 – Анализ исходного кода программы

№ п/п

Наименование переменных

Номера строк

Р ( для расчетов и для обеспечения вывода)

1

m

8

2

n

8

3

a

10

М ( модифицируемые или создаваемые внутри программы переменные)

1

i

13

2

j

13

3

k

13

4

d

13

5

b

11

C (управляющие переменные)

1

g

15

2

p

14

3

клавиша

12

T  (не используемые в программе переменные)

Отсутствуют

Переменные т,п и а используются в качестве исходных данных.

Переменные i, j, k, d и b в процессе выполнения программы создаются и модифицируются.

Переменные g, р и клавиша используются для управления выполнением программы.

Таким образом, исходя из результатов анализа исходного текста программы, получаем следующие значения характеристик:

Р = 3 - количество переменных для расчетов;

М = 5 - количество модифицируемых переменных;

С = 3 - количество переменных, используемых в управлении программой;

Т = 0 - количество неиспользуемых переменных (такие переменные в программе отсутствуют).

Расчет метрики Чепина:

Q = P + 2M + 3-C + 0,ST = 3 + 2-5 + 3-3 + 0,5-0 = 22.

На основе полученных значений метрики Чепина уровень сложности данного решения можно считать сравнительно низким, как так в исходном тексте программы используется незначительное количество переменных, что не затрудняет понимание программы.

EMBED Equation.3  

EMBED Equation.3  

EMBED Equation.3  


 

А также другие работы, которые могут Вас заинтересовать

74408. Вторичное утолщение корней 30 KB
  В результате образуется замкнутое камбиальное кольцо с лопастным и только в диархных корнях овальным очертанием на поперечных срезах. У многих многолетних растений деятельность камбия в корнях так же как и в стеблях периодична и часто можно видеть кольца прироста рис. У древесных пород относящихся к двудольным гистологическое различие между древесиной корня и ствола выражено еще более резко: в корнях трахеи и трахеиды более многочисленны и более тесно расположены более тонкостенны а обычно и более широкопросветны1 снабжены более...
74409. Гинецей 59.5 KB
  У некоторых растений столбик не развит рыльце находится непосредственно на завязи и называется сидячим. Так как семяпочки заключены внутри завязи то на них не могут непосредственно как у голосеменных переноситься пылинки.
74410. Половое размножение голосеменных растений 48.5 KB
  Покров вырастает из основания нуцеллуса так называемой халацы обрастает нуцеллус постепенно снизу вверх но на вершине не смыкается оставляя отверстие так называемый пыльцевход или семявход илимикропиле. Из получающихся четырех клеток одна сильно разрастается вытесняя три остальные и большую часть нуцеллуса; это и будет мегаспора...
74411. Заложение и развитие листа 29.5 KB
  Сначала его клетки делятся во всех трех направлениях и зачаток листа растет в толщину и высоту. Довольно рано рост в толщину прекращается и зачаток листа становится плоским. Вначале зачаток листа не разделен на части но вскоре можно различить две части верхнюю и нижнюю причем верхняя апикальная первое время растет быстрее нижней базальной.
74412. Заложение прокамбия и типы строения стеблей 46.5 KB
  Закладывается замкнутое кольцо прокамбия. Довольно часто внутрь от первичной ксилемы часть прокамбия дифференцируется в дополнительные участки внутренней флоэмы барвинок Vinc вьюнок Convolvulus и др. При таком заложении прокамбия листовые следы могут быть совсем незаметны а могут быть хорошо выражены.
74413. Перидерма и корка корней 26 KB
  Клетки экзодермы паренхимы первичной коры и эндодермы не могут обеспечить такого интенсивного разрастания и первичная кора при этом разрывается и разрушается. Перед сбрасыванием первичной коры в более глубоких слоях образуется перидерма. Из двулетних растений с мясистыми корнями многие в том числе морковь образуют перидерму; в корнях других растений например свеклы феллоген не закладывается: происходит лишь подкрепление кольца толстостенной эндодермы путем отложения утолщений на стенках клеток первичной коры примыкающих к эндодерме а...
74414. Перидерма 48 KB
  В силу плотного смыкания клеток пробки заполнения их полостей воздухом обладающим как известно очень слабой теплопроводностью и наличия в оболочках клеток суберинового слоя очень слабо проницаемого для воды и воздуха пробка предохраняет стволы и ветви от излишней потери воды за счет испарения и от резких температурных колебаний. Кольцо феллогена в большей своей части состоит из плотно сомкнутых живых паренхимных клеток имеющих на поперечном разрезе форму прямоугольника относительно малого радиального размера а на продольном...
74415. Покровные ткани 52 KB
  Кожица состоит из плотно сомкнутых клеток имеющих в плане у большинства растений более или менее извилистые очертания рис. У некоторых растений например у многих злаков кожица состоит из клеток нескольких типов рис. Оболочка эпидермальных клеток утолщается обычно неравномерно: в каждой клетке наиболее толста наружная стенка боковые стенки несколько тоньше внутренняя сравнительно тонка. Боковые и внутренние стенки клеток обычно имеют поры рис.
74416. ПРОВОДЯЩИЕ ПУЧКИ 36 KB
  Проводящие пучки нередко включают и иные ткани живую паренхиму млечники склеренхиму. Проводящие пучки сопровождаемые примыкающими к ним тяжами механической ткани обычно склеренхимы называются сосудисто-волокнистыми или армированными проводящими пучками. Проводящие пучки тянутся на значительном протяжении вдоль органа; ответвлениями и перемычками анастомозами они связываются в трехмерную сетку.