авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

Пышкин Е.В.

СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ:

ОСНОВАНИЕ И РАЗВИТИЕ МЕТОДОВ

С примерами на языке C++

Учебное пособие

Санкт-Петербург

Издательство Политехнического университета

2005

УДК 004.415.2:004.43 (075.8)

ББК 32.973-018я73

Пышкин Е.В. Структурное проектирование: основание и развитие

методов. С примерами на языке C++: Учеб. пособие. – СПб.: Изд-во

Политехнического ун-та, 2005. – 324 с., ил.

Учебное пособие содержит материал, сопровождающий курс лекций, читаемый автором студентам факультета технической кибернетики Санкт Петербургского государственного политехнического университета.

В учебном пособии рассматриваются основные модели управления вычислительным процессом, лежащие в основе структурного программирования, и систематические методы проектирования программного обеспечения, ориентированные на процедурную парадигму. Книга также содержит краткое введение в мультипарадигменное программирование. В качестве базового языка используется язык программирования C++.

Учебное пособие может быть использовано при проведении занятий по курсам «Алгоритмизация и теория программирования», «Программирование на языке высокого уровня», «Теория и технология программирования» и при изучении смежных дисциплин студентами, обучающимися по специальностям 210100 «Информатика и управление в технических системах», «Вычислительные машины, комплексы, системы и сети», «Программное обеспечение вычислительной техники и автоматизированных систем». Материалы учебного пособия могут использоваться студентами, обучающимися по программе второго высшего образования, а также для самообразования.

Рекомендовано к изданию кафедрой автоматики и вычислительной техники факультета технической кибернетики.

Табл. 9. Ил. 150. Библиогр.: 79 назв.

© Пышкин Евгений Валерьевич, © Санкт-Петербургский государственный политехнический университет, ISBN 5-7422-1000- Мы структурируем программы, чтобы облегчить их модификацию;

в конце концов, программы тем и отличаются от «железа», что их можно менять Мартин Фаулер Глаз следует путями, проложенными для него в произведении Пауль Клее... элемент не предшествует в своем существовании целому, он не опережает целое и не одновременен с ним, не отдельные элементы определяют целое, но целое определяет свой элементный состав: знание о законах целого и о его структуре невозможно было бы вывести из информации о его отдельных частях Жорж Перек Одного формализма недостаточно, поскольку он ведет к малопонятным деталям;

точно так же недостаточно одного здравого смысла и интуиции (...), поскольку им сопутствует много ошибок и плохих решений. Что необходимо - это тонкое равновесие между ними Дэвид Грис... профессиональное использование иерархической декомпозиции в сочетании с пошаговым уточнением структур данных – более важные инструменты разработки программного обеспечения, поскольку они не зависят от выбранной формы реализации (функционально ориентированной или объектно ориентированной) Михаил Федорович Лекарев Об авторе этой книги Пышкин Евгений Валерьевич – кандидат технических наук, доцент кафедры автоматики и вычислительной техники Санкт-Петербургского государственного политехнического университета.

Области интересов автора в научной и преподавательской деятельности связаны с изучением современных моделей и технологий программирования. Опубликовал ряд книг и статей по различным аспектам программирования, в том числе в 2005 году: монографию «Основные концепции и механизмы объектно-ориентированного программирования», статью «Уровни абстрагирования при управлении сложными типами в структурном программировании», статью «Синтаксический анализ выражений в скобочной форме на основе визуального формализма L-сети»

(в соавторстве с М.Ф. Лекаревым).

В ходе работы на кафедре Пышкин Е.В. участвовал в ряде международных проектов. В рамках сотрудничества в области образовательных технологий приглашался в Финляндию (Central Ostrobothnia Polytechnic) для проведения краткосрочных курсов: «Основы языка программирования Java», «Введение в программирование на платформе Microsoft.NET Framework». Для организации соответствующих лекционных курсов и практикума были подготовлены и опубликованы учебные пособия на английском языке: «Understanding the Object Model»

(2003), «An Introduction to the Microsoft.NET Framework Architecture and Tools» (2004).

В СПбГПУ читает следующие курсы:

Основы алгоритмизации и программирования. Технология программирования. Программирование на языке высокого уровня Объектно-ориентированное программирование Информационные технологии в проектировании программного обеспечения Играет на фортепиано. В 2004 году в концертном зале Ylivieskatalo Akustiikka (Финляндия) записал программу “Night in Ylivieska”, составленную из произведений Моцарта, Дебюсси, Скрябина и нескольких собственных сочинений.

Содержание Предисловие............................................................................................. Введение.................................................................................................. Изучение структурного программирования: проблемы и современное состояние...................................................................... Организация книги............................................................................... Исходные тексты программ............................................................... Использование книги в учебном процессе...................................... Глава 1. Основание программирования.......................................... 1.1. Необходимые предпосылки........................................................ Кодирование и содержание........................................................................... Системы счисления........................................................................................ Понятие сложности кода................................................................................ Цифровые вычислительные машины........................................................... Операции над двоичными числами.............................................................. Основные элементы языка программирования........................................... Языки программирования C и C++: цели разработки и назначение.......... 1.2. «Алгоритмы + структуры данных = программы»..................... Описания программных объектов................................................................. Определение действий над программными объектами............................. Понятие об определении и объявлении....................................................... 1.3. Понятие о структурно-императивном программировании..... Определение императивного программирования....................................... Целевая архитектура...................................................................................... Процедурная парадигма................................................................................ Глава 2. Понятие типа данных........................................................ 2.1. Стандартные типы данных.......................................................... Целые типы..................................................................................................... Символьные типы........................................................................................... Плавающие типы............................................................................................ Логический (булевский) тип........................................................................... Указатели......................................................................................................... Ссылки............................................................................................................. 2.2. Массивы.......................................................................................... 2.3. Перечисления................................................................................. 2.4. Множества...................................................................................... 2.5. Структуры и классы...................................................................... 2.6. Объединения.................................................................................. 2.7. Система типов C++........................................................................ Глава 3. Организация процедурного кода...................................... 3.1. Алгоритмы: определения и способы записи............................ Текстуальная форма записи........................................................................ Схема алгоритма.......................................................................................... Диаграммы Нэсси-Шнейдермана................................................................ Диаграммы Дейкстры................................................................................... Псевдокод...................................................................................................... Запись в форме программы на языке программирования........................ ДРАКОН-схемы............................................................................................. Р-схемы.......................................................................................................... Запись алгоритмов функционирования реактивных систем..................... От схем алгоритмов и конечных автоматов к визуализации проектирования.

............................................................................................ 3.2. Основные управляющие конструкции структурно императивного программирования................................................. Условная инструкция.................................................................................... Повторяющиеся вычисления (циклы)......................................................... Безусловная передача управления............................................................ Мультиветвление.......................................................................................... 3.3. Функционально-иерархическая декомпозиция....................... Основные стратегии проектирования: первоначальные сведения.......... Процедуры и функции.................................................................................. Вызов функционального блока и возврат управления.............................. 3.4. Области видимости и классы памяти....................................... Область видимости программных объектов.............................................. Классы памяти и время жизни программных объектов............................. 3.5. Механизмы связывания функциональных модулей............. Связывание по значению............................................................................. Связывание с косвенной адресацией......................................................... Связывание по ссылке................................................................................. Связывание через общий интерфейс......................................................... 3.6. Функции и управление исполнением программы.................. Механизм обратного вызова........................................................................ Рекурсия........................................................................................................ Глава 4. Управление данными в процедурной программе....... 4.1. Построение модели предметной области................................ Постановка демонстрационной задачи...................................................... Анализ предметной области........................................................................ Построение модели обрабатываемых данных.......................................... Построение модели фрагмента грамматики русского языка.................... 4.2. Иерархия функций обработки подготовленных данных....... Подготовка набора сведений, описывающих десятичную константу...... Формирование текстуальных наименований............................................. 4.3. Модульность в связи с управлением данными..................... 4.4. Полиморфизм в процедурном программировании............... Перегруженные функции.............................................................................. Шаблоны функций........................................................................................ Функции как параметры функций................................................................ Введение в процедурно-параметрический полиморфизм........................ Глава 5. Управление связанными структурами данных........ 5.1. Матричный контейнер................................................................ Постановка задачи........................................................................................ Решение на базе структурной модели управления действиями и данными......................................................................................................... Уровни абстрагирования и обобщенная модель....................................... Интеграция сегментов: «Вычисления = операции + управление»........... 5.2. Списочные структуры (на примере односвязного списка).. Постановка задачи........................................................................................ Реализация абстракции списка и базового комплекта операций............ Определение других операций над списком. Первоначальное представление о рефакторинге кода.......................................................... Реализация операций вставки элемента в обобщенной форме.............. Проблемы реализации................................................................................. Построение гибридного кода....................................................................... 5.3. Древовидные структуры............................................................ Бинарное дерево как вариант организации данных в одномерном массиве.......................................................................................................... Алгоритм поиска с использованием бинарного дерева............................ Алгоритм сортировки с использованием бинарного дерева.................... 5.4. Hash-таблицы и ассоциативные массивы.............................. Hash-поиск. Идея алгоритма....................................................................... Распознавание служебных слов из фиксированного набора................... Ассоциативные массивы.............................................................................. Глава 6. Вычислительная процедура, или почему не работает чисто императивный подход.................................... 6.1. Императивная модель................................................................ Задача о возведении в степень. Постановка............................................. «Наивное» решение и его проблемы.......................................................... Решение, учитывающее представление данных в памяти компьютера.................................................................................................... Проблемы чисто императивного решения................................................. 6.2. Функционально-иерархическая декомпозиция...................... Выявление ограничений и контроль вычислительного процесса............ Структурная и модульная организация проекта........................................ Ограничения, присущие процедурной модели.......................................... 6.3. Построение гибридного кода. Введение в мультипарадигменное программирование.................................... Разработка и использование типа SafeLong.............................................. Понятие об общности и изменчивости кода............................................... Глава 7. Визуализация проектирования в примерах и иллюстрациях...................................................................................... 7.1. Визуальный формализм на базе L-сети................................... Среда последовательного управления...................................................... Среда разветвленного управления............................................................. Управление данными................................................................................... 7.2. Визуальный язык ДРАКОН......................................................... 7.3. Визуализация проектирования систем, основанных на событиях.............................................................................................. Диаграммы состояний Д. Харела................................................................ SWITCH-технология...................................................................................... Глава 8. Задачи лексического и синтаксического анализа..... 8.1. Постановка задачи....................................................................... 8.2. Лексический анализ..................................................................... Понятие синтерма: непересекающиеся и пересекающиеся синтермы....................................................................................................... Формирование и распознавание синтерма................................................ 8.3. Решение задачи синтаксического анализа логических выражений в форме L-сети............................................................... Лексический анализатор в форме L-сети................................................... Синтаксический анализатор в форме L-сети............................................. Экспресс-анализ средств проектирования................................................. Заключение............................................................................................ Компьютерные программы для людей........................................... Несколько слов о форме и содержании.......................................... От сложного к простому, или принципы Дэвида Стрэйкера........ Приложение 1. Задачи для самостоятельного практикума............................................................................................ П1.1. Вычислительные процедуры.................................................. П1.2. Управление сложными и связанными типами..................... П1.3. Лексический и синтаксический анализ.................................. Приложение 2. Описание компакт-диска...................................... Список источников............................................................................. Предисловие Существует тесная связь между способностью ясно выражать свои мысли и способностью составлять программы для ЭВМ. Характерно в связи с этим заявление руководителей японских программистов, сделанное на одной из конференций: «Наиболее важным языком, который необходимо знать программисту, является не JCL или PL/1, а японский язык»

Р. Лингер, Х. Миллс, Б. Уитт «Теория и практика структурного программирования»

В настоящее время многие специалисты отмечают, что методы разработки, ориентированные на функционально-ориентированное (процедурное) программирование, не исчерпали себя, более того – во многих областях применения информационных технологий остаются главенствующими [Brooks, 1995], [Паронджанов, 1999], [Лекарев, 1997], [Легалов, 2000].

Понятие «структура программы» в последнее время претерпело существенные изменения. Эти изменения отчасти обусловлены успехами развития технологий программирования, основывающихся на объектно ориентированной парадигме. Использование объектно-ориентированных технологий само по себе не влечет автоматического улучшения качества программного обеспечения и преодоления присущей программному обеспечению (ПО) сложности. М.Ф. Лекарев отмечает, что, хотя объектно ориентированные методы представляют собой существенный прогресс в развитии систем проектирования ПО и позволяют преодолеть многие виды дополнительной сложности, этот прогресс не затрагивает существенную сложность, поскольку относятся в большей части к форме представления решения [Лекарев, 2000-1].

Ошибочно противопоставление структурных методов, основывающихся на иерархической декомпозиции и пошаговом уточнении структур данных, объектно-ориентированным технологиям. В конечном счете, наилучшие результаты дает совместное применение систематических методов проектирования, хорошо зарекомендовавших себя в проектной практике, и различных парадигм программирования [Coplien, 1999], [Stroustrup, 2001].

В процессе преодоления с у щ е с т в е н н о й сложности ПО важнейшим инструментом является визуализация. Изучение структурного программирования исключительно как инструмента разработки текстов программ, построенных на базе основной «структурной триады» (линейная последовательность, ветвление и цикл), является не просто недостаточным, а, по сути дела, сводит на нет анализ преимуществ структурного подхода. Так, И.В. Вельбицкий вообще предложил существенно расширить понятие «структура программы», принимая во внимание многомерный характер этой структуры, учитывающий ассоциативные возможности мышления человека и особенности зрительного восприятия окружающей действительности [Вельбицкий, 1984, 1985]. В.Д. Паронджанов замечает, что «все больше ученых приходит к выводу, что визуальную формализацию знаний нельзя рассматривать как нечто второстепенное для научного познания, поскольку она входит в саму ткань мысленного процесса».

Поэтому основную задачу этой книги автор видит не в том, чтобы представить классическую модель структурного программирования и ее реализацию в каком-либо языке, а в том, чтобы описать эту модель с учетом развития технологий и методологий программирования и их сегодняшнего состояния. Исходя из учебного характера книги, акцент делается на структуре программных проектов не только с точки зрения организации вычислительного процесса как совокупности действий, реализующих некоторое множество алгоритмов, но и с точки зрения представления данных и управления типами данных.

Недостатком многих учебников является то, что в качестве демонстрационных примеров в них зачастую приводятся готовые проекты, а собственно процесс получения проектных решений остается за рамками повествования. В данном учебном пособии автор предпринимает попытку преодолеть эту проблему, показав студентам, что даже формально корректный код приходится преобразовывать и переписывать, руководствуясь возникающими в процессе проектирования новыми представлениями о структуре и содержании данных и управляющих конструкций.

Введение Данное учебное пособие обеспечивает курсы, читаемые студентам в начале обучения и обобщаемые наименованием «Теория и технология программирования». Основная задача этих курсов – дать студентам начальные сведения о представлении информации и обработке программ в ЭВМ, о построении алгоритмов и структуры программного кода и основных направлениях развития информационных технологий в области разработки ПО.

Изучение структурного программирования: проблемы и современное состояние Традиционно на начальном этапе основное внимание уделяется изучению двух парадигм программирования, а именно: структурному и объектно-ориентированному программированию (ООП). Несмотря на то, что основным методом разработки коммерческого ПО на сегодняшний день является объектно-ориентированное проектирование (а также во многом произошедшее из него компонентное проектирование), изучение фундаментальных основ структурного программирования и принципов разработки функционально-ориентированного (процедурного) программного обеспечения остается актуальным.

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

Если анализировать обобщающее наименование системы курсов по программированию – «Теория и технология программирования», то первая составляющая подразумевает, прежде всего, изучение моделей и методов проектирования ПО, концепций проектирования, реализуемых этими методами, изобразительных средств, синтаксиса и семантики конструкций языков программирования, которые выражают эти концепции. Каждый язык программирования выражает, по существу, определенную модель вычислительного процесса. В связи с этим студенты должны иметь представление об организации вычислительного процесса для выполнения компьютерной программы, о способах представления данных в ЭВМ и манипулирования этими данными. В качестве основного инструмента проектирования принципиально может выбираться любой язык, поддерживающий процедурную модель. В данной книге в качестве основного средства иллюстрации изучаемых концепций используется язык программирования C++.

Вторая составляющая – технология программирования – подразумевает овладение правильными приемами применения языковых конструкций на практике, формирование умения связать пространство понятий проблемной области с пространством понятий программной реализации, выработку стиля программирования. Одним из приоритетов должно становиться понимание студентами того, что программные тексты ориентированы, прежде всего, на человеческое восприятие, и, следовательно, нужно стремиться к тому, чтобы они обладали такими свойствами как наглядность, понятность, сопровождаемость, модифицируемость. Студенты должны понять смысл и преимущества метода иерархического проектирования, который, вообще говоря, не привязан к конкретной методологии программирования. Кроме того, изучение технологии программирования предполагает изучение современных средств и платформ проектирования.

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

Недостатком традиционного обучения структурному программированию является изучение его обособленно, в отрыве от других методологий проектирования и даже в противопоставлении одних другим. В этой книге делается попытка преодолеть данных учебно-методический разрыв. В этом смысле важнейшим результатом обучения должно быть понимание студентами того факта, что основные концепции проектирования, такие как абстрагирование, модульность, иерархическое проектирование и полиморфизм, не «принадлежат» какой-либо одной методологии программирования.

Организация книги В структуре данной книги автор попытался выразить идеи, сформулированные выше: студент должен получить знания не только об организации порядка вычислений в соответствии с принципами структурного программирования (язык управления), но также и о конструировании типов (декларативный язык) и визуальных моделях описания и разработки ПО (изобразительный язык).

В главе 1 представлены сведения из информатики, необходимые для успешного освоения курса программирования (понятие о кодировании и содержании, понятие о синтаксисе и семантике, системы счисления, двоичный код и основные операции над двоичными числами, элементы определения языка программирования), а также первоначальные сведения о методологии структурного программирования. Рассматривается классическая модель программы, сочетающая управляющий код (реализацию алгоритмов) и структуры данных. Анализируется смысл понятия «императивное программирование», элементы архитектуры фон Неймана, основные принципы организации процедурного кода.

В главе 2 дается определение и анализ понятия типа данных.

Представлена система типов, поддерживаемая языком C++. Рассмотрены стандартные скалярные типы данных и составные типы, конструируемые пользователем.

В главе 3 вводится понятие алгоритма, анализируются основные механизмы реализации управляющих конструкций в языках высокого уровня, в частности структурной триады (последовательные вычисления, ветвления и циклы) и причины отклонения от ортодоксальной структурной модели в различных языках программирования. В связи с организацией процедурной программы анализируются: стратегия нисходящего проектирования, задачи функционально-иерархической декомпозиции, организация вызова функций и возврата управления, понятие об аргументах и параметрах функций. Подробно рассматриваются механизмы связывания аргументов и параметров при вызове функций (по значению, с косвенной адресацией, по ссылке, через общий интерфейс). Представлены особые варианты управления вызовами функций (функции обратного вызова и рекурсивные функции). В качестве примеров рекурсивного алгоритма рассматривается важный алгоритм быстрой сортировки и его преобразование к нерекурсивной форме.

В главе 4 основной акцент делается на представлении данных, управлении данными и модульной организации проектов. Анализируются задачи, решаемые программистом при переходе от модели предметной области к программной модели, и основной инструмент построения пользовательских типов в структурном программировании – структурные типы. Приводится анализ методов проектирования, нацеленных на реализацию модели процедурно-параметрического полиморфизма. В связи с этим показано, что полиморфизм как концепция проектирования не является исключительной особенностью ООП.

В главе 5 на примерах управления матричными объектами, списками, деревьями и hash-таблицами анализируются проблемы управления связанными структурами данных и принципы организации кода, использующего такие структуры. В качестве примеров приведены алгоритмы двоичного поиска, поиска в hash-таблицах, распознавания зарезервированных идентификаторов из некоторого множества.

В главе 6 на примере задачи о целочисленном возведении в степень обсуждаются проблемы чисто императивной модели управления действиями и данными, обосновывается необходимость тщательного продумывания функциональной структуры проекта. Анализируются проблемы в связи с обработкой ошибок, возникающие в ходе выполнения вычислений. Предлагается гибридное решение задачи с использованием объектно-ориентированных элементов решения. Таким образом, студентам представляется введение в мультипарадигменное программирование, позволяющее использовать достоинства обеих обозреваемых методологий.

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

«Классические» визуальные формализмы, упомянутые в гл. 3 (схемы алгоритмов и программ, диаграммы Нэсси-Шнейдермана, Р-технология и др.), дополняются относительно новыми разработками, в числе которых:

визуальный формализм на базе L-сети [Лекарев, 1997], визуальный язык ДРАКОН [Паронджанов, 1999], SWITCH-технология [Шалыто, 1998].

В главе 8 рассматриваются проектные проблемы, возникающие при решении задач обработки текстов. Студенты получают представление о задачах лексического и синтаксического анализа и варианта решения этих задач на основе совместного использования структурного программирования на языке C++ и визуального формализма для разработки ПО на базе L-сети [Лекарев, 1997].

Исходные тексты программ Исходные тексты примеров программ предоставляются читателю на прилагаемом к книге компакт-диске. Описание содержимого компакт диска см. в приложении 2.

Автор специально обращает внимание читателей на то, что основное назначение данных примеров заключается в иллюстрации положений книги. Поэтому их не следует рассматривать как законченные программные проекты. В некотором смысле, данные проекты являются черновыми.

Однако, по справедливому замечанию М.Ф. Лекарева, «термин черновые записи не означает неаккуратные записи!» [Лекарев, 2000-3].

Использование книги в учебном процессе Данная книга совместно с книгами [Лекарев, Давыдов, 2002], [Давыдов, 2003], [Pychkine, 2003], [Pychkine, 2004], [Давыдов, 2005], [Пышкин, 2005], написанных преподавателями кафедры автоматики и вычислительной техники (АиВТ) факультета технической кибернетики Санкт-Петербургского государственного политехнического университета, является частью литературного обеспечения курсов «Программирование на языке высокого уровня», «Основы программирования и алгоритмизации», «Технология программирования» и ряда смежных курсов, читаемых студентам кафедры АиВТ.

Книга не является учебником по программированию на языке C++, хотя и содержит некоторый учебный материал в связи с языком C++. Задачи обучения языку C++ в достаточной степени решаются во многих современных учебниках, активно используемых в учебном процессе (например, [Eckel, 2000], [Stroustrup, 2000], [Павловская, 2001], [Давыдов, 2003] и др.).

Действительно, учебные пособия, разрабатываемые коллегами, преподающими на одном и том же факультете (и иногда – одним и тем же студентам), должны в идеале не дублировать, а скорее дополнять друг друга, чтобы студенты получили наиболее полную информацию, отражающую как разные стороны искусства программирования, так и разные подходы к обучению этому искусству. Автор надеется, что представляемое учебное пособие хотя бы отчасти реализует этот тезис.

Глава 1. Основание программирования В данной главе рассматриваются фундаментальные концепции, лежащие в основе структурного программирования, а также основные понятия процедурного программирования, для которого структурно императивная модель управления действиями и данными является концептуальной базой.

1.1. Необходимые предпосылки Приступая к изучению программирования как академической дисциплины и как отрасли научного знания, необходимо рассмотреть ряд важных понятий и определений, используемых в информатике. Наличие данного раздела позволяет студентам ощутить тесную взаимосвязь таких дисциплин как теория информации и теория кодирования, теория и практика синтаксического анализа и компиляции, теория чисел и схемотехника, архитектура вычислительных систем и др.

Кодирование и содержание Термин «информация» является сильно нагруженным, достаточно заглянуть в любой толковый словарь. Даже применительно к задачам технической науки можно констатировать разнообразие уровней абстрагирования при определении термина «информация». Н. Винер, рассматривая подобие процессов управления и связи в машинах, живых организмах и обществах, определял эти процессы как передачу, хранение и переработку информации, т.е. различных сигналов, сообщений, сведений [Wiener, 1961]. Любой сигнал рассматривается как некоторый выбор между двумя и более значениями, наделенными известными вероятностями. Винер заложил основы селективной концепции информации, на которой базируется статистическая теория информации.

А.Н. Колгоморов сформулировал и развил разделы теории информации, связанные с оценкой сложности информации, предложив механизмы оценки количества информации и способы измерения количества информации при помощи сравнения любой информации с информацией в виде некоторого числа двоичных знаков. А.Н. Колмогоров ввел определение сложности объекта как минимальной длины описания объекта в некотором коде, заложил основы математической теории алгоритмов [Колмогоров, 1987], [Ming, Vitanyi, 1993].

В современном обществе (иногда называемом постиндустриальным) информация отражает другую информацию, при этом не обязательна фиксация информации в материальной форме, информация приобретает стоимость и становится объектом рынка. Эти тенденции проявляются в появлении различных форм электронных документов, развитии информационных систем электронного документооборота, систем анализа и управления потоками информации [Пышкин, 2004].

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

Информация, воплощенная и зафиксированная в некоторой материальной форме, называется сообщением. Минимальный элемент сообщения – символ. Множество допустимых символов – алфавит. При этом понятие символа следует трактовать расширенно. В бытовом общеупотребительном смысле под термином символ мы часто понимаем букву, знак, элементарную единицу текста. С точки зрения теории информации символ как минимальный элемент сообщения может быть довольно сложной абстракцией. Например, в устной французской речи роль подобного минимального элемента устного сообщения выполняет ритмическая группа, которая может соответствовать одному слову языка, а может объединять несколько слов. На письме грамматика языка определяется как набор правил корректных сочетаний слов языка. Таким образом, в этом случае символом является отдельное слово.

Алфавит – базовая характеристика любого кода. Без знания алфавита невозможно расшифровать код и «вычислить» его содержание. Однако знания алфавита недостаточно, поскольку код сам по себе не имеет смысла (пример: древние языки, нерасшифрованные нотации, например, знаменная нотация церковного пения до 15 века). Причина заключатся в отсутствии правила расшифровки (правила декодирования). Ошибка в декодировании приводит к искажению смысла (рис. 1.1).

Информация Правила Кодирование кодирования Алфавит Код Смысл одинаков?

Правила Декодирование декодирования Информация Рис. 1.1. Кодирование и декодирование Информация, с которой имеют дело вычислительные машины, обычно обобщенно называется термином «данные».

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

Систему счисления определяет алфавит символов, используемых при записи чисел. Системы счисления бывают позиционные и непозиционные. В непозиционной системе счисление значение символа не зависит от его положения в числе. На объявлении об охраняющей двор злой собаке (см. рис. 1.2) использована непозиционная система счисления.

Почтальоны Воришки Гости Молочники Рис. 1.2. «Осторожно, злая собака!»

Непозиционной является и используемая до сих пор римская система счисления, в которой для записи чисел используется 7 латинских букв: I, V, X, L, C, D, M (соответственно для обозначения привычных для нас чисел 1, 5, 10, 50, 100, 500, 1000). Ниже приведены некоторые числа, записанные в римской нотации.

3 III 4 IV 8 VIII 19 XIX 256 CCLVI 2005 MMV Ч. Петцольд замечает, что, долгое время римские числа считались весьма удобными для выполнения операций сложения и вычитания, однако умножение и деление римских чисел является весьма нетривиальной задачей [Petzold, 1999].

В позиционной системе счисления (например, в десятичной) вес цифры в числе зависит от ее положения. Количество цифр, используемых при записи чисел в некоторой системе счисления (число символов в алфавите) называется основанием системы счисления.

Запись целого числа в позиционной системе счисления Пусть q – основание системы счисления.

В десятичной системе счисления – 10 цифр: 0,1,2,3,4,5,6,7,8,9 ( q 10 ).

В сокращенной форме записи целое десятичное число записывается как набор составляющих его цифр: Aq a n 1an 2...a2 a1a0, где n – число разрядов. Это представление можно расшифровывать следующим образом:

10 n 1 a n... 10 2 a 2 10a A10 a Такая запись иногда называется развернутой записью числа.

Например, для числа 319 получим следующую развернутую запись:

319 100 3 10 1 В некотором смысле можно сказать, что естественность десятичной системы для человека обусловлена физиологическими особенностями (у человека – 10 пальцев). Остроумное наблюдение Ч. Петцольда за миром мультипликационных героев Диснея позволяет ему заключить, что для них наиболее естественной формой представления числовой информации была бы, вероятнее всего, система счисления с основанием 8 (восьмеричная), ведь у «мультяшек» всего по 4 пальца на каждой руке. Если же на секунду вообразить образованного краба, то с его «раздвоенными» клешнями ему бы, безусловно, подошла система счисления с основанием 4 (четверичная) [Petzold, 1999].

Для произвольной системы счисления представление целого числа в развернутой форме записи будет иметь вид:

n q n 1an... q 2 a 2 q 1 a1 q 0 a0 q i ai Aq i Поскольку система счисления определяет только форму представления числа, а не его значение (смысл), то всегда можно перевести число из одной системы счисления в другую (то есть из одной формы представления в другую).

Проще всего перевести в десятичную систему счисления, например, для двоичного числа 1101 получим:

2 3 1 2 2 1 21 0 2 0 1 Теперь рассмотрим, как осуществить обратное преобразование (в данном случае – из десятичной системы в двоичную).

Для этого нужно внимательно посмотреть на развернутую запись числа. Как выделить цифры числа, исходя из его значения? Нетрудно заметить, что для этого нужно делить число на основание системы счисления. После первого целочисленного деления в остатке получаем значение младшего разряда. Частное от деления снова делим на основание, опять выделяя младший разряд, и так продолжаем до тех пор, пока нечего будет делить. Например:

31, остаток: 9 (разряд единиц) 3, остаток: 1 (разряд десятков) 0, остаток: 3 (разряд сотен) Аналогично, чтобы перевести десятичное число в другую систему счисления, нужно делить его на основание другой системы, например, для числа 13, переводимого в двоичную систему счисления, получим:

6, остаток: 1 (самый младший разряд) 3, остаток: 1, остаток: 0, остаток: 1 (самый старший разряд) Последовательность остатков от деления и определяет искомый результат.

Представление и преобразование чисел с дробной частью Развернутую форму записи чисел нетрудно обобщить на случай чисел, имеющих дробную часть:

n qn... q1 a1 q 0 a0 1 m q i ai Aq an q a... q am 1 i m где n – число разрядов в целой части, а m – число разрядов в дробной части. В сокращенной форме записи это эквивалентно:

Aq an 1an 2...a2 a1a0.a 1a 2...a m Поскольку вес разрядов дробной части соответствует долям единицы, то для преобразования дробной части из одной системы счисления в другую необходимо умножать дробную часть на основание целевой системы счисления, выделяя целые части произведений (это и будут цифры представления дробной части). Для получающихся при умножении дробных частей процесс умножения повторяется до тех пор, пока не получится нулевая дробная часть (это означает, что нам удалось найти точное представление числа в заданной системе счисления) или пока не будут исчерпаны ячейки памяти для хранения результата (в этом случае говорят о приближенном результате преобразования).

Рассмотрим пример. Пусть необходимо перевести в двоичную систему счисления десятичное число 13.4375. Перевод целой части мы рассмотрели выше. Теперь займемся переводом дробной части. Сначала умножаем дробную часть на 2:

0.4375 2 0. Целая часть произведения равна нулю, следовательно, разряд двоичного числа с весом 2 1 0.5 равен нулю. Дробную часть снова умножаем на 2:

0.875 2 1 0. Целая часть произведения (единица) – это разряд двоичного числа с весом 2 2 0.25. Дробную часть снова умножаем на 2:

0.75 2 1 0. Целая часть произведения (единица) – это разряд двоичного числа с весом 2 3 0.125. Дробную часть снова умножаем на 2:

0.5 2 Целая часть произведения (единица) – это разряд двоичного числа с весом 2 4 0.0625. Дробной части нет, следовательно, преобразование закончено, окончательное представление десятичного числа 13.6875 в двоичной системе счисления имеет вид:

1101. Еще раз подчеркнем важную особенность преобразования дробной части: точное преобразование возможно не всегда. Попробуйте, например, преобразовать в двоичную систему счисления десятичное число 0.4.

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

Структура двоичного кода, используемого при представлении данных в ЭВМ, обсуждается далее в этом разделе и в разд. 2.1.

Системы счисления, используемые в информатике и вычислительной технике Помимо двоичной системы счисления, наибольшее распространение в различных областях вычислительной техники получили системы счисления с основаниями 8 (восьмеричная), 16 (шестнадцатеричная) и нередко используемая в схемотехнике двоично-десятичная система счисления (в двоичном коде раздельно представляется каждая десятичная цифра). Для представления цифр в системах счисления с основанием больше десяти обычно используют строчные или прописные латинские буквы в порядке их следования в латинском алфавите. Шестнадцатеричные цифры, соответствующие десятичным значениям от 10 до 15, приведены в табл. 1.1.

Таблица 1.1. Шестнадцатеричные цифры Двоичный код Десятичный код Шестнадцатеричная цифра 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 10 A 1011 11 B 1100 12 C 1101 13 D 1110 14 E 1111 15 F Преобразование из двоичной системы счисления в системы счисления с основанием, кратным степеням двойки (в частности, восьмеричную и шестнадцатеричную системы), и обратно, осуществляется очень просто.

Каждая цифра системы счисления с основанием 2 r представляется точно r разрядами соответствующего двоичного представления. Так, каждая восьмеричная цифра соответствует двоичной триаде (трем разрядам), а каждая шестнадцатеричная цифра – двоичной тетраде (четырем разрядам).

Если число разрядов двоичного представления не кратно числу разрядов восьмеричного (шестнадцатеричного и т.д.) представления, то двоичное число дополняется необходимым числом старших разрядов в целой части и младших разрядов в дробной части. Рассмотрим пример преобразования двоичного числа 1101.0111 в восьмеричную систему счисления. Двигаясь от десятичной точки влево, составляем две триады, дополняя двумя нулевыми старшими разрядами. Двигаясь от десятичной точки вправо, также выделяем две триады, на этот раз дополняя нулями разряды справа. Условно выделяя триады запятыми, получим 001,101.011,100, что соответствует восьмеричной записи 15.34.

Преобразование в шестнадцатеричную систему в данном случае не требует добавления нулей, поскольку и так имеется ровно две тетрады, соответствующее шестнадцатеричное представление имеет вид D.7.

Понятие сложности кода Поскольку любая алфавитная (буквенно-цифровая) информация может быть закодирована в двоичной форме, то подобным образом с использованием двоичных сигналов можно закодировать условия и решения для любых задач. Говоря о причинах использования двоичного кода для представления информации в ЭВМ, обычно выделяют уровень физической реализации способов представления и хранения информации в ЭВМ.

Подробности представления информации в ЭВМ на физическом уровне студенты изучают в курсах электроники, схемотехники и архитектуры ЭВМ.

Поскольку для большинства элементов «электронной начинки» ЭВМ характерно два устойчивых состояния, использование двоичного кода в качестве основного способа представления обрабатываемой ЭВМ информации выглядит вполне естественным. Однако на заре развития средств вычислительной техники, архитектура и особенности организации вычислительных устройств была предметом исследований. Поэтому полезно рассмотреть причины выбора двоичной системы, исходя из уровня характеристик самого кода, а не только из соображений электроники.

Для этого мы воспользуемся предложеным А.Н. Колмогоровым способом оценки количества информации при помощи сравнения любой информации с информацией в виде некоторого числа двоичных знаков (битов) [Колмогоров, 1987]. По Колмогорову, сложность – это минимальное число (двоичных) знаков, содержащих всю информацию о задаваемом объекте, достаточную для декодирования. Исходя из предположения, что чем больше основание системы счисления, тем больше двоичных знаков требуется для представления одной цифры, можно записать сложность представления цифры следующим образом:

kq, где Ldigit k – технологический коэффициент, а q– основание системы счисления.

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

kqn, где LA n – число разрядов в представлении A. Тогда для системы счисления с основанием q имеем:

LAq kq log q A Рассмотрим отношение сложности представления числа в системе счисления с основанием q к сложности представления этого же числа в двоичной системе.

L Aq kq log q A q log 2 A q Lr L A2 2k log 2 A 2 log 2 A log 2 q 2 log 2 q Получили относительную сложность как функцию основания системы счисления. Некоторые значения функции Lr (q) приводятся в табл. 1.2.

Таблица 1.2. Относительная сложность q Lr (q) 2 e 0. 3 0. 4 5 1. 6 1. 7 1. 8 1. Если на мгновение абстрагироваться от дискретного характера q, видно, что функция Lr (q) имеет минимум при значении аргумента, равном e. Таким образом, выбирать приходится между ближайшими целыми значениями 2 и 3. Значение функции Lr (3) ближе к оптимуму, но здесь и вступают в силу схемотехнические соображения: необходимость различать три сигнала приводит к худшим показателямс точки зрения помехозащищенности. Следовательно, обеспечение адекватного двоичному коду уровня надежности обернется либо увеличением сложности системы, либо ухудшением энергетических показателей (например, придется передавать сигналы большей амплитуды).

Данный комплекс причин наряду с оценочными характеристиками, вытекающими из сопоставления предполагаемой сложности реализаций и обусловил выбор, сделанный в пользу использования в ЭВМ двоичной системы счисления.

Цифровые вычислительные машины Большинство используемых в настоящее время вычислительных машин являются цифровыми. Это означает, что для представления данных используются дискретные величины (числа). Для наглядного представления вычислительные машины обычно изображаются в виде схем, состоящих из блоков и связей между ними (см. разд. 1.3). С каждым блоком связаны входные данные, выходные данные и выполняемая блоком функция. Таким образом, блоки являются преобразователями информации.


Данные представлены сигналами на входах и выходах. Сигнал – это изменение некоторой физической величины во времени, обеспечивающее передачу сообщения. Сообщение – это совокупность символов для представления информации, смысл которых устанавливается людьми и должен быть выучен. Отсюда следует, что ошибки при декодировании информации, обрабатываемой вычислительной системой, связаны, прежде всего, с ошибками проектировщика (то есть человека).

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

В настоящее время подавляющее большинство преобразователей информации представляют собой электронные схемы, содержащие соединенные определенным образом между собой электронные ключи – вентили. Эти электронные схемы реализуются с использованием технологий современной микроэлектроники в виде интегральных схем (ИС), которые могут содержать от нескольких единиц до нескольких миллионов вентилей.

В виде ИС выпускаются микропроцессоры, микроконтроллеры, блоки памяти, контроллеры различных устройств и др. Для работы ИС к ней подводится напряжение питания. При этом сигналы в ИС представлены уровнем напряжения. Исходя из двоичной природы представления информации в большинстве компьютеров, для представления сигналов приняты всего два непересекающихся диапазона уровней напряжения. При напряжении питания 5 В это:

диапазон (0..0,4) В, соответствующий логическому значению сигнала «0»;

диапазон (2,4..5) В, соответствующий значению сигнала «1».

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

Операции над двоичными числами Несмотря на то, что человеку привычно иметь дело с десятичной арифметикой, можно сказать, что операции над двоичными числами не слишком отличаются от операций над десятичными числами (а в действительности – даже проще, так как двоичный алфавит состоит всего из двух цифр).

Биты, байты, слова, слова, слова… Вообще говоря, при обработке двоичных данных манипулируют не отдельными битами, а последовательностями битов. Стандартная длина такой последовательности битов – 8. В вычислительной технике восьмерка двоичных разрядов называется байтом (этот термин используется примерно с середины 50-х годов XX века). При записи байта принято изображать все восемь битов, даже если старшие биты нулевые, например, 00010011, а не 10011.

Почему байт содержит именно 8 битов? Несмотря на то, что ряд причин принятия такого решения имеет скорее исторический характер, Ч. Петцольд приводит и некоторые разумные технические объяснения.

Поскольку байт позволяет представить 256 различных комбинаций, то его удобно использовать для представления большинства символов, используемых в разных языках (за исключением китайских, японских и корейских иероглифов), что и было реализовано в 1967 году в виде стандарта ASCII. Байт также вполне подходит для представления оттенков серого цвета на черно-белых фотографиях, поскольку человеческий глаз способен различать в среднем около 256 оттенков [Petzold, 1999].

В тех случаях, когда для представления информации возможностей, обеспечиваемых одним байтом, недостаточно, используют двухбайтовые последовательности (часто называемые словами). Например, формат Unicode, разработка которого началась в 1988 году, обеспечивает двухбайтовые коды символов (65536 комбинаций). Это позволяет представить все символы, используемые в настоящее время в разных языках, даже с некоторым запасом.

Для обеспечения эффективной обработки данных (например, при представлении чисел с плавающей точкой) используют четырехбайтовые (32 разрядные) и восьмибайтовые (64-разрябные) слова.

В дальнейшем мы будем записывать двоичные коды именно в виде последовательности байтов.

Сложение двоичных чисел Правила поразрядного сложения двоичных чисел могут быть сведены в несложную таблицу (см. табл. 1.3), определяющую все четыре комбинации битов слагаемых:

Таблица 1.3. Формирование бита переноса бит суммы бит бит первого бит второго переноса слагаемого слагаемого 0 0 1 0 1 1 1 1 0 С учетом того обстоятельства, что бит переноса должен учитываться при операциях над последующими разрядами при просмотре их справа налево, получаем таблицу, содержащую 8 комбинаций (табл. 1.4):

Таблица 1.4. Двоичное сложение бит суммы бит бит переноса бит первого бит второго переноса на на входе слагаемого слагаемого выходе 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 Рассмотрим пример сложения десятичных чисел 123 и 67, записанных в двоичном коде (см. рис. 1.3).

123 + + 67 Рис. 1.3. Сложение в двоичном коде Как явствует из приведенного рисунка, в результате последовательного сложения всех разрядов формируется бит переноса, так что для записи результирующего значения нужно все 8 двоичных разрядов (результат уместился в пределах одного байта). Однако возможны комбинации данных, когда для представления результата имеющихся разрядов недостаточно. Таким образом, наши возможности ограничены заданной разрядностью кода. Ситуация, возникающая при получении кода, который не может быть размещен в пределах ограниченной разрядности, называется переполнением разрядной сетки.

Вычитание двоичных чисел. Особая роль сложения Задача вычитания осложняется тем обстоятельством, что вместо простого в реализации действия переноса, при вычитании возможен так называемый «заем» более старшего разряда (рис. 1.4).

..

_ Рис. 1.4. Вычитание целых чисел Оказывается, однако, что, осуществив несложные арифметические преобразования исходного выражения, можно обойтись без использования занимаемого разряда.

Некоторое выражение a b можно преобразовать к эквивалентной форме a b 1000 1000, которое, в свою очередь, преобразуется к виду a b 999 1 1000. Осуществляя перегруппировку операндов, получаем эквивалентное представление a (999 b) 1 1000. Нетрудно заметить, что при выполнении действия в скобках не нужно занимать разряды. После выполнения действия в скобках останется сложить полученный результат с a, добавить 1 и вычесть 1000. Для нашего примера ситуация выглядит так, как показано на рис. 1.5,а.

1111111 _999 _ _ 1000011 0111100 932 0111100 +123 + + 1111011 10110111 1055 +1 + + 1 _ 1056 _ _ 10000000 00111000 (а) Вычитание в (б) Вычитание в двоичном коде десятичном коде Рис. 1.5. Вычитание чисел в десятичном и двоичном коде В двоичном коде дело обстоит еще проще (см. рис.1.5,б). Обратим внимание на то, что, в действительности, результат первого действия может быть получен простым инвертированием всех разрядов вычитаемого. Таким образом, операция вычитания двоичных чисел, фактически, сводится к их сложению.

Положительные и отрицательные числа. Понятие о дополнительном коде Изложенный подход хорошо работает, но что, если нам нужно вычесть 123 из 67? Как обеспечить адекватную схему вычислений, позволяющую оперировать с отрицательными числами?

Предположим, что мы ограничены возможностями 1 байта. Один бит нужно занять для представления знака числа. В большинстве архитектур знаковым разрядом является самый старший (самый левый) разряд, причем означает положительное число, а 1 – отрицательное. Собственно для значащих цифр остается 7 разрядов.

8 разрядов позволяет представить 256 комбинаций. Половина комбинаций (от 0000 0000 до 0111 1111) соответствуют десятичным числам от 0 до 127. Остальная половина (от 1000 0000 до 1111 1111) соответствует отрицательным кодам. В табл. 1.5 приведены двоичные коды и соответствующие им десятичные числа.

Таблица 1.5. Дополнительный код Двоичный код (1 байт) Десятичное число 1000 0000 - 1000 0001 - 1000 0010 - 1000 0011 - … … 1111 1101 - 1111 1110 - 1111 1111 - 0000 0000 0000 0001 0000 0010 … … 0111 1101 0111 1110 0111 1111 Нетрудно заметить, что отрицательное число получается вычитанием положительного числа с тем же абсолютным значением из максимального кода 1111 1111 (то есть инверсией) с последующим добавлением единицы (рис. 1.6). Код, представленный в таблице, называется дополнительным, или комплементарным кодом (two’s complement code).

Дополнительный код позволяет свести вычитание к сложению (рис. 1.7), при этом сложение положительных и отрицательных чисел осуществляется просто с использованием правил сложения с переносом, специальный анализ знакового разряда не требуется.

При выполнении вычислений в рамках ограничений, накладываемых разрядностью кода, возможно возникновение ситуаций переполнения сверху (overflow), когда результат превышает максимальный положительный код (в нашем примере это код числа 127), и переполнения снизу (underflow), когда результат оказывается меньше минимального отрицательного кода (для числа -128).

_ 01111011 + _ 10000101 Рис. 1.6. Комплементарный код 01000011 _ + 10000101 _ 11001000 Рис. 1.7. Вычитание в комплементарном коде Основные элементы языка программирования В данном разделе мы рассмотрим элементы, позволяющие формально определить любой язык, при этом для иллюстрации используемых понятий мы будем использовать определение языка C++.

Алфавит языка Алфавит языка – это набор символов, используемых для записи программ. Эти символы обычно называют литерами. Из литер конструируются лексемы (tokens) – относительно обособленные элементы синтаксических конструкций языка. Наиболее распространены пять основных категорий лексем:

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

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

литералы: целочисленные, с плавающей точкой, символьные, строковые – для записи констант;

знаки операций (арифметических, логических, операций отношения и др.) – для записи элементарных действий над данными;


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

Например, в языке C++ разрешается использовать следующие символы для образования лексем:

abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ +-*/= () {} [] '"!#~%^&_;

:,.?\| Символы пробелов и табуляции При генерации лексем компилятор выбирает наиболее длинную строчку, которая составляет лексему. Подробнее задача лексического анализа рассматривается в гл. 8.

Синтаксис и семантика Прежде чем программа, написанная на языке C++, будет исполнена, необходимо осуществить ее перевод в машинный код – то есть на язык, естественный для данной вычислительной системы. Этот перевод называется трансляцией программы. Смысл программы в результате трансляции не должен измениться, должна измениться только форма ее представления.

Обеспечивается это тем, что правила составления предложений языка строго регламентированы. Этот регламент и называется синтаксисом. Итак, синтаксис – это правила построения языка и его конструкций.

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

В естественных языках синтаксически корректное предложение в некоторых случаях может трактоваться по-разному (иметь различную семантику) в зависимости от контекста (если речь идет об идиомах) или порядка применения правил языка. М.Ф. Лекарев приводит следующий выразительный пример из русского языка. В предложении «он встретил ее на лугу с цветами», на первый взгляд, речь может идти о галантном кавалере, не забывшем принести букет цветов на встречу с любимой. «Однако правила русского языка допускают и иное толкование», - замечает автор – «с цветами в руках могла быть она. Наконец, цветами мог быть усеян цветущий луг»

[Лекарев, 2000-1]. Несмотря на то, что правила языка обычно содержат рекомендации для подобных неоднозначностей (в данном случае, руководствуясь принципом применения правил к ближайшему определяемому слову, следует, вероятно, считать, что все-таки романтика ситуации ограничивалась цветением луга! – Е.П.), полностью проблема не снимается. Синтаксис формальных языков специально разрабатывается таким образом, чтобы исключить возможность неоднозначного толкования предложений языка.

Программист должен Программа на языке руководствоваться программирования Правила синтаксиса Должны иметь один и Компилятор использует Компилятор тот же смысл Программа на машинном языке (объектный код) Рис. 1.8. Синтаксически-ориентированная трансляция «Вычисление» единственно возможного смысла программного кода на основании анализа синтаксиса называют синтаксически ориентированной трансляцией (рис. 1.8). Обратите внимание на то, что соблюдение синтаксиса не влечет за собой автоматически корректность семантики.

Транслятор способен проверить только корректность синтаксиса, обеспечение корректности семантики – задача программиста (рис. 1.9).

Семантика, подразумеваемая программистом Текст, выражающий семантику Правила Семантика требует синтаксиса внимания Позволяет проверить ПРОГРАММИСТА синтаксические ошибки при записи текста Компилятор Объектный код:

семантика, вычисленная транслятором Рис. 1.9. Синтаксис и семантика Для описания синтаксиса используют различные способы. Наиболее распространенными из них являются два способа: металингвистические формулы Бэкуса-Наура (текстовая форма описания синтаксиса) и синтаксические диаграммы, впервые предложенные Н. Виртом (текстографическая форма описания синтаксиса, см. рис. 1.10).

Аналогичные правила в форме Бэкуса-Наура будут выглядеть следующим образом:

десятичная-цифра ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | идентификатор ::= { латинская-буква} | _ } [ латинская-буква | десятичная-цифра | _ ]...

Описание семантики является более сложной проблемой, чем описание синтаксиса. Читатель, интересующийся методами описания семантики, может обратиться, например, к [Sebesta, 2002].

Начало диаграммы Конец диаграммы Нотационная константа Соединители Нотационная переменная Пример синтаксической диаграммы без использования нотационных переменных десятичная-цифра ::= 1 2 3 4 5 6 7 8 Пример синтаксической диаграммы с использованием нотационных переменных идентификатор ::= латинская буква латинская буква _ десятичная цифра _ Рис. 1.10. Синтаксические диаграммы Идентификаторы Идентификатор – одна из основных синтаксических конструкций, используемых в программах. Любое имя, используемое в программе, должно быть идентификатором. Идентификатор может состоять из одного или более символов. Первым символом должна быть латинская буква или знак подчеркивания (см. рис. 1.10).

Длина идентификатора в C++ может быть любой, при этом число значащих символов может отличаться в разных реализациях языка.

Например, стандарт ANSI C позволяет различать идентификаторы по первым 6 символам (для глобальных имен) и 31 символу (для локальных имен). Компилятор Microsoft С, интегрированный в платформу Microsoft.NET 2003, допускает различение идентификаторов C по первым 247 символам (при этом не делается различия между локальными и глобальными именами). Компилятор Microsoft Visual C++ различает идентификаторы до 2048 символов.

Ряд идентификаторов явно зарезервирован для нужд языка. Это – ключевые (служебные) слова языка, о которых мы будем говорить далее.

Относительно некоторых из идентификаторов в С++ имеются определенные соглашения. Так, идентификаторы, начинающиеся с двойного подчеркивания, или с подчеркивания, вслед за которым следует прописная буква, считаются зарезервированными для использования системой. В некоторых средах разработки существуют свои стандарты, которым рекомендуется следовать, если предполагается совместное использование программного кода коллективами разработчиков.

Ключевые слова Ключевые, или служебные, слова – это идентификаторы, имеющие предопределенный смысл в языке. В языке C++ служебные слова зарезервированы. Это означает, что их нельзя переопределить или использовать в контексте, отличном от предписанного правилами языка.

Служебные слова в языках C/C++ набираются в нижнем регистре, таким образом, идентификаторы IF, FOR, WHILE являются корректными незарезервированными идентификаторами. Однако из этого н е с л е д у е т, что их нужно использовать для именования пользовательских объектов.

Список служебных слов может несколько отличаться в разных системах C++, однако в большинстве случаев можно руководствоваться нижеследующим стандартным списком.

Часть ключевых слов унаследована от языка C:

asm Вставка ассемблерного кода в код на C auto Спецификатор класса памяти «автоматическая переменная»

break Прекращение итераций цикла, выход из мультиветвления case Ветвь мультиветвления char Спецификатор типа «символьный»

continue Переход к очередной итерации цикла default Ветвь мультиветвления «по умолчанию»

do Заголовок цикла с постусловием do...while double Спецификатор типа «с плавающей точкой двойной точности»

else Ветвь «иначе» в инструкции if enum Спецификатор перечисляемого типа extern Спецификатор доступа к внешним объектам float Спецификатор типа «с плавающей точкой»

for Заголовок цикла с предусловием for goto Безусловный переход на метку if Условная инструкция int Спецификатор типа «стандартное целое» (2 или 4 байта) long Спецификатор типа «длинное целое» (4 байта) main Зарезервированное имя функции-точки входа register Спецификатор класса памяти «регистровая переменная»

return Возврат управления из функции short Описатель типа «короткое целое» (2 байта) signed Спецификатор типа «целое со знаком»

sizeof Операция определения размера программного объекта static Спецификатор класса памяти «статический»

struct Спецификатор структурного типа switch Инструкция «мульиветвление»

typedef Спецификатор пользовательского типа union Спецификатор типа-объединения unsigned Описатель «целое без знака»

while Заголовок цикла с предусловием while void Спецификатор типа void Остальные слова являются специфичными для C++:

bool Спецификатор типа «булевский»

catch Заголовок обработчика исключения class Спецификатор типа «класс»

const_cast Преобразование типа для избавления от константности delete Операция удаления объекта из динамической памяти dynamic_cast Преобразование типа времени выполнения explicit Спецификатор конструктора «без неявного преобразования»

false Зарезервированная константа булевского типа «ложь»

friend Спецификатор дружественного доступа inline Спецификатор подставляемой (встроенной) функции mutable Спецификатор «никогда не является константой»

namespace Спецификатор простраства имен new Операция размещения объекта в динамической памяти operator Спецификатор перегружаемой операции private Спецификатор «закрытый доступ к членам класса»

protected Спецификатор «защищенный доступ к членам класса»

public Спецификатор «открытый доступ к членам класса»

reinterpret_cast Спецификатор «произвольное преобразование типа»

static_cast Спецификатор «преобразование времени компиляции»

template Спецификатор «шаблонное объявление»

this Зарезервированный константный указатель на объект throw Инструкция генерации исключения true Зарезервированная константа булевского типа «истина»

try Спецификатор блока «возможно возникновение исключения»

typeid Определение информации о типе во время выполнения typename Спецификатор для разрешения неоднозначностей в шаблонах using Спецификатор для использования пространств имен virtual Спецификатор «виртуальная функция»

volatile Спецификатор «изменяемый извне (фоновым процессом)»

wchar_t Спецификатор типа «символьный в формате Unicode»

Ряд служебных слов (auto, goto, register, signed) по разным причинам довольно редко встречаются в современной практике программирования на C++, область употребления некоторых служебных слов крайне ограничена (continue, mutable, volatile, явные приведения типов).

Запись текстов программ В разных языках могут устанавливаться различные правила форматирования текстов. Формат может быть жестко зафиксирован (когда взаимное расположение конструкций языка жестко регламентировано), быть полуфиксированным (как во многих ассемблерных языках) или свободным.

Большинство современных универсальных языков программирования (в том числе C++) поддерживают свободный формат записи программ. Это означает, что синтаксические конструкции могут начинаться с любой позиции строки текста программы. Одна инструкция может располагаться в нескольких строках программы. Несколько инструкций могут располагаться в одной строке. Между отдельными лексемами может быть помещен один или более пробелов или других символов пробельной группы (табуляции, символы перевода строки).

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

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

Несмотря на то, что самим языком правила форматирования исходного текста программы не обязательно жестко зафиксированы, форматирование исходного текста в соответствии с его логической структурой существенно облегчает разработку и восприятие текстов программ. По сути дела, форматирование исходного текста в соответствии с его логической структурой – не что иное, как один из визуальных формализмов, используемых уже в течение десятилетий [Straker, 1992]. При этом, хотя полезность форматирования «настолько очевидна, что не оспаривается никем [...], конкретные правила форматирования были и остаются предметом дискуссии» [Лекарев, 1997]. Тем не менее, можно перечислить приемы, которые чаще всего применяются, проверены практикой и поэтому могут быть рекомендованы студентам:

Вертикальное форматирование: действия, составляющие один логический блок, комментарии, сопровождающие текст, символы, ограничивающие обособленные блоки (например, фигурные скобки в языке C++, пары ключевых слов begin, end в языке Pascal) записываются друг под другом с выравниванием по левому краю.

Горизонтальное форматирование: при оформлении перехода к вложенному логическому блоку (в ветвлениях и циклах) используются отступы, или табуляции.

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

Преимущественно текст организуется таким образом, что в отдельной строке помещается одна высокоуровневая инструкция, за естественным исключением тех случаев, когда группа инструкций образует единое целое в синтаксическом (например, оформление ветвлений или заголовков циклов) или в математическом смысле (например, одновременные присваивания).

Большинство опытных программистов согласятся с тем, что в грамотно отформатированной программе обычно содержится меньше ошибок, а продуманная структура текста – один из признаков высокой квалификации программирования. Отладка отдельных фрагментов существенно облегчается за счет возможности их четкого выделения из ясной структуры.

Таким образом, даже при использовании только текстовых форм форматирования существуют возможности визуализации программного обеспечения, которыми ни в коем случае не следует пренебрегать (см. также материал гл. 7).

Комментарии Важным инструментом сопровождения программного кода являются комментарии. В языке C++ используются комментарии двух видов:

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

/* это - комментарий Си */ /* комментарий Си может располагаться на нескольких строчках и заканчивается в любом месте строки */ // Это – однострочный комментарий, продолжающийся до конца строки /* При наличии однострочных комментариев возможно // вот такое вложение комментария.

Это иногда удобно при отладке */ С точки зрения назначения в тексте программы комментарии можно классифицировать следующим образом:

Заголовочные, или титульные, комментарии - комментарии в начале файла (модуля), содержащие, в частности, информацию об имени файла (и, возможно, расшифровку этого имени) - это удобно при распечатке;

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

дату создания и последней корректировки файла;

сведения об авторе.

Выделяющие, или предваряющие, комментарии (Д. Стрэйкер использует термин блочные комментарии [Straker, 1992]) размещаются перед относительно обособленными фрагментами текста, служат промежуточными заголовками к группам данных или действий или объясняют назначение отдельных подпрограмм.

Сопровождающие, или поясняющие, комментарии - обычно располагаются справа от основного текста и предназначены не только для пояснения отдельных моментов, но и просто облегчают читателю (в том числе и самому проектировщику) ориентирование в тексте.

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

Нижеследующий фрагмент кода (листинг 1.1) иллюстрирует применение комментариев различных видов, а также построение текста с учетом правил форматирования.

Листинг 1.1. Комментарии к функциям обработки параметров командной строки /* * Файл: PARMOS.CPP * PARaMeters from Operating System CPP module * * Проект: описание проекта * * Назначение: обработка параметров командной строки * * Дата создания : 13.06. * Дата корректировки : 21.07. * * Copyright (C) Пышкин Евгений Валерьевич, */ #include string.h #include "parmos.h" /* * Внешние интерфейсы данных */ PARMOS ParmOS;

// Сведения о параметрах командной строки /* * Конфигурируемые внутренние параметры модуля */ static const int nameLimit = 32;

// Предельно допустимая длина // имени файла (без расширения) static const int extLimit = 4;

// Предельно допустимая длина // расширения /* * Функции, входящие в состав модуля */ // SEND PARAMETERS from main program // Параметры, пересылаемые основной программой.

// Функция возвращает значения кода ошибки при работе // с командной строкой int SendParameters( int argc_copy, char *argv_copy[] ) { ParmOS.ErrorCode = 0;

// Проверка корректности количества параметров if( argc_copy PMLIM ) return ParmOS.ErrorCode = 1;

ParmOS.IxLast = argc_copy-1;

// Формирование массива значений параметров for( ParmOS.IxPm = 0;

ParmOS.IxPm = ParmOS.IxLast;

ParmOS.IxPm++ ) { if( strlen( argv_copy[ ParmOS.IxPm ] ) PMLEN-1 ) return ParmOS.ErrorCode = 4;

strcpy( ParmOS.Value[ ParmOS.IxPm ], argv_copy[ ParmOS.IxPm ] );

} if( ParmOS.IxLast 1 ) // обязательный параметр отсутствует { return ParmOS.ErrorCode = 1;

} // Проверка первого параметра (имя исполняемого файла) if( !ExeNameIsCorrect() ) { return ParmOS.ErrorCode = 2;

} // Проверка второго параметра (имя файла с исходными данными) if( !InputFileNameIsCorrect() ) { return ParmOS.ErrorCode = 3;

} // Проверка третьего параметра (имя файла результатов) if( OutputFileNameExists() ) { if( !OutputFileNameIsCorrect() ) { return ParmOS.ErrorCode = 4;

} } else ComposeOutputFileName();

return ParmOS.ErrorCode = 0;

} //...

// INPUT FILE NAME IS CORRECT?

// Проверка: имя исходного файла корректно?

bool InputFileNameIsCorrect() { char *observed;

// Указатель на обозреваемый символ char *preobserved;

// Прежнее значение "observed" // Поиcк первого вхождения символа '\' observed = strchr( name, (int) '\\' );

if( observed != NULL ) // есть по крайне мере один символ '\' { while( observed != NULL ) { preobserved = observed + 1;

observed = strchr( observed, (int) '\\' );

} observed = preobserved;

} else observed = name;

// нет ни одного символа '\' // Эдесь: "observed" указывает на начальный символ // собственно имени файла (без пути).

if( *observed == '\0' || // имя отсутствует strlen( observed ) nameLimit ) // или слишком длинное { return false;

} observed = strchr( observed, (int) '.' );

if( observed == NULL ) // расширение отсутствует { return false;

} observed++;

// Эдесь: "observed" указывает на начало расширения if( strlen( observed ) extLimit ) // расширение слишком // длинное { return false;

} return true;

// имя корректно } //...

/* * Конец файла PARMOS.CPP */ Стоит заметить, что затруднение, возникающее при попытке пояснить программный текст, часто связано с плохим качеством самого текста, так что комментирование программы служит и дополнительным средством контроля качества собственной разработки. Б. Керниган предлагал руководствоваться следующими правилами: «не комментируйте плохой код – перепишите его», стремитесь к ясности самого кода, «не умничайте»

[Kernighan, Plauger, 1978]. Продуманный, легко читаемый, грамотный комментарий, как правило, является свидетельством качественной разработки, ибо если проектировщик не может ясно рассказать о своих проектных решениях на естественном языке, то разве можно ожидать от него элегантных, красивых и надежных решений на языке искусственном?

Зона комментария иногда используется различными программами мастерами проектов для помещения туда служебной информации. Это связано с тем, что при использовании современных технологий проектирования исходные тексты некоторых компонентов ПО генерируются автоматически. При этом необходимая дополнительная информация помещается в комментарии. Обычно таким комментариям предшествует текст подобного содержания:

// DO NOT EDIT THIS TEXT!

// IT IS MACHINE GENERATED!



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.