МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Кафедра 22
Пояснительная записка к
КУРСОВОЙ РАБОТЕ
на тему:
"Синтаксический анализ языка НОРМА. Разбор описаний "
студента группы К9-02а
Жучкова Александра Викторовича
Научный руководитель:
Комиссия:
Оценка:
Москва 1996г.
1. ВВЕДЕНИЕ
Задание, полученное мной на УИР и КП в данном семестре являлось
продолжением групповой работы, начавшейся в предыдуших семестрах, и
состояло в следующем:
. изучить раздел описаний языковых конструкций Нормы;
. разработать структуры данных и алгоритмы для разбора описаний языка программирования Норма, с учетом специфики языка, а так же удобства написания функций, необходимых для последующей работы транслятора;
. написать функции разбора раздела описаний;
. написать некоторые рабочие функции оперирующие с областями
2. Общее описание языка Норма
Язык программирования Норма является декларативным (непроцедурным) языком и предназначен для спецификации численных методов решения задач математической физики. Изначально он был ориентирован на решение задач математической физики разностными методами, однако может быть использован для решения более широкого класса вычислительных задач.
Главная идея, положенная в основу языка Норма, заключается в том, что полученные специалистом в процессе решения прикладной задачи расчетные формулы почти непосредственно используются для ввода в вычислительную систему и проведения счета. Таким образом, язык Норма дает прикладному математику возможность сформулировать свою задачу в привычных для него терминах. Запись на языке Норма - это, по существу, строгая запись численных методов решения математической задачи, запись еще не алгоритмов, а просто расчетных формул и остальной необходимой информации.
Отметим, что в записи на Норме не требуется никакой информации о
порядке счета, способах организации вычислительных (циклических) процессов.
Порядок предложений языка может быть произвольным - информационные
взаимосвязи будут выявлены и учтены при организации процесса счета
транслятором. Эта возможность, конечно, увеличивает трудоемкость и
сложность при компиляции текста программы, но разработчики языка
сознательно пошли на это, чтобы сделать данный язык удобным для
использования широким кругом специалистов-математиков, имеющих небольшой
опыт работы на компьютере.
Выбор уровня языка Норма определяет характерную его черту - в этом
языке нет необходимости вводить такие понятия, как оператор присваивания и
возможность переприсваивания значений (типа х:=х+1) и операторы перехода.
Наличие таких понятий в традиционных языках программирования объясняется
необходимостью формулировки конкретного алгоритма с учетом вопросов
экономии и распределения памяти, порядка выполнения операторов и т. п.
Побочный эффект в языке Норма отсутствует по определению. Понятно, что
многие из этих вопросов появляются снова на этапе синтеза рабочей
программы. Однако, здесь они решаются автоматически по строгим правилам,
гарантирующим правильность синтезируемой программы.
Непроцедурность языка Норма позволяет преодолеть еще одну трудность, связанную с распараллеливанием алгоритма при счете на ЭВМ, допускающих совмещение операций. Известные методы распараллеливания последовательных алгоритмов основаны на выявлении, при некоторых ограничениях, частей алгоритма, которые можно выполнять независимо, в соответствии с заданным критерием параллелизма - асинхронные вычисления, синхронные и т. п. Однако, выявление взаимосвязей в уже сформированном последовательном алгоритме является неестественной и трудной задачей, так как анализируемая формулировка, как правило, насыщена избыточными взаимосвязями (типа введения рабочих переменных , конкретных способах организации циклов и т. п.). Вообще говоря, ни откуда не следует, что последовательный алгоритм надо транслировать в параллельный, а не определять параллельный сразу по непроцедурной записи.
Эти свойства, и некоторые другие ограничения, позволяют строго
обосновать разрешимость синтеза выходной программы, так как в достаточно
общей постановке решение этой задачи приводит к значительным математическим
трудностям - она может оказаться NP-полной, либо вообще неразрешимой. С
другой стороны, исследования, связанные с разработкой и применением языка
Норма показывают, что имеющиеся ограничения приемлимы с практической точки
зрения.
3 Структура транслятора с языка Норма.
Транслятор с языка Норма сразу проектировался как многопроходный. На
первом проходе на вход лексического анализатора поступает текст исходной
программы (см. приложение 1), который преобразуется в последовательности
лексем, объединенные в кванты*. Параллельно происходит начальное заполнение
таблиц имен и констант, после этого эти таблицы из хеш-структур
преобразуются в массивы. Это делается для максимального освобождения
оперативной памяти перед следующими проходами, а так же для ускорения
доступа, так как далее идет очень интенсивное обращение к этим таблицам. На
втором проходе происходит сортировка этих квантов по определенным правилам.
Отсортированный список квантов поступает на следующем проходе на вход
синтаксического анализатора, который разбирает описания языковых
конструкций, операторы ввода, операторы вывода, операторы присваивания и
т.д. В результате работы синаксического анализатора заполняются множество
рабочих таблиц: областей, условий и т.п. На следующем проходе по данным
таблицам происходит определение информационных зависимостей между
операторами, определяется порядок вычисления. Далее для не сильно связанных
компонентов методом нахождения гиперплоскостей происходит распараллеливание
отдельных фрагметов программы. После чего генерируется выходная фортран-
программа.
Для обеспечения доступа к верхней памяти, а также для возможного свопинга практически все операции с оперативной памятью осуществляются с использованием библиотеки функций менеджера памяти, написанной сотрудниками института прикладной математики.
4 Описание и решение задачи.
4.1 Постановка задачи.
В программе, написанной на языке Норма могут встречаться следующие специфические объекты:
. параметры областей, задающие в неявном виде границы диапазонов при описании областей;
. индексы областей, которые задают как бы имена различным кординатным направлениям в областях.
. индексы распределения, служащие для отображения двух индексных направлений индексного пространства области задачи на матрицу процессорных элементов (ПЭ) распределенной системы;
. индексные конструкции, служащие для сокращения записи сложных индексных выражений;
. внешние функции и разделы;
. области;
. скалярные величины и величины на области
(синтаксис смотри приложение 2).
Как видно из вышеперечисленного, наиболее важным и информативным
объектом является описание области. Дейсвительно, и индексы и параметры
области являются лишь вспомогательными понятиями, делающими описания
областей более удобочитаемыми или более гибкими. Для величин, определенных
на области, их области являются тем множеством, на котором они существуют.
Понятие области введено в языке Норма для представления понятия индексного
пространства. Область - это совокупность целочисленных наборов {i1,...,in},
n>0, ij>0, j=1,...,n, каждый из которых задает координаты точки n-мерного
индексного пространства. С каждым направлением (осью координат) n-мерного
пространства задачи связывается уникальное имя - имя-индекса (имя оси
координат индексного пространства). Следует отметить, что область
определяет значения координат точек индексного пространства, а не значения
расчетных величин в этих точках. Так же следует отметить то, что все
множества должны быть конечны, т.к. конечно пространство памяти ЭВМ, на
которое будут в последствии отображатся величины на области.
Разработчики языка Норма на основании опыта, накопленного ими при решении задач вычислительной математики, решили, что для решения большинства задач подобного класса достаточно ввести следующие разновидности областей:
. прямоугольные;
. диагональные;
. условные.
В свете вышесказанного перед нами (группой разработчиков) встала задача напсания транслятора с языка Норма с использованием инструментальных средств языка программирования Си и библиотеки функций работы с оперативной памятью. Передо мной были поставлены задачи:
. разработка структур для хранения данных, полученных в результате разбора описаний областей;
. разработка алгоритмов и написание функций разбора описаний;
. разработка алгоритмов для написания функций пересечения областей
4.2 Решение задачи. Выбор структуры данных
Проанализировав различия и сходство той информации, которую необходимо хранить для каждой разновидности области, мною, при согласовании с разработчиками языка и моими коллегами, были выбраны следующие структуры.(смотри приложение 4 ).
Во первых, главная таблица областей (далее просто таблица областей), в
которой для всех областей хранится количество направлений (мерность
множества), по каждому направлению имя индекса и значения левой и правой
границ, тип области, ключ для поиска детальной информации в других
таблицах. Решено было ввести четыре типа области: прямоугольная - она
характерна тем, что проекцией на любую двумерную систему координат будет
прямоугольник; диагональная - это область, границы которой по некоторым
направлениям могут быть прямые под углом 45( к оси; положительно-условные -
это часть родительской области, на которой логическое выражение, задающее
эту область будет выдавать значение правда; отрицательно-условные - это то
же, что и положительно-условные, только логическое выражение будет выдавать
значение ложь. Получилось так, что таблица областей вышла неоднородной, так
как могут существовать области с различным количеством направлений. Хранить
эту таблицу в массиве с размером полей, расчитанным на максимально
возможное количество направлений, я посчитал нерациональным. Была
рассмотрена возможность реализации хранения на списках, но эта возможность
мною тоже была отвергнута, потому что получился бы список с большим
количеством мелких элементов, что затруднило бы работу менеджера памяти
(которому на каждый такой элемент пришлось бы заводить рабочие структуры,
что тоже использовало бы память), а так же увеличило бы время работы.
Поэтому было решено хранить эти таблицы в одном большом буфере и иметь
специальные функции, позволяющие производить запись и чтение из этого
буфера. Этот способ экономен в использовании памяти (мало пустующего
пространства), удобен менеджеру памяти (работает с одним блоком),
достаточно быстрый доступ. Тем более что похожий механизм был ранее
реализован моим коллегой при работе с таблицей имен на этапе лексического
анализа, и он согласился реализовать эти функции.
Во-вторых, таблица диагональных областей, где хранится детальная
информация, позволяющая полностью охарактеризовать диагональную область, а
именно: количество диагональных плоскостей, по каждой диагональной
плоскости имена индексов и константы пересечения диагоналей с осью,
определенной первым индексом. Например, если индексы родительской области
находятся в пределах 1( i (10 1( j (5, а условие имеет вид i < j то
построение записи в таблицу будет таким : j j c2
5
1 c1
1 10 i i
Так как получается схожая с таблицей областей картина, а именно, записи в таблице диагональных областей могут иметь различную длину, решено было использовать тот же механизм хранения информации.
В-третьих, таблица условных областей, в которой хранится номер положительно-условной области, отрицательно-условной области, родительской области, ключ для поиска условия в таблице условий. Так как поля данной таблицы однородны, то она легко хранится в структуре массива. В основном данная таблица была заведена с целью сохранения связи положительно- и отрицательно-условных областях, имеющих общую родительскую область. Это впоследствии облегчает проведение таких операций, как пересечение над условными областями.
В-четвертых, на основе механизма, использовавшегося для хранения таблицы областей, была создана таблица условий, в которой хранятся логические выражения, заданные при описании условных областей.
4.3 Разработка алгоритмов и реализация функций разбора описаний областей
В языке различается описание области - это именованная условная, прямоугольная или диагональная область, и использование области - синтаксически это имя-области или описание области без имени. Области используются в описаниях величин, определенных на области, при задании области вычисления в операторах ASSUME, в описания входных или выходных величин, при задании областей фактических параметров в вызовах разделов или функций, в функциях редукции.
Чтобы учесть эти два случая при описании области без имени я решил
заводить новые имена в таблице имен и отождествлять их с этими областями.
Для этого строится расширение уже существующей таблицы имен. При разборе
мною был использовался метод прямого анализа. Разбор осуществляется
последовательным сканирование цепочки лексем слева направо. По ходу
сканирования происходит проверки как синтаксических конструкций, так и ряда
семантических правил, при этом происходит постепенное накопление в рабочих
структурах информации об объекте, которая в случае успешного окончания
разбора заносится в таблицы общего назначения. Разбор описания области
осуществляет функция razb_obl (см. приложение 3). Функция, путем нахождения
“уникальных” лексем или их сочетаний, вызывает для разбора каждой
разновидности области свою функцию (например, razb_multobl разбирает
описание многомерной области). Затем каждая отдельная функция разбирает
описание своей области и при успешном окончании заполняет нужные таблицы
(областей, диагональных областей и т.д.), а так же таблицу имен. В случае
неудачного разбора выдается сообщение об ошибке.
4.4 Разработка алгоритмов для фукций работы с областями
Помимо задания вычисляемого пространства для величины на области,
понятие и описание области используются в Норме во многих местах. Например,
в операторах FOR ASSUME или в операторах ввода и вывода. Очень часто
необходимо произвести над областями проверку, является ли их пересечение
пустым множеством или нет. Например, при определении информационных
зависимостей между опреаторами и определением порядка вычислеий. В данном
примере необходимо установить дает ли пересечение требуемой области Sтреб
и
FOR B ASSUME X=F(Z,Y[i+1,j]...)
Sтреб
FOR C ASSUME Y=F(P,K[i-1,j]...)
области С пустое множество. Если дает, то данные операторы не связаны между
собой, иначе второй оператор необходимо вычислить раньше первого.
Пересечение областей я планирую проводить следующим образом. Для случая
прямоугольных областей необходимо по каждому направлению сравнить верхние и
нижние границы индексов. Для диагональных областей помимо сравнения
диапазонов индексов необходимо аналогичным образом сравнивать диагональные
диапазоны. Если мы имеем дело с условными областями то необходимо
рассматривать два случая. Первый - это когда две эти области имеют общего
(пускай не ближайшего) родителя. Тогда необходимо найти первого такого
родителя и от него провести проверку, какие еще предки, положительно или
отрицательно-условные, находятся на пути от этого родителя к данным
областям, и если есть различия, то пересечение пусто, иначе нет. Это можно
проиллюстировать с помощью представления условных областей в виде бинарного
дерева, где в одну сторону идут положительно-условные области,
|а в другую отрицательно-условные. На рисунке |
|пересечение двух темно закрашенных областей не |
|пусто , а пересечение темно и светло закрашенных|
|- пусто. Другой случай возникает, если области |
|не имеют ни одного общего предка (хотя такой |
|случай очень странен в смысле логики программы).|
|Тогда мы можем проверить на пересечение самых |
|первых предков этих областей (они являются |
|прямоугольными). Если они не пересекаются, то и |
|условные не пересекаются, иначе мы считаем, что |
|они могут пересечься. |
Помимо пересечения областей часто требуется найти объединение. Эту задачу аналитическими методами решить очень сложно, поэтому планируется реализовать ее методом перебора
5. ЗАКЛЮЧЕНИЕ
В результате проделанной работы мною были достигнуты следующие цели:
. разработаны сновные структуры для хранения данных, полученных в результате разбора описаний областей;
. разработаны алгоритмы и написаны функции разбора описаний областей;
. разработаны алгоритмы для написания функций пересечения областей
Некоторые функции находится на стадии доработки и отладки. Завершение работы над ними планируется в следующем семестре. Задание на УИР и КП выполнил практически полностью.
Список литературы:
А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло, Н.В. Поддерюгина "Язык
Норма"
А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло "Непроцедурный язык Норма и методы его реализации"
А.Б. Бугеря "Реализация математических функций языка Норма для распределенных высислительных систем"
Ф.Льюис “Теоретические основы проектирования компиляторов”
* Квант - семантически законченный фрагмент текста программы(например,
описание области)