Лекции по конструированию компиляторов глава 6 контекстные условия языков программирования


Содержание

Основы компиляторов

Основные задачи компиляторов

Компьютеры сами по себе способны выполнять только очень ограниченный набор операций, называемых машинными кодами. В старые времена, когда появились первые компьютеры, программы писались в машинных кодах, представляющих собой последовательности двоичных чисел, однозначно воспринимаемых компьютером. В конце 50-х кодов прошлого века появились первые языки программирования, такие как язык ассемблера и Фортран. Для того, чтобы компьютер мог понять программу, написанную на каком-то языке программирования, необходим переводчик ( транслятор ) такой программы в машинные коды. Отметим, что, если оператор языка ассемблера отображается при трансляции чаще всего 1 Некоторые операторы языка ассемблера, например, такие, как операторы ввода/вывода, отображаются в несколько машинных команд. в одну машинную инструкцию, предложения языков более высокого уровня отображаются, вообще говоря, в несколько машинных инструкций.

Трансляторы бывают двух типов: компиляторы ( compiler ) и интерпретаторы ( interpreter ). Процесс компиляции состоит из двух частей: анализа ( analysis ) и синтеза ( synthesis ). Анализирующая часть компилятора разбивает исходную программу на составляющие ее элементы (конструкции языка) и создает промежуточное представление исходной программы. Синтезирующая часть из промежуточного представления создает новую программу, которую компьютер в состоянии понять. Такая программа называется объектной программой. Объектная программа может в дальнейшем выполняться без перетрансляции. В качестве промежуточного представления обычно используются деревья, в частности, так называемые деревья разбора. Под деревом разбора понимается дерево , каждый узел которого соответствует некоторой операции , а сыновья этого узла — операндам.

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

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

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

В том случае, если исходный язык достаточно прост (например, если это язык ассемблера или Basic ), то никакое промежуточное представление не нужно, и тогда интерпретатор — это простой цикл . Он выбирает очередную инструкцию языка из входного потока, анализирует и выполняет ее. Затем выбирается следующая инструкция . Этот процесс продолжается до тех пор, пока не будут выполнены все инструкции, либо пока не встретится инструкция , означающая окончание процесса интерпретации.

Компилятор

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

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

Существует огромное количество различных языков программирования, начиная с таких традиционных языков программирования как Fortran и Pascal и кончая современными объектно-ориентированными языками такими, как C# и Java . Практически каждый язык программирования имеет какие-то особенности с точки зрения создателя транслятора. Однако мы начнем с рассмотрения разнообразных целевых языков компиляторов.

Тема 7.Основные конструкции программирования. Структурное программирование. Процедурное программирование. Объектно-ориентированное программирование

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

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

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

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

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

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

Структу́рное программи́рование — методология разработки программногообеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.

В соответствии с данной методологией

1. Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

o последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

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

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

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

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

3. Разработка программы ведётся пошагово, методом «сверху вниз».

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

Функциональное программирование объединяет разные подходы к определению процессов вычисления на основе достаточно строгих абстрактных понятий и методов символьной обработки данных. Сформулированная Джоном Мак-Карти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов XX века. Выбирая лямбда-исчисление как теоретическую модель, Мак-Карти предложил рассматривать функции как общее базовое понятие, к которому достаточно естественно могут быть сведены все другие понятия, возникающие при программировании. Существуют различия в понимании функции в математике и функции в программировании, вследствие чего нельзя отнести Си-подобные языки к функциональным, использующим менее строгое понятие. Функция в математике не может изменить вызывающее её окружение и запомнить результаты своей работы, а только предоставляет результат вычисления функции.

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

Процедурный язык программирования предоставляет возможность программисту определять каждый шаг в процессе решения задачи. Особенность таких языков программирования состоит в том, что задачи разбиваются на шаги и решаются шаг за шагом. Используя процедурный язык, программист определяет языковые конструкции для выполнения последовательности алгоритмических шагов. Процедурные языки программирования Ada,Basic, Си, КОБОЛ, Фортран, Модула-2, HAL/S, Pascal, ПЛ/1, Рапира, REXX.

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

К динамическим языкам относятся: Perl, Tcl, Python, PHP, Ruby, Smalltalk, JavaScript. Visual Basic также обладает некоторыми динамическими чертами.

Объектно-ориентированныйязык программирования (ОО-язык) — язык, построенный на принципах объектно-ориентированного программирования.

В основе концепции объектно-ориентированного программирования лежит понятие объекта — некоей субстанции, которая объединяет в себе поля (данные) и методы (выполняемые объектом действия).

Не нашли то, что искали? Воспользуйтесь поиском:

Конструирование транслятора для модельного языка

Основные методы описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта. Разработка алгоритма решения задачи. Лексический и синтаксический анализатор, семантический анализ. Структурная организация данных.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 12.06.2011
Размер файла 680,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Министерство образование Российской Федерации

Федеральное агентство образования

Государственное образовательное учреждение

высшего профессионального образования

«Оренбургский Государственный Университет»

Кафедра администрирования информационных систем

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

Конструирование транслятора для модельного языка

Введение

Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма «творческим» процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от «творчества» к «науке». Именно благодаря этому, стало возможным появление сотен новых языков программирования.

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

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

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

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

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

1. Постановка задачи к курсовой работе

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

2. В соответствии с номером варианта составить формальное описание модельного языка программирования с помощью:

а) РБНФ;

б) диаграмм Вирта;

в) формальных грамматик.

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

4. Составить таблицы лексем для тестовых примеров из п.3.

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

6. Вывести примеры таблиц идентификаторов и чисел.

7. Реализовать синтаксический анализатор текста программы на модельном языке методом рекурсивного спуска.

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

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

10. Показать динамику изменения содержимого стека при семантическом анализе программы на примере одного синтаксически правильного выражения.

11. Записать правила вывода грамматики с действиями по переводу в ПОЛИЗ программы на модельном языке.

12. Пополнить разработанное программное средство процедурами, реализующими генерацию внутреннего представления введенной программы в форме ПОЛИЗа.

13. Разработать интерпретатор ПОЛИЗа программы на модельном языке.

14. Составить набор контрольных примеров, демонстрирующих:

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

б) перевод в ПОЛИЗ различных конструкций языка;

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

2. Формальная модель задачи

Существуют три основных метода описания синтаксиса языков программирования: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта.

Определение 2.1. Формальной грамматикой называется четверка вида:

где VN — конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

VT — множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VT VN = ;

Р — множество правил вывода грамматики, являющееся конечным подмножеством множества (VT VN) + (VT VN) * ; элемент ( , ) множества Р называется правилом вывода и записывается в виде (читается: «из цепочки выводится цепочка »);

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

Формы Бэкуса-Наура (БНФ)

Метаязык, предложенный Бэкусом и Науром, использует следующие обозначения:

— символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);

— нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки « »;

— терминалы — это символы, используемые в описываемом языке;

— правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).

Расширенные формы Бэкуса-Наура (РБНФ)

Для повышения удобства и компактности описаний, в РБНФ вводятся следующие дополнительные конструкции (метасимволы):

— квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

— фигурные скобки «<» и «>» означают повторение заключенной в них синтаксической конструкции ноль или более раз;

— сочетание фигурных скобок и косой черты «» используется для обозначения повторения один и более раз;

— круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.

В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 2.1.

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

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

— каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

— альтернативы в правилах задаются ветвлением дуг, а итерации — их слиянием;

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

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

Размещено на http://www.allbest.ru/

::= WHILE DO ENDWHILE

Опишем РБНФ с помощью формальной грамматики, согласно принятым обозначениям металингвистических переменных нетерминалами формальной грамматики (таблица 1).

C > 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Таблица 1 — Соответствия металингвистических переменных РБНФ и нетерминалов формальной грамматики

3. Разработка алгоритма решения задачи

3.1 Лексический анализатор


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


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


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

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

В процедурных языках лексемы делятся на классы:

1 — служебные слова;

и помещаются в таблицу лексем с соответствующими номерами.

Так, что лексема представляется парой чисел (n,k), где n — номер таблицы, k — номер лексемы в этой таблице.

Приведем один из алгоритмов реализации лексического анализатора:

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

Выход: файл лексем, таблица идентификаторов, сообщение об ошибке.

1. открыть файл транслируемой программы и считать i-тую строку;

2. в исходной строке считываем символы в новую строку s до тех пор, пока не встретится пробел, либо ограничитель.

3. проверяем, принадлежит ли полученная строка s таблице служебных слов, если да то к пункту 4, иначе к пункту 5.

4. записываем в таблице лексем числа k1, k2, k3, где k1 — номер лексемы в таблице, где k2 — номер таблицы, k3 — номер строки в транслируемой программе.

5. проверяем, является ли s идентификатором. Если да, то записываем информацию в файл лексем, согласно пункту 4, и записываем s в таблицу идентификаторов.

6. если s[j] принадлежит таблице ограничителей, то проверяем, является ли следующий за ним символ ограничителем. Если да, то записываем в новую строку str символы s[j], пока они являются ограничителями. Далее сравниваем строку str с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту 4. Иначе сравниваем символ s[j] с ограничителями, если находятся равные, то записываем в файл лексем согласно пункту

8. если конец строки, то i:=i+1, к пункту 1.

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

3.2 Синтаксический анализатор


Рассмотрим простейший пример программы на модельном языке:


Пример 1


Begin


Составим для примера1 цепочку вывода:


P1 D2B Integer i;B Integer D<,D>;B Integer i<,B1>;B Integer i,n;B Integer i,n; Begin S1 End Integer i,n; Begin D:=V1; End Integer i,n; Begin i:=V1; End Integer i,n; Begin i:=[ _ ]V; End Integer i,n; Begin i:=P; End Integer i,n; Begin i:=M; End Integer i,n; Begin i:=D; End Integer i,n; Begin i:=i; End Integer i,n; Begin i:=i + P; End Integer i,n; Begin i:=i + M; End Integer i,n; Begin i:=i + K; End Integer i,n; Begin i:=i + 1; End


Построим дерево вывода для данного примера1 (рисунок 1).

Размещено на http://www.allbest.ru/

Рисунок 1 — дерево разбора для примера1


Для синтаксического разбора используются КС-грамматика (контекстно-свободная грамматика).


Разбор по КС-грамматикам можно реализовать различными способами.


Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method) .


— для каждого нетерминала грамматики создается своя процедура, носящая его имя;


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


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


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


Метод рекурсивного спуска


Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид:


a) либо , где и это единственное правило вывода для этого нетерминала, где V- множество терминалов, N- множество нетерминалов;


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


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


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


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


Общий вид этих правил:


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


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


Procedure L;


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


3) если в грамматике есть нетерминал, у которого несколько правил вывода, и среди них есть правила, начинающиеся нетерминальными символами, т.е. имеют вид


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


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


Алгоритм решения задачи


Входные данные СиА — файл лексем (построенный на этапе лексического анализа)


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


Алгоритм:


1. для каждого нетерминала грамматики создаем рекурсивную процедуру. Самой первой процедурой синтаксического анализатора является процедура Рroc_P1, внутри нее расположены процедуры D2 и B, которые вызываются поочерёдно в зависимости от их расположения


2. открываем файл лексем, созданный на этапе лексического анализатора


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


4. при несоответствии считанной лексемы терминалу выдается сообщение об ошибке


5. при успешном распознавании цепочки выдается сообщение об отсутствии ошибок в синтаксисе программы


3.3 Семантический анализ


Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:


1) обработка описаний;


2) анализ выражений;


3) проверка правильности операторов.


В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно.


Обработка описаний


Анализ выражений


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


Проверка правильности операторов


1) выяснить, все ли переменные, встречающиеся в операторах, описаны;


2) установить соответствие типов в операторе присваивания слева и справа от символа «:=»;


3) определить, является ли выражение V2 в операторе цикла целым.


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


Рассмотрим алгоритм решения данной задачи


1)Реализуем обработку описаний следующим образом:


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


2) Реализуем анализ выражений следующим образом:


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

4. Спецификация основных процедур и функций

4.1 Лексический анализатор

Таблица 2 — Основные процедуры и функции

Описание входных данных

Описание выходных данных

Заполнение таблиц служебных слов

Заполнение таблиц ограничителей

Вывод примера программы

Sender: TObject, файл лексем

Сообщение об ошибке, сообщение о правильности программы

Таблица идентификаторов ,таблица цифр, и файл лексем

4.2 Синтаксический анализатор

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

Таблица 3 — Основные процедуры и функции

Описание входных данных

Описание выходных данных

Реализует переход на следующий символ

Синтаксический анализ программы

Сообщение об ошибке или об отсутствии синтаксических ошибок

Главная процедура рекурсивного спуска

Строка лексем k1,k2, k3 из файла лексем

Реализует проверку входных данных

Строка лексем k1,k2, k3 из файла лексем

Реализует проверку тела проверяемой программы

Строка лексем k1,k2, k3 из файла лексем

Реализует проверку выражений

Строка лексем k1,k2, k3 из файла лексем

Реализует проверку на унарн. Минус

Реализует проверку подвыражений

Реализует проверку логическогого выражения

Реализует проверку цикла

Реализует проверку множителей

Реализует проверку произведений

Реализует проверку описания входных данных

проверку списков операторов

Реализует переход на предыдущую лексему

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

Таблица 4 — Основные процедуры и функции

Описание входных данных

Описание выходных данных

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

Реализует проверку на дубликат идентификатора

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

5. Структурная организация данных

5.1 Спецификация входных данных


5.1.1 Этап лексического анализа

Для исходного языка представим несколько примеров программ.

Таблица 7 — Спецификации входных данных лексического анализа

WHILE i | = | = в строке

нет идентификатора в строке

Сообщение о выполнении синтаксического анализа

Успешно выполнен анализ

5.2.3 Этап семантического анализа

На этапе семантического анализа возможны сообщения об ошибке (таблица 10).

Таблица 10 -Сообщения об ошибке на этапе семантического анализа

Сообщения об ошибке

Данный идентификатор уже объявлен

6. Установка и эксплуатация программного средства

Cистемные требования (минимум)

1. 1.5 Мб свободного пространства на жестком диске

2. 128 Мб оперативной памяти

3. 1.8 ГГц частота ядра процессора

Установка: для установки поместите папку «Анализ» в удобное для вас место на жестком диске. Эта папка содержит файлы:

10. Unit1.C++ Builder Form


Папку «sin» содержащую файлы:

10. Unit1.C++ Builder Form

7. Работа с программным средством

Для работы с данным программным средством необходимо выполнить следующие действия:

1. Откройте папку с именем «Программа».

2. Откройте приложение. Нажмите кнопки «Вывести служ. слова»: для вывода служебных слов для вывода ограничителей.

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

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

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

6. Если анализ прошел успешно то в окне приложения появится сообщение об успешном выполнении синтаксического анализа:

7. иначе выдастся сообщение об ошибке. Например:

Мы создали лексический, синтаксический и семантический анализы с заданного подмножества языка программирования TURBO PASCAL с незначительными модификациями и изменениями. Также изучили составные части, основные принципы построения и функционирования компиляторов. Разработали РБНФ, БНФ и диаграммы Вирта для данной грамматики.

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

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

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

Список использованных источников

1. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты.: Пер. с англ. — М.: Изд. дом «Вильямс», 2001. — 768с.

2. Опалева Э. А., Самойленко В. П. Языки программирования и методы трансляции. — СПб.: БХВ-Петербург, 2005. — 480 с.: ил.

3. Ишакова Е. Н. Разработка компиляторов: Методические указания к курсовой работе. — Оренбург: ГОУ ОГУ, 2005. — 50 с.

4. Афанасьев А.Н. Формальные языки и грамматики: Учебное пособие. — Ульяновск: УлГТУ, 1997. — 84с.

5. Волкова И.А., Руденко Т.В. Формальные языки и грамматики. Элементы теории трансляции. — М.: Диалог-МГУ, 1999. — 62 с.

6. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под ред. А. Матросова. — СПб: Питер, 2002. — 688с.

7. Рейуорд-Смит В. Теория формальных языков. Вводный курс: Пер. с англ. — М.: Радио и связь, 1988. — 128с.

8. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб.пособие. — М.: Финансы и статистика, 2004. — 320с.

9. Федоров В.В. Основы построения трансляторов: Учебное пособие. — Обнинск: ИАТЭ, 1995. — 105с.

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Diplom Consult.ru

Основы конструирования компиляторов

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

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

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

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

Место компилятора в программном

2 Языки и их представление

Алфавиты, цепочки и языки . . . . . . . . . . . . . . . . .

2.3 Грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.1 Формальное определение грамматики . . . . . . . . 17

2.3.2 Типы грамматик и их свойства . . . . . . . . . . . . 18

3 Лексический анализ

Регулярные множества и выражения . . . . . . . . . . . .

3.3 Алгоритмы построения конечных автоматов . . . . . . . . 29

3.3.1 Построение недетерминированного конечного автомата по регулярному выражению . . . . . . . . . . 29

3.3.2 Построение детерминированного конечного автомата по недетерминированному . . . . . . . . . 31

3.3.3 Построение детерминированного конечного автомата по регулярному выражению . . . . . . . . 32

3.3.4 Построение детерминированного конечного автомата с минимальным числом состояний . . . . 36

Регулярные множества и их представления . . . . . . . .

Конструктор лексических анализаторов LEX . . . . . . .

4 Синтаксический анализ

4.1 КС-грамматики и МП-автоматы . . . . . . . . . . . . . . . 49

4.2 Преобразования КС-грамматик . . . . . . . . . . . . . . . 54

4.3 Предсказывающий разбор сверху-вниз . . . . . . . . . . . 56

4.3.1 Алгоритм разбора сверху-вниз . . . . . . . . . . . . 56

Функции F IRST и F OLLOW . . . . . . . . . . . . . 59

4.3.3 Конструирование таблицы предсказывающего анализатора . . . . . . . . . . . . . . . . . . . . . . . . 61

4.3.4 LL(1)-грамматики . . . . . . . . . . . . . . . . . . . 62

Удаление левой рекурсии . . . . . . . . . . . . . . .

4.3.8 Восстановление после синтаксических ошибок . . .

4.4 Разбор снизу-вверх типа сдвиг-свертка . . . . . . . . . . .

4.4.1 Основа . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4.2 LR(1)-анализаторы . . . . . . . . . . . . . . . . . . 69

4.4.3 Конструирование LR(1)-таблицы . . . . . . . . . . 73

4.4.4 LR(1)-грамматики . . . . . . . . . . . . . . . . . . . 76

4.4.5 Восстановление после синтаксических ошибок . . . 79

5 Элементы теории перевода

Преобразователи с магазинной памятью . . . . . . . . . .

Синтаксически управляемый перевод . . . . . . . . . . .

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

5.2.2 Обобщенные схемы синтаксически управляемого пе-

Определение атрибутных грамматик . . . . . . . .

5.3.2 Классы атрибутных грамматик и их реализация . . 92

5.3.3 Язык описания атрибутных грамматик . . . . . . . 94

6 Проверка контекстных условий

6.1 Описание областей видимости и блочной структуры . . . . 99

6.2 Занесение в среду и поиск объектов . . . . . . . . . . . . . 101

7 Организация таблиц символов

7.1 Таблицы идентификаторов . . . . . . . . . . . . . . . . . . 109

7.2 Таблицы расстановки . . . . . . . . . . . . . . . . . . . . . 111

Таблицы расстановки со списками . . . . . . . . . . . . .

7.5 Таблицы на деревьях . . . . . . . . . . . . . . . . . . . . . 116

7.6 Реализация блочной структуры . . . . . . . . . . . . . . . 120

7.7 Сравнение методов реализации таблиц . . . . . . . . . . . 121

8 Промежуточное представление программы

8.1 Представление в виде ориентированного графа . . . . . .

8.2 Трехадресный код . . . . . . . . . . . . . . . . . . . . . . . 124

8.3 Линеаризованные представления . . . . . . . . . . . . . . 128

8.4 Виртуальная машина Java . . . . . . . . . . . . . . . . . . 130

8.4.1 Организация памяти . . . . . . . . . . . . . . . . . 131

8.4.2 Набор команд виртуальной машины . . . . . . . . . 131

8.5 Организация информации

8.6 Уровень промежуточного представления . . . . . . . . . .

9 Генерация кода

9.1 Модель машины . . . . . . . . . . . . . . . . . . . . . . . . 135

9.2 Динамическая организация памяти . . . . . . . . . . . . . 138

9.2.1 Организация магазина со статической цепочкой . . 139

9.2.2 Организация магазина с дисплеем . . . . . . . . . . 143

9.3 Назначение адресов . . . . . . . . . . . . . . . . . . . . . . 144

9.4 Трансляция переменных . . . . . . . . . . . . . . . . . . . 146

9.5 Трансляция целых выражений . . . . . . . . . . . . . . . 148

9.6 Трансляция арифметических выражений . . . . . . . . . 149

9.7 Трансляция логических выражений . . . . . . . . . . . . 158

9.8 Выделение общих подвыражений . . . . . . . . . . . . . . 165

9.9 Генерация оптимального кода методами синтаксического

9.9.1 Сопоставление образцов . . . . . . . . . . . . . . .

9.9.2 Синтаксический анализ для T-грамматик . . . . . .

9.9.3 Выбор дерева вывода наименьшей стоимости . . . .

9.9.4 Атрибутная схема для алгоритма сопоставления об-

10 Системы автоматизации построения трансляторов

1.1 Место компилятора в программном обеспечении

Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые “универсальные” языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать

о микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает боль-

ГЛАВА 1. ВВЕДЕНИЕ

шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.

Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.

1.2 Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции показаны на рис. 1.1.

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

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

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

Основная задача синтаксического анализа – разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант – рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) – при исполь-

1.2. СТРУКТУРА КОМПИЛЯТОРА

Ijhf `mlhqgZy nhjfZ

nbdkgZy ljhcdb b ^j

Ijhf `mlhqgZy nhjfZ

ГЛАВА 1. ВВЕДЕНИЕ

зовании систем автоматического построения синтаксических анализаторов.

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

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

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

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

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

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

Основы программирования. Лекции

Раздел 1. Введение в программирование

Тема 1.1. Основы алгоритмизации

Лекция№1 Алгоритмы. Свойства и способы описания линейных алгоритмов.

1. Определение алгоритма Свойства

2. Типы алгоритмов

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

Средства наглядности: презентация

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

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

— алгоритм представляет собой последовательность элементарных шагов (команд исполнителя).

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

3. Завершаемость (конечность) —

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

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

5. Массовость — применимость алгоритма ко множеству исходных данных.

Порядок выполнения алгоритма:

  1. Действия в алгоритме выполняются в порядке их записи
  2. Нельзя менять местами никакие два действия алгоритма
  3. Нельзя не закончив одного действия переходить к следующему

1.Линейные (описание действий, которые выполняются однократно в заданном порядке; имеет линейную структуру).

2.Разветвляющиеся (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);

3.Циклические (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);

4,Вспомогательные (алгоритм, который можно использовать в других алгоритмах, указав только его

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

Способы записи алгоритмов определяются исполнителем. Команды, которые может выполнять исполнитель наз. СИСТЕМОЙ КОМАНД ИСПОЛНИТЕЛЯ (СКИ). Способы записи бывают:

на естественном языке;

на специальном (формальном) языке (псевдокод);

с помощью формул, рисунков, таблиц;

с помощью стандартных графических объектов (геометрических фигур)

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

Правила оформления блок-схем можно посмотреть в ГОСТ 19.701-90.

ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения.

ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные

Каждому действию алгоритма соответствует геометрическая фигура

(блочный символ). Перечень наиболее часто употребляемых символов

приведен в таблице ниже.

Выполняемая функция (пояснение)

1. Блок вычислений

Выполняет вычислительное действие или группу действий

2. Логический блок

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

3. Блоки ввода/вывода

Ввод или вывод данных вне зависимости от физического носителя

Вывод данных на печатающее устройство

4. Начало/конец (вход/выход)

Начало или конец программы, вход или выход в подпрограмму

5. Предопределенный процесс

Вычисления по стандартной или пользовательской подпрограмме

6. Блок модификации

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

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

8. Межстраничный соединитель

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

Правила построения блок-схем:

1. Блок-схема выстраивается в одном направлении либо сверху вниз, либо слева направо

2. Все повороты соединительных линий выполняются под углом 90 градусов

Алгоритм 1. (словесное описание)

Алгоритм 2. (псевдокод)

Пример. А.2., представленный блоксхемой

1. Дайте определение алгоритма. В каких сферах человеческой

деятельности применимы алгоритмы?

2. Какие свойства алгоритмов вам известны? Объясните на примере

разработанных вами алгоритмов суть этих принципов.

3. Какие существуют формы записи алгоритмов? Опишите их

достоинства и недостатки. В каких случаях они применяются?

4.Перечислите основные правила составления алгоритмов.

Лекция№2 Составные команды (следования, ветвления, цикла)

1.Определение команды (оператора)

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

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

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

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

б) неполное ветвление а) полное ветвление

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

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

В том случае, когда условие соблюдено, продолжение исполнения алгоритма происходит по стрелке «+», в противном случае — по стрелке «—».

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

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

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

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

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

Циклические алгоритмы бывают двух типов:
Циклы со счетчиком(параметром), в которых какие-то действия выполняются определенное число раз; (безусловные циклы или арифметические циклы )
Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

Схема цикла с предусловием

Под действием, как и прежде, понимается простая или составная команда. Исполнение такой команды повторения состоит в том, что сначала проверяется условие (отсюда и название — цикл с предусловием), и если оно соблюдено, то выполняется команда, записанная после служебного слова повторять. После этого снова проверяется условие. Выполнение цикла завершается, когда условие перестает соблюдаться. Для этого необходимо, чтобы команда, выполняемая в цикле, влияла на условие. (этот тип цикла называют также циклом «пока»). . Можно сказать что условие цикла «пока» — это условие входа в цикл. В частном случае может оказаться что действие не выполнялось ни разу. Условие цикла необходимо подобрать так, чтобы действия, выполняемые в цикле, не привели к нарушению его истинности, иначе произойдет зацикливание. Зацикливание — бесконечное повторение выполняемых действий.

Схема цикла с постусловием

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

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

В общем случае схема циклического алгоритма с условием будет выглядеть так:
Пока — условие повторять — действие..Назовите правила с

Для создания циклов со счётчиком ( параметром) необходимо использовать правила:

Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа

Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра

Запрещено входить в цикл минуя блок модификации

Если начальное значение больше конечного, то шаг — число отрицательное

После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях

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

1 Дайте определение команды (оператора).

2. 3.Объясните роль условия в команде ветвления

3.Чтотакое «тело цикла» ?

4.Назовите правила создания цикла со счетчиком.

Лекция№3 Команда присваивания. Заголовок алгоритма

1.Формат команды присваивания

4. Заголовок алгоритма.

Команда присваивания — команда исполнителя, в результате которой переменная получает новое значение. Формат команды:

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

Пример.

Например, запись A:=B+5 читается так: «переменной A присвоить значение выражения B плюс 5».

Знаки присваивания «:=» и равенства «=» — разные знаки:

знак «=» означает равенство двух величин, записанных по обе стороны от этого знака;

знак «:=» предписывает выполнение операции присваивания.

Например, запись A:=A+1 выражает не равенство значений A и A+1, а указание увеличить значение переменной A на единицу.

При выполнении команды присваивания сначала вычисляется значение выражения, стоящего справа от знака «:=», затем результат присваивается переменной, стоящей слева от знака «:=». При этом тип выражения должен быть совместим с типом соответствующей переменной.

1. пока переменной не присвоено значение, она остаётся неопределённой;

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

3. если мы присваиваем некоторой переменной очередное значение, то предыдущее её значение теряется безвозвратно.

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

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

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

При описании алгоритмов не обязательно соблюдать строгие правила записи выражений, это можно делать в обычной математической форме, так как это еще не язык программирования со строгим синтаксисом. В рассматриваемом алгоритме имеется команда ввода: ввод a, b, c, d. В блок-схемах команда ввода записывается в параллелограмме — блоке ввода-вывода. При выполнении этой команды процессор прерывает работу и ожидает действий пользователя. Пользователь должен набрать на устройстве ввода (клавиатуре) значения вводимых переменных и нажать клавишу ввода. Значения следует вводить в том же порядке, в каком эти переменные рас- положены в списке ввода. Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточных и конечных величин. Полученные компьютером результаты решения задачи должны быть сообщены пользователю, для чего и предназначена команда вывода: вывод m, n. С помощью этой команды результаты выводятся на экран или через устройство печати на бумагу.

Составим алгоритм, в результате которого переменные A и B литерного типа обменяются своими значениями.


Решение вида A:=B B:=A неверно, так как после выполнения первой команды присваивания первоначальное значение переменной A будет безвозвратно утеряно. Вторая команда присвоит переменной B текущее значение переменной A. В результате обе переменные получат одно и то же значение.

Для решения исходной задачи введём промежуточную переменную M. . Тогда задачу обмена значениями можно решить последовательным выполнением трех команд присваивания. Алгоритм обмена значениями переменных A и B запишем так:

Этой задаче аналогична следующая ситуация. Имеются два стакана: один — с молоком, другой — с водой. Требуется произвести между ними обмен содержимым. Ясно, что в этом случае необходим третий стакан — пустой. Последовательность действий при обмене будет такой: 1) перелить молоко из 1-го стакана в 3-й; 2) воду из 2-го стакана в 1-й; 3) молоко из 3-го стакана во 2-й.

а) Имя алгоритма

При работе на ЭВМ принято давать имена, состоящие из не более 8 символов, без пробелов, на первом месте обязательно буква, после имени состоящем из восьми символов через точку пишется расширитель имени, состоящем из не более трех символов на первом месте обязательно буква. Например: KWUR.E, BASIC.COM,
LR4B.SC2 и т.д.
б) Список величин (входные и выходные величины) с указанием их типа.
в) аргументы (входные данные) и результаты (выходные данные).
Общий вид заголовка алгоритма работы с величинами таков:

алг имя алгоритма (список величин с указанием типов)

дано имена аргументов (имена входных величин)

надо имена результатов (имена выходных величин)

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

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

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

В общем случае переменным в условии задачи соответствуют аргументы в заголовке алгоритма.

1.Опишите порядок выполнения команды присваивания.

2.Назовите свойства присваивания.

3.Верно ли решение вида A:=B B:=A ? Почему?

4.Приведите пример заголовка алгоритма

Лекция№4 Табличные величины, виды таблиц

2. Примеры использования таблиц.

3. Табличные величины в алгоритмах.

Определение. Таблица – это упорядоченная последовательность величин одного типа, имеющая имя. Например;

Таблица умножения Пифагора;

Поля игры “Морской бой”.

Из всего многообразия таблиц можно выделить простые и сложные.

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

Сложные таблицы – это такие таблицы, которые состоят из простых.

Например, таблица “Расписание уроков на неделю”:

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

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

Рассмотрим примеры использования таблиц в практической деятельности человека.

Пример 1. На метеостанции каждый час измеряется температуры воздуха и значения измерения записываются в таблицу:

Время измерения, ч

Температура, 0 С

Эта линейная таблица содержит 24 элемента, занумерованные от 0 до 23. Второй элемент имеет значение 15,5, а нулевой элемент – 17. Время измерения в таблице имеет значение номера столбца, в котором находятся показания температуры.

Пример 2. На метеостанции вычисляют среднюю температуру воздуха каждые сутки и записывают в другую таблицу. Пусть нас интересует средняя температура с 22 по 28 апреля:

Средняя температура, 0 С

Данная линейная таблица содержит семь элементов, занумерованных от 22 до 28.

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

В первом примере таблицу можно записать так: вещтаб температура [0:23 ], во втором – вещтаб средняя температура [22:28].

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

Напримеры: вещтаб F[7:12], нат таб D[1:12], лит таб G[5:9].

G[5]:= «Петров»; G[6]:= «Иванов»; … ; G[9]:= «Курочкин».

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

Таблица S Таблица Р

наттаб S[1:4,1:4] наттаб Р[1:4,1:4]

При измерении температуры в течение месяца ежедневно каждый час данные можно вводить в таблицу:

вещтаб температура [1:31,0:23]

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

Табличные величины удобно использовать в алгоритмах. Рассмотрим примеры таких алгоритмов.

алг таблица сложения (наттаб S[1:4,1:4]) рез S начнатi,j i:=1 пока i≤4 нц j:=1 пока j≤4 нц S[i,j]:=i+j еслиS[i,j]≥5 то S[i,j]:=10+ (S[i,j]-5) все j:=j+1 кц i:=i+1 кцкон

алг таблица умножения (наттаб Р[1:4,1:4]) рез Рначнат i,j i:=1 пока i≤4 нц j:=1 пока j≤4 нц Р[i,j]:=i×jпока Р[i,j]≥5 нц Р[i,j]:= Р[i,j]-5 а:=а+1 кц Р[i,j]:=а×10+ Р[i,j]; j:=j+1 кц i:=i+1 кц кон

алг таблицы сложения и умножения (наттаб S[1:4,1:4],наттаб Р[1:4,1:4 ) рез Р,S начнат i,j i:=1 пока i≤4 нцj:=1 пока j≤4 нц a:=0 S[i,j]:=i+j Р[i,j]:=i×j пока Р[i,j]≥5нц Р[i,j]:= Р[i,j]-5 а:=а+1 кц если S[i,j]≥5 тоS[i,j]:=10+ (S[i,j]-5) все Р[i,j]:=а×10+ Р[i,j] j:=j+1 кцi:=i+1 кц кон

При сложении или умножении номера строки и столбца мы получаем число в десятичной системе счисления. 5 = 10, значит необходимо определить количество пятерок в полученной сумме или произведении. Это количество определяется в алгоритме «таблица умножения» с помощью команды повторения. В алгоритме «таблица сложения» учитывается тот факт, что 4+4=8, т.е. больше одной пятерки при сложении в сумме содержаться не может, поэтому достаточно использовать команду ветвления. Можно в обоих алгоритмах использовать команду повторения. Более того, оба эти алгоритма можно объединить в один .

Составим алгоритм для вычисления средней суточной температуры воздуха в течении месяца (Пример 4). Для удобства записи назовем таблицу «температура» одной буквой «Т». Для сохранения значений средней температуры в течении месяца создадим линейную таблицу на 31 элемент и назовем ее «С». Каждый элемент первой таблицы будет различаться по номеру строки и столбца – Т[i,j], а каждый элемент второй таблицы будет различаться по номеру столбца – С[i]. Среднесуточную температуру будем вычислять по правилу вычисления среднего арифметического, и сохранять результат в созданной нами линейной таблице.

алг среднесуточная температура (вещтаб Т[1:31,0:23], вещтаб С[1:31]) арг Т рез С начнат i,j i:=1 пока i≤31 нц j:=0 пока j≤23 нц k:=k+ T[i,j] j:=j+1 кц C[i]:=k/24 i:=i+1 кцкон

2. Примеры использования таблиц.

3. Табличные величины в алгоритмах

Лекция№5 Вспомогательные алгоритмы Тестирование ПО

5.Рекомендации по тестированию

5. Виды тестирования

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

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

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

Алгоритмический язык

Паскаль

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

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

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

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

procedure SubTest(a,b:integer; var c:real, var d:integer);

здесь параметры а и b передаются по значению, а параметры с и d — по ссылке.

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

Бейсик

Паскаль

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

Вызов функции производится в выражениях и операторах подобно стандартным функциям языка:

Реализация алгоритмов с помощью подпрограмм — процедур и функций — называется процедурным программированием. В последние годы все большую популярность приобретают методы объектного и событийного программирования.

«Тестирование программ может использоваться для демонстрации наличия ошибок,

но оно никогда не покажет их отсутствие»Эдсгер Вибе Дейкстра

Необходимо различать понятия тестирование и отладка.

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

Программа подвергается постоянному тестированию на протяжении всего процесса работы над ней.

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

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

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

3) Необходимо тестировать пред- и постусловия. Другими словами, прежде чем использовать данные в вычислениях, необходимо удостовериться в их корректности. Например, при вычислении частного двух чисел делитель не должен быть равен 0; индекс массива не должен превышать допустимый диапазон.

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

Альфа-тестирование – тестирование готового продукта на специально созданных задачах.

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

Если «альфа-» и «бета-тестирование» относятся к стадиям до выпуска продукта (а также, неявно, к объёму тестирующего сообщества и ограничениям на методы тестирования), тестирование «белого ящика» и «чёрного ящика» имеет отношение к способам, которыми тестировщик достигает цели..

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

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

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

В заключение отметим, что даже после внедрения в эксплуатацию процесс тестирования не прекращается.

5.Рекомендации по тестированию

5. Виды тестирования

Тема 1.2. Языки программирования

Лекция№6 Языки программирования, их классификация.

1. ЯП: определение, классификация.

2. История ЯП. Презентация

3. Достоинства/ недостатки ЯП.

4. Эволюция ЯП BASIC, Pascal

Средства наглядности: презентации

Язык программирования — это формализованный язык, который представляет собой совокупность алфавита, правил написания конструкций (синтаксис) и правил толкования конструкций (семантика).

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

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

Командные языки баз данных

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

Универсальные языки высокого уровня обеспечивают создание различных программ (задач), например Алгол, Си, ПЛ/1 и т.д..

Проблемно-ориентированные языки создавались под какие-то конкретные классы задач, например, Фортран — научные расчеты, Кобол — экономические расчеты, Лисп и Пролог — искусственный интеллект и т.д.

Объектно-ориентированные языки четвертого поколения (4GL — forth-generation language) и программирование основаны на создании модели системы, как совокупности объектов и использует следующие базовые понятия: класс, объект, событие, свойства объекта, метод обработки. Первым языком программирования этой группы был — Симула-67. В настоящее время к этим языкам относятся — С++, Visual Basic, Java Script и динамический HTML и другие современные языки программирования.

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

История языков программирования.

Неструктурные языки (широко использовались 40-е годы)

Оптимизация программы под аппаратную архитектуру.

Как следствие, обеспечение высокой эффективности вычислений.

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

Применение: быстрые численные расчеты, создание драйверов устройств.

Примеры языков: Ассемблеры.

Директивные (структурные) языки (появились в 50-е годы)

Повторное использование ранее написанных блоков кода.

Высокая степень независимости программы от типа вычислительной машины.

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

Некоторая потеря в скорости вычислений.

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

Примеры языков: FORTRAN, C, Pascal.

Декларативные (функциональные и логические) языки (зародились в 60-е годы)

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

Легче формализуется математическими средствами.

Как следствие, программы проще тестировать, т.е. проверять на наличие ошибок.

Высокая степень абстракции.

Снижение скорости работы программы.

Применение: доказательство теорем, возможность обработки разнородных данных.

Функциональные языки

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

Автоматическое динамическое распределение памяти компьютера для хранения данных.

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

Нелинейная структура программы, следовательно, такое программирование сложно для понимания.

Относительно невысокая эффективность вычислений.

Применение: обработка рекурсивных структур данных, обработка символьной информации.

Примеры языков: Haskell.

Логические языки

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

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

Узкий класс решаемых задач.

Применение: эмуляция искусственного интеллекта, разработка экспертных систем.

Примеры языков: Prolog.

Объектно-ориентированные языки

Программа представляет собой описание объектов, их свойств (или атрибутов), классов и отношений между ними, способов взаимодействия.

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

Использование ранее созданных библиотек классов позволяет сэкономить время.

Полиморфизм обеспечивает гибкость и универсальность программного обеспечения.

Удобство разработки ПО группой лиц.

Сложность полной формализации реального мира создает в дальнейшем трудности тестирования созданного ПО.

Применение: разработка больших пользовательских приложений.

Примеры языков (большинство современных языков программирования поддерживают концепцию объектно-ориентированного программирования): C++, Python.

Языки сценариев

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

Основные достоинства данного класса языков программирования унаследованы от объектно-ориентированных языков.

Легкость использования с инструментальными средствами автоматизированного проектирования и быстрого создания ПО.

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

Большая вероятность побочных эффектов.

Применение: интернет технологии. Примеры языков: JavaScript, Python, PHP

Эволюция ЯП BASIC, Pascal

1.ЯП: определение, классификация.

2. История ЯП. Презентация

3. Достоинства/ недостатки ЯП.

4. Эволюция ЯП BASIC, Pascal . Презентация

Лекция»7 Принципы построения ПО. Трансляторы

3. Разработка ПО

Средства наглядности: презентация

Программное обеспечение (ПО)

– (Семакин И.Г., Хеннер Е.К.) это совокупность программ, хранящихся в долговременной памяти компьютера.

ПРИМЕРЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

Системное ПО

Операционные системы: Windows, Linux и др.

Файловые менеджеры: Total Commander, FAR.

Антивирусные программы:DrWeb, Антивирус Касперского, Avast

Архиваторы:Winrar, Winzip, 7-zip

Программы обслуживания дисков: Defrag, Norton Disk Doctor

Инструментальное ПО

Системы программирования: Borland Delphi ,Borland C++ Builder, Microsoft Visual Basic , Microsoft Visual C++

Среды программирования, облегчающие разработчику создание программы: Microsoft Visual Studio.

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

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

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

Программы общего назначения: текстовые и графические редакторы, системы управления базами данных (СУБД), табличные процессоры, коммуникационные (сетевые) программы.

. Операционная система — это набор программ, управляющих оперативной памятью, процессором, внешними устройствами и файлами, ведущих диалог с пользователем .

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

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

Сервисные — Множество специальных программ обслуживающего (сервисного) характера.

Разрабо́тка ПО (англ. software development) — это род деятельности) и процесс, направленный на создание и поддержание работоспособности, качества и надежности программного обеспечения, используя технологии, методологию и практики из информатики, управления проектами, математики, инженерии и других областей знания [

Разработка ПО может быть разделена на несколько разделов. Это:

Требования к ПО (извлечение, анализ, спецификация и ратификация )

Проектирование ПО средствами Автоматизированной Разработки Программного Обеспечения (CASE) и стандарты формата описаний, такие как Унифицированный Язык Моделирования (UML), используя различные подходы: проблемно-ориентированное проектирование и т. д.

Программирование (создание ПО с помощью языков программирования)

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

Управление конфигурацией ПО (стандартизированный и структурированный методы)

Инструменты разработки ПО, см. CASE: методика оценки сложности системы, выбора средств разработки и применения программной системы.

Качество программного обеспечения: методика оценки критериев качества программного продукта и требований к надёжности.

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

Участники процесса разработки ПО: пользователь, заказчик, разработчик, руководитель проекта, аналитик, тестировщик, поставщик.

Трансляторы

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

Интерпретатор переводит каждую команду программы с одновременным её выполнением и, если обнаруживает ошибку, сообщает о ней и прекращает выполнение программы.

Компилятор переводит всю программу целиком и в конце работы выдаёт список ошибок, если они обнаружены.

Трансляция — процесс перевода программы, написанной на алгоритмическом языке, на машинный язык (в коды компьютера).

Транслятор — программа-переводчик.

Компиляция: процесс трансляции и выполнения программы четко разделены во времени.

Интерпретация: последовательно чередуются перевод группы инструкций языка в коды и их выполнение

Компиляция выгодней по времени выполнения и памяти.

Интерпретация удобней для организации диалоговых программ.

По типу выходных данных различают два основных вида трансляторов:

компилирующие окончательный выполнимый код;

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

Окончательным выполнимым кодом являются приложения, реализованные как EXE-файлы, DLL-библиотеки, COM-компоненты. К интерпретируемому коду можно отнести байт-код JAVA-программ, выполняемый посредством виртуальной машины JVM.

Языки, формирующие окончательный выполнимый код, называются компилируемыми языками (С, C++, FORTRAN, Pascal). Языки, реализующие интерпретируемый код, называются интерпретируемыми языками(Java, LISP, Perl, Prolog).

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

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

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

Рис. 2.1. Основные этапы трансляции программы

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

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

К наиболее общим задачам, решаемым семантическим анализатором, относятся:

обнаружение ошибок времени компиляции;

заполнение таблицы символов конкретными значениями;

замена макросов их определениями;

выполнение директив времени компиляции.

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

На фазе синтеза программы производится: генерация кода; редактирование связей.

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

Так, процесс генерации кода.

3. Разработка ПО

5. Трансляция Презентация

Тема1.2 ЯП

Лекция№ 8 Стадии разработки программного продукта. Этапы решения задач на ПК.

  1. Постановка задачи
  2. Анализ
  3. Проектирование
  4. Программирование
  5. Оформление документации
  6. Испытания Эксплуатация
  7. Этапы решения задачи на ЭВМ.

При разработке программного продукта можно выделить следующие стадии:

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

Часто её называют стадией постановки задачи., чтобы позволить программисту или аналитику однозначно определить, что будет делать создаваемая программа. Постановка решаемой на компьютере задачи должна включать список ее входных данных, список требуемых результатов и любые инструкции (правила), которых нужно следовать при решении задачи. В результате согласования между заказчиком и исполнителем всех перечисленных вопросов составляют техническое задание (ТЗ) в соответствии с ГОСТ 19.201-78, которое служит основанием для дальнейшей работы.

Стадия технического предложения (анализ)— определение методов решения задачи.

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

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

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

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

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

При определении структуры данных с каждым объектом данных должно быть связано осмысленное имя или идентификатор. При разработке программы идентификаторы будут связаны с расположением данных в памяти.

На данной стадии разрабатываются и оцениваются алгоритмы подпрограмм.

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

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

Пример 1

find_area (Найти площадь),

calc_balance (Вычислить_баланс)


prepare_fit (Подготовить_декларацию)

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

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

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

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

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

Отлаженная программа подвергается тестированию. Тестирование — это процесс выполнения программы при различных наборах данных с целью обнаружения логических ошибок. Для поиска логических ошибок также можно использовать отладчик: по шагам отследить процесс получения результатов.

Документация должна включать: описание постановки задачи; описание анализа задачи; описание определения структуры данных;

описание алгоритма; текст программы с комментариями;

тесты с входными и выходными данными; записи о процедурах внедрения;

руководство пользователя; записи о всех модификациях.

Стадии испытаний и внедрения в эксплуатацию — всестороннее тестирование программы и сопровождение при внедрении в эксплуатацию.

Эргономические цели и показатели качества программного продукта

Эргономика включается в процессы разработки и тестирования программного продукта как часть системы качества. Разработка пользовательского интерфейса (ПИ) ведется параллельно дизайну программного продукта в целом и в основном предшествует его осуществлению.
Графический интерфейс пользователя ( англ. graphical user interface, GUI – система средств для взаимодействия пользователя с компьютером.
С точки зрения эргономики, самое важное в программе — создать такой пользовательский интерфейс, который сделает работу эффективной и производительной, а также обеспечит удовлетворенность пользователя от работы с программой.

Этапы решения задачи на ЭВМ.

Работа по решению любой задачи с использованием компьютера включает в себя следующие шесть этапов: 1.постановка задачи, 2.формализация задачи, 3.построение алгоритма, 4.составление программы на языке программирования, 5.отладка и 6.тестирование программы.

6. Проведение расчетов и анализ полученных результатов.

Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ (непосредственно к программированию из этого списка относятся п. 3 … 5).

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

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

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

  1. Постановка задачи
  2. Анализ
  3. Проектирование
  4. Программирование
  5. Оформление документации
  6. Испытания Экксплуатация
  7. Этапы решения задачи на ЭВМ.

Лекция №9 Величины. Типы данных.

  1. Константы и переменные
  2. Простые и структурированные типы данных

3. Основные типы данных

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

Всякая величина занимает свое определенное место в памяти ЭВМ ( ячейку памяти). тип. В алгоритмах и языках программирования величины подразделяются на констан-ты и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, True и др. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются в алгоритме символическими именами — идентификаторами, например: X, S2, cod15 и др. Любые константы и переменные занимают ячейку памяти, а значения этих величин определяются двоичным кодом в этой ячейке.

Типы величин: целые, вещественные, логические и символьные Это понятие является фундаментальным в программировании.

Рис. 1.1. Уровни данных относительно программы

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

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных. По структуре данные подразделяются на простые и структурированные. Для простых величин, называемых также скалярными, справедливо утверждение одна величина — одно значение, а для структурированных — одна величина — множество значений.

таблица 1.1. Основные типы данных

К структурированным величинам относятся массивы, строки, множества и др.

Любые данные ТП характеризуются своими типами. Тип определяет:

  1. Формат представления данных в памяти компьютера
  2. Множество допустимых значений, принимаемое переменной или константой, принадлежащей к выбранному типу
  3. Множество допустимых операций применимых к этому типу

Тип переменной определяется при ее декларации. Одна из базовых концепций Паскаля заключается в жесткой проверке соответствия типов в операциях присваивания.
Типы данных в языке ТП делятся на 5 основных классов:

  1. Простые типы
  2. Структурированные типы
  3. Ссылочные типы
  4. Процедурные типы
  5. Объектные типы

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

В TP имеется 5 предопределенных, целочисленных типов. Каждый тип обозначает определенное подмножество целых чисел:

Короткое целое shortint

8 бит со знаком

16 бит со знаком

Длинное целое longint

32 бита со знаком

Длиной в байт byte

8 бит без знака

Длиной в слово word

16 бит без знака

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

К логическим типам относятся данные типов Boolean, ByteBool, WordBool, LongBool.
Значением каждого данного логического типа могут являться 2 значения: TRUE (1) и FALSE (0).
Для данных логического типа применимы только две операции сравнения: равно и не равно.
Переменные типа Boolean и ByteBool занимают один байт; переменная WordBool — 2 байта.
Интервальный тип данных определяется посредством задания подмножества значений одного из ранее определенных типов. Можно использовать все простые типы, за исключением вещественного. При задании диапазона указывается наименьшее и наибольшее значения, разделенные двумя точками. При этом оба значения обязательно одного типа.
К вещественному типу относится подмножество вещественных чисел, представленных в формате с плавающей точкой и фиксированным числом цифр.
В ТП имеется 5 видов вещественных типов:

2.9*10 -39 ..1.7*10 38

Single (с одинарной точностью)

1.5*10 -45 ..3.4*10 38

Double (с двойной точностью)

5.0*10 -324 ..1.7*10 308

Extended (с повышенной точностью)

3.4*10 -4932 ..1.1*10 4932

-9.2*10 18 ..9.2*10 18

Действия над типами с одинарной, двойной, повышенной точностью и сложным типом могут выполняться только при наличии числового сопроцессора. Поэтому считается что постоянно доступным является только тип Real.

  1. Константы и переменные
  2. Простые и структурированные типы данных

3. Основные типы данных

Раздел 2. Основные конструкции языков программирования

Тема 2.1. Операторы языка программирования

Лекция№10 Синтаксис языка. Арифметические выражения

  1. Описание синтаксиса языка
  2. Синтаксические определения
  3. Арифметические выражения

Язык программирования — это формализованный язык, который представляет собой совокупность алфавита, правил написания конструкций (синтаксис) и правил толкования конструкций (семантика).

Описание синтаксиса языка включает определение алфавита и правил построения различных конструкций языка из символов алфавита и более простых конструкций. Для этого обычно используют форму Бэкуса-Наура (БНФ) или синтаксические диаграммы.

СИМВОЛЫ языка-это основные неделимые знаки, в терминах которых пишутся все тексты на языке.

ЭЛЕМЕНТАРНЫЕ КОНСТРУКЦИИ -это минимальные единицы языка, имеющие

самостоятельный смысл. Они образуются из основных символов языка.

ВЫРАЖЕНИЕ в алгоритмическом языке состоит из элементарных конструкций и символов, оно задает правило вычисления некоторого значения.

ОПЕРАТОР задает полное описание некоторого действия, которое необходимо выполнить. Для описания сложного действия может потребоваться

группа операторов. В этом случае операторы объединяются в СОСТАВНОЙ

ОПЕРАТОР или БЛОК.

Действия, заданные операторами, выполняются над ДАННЫМИ. Предложения алгоритмического языка, в которых даются сведения о типах данных,

называются ОПИСАНИЯМИ или неисполняемыми операторами.

Объединенная единым алгоритмом совокупность описаний и операторов образует ПРОГРАММУ на алгоритмическом языке.

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

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

изучаемого языка — МЕТАЯЗЫКОМ.

Синтаксические определения могут быть заданы формальными или неформальным способами. Существуют три формальных способа:

-металингвистическая символика, называемая Бэкуса-Наура формулами;

О С Н О В Н Ы Е С И М В О Л Ы

Основные символы языка-буквы, цифры и специальные символы-состав-

ляют его алфавит. ТУРБО ПАСКАЛЬ включает следующий набор основных

1) 26 латинских строчных и 26 латинских прописных букв:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

a b c d e f g h i j k l m n o p q r s t u v w x y z

2) _ подчеркивание

0 1 2 3 4 5 6 7 8 9

4) знаки операций:

7) служебные (зарезервированные) слова:

ABSOLUTE EXPORTS LIBRARY SET

ASSEMBLER EXTERNAL MOD SHL

AND FAR NAME SHR…

Кроме перечисленных, в набор основных символов входит пробел. Про-

белы нельзя использовать внутри сдвоенных символов и зарезервирован-

Э Л Е М Е Н Т А Р Н Ы Е К О Н С Т Р У К Ц И И

Элементарные конструкции языка ПАСКАЛЬ включают в себя имена, чис-

называют терминалами (лексемами) — это «конечные символы», т.е. по умолчанию известные в ЯП.

так называемый нетерминал (нетерминальный символ).

Он определяется через терминалы, другие нетерминалы и самого себя. Причем в последнем случае правило задания нетерминала называется рекурсивным (как определение нетерминала ) РБНФ (Расширенные БНФ)

[] — 0 или 1 повторение.

<> — 0 и более повторений

Грамматика языка — совокупность всех синтаксических правил данного ЯП, обычно заданных в форме БНФ.

Грамматика не учитывает все виды ошибок, в ЯП формулируются дополнительные семантические правила.

ключевые слова (begin, end, if, for)

идентификаторы (a, b1)

константы (2, ‘ABC’, #5)

комментарии (3 вида)

Переменные и их описание

Переменная — это ячейка памяти компьютера, имеющая имя и тип.

Тип определяет размер переменной и множество принимаемых ею значений.

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

Синтаксис в виде РБНФ

Пример секции описания переменных.

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

В арифметических выражениях если a и b — одного типа, то и a op b принадлежит к тому же типу. Исключением является операция «/»:

a / b — вещественное.

Если a и b принадлежат к различным типам, то выражение принадлежит к «старшему» типу. Например:

В арифметические выражения могут входить стандартные функции:

Порядок выполнения операций в арифметических выражениях

Операции с большим приоритетом выполняются первыми

Функции вычисляются до операций

Выражение в скобках вычисляется раньше

Операции с одинаковым приоритетом выполняются слева направо, если идут подряд. Операции div и mod для целых

x div y = x / y, округленное до ближайшего целого по направлению к нулю. Это результат от целочисленного деления. x mod y = x ‐ (x div y) * y. Это остаток от целочисленного деления.

Целочисленные операции часто применяются для определения четности числа:

  1. Описание синтаксиса языка
  2. Синтаксические определения
  3. Арифметические выражения

Раздел 2 Тема 2.1

Лекция№ 11 Ввод и вывод данных.

1.Синтаксис и семантика оператора ввода

2. Обработка ошибок ввода

3. Синтаксис и семантика оператора вывода

4. Форматы вывода

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

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

Происходит считывание данных с клавиатуры и запись их в переменные из где — это последовательность имен переменных, разделенных запятыми. Слово read переводится как читать(Точнее говоря, Read — это оператор обращения к стандартной процедуре ввода.)

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

Другой вариант оператора ввода с клавиатуры имеет вид:

Здесь слово ReadLn означает read line — читать строку. Этот оператор отличается от Read только тем, что после считывания последнего в списке значения для одного оператора ReadLn данные для следующего оператора будут считываться с начала но

Имеются также стандартные функции ReadInteger, ReadReal, ReadlnInteger, ReadlnReal:

С процедурой ввода связан ряд ошибок времени выполнения (например, если переменная используется в качестве делителя, и вводится 0, или, если должно быть получено целое число, а вводится ‘ABC’). Эти ошибки нужно уметь обрабатывать.

Оператор try/except и обработка ошибок ввода

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

Если внутри блока try происходит ошибка выполнения, то все последующие операторы в блоке игнорируются, и выполнение программы переходит к блоку except. По выходе из except программа продолжает работу.

Если ошибки не происходит, то выполняются все операторы в блоке try, блок except не выполняется, и программа продолжает работу.

Выражения в списке вычисляются, и их значения выводятся на экран. В случае writeln после вывода осуществляется переход на новую строку.

Вывод с помощью write[ln]Format

Пример вывода с использованием форматной строки.

В форматной строке тоже можно использовать формат вывода.

<0, 10>: 10 — это ширина поля вывода

<0, 10:f3>: 3 — это количество знаков в дробной части для вещественного числа (показывает это спецификатор f).

1.Синтаксис и семантика оператора ввода

2. Обработка ошибок ввода

3. Синтаксис и семантика оператора вывода

4. Форматы вывода

Раздел 2 Тема 2.2 Условный оператор

Лекция№ 12 Условный оператор. Оператор выбора.

2 Синтаксис, семантика оператора IF

3.. Правила записи

4. Синтаксис, семантика оператора case

ОПЕРАТОР задает полное описание некоторого действия, которое необходимо выполнить. Для описания сложного действия может потребоваться группа операторов. В этом случае операторы объединяются в СОСТАВНОЙ ОПЕРАТОР или БЛОК.

Пример 3. Упорядочить по возрастанию значения в двух переменных а, Ь:

В данном примере использован составной оператор — последовательность операторов, заключенная в фигурные скобки. В Си фигурные скобки выполняют роль операторных скобок по аналогии с Begin, End в Паскале.

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

Условный оператор IF

IF a=28 THEN WriteLn (f) ELSE k:=44

Переводится он так:

ЕСЛИ a=28 ТО печатай f ИНАЧЕ присвой переменной k значение 44.

Оператор if можно записывать и без части else. Например, if s 2 then WriteLn (‘. ‘) else WriteLn (‘!’)

a:=4; if a>5 then a:=a+10 else a:=a-1; WriteLn (a)

s:=6; if s-8 , после чего его значение ищется в одном из

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

Ограничения выражениепереключатель должно иметь так называемый порядковый тип:

целый символьный перечислимый

НО НЕ строковый или вещественный.

значения в не должны пересекаться.

Примеры использования оператора выбора

Пример 1. День недели

Пример 2. Цифра или буква

2. Синтаксис, семантика оператора IF

3. Правила записи

4. Синтаксис, семантика оператора case

Тема 2.3. Операторы цикла

Лекция№13 Циклы с пост и предусловием Цикл с параметром Вложенные циклы

1.Оператор цикла while

2.Оператор цикла repeat (do while)

4.Оператор цикла с параметром (for)

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

В языке Си операторы while, do while и for , в языке Pascal операторы while, repeat

Оператор цикла while называется циклом с предусловием и имеет следующий формат: while (выражение) оператор

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

1. Вычисляется выражение.

2. Если выражение ложно, то выполнение оператора while заканчивается и выполняется следующий по порядку оператор. Если выражение истинно, то выполняется тело оператора while.

3. Процесс повторяется с пункта 1.

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

Синтаксис цикла while Семантика цикла while

В качестве примера использования оператора цикла рассмотрим программу вычисления факториала целого положительного числа NL Сопоставим программу решения этой задачи, написанную на Паскале, с программой на Си. Пример…см.учебник СемакинаИ.Г. стр65/стр.202, метуказ. Лясина Д.В. ОП лаб2

Синтаксис цикла repeat (ЯП Паскаль), цикла do whil (ЯП С++)

Циклы с постусловием (repeat) — сначала делается повторение цикла, а потом проверяется условие и если оно выполняется, то происходит следующее повторение цикла.

Исполнение цикла повторяется до того момента, когда станет равным true. Семантика цикла repeat

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

do <тело>while (выражение);

Схема выполнения оператора do while (рис.2):

1. Выполняется тело цикла (которое может быть составным оператором).

2. Вычисляется выражение.

3. Если выражение ложно, то выполнение оператора do while заканчивается и выполняется следующий по порядку оператор. Если выражение истинно, то выполнение оператора продолжается с пункта 1.

Зацикливание происходит, если:

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

условие цикла с постусловием всегда ложно, иными словами равно нулю.

Использование в качестве выражения константы 1 приводит к тому, что условие повторения цикла все время остается истинным и работа цикла никогда не заканчивается. Тело в этом цикле представляет собой пустой оператор. При исполнении такого оператора программа будет «топтаться на месте». см. учебник Семакина стр.202

Итерация — однократное повторение тела икла. Отличия между циклами while и repeat while тело может не выполниться ни разу ,repeat тело выполнится хотя бы один раз.

Пример 1. Сумма нечетных двузначных чисел

С использованием while С использованием repeat

Моделирование repeat с помощью while Моделирование while с помощью repeat

Операторы while и do while могут быть вложенными.

while (a[k] > mas[i]; //вводим очередной элемент массива

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

Ввод строки с клавиатуры

cin >> str;//или scanf(”%s”, str)

Вывод содержимого строки на экран

cout s2. Отношение s1>s2носит лексикографический характер, по которому, например:

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

if (!strcmp(str, “мой пароль”))

Функция сравнения имеет ряд модификаций:

int stricmp(char *s1, char *s2);

Операцию поиска подстроки в строке можно реализовать с использованием функции strstr:

char *strstr(char *s1, const char *s2);

Функция ищет в строке s1 строку s2. Возвращает адрес первого символа вхождения строки s2. Если строка отсутствует — возвращает нуль.

char str1[20]=“One, two, three, two”;

char str2[10]=“two”;
cout b then .

Если множества a и b отличаются хотя бы одним элементом .

Если b является подмножеством a, то есть все элементы b являются элементами a .

Операция проверки вхождения элемента E в множество a:

if E in a then .

Например, a:= [1,2,4]; if 2 in a then .

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

Пусть задано множество a, описанное, как set of Byte. Будем пробовать уменьшать его на все элементы подряд, от 1 до 255, и каждый раз, когда это удается, распечатывать соответствующее число. Вот подходящий фрагмент, в котором мне понадобится “для транзита” еще одно множество b:

for i:=1 to 255 do begin
b:=a-[i]; if a<>b then begin WriteLn(i); a:=b end
end

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

for i:=0 to 255 do if i in a then WriteLn(i)

Я думаю, что работа с множествами Паскаля — любопытное и полезное занятие. Например, она нужна математикам, чтобы проверять свои теоремы. Я проиллюстрирую работу с множествами на простеньком примере:

Медиум загадывает шестерку чисел, каждое в диапазоне от 0 до 10 (числа могут и совпадать). Экстрасенс отгадывает их, называя свою шестерку. Есть ли между шестерками совпадающие числа? Если есть, то распечатать их.

Сначала решим задачу традиционными методами, а именно с применением массивов, а не множеств:

CONST razmer = 10; kol = 6;


VAR Medium, Extrasens :array[1..kol] of 0..razmer;
i, j, k :Integer;
BEGIN
<Формируем случайным образом две шестерки:>
Randomize;

for i:= 1 to kol do begin
Medium[i] :=Random(razmer+1); Extrasens[i] :=Random(razmer+1)

end ;
<Проверяем две шестерки на совпадение:>
k:=0; <Нам придется подсчитывать количество совпадений. k - счетчик>
for i:= 1 to kol do
for j:= 1 to kol do
if Medium[i] = Extrasens[j] then begin
k:=k+1;
WriteLn(Medium[i]) <Распечатываем совпадения>
end ;
if k=0 then WriteLn(‘Не угадал ни разу‘)
END.

У данной программы есть недостатки. Пусть медиум загадал числа 2 4 1 5 4 8, а экстрасенс назвал 1 4 9 6 1 4. Программа распечатает числа 4 4 1 1 4 4, а достаточно было бы только 1 4. К тому же пришлось организовывать счетчик совпадающих чисел, чтобы иметь возможность ответить, угадано ли хоть одно число.

А теперь применяем множества:

CONST razmer = 10; kol = 6;

VAR Medium, Extrasens, a :set of 0..razmer;
i :Integer;
BEGIN
<Формируем случайным образом две шестерки:>

Randomize;
Medium:=[ ]; Extrasens:=[ ]; <Начинаем формировать “с нуля”, то есть с пустых множеств>
for i:= 1 to kol do begin
Medium := Medium + [Random(razmer+1)]; <Наращиваем по одному элементу в множестве медиума>
Extrasens := Extrasens + [Random(razmer+1)] <Наращиваем по одному элементу в множестве экстрасенса>
end

a:= Medium * Extrasens; <Множество a содержит совпадающие числа. Вот так – одним махом.>
if a=[ ] then WriteLn(‘Не угадал ни разу‘)
else begin
WriteLn(‘Есть совпадения, вот они: ‘);
<Распечатываем элементы множества a:>
for i:=0 to razmer do if i in a then WriteLn(i);

end
END.

Описание множеств. Множестваконстанты. Пустое множество.

Операции над множествами:

Цикл foreach по множеству.

Пример использования множеств: решето Эратосфена. Алгоритм.

Код алгоритма Эратосфена

  1. Свойства множеств
  2. Операции объединения, пересечения, разности
  3. Множестваконстанты. Пустое множество.

Тема 4.4. Записи

Лекция№22 Определение типа записи. Правила работы с записями.

2. Обращение к записи

Для реализации объединения данных разного типа в языке Pascal существует специальная структура — запись. Объявление записи начинается с зарезервированного словаrecord, за которым перечисляются имена и типы всех составляющих записей ее полей. Заканчивается объявление скобкой end.
Пример:
type
karta = record
family: string[20];
name: string[15];
age: integer;
end;
При обращении к записи в программе указывается имя записи и через точку имя поля.
Пример:
karta.family:=’Иванов’;
karta.name:=’Иван’;
karta.age:=20;
Для упрощения обращения к записи может быть использован оператор работы со структурой with.
Пример:
with karta do
begin
family:=’Иванов’;
name:=’Иван’;
age:=20;
end;
Полями записи наряду с простыми типами могут быть и данные структурированных типов, например, массивы или записи.
Пример 1:
var z: record
pole1: string;
pole2: array [1..10] of byte;
end;
Begin
for i:=1 to 10 do
read (z.pole2[i]);
End.

Пример 2: объявите запись, содержащую сведения о фамилии, дате рождения и адресе студента.
var student: record
fam: string[15];
data: record
day: 1..31;
mes: 1..12;
year: integer;
end;
adres: record
street: string[15];
dom: byte;
kvart: byte;
end;
end;
Begin
with student do
begin
fam:= ‘Иванов’;
with data do
begin
day:= 30;
mes:= 4;
year:= 1987;
end;
with adres do
begin
street:= ‘Туполева’;
dom:= 22;
kvart:= 154;
end;
end;
End.
Для использования в программе набора с одинаковыми полями используются массивы записей.
Пример: объявить массив из десяти записей.
1 вариант решения:
var A: array [1..10] of record
fam: string;
name: string;
end;
2 вариант решения:
type student = record
fam: string;
name: string;
end;
var A: array [1..10] of student;

1. Объявление записи

2. Обращение к записи

Тема 4.5. Файлы

Лекция№23 Типы файлов. Файлы последовательного доступа.

  1. Определение
  2. Классификация
  3. Понятие файловой переменной, файлового указателя
  4. 2 способа открытия файла
  5. Буферизация в файлах

Файл — именованная область на диске, содержащая некоторую информацию.

  1. Хранят данные в промежутках между запусками программ.
  2. Размер данных в файле может существенно превышать оперативную память компьютера.

Файлы обычно классифицируют по двум признакам: 1. По типу компонент:

2. По способу доступа:

Тип text. Состоят из строк переменной длины, в конце каждой из которых находится символ перехода на новую строку (#13#10 в Windows, #10 в Linux). В

PascalABC.NET это константа NewLine.

Двоичные файлы: информация хранится в виде двоичного кода.

Тип file of . Содержат данные фиксированного типа .

Тип file. Могут хранить данные различных типов.

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

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

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

текстовые, бестиповые файлы.

Типизированные файлы имеют произвольный доступ.

Понятие файловой переменной, файлового указателя

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

Закрытый файл можно:

переименовывать перемещать копировать удалять

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

Файловый указатель создается при открытии файла, и, как правило, устанавливается на 1й элемент файла.

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

2 способа открытия файла

  1. Reset(f) — открытие текстового файла на чтение, а двоичного — на чтение и запись; файл должен существовать; файловый указатель — на начало файла;
  2. Rewrite(f) — создание нового файла (если такого файла не существовало) или обнуление существующего; файловый указатель — в начало;

текстовые файлы при этом открываются только на запись, а двоичные — на чтение и запись;

Функция Eof(f) [расшифровывается как End Of File] возвращает true, если файловый указатель находился за концом файла.

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

Если, не закрывая, выполнить Reset(f), то файловый указатель просто перейдет к началу.

Буферизация в файлах

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

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

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

Подпрограммы для работы с закрытыми файлами

Типичные ошибки вводавывода при работе с файлами

  1. Файл открыли, но забыли выполнить Assign.
  2. Открыли, но файла нет на диске (или нет прав доступа на чтение).
  3. Попытка считывания за концом файла.

Все эти ошибки нужно обрабатывать с помощью исключений.

Пример 1. Файл не существует.

Этот оператор отличается тем, что не обрабатывает исключение, а лишь выполняет некоторое завершающее действие, которое должно быть совершено в любом случае. Для обработки нужен внешний блок try..except.

Пример 2. Попытка считывания за концом файла.

  1. Определение
  2. Классификация
  3. Понятие файловой переменной, файлового указателя
  4. 2 способа открытия файла
  5. Буферизация в файлах

Лекция№24 Файлы произвольного доступа. Создание структуры записи.

Файлы произвольного доступа

Структура описания файловой переменной

Чтение элементов файла

Последовательность действий для создания и заполнения файла

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

Все файлы, содержащие элементы разного размера могут иметь только последовательный доступ к элементам

Прямой доступ к записям файла. В стандарте языка Паскаль до

пустим только последовательный доступ к элементам файла. Од

ной из дополнительных возможностей, реализованных в Турбо

Паскале, является прямой доступ к записям файла.

Как уже отмечалось, элементы файла пронумерованы в порядке

их занесения в файл, начиная с нуля. Задав номер элемента файла,

можно непосредственно установить на него указатель. После этого

можно читать или перезаписывать данный элемент. Установка ука

зателя на нужный элемент файла производится процедурой

Здесь F V — имя файловой переменной, п — порядковый номер

элемента. В следующем примере эта процедура будет использована. Пример 2. Имеется файл, сформированный программой из пре

дыдущего примера. Пусть некоторые студенты пересдали экзамен

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

татов переэкзаменовки в файл. Программа будет запрашивать но

мер студента в ведомости и его новую оценку. Работа заканчивает

ся, если вводится несуществующий номер (9999).

Пример требует некоторых пояснений. Список студентов в ве

домости пронумерован, начиная от 1, а записи в файле нумеру

ются от 0. Поэтому, если п — это номер в ведомости, то номер

соответствующей записи в файле равен п-1 . После прочтения

записи «номер п-1» указатель смещается к следующей п-й запи

си. Для повторного занесения на то же место исправленной запи

си повторяется установка указателя.

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

Структура описания файловой переменной:

где может быть любым, кроме файлового.

Var Fi: File Of Integer;

Fr: File Of Real;

Fc: File Of Char;

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

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

Для того чтобы начать запись в файл, его следует открыть для записи. Это обеспечивает процедура Rewrite (FV) ; где FV — имя файловой переменной. При этом указатель устанавливается на начало файла. Если в файле есть информация, то она исчезает.

Схематически выполнение процедуры Rewrite можно представить так:

Стрелка внизу отмечает позицию указателя.

Запись в файл осуществляется процедурой Write (FV, V); где v — переменная того же типа, что и файл FV. Запись происходит туда, где установлено окно (указатель). Сначала записывается значение, затем указатель смещается в следующую позицию. Если новый элемент вносится в конец файла, то сдвигается маркер конца.

Схема выполнения оператора:

Пример 1. В файловую переменную Fx занести 20 вещественных

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

Для чтения элементов файла с его начала следует открыть файл для чтения. Это делает процедура Reset (FV). В результате указатель устанавливается на начало файла. При этом вся информация в файле сохраняется. Схема выполнения процедуры:

Чтение из файла осуществляется процедурой Read (FV, v) ; гдеv — переменная того же типа, что и файл FV. Значение текущегоэлемента файла записывается в переменную v; указатель смещается к следующему элементу.

Пример 1. В файловую переменную Fx занести 20 вещественных

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

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

1. Описать файловую переменную.

2. Описать переменную того же типа, что и файл.

3. Произвести назначение (Assign).

4. Открыть файл для записи (Rewrite).

5. Записать в файл данные (Write).

6. Закрыть файл (Close).

Ее результат — целое число, равное текущей длине файла.

Замечание: согласно стандарту Паскаля в файл, открытый опе

ратором Rewrite, можно только записывать информацию, а файл,

открытый оператором Reset , можно использовать только для чте

ния. В Турбо Паскале допускается запись (Write) в файл, откры

тый для чтения (Reset). Это создает определенные удобства для

Тема 4.6. Указатели

Лекция№ 25. Указатели и применение динамически распределяемой памяти.

  1. Определение указателя
  2. Типы указателей
  3. Бестиповые указатели
  4. Динамическая память

Оперативная память состоит из последовательный ячеек. Каждая ячейка имеет номер, называемый адресом. В 32битных системах можно адресовать 2 32 байт ( 4Гб) памяти, в 64битных — 2 64 соответственно.

Переменная (или константа), хранящая адрес, называется указателем.

Для чего нужны указатели

Указатели повышают гибкость доступа к данным:

Вместо самих данных можно хранить указатель на них. Это позволяет хранить данные в одном экземпляре и множество указателей на эти данные.

Через разные указатели эти данные можно обновлять (пример — корпоративная БД).

Указателю можно присвоить адрес другого объекта (вместо старого появился новый телефонный справочник).

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

Указатели делятся на:

1.Типизированные (указывают на объект некоторого типа)

Имеют тип: ^ Пример. ^integer — указатель на integer

2.Бестиповые (хранят адрес ячейки памяти неизвестного типа)

Преимущество: могут хранить что угодно Имеют тип: pointer Пример кода.

@ — унарная операция взятия адреса

Операция разадресации (разыменования)

^ — операция разыменования pi^ — то, на что указывает pi, т.е. другое имя i или ссылка на i.

Тут надо вспомнить определение ссылки: Ссылка — другое имя объекта.

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

Попытка разыменовать нулевой указатель приводит к ошибке времени выполнения.

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

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

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

Вопрос. Нельзя ли интерпретировать память, на которую указывает p, как принадлежащую к определенному типу? Ответ — да, можно. Вот как это сделать:

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

Замечание. Важно, что типы real и Rec имеют один размер.

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

Особенности динамической памяти

Память, принадлежащая программе, делится на:

1.Статическую (память, занимаемая глобальными переменными и константами)

2. Автоматическую (память, занимаемая локальными данными, т.е. стек программы)

3.Динамическую (память, выделяемая программе по специальному запросу)

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

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

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

По окончании работы программы, вся затребованная программой динамическая память возвращается ОС.

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

Ошибка разыменования нулевого указателя (попытка использовать невыделенную динамическую память).

Утечка памяти (память, которая выделилась в результате первого вызова New(p), принадлежит программе, но не контролируется никаким указателем.

Утечка памяти в подпрограмме: обычно если динамическая память выделяется в подпрограмме, то она должна в этой же подпрограмме возвращаться. Исключение составляют т.н. «создающие» п/п:

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

Out of Memory (очень большие утечки памяти, в результате которых динамическая память может «исчерпаться»).

  1. Определение указателя
  2. Типы указателей
  3. Бестиповые указатели
  4. Динамическая память

Тема 4.6

Лекция№26. Структуры данных на основе указателей.

  1. Определение ДСД
  2. Виды ДСД
  3. Стеки
  4. Очереди
  5. Линейные списки

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

struct Node
< … //информационный блок
Node *field1, *field2, *mas[10];//адресный блок

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

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

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

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

LIFO (Last-In, First-Out)

поступивший последним, обслуживается первым.

Обычно над стеками выполняется три операции:

-начальное формирование стека (запись первой компоненты);

-добавление компоненты в стек;

-выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая — вспомогательная. Пусть описание этих переменных имеет вид:

var pTop, pAux: Pointer;

где pTop — указатель вершины стека;

pAux — вспомогательный указатель.

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

FIFO (First-In, First-Out) —

поступивший первым, обслуживается первым.

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

Описание компоненты очереди и переменных типа указатель дадим сле-

pBegin, pEnd, pAux: PComp;

где pBegin — указатель начала очереди, pEnd — указатель конца очереди, pAux — вспомогательный указатель.

Тип Т определяет тип данных компоненты очереди.

Линейный односвязный список

Циклический односвязный список

Двусвязный линейный список

Циклический двусвязный список

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

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

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

Основные отличия связного списка от стека и очереди следующие:

-для чтения доступна любая компонента списка;

-новые компоненты можно добавлять в любое место списка;

-при чтении компонента не удаляется из списка.

Для формирования списка и работы с ним необходимо иметь пять пере-

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

вторая — конец списка, остальные- вспомогательные.

Описание компоненты списка и переменных типа указатель дадим сле-

pBegin, pEnd, pCKey, pPreComp, pAux: PComp;

где pBegin — указатель начала списка, pEnd — указатель конца списка,

pCKey, pPreComp, pAux — вспомогательные указатели.

  1. Определение ДСД
  2. Виды ДСД
  3. Стеки
  4. Очереди
  5. Линейные списки

Раздел 5. Объектно-ориентированное программирование

Тема 5.1 Основные принципы объектно-ориентированного программирования (ООП)

Лекция№27. Базовые понятия ООП. Основные принципы ООП.

  1. Концепция ООП
  2. Принципы ООП
  3. Элементы ООП
  4. История

Объе́ктно-ориенти́рованное программи́рование (ООП) — методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определенного класса [1] , а классы образуют иерархию наследования

Необходимо обратить внимание на следующие важные части этого определения: 1) объектно-ориентированное программирование использует в качестве основных логических конструктивных элементов объекты, а не алгоритмы; 2) каждый объект является экземпляром определенного класса; 3) классы образуют иерархии. Программа считается объектно-ориентированной, только если выполнены все три указанных требования. В частности, программирование, не использующее наследование, называется не объектно-ориентированным, а программированием с помощью абстрактных типов данных

Концепция объектно-ориентированного программирования

Концепцию ООП характеризует следующее:

  1. В качестве строительных блоков разрабатываемых приложений используются объекты.
  2. Каждому классу соответствует некоторый объектный тип, представляющий собой совокупность элементов данных и методов (для операций над данными), скомпонованных вместе для удобства использования.
  3. Каждый объект – переменная, являющаяся представителем (экземпляром) определённого класса.
  4. Классы связаны друг с другом соотношениями, с помощью которых объекты могут расширяться; при этом описания существующих объектов могут многократно использоваться при описании новых объектов.
  5. Представителями класса могут быть представители, как непосредственного класса, так и любого класса предка.

Концепция ООП базируется на трёх основных принципах:

Инкапсуляция

Инкапсуляция – объединение данных и действий над ними в одном объектном типе.

Наследование

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

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

Полиморфизм

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

Класс является описываемой на языке терминологии исходного кода моделью ещё не существующей сущности (объекта). Фактически он описывает устройство объекта, являясь своего рода чертежом. Говорят, что объект — это экземпляр класса. При этом в некоторых исполняющих системах класс также может представляться некоторым объектом при выполнении программы посредством динамической идентификации типа данных. Обычно классы разрабатывают таким образом, чтобы их объекты соответствовали объектам предметной области.

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

История

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

Взаимодействие объектов происходит посредством сообщений. Результатом дальнейшего развития ООП, по-видимому, будет агентно-ориентированое программирование, где агенты — независимые части кода на уровне выполнения. Взаимодействие агентов происходит посредством изменения среды, в которой они находятся.


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

Первым языком программирования, в котором были предложены основные понятия, впоследствии сложившиеся в парадигму, была Симула, но термин «объектная ориентированность» не использовался в контексте использования этого языка. Взгляд на программирование «под новым углом» (отличным от процедурного) предложили Алан Кэй и Дэн Ингаллс в языке Smalltalk. Здесь понятие класса стало основообразующей идеей для всех остальных конструкций языка (то есть класс в Смолтоке является примитивом, посредством которого описаны более сложные конструкции).

Наиболее распространённые в промышленности языки (С++, Delphi, C#, Java и др.) воплощают объектную модель Симулы. Примерами языков, опирающихся на модель Смолтока, являются Python, Ruby.

  1. Концепция ООП
  2. Принципы ООП
  3. Элементы ООП

Тема 5.1

Лекция№28. Классы объектов. Компоненты и их свойства.

  1. Определение класса
  2. Объявление класса
  3. Поля
  4. Свойства
  5. Палитра компонентов

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

Переменные в зависимости от предназначения именуются полями или свойствами. Процедуры и функции класса – методами. Соответствующий классу тип называется объектным типом.

Пример объявления простого класса:

type

TPerson = class (TObject)

fname: string[15]; faddress: string[35];

end;

TPerson – это имя класса, fname и faddress – имена полей, show – имя метода.

Согласно принятому в Delphi соглашению, имена полей должны начинаться с буквы f (от слова field – поле).

Описание класса помещают в программе в раздел описания типов (type).

Тексты на Object Pascal представляются в виде модулей (pas – файлов). Классы могут быть объявлены в секции интерфейса (interface) или в секции реализации (implementation) модуля. Определение классов внутри подпрограмм и других блоков не допускается.

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

Объект может содержать другой объект. Например, объект формы может содержать объект кнопки.

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

Переменная типа класс – это переменная объектного типа и называется экземпляром класса или объектом.

Объекты как представители класса объявляются в программе в разделе var, например:

Var student: TPerson; professor: TPerson;

Поля

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

При создании новых классов на базе ранее созданных класс-потомок наследует все поля класса-родителя. Удаление и переопределение полей невозможно. Допускается добавление новых полей.

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

В Delphi у всех стандартных классов все поля недоступны и заменены базирующимися на них свойствами. Свойства компонентов Delphi определяют их внешний вид и поведение.

Свойства

Свойства – это высокоуровневые атрибуты компонентов класса.

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

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

Методы

Метод – это подпрограмма (процедура или функция), которая определена как элемент класса. Описание метода аналогично описанию обычной подпрограммы модуля. Внутри одного класса можно объявить столько методов, сколько надо.

Компоненты и палитра компонентов

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

Окно формы – это окно Windows.. Сама форма также является компонентом. Новая форма, которая создаётся при загрузке Delphi или при создании нового проекта, является главной формой приложения.

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

Компоненты Delphi

Библиотека визуальных компонентов (Visual Component Library — VCL) Delphi содержит множество предопределенных типов компонентов, из которых пользователь может строить свою прикладную программу. Палитра компонентов расположена справа в полосе инструментальных панелей интегрированной среды разработки Delphi.

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

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

Имена на ярлычках выглядят, например, так: MainMenu, Button и т.д. Однако, в Delphi все имена классов в действительности начинаются с символа «Т», например, TMainMenu, TButton.

Все компоненты системы Delphi можно разделить на:

 визуальные, т.е. те, которые будут представлены на форме во время выполнения приложения в том же виде, что и при разработке приложения (например, кнопки, метки и пр.);

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

  1. Определение класса
  2. Объявление класса
  3. Поля
  4. Свойства
  5. Палитра компонентов

Тема 5.2 Интегрированная среда разработчика

Лекция№29. Интерфейс среды разработчика: основные окна, интегрированной среде

  1. Определение
  2. Преимущества интегрированной среды

3. Окна интегрированной среды

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

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

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

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

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

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

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

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

Работа в интегрированной среде дает программисту:

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

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

Возможность организации и ведения параллельной работы над несколькими проектами. Менеджер проектов позволяет использовать любой проект в качестве шаблона для вновь создаваемого проекта;

Перекомпиляции подвергаются только редактировавшиеся модули;

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

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

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

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

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

Переключение между окнами Конструктора формы и Редактора кода удобно выполнять с помощью клавиши .

Окно Проводника кода (Exploring Unitl.pas) пристыковано слева от окна Редактора кода. В нем в виде дерева отображаются все объекты модуля формы, например, переменные и процедуры (рис. 1.2). В окне Проводника кода можно удобно просматривать объекты приложения и быстро переходить к нужным объектам, что особенно важно для больших модулей. Вызов окна Проводника кода выполняется по команде Code Explorer (Проводник кода) меню View (Вид).

Окно Инспектора объектов находится в левой части экрана и отображает свойства и события объектов для текущей формы Formi. Его можно вызвать на экран командой View | Object Inspector (Просмотр | Инспектор объектов) или нажатием клавиши .

Окно Инспектора объектов имеет две страницы: Properties (Свойства) и Events (События).

Страница Properties отображает информацию о текущем (выбранном) компоненте в окне Конструктора формы и при проектировании формы позволяет удобно изменять многие свойства компонентов.

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

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

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

Для соединения двух окон следует с помощью мыши поместить одно из них на другое, и после изменения вида рамки перемещаемого окна отпустить его, после чего это окно автоматически пристыкуется сбоку от второго окна. Разделение окон выполняется перемещением пристыкованного окна за двойную линию, размещенную под общим заголовком. После соединения окна представляют собой одно общее окно, разделенное на несколько частей. При стыковке/расстыковке окно изменяет свое название. Так, окно Проводника кода, состыкованное с окном Редактором кода, имеет общее с ним название, например, Unitl.pas, в то время как при отстыковке название изменяется на Exploring Unitl.pas. Окна Инспектора объектов и Обозревателя дерева объектов при стыковке объединяют свои названия (через запятую указываются названия каждого

Скрытое окно вызывается на экран командой пункта View (Просмотр) главного меню. Например, окно Проводника кода выводится на экран командой View | Code Explorer (Просмотр | Проводник кода).

  1. Определение
  2. Преимущества интегрированной среды

3. Окна интегрированной среды

Тема 5.3 Этапы разработки приложения

Лекция№30. Проектирование, тестирование и отладка приложения.

2. Создание приложения в среде Delphi

3. Создание приложения в среде Visual Basic

Процесс разработки новых приложений состоит из 4-х основных этапов:
1. Проектирование. Определяются цели и задачи, способы их решения, а также определяется структура данных и язык программирования, на котором будет написано приложение.
2. Создание интерфейса. В программную среду разработки вводятся необходимые управляющие элементы: кнопки, текстовые поля, флажки, переключатели и другие элементы.
3. Отладка. Все управляющие элементы связываются программным кодом и путем ввода конкретных значений происходит проверка работоспособности кода и отлавливание возможных ошибок. Логические ошибки самые коварные в этом плане. Этот этап по времени самый длительный.
4. Заключительный этап. Идет компиляция кода и создание дистрибутива. Компиляция — процесс перевода программного кода в машинный язык, понятный каждому компьютеру. Здесь же идет подключение необходимых программных библиотек для полной работоспособности приложения. На выходе получаем законченный продукт — файл с расширением «.ехе».

Создание приложения в среде Delphi можно условно разделить на несколько этапов:

1. Создание графического интерфейса будущего приложения

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

2. Задание значений свойств объектов графического интерфейса

С помощью окна «Свойства объекта» задаются значения свойств управляющих элементов, помещенных ранее на форму.

3. Создание и редактирование программного кода

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

4. Сохранение проекта

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

– Сначала необходимо сохранить форму и связанный с ней программный модуль (файл с расширением pas) с помощью команды Save As.… По умолчанию для файла формы предлагается имя Unit1.pas.

– Далее необходимо сохранить файл главного модуля, который содержит описание проекта (файл с расширением dpr) с помощью команды Save Project As…

– В процессе сохранения в папку проекта записываются вспомогательные файлы: файл с расширением res, описывающий ресурсы; файл с расширением dfm, описывающий форму, и некоторые другие файлы.

5. Компиляция проекта в приложение

Сохраненный проект может выполняться только в самой системе программирования Delphi. Для того чтобы преобразовать проект в приложение, которое может выполняться непосредственно в среде операционной системы, необходимо сохранить проект в исполнимом файле (типа exe). Для компиляции проекта в исполнимый файл используется команда [Project-Compile].

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

Компонент Набора данных (TTable, TQuery, TStoredProc);

один или несколько компонентов отображения данных..

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

Интегрированная среда разработки Visual Basic

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

В Visual Basic реализована модель объектно-ориентированного событийно — управляемого программирования.

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

Форма – основной элемент внешнего интерфейса проекта, аналог окна Windows. Она имеет строку заголовка с кнопками управления и системным меню, а также возможности управления мышью. Все это не надо программировать, форма, включённая в проект, обладает этими свойствами. Обычно в проекте бывает несколько форм.

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

Этапы разработки приложения в среде Visual Basic

Создание интерфейса (этап проектирования)

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

Создание программного кода

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

Для создания или редактирования кода надо вызвать окно Редактора кода. Окно используется для размещения, просмотра и редактирования всех текстовых элементов программы — описания констант, переменных, массивов, процедур и пр.

Отладка, тестирование, компиляция

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

2. Создание приложения в среде Delphi

3. Создание приложения в среде Visual Basic

Тема 5.4 Иерархия классов

Лекция№31. Классы объектно-ориентированного языка программирования.

1.Определение класса ООП

3. Отношения между классами

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

Класс — разновидность абстрактного типа данных в объектно-ориентированном программировании (ООП), характеризуемый способом своего построения. Класс определяет одновременно как интерфейс, так и реализацию для всех своих экземпляров, а вызов метода-конструктора обязателен.

В объектно-ориентированной программе с применением классов каждый объект является «экземпляром» некоторого конкретного класса, и других объектов не предусмотрено. То есть «экземпляр класса» в данном случае означает не «пример некоторого класса» или «отдельно взятый класс», а «объект, типом которого является какой-то класс». В современных объектно-ориентированных языках программирования (в том числе в php, Java, C++, Oberon, Python, Ruby, Smalltalk, Object Pascal) создание класса сводится к написанию некоторой структуры, содержащей набор полей и методов (среди последних особую роль играют конструкторы, деструкторы, финализаторы). Практически класс может пониматься как некий шаблон, по которому создаются объекты — экземпляры данного класса. Все экземпляры одного класса созданы по одному шаблону, поэтому имеют один и тот же набор полей и методов.

Например, абстрактный тип данных «строка текста» может быть оформлен в виде класса, и тогда все строки текста в программе будут являться объектами — экземплярами класса «строка текста».

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

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

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

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

1.Базовый (родительский) класс (суперкласс) — класс, на основе которого создаются другие классы. Классы, полученные на основе суперкласса, называются дочерними классами, производными классами или подклассами.

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

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

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

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

В языке UML класс может иметь собственный набор корневых (root) свойств для обозначения, что это именно базовый класс.

В C++-стиле (который используется в C# и других языках) термин «базовый класс» используется вместо термина «суперкласс».

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

В ряде языков программирования все классы явно или неявно наследуются от некого базового класса. Smalltalk был одним из первых языков, в которых использовалась эта концепция. К таким языкам Java (java.lang.Object), C# (System.Object), Delphi (TObject).

Подклассы и суперклассы часто обозначаются как производные или порождённые (derived) и базовые (base) классы соответственно, причём эти термины закреплены создателем C++ — Бьёрном Страуструпом, который нашёл эти термины более интуитивно понимаемыми по сравнению с традиционной номенклатурой названий.

3. Абстрактный класс в объектно-ориентированном программировании — базовый класс, который не предполагает создания экземпляров. Абстрактные классы реализуют на практике один из принципов ООП — полиморфизм. Абстрактный класс можно рассматривать в качестве интерфейса к семейству классов, порождённому им, но, в отличие от классического интерфейса, абстрактный класс может иметь определённые методы, а также свойства.

Абстрактные методы часто являются и виртуальными, в связи с чем понятия «абстрактный» и «виртуальный» иногда путают.

В Delphi может быть объявлен абстрактный класс с абстрактными методами:

procedure NonAbstractProcedure;

procedure AbstractProcedure; abstract;

end;

Для такого класса может быть создан объект, но обращение к методу AbstractProcedure этого объекта во время выполнения вызовет ошибку.

.Интерфе́йс (от лат. inter — «между», и face — «поверхность») — синтаксическая конструкция в коде программы, используемая для специфицирования услуг, предоставляемых классом или компонентом.

Интерфейсы позволяют наладить множественное наследование объектов и в то же время решить проблему ромбовидного наследования. В языке C++ она решается через наследование классов с использованием ключевого слова virtual.

Отношения между классами

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

1.Определение класса ООП

3. Отношения между классами

Лекция№32. Наследование. Перегрузка методов

  1. Определение наследования
  2. Типы наследования
  3. Единый базовый класс
  4. Перегрузка (методов

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

Типы наследования

Класс, от которого произошло наследование, называется базовым или родительским (англ. base class). Классы, которые произошли от базового, называютсяпотомками, наследниками или производными классами (англ. derived class).

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

При множественном наследовании у класса может быть более одного предка. В этом случае класс наследует методы всех предков. Достоинства такого подхода в большей гибкости. Множественное наследование реализовано в C++. Из других языков, предоставляющих эту возможность, можно отметить Python и Eiffel. Множественное наследование поддерживается в языке UML.

Множественное наследование — потенциальный источник ошибок, которые могут возникнуть из-за наличия одинаковых имен методов в предках

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

Единый базовый класс

В ряде языков программирования все классы явно или неявно наследуются от некого базового класса. Smalltalk был одним из первых языков, в которых использовалась эта концепция. К таким языкам Java (java.lang.Object), C# (System.Object), Delphi (TObject).

Абсолютно все классы в Delphi являются потомками класса TObject. Если класс-предок не указан, то подразумевается, что новый класс является прямым потомком класса TObject.

Множественное наследование в Delphi частично поддерживается за счёт использования классов-помощников (Сlass Helpers).

Python поддерживает как одиночное, так и множественное наследование.

Перегрузка методов (процедур и функций)

— возможность использования одноимённых подпрограмм: процедур или функций в языках программирования.

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

Метод — это не что иное, как набор выполняемых инструкций. Методы также определяют интерфейс данных объекта. Ещё они помогают обеспечивать структурный подход к программированию. Программа может быть разделена на различные методы, которые является только логической группировкой связанных выполняемых инструкций. Методы помогают при отладке программы, поскольку отладчик может непосредственно перейти к специфическому методу и сделать необходимые исправления. Если программа размером в 1 КБ не содержит ни одного метода, то отладить такую программу будет достаточно трудно.

Обратите внимание: Методы также называются функциями.

Преимущества методов:
Есть два типа методов, а именно перегруженные методы и переопределённые методы.

Перегруженные методы — это методы, которые находятся в том же самом классе и имеют то же самое имя, но различные списки параметров. Переопределённые методы — это методы, которые находятся в суперклассе так же как и в подклассе.

Обратите внимание: Перегруженные методы постоянно находятся в одном классе. Они имеют одну и ту же область видимости с классом.

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

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

  1. Определение наследования
  2. Типы наследования
  3. Единый базовый класс
  4. Перегрузка (методов

Тема 5.5. Визуальное событийно-управляемое программирование

Лекция№33. Основные компоненты интегрированной среды разработки

1.Преимущества Visual Basic

2. Элементы среды разработчика

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

Причины столь широкой популярности и у Visual Basic, и у системы Windows примерно одинаковы: фирма Microsoft сумела такую сложную технологию, как написание компьютерных программ, сделать доступной широкому кругу пользователей путем применения графического интерфейса..

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

Одним из основных преимуществ языка Visual Basic является возможность очень быстрого создания работоспособных приложений. С появлением версии Visual Basic 6.0 сбылась мечта программиста — простые приложения можно создавать, практически не прибегая к написанию программного кода, а в сложных приложениях рутинный процесс его создания сведен к минимуму. Мастера, включенные в состав Visual Basic, дают возможность быстро создавать прототипы приложений, готовых для обсуждения и согласования с заказчиком. Данная реализация языка ставит его практически в один ряд с такими средствами разработки, как Visual C++, Delphi и другими.

Простота и мощность языка Visual Basic позволили сделать его встроенным языком для приложений Microsoft Office. Многие независимые разработчики, например, известная своими программами в области бухгалтерского учета фирма «1C», приобретают лицензии на использование языка Visual Basic в качестве внутреннего языка своих приложений.

Фирма Microsoft интегрировала также специальную версию Visual Basic, известную под именем Visual Basic for Application (VBA) во все компоненты пакета Microsoft Office, Microsoft Project и некоторые другие программы. Кроме того, фирма Microsoft продала лицензию на VBA очень многим фирмам — производителям программного обеспечения. Поэтому в настоящее время Basic уже не считается учебным языком — знание Visual Basic и его диалектов (VBA, VBScript) становится необходимостью для современного программиста любого уровня

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

Основными элементами среды являются:

А) Главное окно среды напоминает окна Windows: есть строка заголовка, главное меню и панель инструментов.

Заголовок состоит из названия системы программирования Microsoft Visual Basic, левее этих слов расположено название проекта — Project1. Это название Visual Basic присвоил автоматически, его можно заменить каким-либо более осмысленным. В правой части Строка меню и панель инструментов во многом совпадают с меню и панелью Windows, однако, в них имеются меню и инструменты, которые обеспечивают доступ к специальным средствам Visual Basic.

Строка меню состоит из заголовков меню, которые содержат все команды, необходимые при работе с Visual Basic. Меню File, View, Edit, Window и Help являются характерными для Windows и приложений Windows, но имеют ряд особенностей.

Б) Окно конструктора форм: В серединной части экрана расположено окно проектов, озаглавленное Project1 — Form1 (Form). Оно является основным во время создания интерфейса будущего приложения. Внутри этого окна размещено окно дизайнера (конструктора) форм, чаще его называют просто окном форм. Его название Form1, автоматически присваивается Visual Basic, и должно быть впоследствии изменено. На этапе конструирования проекта на поверхности окна форм размещают необходимое количество объектов, предназначенных для управления приложением. Поверхность окна форм в режиме конструирования покрыта точками. Эти точки являются узлами координатной сетки и служат для облегчения размещения объектов на форме.

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

Г) Окно Свойства объекта (Properties): используется, чтобы задать свойства формы и размещенных на ней объектов на этапе проектирования. Это окно содержит перечень тех свойств объекта, которые пользователь может изменить. Значения свойств можно изменять непосредственно в окне Properties. Способы изменения свойств объекта:

в правое поле можно ввести значение свойства. Свойство будет изменено, если новое значение допустимо;

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

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

Д) Окно Проводник проекта (Project Explorer): позволяет анализировать структуру проекта и его состав. Приложение Visual Basic на этапе разработки состоит из нескольких файлов, которые все вместе составляют проект.. Окно проводника содержит три кнопки — View Code — показать окно кодов, View Object — показать окно форм и Toggle Folders — открыть/закрыть папку, содержащую список объектов.

Е) Еще одно окно — Code — окно Редактора кода в исходном состоянии среды не видно. Оно предназначено для создания и редактирования кода программы и вызывается на экран по мере необходимости.

1.Преимущества Visual Basic

2. Элементы среды разработчика

Тема 5.5.

Лекция№34. События компонентов Процедуры, определенные пользователем.

  1. Интерфейсные объекты
  2. Графический интерфейс
  3. Событийная процедура

Рассмотрим простую и естественную модель событийно-управляемого и визуального программирования, характерную для языка и среды Visual С++. В этой модели у приложения три составляющие: визуальная, системная и обработчик событий. Визуальная составляющая задает образ на экране, с которым будет работать пользователь. Она, как правило, разрабатывается визуальным инструментарием, позволяющим программисту создавать из элементов нужный образ на экране. Эти элементы являются объектами со своими свойствами и поведение.

Визуальная составляющая определяет интерфейс пользователя. Такие элементы интерфейса, как кнопки, окна редактирования, окна списков, называют элементами управления (controls). Эти и другие элементы интерфейса стандартизированы в стандарте пользовательского интерфейса CUA (Common User Access) в рамках общего стандарта SSA (system Application Architecture) фирмы IBM. Поэтому в разных средах разработки (Visual Basic, Visual C++, Delphi и др.) визуальный инструментарий содержит одни и те же элементы интерфейса. Такие же элементы интерфейса содержат разные приложения.

Элементы управления являются объектами, свойства и поведение которых определяется их переменными и методами. Они относятся к интерфейсным объектам.

Пользователь — это возмутитель спокойствия в мире объектов приложения. Он «нажимает» на кнопки, выбирает элементы списков, печатает тексты в окнах редактирования. Каждому его действию соответствует некоторое событие. Системная составляющая приложения, которая включает в себя средства операционной системы и средства среды программирования, определяет тип и параметры события и формирует сообщение объекту, с которым связано событие. Иначе говоря, системная составляющая находит нужный объект и запускает функцию-обработчик сообщения — соответствующий метод этого объекта. Таким образом, пользователь может взаимодействовать с элементами визуальной составляющей, а само взаимодействие обеспечивается системной составляющей.

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

Программирование на Visual С++ полностью соответствует концепциям визуального и событийно-управляемого программирования. Чтобы создать приложение на Visual С++, нужно сделать две вещи: разработать с помощью визуального инструментария интерфейс пользователя и написать реакции на действия пользователя, т.е. для каждого возможного события — обрабатывающий его метод.

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

Графический интерфейс. Визуальное программирование позволяет делать графический интерфейс разрабатываемых приложений на основе форм и управляющих элементов.
В роли основных объектов при визуальном программировании выступают формы (Forms). Форма представляет собой окно, на котором размещаются управляющие элементы. Управляющие элементы — это командные кнопки (CommandButton), переключатели, или «флажки» (Checkbox), поля выбора, или «радиокнопки» (OptionsButton), списки (ListBox), текстовые поля (TextBox) и др.

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

Имя процедуры включает в себя имя объекта и имя события.

Каждая процедура представляет собой отдельный программный модуль, в начале и в конце которого ставятся ключевые слова Sub и End:

Sub Объект_Событие() Программный код End Sub Разрабатываемое на языке Visual Basic приложение называется проектом. Проект включает в себя не только форму с размещенными на ней управляющими элементами, но и программные модули событийных процедур, которые описывают поведение объектов приложения и взаимодействие объектов между собой.

  1. Интерфейсные объекты
  2. Графический интерфейс
  3. Событийная процедура

Тема 5.6. Разработка оконного приложения

Лекция№35. Создание интерфейса оконного приложения. Компиляция и запуск приложения.

  1. Программы с оконным интерфейсом на Linux
  2. Этапы создания программы с оконным интерфейсом

Программы с оконным интерфейсом на Linux

Многие современные программы имеют оконный интерфейс (или просто GUI – Graphical User Interface). Он делает намного удобнее общение с пользователем, позволяет ускорить выполнение ряда рутинных процедур, да и просто GUI – это эстетично и современно. Мы создадим одну очень короткую программу. Задача не в том, чтобы научиться создавать программы с оконным интерфейсом (этому будут потом посвящены отдельные руководства), а в том, чтобы продемонстрировать, что их сборка и распространение принципиально не отличаются от того, что мы видели в случае с консольными программами.

Ключевым звеном оконных программ является X-сервер. Он отвечает за прорисовку графических элементов. Программы, имеющие оконный интерфейс должны обращаться к X-серверу. Для обращения к нему служит специальный интерфейс (он называется Xlib). Однако существуют средства, позволяющие избежать непосредственного обращения к низкоуровневому интерфейсу (а работа с ним занимает длительное время). Два наиболее распространённых таких средства – это библиотеки GTK и Qt.

Напишем очень короткую программу с оконным интерфейсом с использованием библиотеки GTK+ 2.0.

Чтобы простым способом её скомпилировать, нужно воспользоваться обычным компилятором gcc, сообщив ему, что надо подключить библиотеку GTK+. Для этого мы вызываем утилиту pgk-config. Эта утилита ищет установленные в системе библиотеки и возвращает путь к ним. В данном случае нам нужна библиотека gtk+, что мы и указываем в параметре.

gcc main.c -o gtkdemo `pkg-config —cflags —libs gtk+-2.0`

Теперь давайте подготовим эту программку для распространения.

Создайте каталог проекта. Назовите его gtkdemo. В нём, как обычно, каталог src. В каталоге src – вышеуказанный файл main.c.

В корневом каталоге создайте файл configure.ac

Вы, конечно, заметили, что, помимо уже знакомых строк мы сюда включаем директиву PKG_CHECK_MODULES. Эта директива запускает уже знакомую утилиту pkg-config. Путь к заголовочным файлам библиотеки gtk+ сохраняется в переменной DEPS_CFLAGS. Путь к библиотечным файлам – в переменной DEPS_LIBS.

Ещё в корневом каталоге создайте файл Makefile.am

А в каталоге src – другой файл Makefile.am

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

Всё! Собираем, как обычно.

touch NEWS README AUTHORS ChangeLog

Далее можете при желании инсталлировать программу.


Или подготовить дистрибутив.

В этот дистрибутив будет входить и файл проекта (qtdemo.pro). Поэтому пользователи, получив такой пакет не должны запускать configure. Всё, что им надо, это дать следующие команды:

Хотя qmake не требует обязательного присутствия в дистрибутиве файла README, желательно такой файл создать, и описать подробно, как правильно устанавливать программу. Будет неприятно, если пользователь будет источать на вас весь запас бранных слов только из-за того, что у него не установлена библиотека Qt, или из-за того, что его не предупредили, что в данном пакете не надо запускать ./configure.

Курьёзно, что никто вам не запрещает пользоваться утилитой qmake для сборки самых обычных консольных программ, не имеющих никакого отношения к Qt.

Если мы возьмём нашу последнюю версию, то там к программе требовалось подключить библиотеку libcalculate.

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

  1. Программы с оконным интерфейсом на Linux
  2. Этапы создания программы с оконным интерфейсом

Список литературы

  1. Семакин И.Г. Основы алгоритмизации и программирования. Учебник для студентов учреждений среднего профессионального образования — 3-е изд., стер. — М. : Издательский центр «Академия», 2013. 400 с.
  2. Семакин И., Шестаков А. Основы алгоритмизации и

программирования. Практикум. Учебное пособие М.: Академия, 2013г. – 144с.

  1. Голицына О.Л., Попов И.И. Основы алгоритмизации и

программирования: учебное пособие. М.: Форум, 2014г. – 432с.

  1. С. Скиена. Алгоритмы. Руководство по разработке. СПб.: БХВ-

Петербург, 2011г. – 720с.

  1. Т.Х. Кормен. Алгоритмы. Вводный курс. М.: Вильямс. 2014г. – 208с.
  2. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы.

М.: Вильямс, 2010г.-720с.

Официальный сайт ГБПОУ МО «Орехово-Зуевский железнодорожный техникум имени В.И. Бондаренко»

Сайт Министерства образования Московской области

Официальный сайт городского округа Орехово-Зуево

Книга о истории Ореховского индустриального техникума

Лекции по конструированию компиляторов

Название Лекции по конструированию компиляторов
Дата публикации 08.02.2014
Размер 91.59 Kb.
Тип Книга

skachate.ru > Информатика > Книга

Лекции по
конструированию компиляторов

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

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

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

Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

^ Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

2.2. Конечные автоматы 14

2.3. Построение детерминированного конечного
автомата по недетерминированному 16

2.4. Построение детерминированного конечного
автомата по регулярному выражению 18

2.5. Построение детерминированного конечного
автомата с минимальным числом состояний 21

2.6. Программирование лексических анализаторов 23

2.7. Конструктор лексических анализаторов LEX 27

^ Глава 3. Синтаксический анализ 32

3.1. Основные понятия и определения 32

3.2. Таблично-управляемый предсказывающий разбор 34

3.2.1. Алгоритм разбора сверху-вниз 34

3.2.2. Множества FIRST и FOLLOW 38

3.2.3. Конструирование таблиц
предсказывающего анализатора 40

3.2.4. LL(1)-грамматики 41

3.2.5. Удаление левой рекурсии 42

3.2.6. Левая факторизация 44

3.2.7. Рекурсивный спуск 45

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 49

3.3. Разбор снизу-вверх типа сдвиг-свертка 50

3.3.2. LR(k)-анализаторы 52

3.3.3. LR грамматики 57

3.3.4. Конфликты разбора типа сдвиг-свертка 63

3.3.5. Восстановление после синтаксических ошибок 64

^ Глава 4. Элементы теории перевода 65

4.1. Преобразователи с магазинной памятью 65

4.2. Синтаксически управляемый перевод 66

4.3. Атрибутные грамматики 70

4.3.1. Определение атрибутных грамматик 70

4.3.2. Атрибутированное дерево разбора 71

4.3.3. Язык описания атрибутных грамматик 72

4.3.4. Классы атрибутных грамматик и их реализация 75

^ Глава 5. Контекстные условия языков программирования 77

5.1. Описание областей видимости и блочной структуры 77

5.2. Структура среды Модулы-2 78

5.3. Занесение в среду и поиск объектов 81

^ Глава 6. Организация таблиц символов компилятора 89

6.1. Таблицы идентификаторов и таблицы символов 89

6.2. Таблицы идентификаторов 90

6.3. Таблицы символов и таблицы расстановки 93

6.4. Функции расстановки 94

6.5. Таблицы на деревьях 96

6.6. Реализация блочной структуры 100

6.7. Сравнение различных методов реализации таблиц 100

^ Глава 7. Промежуточные представления программы 102

7.1. Представление в виде ориентированного графа 102

7.2. Трехадресный код 102

7.3. Линеаризованные представления 107

7.4. Виртуальная машина Java 109

7.5. Организация информации в генераторе кода 113

7.6. Уровень промежуточного представления 115

^ Глава 8. Генерация кода 116

8.1. Модель машины 116

8.2. Динамическая организация памяти 119

8.2.1. Организация магазина со статической цепочкой 120

8.2.1. Организация магазина с дисплеем 124

8.3. Назначение адресов 126

8.4. Трансляция переменных 128

8.5. Трансляция целых выражений 134

8.6. Распределение регистров при вычислении
арифметических выражений 136

8.7. Трансляция логических выражений 145

8.8. Выделение общих подвыражений 153

8.9. Генерация оптимального кода методами
синтаксического анализа 157

8.9.1. Сопоставление образцов 157

8.9.2. Синтаксический анализ для Т-грамматик 160

8.9.3. Выбор дерева вывода наименьшей стоимости 168

Глава 1. Введение

1.1. Место компилятора в программном обеспечении

Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые «универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel-80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает большое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.

Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM/RS-6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.

^ 1.2. Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции показаны на рис. 1.1.

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

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

Лексический Диагностика
анализ Поток лексем
таблицы имен
Конечные и констант
автоматы
Синтаксический Диагностика
анализ
Дерево разбора
Контекстно- + таблицы
свободные имен и констант
грамматики

Контекстный
анализ Диагностика
Атрибутированное
Атрибутные дерево +
грамматики таблица символов

Генерация Промежуточная форма
промежуточного (префиксная, пост-
представления фиксная,тройки идр.)

СУ-трансляция
Оптимизация
Промежуточная форма
Потоковый (ориентированный граф)
анализ

Генерация кода
Таблицы решений,
Объектный
динамическое модуль
программирование и др

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

Основная задача синтаксического анализа — разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) — при использовании систем автоматизации построения синтаксических анализаторов.

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

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

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

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

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

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

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

Синтаксический разбор языков программирования

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

Но ввиду отсутствия образования, не могу вникнуть в суть ГРАММАТИК СИНТАКСИЧЕСКОГО РАЗБОРА.
То есть суть почти понимаю и могу решать простые задачи и упражнения по разбору (чисто их правилами разбора), но очень в отрыве от любого кода или даже просто алгоритма. Программирую на бейсике .
Книги конечно читаю, но там всё объяснение в формулах и всё как-то не однозначно.
Очень хотелось бы получить ответы от знающих людей на несколько вопросов по этой теме, что-бы было от чего отталкиватся.

1) Насколько я понял LL(1) грамматика самая простая и быстрая, это так -?
Простая всмысле ручного программирования, и парсер будет самый эффективный по скорости разбора -?

2) Является ли EcmaScript (JavaScript) языком подходящим для LL(1) грамматики -? или только LR грамматики -?

3) ТЕРМИНАЛЫ это — «for», «next», «else», то есть конкретные однозначные имена операторов, переменных и тд. НЕТЕРМИНАЛЫ это — формулы, выражения, конструкции, то есть не конкретный оператор с именем «FOR», а просто абстактно любой «оператор» Я правильно понял -?

4) Из википедии: Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики.

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

Если не трудно, подскажите пж-ста, конкретные однозначные ответы, задолбали эти абстракции.
СПАСИБО.

06.08.2020, 18:32

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

Запоминание разных языков программирования
Приветствую. Только начал изучать C++, до этого изучал VB.Net. В связи с этим возник вопрос.

Описание языков программирования + фреймворки
Задача: нужно быстро получить общее представление о том, на чем сейчас программирует народ. .

Необходим совет по изучению языков программирования.
Здрастсвуйте. Есть такой вопрос. Решил выучить язык программирования. Выбор пал на С++ или C#. Я.

Как делаются диалекты языков программирования?
Как делаются диалекты языков программирования? Прошу расписать полный путь (допустим у нас взят.

10.08.2020, 12:24 [ТС] 2

Здравствуйте. Жаль ни кто подсказать не может.
У меня за неделю неожиданно продвинулись познания, поэтому отвечу сам себе

1) Да
2) с ECMASCRIPT точно справится «Грамматики с операторным предшествованием»
3) Да с оговорками
4) Анализирует поток слева на право — это начиная с первой буквы до конца текста.

Виной всему эта книга : Конспективное изложение теории языков часть 1, 2015г
Есть ещё часть 2, практическая.

Написано по доходчивей, чем обычно пишут в такой литературе.
Вот пример объяснения грамматики:

Рассмотрим грамматику, которая описывает синтаксическую конструкцию «объявление переменной» в стиле языка Си:
G12a(, , <
(1) S→ t «;»
(2) A→ d | (3) A «,»d
>,S).
В этой грамматике:
(1), (2), (3) — номер применяемого правила.
— символ «t» обозначает произвольный тип переменной;
— символ «d» обозначает произвольный идентификатор;
— символы «;» и «,» обозначают сами себя. Символы заключены в кавычки, чтобы отличить их от соответствующих знаков пунктуации.
— символ «S» является целевым и обозначает оператор объявления, то есть всю конструкцию оператора.
— символ «A» обозначает список объявляемых переменных.
Правило (1) S→ tA«;» имеет следующий смысл:
Строка объявления – это тип, список переменных, точка с запятой.
Правило (2) A→ d: список переменных – это идентификатор
Правило (3) A→ A «,»d : список переменных – это список переменных, запятая, идентификатор
С помощью этой грамматики порождаются цепочки вида:
«тип ид;»
«тип ид, ид;»
«тип ид, ид, ид;» и т.д.
Здесь «тип» обозначает произвольный тип t (тип объявляемой переменной), а «ид», соответственно- некоторый произвольный идентификатор d (имя переменной).
Грамматика порождает цепочку «тип ид;» следующим образом:
S → (1) tA; →(2) td;
Цепочка вида «тип ид, ид;»
Преобразовывается так:
S → (1) tA; → (3) tA,d; → (2) td,d;.

Моё . Описание смысла этого преобразования :
Оператор объявления переменных (S) содержит : тип переменных(t), список переменных(A), точка с запятой(
Далее, если при чтении текста программы выясняется, что переменная в списке не одна, то применяем правило (3) и распиливаем список переменных (A) на список переменных(A)+ запятая(,)+ имя переменной(d)), то есть выдёргиваем переменную(d) и запятую из списка(A) и пишем их рядом. И так пока в списке(A) не останется только одна переменная (d).

Если в списке остаётся только одна переменная, то применяем правило (2), то есть полностью заменяем (оставшийся) список переменных(A) на имя последней переменной(d), а символ (A) полностью исключаем из формулы.

Остальное я не буду переписывать.
Не знаю, можно ли выкладывать ссылки сюда? Я накопытил более 100 книг и больших статей по теме.

Спасибо себе, дальше я сам

11.08.2020, 14:25 [ТС] 3

Всем привет!
Кому интересна тема » компиляторы, интерпретаторы, трансляторы, синтаксический разбор языков программирования, грамматики разбора и подобное «.

Вот подборка литературы (РУС) на данную темы.

Вот перечень файлов в архиве:

Вирт — Разработка ОС и компилятора. 2012 с исходниками
31-Конечный-автомат
instruction_tables — таблица времени выполнения инструкций ассемблера
LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ
Абельсон Х. Структура и интерпретация компьютерных программ.2004
Автоматное программирование
Алгоритмы оптимизации кода
Алгоритмы, языки, автоматы и компиляторы
Ахо — Компиляторы — Принципы, Технологии, Инструменты 2003
Ахо, — Компиляторы. Принципы, технологии, инструменты.2ed.2008
Баранов язык ФОРТ и его реализации 1988
Вирт Н. — Построение компиляторов (Классика программирования) — 2010
Виртуальные машины компиляция
Восходящие анализаторы
Генератор синтаксических анализов для КС грамматик 2010
Гриффитс А.GCC. Настольная книга. Диасофт.[RUS,624p,2004]
Гуренко В.В. Введение в теорию автоматов
Давайте создадим компилятор
ИНТЕРПРЕТАТОР СКРИПТОВОГО ЯЗЫКАJAVASCRIPT
Интерпретация Лиспа
Карпов — Основы построения трансляторов (2005)
Конечные автоматы. Разбор выражений
Конспективное изложение теории языков 2015
Конструирование компиляторов (учебное пособие) 2015
Креншоу Д. Пишем компилятор
Лекции Грамматики слабого предшествования
Лекции о компиляции
ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ 2009
Лекции по транслятору
ЛЕКЦИЯ № 3 ТЕОРИЯ ЯЗЫКОВ И ФОРМАЛЬНЫХ ГРАММАТИК
Лингвистическое обеспечение а. систем
МАГАЗИННЫЕ АВТОМАТЫ ГЛАВА 5
МЕТОДЫ ТРАНСЛЯЦИИ конспект лекций ч1
Методы трансляции уч. пособие 2000
Методы ускорения алгоритмов распознавания символов
Недетерминированные конечные автоматы 2007
Недетерминированные конечные автоматы
О некоторых свойствах автоматов с магазинной памятью
Опалёва. Языки программирования и методы трансляции (2005)
Основы разработки трансляторов в САПР
Основы трансляции конспект лекций
Основы функционального программирования 2004
Парсер-комбинаторы и левая рекурсия
Построение простейшего дерева вывода
Практикум по теории языков и трансляции 2015
Приведение грамматики к виду LL(1)
Принципы построения распознавателей КС-языков без возвратов
Программа управления компиляцией GNU make Версия 3.79
Проект «исследовательский компилятор»
Разбор и вычисление выражений
Редкая профессия
Робин Хантер — основные концепции компиляторов 2002
Свердлов Языки программирования и методы трансляции 2007
Серебряков В.А. — Основы конструирования компиляторов — 2001
Способы внутреннего представления программ
Сравнение алгоритмов восходящих и нисходящих.
Теорема о равносильных определениях LL(1)
Теория автоматов 2001
Теория и практика языков программирования 2013
Теория и реализация языков программирования 2006
Теория синтаксического анализа, перевода и компиляции 1978
Теория синтаксического анализа, перевода и компиляции. 1978 Том 2
Теория языков программирования и методы трансляции
Технологии трансляции 2008
Трансляторы.chm
Фомичев — Формальные языки
Формальные грамматики и языки 1999
Формальные языки и основы трансляторов 2003
Элементы теории конечных автоматов 2010
Языки и трансляции 2008
Языки программирования и методы трансляции 2007
Языки программирования и методы трансляции 2013 конспект
Языки программирования и методы трансляции ч2
Языки программирования и методы трансляции
ЯЗЫКИ ПРОГРАММИРОВАНИЯ концепции и принципы 1986
Курс о теории формальных языков
Курс Основы построения трансляторов
Папка со статейками из инета

Пользуйтесь на здоровье!

12.08.2020, 16:12 [ТС] 4

Уточнение по поводу терминальных — нетерминальных символов. Что бы не было вопросов.

Лексический анализ текста — это разбор символов входного текста (из букв и цифр) на лексемы.
Лексема – простейшая смысловая конструкция распознаваемого языка,
может состоять из нескольких символов (знаков, букв, цифр), например это может быть
ключевое слово («FOR» , «NEXT» и т.д.») или идентификаторы («A» -имя переменной)
или знаки пунктуации («,» «.» «:» «;» и т.д.) или знаки математических операций («+» «-» «*» «/» и т.д.)
или литералы («123» — непосредственная запись значения: символьная, числовая или строковая)

Лексема определённой категории – токен.

После лексического анализа образуется поток токенов- лексем, который является входным текстом для синтаксического анализа, а токены – ТЕРМИНАЛЬНЫМИ символами для синтаксических грамматик разбора.

Нетерминальные символы – это условные символы, обозначающие КОНСТРУКЦИИ языка, состоящие из токенов, а не отдельные токены. Например: IF – токен, THEN – токен, ELSE – токен, а условный символ «А», обозначающий синтаксическую конструкцию «IF then Else» — это и есть НЕТЕРМИНАЛЬНЫЙ символ «А».

А в основном, смысл грамматик разбора в подмене по ОПРЕДЕЛЁННЫМ ПРАВИЛАМ нетерминалов «А» на терминалы «а» — они же токены.
Всё просто.

Лекции по конструированию компиляторов глава 6 контекстные условия языков программирования

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

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

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

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

Курс лекций по основам программирования Учебно-методическое пособие (стр. 1 из 9)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

«Нижегородский государственный университет им. Н.И. Лобачевского»

Кафедра экономической информатики

Курс лекций по основам программирования

Рекомендовано методической комиссией экономического факультета

для студентов высших учебных заведений, обучающихся

по направлениям экономика, менеджмент

Малыженков В.И. Информатика и вычислительная техника. Курс лекций по основам программирования: Учебно-методическое пособие – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. – 52 с.

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

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

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

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

Рецензент: доцент, к.т.н. Громницкий Владимир Семенович

© Малыженков В.И., 2011

университет им. Н.И. Лобачевского, 2011

Глава1. Основы компьютерной грамотности………………. …………………5

1. Что такое компьютер. 5

2. Базовая конфигурация ПК………………………………………………..5

3. Операционные системы (ОС)………………………………………….…7

4. Файловая система MS DOS и WINDOWS……………………………….8

5. Структура файловых систем………………………………….…………10

Глава 2. Обработка данных в среде алгоритмических языков……………..…11

1. Парадигмы программирования………. ………………………………11

2. Этапы решения задач на компьютере…………………………………..11

3. Общее описание языков программирования (Basic, Pascal)…………..16

3.3.1. Арифметические выражения……………………………21

3.3.3 Строковые выражения………………………..…………..23

3.4.Основные исполняемые операторы языков……………………. 23

3.4.1 Оператор присваивания………………………………….24

3.4.2 Условный оператор………………………………………24

3.4.3 Оператор выбора по ключу…………………..………….25

3.4.5 Оператор безусловного перехода…………. ……….30

3.4.6 Операторы ввода – вывода……………………………30

3.5.Структура программного модуля……………………………. …31

4. Пример решения задач с модульным подходом……………………….32

6. Обработка файлов данных…………………………………..………….38

6.2. Основные операции по обработке файлов………..…………….39

6.3 Операторы (процедуры) обработки файлов в Basic и Pascal…. 40

7. Принципы структурного программирования…………..……………..44

8. Описание простейших модулей………………………………………..46

9. Пример составления программы в соответствии с принципами структурного программирования………………………………………47

Термин «информатика» впервые появился во Франции в начале 70-х годов и произошел от сочетания двух слов: information (информация, разъяснение) и automatique (автоматика, автоматический). Так образовалось французское слово informatique . В русском языке вместо вольного перевода этого термина как «информационная автоматика» утвердилось понятие «информация и средства её автоматической обработки». В США укоренился другое словосочетание — с omputer science – наука о компьютерах.

В нашем курсе мы будем представлять информатику как составляющую следующих компонент:

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

Глава1. Основы компьютерной грамотности.

1. Что такое компьютер?

Термин «компьютер» образован от английского слова compute – вычислять. Так же переводится и английское слово calculate , однако под compute обычно понимается выполнение более сложных операций, в том числе и логических. Так появилось два типа счетно-решающих устройств: компьютеры и калькуляторы.

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

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

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

2. Базовая конфигурация ПК.

К основным устройствам персонального компьютера относятся:

1) системный блок;

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

Кроме того в системном блоке находятся:

HDD, НЖМД – hard disk drive, накопитель на жестких магнитных дисках (жесткий диск, винчестер) — устройство хранения информации. Информация с HDD пересылается в оперативную память для обработки или на внешние устройства. Отличается от оперативной памяти существенно большими объемами хранимой информации, но меньшей скоростью доступа к ней. На винчестере храниться важнейшая часть программного обеспечения любого компьютера — операционная система;

FDD, НГМД – floppy disk drive – дискета, предназначенная для переноса информации с одного на другой компьютер;

CD ROM – compact disk read only memory (память только читается);

DVD –R, RW – design video drive, диски для чтения или чтения-записи. Отличаются от CD , большим обьемом хранимой информации;

Видео – и сетевые карты;

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

Монитор – это устройство для просмотра вводимой и выводимой информации, диалоговое устройство.

Мониторы бывают разных типов: с ЭЛТ – электронно-лучевая трубка; ЖК – жидкокристаллические, плазменные. В настоящее время в основном используются ЖК-монитры. Мониторы обладают определенными характеристиками:

1. размер диагонали экрана (типовые 14″-21″, всего от 9″ до 42″ (23-106см);

2. частота обновления и регенерации от 75-до 110Гц. Ниже — мигание, выше – размывание и удвоение изображение;

3. разрешение – количество пикселей на миллиметр(мин:640х480, — 1024х768 — мах:1280х1024); размер пикселя в среднем 0.18-0.25 мм, не выше 0,28;

4. ТСО-92-95-99 – Total Cost Oqupation — это классы защиты потребителя от электромагнитного излучения экрана монитора.

Клавиатура является устройством ввода информации. С помощью клавиатуры можно вводить тексты, текстовые команды и некоторые специальные команды (Esc,Ctrl и другие).

Лекция 8. Языки программирования

1.1.Понятие «язык программирования»

1.2.Компиляторы и интерпретаторы

1.4.Классификация и обзор языков программирования

1.5.Объектно-ориентированное программирование (ООП)

1.6.Этапы подготовки и решения задач на компьютере

Компьютерная программа представляет собой логически упорядоченную последовательность команд, предназначен­ных для управления компьютером. Процессор компьютера исполняет программы, написанные на машинным кодом. Писать программы в машинных кодах вручную очень сложно, причем с ростом размера программы эта задача усложняется. В компьютерах первого поколения использовались программы, написанные в ма­шинных кодах, причем для каждого компьютера существовал свой собственный машинный код. В тот период (начало 50-х гг.) средства програм­мирования и программное обеспечение только зарождались и были еще не развиты. Для того чтобы сделать программу читабельной и иметь возможность следить за ее смысловой структурой, разработали символический язык ассемблер, близкий к машинному (конец 50-х – начало 60-х гг.), в котором появилось понятие переменной. Ассемб­лер стал первым полноценным языком программирования. Благода­ря этому заметно уменьшилось время разработки и возросла надеж­ность программ. Для записи кодов операций и обрабатываемой информации в ассемблере используются стандартные обозначения, позволяющие записывать числа и текст в общепринятом виде, для кодов команд приняты мнемонические обозначения, например MOV AX, BX (переместить машинное слово из регистра AX в регистр BX), ADD AX, CX (сложить регистр AX c CX), JMP loop1 (безусловный переход не метку loop1) и др. Для обозначе­ния величин, размещаемых в памяти, можно применять имена констант. После ввода программы ассемблер сам заменяет символические имена на адреса памяти, а символические коды команд на числовые. Исполь­зование ассемблера сделало процесс программирование более нагляд­ным. Дальнейшее развитие этой идеи привело к созданию языков программирования высокого уровня, в которых длинные и сложные последовательности машинных кодов были заменены одним един­ственным обозначающим их словом – операторы.

Понятие «язык программирования»

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

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

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

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

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

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

Илон Маск рекомендует:  Что такое код pdf_end_pattern
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL