УДК 004.05

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

О.Г. Артеменко*1, О.И. Федяев*2

*1 магистрант, Донецкий национальный технический университет, olga_artyomenko@bk.ru

*2 к.т.н, доцент, Донецкий национальный технический университет, fedyaev@donntu.org, OrcID: 0000-0001-6822-7306, SPIN-код: 7777-3791

Артеменко О.Г., Федяев О.И. Оценка качества программного обеспечения на основе лексического анализа исходного кода. В статье рассмотрены вопросы оценки качества программного обеспечения на основе лексического анализа. Оценка характеристик программ, написанных на языке программирования, выполнена с помощью метрик Холстеда.

Ключевые слова: качество программного обеспечения, метрики качества, метрики Холстеда, оценка характеристик программы.

Введение

Требования к скорости разработки и качеству программного обеспечения (ПО) растут неимоверно быстрыми темпами в условиях сегодняшнего быстроразвивающегося рынка ПО. Использование гибкой архитектуры и разнообразие приёмов проектирования способны влиять на повышение качества разработки, однако, что касается формальных критериев, таких как метрики кода, показывающие количественные характеристики программной системы в различных измерениях, также являются крайне значимыми [1].

Связано это с тем фактом, что в отличие от большинства отраслей материального производства, в вопросах проектов создания ПО недопустимы простые (традиционные) подходы. Известный американский инженер-программист Том Демарко сказал: «Вы не можете контролировать то, что не можете измерить» [2]. Именно поэтому для решения задач, связанных с метрическими показателями ПО, используются всесторонние и глубокие методики, которые требуют высокой ответственности в применении и определенного времени на адаптацию.

Существующие комплексные системы оценки характеристик проектов создания ПО могут, чаще всего, на качественном уровне (в рекомендательном стиле) определить моменты ухода разработки на более низкий качественный уровень, распознать наиболее сложные участки в системе, изучить сложность уже разработанного ПО или проекта на этапе разработки, оценить объём работ, стилистику и усилия, которые были затрачены на реализацию того или иного алгоритма [1], [7]. Определение же числовых показателей может дать новые сведения о разрабатываемом программном продукте и помочь более грамотно планировать направление на его дальнейшее улучшение.

Основные критерии качества ПО подразделяются на «внешние» [3], которые могут быть определены конечным пользователем, и «внутренние» [1], [8], которые важны для инженера-программиста и являются предметом исследования. Поэтому в данной статье приводятся результаты анализа одной из «внутренних» методик, направленной на количественную оценку характеристик программных средств на основе лексического анализа текста программ, которые будут полезными как в теоретическом, так и в практическом плане для специалистов по программной инженерии.

Измеряемые свойства программы по метрике Холстеда

В 1977 году Морисом Холстедом была предложена группа метрик, построенных на анализе числа строк и синтаксических элементов исходного кода программы [1], [4]. Она является интересной интегральной системой оценивания не только сложности, но и качества программ.

Непосредственным объектом анализа является сама программа, то есть исходный текст программы в виде набора строк кода на одном из языков программирования.

Согласно данной методике, оценка качества ПО проводится по результатам выявленных операторов и операндов в тексте программы с помощью лексического разбора. Операнд -- это некоторый объект или величина, обрабатываемая в программе (переменные, константы). Оператор -- это обозначение конкретного действия, выполняемого по отношению к операнду (обработка, порядок следования и др.) [1], [5]. Совокупность всех имён операторов и операндов образует словарь программы. К числу операторов также относятся:

  • имена арифметических и логических операций;
  • присваивания;
  • разделители;
  • скобки;
  • имена процедур и функций;
  • begin...end, if...then...else, do...while и др.

М.Холстед исходил из того, что тексты программ всегда удовлетворяют следующим условиям [1]:

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

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

Предполагается, что в коде программы отсутствуют ошибки, непосредственно связанные с языком программирования, что логично при условии, что программа перед оценкой её качества была скомпилирована.

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

  • n1 -- число уникальных операторов в программе;
  • n2 -- число уникальных операндов в программе;
  • N1 -- общее число всех операторов в программе;
  • N2 -- общее число всех операндов в программе;
  • f1j -- число появлений в программе j-го оператора (j=1,2,3,...,n1);
  • f2j -- число появлений в программе j-го операнда (j=1,2,3,...,n2).

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

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

  • словарь программы (n=n1+n2);
  • длина реализации программы (N=N1+N2).

Общее число всех операторов и операндов определяется по следующим формулам:

N1 = ∑ f1j, где j=1 до n1

N2 = ∑ f2j, где j=1 до n2

К важным метрическим характеристикам относится теоретическая длина программы. Для измерения теоретической длины программы N′ Холстед вводит идеализированную аппроксимацию формулы N=N1+N2:

N′ = (n1 log2 n1)+(n2 log2 n2) -- теоретическая длина программы

Метрики «теоретическая длина программы» (N′) и «длина реализации» (N) могут использоваться для выявления несовершенства программирования, которые являются следствием применения не самых удачных приёмов программирования. Используется утверждение, что если |N - N′| > 10%, то это свидетельствует о возможном наличии в программе ряда следующих несовершенств (стилистических ошибок):

  • последующая операция уничтожает результат предыдущей без их использования (a = d; a = c);
  • присутствуют тождественные выражения, решающие совершенно одинаковые задачи, например, общие подвыражения ((a + b) ∙ c + d ∙ (a + b));
  • ненужное присваивание c = a + b, если переменная «с» используется в программе только один раз;
  • наличие выражений, которые не представлены в свёрнутом виде, например x ∙ x + 2 ∙ x ∙ y + y ∙ y.

Однако, следует отметить, что на практике величины N и N′ часто существенно различаются.

Реальный и потенциальный объём программ. Другой важной характеристикой программы является её реальный объём V:

V = N ⋅ log2 n.

Как известно, если в словаре имеется n слов, то для задания номера любого из них требуется минимум log2n бит. Справедливо также:

V = n ⋅ log2 n.

В отличие от длины программы N объём V измеряется не количеством слов, а числом двоичных разрядов (бит).

Холстед вводит параметр n′ - теоретический словарь программы:

n′ = n′1 + n′2.

Здесь n′2 - количество имён входных и выходных переменных, а n′1 - количество операторов в предельно сжатом представлении программы.

Используя n′, вводится более практичная оценка:

V′ = (2 + n′2) log2 (2 + n′2).

Она основана на предположении, что существует некоторый язык программирования, называемый потенциальным, в котором все программы (по крайней мере, для некоторой предметной области) уже написаны и представлены в виде процедур или функций. Тогда для реализации любого алгоритма на этом языке потребуется всего два оператора (функция и присваивание, т.е. n′1 = 2) и имена входных и выходных переменных.

Поскольку в такой записи никакие слова не повторяются, то длина программы фактически совпадает с её объёмом. С её помощью описывается потенциальный (минимально возможный) объём программы, соответствующий максимально компактно реализующей данный алгоритм.

Уровень качества программирования. Это показатель степени расширения текста программы относительно её потенциального объёма V′.

L = V′ / V.

Нередко целесообразно определять уровень программы, не прибегая к оценке её теоретического объёма, поскольку список параметров программы часто зависит от реализации и может быть искусственно расширен [6]. Это приводит к завышению характеристики качества программирования. Показатель L характеризует степень компактности программы, экономичность использования изобразительных средств алгоритмического языка. Чем ближе значение L к 1, тем совершеннее программа. Холстед предложил аппроксимировать эту оценку выражением, включающим только фактические параметры, т.е. параметры реальной программы:

L′ = 2n2 / (n1 N2).

Специалисты считают её более корректной, чем L.

Уровень языка программирования. Было введено формальное определение уровня языка программирования, как:

λ = L ⋅ V′.

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

Как видно, значения λ заключены в узком диапазоне. Это обстоятельство объясняет тот факт, что длительные поиски «самого эффективного» языка ни к чему не привели.

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

Работа программирования. Из инженерной психологии известно, что общее количество выборок (работа программирования) будет пропорциональна N log2 n, т.е. объёму программы. Однако необходимо ещё учесть уровень её реализации L: количество выборок при этом возрастёт в 1/L раз. Обозначив интеллектуальные усилия при программировании (работу программиста) буквой Е, окончательно получим:

E = V / L.

Пример оценки качества разработанной программы

В качестве демонстрационного примера рассмотрим прототип библиотеки синтаксического анализатора (парсера), который представлен исходным кодом на языке Python (рис. 1). Библиотека реализует класс HTMLParser, который имеет два метода:

  • parse_file - получает путь к файлу и возвращает кортеж из содержимого его тега title и счетчиков изображений, таблиц и ссылок;
  • parse_dir - получает путь к директории и возвращает итератор, который возвращает кортеж из имени файла и результата исполнения метода parse_file для него.
Исходный код парсера на языке Python

Рисунок 1 — Исходный код парсера на языке Python

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

Словарь программы

Рисунок 2 — Словарь программы

В рассматриваемой программе список входных и выходных параметров не обладает большим разнообразием (табл. 2). Входными параметрами являются self, fname и dpath. Выходными параметрами являются глобальные переменные title, imgs, tables, links и fname.

Таблица 2 — Входные и выходные переменные программы
Входные Выходные
self title
fname imgs
dpath tables
links
fname

Используя исходные данные из сформированных таблиц и применяя соотношения Холстеда, можно вычислить характеристики рассмотренной программы HTMLParser (табл. 3).

Таблица 3 — Значения метрик Холстеда для программы
Характеристика Обозначение Значение
Число простых (отдельных) операторов и операций n1 19
Число простых (отдельных) операндов n2 25
Общее число операторов и операций N1 75
Общее число операндов N2 59
Общее число входных и выходных переменных n′2 8
Словарь программы n 44
Длина реализации N 134
Теоретическая длина программы N′ 196.8
Объём программы (в битах) V 731.56
Потенциальный объём программы V′ 240.21
Уровень реализации программы L 0.33
Уровень языка λ 78.87
Работа по программированию E 2230.36

Анализируя полученные значения, можно прийти к следующим заключениям:

  • уровень реализации (L) программы низкий, т.к. потенциальный объём программы в 3 раза меньше её реального объёма V;
  • длина реализации (N) программы меньше расчётной (теоретической) длины программы (N′), что может свидетельствовать об отсутствии несовершенства программирования в данной программе.

Для устранения первого замечания можно внести изменения, а конкретно убрав инициализацию счётчиков в начале метода parse_file, тогда n2 уменьшится на 2, а N2 на 6, программа улучшит свои характеристики и будет иметь следующий вид (рис. 3):

Оптимизированный алгоритм программы

Рисунок 3 — Оптимизированный алгоритм программы

Заключение

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

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

В предположении о выполнении любым текстом программы ряда условий, приведенных в статье, даётся обоснованное математическое описание метрических оценок Холстеда. Проведена апробация рассмотренной методики на примере программы, написанной на языке Python. Благодаря полученным метрическим оценкам были выявлены слабые стороны программы и внесены улучшения в программную реализацию алгоритма.

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

Литература

  1. Черников Б.В. Оценка качества программного обеспечения: Практикум: учебное пособие / Б.В.Черников, Б.Е.Поклонов; под ред. Б.В.Черникова. -- М.: ИД «ФОРУМ»: ИНФРА-М, 2017. -- 400 с.
  2. Demarco T. Controlling Software Projects: Management, Measurement & Estimation. Yourdon Press, 1982. -- 304 P.
  3. ГОСТ Р ИСО/МЭК 25010-2015. Системная и программная инженерия. - М.: Изд-во стандартов, 2015. - 36 с.
  4. Карпович Е.Е. Оценивание качества программного обеспечения САПР на основе метрических характеристик [Электронный ресурс] -- Режим доступа: https://cyberleninka.ru/article/n/otsenivanie-kachestva-programmnogo-obespecheniya-sapr-na-osnove-metricheskih-harakteristik/viewer
  5. Апостолова Н.А., Гольдштейн Б.С., Зайдман Р.А. О программометрическом подходе к оценкам программного обеспечения // Программирование. 1995. № 4. - С. 38--44.
  6. Липаев В.В. О проблемах оценивания качества программных средств // Качество, инновации, образование. 2002. № 1. - C. 93--97.
  7. Создание, использование и анализ метрик. Главные метрики [Электронный ресурс] -- Режим доступа: https://redcomrade.ru/windows-7/sozdanie-ispolzovanie-i-analiz-metrik-glavnye-metriki/
  8. Метрики Кода и их практическая реализация в Subversion и Clearcase [Электронный ресурс] -- Режим доступа: http://computers-pic-co.50webs.com/metriki-koda-i-ix-prakticheskaya-realizaciya-v-subversion-i-clearcase-chast-1-metriki-603328.html

Артеменко О.Г., Федяев О.И. Оценка качества программного обеспечения на основе лексического анализа исходного кода. В статье рассмотрены вопросы оценки качества программного обеспечения на основе лексического анализа. Оценка характеристик программ, написанных на языке программирования, выполнена с помощью метрик Холстеда.

Ключевые слова: качество программного обеспечения, метрики качества, метрики Холстеда, оценка характеристик программы.

Artemenko O.G., Fedyaev O.I. Software quality assessment based on lexical analysis of the source code. The article deals with the issues of assessing the quality of software based on lexical analysis. The evaluation of the characteristics of programs written in a programming language was carried out using Halstead's metrics.

Keywords: software quality, quality metrics, Halsted metric, assessment of program characteristics.