Информатика_ Конспекты лекций

17)Какие значения получат c и d в результате выполнения алгоритма (a = 8: b

=3: если a < b, то c = b − a, иначе с = 2 × (a − b) : d = 0: пока c > a

выполнить действия: d = d + 1, c = c −1)?

18)Определите количество повторений цикла в фрагменте алгоритма (a = 3: b

=7: пока a / b <= b / 3: a = a + 2: b = b + 3).

19)Какие значения получат элементы массива в результате выполнения алгоритма (i = 2: N = 8: пока i <= N: A(i) = i × i: i = i + 2)?

20)Какие значения получат элементы массива в результате выполнения алгоритма (i = 1: N = 4: пока i <= N: A(i) =i × 2 + 2: i= i+ 1)?

21)Что представляет собой R, полученное в результате выполнения алгоритма

(R = 1: N = 10: i = 2: пока i <= N: если x(i) < 0

тогда R = R × x(i): i= i + 2: вывод R), по отношению к элементам заданного массива: x(1), x(2), ..., x(n)?

22)Что представляет собой K, полученное в результате выполнения алгоритма

(K = 0: N = 10: i = 1: пока i <= N: если x(i) = 0 тогда K = K + 1: i = i + 1:

вывод K), по отношению к элементам заданного массива: x(1), x(2), ..., x(n)?

23)Что представляет собой S, полученное в результате выполнения алгоритма

(S = 0: N = 10: i = 1: пока i <= N: если x(i) > 0 тогда S = S + x(i): i = i + 1:

вывод S), по отношению к элементам заданного массива: x(1), x(2), ..., x(n)?

24)Что необходимо изменить, чтобы бесконечный цикл, содержащийся во

x= x + 1), стал конечным?

25)Какое значение будет выведено в результате выполнения алгоритма (N = 0:

y= 0: пока N < 10: y = y + N: N = N + 1: вывод y)?

131

Тема 12. Средства и технологии программирования

Содержание

1. Средства создания программ

1.1.Текстовый редактор

1.2.Компилятор

1.3.Интерпретатор

1.4.Редактор связей (сборщик)

2. Технологии программирования

2.1.Алгоритмическое программирование

2.2.Структурное программирование

2.3.Объектно ориентированное программирование

3. Языки программирования

3.1.Языки программирования низкого уровня

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

3.3.Программирование баз данных

3.4.Программирование для сети Интернет

1.Средства создания программ

1.1.Текстовый редактор

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

1.2. Компилятор

Понятие «компилятор» можно изложить в виде следующих определений:

•программа или техническое средство, выполняющее компиляцию;

•машинная программа, используемая для компиляции;

•программа, переводящая текст программы на языке высокого уровня в эквивалентную программу на машинном языке;

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

•программа выполняющая (после трансляции) компоновку программы.

132

Компиляция – это:

•трансляция программы на язык, близкий к машинному, и последующая её компоновка;

•трансляция программы, составленной на исходном языке, в объектный модуль (осуществляется компилятором) и последующая её компоновка в готовый к использованию программный модуль;

•трансляция программы, составленной на исходном языке, и последующая её компоновка в программу на некоем машинонезависимом низкоуровневом интерпретируемом коде (как например, в случае языка

Java).

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

Виды компиляторов:

•векторизующий – компилирует исходный код в машинный код для компьютеров, оснащённых векторным процессором;

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

спомощью компилятора компиляторов;

•диалоговый – диалоговый транслятор;

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

•интерпретирующий (пошаговый) – последовательно выполняющий независимую компиляцию каждого отдельного оператора (команды) исходной программы;

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

•отладочный – устраняющий отдельные виды синтаксических ошибок;

•резидентный – постоянно находится в оперативной памяти и доступен для повторного использования многими задачами;

•самокомпилируемый – написан на том же языке, с которого осуществляется компиляция;

•универсальный – основан на формальном описании синтаксиса и семантики входного языка. Важными составными частями такого компилятора являются: ядро, синтаксический и семантический загрузчики.

Виды компиляции:

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

•построчная то же, что и интерпретация;

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

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

133

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

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

Некоторые компиляторы (например, Java) переводят программу не в машинный код, а в программу на некотором специально созданном низкоуровневом интерпретируемом языке. Такой язык — байт-код (в случае с Java Java-байт-код) — также можно считать языком машинных команд, поскольку в качестве его интерпретатора используется виртуальная машина. Байт-код не является машинным кодом какого-либо компьютера, то есть машинным кодом в прямом смысле слова, и может переноситься на различные компьютерные архитектуры без перекомпиляции. Байт-код интерпретируется

(исполняется) виртуальной машиной.

Например, для языка Java это JVM (язык виртуальной машины Java), или так называемый байт-код Java (вслед за ним все промежуточные низкоуровневые интерпретируемые языки стали называть байт-кодами). Для языков программирования на платформе .NET Framework (C#, Managed C++, Visual Basic .NET и другие) – это MSIL (Microsoft Intermediate Language).

Программа на байт-коде подлежит интерпретации виртуальной машиной, либо ещё одной компиляции уже в машинный код непосредственно перед исполнением. Последнее называется «Just-In-Time компиляция» (JIT), по названию подобного компилятора для Java. MSIL-код компилируется в код целевой машины также JIT-компилятором, а библиотеки .NET Framework компилируются заранее.

Для каждой целевой машины (IBM, Apple, Sun и т. д.) и каждой операционной системы или семейства операционных систем, работающих на целевой машине, требуется написание своего компилятора. Существуют также так называемые кросс-компиляторы, позволяющие на одной машине и в среде одной ОС генерировать код, предназначенный для выполнения на другой целевой машине и/или в среде другой ОС. Кроме того, компиляторы могут быть оптимизированы под разные типы процессоров из одного семейства (путём поддержки специфичных для этих процессоров машинных команд). Например, код, скомпилированный под процессоры семейства Pentium, может использовать специфичные для этих процессоров наборы инструкций – MMX, SSE, SSE2.

134

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

Существуют программы, которые решают обратную задачу – это перевод программы с низкоуровневого языка на высокоуровневый. Этот процесс называют декомпиляцией, а такие программы – декомпиляторами. (Яркий пример таких программ – дизассемблеры) Но поскольку компиляция – это процесс с потерями, точно восстановить исходный код, скажем, на C++, в общем случае невозможно. Более эффективно компилируются программы в байт-кодах – например, существует довольно надёжный декомпилятор для Flash. Разновидностью декомпилирования является дизассемблирование машинного кода в код на языке ассемблера, который всегда выполняется успешно. Связано это с тем, что между кодами машинных команд и командами ассемблера имеется практически взаимно-однозначное соответствие.

Любой компилятор состоит из транслятора и компоновщика. Часто в качестве компоновщика компилятор использует внешний компоновщик, реализованный в виде самостоятельной программы, а сам выполняет лишь трансляцию исходного текста (по этой причине многие ошибочно считают компилятором разновидность транслятора). Компилятор может быть реализован и как своеобразная программа-менеджер, для трансляции программы, разные части которой написаны на разных языках программирования. Эта программа-менеджер вызывает соответствующие трансляторы и затем – для компоновки программы – вызывает компоновщик. Ярким примером такого компилятора является имеющаяся во всех UNIXсистемах (и Linux-системах в том числе) утилита make (имеются реализации утилиты make и в других системах, в частности в Windows-системах).

Процесс компиляции состоит из следующих фаз:

1.Лексический анализ. На этой фазе последовательность символов исходного файла преобразуется в последовательность лексем.

2.Синтаксический (грамматический) анализ.

3.Семантический анализ. Древо разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их определениям, типам данных, проверка совместимости типов данных, определение результирующих типов данных выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным древом разбора, новым древом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.

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

135

например, над промежуточным кодом или над конечным машинным кодом.

5.Генерация кода. Из промежуточного представления порождается код на целевом языке (в том числе выполняется компоновка программы).

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

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

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

1)разбор исходной программы и перевод ее во внутреннее представление, удобное для дальнейшей работы;

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

3)оптимизация кода программы;

4)генерация выходного кода на машинном языке.

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

136

1.3. Интерпретатор

Понятие «интерпретатор» можно изложить в виде следующих определений:

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

интерпретацию;

•вид транслятора, осуществляющего пооператорную (покомандную) обработку и выполнение исходной программы или запроса (в отличие от компилятора, транслирующего всю программу без её выполнения);

•программа (иногда аппаратное средство), анализирующая команды или операторы программы и тут же выполняющая их;

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

Типы интерпретаторов:

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

Интерпретатор компилирующего типа – это система из компилятора,

переводящего исходный код программы в промежуточное представление, например, в байт-код или p-код, и собственно интерпретатора, который выполняет полученный промежуточный код (так называемая виртуальная машина). Достоинством таких систем является большее быстродействие выполнения программ (за счёт выноса анализа исходного кода в отдельный, разовый проход, и минимизации этого анализа в интерпретаторе). Недостатки — большее требование к ресурсам и требование на корректность исходного кода. Применяется в таких языках, как Java, PHP, Python, Perl (используется байт-код), REXX (сохраняется результат парсинга исходного кода), а также в различных СУБД (используется p-код).

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

Некоторые интерпретаторы (например, для языков Lisp, Scheme, Python, Бейсик и других) могут работать в режиме диалога или так называемого цикла

137

чтения-вычисления-печати (англ. read-eval-print loop, REPL). В таком режиме интерпретатор считывает законченную конструкцию языка (например, s- expression в языке Lisp), выполняет её, печатает результаты, после чего переходит к ожиданию ввода пользователем следующей конструкции.

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

Следует также отметить, что режимы интерпретации можно найти не только в программном, но и аппаратном обеспечении. Так, многие микропроцессоры интерпретируют машинный код с помощью встроенных микропрограмм, а процессоры семейства x86, начиная с Pentium (например, на архитектуре Intel P6), во время исполнения машинного кода предварительно транслируют его во внутренний формат (в последовательность микроопераций).

Алгоритм работы простого интерпретатора:

1.прочитать инструкцию;

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

3.выполнить соответствующие действия;

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

Достоинства интерпретаторов:

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

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

•упрощение отладки исходных кодов программ;

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

Недостатки интерпретаторов:

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

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

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

138

1.4. Редактор связей (сборщик)

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

.EXE или .COM.

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

2.Технологии программирования

2.1.Алгоритмическое программирование

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

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

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

Для больших программ такая технология программирования мало приемлема из-за большого количества возникающих проблем. К ним относятся следующие:

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

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

139

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

•набрать и отладить длинную (более 1000 строк кода) линейную последовательность операторов крайне затруднительно или практически невозможно.

2.2. Структурное программирование

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

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

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

140