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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра 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°к оси; положительно-условные — это часть родительской области, на которойлогическое выражение, задающее эту область будет выдавать значение правда;отрицательно-условные — это то же, что и положительно-условные, толькологическое выражение будет выдавать значение ложь. Получилось так, что таблицаобластей вышла неоднородной, так как могут существовать области с различнымколичеством направлений. Хранить эту таблицу в массиве с размером полей,расчитанным на максимально возможное количество направлений, я посчиталнерациональным. Была рассмотрена возможность реализации хранения на списках, ноэта возможность мною тоже была отвергнута, потому что получился бы список сбольшим количеством мелких элементов, что затруднило бы работу менеджера памяти(которому на каждый такой элемент пришлось бы заводить рабочие структуры, чтотоже использовало бы память), а так же увеличило бы время работы. Поэтому былорешено хранить эти таблицы в одном большом буфере и иметь специальные функции,позволяющие производить запись и чтение из этого буфера. Этот способ экономен виспользовании памяти (мало пустующего пространства), удобен менеджеру памяти(работает с одним блоком), достаточно быстрый доступ. Тем более что похожиймеханизм был ранее реализован моим коллегой при работе с таблицей имен на этапелексического анализа, и он согласился реализовать эти функции.

<img src="/cache/referats/2174/image001.gif" v:shapes="_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029"><img src="/cache/referats/2174/image002.gif" v:shapes="_x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035"><img src="/cache/referats/2174/image003.gif" v:shapes="_x0000_s1036">Во-вторых, таблица диагональных областей, гдехранится детальная информация, позволяющая полностью охарактеризоватьдиагональную область, а именно: количество диагональных плоскостей, по каждойдиагональной плоскости имена индексов и константы пересечения диагоналей сосью, определенной первым индексом. Например, если индексы родительской областинаходятся в пределах 1£i £10 1£j £5, а условие имеет вид i< j то построение записи в таблицу будет таким :

j j

<img src="/cache/referats/2174/image004.gif" v:shapes="_x0000_s1038">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]...)

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

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

<img src="/cache/referats/2174/image006.gif" v:shapes="_x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045 _x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052">а в другую отрицательно-условные. На рисунке пересечение двух темно закрашенных областей не пусто, а пересечение темно и светло закрашенных — пусто. Другой случай возникает, если области не имеют ни одного общего предка (хотя такой случай очень странен в смысле логики программы). Тогда мы можем проверить на пересечение самых первых предков этих областей (они являются прямоугольными). Если они не пересекаются, то и условные не пересекаются, иначе мы считаем, что они могут пересечься.

Помимо пересечения областейчасто требуется найти объединение. Эту задачу аналитическими методами решитьочень сложно, поэтому планируется реализовать ее методом перебора

5. ЗАКЛЮЧЕНИЕ

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

·

разработаны сновные структуры для хранения данных, полученных врезультате разбора описаний областей;

·

разработаны алгоритмы и написаны функции разбора описаний областей;

·

разработаны алгоритмы для написания функций пересечения областей

Некоторые функции находитсяна стадии доработки и отладки. Завершение работы над ними планируется вследующем семестре. Задание на УИР и КП выполнил практически полностью.

Список литературы:

А.Н. Андрианов, К.Н.Ефимкин, И.Б. Задыхайло, Н.В. Поддерюгина «Язык Норма»

А.Н. Андрианов, К.Н.Ефимкин, И.Б. Задыхайло «Непроцедурный язык Норма и методы егореализации»

А.Б. Бугеря «Реализацияматематических функций языка Норма для распределенных высислительныхсистем»

Ф.Льюис “Теоретическиеосновы проектирования компиляторов”

* Квант — семантически законченный фрагмент текста программы(например, описание области)

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Основы алгоритмизации и алгоритмические языки

29 Августа 2013

Реферат по программированию, базе данных