Файл: Практикум Под редакцией Б. В. Черникова Рекомендовано умо в области.pdf

Практическое занятие
1
ОЦЕНКА ХАРАКТЕРИСТИК ПРОГРАММ
НА ОСНОВЕ ЛЕКСИЧЕСКОГО АНАЛИЗА
1.1. Метрики Холстеда
1.1.1. Теоретические сведения
Особенности формирования словаря программы
Любая программа определяет последовательность действий над операндами с помощью операторов. Исходный текст программы, за- писываемой на том или ином языке программирования представляет собой набор текстовых строк, которые записываются по специаль- ным правилам, и в том числе имеет свои элементы. Операнд – это некоторый объект или величина, обрабатываемая в программе, а опе-
ратор представляет собой обозначение конкретного действия, вы- полняемого по отношению к операнду.
Если считать, что словарь любой программы состоит только из имен операторов и операндов, то тексты программ всегда удовлетво- ряют следующим условиям:
• маловероятно появление какого-либо имени оператора или операнда много раз подряд – языки программирования, как правило, позволяют создавать такие конструкции, в которых подобные фраг- менты программы имеют минимальную длину;
• циклическая организация программ исключает многократное повторение какой-либо группы операторов и операндов – более ком- пактные варианты текстов получаются при разумном использовании развитых возможностей языков программирования, причем многооб- разие языков предоставляет богатую палитру инструментов;
• блоки программ, требующие периодического повторения при ее исполнении, обычно оформляются как процедуры или функции, поэтому в текстах программ достаточно применения только их имен;

Практическое занятие 1
12
• имя каждого операнда должно появляться в тексте программы хотя бы один раз – многие среды программирования обращают вни- мание программистов на неиспользуемые имена, которые следует удалять из текста программ, чтобы сократить объем памяти, исполь- зуемой при объявлении переменных.
Схематично эти условия, относящиеся к тексту программ, ото- бражены на рис. 1.1.
Рис. 1.1. Условия образования словаря программы
В настоящем издании будут в основном рассматриваться приме- ры программ, разработанных на языках программирования С, С++ и
С#, поэтому описание будет проводиться именно для них.
В рассматриваемых языках программирования добавление к на- бору символов, являющихся выражением, знака «;» превращает его в оператор. Так, набор символов «i++» является выражением, а конст- рукция «i++;» уже является оператором (или statement по терминоло- гии Кернигана и Ритчи [3]).
При разработке программ существует ряд особенностей, связан- ных со скобками: круглыми, фигурными и квадратными.
Одним из действий, которые могут быть записаны в исходном тексте программ, является вызов функций, записываемый в формате
Имя_функции().
В словаре операторов и операций, которые будут формироваться далее в примерах, будем различать вызов функции по появлению па- ры круглых скобок и следующим перед ними именем. Следует обра-

Лексический анализ программ
13
тить внимание, что при этом нужно отличать пару круглых скобок, используемых с другими языковыми конструкциями (например, с операторами if или for).
При формировании словаря операторов и операций учитываются еще и фигурные скобки. Они, казалось бы, не вызывают никаких дей- ствий, но связаны с ограничением области видимости переменных.
Операции, которые связаны с квадратными скобками, это обра- щение к элементам массива. Действия, связанные с их интерпретаци- ей, обеспечивают доступ к элементам массивов.
Операторы и операции связаны с объектами, над которыми они выполняются. Таким объектами являются, прежде всего, константы, простые переменные, массивы и структуры, однако подобными объ- ектами (операндами) являются и функции, а также классы и методы.
Сделаем еще одно важное замечание. При формировании слова- рей будем учитывать элементы, используемые в разделах описаний, поскольку эти элементы также можно рассматривать как операнды или операторы.
Измеряемые свойства программ
При разработке программы формируется ее текст на каком-либо языке программирования, реализующий алгоритм получения искомо- го результата на основании обработки заданной совокупности дан- ных. В тексте программы можно идентифицировать все операнды, определенные как переменные или константы, используемые в дан- ной реализации. Аналогичным образом идентифицируются все опе- раторы, определенные как символы или комбинации символов, влияющие на способ обработки, изменение значения или порядок следования и преобразования операндов. Исходя из идентификации операторов и операндов, можно определить ряд измеримых катего- рий, обязательно присутствующих в версиях любого алгоритма. Они определяются метриками, с помощью которых могут быть получены основные характеристики качества программ.
В состав измеримых свойств любого представления алгоритма
(или программы) могут быть включены следующие метрические ха- рактеристики
:
• η
1
– число простых (уникальных) операторов
,
появляющихся в данной реализации
;

Практическое занятие 1
14
• η
2
– число простых (уникальных) операндов
,
появляющихся в данной реализации
;
• N
1
– общее число всех операторов
,
появляющихся в данной реализации
;
• N
2
– общее число всех операндов
,
появляющихся в данной реа- лизации
;
• f
1j
–
число появлений в программе j-го оператора
, где j = 1, 2, 3,
...,
η
1
;
• f
2j
–
число появлений в программе j-го операнда
, где j = 1, 2, 3,
...,
η
2
Учитывая эти основные метрические характеристики для програм- мы, в конкретной реализации текста программы можно определить:
• словарь η = η
1
+
η
2
;
• длину реализации программы N = N
1
+ N
2
;
• длину программы Ñ = (η
1
· log
2
η
1
) + (
η
2
· log
2
η
2
).
Следует отметить, что помимо своегопрямого назначенияметрики длины программы и длины реализации можно использовать для выяв- ления несовершенств программирования, которые являются следстви- ем применения не самых удачных приемов программирования. Если расчетные значения длины программы и длины реализации отличают- ся более чем на 10 %, то это свидетельствует о возможном наличии в программе следующих шести классов несовершенств:
1. Наличие последовательности дополняющих друг друга опера- торов к одному и тому же операнду, например А + C – А. Понятно, что в подобном случае будет выполнено два совершенно ненужных действия, дополняющих переменную С одной и той же величиной, взятой с противоположными знаками.
2. Наличие неоднозначных операндов, например A = D и A = С.
При выполнении таких действий программа будет поставлена в за- труднительное положение, поскольку присвоение осуществляется пу- тем приравнивания значения операнда, указанного в левой части, зна- чению, приведенному в правой части выражения. В лучшем случае произойдет ненужное присвоение нового значения уже имеющемуся.
3. Наличие синонимичных операндов, например А = В и С = В.
Поскольку одно и то же значение должно быть присвоено разным переменным, то для данного примера переменная В вообще может не использоваться. Более лаконичным вариантом является простое при- равнивание значений переменных А и С.

Лексический анализ программ
15
4. Наличие общих подвыражений, например:
(А + В) · С + D · (А + В).
Здесь применено совсем не обязательное повторение суммирова- ния переменных А и В, что приводит к дополнительному времени выполнения программы.
5. Ненужное присваивание, например С = А +В, если переменная
С используется в программе только один раз. При однократном вы- полнении каких-либо операций над переменной нецелесообразно вводить дополнительный операнд, это ведет к увеличению объема памяти, резервируемой под переменные программы, и увеличивает размер словаря.
6. Наличие выражений, которые не представлены в свернутом виде как произведение множителей, например:
X · X + 2 · X · Y + Y · Y.
Данное преобразование можно представить как
(X + Y) · (X + Y), т. е. свернуть выражение до квадрата суммы переменных Х и Y.
Такое представление окажется более лаконичным и сократит время, необходимое для выполнения программы.
В соответствии с приведенными определениями применяются следующие соотношения:
1 1,
1
;
j
j
N
f
η
=
=
∑
(1.1.1)
2 2,
1
;
j
j
N
f
η
=
=
∑
(1.1.2)
2
,
1 1
i j
i
j
N
f
η
=
=
=
∑∑
(1.1.3)
Таким образом, длина реализации и объем программы определяются исключительно на основе анализа текста программы путем подсчета количества операндов и операторов, а также числа их вхождений в текст программы, т. е. на основе лексического анализа текста программы.
Длина программы представляет собой математическое ожидание коли- чества слов в тексте программы при фиксированном словаре.

Практическое занятие 1
16
Другой важной характеристикой программы является ее объем V.
В отличие от длины программы N объем измеряется не количеством слов, а числом двоичных разрядов. Если в словаре имеется η слов, то для задания номера любого из них требуется минимум
2
log η бит.
Объем программы определяется следующим образом:
2 2
2
log log
V
N
= ⋅
η = η⋅
η
. (1.1.4)
Тогда с точностью до обозначений полученные соотношения окажутся совершенно идентичными, хотя смысл их будет различным:
2
log
N
≈ η⋅
η
; (1.1.5)
2 2
log
V
= η⋅
η
. (1.1.6)
В первом случае зафиксирована взаимная связь между длиной программы N и размером словаря η, во втором – между величиной словаря и объемом программы V. Следовательно, по известному раз- меру словаря η можно найти значения N и V. Идентичность этих вы- ражений говорит о том, что соотношение между величиной словаря и длиной текста единственно и взаимно однозначно.
Выше было отмечено, что словарь программы состоит только из операторов и операндов. Учитывая принятые обозначения, соотно- шение Холстеда примет следующий вид:
1 2
2 2
1 2
1 2
2 2
1 2
log log log log
N
N
N
= η ⋅
η+ η ⋅
η ≈ η ⋅
η + η ⋅
η =
+
. (1.1.7)
Как правило, при проведении статистических исследований тек- стов программ к словарю операторов относят следующие элементы:
• имена арифметических и логических операций;
• присваивания;
• условные и безусловные переходы;
• разделители;
• скобки (парные);
• имена процедур и функций;
• выражения типа BEGIN...END, IF...THEN...ELSE, DO...WHILE.
Выражения типа BEGIN...END, IF...THEN...ELSE, DO...WHILE и им подобные, осуществляющие блочную группировку операторов, при этом рассматриваются как единые операторы (то же относится и к парам скобок).

Лексический анализ программ
17
Величины количества операторов и операндов η
1
и η
2
независимы и могут принимать произвольные значения. Однако этого нельзя ска- зать относительно N
1
и N
2
,
т. е. числа появления всех операторов
1 1
2 1
log
N
= η ⋅
η
и всех операндов
2 2
2 2
log
N
= η ⋅
η в тексте програм- мы: между ними можно установить приблизительное соответствие, причем оно будет взаимно однозначным. В каждом конкретном слу- чае каждый операнд не может позиционироваться в программе обо- собленно, он входит в текст, по крайней мере, хотя бы с одним опе- ратором: например, с разделителем (точка с запятой), отделяющим его от других операторов, или другим набором символов, опреде- ляющим способ действия над этим операндом. В то же время приме- нение нескольких операторов к одному операнду маловероятно. По- этому можно утверждать, что N
1
≈ N
2
, хотя величины словарей
η
1 и
η
2
могут сильно отличаться друг от друга. Это позволяет прийти к весь- ма важному практическому выводу относительно объема программы:
2 2
2 2 2
= 2 log
N
N
≈ ⋅
⋅η ⋅
η
(1.1.8)
Основной исходный параметр, на котором базируются все расче- ты метрических характеристик будущего ПС, – количество имен входных и выходных переменных
η
2
∗
, представленных в предельно краткой записи (с точки зрения алгоритмической сложности – сжа- той). Например, для задания одномерного массива (т. е. строки), ка- ково бы ни было число его элементов, требуется всего два имени:
• указатель адреса начала массива;
• количество элементов в нем.
Точно так же для задания двумерного массива достаточно иметь три параметра:
• указатель адреса первого элемента;
• число столбцов;
• число строк.
Если параметр
η
2
∗
, определенный таким образом, рассматривать как размер генеральной совокупности имен входных и выходных пе- ременных, то величина словаря программы
η
2
в соответствии с соот- ношением Холстеда не будет превосходить
2 2
log
∗
∗
η ⋅
η . Таким образом, можно считать, что
2 2
2 2
log
∗
∗
η ≈ η ⋅
η
. (1.1.9)

Практическое занятие 1
18
Предположим, что существует некоторый язык программирова- ния, называемый потенциальным, в котором все программы (по крайней мере – для некоторой предметной области) уже написаны и представлены в виде заранее подготовленных процедур или функций.
Тогда для реализации любого алгоритма на таком языке потребуется всего два оператора (функция и присваивание) и
η
2
∗
имен входных и выходных переменных. Это объясняется тем, что в таком потенци- альном языке программист должен будет только выбрать нужную процедуру или функцию и применить ее к нужной переменной. По- скольку в такой записи никакие слова не повторяются, то длина про- граммы совпадает с ее объемом и равна:
(
)
(
)
2 2
2 2 log
2
V
∗
∗
∗
= η + ⋅
η +
. (1.1.10)
Эта величина называется потенциальным объемом (минимально возможным), соответствующим максимально компактному тексту программы, реализующей данный алгоритм. Это объясняется тем, что в потенциальном языке минимизировано число операторов, а все операнды сведены к перечню процедур или функций и списку вход- ных и выходных переменных.
В таком случае можно определить уровень реализации програм- мы, который рассчитывается с помощью отношения
V
L
V
∗
=
(1.1.11)
Уровень реализации представляет собой метрический показатель, который характеризует степень компактности программы, экономич- ность использования средств алгоритмического языка. Чем ближе значение L к единице, тем более совершенна программа.
При переводе алгоритма с одного языка на другой его потенци- альный объем V* не изменяется, но действительный объем V может увеличиваться или уменьшаться в зависимости от развитости языков программирования.
Для потенциального языка справедливо равенство V = V*, для любого менее развитого языка следует учитывать соотношение V
>
V*. Это обусловлено тем, что для потенциального языка N*=
η*, в то время как для всех других языков применяется уравнение длины и учет соотношения N
> η.

Лексический анализ программ
19
Оптимизация количества
и длины модулей в программе
Соотношение Холстеда позволяет контролировать процесс разра- ботки программных средств, благодаря тому, что если заранее опреде- лить их длину, то можно выходить на эту заданную длину модулей при проектировании программ. Действительно, длина модулей (в пре- делах точности этого соотношения) определяется только их словарями.
В свою очередь, величина словарей зависит только от числа групп, на которые разбивается
η
2
∗
входных и выходных переменных програм- мируемой задачи. Таким образом, величина словаря модуля – кон- тролируемый параметр, а если это так, то, следовательно, и его длина может контролироваться.
Пусть k – число модулей. Тогда словарь операндов одного моду- ля будет определяться следующим выражением:
2 2
2 2
log
k
k
k
∗
∗
η
η
η =
⋅
, (1.1.12) а для всей программы (с учетом того, что в программе содержится k модулей) данное выражение будет иметь вид:
2 2
2 2
log
k
∗
∗
η
η = η ⋅
. (1.1.13)
Понятно, что каждой группе присваивается имя, которое замеща- ет эту группу в тексте программы. С учетом этого обстоятельства окончательно имеем:
2 2
2 2
2
log log
k
k
k
∗
∗
η
η = η ⋅
+ ⋅
. (1.1.14)
Наилучшее количество модулей, которое будет обеспечивать ми- нимальную длину программы, можно найти следующим образом:
2
опт
2 2
log 2
k
∗
∗
η
≈
η
(1.1.15)
При этом число входных имен каждого модуля будет равно: опт
*
2 2
2
log 2 .
k k
∗
η
=
η
(1.1.16)

Практическое занятие 1
20
Исследуя надежность программных средств, Морис Холстед в своих работах показал, что наименьшее количество ошибок обнаружи- вается в модулях, число входных переменных которых не превосходит восьми, т. е. при
η
2k
∗
≈ 8.
Программные средства реальных информационных систем имеют сложную иерархическую структуру. Как правило, самый нижний уро- вень, на котором располагаются «исполнительные» модули, является наиболее многочисленным, в то время как в верхней части управляю- щей «пирамиды» размещается один модуль, являющийся головным.
Изучая структуры больших программных систем, В.В. Липаев устано- вил, что наиболее жизнеспособными являются такие программные средства, число уровней которых не превосходит 7–8.
Проблема структуризации проектируемых программных средств, безусловно, имеет сугубо содержательный характер и принципиально не может быть формализована. Однако расчетные метрические ха- рактеристики (длина модулей, их число, количество иерархических уровней) задают оптимальные параметры структуры программных средств, наиболее рациональные в аспекте обеспечения качества реа- лизации проекта.
Оценка уровня языков программирования
Если N – длина программы, а
η – словарь программы, то общее количество выборок необходимых элементов словаря (т. е. фактиче- ски – работа программирования) в соответствии с законом Хика бу- дет равна объему программы N · log
η.
В то же время необходимо еще учесть уровень реализации програм- мы L: количество выборок при этом возрастет в 1/ L раз. Обозначив ра- боту программирования символом Е и учитывая формулу для вычисле- ния уровня реализации программы (1.1.11), окончательно получим:
2 2
log
N
V
V
E
L
L
V
∗
⋅
η
=
=
=
. (1.1.17)
В начале 1980-х гг. Холстед ввел формальное определение уров- ня языка программирования [10], определив этот уровень языка сле- дующим образом:
λ = L · V*, (1.1.18)