Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

2.3. ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ

4. Завершить вычисление <Выражения-Сложения>.

Следует обратить внимание на то, что абстрактное вычисление выраже-

ния предполагает объявление результата-значения, тогда как для оператора

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

ющих операции, определяется подобным образом. Если порядок операндов

операции (как, к примеру, для вычитания) существенен, то он наследуется от

текстового представления и сохраняется в синтаксической структуре, а пото-

му есть возможность использования его при задании вычислений. В против-

ном случае (как при сложении) текстовый порядок операндов игнорируется.

Конкретно-синтаксическое понятие <операторы>может представлять по-

следовательно выполняемые операторы, параллельно выполняемые опера-

торы, либо совместно выполняемые операторы. Соответственно, в абстракт-

но-синтаксическом представлении должны поддерживаться три варианта ис-

пользования этой конструкции. Однако, применительно к языку

, конструк-

ция <операторы> всегда задает последовательное выполнение. Поэтому для

данного языка можно ограничиться одним из абстрактно-синтаксических ее

представлений. Тем не менее, для полноты картины полезно определить еще

совместно выполняемые последовательности операторов. Это может исполь-

зоваться, например, когда транслятор в состоянии определить, что эффект

выполнения некоторой серии операторов не зависит от их порядка, а потому

допустимо задание такой последовательности вычислений, которая удобна в

данной ситуации.

Таким образом, на рис. 2.7 показаны две схемы для образования абстракт-

но-синтаксической структуры операторов:

• операторы,выполняемые последовательно (схема используется в пози-

ции, называемой далее <Операторы>), и

• совместно выполняемые операторы (схема предназначена для исполь-

зования в позиции <Совместные операторы>).

В обеих схемах скобками выделены наборы, состоящие из нуля и более ве-

твей (на это указывает пометка “*”).Представленные схемы отличаются толь-

ко тем, что в первой из них набор упорядочен, а во второй — нет (исполь-

зование квадратных и фигурных скобок, соответственно). Новое в них то,

что демонстрируется возможность не указывать наименование ветвей, когда

в этом нет необходимости.

Алгоритм работы абстрактного вычислителя для <Последовательно вы-

полняемых операторов> задается следующим образом:

ГЛАВА 2. ССП

Операторы

Оператор

Последовательно

выполняемые

Совместные

операторы

Оператор

Совместно

выполняемые

Рис. 2.7. Две схемы исполнения

1. Если ветвей у вершины нет, то

завершить вычисление <Последовательно выполняемых операторов>.

2. Вычислить последовательно все ветви вершины.

3. Завершить вычисление <Последовательно выполняемых операторов>.

Как уже отмечалось,разветвление вычислений —необходимое средство язы-

ков программирования. В большинстве языков для этого используется кон-

струкция условного оператора. Эта конструкция, как правило, представлена

в двух видах: с вариантом “иначе” и без него. В абстрактно-синтаксической

схеме можно обойтись одним видом, т. к. нужный эффект дает пустой на-

бор операторов в качестве одной из ветвей. На рис. 2.8 представлена требуе-

мая схема. Здесь <Действия T> — это операторы, выполняемые, когда ветвь

<Условие> дает истину, а <Действие F> — когда оно дает ложь.

Стоит отметить, что на абстрактно-синтаксическом уровне ничего не го-

ворится о порядке ветвей вершин операторов присваивания и условного опе-

ратора.Это чисто текстовая информация, хотя в иных случаях, например,при

задании последовательно выполняемых операторов, операции вычитания и

др., порядок ветвей существенен.

2.3. ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ

усло

ный

Условие

Выраж

ние

Действия T

Оп

раторы

Действия F

Оп

раторы

Оп

ратор

Рис. 2.8. Условный оператор

Алгоритм работы абстрактного вычислителя для <Условного оператора>

сводится к следующему:

1. Вычислить ветвь <Условие>.

2. Если результат вычисления 1 — истина, то

Вычислить ветвь <Действие T>.

3. Если результат вычисления 1 — ложь, то

Вычислить ветвь <Действие F>.

4. Завершить вычисление <Условного оператора>.

Для определения условного оператора может быть предложен альтернатив-

ный способ, который не предполагает вычисления <Действие F> с пустым

набором операторов. Но в этом случае ветвь “иначе” должна быть факульта-

тивной, т. е. допускающей отсутствие ее в абстрактно-синтаксической струк-

туре. По существу, это отказ от совмещения двух вариантов <Условного опе-

ратора>: с “иначе” и без него. Новые средства, нужные для такого предста-

вления условного оператора, демонстрируются на рис. 2.9, где факультатив-

ность ветви отмечается фигурными скобками с вопросительным знаком (ветвь

может появиться один раз или отсутствовать). Естественно, что при исполь-

зовании альтернативного представления необходимо переопределить алго-

ритм работы абстрактного вычислителя.

ГЛАВА 2. ССП

усло

вный

Условие

Выраж

ение

Действия T

Операторы

Действия F

Оп

ераторы

Оператор

Рис. 2.9. Альтернативная форма условного оператора

Подобным образом описываются все другие абстрактно-синтаксические

схемы языковых конструкций и действия абстрактного вычислителя с ни-

ми. Перечислим различные варианты связей между элементами абстрактной

древовидной синтаксической структуры:

a) число ветвей данной вершины фиксированное, вариантное или произволь-

ное;

b) ветви упорядочены или нет;

c) идентификация ветвей посредством имен или иным способом;

d) наличие или отсутствие у вершины атрибута, используемого для вычи-

слений.

Что дают абстрактно-синтаксические представления?

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

текстов и как о способе задания программ для вычислений;

2. Точнее указывают на то, что существенно, а что нет с разных позиций,

точек зрения: текста, семантики трансляции и семантики вычислений;

3. Облегчают сравнение структур языков.

Следует подчеркнуть,что дерево абстрактного синтаксиса —это дерево струк-

туры, т. е. оно отражает отношение между конструкциями, которое можно

охарактеризовать глаголом «содержит»:вершина-конструкция содержит в ка-

честве своих составляющих конструкции ветвей.

2.3. ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ

2.3.4. Вызовы как пример синтаксических схем

Особый интерес представляют схемы, которые изображают использова-

ние средств, конструируемых программистом. К ним, в частности, относятся

вызовы процедур и функций. Для таких средств можно предложить два ва-

рианта вычислений:

a) задание универсального механизма,использующего как параметр имя сред-

ства, определяемого программистом и, тем самым, дающего возможность

отослать к определению средства для активизации вычислений, когда это

требуется;

b) динамическое определение (построение) схемы активизации вычислений

для заданного программистом средства, а также настройка шаблона дей-

ствий абстрактного вычислителя для работы с появляющейся схемой. Это

делается при описании данного средства, а при использовании описанно-

го понятия (вызове средства) осуществляется активизация настроенного

шаблона.

Оба варианта имеют право на существование: первый проще с точки зрения

задания абстрактных вычислений, второй более нагляден, т. к. дает возмож-

ность не различать встроенные в язык и определяемые программистом сред-

ства.В качестве иллюстрации на рис. 2.10 приводятся два варианта абстракт-

Имя

Параметр

Выражение

функции

Вызов

Имя

функции

Параметр

Выражение

Выражение,

Оператор

функции

Имя

Выражение,

Оператор

(a) (b)

Рис. 2.10. Два варианта вызова функции

но-синтаксических схем, представляющих конструкцию <вызов функции>

для языка

100

ГЛАВА 2. ССП

Алгоритм действий абстрактного вычислителя для схемы (a) предпола-

гает определение того, какая именно функция должна быть вызвана (рабо-

та с ветвью Имя функции). Во втором варианте при обработке определения

функции должна быть подготовлена схема и задействован соответствующий

шаблон действий абстрактного вычислителя, который активизируется при

обработке вершины Имя функции в синтаксической структуре. Указанные

различия нашли свое отражение и в наименованиях схем.

Выбор варианта определения семантики вычислений обусловливается осо-

бенностями языка, а точнее, возможностями, предоставляемыми программи-

сту для организации оперирования с создаваемыми им конструкциями.

Пример на рис. 2.11демонстрирует древовидное представление фрагмен-

та текста программы 1.4.2:

Программа 2.3.1

...

if ( D > 0 )

{

D = sqrt ( D );

X1 = r + D;

X2 = r - D;

printf ("\nX1 = %f, X2 = %f\n", X1, X2);

}

else

...

и возможности использования представленных выше схем.

Если вы захотите переписать фрагмент, приведенный в программе 2.3.1,

скажем, на язык

Pascal

, и построите его абстрактно-синтаксическую струк-

туру (понятно, что для этого нужна предварительная работа: описание со-

ответствующих шаблонов!), то вы убедитесь, что с точностью до оператора

вывода результатов счета, получится то же, что и для языка

. Это ли не под-

тверждение родственности моделей вычислений двух языков!

§ 2.4. ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ

Любой алгоритмический язык является формальным языком

. Поэтому

Точнее, должен являться в теории и во всякой своей конкретной реализации является.

2.4. ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ

101

...

Имя = printf

Условие

Действия T

Последовател

но

выполняемые

…

Условный

Переме

ная

Операнд

Константа

Операнд

Присваи

ание

Присваи

ние

Присваи

ние

Имя

функции

Имя = D Значение = 0

Адрес

Получ

тель

Переменная

Параметр

Константа

Параметр

Переменная

Источник

Переме

ная

Получ

тель

—

Источник

Имя = D

Переме

ная

Операнд

Имя = r Имя = D

Переменная

Операнд

Переме

ная

Операнд

Имя = r Имя = D

Переменная

Операнд

Имя = X1

Имя = X2

Переме

ная

Операнд

Имя = sqrt

Имя = D

Имя = X2

Переменная

Параметр

Имя = X1

Значение = "

nX1 = %f, X2 = %

\n"

Получатель

Источник

Имя

функции

Последовател

но

Действия F

выполня

мые

Рис. 2.11. Представление фрагмента текста программы

102

ГЛАВА 2. ССП

для его точного определения нужно задать его синтаксис и семантику. Мето-

ды определения синтаксиса рассматриваются во вводных курсах программи-

рования для будущих профессионалов. Хотя полноты определения синтакси-

са обычно не достигают, но изложение этих методов достаточно последова-

тельное и строгое (как Вы могли увидеть в предыдущих главах данной кни-

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

определения (как, например, соглашения о том, какое описание соответству-

ет какому вхождению идентификатора), об этом говорится прямо.

Семантику же обычно рассказывают на поверхностном уровне, без те-

ни точных определений, в выражениях типа «При исполнении присваивания

x:=S

старое значение, содержавшееся в памяти, обозначенной именем

, ис-

пользуется для вычисления

, после чего заменяется на полученное значе-

ние.» Это скорее беда, чем вина начальных (да и профессиональных) курсов

программирования. Ведь смысл — многоаспектное, крайне сложное и не-

формализуемое понятие. Это означает, что любое его уточнение приемлемо

лишь для некоторых целей и отказывает в других случаях. Но это не озна-

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

ее формализации, мы тем самым сползем на позицию первых языков типа

FORTRAN

: смысл выражений языка определяется тем, как они переводятся

транслятором и исполняются компьютером.

Далее, поскольку алгоритмические языки делались прежде всего не для

удобства определения их свойств, а для удобства их использования, работа-

ет концептуальное противоречие, которое вы могли бы уже заметить в кур-

се, например, логики: чем удобнее представление формального понятия для

применения, тем тяжелее его строгое формальное определение. Определе-

ние семантики реальных алгоритмических языков намного сложнее семан-

тик математических языков (хотя и намного проще семантик естественных

языков). Оно находится как раз на той грани, когда считанные по пальцам

профессионалы еще могут создать точное и полное определение и восполь-

зоваться им, но при этом практически все их интеллектуальные ресурсы ухо-

дят на выработку и освоение данного понятия. Соответственно, данное точ-

ное определение задает лишь значение либо действие конструкций языка,

Конечно, такое определение семантики алгоритмического языка в принципе является не-

погрешимым для каждой конкретной его реализации, применяемой в конкретной среде про-

граммирования. Но оно, мало того, что ничего не дает для осмысленного применения чело-

веку, еще и меняется непредсказуемо при изменениях версии или настроек транслятора и

всей вычислительной системы.

2.4. ПРИНЦИПИАЛЬНЫЕ ТРУДНОСТИ, СВЯЗАННЫЕ С СЕМАНТИКОЙ

103

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

ся алгоритмическим языком на практике, прибегает к точному определению

(если оно имеется; в частности, у языка

Pascal

его нет, есть лишь стандар-

ты, которые практически не применяются) лишь в самом крайнем случае, и

обычно при помощи посредника-трансляторщика. И даже те, кто реализуют

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

если только они не будут проходить официальную аттестацию на строгое со-

ответствие принятому стандарту (как, например, разработчики трансляторов

для языка

Ada

, сертифицируемых Министерством обороны США).

Рассмотрим, какие же стороны смысла нужно принять во внимание при

анализе семантик алгоритмических языков.

I) Интерпретационная семантика. Прежде всего, программа задает ал-

горитм,который должен исполняться вычислительным устройством.Та-

ким образом, нужно для всех осмысленных конструкций языка (грубо

говоря, для всех лексем) задать, какие действия либо вычисления они

должны вызывать.

II) Функциональная семантика. Далее, программа нам часто нужна как

способ получения ответа по входным данным. Соответственно, если

нас интересует данный аспект программ, то мы должны интересоваться

программой в целом как функцией либо преобразователем состояний,

и в принципе действия отдельных лексем либо операторов программы

нам безразличны.

III) Логическая семантика. Далее, программа решает некоторую задачу.

Часто нам совершенно безразлично, какой конкретный результат дает

программа, лишь бы для некоторого множества исходных данных она

давала бы ответ, удовлетворяющий сформулированным требованиям.

Применим идеализацию, что условия на вход и на связь между входом

и выходом заданы точно (т. е. описаны на языке логики). Тогда нас инте-

ресуют прежде всего свойства входных и выходных данных, исходных

и конечных состояний и, соответственно, возможно, также свойства не-

которых промежуточных данных либо состояний. Программа в данном

случае выступает как преобразователь условий.

IV) Трансляционная семантика. Далее, программа должна быть обрабо-

тана нашей вычислительной системой и переведена в исполняемый код.

Поэтому нас интересует соотношение между понятиями программы и

104

ГЛАВА 2. ССП

внутренними понятиями вычислительной системы. Это необходимо пре-

жде всего для построения транслятора либо интерпретатора. Соответ-

ственно,данный вид семантик подробнее всего разработан,но реже все-

го применим для программистов-практиков.

V) Алгебраическая семантика. И, наконец, нам часто нужно преобразо-

вывать программы, и тогда на совокупность программ естественно смо-

треть как на некоторую обобщенную алгебраическую систему. Соответ-

ственно, те внутренние понятия программ, для которых критично нали-

чие внутренне непротиворечивой и богатой системы преобразований,

тоже описываются на алгебраическом языке.

В каждый момент практической деятельности нам нужна лишь часть из этих

аспектов семантики программ, но зато конкретные проблемы часто требу-

ют аккуратного выбора конкретного формализма. А в некоторых из перечи-

сленных выше областей различающихся по своим целям и возможностям

формализмов уже достаточно много. Поэтому для успешного применения

накопленных мощных методов и орудий необходимо комплексное видение

сложнейшей проблемы семантического описания алгоритмических языков и

программ. Далее, часто, как и бывает в столь сложных и основательно про-

анализированных областях, приносит пользу не столько само по себе теоре-

тическое решение, сколько подсказанные им идеи либо выявленные при его

анализе ограничения.

Но для корректного применения аппарата и идей приходится преодолеть

достаточно много трудностей, поскольку математический аппарат, использу-

емый теорией семантик алгоритмических языков, весьма изощрен и исполь-

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

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

Задача часто усложняется еще и тем, что разные виды семантик тесно

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

функциональная семантика тесно взаимосвязаны, а логическая вообще по-

чти никогда не ходит в одиночку.

Задания для самопроверки

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

переписывание программы могут превысить 100% ее исходной стои-

мости?