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

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

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

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

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

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

“____ ” ________________ 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].

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

Во-первых, несмотря на достаточно большое количество графических и текстовых редакторов (например: Page Maker, Corel Draw, Word и т.д.) нужны:

1. Свой графический редактор, так как настройка на внутренние форматы файлов этих систем приводит к неэффективному использованию ресурсов ЭВМ, Поэтому необходим эффективный, графический редактор, ориентированный только на объекты типа блоков.

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

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

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

1. Язык блок-схем (“Графический” язык),

2. Язык функционального наполнения блок-схем.

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

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

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

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

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

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

max=y;						max=x;

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

3.2. Блоки

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

В таблице 1 приведен перечень блоков для построения блок-схем алгоритмов.

таблица 1.

Рассмотрим функциональное назначение каждого блока.

“НАЧАЛО” С этого блока начинается исполнение блок-схемы. Присутствие этого блока обязательно. Необходимо заметить, что блок “НАЧАЛО” в блок схеме должен быть один.

“КОНЕЦ” После того, как обрабатывается этот блок, исполнение блок-схемы завершается. Присутствие данного блока также обязательно, но в отличие от предыдущего, блоков “КОНЕЦ” может быть несколько.

“АВТОМАТИЧЕСКИЕ ДЕЙСТВИЯ” Присутствие данного блока, как и всех последующих блоков, в схеме не обязательно. В блоке действий могут выполняться:

· любые математические действия, согласно правилам математики;

· стандартные функции, предоставленные системой “Блок-схема”;

· инициализация переменных.

“ПОДПРОГРАММА” В этом блоке происходит вызов подпрограммы, которую составил сам пользователь.

“ВЕТВЛЕНИЕ ПО УСЛОВИЮ” В этом блоке проверяется заданное условие на истинность. И в зависимости от результата осуществляется ветвление.

“ВВОД / ВЫВОД” При помощи этих блоков организуется интерфейс пользователя с исполняемой схемой, то есть вводится и выводится информация.

“МЕТКА” Помечает позицию блока, на который происходит переход во время выполнения связки “БП”. В этом блоке указывается соответствующая метка. Данный блок является частью связки - “БП”.

“БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ” В этом блоке указывается метка, на которую будет происходить переход. Этот блок является частью связки - “БП”.

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

“МУЛЬТИВЕТВЛЕНИЕ” В этом блоке находится переменная, по которой будет происходить мультиветвление. Блок “мультиветвление” является частью связки с аналогичным названием (описание связок смотрите далее).

“ВЕТВЬ” Блок “ветвь” является частью связки “мультиветвление”. В блоке “ветвь” задается константа, с которой выполняется сравнение значения, полученного в блоке “мультиветвление.”

3.3. Связки

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

Язык блок-схем располагает всего двумя связками:

· “БП” - безусловный переход;

· “Мультиветвление” – мультиветвление.

“БП” - представляет собой связку из двух блоков: “БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ” и “МЕТКА”. Входящие в связку блоки должны содержать одну и ту же метку.

“МУЛЬТИВЕТВЛЕНИЕ” представляет собой связку из последовательности блоков, которая начинается с блока “мультиветвление”. Далее идет последовательность блоков “ветвь”. Заканчивается данная связка тогда, когда встречается блок отличный от блока “ветвь”.

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

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

· С (его упрощенный вариант);

· Pascal (его упрощенный вариант).

“НАЧАЛО” С этим блоком связывается описание переменных. Переменные описываются следующим образом:

тип переменная 1, переменная 2, ... , переменная N;

тип переменная N+1, ...;

Множество типов в языке блок схем ограничено:

· int - целое ;

· long_int - длинное целое ;

· float - вещественное ;

· char - символьное .

Имя переменной - стандартный идентификатор имени в языке C, Pascal. Длина имени не ограничена.

“КОНЕЦ” Содержимое этого блока не просматривается.

“АВТОМАТИЧЕСКИЕ ДЕЙСТВИЯ” Здесь задаются выражения, строящиеся из переменных, констант, математических знаков, математических и стандартных функций:

+ сложение,

- вычитание,

* умножение,

/ деление,

= присвоение,

sin синус,

cos косинус,

tg тангенс,

ctg котангенс,

arcsin арксинус,

arccos арккосинус,

arсtg арктангенс,

arcctg арккотангенс,

ln натуральный логарифм,

lg десятичный логарифм,

abs абсолютное значение числа (модуль),

exp функция экспоненты,

mod взятие целой части при делении,

div взятие дробной части при делении,

^ возведение в степень,

sqrt нахождение квадратного корня,

sh гиперболический синус,

ch гиперболический косинус,

th гиперболический тангенс,

а также, стандартные функции, предоставляемые системой "Блок-схема":

randomize() инициализация датчика случайных чисел,

random() получение случайного числа,

clock() получение времени,

getch() получение кода нажатой клавиши,

kbhit() получение значения была ли нажата клавиша,

strlen() получение длины строки,

и т.д.

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

“ВЕТВЛЕНИЕ ПО УСЛОВИЮ” Текст этого блока должен представлять собой логическое условие, после которого ставится “;”. Условие может содержать логические связки И - &&, ИЛИ - ||, НЕ - !.

Например:

“ВВОД” В этом блоке через запятую указываются переменные значения которые вводит сам программист с терминала. После перечисления всех переменных ставится “;”

Например:

“ВЫВОД” Текст этого блока имеет следующую структуру:

“текст”, переменная 1, “текст”, переменная 2, ... , переменная N;

“текст”, переменная N+1, ...;

то есть, текстовые константы чередуются через запятую с переменными, которые надо вывести на экран монитора. В конце ставится “;”.

Например:

“БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ” Содержимым этого блока является имя метки с “;” на конце.

Например:

“МЕТКА” Определяется аналогично предыдущему блоку.

“ПОДПРОГРАММА” Содержится имя подпрограммы с параметрами.

Например:

“МУЛЬТИВЕТВЛЕНИЕ” Вариант оператора “switch” языка Си. В данном блоке содержится имя переменной, по которой будет выполняться ветвление.

Например:

“ВЕТВЬ” Блок “ветвь” может присутствовать только в связке “мультиветвление”. Отдельно не имеет смысла. В блоке “ветвь” задается константа, с которой выполняется сравнение значения, полученного в блоке “мультиветвление”.

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

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

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

Г.Р. - это программа, позволяющая программисту “рисовать” новые и редактировать старые блок-схемы. Пользователю предлагается в режиме меню следующие возможности для редактирования блок-схем:

* Удаление блоков;

* Установка блоков;

* Разметка планшета координатной сеткой;

* Скроллинг планшета;

* Выбор типа блоков (либо стрелки, либо сами блоки);

* Автоматическое соединение двух выделенных блоков на планшете;

* Изменение параметров планшета;

* Изменение палитры планшета (цветов);

* Возможности редактирования с помощью буфера обмена.

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

Рассмотрим понятие ПЛАНШЕТ . Назовём поверхность, на которой выполняется рисование блок-схемы ПЛАНШЕТОМ . Будем считать, что размеры планшета не ограничены. В каждый текущий момент пользователь находится в позиции планшета с координатами (X,Y). Координаты (X,Y) задаются в Декартовой системе координат, начало координат (0,0) - это середина планшета (именно в этой точке находится пользователь при начальном запуске системы “Блок-схема”).

Планшет может быть размечен координатной сеткой (рис.2.).

рис.2.

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

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

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

Y X₀ X₁ 640

Y₀

J

N_Y

Y₁

J+N_Y N_X

X

I I+N_X 480

схема 1.

Рассмотрим процедуру размещения элементов блок-схемы в окне редактора. Так как разрабатываемая система опирается на графический драйвер, поддерживающий разрешение 640 на 480 pixel, а координатные оси на экране расположены так, как показано на схеме 1, то окно редактора - это прямоугольная область экрана с координатами верхнего левого угла (X₀ ,Y₀ ) и с координатами нижнего правого угла (X₁ ,Y₁ ).

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

height =(Y₁ -Y₀ )/N_Y; это высота блока в экранных координатах;

width =(X₁ -X₀ )/N_X; это ширина блока в экранных координатах;

Далее установим соответствие между координатами блоков в координатной системе планшета и координатами блоков в экранной системе.

Будем считать, что существует другая система координат, в которой I~I’ и J~J’, и, зная, что координате (I,J) соответствует координата (X₀ ,Y₀ ), то, следовательно, I~I’=0 и J~J’=0. Аналогично для координат (I+N_X,J+N_Y), зная, что ей соответствует, координата (X₁ -width,Y₁ -height) будем иметь, что (I+N_X)~(I’+N_X)=N_X и (J+N_Y)~(J’+N_Y)=N_Y.

Таким образом для блока с координатами ( i , j), где ( i , j) принадлежит прямоугольнику [I,J,I+N_X,J+N_Y] будет иметь место следующее преобразование координат:

X = X₀ +(i-I)*width;

Y = Y₀ +(j-J)*height;

где X,Y экранные координаты блока (i , j). Когда выполнены эти преобразования, осуществляется вывод этой прямоугольной области в окно редактора. Вывод осуществляется последовательно, перебирая все элементы области.

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

Теперь рассмотрим другие функции графического редактора.

В системе “Блок-схема”, как и в любой другой интерактивной системе, заданы кодовые комбинации клавиш, благодаря которым можно не выполнять полный набор команды для выполнения какого-либо действия. Для этого достаточно нажать так называемые “горячие” клавиши. Информацию о них можно получить, выбрав соответствующий пункт в меню “СПРАВКА”.

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

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

Выполняется эта процедура с помощью клавиш в MS-Dos:

<Page Up> - вверх;

<Page Down> - вниз;

<Ctrl><Right Arr> - вправо;

<Ctrl><Left Arr> - влево;

а также посредством манипулятора мышь при выборе соответствующих кнопок меню.

Выбор блока, который необходимо установить в данную позицию выполняется через пункт “БЛОКИ” или “СТРЕЛКИ” в подменю “РЕДАКТОР” главного меню. Выбранный блок прорисовывается, когда нажата клавиша <ENTER> или одновременно нажаты левая и правая клавиши манипулятора мышь, а также когда выбран пункт “УСТАНОВИТЬ” в подменю “РЕДАКТОР” главного меню.

Выбор типа блоков (либо стрелки, либо блоки) можно осуществлять посредством “горячих” клавиш:

<Ctrl><S> - стрелки;

<Ctrl><B> - блоки.

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

Удаление блоков выполняется следующим образом: c помощью указателя выбирается блок, который нужно удалить, а потом нажимается клавиша <DELETE>, либо выбирается пункт “УДАЛИТЬ” в подменю “РЕДАКТОР” главного меню.

В Windows варианте эти возможности можно выбирать посредством манипулятора мышь или аналогичным образом с помощью клавиатуры. Кроме того, Windows вариант предусматривает соединение двух заданных блоков с помощью волнового алгоритма Ли[10].

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

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

Редактор для среды Windows по своим возможностям не уступает большинству современных текстовых редакторов, предоставляемых фирмой Borland. Редактор обладает следующими возможностями:

· нет ограничения на размер текста внутри блока;

· допускаются работа с буфером обмена;

· существует возможность изменения шрифта текста;

· два режима набора текста программы (режимы вставки и перезаписи);

· поиск текста по заданному образцу;

· замена заданного образца текста на заданный текст.

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

С помощью клавиш управления осуществляется перемещение курсора по окну редактора текста блока. А с помощью клавиш <DEL> и <BACKSPASE> осуществлять удаление текста со сдвигом строки.

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

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

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

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

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

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

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

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

Перевод на внутренний язык

Оптимизация
Анализ

Оптимизация

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

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

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

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

Транслятор, предложенный в данной работе, имеет следующую структуру:

· Поиск блока “начало” · Построение свертки текста блока · Проверка синтаксиса блока “начало” · Выделение памяти под переменные
· Построение сверток всех блоков · Проверка синтаксиса блоков · Построение ПолИЗа
· Установка связей между блоками · Проверка правильности связей
		· Трансляция и выполнение · Пошаговая трансляция

Оптимизация не выполняется.

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

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

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

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

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

1) перекодировать исходную программу, рассматриваемую как входная строка, и привести ее к стандартному входному языку;

2) выделить и собрать из отдельных знаков в слова идентификаторы и служебные слова (основные символы языка);

3) выделить и собрать из цифр, а также перевести в машинную форму числовые константы.

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

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

Другой вид контроля, иногда применяемый при лексическом анализе, - проверка сочетаемости стоящих рядом символов. Например, пары символов begin x и else begin – сочетаемы (допустимы), но те же символы, стоящие в обратном порядке: x begin и begin else – несочетаемы. В то же время пары +end, +/, *[ - несочетаемы ни в каком порядке. Основной (главной) частью лексического анализатора является сканер.

4.3.2.2. Сканер

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

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

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

Пусть входная строка: s₁ , s₂ , s₃ ,…, s_n .

s,i СКАНЕР L,t

где L – лексема, t – ее тип.

0, константа типа int

1, константа типа long_int

t= 2, константа типа float

3, константа типа char

4, идентификатор

-1, ошибка, не распознаваемый тип лексемы

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

s_i класс символа k

где

1, если s_i буква

2, если s_i цифра

3, если s_i `

k= 4, если s_i “ или ”

5, если s_i верный знак

0, если s_i ошибочный символ

Тогда диаграмма состояний имеет вид: (смотри в приложении).

Входная программа

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

Рис.3. Блок схема лексического анализа.

ЗАМЕЧАНИЕ:

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

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

Изобразим блок - схему работы лексического анализатора (рис.3.).

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

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

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

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

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

<переменная> = <выражение>

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

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

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

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

Цель польской инверсной записи – представить операции исходного выражения в порядке их выполнения (вычисления). В данной работе был использован алгоритм построения ПолИЗа, который был предложен Дейкстрой.

Пример ПолИЗа:

Исходное выражение : x=a+f*c;

Выражение на ПолИЗе :xafc*+=.

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

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

ПРИОРИТЕТ ОПЕРАЦИИ – это целое число, означающее старшинство операции по отношению к другим операциям. Приоритет операций изменяется с использованием скобок ( и ) .

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

АЛГОРИТМ:

1. Если элемент операнд, то он заносится в ПолИЗ.

2. Если элемент операция, то она заносится в ПолИЗ через СТЕК по правилу.

2.1. Если СТЕК пуст, то знак операции заносится в СТЕК,

2.2. Иначе: если приоритет входного знака равен 0, то он заносится в СТЕК, иначе сравниваются приоритеты входного знака и знака в вершине СТЕКа.

2.3. Если приоритет входного знака больше приоритета знака в вершине СТЕКа, то он заносится в СТЕК.

2.4. Иначе из СТЕКа выталкиваются все знаки с приоритетом больше или равным приоритету входного знака в вершине СТЕКа и приписываются к ПолИЗу, затем входной знак заносится в СТЕК.

3. Особо обрабатываются ( и ) .

( - имея приоритет 0 сразу же заносится в СТЕК по 2.2.

) – имея приоритет равный 1 выталкивает из СТЕКа все знаки до ближайшей открывающей скобки ( , затем они взаимно уничтожаются.

4. При появлении признака конца выражения ( в нашем случае ; ) СТЕК очищается : все оставшиеся знаки выталкиваются и приписываются к ПолИЗу.

Так же ПолИЗу соответствует так называемое дерево ПолИЗа.

Пример: (x+a)*(x-b)+3;

Дерево:

x a x b

ПолИЗ: x a + x b - * 3 +.

Построение ПолИЗа по дереву осуществляется обходом дерева по правилу левое поддерево, правое поддерево, корень.

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

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

a[i+1]-b[i,j-1]*a[2*i+1]

Индексные выражения.

Выведем формулы вычисления адресов элементов массива.

Для одномерного массива а, описание которого на Паскале и Си имеет вид:

a: array [1..n] of integer; // Pascal

int a[n]; // C/C++

и каждый элемент имеет массива занимает k-байт.

Адрес первого элемента равен A . Выясним чему будут равны адреса других элементов. Для этого рассмотрим расположение элементов массива в физической памяти ЭВМ.

A +k +2k +3k A+k*(i-1)…

k байт

тогда a[i] А+k*(i-1) для языка программирования Паскаль, а для языка программирования C/C++ a[i] A+k*i. Тогда если элемент занимает k – байт, то

a[i] -----> A+k*(i-1) (1)

a[i] -----> A+k*i (1’)

Для двумерного массива:

b: array [1..m,1..n] of integer;// Pascal

int b[m][n];//Си

Адрес элемента с индексами i,j вычисляется по правилу:

b[i,j] -----> B+k*((i-1)*n+(j-1)) (2)

b[i,j] -----> B+k*(i*n+j) (2’)

Для формирования ПолИЗа введем операцию АЭМ (адрес элемента массива) с операндами:

1. Идентификатор массива, ему после распределения памяти транслятором будет соответствовать адрес первого элемента массива.

2. Индексное выражение.

Результат: адрес элемента массива вычисленный по формулам (1)-(2’).

ПолИЗ: a i 1 + А.Э.М. b i j 1 – А.Э.М. a 2 i * 1 + А.Э.М. * -

Анализ ПолИЗа говорит о том, что у операции АЭМ переменное число операндов и их количество надо задавать явно. Сделаем следующую замену: АЭМ – k] , где k - количество операндов.

Тогда ПолИЗ: a i j + 2] b i j 1 – 3] a 2 i * 1 + 2] * -.

Изобразим дерево выражения: (смотри рисунок )

-

А.Э.М. *

а + А.Э.М. А.Э.М.

i 1 b i – a +

i j * 1

2 i

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

ПРАВИЛА:

1. [ , имея приоритет 0 заносится в СТЕК [k , где k – минимальное число операндов операции А.Э.М.

2. , , имея приоритет 1 выталкивает из СТЕКа все ближайшие знаки до ближайшей [k и увеличивает k на 1: k=k+1; , никуда не заносится.

3. ] , имея приоритет 1 выталкивает из СТЕКа все знаки до ближайшей [k , которая удаляется из СТЕКа, а в ПолИЗ заносится k] .

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

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

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

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

Рассмотрим пример: a+b*c-d/(a+b)

ПолИЗ: abc*+dab+/-

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

Результат выполнения операции фиксируется в виде рабочей переменной вида r_j . После очередной операции рабочая переменная r₁ или r₂ вычеркивается, освободившуюся рабочую переменную можно использовать вновь для записи результата операции. Использование каждый раз свободной рабочей переменной с минимальным номером экономит количество занятых рабочих переменных. Такой пример экономии рабочих ячеек приведен в таблице № 2. Это же правило используют в трансляторах.

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

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

Таблица № 2

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

В рассмотренном примере встречались двухместные операции. Каждая такая операция, как правило, заменяется одной или двумя машинными командами (в зависимости от адресации машины). В общем случае операция R может иметь k операндов (k ³1). На ЭВМ такая операция должна заменяться группой машинных команд. Будем считать, что к моменту генерирования машинных команд проведено распределение памяти, и каждый операнд представлен соответствующей ссылкой на таблицу имен, содержащую адрес операнда. Аналогично, для каждой рабочей переменной известен ее адрес.

Для трансляции выражений из обратной польской записи в машинные команды используется стек операндов (СО) с указателем i . В исходном состоянии стек операндов пуст, а указатель i= 1. Будем также считать, что в исходном состоянии номер первой свободной рабочей переменной j =1.

Алгоритм трансляции состоит в следующем.

1. Взять очередной символ S из обратной польской записи выражения.

2. Если S – операнд, то занести S в СО[i ] , выполнить i=i+ 1 и перейти к пункту 1, иначе к пункту 3.

3. Если S – не знак операции, то перейти к пункту 4, иначе, если S – знак операции R , выполнить следующее

3.1. Среди элементов стека СО[i-k ], где k – число операндов операции R , найти рабочую переменную с минимальным номером l . Если в рассматриваемых элементах стека нет рабочих переменных, то положить l=j .

3.2. Записать машинные команды, реализующие оператор присваивания r_l =R (СО[i-k ],…,СО[i- 1]). Здесь R (x₁ , … , x_k ) – результат выполнения операции R над операндами x₁ , … , x_k .

3.3. Занести символ r_l в СО[i-k ].

3.4. Выполнить: i=i-k+ 1 и j=l+ 1. Перейти к пункту 1.

4. Если запись выражения исчерпана, то трансляция закончена. Стек операндов должен содержать только переменную r_l , в противном случае нужно записать информацию об ошибке в таблицу ошибок.

Вход

Рис.4. Блок-схема перевода обратной польской записи в машинные команды.

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

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

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

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

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

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

struct Blocks

{

int type; // тип блока

int x; // координаты блока на планшете по оси X

int y; // координаты блока на планшете по оси Y

int true_x; // координаты блока на планшете для перехода

int true_y; // по ИСТИНЕ (TRUE)

int false_x; // координаты блока на планшете для перехода

int false_y; // по ЛЖИ (FALSE)

char* text; // указатель на текст блока

struct Blocks far *next; // указатель на следующий блок в списке блоков

};

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

НАЧАЛО – блок «НАЧАЛО» отвечает за описание переменных. Строка символов, принадлежащая этому блоку, переводится в список указателей (см. параграф «Структуры данных»). Затем происходит формирование таблицы переменных одновременно с лексической и семантической проверкой. Если функция блок отработала без ошибок, то процесс интерпретации продолжается, иначе нет.

КОНЕЦ – Функция блока ничего не делает. После того, как она передаст управление функции управления интерпретацией, интерпретатор заканчивает свою работу.

АВТОМАТИЧЕСКИЕ ДЕЙСТВИЯ – Строка символов переводится в массив указателей. Затем этот массив переводится в обратную польскую запись (ПолИЗ) и выполняется. Предварительно производится лексический и синтаксический анализ. Если ошибок нет, то управление передается функции управления интерпретацией.

ПОДПРОГРАММА – Предварительно производится лексический и синтаксический анализ. Потом текст переводится в список дескрипторов ПолИЗа, и если ошибок нет, то управление передается функции управления интерпретацией.

ВЕТВЛЕНИЕ ПО УСЛОВИЮ – Сначала производится синтаксический и лексический анализ. Затем строка символов переводится в массив указателей, потом этот массив переводится в ПолИЗ и выполняется. После выполнения ПолИЗа осуществляется семантический анализ. Если ошибок не было, то в зависимости от результата анализа функции управления будет передана информация, как выполнять ветвление.

ВВОД\ВЫВОД – В этих блоках происходит семантический и лексический анализ. По результатам анализов происходит либо выдача сообщений в окно, либо вывод (ввод) значений переменных. Особенность возникает при обработке массивов, так как в этом случае необходимо вычислять адрес элемента массива. Для этого, выражение стоящие внутри квадратных скобок ( [ , ] ) переводится в обратную польскую запись и после обработки ПолИЗа, происходит либо ввод, либо вывод определенного элемента массива. По окончании работы функции обработки блоков, они передают управление функции управления интерпретацией.

МЕТКА – Обработка этого блока происходит в функции блока БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ.

БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ – Функция обработки этого блока ищет в списке структур блоков блок, содержащий такую же метку, которую содержит и он сам (блок). По окончанию работы функция обработки блока передает функции управления интерпретацией, на какой блок нужно осуществить переход для продолжения интерпретации программы.

МУЛЬТИВЕТВЛЕНИЕ При выполнение этого блока формируется константа с которой будет выполняться сравнение при встрече с блоком “ветвь.”

ВЕТВЬ Обработка данного блока происходит следующим образом: если константа, содержащаяся в этом блоке, совпадает с константой, которая была сформирована в блоке мультиветвление, то происходит переход по истине (true), иначе по лжи (false).

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

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

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

В системе “Блок схема” для работы с файлами создана унифицированная и очень дружелюбная система диалогов с пользователем. Она позволяет легко сохранять схемы на внешнем запоминающем устройстве (дискета или винчестер) или считывать уже созданные. За основу диалогов системы взяты диалоги, разработанные фирмой Borland, и несколько модифицированы в варианте под операционную систему MS-Dos, а под Windows приняты стандартные диалоги в среде MS Windows 95. Схема, созданная в системе “Блок схема”, хранится на диске и имеет свое уникальное имя. Файл имеет расширение sch – MS-Dos и scw - Windows.

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

struct FILE_SCHEME

{

int type; // тип блока

int x; // координаты блока на планшете по оси X

int y; // координаты блока на планшете по оси Y

int true_x; // координаты блока на планшете для перехода

int true_y; // по ИСТИНЕ (TRUE)

int false_x; // координаты блока на планшете для перехода

int false_y; // по ЛЖИ (FALSE)

};

и строка, содержащая текст данного блока.

Эти записи строятся следующим образом. В поле type содержится тип, сохраняемого блока. В полях x,y – координаты блока на планшете. В полях true_x, true_y – координаты блока на планшете для перехода по истине. И соответственно, в полях false_x, false_y - координаты блока на планшете для перехода по условию ложь. В последнем поле содержится текст соответствующий данному блоку или текстовая константа NULL, если текста нет.

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

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

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

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

Итак, Вы решили поработать с системой, предлагаемой в данной работе. Вы должны находиться в операционной системе MS-DOS 3.0 или Windows 3.1 и выше. Выбрав в диспетчере файлов имя программы MAIN_CURS.EXE, запустите ее. На мониторе компьютера появится главное окно программы, в котором будут указаны автор работы и его научный руководитель. После этого нужно нажать клавишу <ENTER>, либо подвести указатель манипулятора мышь на кнопку <Ok> и нажать левую кнопку манипулятора.

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

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

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

Текст этот пункт предназначен для набора и редактирования текста внутри блока.

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

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

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

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

Если Вы нажмете комбинацию <ALT><T>, то перед Вами появится окно текстового редактора. В нем Вы можете производить набор и редактирование текста, который принадлежит данному блоку. Для выхода из него надо нажать клавишу <Esc> при этом текст данного блока будет автоматически сохранен.

Если Вы решили запустить программу на выполнение, то Вам нужно выбрать пункт “Интерпретация” в главном меню, а в нем пункт “выполнить”. После этого, перед Вами появится окно, которое сообщит Вам, были ли допущены Вами ошибки при создании программы. Если их не было, то перед Вами появится следующее окно, которое называется окном интерпретации.

После выполнения проверки и обнаружения ошибок выдается сообщение о наличии ошибок:

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

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

Чтобы выйти из системы нужно выбрать команду “выход” в меню файл или нажать клавиши: <Alt><X>.

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

Для запуска системы под операционную систему Windows, Вы должны запустить файл “Блок-схема.exe”. На экране появится главное окно программы.

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

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

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

Редактор текста блока этот пункт предназначен для набора и редактирования текста внутри блока.

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

Опции задание параметров системы и планшета.

Окно работа с окнами приложения.

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

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

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

Текстовый редактор позволяет выполнять следующие действия:

· Вырезать выделенный текст из текста блока и записать его в буфер обмена;

· Вставить текст из буфера;

· Изменить шрифт текста;

· Разрешить или запретить доступ к панели инструментов;

· Найти текст по заданому образцу;

· Заменить заданный образец текста на новый текст.

Для выхода из редактора надо нажать клавишу <Esc>, либо кнопку с надписью “Выход”.

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

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

· Пошаговая отладка;

· Следующий шаг;

· Прервать интерпретацию;

· Установить точку входа в программу;

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

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

Во время работы транслятора выдается следующее окно,

и при обнаружении ошибки выдается окно сообщений, в котором описана возможная ошибка. Например,

А в общем виде это будет выглядеть следующим образом:

Если вы захотите изменить параметры планшета, то Вам нужно вызвать “свойства ” системы. Для этого Вам нужно один раз нажать правую кнопку мыши. После этого перед Вами появится контекстное меню со следующими пунктами:

· Удалить блок;

· Копировать блок;

· Вставить блок;

· Вырезать;

· Свойства.

Нажав на пункт свойства, перед Вами появится следующее диалоговое окно:

Закладка “Планшет” отвечает за свойства планшета. Закладка “Редактор” отвечает за свойства текстового и графического редакторов. Закладка “Интерпретатор” отвечает за параметры интерпретатора.

Для того, чтобы посмотреть значения переменных, надо в меню “Окно” выбрать пункт “ таблица переменных ”. Выглядеть на мониторе компьютера это будет так:

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

Чтобы закончить работу с системой нужно выбрать команду “выход” в меню “файл” или нажать клавиши: <Alt><X>.

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

Перечислим основные структуры данных, используемые в системе “Блок схема”.

Блок-схема алгоритма представляется как список структур следующего вида:

struct BLOCK

{

unsigned int type; // тип блока

int x; // координата блока по оси x

int y; // координата блока по оси y

char *text; // текст блока

int true_x; // переход по ИСТИНЕ по оси x на планшете

int true_y; // переход по ИСТИНЕ по оси y на планшете

int false_x; // переход по ЛЖИ по оси x на планшете

int false_y; // переход по ЛЖИ по оси y на планшете

struct BLOCK *next; // указатель на следующий элемент схемы

bool StopRun; // признак точки входа в программу

bool ErrorFlag; // признак наличия ошибок в данном блоке

bool RunBlock; // признак выполнения блока в текущий момент

struct SVERTKA* Poliz; // полиз текста блока

};

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

struct BLOCK

{

unsigned int type; // тип блока

int x; // координата блока по оси x

int y; // координата блока по оси y

char *text; // текст блока

int true_x; // переход по ИСТИНЕ по оси x на планшете

int true_y; // переход по ИСТИНЕ по оси y на планшете

int false_x; // переход по ЛЖИ по оси x на планшете

int false_y; // переход по ЛЖИ по оси y на планшете

};

Таблица переменных образованна следующим образом: она состоит из списка структур следующего вида:

struct VARIABLE

{

AnsiString Hint; // подсказка при индексации

char* name; // имя переменной

char type; // тип переменной

unsigned int Size; // размерность массива, если Size == 0,

// то это переменная

unsigned int* SizeN;// массив значений размерностей,

// если это переменная то SizeN == NULL

char* ready; // признак готовности к работе переменной

int* __int; // значение переменной типа int

long int* __long_int;// значение переменной типа long int

char* __char; // значение переменной типа char

float* __float; // значение переменной типа float

double* __double; // значение переменной типа double

struct VARIABLE* next;// указатель на следующий элемент таблицы

// переменной

};

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

struct CONSTANTA

{

unsigned char type; // тип константы

int __long_int; // константа типа long int

int __int; // константа типа int

char __char; // константа типа char

float __float; // константа типа float

double __double; // константа типа double

char* __string; // константа типа string

struct CONSTANTA* next;// указатель на следующий элемент таблицы

};

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

struct SVERTKA

{

unsigned char type; // тип свертки

unsigned char intype; // подтип свертки (номер операции, функции,

// процедуры в списке функций)

struct VARIABLE* variable;// если это не переменная то variable==NULL

// если переменной не существует в таблице

// переменных то variable == NULL

struct CONSTANTA* constanta;//указатель на таблицу констант

// если это не константа то constanta==NULL

// если такой константы не существует в таблице

// констант то constanta == NULL

struct SVERTKA* next; // указатель на следующий элемент свертки

int result; // счетчик числа операндов операций или функции

};

Заключение

Данная работа представляет собой транслятор с языка блок схем.

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

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

· Под операционную систему MS-Dos,

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

Размер исполняемого файла в среде MS-Dos 300 Кбайт, в среде Windows 900 Кбайт.

Результаты данной работы были представлены на 6^ой международной научно-практической конференции “Новые информационные технологии в университетском образовании”, которая проходила в городе Новосибирске с 17 по 19 марта 1999 года. На конференции был сделан доклад (тезисы опубликованы).

Система создавалась с целью обучения студентов первого курса ФПМиК основам программирования. Предполагается её активное использование.

Литература

1. Лебедев В.Н. Введение в системы программирования. - М: Статистика, 1975.-315с.

2. Грис Д. Конструирование компиляторов для цифровых вычислительных машин, - М: Мир, 1975.-544с.

3. Касьянов В.Н. , Поттосин И.В. Методы построения трансляторов.- Новосибирск: Наука, 1986. -343с.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции в 2-х томах. - М: Мир, 1978.

5. Соловьёв А.С. Интерпретатор языка блок-схем. // Материалы научно-практической конференции “Новые информационные технологии в университетском образовании”. - Новосибирск: Издательство ИДМИ, 1999.-227с.

6. Демин А.Ю., Гусев А.В. Визуальное программирование программ на основе блок-схем. // Материалы научно-практической конференции “Новые информационные технологии в университетском образовании” Новосибирск: Издательство ИДМИ, 1999.-227с.

7. Паронджанов В.Д. Язык программирования “ДРАКОН” // Программирование. – 1995. - №3.

8. Паронджанов В.Д. Учись рисовать ясные блок-схемы. - М: “Радио и связь”, 1995.

9. Рейсдорф Кент, Хендерсон Кен Освой самостоятельно Borland C++Builder. - Москва: ЗАО “Издательство БИНОМ”, 1998.-704с.

10. Lee C.Y. An algorithm for path connetion and its applications. // “IRE Trans.”, V.EC-10 - № 3.

Приложение

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

MS-Dos версия:

Windows версия:

Пример 1. Нахождение максимума из двух чисел.

Пример 2. Сортировка методом пузырька (Windows версия).

Пример3. Вычислительная программа (MS-Dos версия)

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

Матрица лексического анализатора (сканера)

Матрица синтаксических переходов блока “НАЧАЛО”

Матрица синтаксических переходов блока “ВВОД”

Матрица синтаксических переходов индексации массивов 1

Матрица синтаксических переходов индексации массивов 2

Матрица синтаксических переходов функции strlen

Матрица синтаксических переходов блока “ВЫВОД”

Матрица синтаксических переходов блока “Автоматические действия”

Матрица синтаксических переходов математического выражения

Матрица синтаксических переходов блока “Подпрограмма”

Матрица синтаксических переходов блоков “Метка” и “Безусловный переход”

Матрица синтаксических переходов блока “Ветвление по условию”

Вспомогательная матрица синтаксических переходов блока

“ Ветвление по условию ”

Матрица синтаксических переходов блока “Стрелка”

Матрица синтаксических переходов блока “Мультиветвление”

Матрица синтаксических переходов блока “Конец”