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

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

1.5. РАБОТА СО ЗНАЧЕНИЯМИ

Но это значение есть адрес (о чем говорит служебное слово ref),и появля-

ется возможность использовать

Имя1

как переменную: можно присваивать

ей значение типа type.

Аналогично

ref type Имя2;

сокращение для

ref ref type Имя2 = loc ref type;

Таким образом, есть возможность присваивать

Имя2

значение типа ref type.

Иными словами,

Имя2

— это переменная, предназначенная для размещения

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

Таким образом, последовательность предложений

real

= 53/5;

real

;

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

5, и переменную B вещественного типа. Можно записать и выполнить при-

сваивание

B:=A

, но не наоборот. Если же записать

real

:= 53/5;

real

;

то

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

A:=B

становится законным.

В языке

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

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

сание

int

;

определяет имена

как переменные, способные принимать целочислен-

ные значения, а

ﬂoat

;

как вещественные переменные. Но, как и обычно, иная простота хуже воров-

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

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

случая,и которые отдельно и достаточно сложно вводятся для более сложных

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

мировании.

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

вычислителя в

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

ГЛАВА 1. ПОНЯТИЯ

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

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

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

граммных единиц. Классы памяти описываются с помощью одного из сле-

дующих служебных слов:

• auto — автоматические переменные (слово auto можно не указывать).

Они имеют локальную область действия: только внутри текста той про-

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

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

ние. Это позволяет, сгруппировав некоторый текст с помощью {}, вво-

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

снаружи. Если снаружи была определена переменная с таким же име-

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

стей действия имен является общепринятой для большинства совре-

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

• external— внешние переменные:имеют глобальную область действия,

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

рой определена внешняя переменная. Внешними также считаются пе-

ременные,описанные (без служебных слов external)вне описаний всех

функций,и тогда они оказываются доступными для всех функций (внеш-

ние переменные формируют общий контекст функций программы).

Внимание!

Имя, описанное в двух и более функциях как внешняя переменная, определя-

ется как одна и та же переменная, входящая в общий контекст всех функций

программы

• static — статические переменные. Этим термином определяются пере-

менные, которым приписано фиксированное место в памяти. Они со-

здаются при входе в программу и никогда не уничтожаются. В част-

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

вызова до вызова функции.

• register — регистровые переменные. Это те переменные, которые для

оптимизации вычислений размещаются в специальных (быстрых) ре-

гистрах процессора (если это возможно). Во всем остальном они пол-

ностью аналогичны автоматическим переменным.

1.5. РАБОТА СО ЗНАЧЕНИЯМИ

Понятие класса памяти подтверждает тот факт, что

создавался как язык

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

час язык

C++

реализован практически для всех архитектур. Но для них, с

одной стороны, некоторые из конкретных средств

оказались избыточны-

ми (например, регистровые переменные на архитектуре

Intel

), с другой сто-

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

С++

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

гирование). В целом в языке

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

однородности памяти.

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

стант. Поскольку с точки зрения процессора традиционной архитектуры кон-

тейнер, содержащий константу, ничем не отличается от контейнера, в ко-

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

дает возможность

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

приписать константам имена, что широко применяется на практике. Соот-

ветствующий пример показан в программе 1.5.1.

Программа 1.5.1

Вычисление среднего арифметического значения

двух вводимых чисел

#include <stdio.h>

#deﬁne two 2

int X, Y;

int main (void)

{

scanf ( "%d, %d ", &X, &Y );

printf ("\n average of %d and %d is %d\n", X, Y, (X + Y) / two );

return 0;

}

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

воречит, в

С++

оператор описания константы введен и имеет обычную форму

(показанную в фрагменте (1.4)).

Тому, чему в

Алголе 68

соответствовали значения типа ref ref type и так

далее, в

соответствуют указатели, например:

int **

;

и ссылки:

int &r;

ГЛАВА 1. ПОНЯТИЯ

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

1. Возьмите книгу по программированию на неизвестном вам языке (же-

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

Ada

Perl

Modula

Java

FORTRAN

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

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

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

2. Перепишите одну из понравившихся вам программ, прочитанных в хо-

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

программирования.

3. Приведите пример программы, в которой выражения вида

(A + B) + C и B + (C + A)

дают различные результаты.

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

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

в зависимости от контекста.

5. Постройте трансляцию формы условного оператора из п. 1 на стр. 56 в

команды фон Неймановского вычислителя.

6. Постройте программу вычисления значения e

при целых значениях x

в диапазоне от −1 000 000 000 до 1 000 000 000, выдающую порядок

числа и 10 точных значащих цифр. Проверьте свою программу, вос-

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

(например,

Maple

Глава 2

Синтаксис, семантика и

прагматика языка

программирования

Назначение этой главы — дать введение в проблему точного определения

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

некоторые из них, имеющие прямое отношение к обучению программиста.

a) Нужно иметь уверенность в том, что составленная программа будет чле-

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

при ее написании, а не иначе. Поэтому нужно точное и доступное для

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

b) Нужно понимать, как представлены средствами языка сущности, закоди-

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

будут исполняться предусмотренные нами действия над данными сущно-

стями.

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

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

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

щественно влияют на решение и полностью сбивают нас с толку.

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

целыми числами при превышении их диапазона. Со следствиями обычно явно не диагно-

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

Например, во многих играх это — одна из самых коварных ошибок.

ГЛАВА 2. ССП

d) Все вышеизложенные аспекты соединяются воедино в проблеме перено-

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

граммистом. Например, Вы написали программу для

Windows

, а исполь-

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

Unix

и так далее. Эта задача является очень сложной и в практически важных

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

Некоторое время ми-

ровое программистское сообщество интенсивно занималось проблемой

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

решло на «более интересные» темы освоения новых архитектур машин

и новых операционных систем, тем более, что фирма

Sun

объявила про-

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

Java

. Тем не менее, проблема стоит,

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

лее запущенном состоянии. Связь данной проблемы со всеми сторонами

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

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

ных и конкретных аспектов системы программирования. На нынешний

момент единственно практичное решение проблемы переносимости — с

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

полнительные затраты труда при этом обычно в пределах 5–10%, а пере-

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

с самого начала, что означает не менее чем 100% дополнительных затрат.

§ 2.1. СИНТАКСИС, СЕМАНТИКА

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

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

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

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

следующие варианты:

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

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

грамма — та, на которой транслятор не выдает ошибки; интерпретация

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

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

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

ние будет либо весьма частным, либо неточным, либо (чаще всего) и частным, и неточным.

2.1. СИНТАКСИС, СЕМАНТИКА

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

ром).

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

жем, легендарный язык

FORTRAN

создавался вместе и одновременно

с первым транслятором с данного языка. Но это — совершенно неудо-

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

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

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

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

случае

) непосредственно на практике, без всякой теории, основыва-

ясь на этом подходе. Эксперименты с первой программой показывают

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

пробелы почти в любом месте текста. Но в некоторых местах это не до-

пускается (например, внутри последовательностей букв). Нельзя (ина-

че ничего не напечатается) удалять строчку

#include <stdio.h>

Транслятор выдаст сообщение об ошибке,если нарушена парность ско-

бок (удалены или добавлены лишние круглые или фигурные скобки).

Таким образом, мы получаем некоторую информацию и о том, какие

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

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

верхностный и малоэффективный, но самое главное, что он не дает

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

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

(грамматику).

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

следовательностей символов, изложенному на стр. 6. Мы выделяем не-

которое множество правильных (синтаксически) программ L и описы-

ваем его формально. Если это описание явное, оно может быть понято

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

ности работы транслятора. Но синтаксическая правильность не гаран-

тирует даже осмысленности программы. Таким образом, здесь опреде-

ляется лишь одна сторона языка — синтаксис.

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

единицами текста и правилами интерпретации. Это также односто-

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

ГЛАВА 2. ССП

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

ну языка — семантику.

Определение 2.1.1.

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

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

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

ющие конструкции и в конце концов на лексемы.

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

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

зволяющее определить,какие последовательности действий абстрактного ис-

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

данное ее внешнее окружение.

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

рой исполняется программа (точность представления данных, объем памяти,

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

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

нения.

Конец определения 2.1.1.

Задаваемое семантикой соответствие между входными данными, програм-

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

граммы, но для понимания программы и работы над ней необходимо, что-

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

ваться автономно от окружающего их текста.

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

ющих требований:

• К понятности для программиста и умеренной сложности описания.

• К точности и полной определенности для построения транслятора или

интерпретатора.

Эти цели концептуально противоречивы. В принципе ничто не мешает их

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

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

понятно для обычного человека. Поэтому точные описания существуют да-

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

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

2.1. СИНТАКСИС, СЕМАНТИКА

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

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

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

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

сис можно разделить на две части: контекстно-свободную грамматику

(КС-

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

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

C++

или

Ada

; и правила задания контекстных

зависимостей, дополняющие контекстно-свободное описание.

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

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

терпретации лексем от описаний имен в программе. На уровне КС-граммати-

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

языка.

Контекстные зависимости сужают множество программ, формально до-

пустимых КС-грамматикой. Например, правило «все идентификаторы долж-

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

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

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

Неоднократные попытки формально описывать контекстные зависимо-

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

чем задание контекстно-свободного синтаксиса. Вдобавок ко всему, даже та-

кие естественные правила, как только что представленное, при формальном

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

ком. По этой причине в руководствах редко прибегают к формализации опи-

саний контекстных зависимостей (одним из немногих исключений такого ро-

да является

Алгол 68

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

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

языка

Pascal

; см. стр. 28).

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

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

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

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

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

стоит достаточно серьезная теория. Эта грамматика представляется во многих формах (син-

таксические диаграммы, металингвистические формулы Бэкуса-Наура либо расширенные

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

изложение конкретного языка. Любое такое конкретное представление КС-грамматики до-

статочно понимаемо.

ГЛАВА 2. ССП

ных зависимостей. Приведем пример такого описания.

Пример 2.1.2. Дадим следующую характеризацию налагаемого (в частно-

сти языком

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

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

Это описание должно стоять либо в данном блоке, либо в охватывающем

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

Два описания одного и того же имени в одном и том же блоке не считаются

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

минанием, а второе — полноценным описанием. Если есть несколько описа-

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

них, которое стоит в самом внутреннем блоке. Если действующее описание

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

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

муся в программе.

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

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

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

Грамматика определяется системой синтаксических правил (в данном па-

раграфе чаще всего называемых просто правилами). На уровне граммати-

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

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

ностей символов. Символы называются также терминальными понятиями, а

все остальные понятия нетерминальными. Понятия бывают смысловые, т. е.

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

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

строения текста, но самостоятельного осмысливания не имеют. Минималь-

ные смысловые понятия (как уже упоминалось)соответствуют лексемам.Не-

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

человека.Минимальные из них (они подобны знакам пунктуации) естествен-

но считать вспомогательными лексемами.

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

с синтаксическими определениями.

Следующие пункты поясняют тот способ определения контекстно-сво-

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

a) Понятия языка (языковые конструкции — определяемые и входящие как

составляющие в определение) задаются как слова и сочетания слов рус-