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

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

План: 2 часа

1.Алгоритмизация.

1.1 Понятие алгоритма.

1.2. Свойства алгоритма.

1.3 Способы описания алгоритмов.

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

2.Эволюция языков программирования.

3.Структура и способы описания языков программирования высокого уровня.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования. – М.: Форум – Инфра - М, 2002.

2.Семакин И.Г. , Шестаков А.П. Основы программирования. – М.: Мастерство, 2002.

1.Алгоритмизация.

1.1 Понятие алгоритма.

Наша цель — научить компьютер решать те задачи, которые он самостоятельно и изначально решать не уме­ет. Что же для этого нужно?

А что, например, следует сделать, если нужно привлечь к решению задачи человека (назовем его исполнитель), не знакомого с ее решением? В общем виде последова­тельность действий здесь следующая:

а) выбрать способ (метод) решения задачи и изучить его во всех подробностях;

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

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

Второй этап значительно сложнее. Дело в том, что если способ (метод) решения задачи описан произвольно, то нет гарантии, что он будет верно понят исполнителем.

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

Именно поэтому описание метода следует выполнять в соответствии с определенными правилами, а именно: - выделить величины, являющиеся исходными для задачи;

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

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

• указать признак окончания процесса решения задачи;

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

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

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

Итак, мы подошли к центральному понятию информа­тики — алгоритму. Более строго это понятие можно дать следующим образом.

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

Или более коротко: алгоритм — это строго опреде­ленная последовательность действий, необходимых для ре­шения данной задачи.

Примером алгоритма может служить уже упоминав­шийся кулинарный рецепт — алгоритм варки картофеля:

1. Подготовить исходные величины — воду, картофель, соль, посуду (кастрюлю с крышкой для варки), нож.

2. С помощью ножа очистить картофель и промыть его водой.

3. Нарезать картофель для варки.

4. Поместить картофель в кастрюлю.

5. Залить содержимое кастрюли водой.

6. Посолить.

7. Довести воду до кипения.

8. Убавить огонь.

9. Варить картофель до готовности (приблизительно в течение 20—30 минут).

10. Снять кастрюлю с огня и слить воду.

11. Картофель готов. Процесс прекратить.

1.2 Свойства алгоритма.

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

1. Дискретность алгоритма. Это свойство означает,

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

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

3. Результативность алгоритма. Свойство алгорит­ма, состоящее в том, что он всегда приводит к результату через конечное число шагов.

4. Массовость алгоритма. Это свойство заключается в том, что каждый алгоритм, разработанный для реше­ния некоторой задачи, должен быть применим для реше­ния задач этого типа при всех допустимых значениях ис­ходных данных.

Действительно, рассмотрим приведенный выше алго­ритм варки картофеля с точки зрения его свойств.

Данный алгоритм дискретен, т.к. весь процесс разбит на отдельные шаги, которых у нас оказалось 11.

Алгоритм определен, т.к. каждая команда описана просто, коротко и достаточно понятно для исполнителя. Более того, команды даны именно в той последовательно­сти, которая необходима для решения данной задачи. Действительно, попробуйте, например, поменять местами пункты 5 и 7 алгоритма. Вряд ли в этом случае вы полу­чите нужный результат.

Алгоритм результативен, т.к. при его точном механи­ческом исполнении вы сможете отведать вполне приемле­мый вареный картофель.

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

1.3 Способы описания алгоритмов. Существует не­сколько способов описания алгоритмов.

1. Словесно-формульное описание алгоритма, т.е. опи­сание алгоритма с помощью слов и формул.

2. Графическое, описание алгоритма, т.е. описание с помощью специальных графических схем алгоритмов - блок-схем.

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

4. Запись алгоритма на одном из языков программирования (Pascal, Basic и т.п.)

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

Пример.

Составить алгоритм начисления зарплаты согласно сле­дующему правилу: «Если стаж работы сотрудника менее 5 лет, то зарплата 130 руб., при стаже работы от 5 до 15 лет — - 180 руб., при стаже свыше 15 лет зарплата по­вышается с каждым годом на 10 рублей».

Сформулируем задачу в математическом виде:

Вычислить:

[pic]

где ZP - зарплата; ST - стаж работы.

A. Словесно-формульное, описание алгоритма решения задачи:

1. Ввести ST, перейти к п.2.

2. Если SТ<5,то ZP:=130, перейти к п. 4, иначе - перейти к п.З.

3. Если 5≤SТ≤15, то ZP:=180, перейти к и. 4, иначе ZP:-=180+(ST-15)10, перейти к п. 4.

4. Вывести значение ZP, перейти к п. 5.

5. Конец работы.

B. Графическое описание алгоритма.

Прежде чем перейти к описанию алгоритма графичес­ким способом, введем понятие блок-схемы алгоритма.

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

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

[pic]

Каждый из описанных блоков № 2 и № 3 имеет один вход и один выход. Блок проверки некоторого условия (4) имеет два выхода — Да и Нет.

Например:

[pic]

Если условие выполняется — выходим из блока по вы­ходу Да, если не выполняется — по выходу Нет.

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

Типы Алгоритмов

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

1. линейные;

2. разветвляющиеся:

3. циклические.

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

Линейные алгоритмы

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

[pic]

Рассмотрим составление схем линейных алгоритмов на конкретных примерах.

Мы получили запись алгоритма решения данной зада­чи с помощью блок-схемы. Рассмотрим теперь запись это­го алгоритма с помощью псевдокода.

Пример.

Даны переменные А и В. Требуется обменять их значе­ния, т.е. переменная А должна получить значение В, а В — значение А.

Решение:

1. Исходные данные: А, В. Вспомогательная перемен­
   ная ВОР. Результат: А, В.

2. Метод решения задачи: в ЭВМ каждая величина
   хранится в отдельном участке памяти (переменной). По­
   этому задача заключается в том, чтобы поменять местами
   содержимое двух ячеек.

Давайте решим следующую задачу: имеется два стака­на: в одном из них вода, в другом молоко. Требуется по­менять содержимое стаканов. Житейский опыт подска­зывает, что нам для решения данной проблемы потребу­ется еще один стакан. В него мы перельем воду из перво­го, затем в первый стакан (из второго) нальем молоко, а из вспомогательного стакана во второй нальем воду.

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

[pic]

Мы получили запись алгоритма решения данной зада­чи с помощью блок-схемы. Рассмотрим теперь запись это­го алгоритма с помощью псевдокода.

Напомню, что псевдокоды — это интерпретация шагов алгоритма на обычном языке, которая описы­вает действие команды.

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

+ - / *.

Знак := (двоеточие и равно) означает операцию при­своения выбранной переменной некоторого значения.

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

- Инструкция ввода — Ввод (х, у, z)*.

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

- Инструкция вывода — Вывод (х, у).

- Инструкция присваивания — х := 32*.

Читается: «х присвоить значение 32».
Алгоритм Перемещение; {заголовок алгоритма]

Переменные А, В, Dop: целые числа; {описатель­ный блок}

Начало

Ввод (А, В);

Dop:=A;

А:=В;

B:=Dop;

Вывод(А, В);

Конец.

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

Пусть переменным А и В задаются значения 3 и 6 соот­ветственно. В итоге переменная А должна содержать 6, а В — 3. Проверим работу нашего алгоритма:

А

В

DOB

1

3

6

0

2

3

6

3

3

6

6

3

4

6

3

3

Результат работы алгоритма совпадает с ожидаемым. Значит, алгоритм составлен верно.

Логические выражения.

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

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

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

В результате сравнения значений двух выражений воз­можны два варианта ответа: сравнение истинно или ложно?

Например:

2+3 > 3+1 — да (истинно);

О < -7? — нет (ложно).

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

Нам известны 6 операций сравнения:

< Меньше

> Больше

<= Меньше или равно >= Больше или равно

= Равно

<> Не равно

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

Часто встречаются задачи, в которых используются не отдельные условия, а совокупность связанных между со­бой условий (отношений). Например, в магазине вам нужно выбрать туфли, размер которых г=45, цвет соl=белый, цена price не более 400 руб.

Другой пример: школьник выяснил, что сможет ку­пить шоколадку, если она стоит 3 руб. или 3 руб. 50 коп.

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

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

первое: (г=45) и (соl=белый) и (не (price>400));

второе: (цена=3) или (цена=3,5).

Алгоритмы ветвящейся структуры

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

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

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

В частном случае может отсутствовать один из блоков «Действие 1» или «Действие 2».

Пусть, например, В — проверяемое условие, a SI, S2 — некоторые выполняемые инструкции (действия). Тогда: Если условие В выполняется (истинно), то

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

иначе

выбрать для исполнения S2

Запишем ветвящийся алгоритм на псевдокоде и гра­фически:

[pic]

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

Пример.

Вычислить значение Y по одной из формул:

[pic]

Решение:

Исходные данные: х.

Результат: Y.

Метод решения задачи: необходимо выявить область, которой принадлежит значение х, для этого достаточно проверить заданные условия по порядку. Запишем алго­ритм в псевдокодах:

Алгоритм Bemel;

Переменные х, у .-вещественные;

Начало

Ввод (х);

Если х<10 тогда у:=х+2

иначе у:=х-2;

Вывод (у);

Конец.

К задачам рассмотренного выше вида очень часто сво­дятся вполне реальные задачи. Например, расчет стипен­дии, если известно среднее арифметическое оценок сту­дента за месяц. Стипендия отличника равна 100 рублям, хорошиста (5 < SRJ4) — 80 рублей, остальные стипендию не получают.

Математическая формула:

[pic]

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

Еще один распространенный вид задач — логические задачи. К ним относятся задачи определения минимума, максимума некоторого числа величин, задачи упорядочи­вания и сортировки данных и др. Это достаточно слож­ные задачи, однако в простейших случаях при неболь­шом числе данных они приводят к построению неслож­ных алгоритмов разветвляющейся структуры. Рассмотрим примеры подобных задач.

Пример.

Определить: Найти максимальное из двух чисел X, Z: У = max{X,Z}.

Решение:

Исходные данные: X, Z.

Результат: Мах.

Метод решения задачи: нужно сравнить два числа и сделать вывод. Блок-схема алгоритма решения этой зада­чи выглядит следующим образом:

[pic]

Циклический Алгоритм

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

Циклом называется последовательность действий, вы­полняемых многократно, каждый раз при новых значени­ях параметров.

Примером циклических алгоритмов может служить ал­горитм покраски забора. Действительно, рассмотрим этот алгоритм в словесно-формульном виде:

Шаг I. Подготовить исходные данные (забор, краску, кисть).

Шаг II. Подойти к забору.

Шаг III. Обмакнуть кисть в краску.

Шаг IV. Нанести краску кистью на поверхность забора.

Шаг V. Если забор еще не весь окрашен, то повто­рить алгоритм, начиная с пункта (Шаг III).

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

1. Инструкция «цикл с параметром» (цикл с задан­ным количеством повторений).

Обозначим:

х — параметр цикла (является счетчиком количества повторений);

a, b — соответственно начальные и конечные значения параметра цикла;

h — шаг, с которым изменяется параметр цикла;

S — оператор (инструкция), повторяемый в цикле.

Общий вид структуры цикла с параметром будет:

Для х := а до b с шагом h повторять

S

Инструкция «цикл с предусловием» (цикл-«пока»):

Обозначим:

В — некоторое проверяемое логическое условие;

S — оператор (инструкция), повторяемый в цикле.

Тогда инструкция в псевдокоде примет вид:

Повторять

S

Блок-схема такого цикла имеет вид:

[pic]

3. Инструкция «цикл с постусловием» (цикл-«до»):

Пока В повторять

S

Блок-схема такого цикла имеет вид:

[pic]

2.Эволюция языков программирования.

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

В 1950-х гг. появляются первые средства автоматизации про­граммирования — языки Автокоды. Позднее для языков этого уровня стало применяться название «Ассемблеры». Появление язы­ков типа Автокод-Ассемблер облегчило участь программистов. Пе­ременные величины стали изображаться символическими име­нами. Числовые коды операций заменились на мнемонические (словесные) обозначения, которые легче запомнить. Язык про­граммирования стал понятнее для человека, но при этом уда­лился от языка машинных команд. Чтобы компьютер мог испол­нять программы на Автокоде, потребовался специальный пере­водчик — транслятор. Транслятор — это системная программа, переводящая текст программы на Автокоде в текст эквивалент­ной программы на ЯМК.

Компьютер, оснащенный транслятором с Автокода, понимает Автокод. В этом случае можно говорить о псевдо-ЭВМ (аппаратура плюс транслятор с Автокода), языком которой является Автокод. Языки типа Автокод-Ассемблер являются машинно-ориентиро­ванными, т.е. они настроены на структуру машинных команд кон­кретного компьютера. Разные компьютеры с разными типами про­цессоров имеют разный Ассемблер. Языки программирования вы­сокого уровня (ЯПВУ) являются машинно-независимыми языками. Одна и та же программа на таком языке может быть выполнена на ЭВМ разных типов, оснащенных соответствующим транслятором. Форма записи программ на ЯПВУ по сравнению с Автокодом еще ближе к традиционной математической форме, к естествен­ному языку. Очень скоро вы увидите, что, например, на языке Паскаль она почти такая же, как на школьном Алгоритмическом языке. ЯПВУ легко изучаются, хорошо поддерживают структур­ную методику программирования.

Первыми популярными языками высокого уровня, появивши­мися в 1950-х гг., были Фортран, Кобол (в США) и Алгол (в Европе). Языки Фортран и Алгол были ориентированы на науч­но-технические расчеты математического характера. Кобол — язык для программирования экономических задач. В Коболе по сравне­нию с двумя другими названными языками слабее развиты мате­матические средства, но зато хорошо развиты средства обработки текстов, организация вывода данных в форме требуемого доку­мента. Для первых ЯПВУ предметная ориентация языков была ха­рактерной чертой.

Большое количество языков программирования появилось в 1960 —1970-х гг. А за всю историю ЭВМ их было создано более тысячи. Но распространились, выдержали испытание временем не­многие. В 1965 г. в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой язык, легко изучаемый, предназначенный для программирования несложных расчетных за­дач. Наибольшее распространение Бейсик получил на микроЭВМ и персональных компьютерах. На некоторых моделях школьных ком­пьютеров программировать можно только на Бейсике. Однако Бей­сик — неструктурный язык, и потому он плохо подходит для обу­чения качественному программированию. Справедливости ради сле­дует заметить, что последние версии Бейсика для ПК (например, QBasic) стали более структурными и по своим изобразительным возможностям приближаются к таким языкам, как Паскаль.

В эпоху ЭВМ третьего поколения получил большое распростра­нение язык PL/1 (Program Language One), разработанный фирмой IBM. Это был первый язык, претендовавший на универсальность, т.е. на возможность решать любые задачи: вычислительные, обра­ботки текстов, накопления и поиска информации. Однако PL/1 оказался слишком сложным языком. Для машин типа IBM 360/370 транслятор с него не мог считаться оптимальным, содержал ряд невыявленных ошибок. На ЭВМ класса мини и микро он вообще не получил распространения. Однако тенденция к универсализа­ции языков оказалась перспективной. Старые языки были модер­низированы в универсальные варианты — Алгол-68, Фортран-77.

Значительным событием в истории языков программирования стало создание в 1971 г. языка Паскаль. Его автор — швейцарский профессор Н.Вирт — разрабатывал Паскаль как учебный язык структурного программирования.

Наибольший успех в распространении этого языка обеспечили персональные компьютеры. Фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для ПК. Турбо Паскаль — это не только язык и транслятор с него, но еще и операционная оболочка, обеспечивающая пользователю удоб­ство работы. Турбо Паскаль вышел за рамки учебного предназна­чения и стал языком профессионального программирования с

универсальными возможностями. Транслятор с Турбо Паскаля по оптимальности создаваемых им программ близок наиболее удачному в этом отношении транслятору — транслятору с Фор­трана. В силу названных достоинств Паскаль стал основой многих современных языков программирования, например, таких как Ада, Модула-2 и др.

Язык программирования Си (английское название — С) со­здавался как инструментальный язык для разработки операцион­ных систем, трансляторов, баз данных и других системных и при­кладных программ. Так же как и Паскаль, Си — это язык струк­турного программирования, но, в отличие от Паскаля, в нем заложены возможности непосредственного обращения к некото­рым машинным командам, к определенным участкам памяти ком­пьютера. Дальнейшее развитие Си привело к созданию языка объек­тно-ориентированного программирования Си++.

Модула-2 — это еще один язык, предложенный Н.Виртом, осно­ванный на языке Паскаль и содержащий средства для создания больших программ.

ЭВМ будущего, пятого поколения называют машинами «ис­кусственного интеллекта». Но прототипы языков для этих машин были созданы существенно раньше их физического появления. Это языки ЛИСП и Пролог.

ЛИСП появился в 1965 г. Язык ЛИСП основан на понятии ре­курсивно определенных функций. А поскольку доказано, что лю­бой алгоритм может быть описан с помощью некоторого набора рекурсивных функций, то ЛИСП, по сути, является универсаль­ным языком. С его помощью на ЭВМ можно моделировать доста­точно сложные процессы, в частности интеллектуальную деятель­ность людей.

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

Реализовать тот или иной язык программирования на ЭВМ — это значит создать транслятор с этого языка для данной ЭВМ. Существуют два принципиально различных метода трансляции. Они называются соответственно компиляция и интерпретация. Для объяс­нения их различия можно предложить следующую аналогию: лек­тор должен выступить перед аудиторией на незнакомом ей языке. Перевод можно организовать двумя способами:

• полный предварительный перевод — лектор заранее передает текст выступления переводчику, тот записывает перевод, раз­множает его и раздает слушателям (после чего лектор может и не выступать);

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

Компиляция является аналогом полного предварительного пе­ревода; интерпретация — аналогом синхронного перевода. Транс­лятор, работающий по принципу компиляции, называется ком­пилятором; транслятор, работающий методом интерпретации, — интерпретатором.

При компиляции в память ЭВМ загружается программа-ком­пилятор. Она воспринимает текст программы на ЯПВУ как исход­ную информацию. После завершения компиляции получается про­грамма на языке машинных команд. Затем в памяти остается толь­ко программа на ЯМК, которая выполняется, и получаются требуемые результаты.

Интерпретатор в течение всего времени работы программы на­ходится во внутренней памяти. В ОЗУ помещается и программа на ЯПВУ. Интерпретатор в последовательности выполнения алгоритма «читает» очередной оператор программы, переводит его в коман­ды и тут же выполняет эти команды. Затем переходит к переводу и выполнению следующего оператора. При этом результаты преды­дущих переводов в памяти не сохраняются. При повторном вы­полнении одной и той же команды она снова будет транслиро­ваться. При компиляции исполнение программы разбивается на два этапа: трансляцию и выполнение. При интерпретации, по­скольку трансляция и выполнение совмещены, программа на ЭВМ проходит в один этап. Однако откомпилированная программа вы­полняется быстрее, чем интерпретируемая. Поэтому использова­ние компиляторов удобнее для больших программ, требующих бы­строго счета. Программы на Паскале, Си, Фортране всегда ком­пилируются. Бейсик чаще всего реализован через интерпретатор.

3. Структура и способы описания языков программирования высокого уровня.

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

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

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

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

Изложение языков Паскаль и Си в данном учебном пособии будет соответствовать этой схеме.

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

[pic]

Рис.1

знать алфавит этого языка. Во-вторых, следует знать правописание слов и правила записи предложений, т.е. то, что называется синтаксисом языка. В-третьих, важно понимать смысл слов и фраз, чтобы адек­ватно реагировать на них: ведь из грамотно написанных слов можно составить абсолютно бессмысленную фразу. Например, в салоне са­молета засветилось табло; на котором написано: Fasten belts! (При­стегните ремни!). Зная правила чтения английского языка, вы, к зависти соседа, правильно прочитаете эту фразу. Однако смысл ее вам может быть непонятен, и поэтому соответствующих действий вы не предпримете, за что получите замечание от стюардессы. Смыс­ловое содержание языковой конструкции называется семантикой.

Всякий язык программирования имеет три основные составля­ющие: алфавит, синтаксис и семантику.

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

Компьютер же — автомат, воспринимающий все «всерьез». В текстах программ нет избыточности, компьютер сам не исправит даже очевидной (с точки зрения человека) ошибки. Он может лишь указать на место, которое «не понял», и вывести замечание о предполагаемом характере ошибки. Исправить же ошибку дол­жен программист.

Для описания синтаксиса языка программирования тоже ну­жен какой-то язык. В этом случае речь идет о метаязыке («надъязыке»), предназначенном для описания других языков. Наибо­лее распространенными метаязыками в литературе по програм­мированию являются металингвистические формулы Бекуса— Наура (язык БНФ) и синтаксические диаграммы. В дальнейшем мы чаще всего будем использовать язык синтаксических диаг­рамм. Они более наглядны, легче воспринимаются. В некоторых случаях для удобства мы будем обращаться к отдельным эле­ментам языка БНФ.

В БНФ всякое синтаксическое понятие описывается в виде фор­мулы, состоящей из правой и левой части, соединенных знаком ::=, смысл которого эквивалентен словам «по определению есть». Слева от знака := записывается имя определяемого понятия (метапеременная), которое заключается в угловые скобки < >, а в правой части записывается формула или диаграмма, определяю­щая все множество значений, которые может принимать метапеременная.

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

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

В записях метаформул приняты определенные соглашения. На­пример, формула БНФ, определяющая понятие «двоичная циф­ра», выглядит следующим образом:

<двоичная цифра>::=0|1

Значок | эквивалентен слову «или». Это определение можно представить на языке синтаксических диаграмм (рис. 2).

[pic]

Рис.2

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

Понятие «двоичный код» как непустую последовательность дво­ичных цифр БНФ описывает так:

<двоичный код>::=<дзоичная цифра>I<двоичный код<двоичная цифра>

Определение, в котором некоторое понятие определяется само через себя, называется рекурсивным. Рекурсивные определения ха­рактерны для БНФ.

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

[pic]

Рис.3

Возвратная стрелка обозначает возможность многократного повторения. Очевидно, что диаграмма более наглядна, чем БНФ.

Синтаксические диаграммы были введены Н. Виртом и исполь­зованы для описания созданного им языка Паскаль.