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

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

Удаление блоков выполняется следующим образом: c помощью указателя

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

, либо выбирается пункт “УДАЛИТЬ” в подменю “РЕДАКТОР” главного

меню.

В Windows варианте эти возможности можно выбирать посредством

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

Windows вариант предусматривает соединение двух заданных блоков с помощью

волнового алгоритма Ли[10].

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

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

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

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

большинству современных текстовых редакторов, предоставляемых фирмой

Borland. Редактор обладает следующими возможностями:

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

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

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

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

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

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

Редактор, предложенный в среде MS-Dos, является простейшим вариантом

текстового редактора, в котором возможен лишь набор текста в режиме

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

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

блок-схемы.

С помощью клавиш управления осуществляется перемещение курсора по окну

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

удаление текста со сдвигом строки.

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. Сканер

Сканер – это часть компилятора, которая читает входную программу и

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

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

грамматиками, так как его можно легко запрограммировать. Следовательно,

сканер выделяют отдельным блоком.

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

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

анализа по диаграмме состояний. Заметим, что процедура анализа представляет

собой восходящий анализ, основой на каждом шаге является текущий символ и

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

подграфы которого это есть диаграммы состояний отдельных лексем.

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

лексему.

Пусть входная строка: s1, s2, s3,…, sn.

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

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

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

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

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

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

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

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

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

использует подпрограмму:

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

где

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

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

3, если si `

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

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

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

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

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

ЗАМЕЧАНИЕ:

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

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

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

указатель стоит на начале следующей лексемы.

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

Так как сканер строится по диаграмме состояний, то для простоты

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

сканера приведена в приложении.

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

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

исходной программы на составные части, формированию ее внутреннего

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

При этом также выполняется полный синтаксический и частичный семантический

контроль программы.

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

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

настолько, насколько это возможно. Когда синтаксический анализатор

(распознаватель) узнает конструкцию исходного языка, он вызывает

соответствующую семантическую процедуру, или семантическую программу,

которая контролирует данную конструкцию с точки зрения семантики и затем

запоминает информацию о ней в таблице символов или во внутреннем

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

семантическая программа проверяет идентификаторы, указанные в этом

описании, чтобы убедиться в том, что они не были описаны дважды, и заносит

их вместе с атрибутами в таблицу символов.

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

=

семантическая программа проверяет переменную и выражение на соответствие

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

представление.

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

как и сканер. Поэтому их частично объединяют и если возможно то совмещают

полностью. В данной работе процесс лексического, синтаксического и

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

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

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

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

Первые процедурно-ориентированные языки программирования высокого

уровня предназначались для решения инженерных и научно – технических задач,

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

часть программ решения таких задач составляют арифметические и логические

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

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

большое число таких трансляторов. Сейчас классическим стал метод трансляции

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

записи, названной так в честь польского математика Яна Лукашевича, который

впервые использовал эту форму представления выражений в математической

логике.

Цель польской инверсной записи – представить операции исходного

выражения в порядке их выполнения (вычисления). В данной работе был

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

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

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

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

Очевидно, что обрабатывать такую последовательность операций

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

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

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

ПРИОРИТЕТ ОПЕРАЦИИ – это целое число, означающее старшинство операции

по отношению к другим операциям. Приоритет операций изменяется с

использованием скобок ( и ).

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

Страницы: 1, 2, 3, 4, 5, 6