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

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

2.2. ПРАГМАТИКА

Во многих языках, в частности, в

Object Pascal

, для подобных целей ис-

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

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

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

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

При этом оказывается исключенной ситуация, приведенная в предыдущем

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

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

задавать не для произвольных фрагментов, а лишь для тех, которые являют-

ся языковыми конструкциями. При условной компиляции проверяется кор-

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

явно отражает ее вариантность (именно это свойство нарушено в примере

2.2.3). Конечно, программист на

может писать тексты, в которых не по-

является незаметная смесь вариантов, но, к сожалению, проверить, что это

условие выполнено, препроцессор не в состоянии.

Разработчики

с самого начала мало заботились о концептуальной це-

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

ная эклектика множилась: надо было заботиться о стихийно складывающих-

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

пользователей. Ситуация типичная, она многократно повторялась в истории.

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

Pascal

линии

Turbo

. Изначально целостная модель вычислений стандартного язы-

ка

Pascal

не во всем удовлетворяла практических программистов. Это стало

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

рует последовательность версий

Turbo Pascal

. Разработчики данной линии

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

тря на значительные расширения. В целом они успешно решали очень труд-

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

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

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

Delphi

и ее языка

Object Pascal

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

банальная конкурентная гонка, которая, безусловно, заставляла чем-то жерт-

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

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

смысленность их самостоятельного раздельного развития. А далее история

Delphi

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

С/С++

. В

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

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

ГЛАВА 2. ССП

§ 2.3. АБСТРАКТНОЕ И КОНКРЕТНОЕ

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

2.3.1. Абстрактное представление

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

туру, в которой каждая структурная единица — языковая конструкция —

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

матики языка. Грамматика, таким образом, задает конкретные синтаксиче-

ские правила построения программы как строки символов и, вместе с тем,

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

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

влением программы. Здесь нет речи о вычислительном аспекте программ, ко-

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

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

ний.

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

ставлении программы.

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

дается грамматикой языка: для каждой грамматической (конкретно-синтак-

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

тель должен осуществить с ее составляющими, т. е. с сыновними вершина-

ми в дереве конструкции. Эти составляющие, являясь также конструкциями

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

составляющими их конструкциями. Однако такое использование конкретной

синтаксической структуры не совсем адекватно, в частности, по следующим

причинам.

a) Есть элементы, вообще никаким действиям не соответствующие и необ-

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

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

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

ные с точки зрения эффекта вычислений, дают разную конкретную син-

таксическую структуру (см. пример).

Пример 2.3.1. Три оператора

X = a ∗ b + c ∗ d;

X = (a ∗ b) + (c ∗d);

X = ((a ∗ b) + (c ∗d));

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

и подобные им содержательно полностью эквивалентны, тогда как с точки

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

В то же время, приведенные выше фрагменты не эквивалентны следую-

щему:

X = a ∗ (b + c) ∗ d;

Конец примера 2.3.1.

Таким образом, нужна структура синтаксических понятий, которая соответ-

ствует некоторому понятию эквивалентности программ. От выбранного кон-

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

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

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

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

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

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

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

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

эквивалентности: скобки вокруг подвыражений, связанных операцией бо-

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

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

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

операций.

Еще одна возможность, открываемая переходом к абстрактно-синтакси-

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

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

A + B ↔ B + A.

Здесь абстрактная эквивалентность выражает не просто соглашение об опус-

кании скобок,а свойство самой операции.Опыт показывает, что дальше ассо-

циативности и коммутативности в абстрактном синтаксисе двигаться весьма

опасно.

Рассмотрим, в частности, предельный случай: если считать эквивалент-

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

получению одних и тех же выходных данных (функциональная эквивалент-

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

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

абсурдно.

ГЛАВА 2. ССП

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

таксических деталей ниже приводится ряд иллюстраций, которые показыва-

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

абстрактно-синтаксических структур.

Пример 2.3.2. [Соответствие конкретного и абстрактного] В качестве раз-

вития приведенных примеров эквивалентных и неэквивалентных фрагмен-

тов программ на рис. 2.2 вверху приведены две (неэквивалентные!) абстракт-

но-синтаксические структуры арифметических выражений и их текстовые

представления. Для выражений, получающихся дописыванием лишних ско-

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

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

жений может быть предложен, если допустить переменное число ветвей у

вершин дерева (см. третий вариант на рис. 2.2, приводится дерево только для

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

риантом). Здесь уже используются конкретные знания о свойствах сложения:

его ассоциативность.

Следующий пример иллюстрирует вызов функции:

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

Приведенная на рис.2.3структура абстрактного синтаксиса для данного опе-

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

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

метра.

Конец примера 2.3.2.

Теперь перейдем к построению структуры,порождающей подобные пред-

ставления.

2.3.2. Структура абстрактного синтаксиса

Следует проводить четкое различие между схемами (шаблонами, прави-

лами и т. п.), определяющими строение какого-либо математического объек-

та, и их применением для построения объектов. Представленные примеры

относятся к применению специальных схем для порождения структур уже

известных языковых конструкций. Рассмотрим такие структуры подробнее.

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

правилом:

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

da b

a + b * c + d

a d

a + (b*c) + d

(a + b)*(c + d)

Рис. 2.2. Абстрактно-синтаксическое представление выражений

ГЛАВА 2. ССП

printf

\nX1 = %f, X2 = %f\n

X1 X2

Рис. 2.3. Оператор печати

<оператор присваивания> ::= <адрес> “=” <выражение> “;”

Языковая суть этой конструкции состоит в том, что имеются две соста-

вляющие оператора присваивания, называемые источником значения (<вы-

ражение>) и получателем значения (<адрес>, это понятие пока можно свя-

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

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

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

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

содержащегося по адресу получателя.

Знаки “=”, “;”, а также порядок следования источника и получателя в тек-

сте — это атрибуты конкретного синтаксиса. Схема задания абстрактно-син-

таксической структуры для этого оператора представлена на рис. 2.4.

Здесь использована следующая нотация:

a) Вершина, имеющая вид

— заголовок, ее внутренняя пометка — на-

именование, а внешняя — указание на те типы вершин, к которым мо-

жет присоединяться заголовок (в ней отражено, что присваивание явля-

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

употребить оператор).

b) Две ветви, оканчивающиеся вершинами

вида , имеют имена: “Полу-

чатель” и “Источник”, а пометки под ними указывают на типы вершин,

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

честве Получателя значения может служить Адрес (в частности, адрес пе-

ременной), а в качестве Источника значения — выражение, которое при-

сваивается Получателю). Вообще говоря, допускаются наборы типов под-

соединяемых вершин, состоящие более чем из одного элемента.

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

Адрес

Источник

присваивания

Оп

ратор

Получатель

Выражение

Рис. 2.4. Абстрактный синтаксис оператора присваивания

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

следующим образом:

1. Вычислить совместно ветви <Получатель> и <Источник>. В резуль-

тате должны быть получены адрес (например, переменной) и значение

<Выражения>.

2. Записать по полученному адресу вычисленное значение.

3. Завершить вычисление присваивания.

Видно, что, определяя вычисления для присваивания, приходится предпо-

лагать, что определены вычисления для каждой из ветвей: для <Адреса> и

<Выражения>;таким образом,данное определение, как и большинство опре-

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

точки зрения, рекурсивный) характер.

<Выражение> на уровне абстрактной синтаксической структуры — это

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

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

ты и переменные являются терминальными конструкциями языка (лексема-

ми) — для каждой такой конструкции считается известным, как извлекаются

ее атрибуты, в данном случае — значения.

ГЛАВА 2. ССП

В качестве характерных примеров раскрытия <Выражения> на рис. 2.5

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

читания (b) и переменной (c). Здесь фигурными и квадратными скобками

ВыражениеВыражение

Сложение

Вычитание

ВыражениеВыражение

Переменная

Выражение,

Адрес

ОперандОперанд

(a) (b) (c)

Имя

Рис. 2.5. Абстрактный синтаксис арифметических выражений

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

ставляют одну или более ветвь (пометка “+” у скобок), если ветви могут от-

сутствовать, то используется пометка “*” — см. ниже. Если представлена

единственная ветвь, то это означает использование унарного плюса (<Сло-

жение>) или минуса (<Вычитание>). Различие между схемами с фигурными

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

дочены, а во втором — упорядочены (это соответствует смыслу сложения и

вычитания как арифметических операций).

Схема (c) демонстрирует две новые возможности. Во-первых, есть не од-

на, а две позиции, в которых она может быть применена, причем с разным

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

ние. Соответственно, данная конструкция может быть использована для вы-

числения значения, и тогда она представляет собой один из вариантов <Вы-

ражения>, или для вычисления адреса, и тогда она представляет собой один

из вариантов <Адреса>. Во-вторых, связь между наименованием <Перемен-

ная> и ветвью <Имя> изображена пунктиром, отражающим тот факт, что для

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

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

<Имя> — порожден из лексемы конкретно-синтаксического уровня (<имя

переменной>),которая идентифицирует соответствующую лексему абстракт-

но-синтаксического уровня (<Переменную>). Правила идентификации, как

уже говорилось на стр. 73, не сводятся к контекстно-свободным граммати-

кам и определяются особо. Для конструкции-лексемы считается известным,

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

менной> по ее атрибуту <Имя>).

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

страктно-синтаксические структуры, изображенные на рис. 2.2 и 2.3. К при-

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

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

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

атрибута <Имя> (см. рис. 2.6). Верхняя вершина на рисунке помечена много-

точием. Это означает, что данная структура является частью другой, не рас-

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

Составление подобных абстрактно-синтаксических структур аналогично

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

схемы можно назвать абстрактно-синтаксическим домино. Но составление

структур, разумеется, не является самоцелью. Назначение их в том, чтобы

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

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

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

зотносительно их синтаксиса и реализации в системах программирования.

2.3.3. Абстрактный вычислитель и абстрактная структура

Алгоритм работы абстрактного вычислителя для <Выражения-Сложения>

определяется следующим образом:

1. Вычислить совместно все ветви <Операнд>. В результате должны быть

получены значения всех Выражений-Операндов;

2. Если набор ветвей состоит только из одной ветви, то

объявить значением <Выражения-Сложения> значение этого <Операн-

да>.

Перейти к п. 4;

3. В противном случае просуммировать значения всех <Выражений-Опе-

рандов> и объявить результат значением <Выражения-Сложения>;

ГЛАВА 2. ССП

Имя = d

Операнд

Выражение

Операнд

Умножение

Выражение

Операнд

Переменная

Имя = a

Переменная

Выражение

Операнд

Имя =

Выражение

Операнд

Имя =

Выражение

Операнд

ПеременнаяПеременная

...

Сложение

Рис. 2.6. Сложное выражение