Технология программирования. 1. Устройство компьютера. Оперативная память, процессор
 Скачать 478.73 Kb.
|
|
Процедурные языки, которые представляют собой последовательность выполняемых операторов. Если рассматривать состояние ПК как состояние ячеек памяти, то процедурный язык – это последовательность операторов, изменяющих значение одной или нескольких ячеек. К процедурным языкам относятся FORTRAN, C, Ada, Pascal, Smalltalk и некоторые другие. Процедурные языки иногда также называются императивными языками. · Аппликативные языки, в основу которых положен функциональный подход. Язык рассматривается с точки зрения нахождения функции, необходимой для перевода памяти ПК из одного состояния в другое. Программа представляет собой набор функций, применяемых к начальным данным, позволяющий получить требуемый результат. К аппликативным языкам относится язык LISP. · Языки системы правил, называемые также языками логического программирования, основываются на определении набора правил, при выполнении которых возможно выполнение определенных действий. Правила могут задаваться в виде утверждений и в виде таблиц решений. К языкам логического программирования относится язык Prolog. 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 23/69 · Объектно-ориентированные языки, основанные на построении объектов как набора данных и операций над ними. Объектно- ориентированные языки объединяют и расширяют возможности, присущие процедурным и аппликативным языкам. К объектно- ориентированным языкам относятся C++, Object Pascal, Java. В настоящий момент наибольшее распространение получили языки, основанные на объектно-ориентированной модели. Они, реализуя процедурную модель построения языка, поддерживают аппликативность конструкций, позволяя представлять блок-схему выполнения структурированной программы как некоторый набор аппликативных функций. 2.4. Состав языка программирования В тексте на любом естественном языке можно выделить четыре основных элемента: символы, слова, словосочетания и предложения. Подобные элементы содержит и алгоритмический язык, только слова называют лексемами (элементарными конструкциями), словосочетания – выражениями, а предложения – операторами. Лексемы образуются из символов, выражения – из лексем и символов, а операторы – из символов, выражений и лексем (рис. 2.1): Рис. 2.1.Состав алгоритмического языка 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 24/69 Алфавит языка, или его символы — это основные неделимые знаки, с помощью которых пишутся все тексты на языке. Лексема, или элементарная конструкция, — минимальная единица языка, имеющая самостоятельный смысл. Выражение задает правило вычисления некоторого значения. Оператор задает законченное описание некоторого действия. Для описания сложного действия требуется последовательность операторов. Операторы могут быть объединены в составной оператор, или блок. В этом случае они рассматриваются как один оператор. Операторы бывают исполняемые и неисполняемые. Исполняемые операторы задают действия над данными. Неисполняемые операторы служат для описания данных, поэтому их часто называют операторами описания или просто описаниями. Каждый элемент языка определяется синтаксисом и семантикой. Синтаксические определения устанавливают правила построения элементов языка, а семантика определяет их смысл и правила использования. Объединенная единым алгоритмом совокупность описаний и операторов образует программу на алгоритмическом языке. 2.5. Стандартизация языков программирования Концепция языка программирования неотрывно связана с его реализацией. Для того чтобы компиляция одной и той же программы различными компиляторами всегда давала одинаковый результат, разрабатываются стандарты языков программирования. Существует ряд организаций, целенаправленно занимающихся вопросами стандартизации. Это Американский национальный институт стандартов ANSI (American National Standards Institute), Институт 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 25/69 инженеров по электротехнике и электронике IEEE (Institute of Electrical and Electronic Engineers), Организация международных стандартов ISO (International Organization for Standardization). Как правило, при создании языка выпускается частный стандарт, определяемый разработчиками языка. Если язык получает широкое распространение, то со временем появляются различные версии компиляторов, которые не точно следуют частному стандарту. В большинстве случаев идет расширение зафиксированных первоначально возможностей языка. Для приведения наиболее популярных реализаций языка в соответствие друг с другом разрабатывается согласительный стандарт. Очень важным фактором стандартизации языка программирования является своевременность появления стандарта – до широкого распространения языка и создания множества несовместимых реализаций. В процессе развития языка могут появляться новые стандарты, отражающие современные нововведения. Так, язык FORTRAN первоначально был стандартизирован в 1966 году. В результате был издан стандарт FORTRAN 66. Далее этот стандарт несколько раз пересматривался (в 1977 году был выпущен FORTRAN 77, затем появился и FORTRAN 90). В процессе развития языка некоторые его конструкции и функции устаревают. Однако с целью обратной совместимости новые версии должны поддерживать и все устаревающие возможности. Это ведет к "разбуханию" компиляторов. В последнее время в реализациях введено понятие не рекомендуемой и устаревшей возможности. В первом случае следующий стандарт еще будет поддерживать не рекомендуемую возможность, но может перевести ее в категорию устаревшей. Во втором случае стандарт может исключить поддержку возможности, объявленной ранее как устаревшая. 2.6. Среда проектирования 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 26/69 С развитием языков программирования совершенствовались и средства разработки программ – от режима командной строки до интегрированной среды проектирования. Такая среда предоставляет удобный графический интерфейс разработки и большой спектр сервисов, включающих управление версиями хранимых данных, утилиты просмотра и управления информацией, библиотеки классов, мастера создания шаблонов приложений и т.п. Компилятор языка программирования выступает как составная часть среды проектирования. Сама программа наряду с конструкциями, предусмотренными стандартом, как правило, использует библиотечные функции и классы, предоставляемые средой проектирования. Так, интегрированная среда разработки VisualStudio содержит библиотеку классов MFC (Microsoft Foundation Classes), значительно упрощающую процесс разработки приложений, использующих оконный интерфейс. 2.7. Трансляторы Программа, написанная на языке высокого уровня, перед исполнением должна быть преобразована в программу на "машинном языке". Такой процесс называется трансляцией, или компиляцией. По типу выходных данных различают два основных вида трансляторов: · компилирующие окончательный выполнимый код; · компилирующие интерпретируемый код, для выполнения которого требуется дополнительное программное обеспечение. Окончательным выполнимым кодом являются приложения, реализованные как EXE-файлы, DLL-библиотеки, COM-компоненты. К 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 27/69 интерпретируемому коду можно отнести байт-код JAVA-программ, выполняемый посредством виртуальной машины JVM. Языки, формирующие окончательный выполнимый код, называются компилируемыми языками. К ним относятся языки С, C++, FORTRAN, Pascal. Языки, реализующие интерпретируемый код, называются интерпретируемыми языками. К таким языкам относятся язык Java, LISP, Perl, Prolog. В большинстве случаев код, получаемый в результате процесса трансляции, формируется из нескольких программных модулей. Программным модулем называется определенным образом оформленный код на языке высокого уровня. Процесс трансляции в этом случае может выполняться как единое целое – компиляция и редактирование связей, или как два отдельных этапа – сначала компиляция объектных модулей, а затем вызов редактора связей, создающего окончательный код. Последний подход более удобен для разработки программ. Он реализован в трансляторах языков С и С++. Объектный код, создаваемый компилятором, представляет собой область данных и область машинных команд, имеющих адреса, которые в дальнейшем "согласуются" редактором связи (иногда называемым загрузчиком). Редактор связи размещает в едином адресном пространстве все по отдельности откомпилированные объектные модули и статически подключаемые библиотеки. Будем называть выполнимой формой программы код, получаемый в результате трансляции исходной программы. 2.8. Процесс трансляции Программу, написанную на языке программирования высокого уровня, называют исходной программой, а каждую самостоятельную 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 28/69 программную единицу, образующую данную программу, - программным модулем. Для преобразования исходной программы в ее выполняемую форму (выполнимый файл) транслятор выполняет некоторую последовательность действий. Эта последовательность зависит как от языка программирования, так и от конкретной реализации самого транслятора. В ходе трансляции важно не просто откомпилировать программу, а получить при этом достаточно эффективный код. В процессе трансляции выполняется анализ исходной программы, а затем синтез выполнимой формы данной программы. В зависимости от числа просмотров исходной программы, выполняемых компилятором, трансляторы разделяются на однопроходные, двухпроходные и трансляторы, использующие более двух проходов. К достоинствам однопроходного компилятора можно отнести высокую скорость компиляции, а к недостаткам - получение, как правило, не самого эффективного кода. Широкое распространение получили двухпроходные компиляторы. Они позволяют при первом проходе выполнить анализ программы и построить информационные таблицы, используемые при втором проходе для формирования объектного кода. Фаза анализа программы состоит из: · лексического анализа; · синтаксического анализа; · семантического анализа. При анализе исходной программы транслятор последовательно просматривает текст программы, представимой как набор символов, выполняя разбор структуры программы. 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 29/69 На этапе лексического анализа выполняется выделение основных составляющих программы – лексем. Лексемами являются ключевые слова, идентификаторы, символы операций, комментарии, пробелы и разделители. Лексический анализатор не только выделяет лексемы, но и определяет тип каждой лексемы. При этом на этапе лексического анализа составляется таблица символов, в которой каждому идентификатору сопоставлен свой адрес. Это позволяет при дальнейшем анализе вместо конкретного значения (строки символов) использовать его адрес в таблице символов. Процесс выделения лексем достаточно трудоемок и требует применения сложных контекстно-зависимых алгоритмов. На этапе синтаксического анализа выполняется разбор полученных лексем с целью получения семантически понятных синтаксических единиц, которые затем обрабатываются семантическим анализатором. Так, синтаксическими единицами выступают выражения, объявление, оператор языка программирования, вызов функции. На этапе семантического анализа выполняется обработка синтаксических единиц и создание промежуточного кода. В зависимости от наличия или отсутствия фазы оптимизации результатом семантического анализа может быть оптимизируемый далее промежуточный код или готовый объектный модуль. К наиболее общим задачам, решаемым семантическим анализатором, относятся: · обнаружение ошибок времени компиляции; · заполнение таблицы символов, созданной на этапе лексического анализа, конкретными значениями, определяющими дополнительную информацию о каждом элементе таблицы; · замена макросов их определениями; 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 30/69 · выполнение директив времени компиляции. Макросом называется некоторый предварительно определенный код, который на этапе компиляции вставляется в программу во всех местах указания вызова данного макроса. На фазе синтеза программы производится: · генерация кода; · редактирование связей. Процесс генерации кода состоит из преобразования промежуточного кода (или оптимизированного кода) в объектный код. При этом в зависимости от языка программирования получаемый объектный код может быть представлен в выполнимой форме или как объектный модуль, подлежащий дальнейшей обработке редактором связей. Так, процесс генерации кода является неотъемлемой частью фазы синтеза программы, а необходимость выполнения редактора связей зависит от конкретного языка программирования. Следует учесть, что на практике термин «генерация кода» часто применяют ко всем действиям фазы синтеза программы, ведущим к получению выполнимой формы программы. Редактор связей приводит в соответствие адреса фрагментов кода, расположенных в отдельных объектных модулях: определяются адреса вызываемых внешних функций, адреса внешних переменных, адреса функций и методов каждого модуля. Для редактирования адресов редактор связей использует специальные, создаваемые на этапе трансляции, таблицы загрузчика. После обработки объектных модулей редактором связей генерируется выполнимая форма программы. Методические указания: § читать учебное пособие 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 31/69 Тема 3. Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. Содержание темы: общее понятие алгоритма, управляющие конструкции алгоритмического языка, язык схем, основные структуры алгоритмов, понятие переменной Цели и задачи изучения темы: получить знания о написании алгоритма решения поставленной задачи, управляющих конструкциях алгоритмического языка, о важнейшем понятии алгоритмического языка – переменной Изучая тему, необходимо акцентировать внимание на следующих понятиях: · алгоритм– описание последовательности действий, которые необходимо выполнить для решения задачи; · псевдокод – алгоритмический язык, максимально приближенный к естественному; · ветвления и циклы – изменяют последовательное выполнение команд; · цикл с предусловием – условие продолжения цикла проверяется перед выполнением тела цикла; · переменная – именованная область в памяти компьютера, в которую могут записываться различные числовые или символьные значения; · присваивание – операция записи значения впеременную; · основные структуры алгоритмов– ограниченный набор стандартных способов соединения отдельных блоков или структур 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 32/69 для выполнения типичных последовательностей действий; 3.1. Общее понятие алгоритма Понятие алгоритма – одно из основных понятий программирования и математики. Алгоритм – это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм записывается на формальном языке, исключающем неоднозначность толкования. В нашем случае исполнитель – это компьютер, но может быть и человек, автоматическое устройство и т.п. Запись алгоритма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова "алгоритм" и "программа" - почти синонимы. Небольшое различие заключается в том, что при упоминании алгоритма, как правило, имеют в виду основную идею его построения, общую для всех алгоритмических языков. Программа же всегда связана с записью алгоритма на конкретном формальном языке. В математике рассматриваются различные виды алгоритмов – программы для машин Тьюринга, алгоритмы Маркова (нормальные алгоритмы), частично рекурсивные функции и т.п. Знаменитый тезис Чёрча утверждает, что все виды алгоритмов эквивалентны друг другу, т.е. классы задач, решаемых разными типами алгоритмов, всегда совпадают. Тезис этот недоказуем (можно лишь доказать совпадение для двух конкретных типов алгоритмов, например, машин Тьюринга и нормальных алгоритмов), но никто в его верности не сомневается. Так что все языки программирования эквивалентны друг другу и различаются лишь тем, насколько они удобны для решения конкретных классов задач. Например, объектно-ориентированные языки оптимальны для программирования в оконных средах, а язык Фортран успешно применяется в научных и инженерных расчетах. 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 33/69 Большинство используемых в программировании алгоритмических языков имеют общие черты. В то же время, при изложении идеи алгоритма, например, при публикации в научной статье, не всегда целесообразно пользоваться каким-либо конкретным языком программирования, чтобы не загромождать изложение несущественными деталями. В таких случаях применяется неформальный алгоритмический язык, максимально приближенный к естественному. Язык такого типа называют псевдокодом. Для специалиста не составляет труда переписать программу с псевдокода на любой конкретный язык программирования. Запись алгоритма на псевдокоде зачастую яснее и нагляднее, она дает возможность свободно выбирать уровень детализации, начиная от описания в самых общих чертах и кончая подробным изложением. Псевдокод объединяет существенные черты множества алгоритмических языков. Для записи алгоритмов в данном курсе будет использоваться как псевдокод, так и конкретные языки: Си, C++. 3.2. Управляющие конструкции алгоритмического языка Большинство алгоритмических языков относится к так называемым процедурным языкам, в которых основной единицей является оператор. Оператор представляет собой команду на выполнение некоторого действия. Язык, таким образом, состоит в основном из фраз в повелительном наклонении. Альтернативой операторам являются описания, определяющие объекты или типы объектов и их взаимосвязи. Считается, что чем больший процент составляют описания, тем более совершенным является язык. Существуют алгоритмические языки, состоящие в основном из описаний (функциональные языки), однако, данный курс ограничивается процедурными языками. 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 34/69 Всякий алгоритм предназначен исполнителю, который однозначно понимает команды алгоритма. Пример: опишем алгоритм проезда от Аэровокзала в Москве до аэропорта Домодедово. алгоритм Проезд от Аэровокзала до Домодедово через МКАД | Дано: находимся у Аэровокзала | Надо: оказаться в аэропорту Домодедово начало алгоритма | повернуть направо на центральный проезд | Ленинградского проспекта в сторону центра; | проехать до второго светофора; | выполнить разворот на перекрестке | проехать по Ленинградскому проспекту из центра | до пересечения с Московской кольцевой дорогой; | переехать мост над кольцевой дорогой и | повернуть направо на внешнюю часть кольцевой дороги; | двигаться по кольцевой дороге в направлении против | часовой стрелки до Каширского шоссе; | повернуть направо на Каширское шоссе в сторону из города; | двигаться, никуда не сворачивая, до | аэропорта Домодедово; конец алгоритма 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 35/69 Строки алгоритма представляют собой фразы в повелительном наклонении, которые предназначены исполнителю алгоритма, т.е. любому водителю, который может отличить внешнюю сторону кольцевой дороги от внутренней. Строки алгоритма выполняются последовательно; считается, что исполнитель алгоритма способен не задумываясь выполнить каждую его команду. Большинство алгоритмов не сводится, однако, к последовательному выполнению команд, в них присутствуют ветвления и циклы. При ветвлении в зависимости от условия выполняется одна из двух ветвей программы; для этого используется оператор "если ... то ... иначе ... конец если". Например, можно модифицировать приведенный выше алгоритм, используя выбор одного из двух альтернативных путей, в зависимости от наличия транспортной пробки. алгоритм Оптимальный путь от Аэровокзала до Домодедово | Дано: находимся у Аэровокзала | Надо: оказаться в аэропорту Домодедово начало алгоритма | если нет пробки на Ленинградском проспекте | | в направлении из центра | | то | | // ...выполняем предыдущий алгоритм... | | Проезд от Аэровокзала до Домодедово через МКАД | | иначе | | повернуть направо на боковой проезд | | Ленинградского проспекта в сторону центра; 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 36/69 | | доехать до пересечения с Беговой улицей; | | повернуть направо на Третье транспортное кольцо; | | ехать по Третьему транспортному кольцу против | | часовой стрелки до пересечения с Варшавским шоссе; | | повернуть направо на Варшавское шоссе | | в сторону из центра; | | ехать прямо до развилки с Каширским шоссе; | | на развилке с Каширским шоссе проехать прямо в сторону | | Каширского шоссе; // Варшавское уходит направо | | двигаться, никуда не сворачивая, до | | аэропорта Домодедово; | конец если конец алгоритма Здесь исполнитель алгоритма сначала должен проверить условие |