Интерпретация блок-схем (DIPLOM)

Посмотреть архив целиком

63



Томский государственный университет


Факультет прикладной математики и кибернетики

Кафедра программирования





ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

зав. кафедрой программирования профессор, д.т.н.

_______________ А.Ю.Матросова

____ ” ________________ 1999 г.





Соловьёв Александр Станиславович


Система визуального программирования

Блок-схема” на основе языка блок-схем


(дипломная работа)





Научный руководитель доцент, к.т.н.

_________ Н.А.Белоусова




Автор работы

_________ А.С. Соловьев









Томск 1999

Реферат


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

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

Система создана в двух вариантах:

  • Под операционную систему MS-DOS 3.x и выше;

  • Под операционные системы Windiows 95, Windows 98 и Windows NT.

В первом случае, разработка велась с помощью языка Borland C++ 3.1 (совместима с языком Turbo C 2.0). Во втором, с помощью пакета Borland C++Builder 3.0.

Оглавление


Введение 4

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

1.1. Классификация 6

1.2. Сравнительная характеристика языков. 8

2. Трансляторы 9

2.1. Классификация 9

2.2. Компиляторы и интерпретаторы 9

3. Язык блок-схем 11

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

3.2. Блоки 12

3.3. Связки 14

3.4. Язык наполнения блок – схем 14

4. Система программирования 18

4.1. Графический редактор 18

4.2. Встроенный текстовый редактор 21

4.3. Интерпретатор 22

4.3.1. Этапы трансляции 22

4.3.2. Лексический анализ 24

4.3.2.1. Задачи лексического анализа 24

4.3.2.2. Сканер 25

4.3.3. Синтаксический и семантический анализ 27

4.3.4. Польская инверсная запись (ПолИЗ) 27

4.3.4.1. Алгоритм Дейкстры формирования ПолИЗа 28

4.3.4.2. ПолИЗ выражений, содержащих переменные синтаксиса 29

4.3.4.3. Алгоритм перевода ПолИЗа в машинные команды 31

4.3.5. Общая схема работы интерпретатора 34

4.4. Оболочка системы 35

4.4.1. Работа с файлами 35

4.4.2. Знакомство с системой 36

4.4.2.1. MS-Dos версия системы 36

4.4.2.2. Windows версия системы 40

4.5. Внутреннее представление данных 46

Заключение 48

Литература 49

Приложение 50

Приложение 1: Примеры блок-схем 50

Приложение 2: Матрицы переходов анализаторов 52

Приложение 3: Текст основных классов программы 58


Введение


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

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

Еще во времена становления программирования, когда программы писались на внутреннем языке ЭВМ – машинном коде (ассемблере), неотъемлемой частью разработки программ было использование блок-схем. Как мы все хорошо знаем: “ Схемой алгоритма называется такое графическое представление алгоритма, в котором этапы процесса обработки информации и носители информации представлены в виде геометрических символов из заданного ограниченного набора, а последовательность процесса отражена направлением линий ” [1]. Их применение значительно облегчало восприятие и анализ программы. Двумерное представление программы более ясно отражало ее структуру. Применение блок-схем позволяло быстрее и качественнее разрабатывать и отлаживать программы, а также облегчалось их сопровождение. Данное свойство блок-схем было “узаконено” и они стали обязательной частью документации.

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

Естественным развитием данной ситуации является объединение двух подходов в описании программ: в виде текста и блок-схемы. Результатом такого объединения является понятие визуального программирования. Под ним понимается способ описания алгоритма решения задачи в графическом виде, соединяющий достоинства текста и блок-схем программ. Что в сочетании с современными графическими возможностями ЭВМ и их способностью взять на себя рутинные операции и максимально упростить весь процесс программирования, делает это направление очень перспективным.

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

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

В 70ых годах были довольно успешные попытки создания систем, с помощью которых ЭВМ понимала язык блок-схем (например, ОДА). Но все-таки это были языки блок-схем не в чистом виде. В них присутствовали описатели, с помощью которых ЭВМ строила из алгоритма блок-схему.

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

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

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

1.1. Классификация


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

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

Искусственные языки, предназначенные для записи программ, называются языками программирования. Каждая ЭВМ имеет свой собственный язык программирования – язык команд или машинный язык и может исполнять программы, написанные только на этом языке. В машинном языке каждой команде соответствует определенная операция, которую может выполнять машина. Однако на машинном языке программировать трудно из-за чрезмерной детализации программы. Поэтому уже на ЭВМ первого и второго поколения для повышения производительности труда программистов начали применять языки программирования, не совпадающие с машинными языками. На ЭВМ третьего поколения машинный язык практически не применяется для программирования задач, за ним сохранилась лишь роль внутреннего языка ЭВМ.

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

  • Машинно-зависимые языки,

  • Машинно-независимые языки.

Машинно-зависимые языки, в свою очередь, делят на машинные и машинно-ориентированные.

Машинно-ориентированные языки иногда называют автокодами. Различают два уровня машинно-ориентированных языков. К первому уровню относятся языки символьного кодирования, иначе называемые мнемокодами, а ко второму – макроязыки.

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

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



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

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

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

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

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

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

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


1.2. Сравнительная характеристика языков.


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

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

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

2. Трансляторы

2.1. Классификация


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

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

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

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

Программа, полученная после обработки транслятором, либо непосредственно исполняется на ЭВМ, либо подвергается обработке другим транслятором.


2.2. Компиляторы и интерпретаторы


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

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

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

Интерпретаторы часто применяются в качестве отладочных и диалоговых трансляторов, обеспечивающих работу пользователя с машиной в диалоговом режиме с дистанционного терминала. Кроме того, интерпретаторы используют для исполнения (интерпретации) на ЭВМ программ, составленных для другой ЭВМ, а иногда в качестве последнего блока транслятора компилирующего типа. В последнем случае транслятор состоит из двух частей: первой – компилятора, переводящего программу на промежуточный язык, являющимся входным языком интерпретатора; второй – интерпретатора, исполняющего программу на промежуточном языке.

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

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

3. Язык блок-схем


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

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

“Схемой алгоритма называется такое графическое представление алгоритма, в котором этапы процесса обработки информации и носители информации представлены в виде геометрических символов из заданного ограниченного набора, а последовательность процесса отражена направлением линий ” [1].


Случайные файлы

Файл
Zadanie_05.09.07.doc
157328.rtf
72278-1.rtf
183019.rtf
121706.rtf