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

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

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

ского языка, обрамляемые угловыми скобками < и >. Эти слова и сочета-

ния слов называются наименованиями понятий.

b) Символы и (непрерывные)последовательности символов,из которых стро-

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

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

жения некоторых лексем.

c) Каждое правило в определении грамматики размещается с нового абзаца.

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

определения знаком ::= (читается: «определяется как»).

e) Вариантные фрагменты правила, т. е. те части определяемой конструк-

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

обрамляются скобками [ и ]; между собой варианты разделяются знаком

f) Если за фрагментом, заключенным в скобки [ и ], следует знак +, то в

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

произвольное число раз.

g) Если за фрагментом, заключенным в скобки [ и ], следует знак *, то фраг-

мент повторяется (произвольное число раз) либо отсутствует.

h) Если за фрагментом, заключенным в скобки [ и ], следует знак ?, то фраг-

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

Имеется ряд достаточно широко применяемых соглашений, облегчающих

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

мальной строгости (которую, впрочем, легко восстановить):

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

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

тельный смысл уже не определяется).

2. Следующие фрагменты текстов считаются комментирующими:

(a) пробелы, знаки табуляции и перехода к следующей строке текста;

(b) последовательности символов, заключенные в /* и */, и не содер-

жащие в себе эти пары символов;

ГЛАВА 2. ССП

ющиеся концом строки текста.

Комментирующие фрагменты нужны только для пояснений.

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

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

4. При описании языка используются понятия вида <имя ...>, где мно-

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

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

как <имя> (см., напр., определение ниже):

<имя ...> ::= <имя>

<буква> ::= “A” | “a” | “B” | “b” | “C” | “c” | “D” | “d” | “E” | “e” | “F” | “f” |

“G” | “g” | “H” | “h” | “I” | “i” | “J” | “j ” | “K ” | “k ” | “L ” | “l” | “M” | “m” | “N”

| “n” | “O” | “o” | “P” | “p” | “Q” | “q” | “R” | “r” | “S” | “s” | “T” | “t” | “U” | “u” |

“V” | “v” | “W” | “w” | “X” | “x” | “Y” | “y” | “Z” | “z” | “_”

<цифра> ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”

<имя> ::= <буква> [ <буква> |<цифра>]*

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

что смысле.

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

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

моменту в примерах программ:

<программа /* на языке С*/>::=<заголовок>[<описание функции /* одна

из которых имеет имя

main

*/> ]+

<заголовок /* это определение упрощено

*/> ::= [<объявление подключа-

емого файла>]*

<объявление подключаемого файла> ::= “#include” <указание имени фай-

ла>

<указание имени файла> ::= “<” <наименование файла> “>” |<наимено-

вание файла>

<наименование файла> ::=

<имя файла> [ “.” <расширение> ]?

Комментарий

/*это определение упрощено*/

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

данное понятие определено более полно. Некоторые из таких понятий в дальнейшем будут

дополняться.

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

<расширение> ::=<имя >

<описание функции> ::= [ <тип функции >]?

<имя функции > “(” [ <параметры> [“,” <параметры> ]* ]? “)”“{”<описания>

<операторы> “}”

<тип функции> ::= <имя типа> |“void”

<параметры> ::= <описатель> < имя параметра > [ “,” <имя параметра>

<описатель /* это определение будет дополняться*/> ::= <имя типа>

<описания> ::=[ <описание> ]*

<описание /* пока это определение дается только для группы перемен-

ных*/> ::= <описатель> <имя переменной> [ “,” <имя переменной> ]*

<операторы> ::=[<оператор> ]*

<оператор /* это определение упрощено*/> ::= <оператор присваивания>

|<оператор вызова функции> |<условный оператор> |<блок> |<пустой опера-

тор>

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

позже */“;”

<оператор вызова функции> ::= <имя функции> “(” [ <аргумент> [“,” <ар-

гумент> ]* ]? “);”

<аргумент> ::= <выражение >

<условный оператор> ::= “if (” <условие> “)” <оператор> [ “else” <опера-

тор> ]?

<условие> ::= <выражение >

<блок> ::= “{” [ <оператор> ]* “}”

<пустой оператор> ::= /* пустая последовательность лексем */

Вывод понятия в КС-грамматике можно представить как дерево, в верши-

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

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

правило. Рассмотрим пример.

Пример 2.1.3. Вывод описания функции

main

смотри на рис. 2.1. С помо-

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

void main(void){}

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

Для усвоения материала настоятельно рекомендуется построить вывод

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

вил.

ГЛАВА 2. ССП

<тип функции>

void

<имя функции>

main

(<параметры>)

void

{<описания> <операторы>}

<оператор>

<пустой оператор>

<описание функции>

Рис. 2.1. Функция

main

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

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

ся вопрос, как задавать это соответствие. В параграфе 2.3 ему будет уделено

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

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

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

перерабатываемых им данных.

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

ка —это построение двух программ:

1. Вычисление функции соответствия: построение по тексту программы

(аргументу функции) его образа как последовательности команд аб-

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

2. Вычисление функции моделирования абстрактного вычислителя коман-

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

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

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

личны также критерии качества (эффективности) их реализации, не всегда

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

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

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

санной им программы.

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

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

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

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

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

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

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

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

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

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

не хочет знать о регистрах, процессоре и других объектах конкретного обо-

рудования.

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

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

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

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

оперирования с программами:

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

ризуется как абстрагирование;

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

лях;

• исследование общих свойств программ математическими методами воз-

можно только при отвлечении от особенностей конкретных вычисли-

телей.

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

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

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

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

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

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

ГЛАВА 2. ССП

Иными словами, библиотечные средства — дополнительные команды аб-

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

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

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

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

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

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

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

К сожалению, говорить об идентичности трансформации абстрактных

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

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

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

числами точно

. Гораздо существеннее то, что при программировании для

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

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

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

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

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

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

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

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

кими будут реальные программы и т. д.

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

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

ми ее воплощения. Как влияет такой компромисс на языки программирова-

На самом деле даже в принципе ни один вычислитель не может точно работать с такими

идеальными и актуально бесконечными объектами, как действительные числа.

Показательный пример такого рода дает язык

FORTRAN

. В этом языке разрешается ис-

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

сто игнорируются), в том чисел и таких:

IF A

DO I

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

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

DO I=1

DO I=1,...

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

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

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

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

ния — предмет обсуждения следующего параграфа.

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

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

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

ющих направлениях:

• Все определения становятся явными (изгоняются такие понятия, как

«не определено», «определяется реализацией» и т. п.)

• Появляются дополнительные конструкции,описатели и др.,обусловлен-

ные реализацией. Они обязательно учитывают:

– особенности вычислительной машины и среды вычислений,

– особенности принятой схемы реализации языка,

– обеспечение эффективности вычислений,

– ориентацию на специфику пользователей.

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

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

лей предназначены язык и его реализация.

Пример 2.2.1. В языке

Pascal

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

тарии, например,

{$I+}, {$I-}

(включение/выключение контроля ввода-выво-

да). Многие из таких комментариев практически во всех версиях одни и те

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

{$...}

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

Рассмотрим крайний случай. Пусть данный язык ориентирован на реали-

зацию лишь в единственной операционной обстановке (например,это какой-

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

ник). Есть ли надобность в этом случае выделять прагматику специально?

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

что — к их оптимизации, ее можно выделить.

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

вания: синтаксическая и семантическая. Синтаксическая прагматика — это

Нельзя абсолютизировать это требование.Совместные вычисления могут оставаться про-

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

ГЛАВА 2. ССП

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

Пример такого рода — скоропись для определения переменных и констант в

Алголе-68

(см. стр. 64).

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

на единицу. В

С/С++

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

<переменная>++;

или

++<переменная>;

<переменная>--;

или

--<переменная>;

Turbo-Pascal

Inc (<переменная>)

Dec (<переменная>)

соответственно.В

С/С++

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

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

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

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

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

Если же рассматривать

Turbo Pascal

как правильное расширение стан-

дартного языка

Pascal

, не содержащего обсуждаемые команды из-за стрем-

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

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

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

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

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

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

Пример 2.2.2. Стандарт языка

Pascal

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

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

са за диапазон допустимых значений. Однако в объектом коде постоянные

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

пример, когда можно гарантировать соответствующие значения индексов).

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

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

распознать шаблон вида

<переменная> “:=” <переменная /* та же самая */> “+” 1

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

<переменная>

указана

явно,но и тогда, когда она вычисляется (индексирование,косвенная адресация и т.д.). Таким

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

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

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

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

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

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

неявно, иногда даже без соответствующих разъяснений в руководствах. При-

мер операторов увеличения и уменьшения на единицу из

Turbo Pascal

демон-

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

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

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

Turbo Pascal

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

ляции и исполнения (см. пример 2.2.1).

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

матику от семантики: прагматика — это то, что органично не вписывается в

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

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

обеспечить явное выделение прагматического уровня. Зачем это нужно? От-

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

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

ко ограничиваются возможности программиста применять в своей практике

методы абстрагирования. Следующие иллюстрации обосновывают данное

утверждение.

Пример 2.2.3. Стандарт языка

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

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

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

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

рет на себя решение задачи подключения к программе внешних (библиотеч-

ных) файлов (см. 1.2), с его помощью можно скрывать утомительные детали

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

основных средствах языка (например, именованные константы — см. 1.5.1).

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

есть то, что получается после ра-

боты препроцессора с текстом (разумеется, если результат такой работы ока-

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

таксическая прагматика языка. Но это противоречит практике работы про-

граммиста: он просто не в состоянии написать содержательную программу,

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

процессора. Если при программировании на

ограничиваются употребле-

ГЛАВА 2. ССП

нием препроцессорных команд подключения файлов определений и опре-

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

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

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

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

ной структуры.

Пусть написано

if (x > 0)

Firstmacro

else

PerformAction

;

Внешне это выглядит как то, что действие выполняется, если x 6 0, но

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

PrepareAction

; if (x <= 0)

CancelAction

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

же она у него так себя ведет...

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

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

мирования на

: они применяются, чтобы в одном общем тексте задать не-

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

работе препроцессора, т. е. до выполнения.

Наложение команд препроцессора на текст программы — это смешение

двух моделей вычислений: одна из них — модель базового языка

, другая —

модель препроцессора.

В результате программист при составлении и изу-

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

провоцирует ошибки.

Модель вычислений препроцессора можно охарактеризовать следующими свойствами.

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

ке

), в котором имеются строки, начинающиеся с символа ‘#’. Такие строки представляют

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

#include ...

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

понимать это буквально — нужно просто обеспечить соответствующий эффект). Другой

пример:

#deﬁne two 2

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

two

дол-

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

жит его команд.