Синтаксический анализ языка НОРМА. Разбор описания

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: рефераты бесплатно, сочинение рассуждение
| Добавил(а) на сайт: Борисюк.

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