Лекция Языки и системы программирования. Структура данных
| Вид материала | Лекция |
- Лекция 3 Инструментальное по. Классификация языков программирования, 90.16kb.
- Календарный план учебных занятий по дисциплине «Языки и технология программирования», 43.35kb.
- Рейтинг-план дисциплины «Языки программирования в иит» в течение семестра Недели, 53.58kb.
- Введение Предмет "Программирование", 19.2kb.
- Языки программирования. Лекция, 95.09kb.
- Рабочей программы учебной дисциплины языки программирования Уровень основной образовательной, 47.91kb.
- Существуют различные классификации языков программирования, 174.02kb.
- Аннотация рабочей программы учебной дисциплины языки программирования Направление подготовки, 135.09kb.
- Ооп бд объектно-ориентированная база данных, 2077.6kb.
- Государственное Образовательное Учреждение высшего профессионального образования Московский, 1556.11kb.
Если исходный язык является языком высокого уровня, например таким, как ФОРТРАН, C и Паскаль, и если объектный язык - ассемблер или некоторый машинный язык, то транслятор называется компилятором. Машинный язык иногда называют кодом машины, поэтому и объектная программа иногда называется объектным кодом.
Трансляция исходной программы в объектную происходит во время компиляции, а фактическое выполнение объектной программы происходит во время выполнения готовой программы.
Ассемблер - это программа, которая переводит исходную программу, написанную на автокоде или на языке ассемблера, на язык вычислительной машины. Автокод (ассемблер) очень близок к машинному языку; действительно, большинство автокодных инструкций является точным символическим представлением команд машины. Более того, автокодные инструкции обычно имеют фиксированный формат, что позволяет легко их анализировать. В автокоде, как правило, отсутствуют вложенные инструкции, блоки и т. п.
Интерпретатор для некоторого исходного языка принимает исходную программу, написанную на этом языке, как входную информацию и выполняет ее. Различие между компилятором и интерпретатором состоит в том, что интерпретатор не порождает объектную программу, которая затем должна выполняться, а непосредственно выполняет ее сам. Для того чтобы выяснить, как осуществить выполнение инструкций исходной программы, чистый интерпретатор анализирует ее всякий раз, когда она должна быть выполнена. Конечно же, это не эффективно и используется не очень часто.
При программировании интерпретатор обычно разделяют на две фазы. На первой фазе интерпретатор анализирует всю исходную программу, почти также, как это делает компилятор, и транслирует ее в некоторое внутреннее представление. На второй фазе это внутреннее представление исходной программы интерпретируется или выполняется. Внутреннее представление исходной программы разрабатывается для того, чтобы свести к минимуму время, необходимое для расшифровки или анализа каждой инструкции при ее выполнении.
Как указывалось выше, сам компилятор - это не что иное, как программа, написанная на некотором языке, для которой входной информацией служит исходная программа, а результатом является эквивалентная ей объектная программа. Исторически сложилось так, что компиляторы писались на автокоде вручную. Во многих случаях это был единственный доступный язык. Однако, сейчас компиляторы разрабатываются на языках высокого уровня (поскольку при этом уменьшается время, затрачиваемое на программирование и отладку, а также обеспечивается удобочитаемость программы компилятора, когда работа завершена).
Кроме того, теперь мы имеем много языков, разработанных специально для составления компиляторов. Эти так называемые "компиляторы компиляторов" являются некоторым подмножеством в "системах построения трансляторов" (СПТ).
Процесс компиляции, структура компилятора, проходы компилятора.
Процесс компиляции разделяется на несколько этапов:
- Препроцессор. Исходная программа обрабатывается путём подстановки имеющихся макросов и заголовочных файлов.
- Лексический и синтаксический анализ. Программа преобразовывается в цепочку лексем, а затем во внутреннее представление в виде дерева.
- Глобальная оптимизация. Внутреннее представление программы неоднократно преобразовывается с целью сокращения размера и времени исполнения программы.
- Генерация кода. Внутреннее представление преобразовывается в блоки команд процессора, которые преобразовываются в ассемблеровский текст или в объектный код.
- Ассемблирование. Если генерируется ассемблерный текст, производится его ассемблирование с целью получения объектного кода.
- Сборка. Сборщик соединяет несколько объектных файлов в исполняемый файл или библиотеку.
На фазе лексического анализа (ЛА) входная программа, представляющая собой поток символов, разбивается на лексемы - слова в соответствии с определениями языка. Основным формализмом, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором за очередной лексемой, либо как полный проход, результатом которого является файл лексем. В процессе выделения лексем ЛА может как самостоятельно строить таблицы имен и констант, так и выдавать значения для каждой лексемы при очередном обращении к нему. В этом случае таблица имен строится в последующих фазах (например, в процессе синтаксического анализа).
На этапе ЛА обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).
Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)- анализ (и его вариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматизации построения синтаксических анализаторов.
Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.
На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно- свободным синтаксисом. Это в основном связи "описание- использование", в частности анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа строится таблица символов, которую можно рассматривать как таблицу имен, пополненную информацией об описаниях (свойствах) объектов.
Основным формализмом, использующимся при контекстном анализе, являются атрибутные грамматики. Результатом работы фазы контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах символов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.
Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие.
Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная - только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д.
Наконец, генерация кода - последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы.
Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.
Принципы работы сред программирования
Следует отличать язык программирования от его реализации, которая обычно представлена в составе среды программирования (Quick Basic, Virtual Pascal) - набора средств для редактирования исходных текстов, генерации исполняемого кода, отладки, управления проектами и т.д. Каждая среда программирования предоставляет свой интерпретатор или компилятор с этого языка, который зачастую допускает использование конструкций, не фиксированных в стандарте.
Использование среды программирования Турбо Паскаль
Разработка программ на Паскале включает в себя следующие действия (этапы разработки программы): ввод и редактирование текста программы на языке программирования Паскаль, ее трансляцию, отладку.
Для выполнения каждого этапа применяются специальные средства: для ввода и редактирования текста используется редактор текстов, для трансляции программы — компилятор, для построения исполняемого компьютером программного модуля с объединением разрозненных откомпилированных модулей и библиотекой стандартных процедур Паскаля — компоновщик (linker), для отладки программ с анализом ее поведения, поиском ошибок, просмотром и изменением содержимого ячеек памяти компьютера — отладчик (debugger).
Для повышения качества и скорости разработки программ в середине 80-х гг. была создана система программирования Турбо Паскаль. Слово Турбо в названии системы программирования — это отражение торговой марки фирмы-разработчика Borland International, Inc. (США).
Систему программирования Турбо Паскаль называют интегрированной (integration — объединение отдельных элементов в единое целое) средой программирования, так как она объединяет в себе возможности ранее разрозненных средств, используемых при разработке программ: редактора текстов, компилятора, компоновщика, отладчика, и при этом обеспечивает программисту великолепные сервисные возможности. Часто ее кратко называют IDE (Integrated Development Environment — интегрированная среда разработки).
Интегрированная среда программирования Турбо Паскаль версий 6.0 и 7.0 имеет следующие возможности:
- множество накладывающихся окон;
- поддержка мыши, меню, диалоговых окон;
- многофайловый редактор, который может редактировать файлы до 1 Мбайта;
- расширенные возможности отладки;
- полное сохранение и восстановление среды разработки.
Основные файлы пакета Турбо Паскаль
Если допустим, что система программирования Турбо Паскаль установлена на диске D: в каталоге D:\BORLAND\BP, то в каталоге ..\ВР находятся следующие основные файлы Турбо Паскаля:
TURBO.EXE — интегрированная среда программирования;
TURBO.HLP — файл, содержащий данные для оперативной подсказки;
TURBO.TP — файл конфигурации системы;
TURBO.TPL — библиотека стандартных модулей Турбо Паскаля.
В каталоге D:\BORLAND\BP\BGI находятся файлы, необходимые для работы в графическом режиме: GRAPH.TPU — модуль с графическими процедурами и функциями Турбо Паскаля, несколько файлов с расширением .BGI — драйверы различных типов видеосистем компьютеров, несколько файлов с расширением .CHR, содержащих векторные шрифты.
Для вызова Турбо Паскаля необходимо отыскать в древовидной структуре каталогов ПК этот каталог и в нем файл TURBO.EXE. Этот файл содержит готовую к работе диалоговую систему программирования Турбо Паскаль.
Окна Турбо Паскаля
Почти все, что вы видите и делаете в среде Турбо Паскаль, происходит в окнах. Окно — это область экрана, которую можно перемещать, изменять в размере, перекрывать, закрывать и открывать.
Интегрированная среда программирования Турбо Паскаль 6.0,7.0 позволяет иметь любое количество открытых окон, но в любой момент времени может быть активным только одно окно. Активное окно — это окно, с которым вы в настоящий момент времени работаете. Любая команда, которую вы выбрали, или текст, который вы набрали, относится только к активному окну. (Если один и тот же файл открыт в нескольких окнах, действие будет применяться к файлу везде).
Справочная система Турбо Паскаль
Интегрированная среда программирования Турбо Паскаль 6.0, 7.0 отличается расширенными возможностями встроенной справочной системы, которая позволяет программисту не только получить контекстно-ориентированную справочную информацию, но и делать вырезки и вставки кода примеров для каждой библиотечной процедуры и функции в текст своей программы, возвратиться назад к другим экранам подсказки (клавиши Alt+Fl), воспользоваться подсказкой по справочной информации (клавиша F1, если вы уже находитесь в системе справочной информации).
Примечание. Название контекстно-ориентированная справочная система Турбо Паскаль получила за возможность получения справочной информации, связанной с текущим состоянием среды программирования, по указанному элементу языка программирования. Например, для получения справочной информации о любом пункте меню интегрированной среды программирования активизируйте этот пункт и нажмите клавишу F1; для получения справки по элементу языка в окне редактирования (оператору, функции и т.п) установите курсор на нужном элементе и нажмите клавиши Ctrl+F1.
Для получения справочной информации (за исключением случаев, когда управление переходит к вашей программе) нужно нажать клавишу F1 или отметить мышью нужный пункт меню Help. Меню Help (клавиша Alt+H) обеспечивает вас таблицей содержания системы справочной информации, подробным оглавлением, способностями поиска (Ctrl+F1). Любой экран справочной информации может содержать одно ключевое слово или несколько ключевых слов (высвеченных элементов), по которым можно получить дополнительную справочную информацию.
Редактор интегрированной среды
Составной частью интегрированной среды разработки программ является редактор Турбо Паскаль, который имеет следующие возможности:
- поддержку мыши;
- поддержку больших файлов (до 1 Мбайта; ограничение в 2 Мбайта для всех комбинаций редактора);
- Shift + клавиши со стрелками — для выбора текста;
- окна редактора, которые можно передвигать, перекрывать и изменять в размере;
- мультифайловые возможности, что позволяет открывать несколько файлов одновременно;
- многочисленные окна, позволяющие иметь несколько представлений одного и того же файла или разных файлов;
- разумный макроязык, позволяющий создавать свои собственные команды редактирования;
- брать текст или примеры из окна справочной информации;
- редактируемый карман, допускающий вырезание, копирование и его передачу между окнами.
Для управления редактором используются клавиши, описанные в справочной системе и строке подсказки.
Средства для трансляции программ и их отладки
Интегрированная система программирования Турбо Паскаль включает в себя средства для трансляции программ и их отладки (компилятор, компоновщик, отладчик). Быстрое управление этими средствами с помощью "горячих клавиш", описанных в справочной системе и пунктах подменю.
Ввод текста программы в окне редактора
Для запуска среды программирования Турбо Паскаль введите команду TURBO и нажмите Enter. После запуска программы на экране раскроется окно редактирования. Введите текст программы. Для удаления неверно введенных символов используйте Backspace и Delete, а для перемещения внутри окна редактора используйте клавиши со стрелками. Для завершения ввода нажимайте Enter в конце каждой строки. Для использования дополнительных возможностей нажатием клавиш Alt+Fl вызывайте локальное меню.
Компиляция программы
Выполните компиляцию программы, для чего нажмите Alt+F9. Если вы ввели текст правильно, то на экран будет выведено сообщение об успешности компиляции.
Создание .ехе-файла
В ответ на сообщение "Compile successful" (компиляция успешна) нажмите любую клавишу.
Если вам требуется записать программу как исполняемый файл (с расширением .ехе) на магнитный диск, то выберите в главном меню пункт Compile, в котором выберите опцию Destination (назначение), и если справа от нее стоит слово Memory (память), указывающее, что выполняемый код будет храниться в памяти, нажмите клавишу Enter или щелкните левую кнопку мыши (при этом установка назначения изменится и станет Disk (диск).
Если опция Destination установлена в Disk, что указывает на запись выполняемого кода на магнитный диск в виде файла с расширением .ехе, то перейдите к опции Make этого пункта меню.
После установки назначения для создания .ехе-файла на магнитном диске выберите в меню Compile опцию Make (сборка) или нажмите клавишу F9. При этом выполняется создание .ехе-файла на диске.
Исполнение программы
В ответ на сообщение "Compile successful" (компиляция успешна) нажмите любую клавишу. Запустите программу на исполнение клавишами Ctrl+F9. После этого раскроется экран пользователя, и на нем появится результат работы программы.
Просмотр выполнения программы на экране пользователя
Чтобы посмотреть результат выполнения программы на экране пользователя, выберите Window/User Screen (или нажмите Alt+F5).
Изучите информацию, выведенную программой на экран пользователя, сопоставьте ее с ожидаемой и оцените правильность выполнения программы. Для возврата в среду Турбо Паскаль снова нажмите клавиши Alt+F5.
Сохранение программы на диске
Пока файл текста первой программы имеет имя NONAMEOO, т. е. ему не присвоено конкретного имени. Сохраните текст программы на диске. Имя программного файла должно отражать назначение программы и быть уникальным.
Примечание, Имя программы задается в соответствии с правилами DOS (не более 8 символов латинского регистра).
Запишите программу на диск под нужным именем, для чего клавишами Alt+F перейдите в File-меню, выберите пункт "Save as ..." (записать под новым именем).
Завершение работы в интегрированной среде программирования
Завершите работу интегрированной среды программирования Турбо Паскаль, для чего клавишами Alt+F перейдите в File-меню, в этом меню выберите пункт "Exit" или нажмите Alt+X.
Открытие файла текста программы
Запустите интегрированную среду программирования Турбо Паскаль и считайте файл с текстом программы, для чего клавишами Alt+F перейдите в File-меню, выберите пункт "Open" (открыть файл) или нажмите клавишу F3. На экран компьютера будет выведено окно выбора открываемого файла из списка.
Нажимая клавиши Tab или Shift+Tab для перехода от одного элемента к другому (каждый элемент, когда он становится активным, высвечивается), перейдите к окну списка Files и установите текущим директорий D:\BORLAND\ BPVTUTOR, из которого нужно считать файл текста программы. Установите курсор (подсветите) файл .PAS, после этого нажатием клавиши Tab выберите кнопку [Open]. Если вы передумали, то выберите кнопку [Cancel] или нажмите клавишу Esc.
Получение справочной информации по редактору
Для получения справочной информации по операциям редактирования клавишей F1 вызовите экран подсказки; нажимая клавишу PageDown, перейдите к перечню подсказок о функциях редактирования.
Ошибки, обнаруженные при компиляции
Часто по результатам компиляции на экран компьютера выводится сообщение об ошибке. Это объясняется тем, что язык программирования Паскаль имеет грамматические правила, которые нужно выполнять. Наиболее частыми ошибками начинающих программистов на языке Паскаль бывают:
Unknown identifier (неизвестный идентификатор)
или
';' expected (ожидается ';')
и другие.
Типы данных
Данные суть факты, идеи, сведения, представленные в знаковой (символьной) форме, позволяющей производить их передачу, обработку и интерпретацию (т.е. толкование, объяснение, раскрытие смысла), а информация— это смысл, который человек приписывает данным на основании известных ему правил представления в них фактов, идей, сообщений. Такое понимание информации соответствует и этимологии обозначающего его слова (от лат. information — разъяснение, изложение).
С дискретностью семантической информации тесно связана и ее структура, которая имеет явно выраженный иерархический характер. В этой структуре также можно различать содержательный и формальный аспекты. При рассмотрении обоих аспектов видно, что чем выше уровень иерархии, тем большую специфику имеет класс информации. В содержательной структуре это связано с ростом кумулятивности информации. Такими классами служат:
- факты;
- гипотезы, теории и концепции;
- основы областей знания;
- мировоззрение.
Формальная структура данных семантической информации так же иерархична, как и содержательная. Низшие уровни этой иерархии являются общими для всех данных семантической информации, в которой можно выделить звуки или буквы, слова, фразы, смысловые фрагменты, произведения. На высших уровнях иерархии, при обращении к научным документам и, особенно, к их потокам мы сталкиваемся со спецификой, присущей одной лишь научной информации. Мотивы создания научных документов, пути и способы их распространения и использования находятся в сфере действия особых закономерностей.
Структурированная информация, т.е. связанная причинно-следственными и иными отношениями и образующая систему, составляет знания. Из этих толкований следует, что если данные воспринимаются и интерпретируются человеком, то они становятся для него информацией. Данные в определенной степени подобны письменному сообщению, передающему какие-то сведения грамотному человеку и остающиеся набором непонятных знаков для неграмотного.
Тип данных характеризует область определения значений данных.
Напомним, что к базовым типам относятся:
- целочисленный тип;
- действительный тип;
- логический тип;
- символьный тип;
- строковый тип.
К простым типам относятся:
- порядковый тип;
- перечислимый тип.
К структурированным типам относятся:
- множества;
- массивы;
- записи;
- файлы;
- объектный тип (тип класса);
- тип ссылки на класс.
Простые типы (simple types) включают в себя перечисляемые (ordinal types) и действительные (real types) типы, которые определяют упорядоченные наборы значений. К перечисляемым типам относятся данные, для которых верным является следующее правило: каждое значение кроме первого имеет уникального предшественника, а каждое значение кроме последнего имеет уникального преемника.
Структурированные типы (structured types) данных позволяют определить переменные, которые могут хранить наборы однотипных или разнотипных данных. К структурированным типам можно отнести множества (sets), массивы (array), записи (record), а также файловые (file), классовые (class) и интерфейсные (interface) типы.
В отличие от простых типов, которые определяются линейно, структурированные типы могут иметь сложную структуру, то есть включать в себя другие типы.