А
Б В
Г Д
Е Ж
З И
К Л
М Н
О П
Р С
Т У
Ф Х
Ц Ч
Ш Э
Ю Я
Реферат: Русификатор.
Русификатор.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Кафедра 22
Пояснительная записка к
КУРСОВОЙ РАБОТЕ
на тему:
"Синтаксический анализ языка НОРМА. Разбор описаний "
студента группы К8-02а
Жучкова Александра Викторовича
Научный руководитель:
Комиссия:
Оценка:
Москва 1995г.
1. ВВЕДЕНИЕ
Задание, полученное мной на УИР и КП в данном семестре являлось продолжением работы, начатой в прошлом семестре, и состояло в следующем:
тщательно изучить раздел описаний языком программирования Норма;
разработать структуру данных и алгоритмы для разбора описаний языка программирования Норма;
написать функции разбора раздела описаний.
2. Общее описание языка Норма
Язык программирования Норма является декларативным (непроцедурным) языком и предназначен для спецификации численных методов решения задач математической физики. Изначально он был ориентирован на решение задач математической физики разностными методами, однако может быть использован для решения более широкого класса вычислительных задач.
Главная идея, положенная в основу языка Норма, заключается в том, что полученные специалистом в процессе решения прикладной задачи расчетные формулы почти непосредственно используются для ввода в вычислительную систему и проведения счета.Таким образом, язык Норма дает прикладному математику возможность сформулировать свою задачу в привычных для него терминах. Запись на языке Норма - это, по существу, строгая запись численных методов решения математической задачи, запись еще не алгоритмов, а просто расчетных формул и остальной необходимой информации.
Отметим, что в записи на Норме не требуется никакой информации о порядке счета, способах организации вычислительных (циклических) процессов. Порядок предложений языка может быть произвольным - информационные взаимосвязи будут выявлены и учтены при организации процесса счета транслятором. Эта возможность, конечно, увеличивает трудоемкость и сложность при компиляции текста программы, но разработчики языка сознательно пошли на это, чтобы сделать данный язык удобным для использования широким кругом специалистов-матемотиков, имеущих небольшой опыт работы на компьютере.
Выбор уровня языка Норма определяет характерную его черту - в этом языке нет необходимости вводить такие понятия, как оператор присваивания и возможность переприсваивания значений (типа х:=х+1) и операторы перехода. Наличие таких понятий в традиционных языках программирования объясняется необходимостью формулировки конкретного алгоритма с учетом вопросов экономии и распределения памяти, порядка выполнения операторов и т. п. Побочный эффект в языке Норма отсутствует по определению. Понятно, что многие из этих вопросов появляются снова на этапе синтеза рабочей программы. Однако, здесь они решаются автоматически по строгим правилам, гарантирующим правильность синтезируемой программы.
Непроцедурность языка Норма позволяет преодолеть еще одну трудность, связанную с распараллеливанием алгоритма при счете на ЭВМ, допускающих совмещение операций. Известные методы распараллеливания последовательных алгоритмов основаны на выявлении, при некоторых ограничениях, частей алгоритма, которые можно выполнять независимо, в соответствии с заданным критерием параллелизма - асинхронные вычисления, синхронные и т. п. Однако, выявление взаимосвязей в уже сформированном последовательном алгоритме является неестественной и трудной задачей, так как анализируемая формулировка, как правило, насыщена избыточными взаимосвязями (типа введения рабочих переменных для экономии памяти, конкретных способах организации циклов и т. п.). Вообще говоря, ни откуда не следует, что последовательный алгоритм надо транслировать в параллельный, а не определять параллельный сразу по непроцедурной записи.
Эти свойства, и некоторые другие ограничения, позволяют строго обосновать разрешимость синтеза выходной программы, так как в достаточно общей постановке решение этой задачи приводит к значительным математическим трудностям - она может оказаться NP-полной либо вообще неразрешимой. С другой стороны, исследования, связанные с разработкой и применением языка Норма показывают, что имеющиеся ограничения приемлимы с практической точки зрения.
3 Структура транслятора с языка Норма.
Транслятор с языка программирования Норма уже написан на языке Рефал. И хотя язык программиорвания Рефал весма удобен для обработки символьной информации, транслятор написанный на этом языке очень не экономно использует ресурсы вычислительной машины, а именно оперативную память, что зачастую правильно написанную программы невозможно оттранслировать из за нехватки оперативной памяти. Поэтому было решено перевести транслятор с языка Норма, используя на язык программирования Си, который был выбран по следующим причинам:
язык Си позволяет гораздо более эффективно использовать ресурсы вычислительной машины;
язык Си универсален и удобен для решения задач системного программирования разработке трансляторов, операционных систем, экранных интерфейсов, инструментальных средств;
разработчиками языка Норма уже написан интерфейс на языке Си, позволяющий законченные части транслятора, написанные на Рефале, заменять на законченные части транслятора, написанные на Си, для отладки транслятора;
менеджер работы с памятью, который используется нами для доступа к верхней памяти и свопинга, написан ориентированно на транслятор Си.
В процессе трансляции, решаются как традиционные задачи - лексический синтаксический, семантический анализ, генерация выходной программы, так и задачи, определяемые спецификой языка Норма: организация вычислений по непроцедурному описанию задачи с выявлением возможного параллелизма вычислений, семантический контроль возможности организации вычислений с учетом возможностей выходного языка и архитектуры компьютера. Выходными языкоми могут быть языки Фортран ВП ориентированный на многопроцессорный вариант ЭВМ ЕС-1191 и Фортран JNS. Трансляция каждого раздела, входящего в Норма программу, проводится автономно: для каждого раздела либо выдается программа на выходном языке, либо, если были обнаружены синтаксические или семантические ошибки, выдается сообщение об ошибке, после чего осуществляется переход к трансляции очередного раздела.
Структура транслятор с языка программирования Норма.
На вход лексического анализатора поступает текст исходной программы (см. приложение 1). На выходе - отсортированный (по описаниям, операторам и итерациям) список лексем, начально заполненные таблици имен и констант. Далее этот список поступает на вход синтаксического анализатора, где происходит разбор конструкций-описаний, операторов, итераций и заполняются таблицы имен, констант, множеств, описания операторов и др. Перед началом этапа синтаксического анализа, для максимальной очистки памяти происходит конвертация начальных таблиц имен и констант. Эти таблицы поступают на вход следующего этапа, где происходит построение графа информационных зависимостей, который используется на следуещем этапе при определение порядка вычислений и разделение на параллельные ветви, независящие друг от друга. На выходе получаем внутренние коды. Внутренние коды поступают на вход кодогенерации. Выходом кодогенерации является программа на языке Фортран.
Для обеспечения доступа к верхней памяти,а также для возможного свопинга практически все операции с оперативной памятью осуществляются с использованием библиотеки функций менеджера памяти, написанной сотрудниками института прикладной математики.
4 Описание и решение задачи.
4.1 Постановка задачи.
В свете вышесказанного перед нами (группой разработчиков) встала задача напсания транслятора с языка Норма с использованием инструментальных средств языка программирования Си и библиотеки функций работы с операивной памятью. Передо мной была поставлена задача разработки алгоритмов и написания функций разбора описаний.
4.2 Решение задачи. Выбор структуры данных
Одной из конструкций языка Норма являются описания, определяющие объекты программы, например, области, индексы, величины, которые необходимы при решении задачи. В Норме могут быть описаны следующие объекты: области, скалярные величины (скаляры), величины, определенные на сетке, индексные конструкции, индексы распределения, параметры области, входные и выходные величины, имена внешних функций и разделов (синтаксис см. приложение 2). На втором проходе лексического анализатора списки лексем делятся на описания, операторы, итерации, а конкретно описания дробятся еще на более мелкие структурные объекты описания области, описания величин и т.д., после чего вызываются конкретные функции синтаксического анализа описаний, причем в строго определенном порядке (разбор параметров областей, разбор индексов областей, разбор описания индексов распределения, разбор индесных конструкций, разбор описания внешних функций и внешних разделов пользователя, разбор описания областей, разбор описания величин). Это обусловлено тем, что порядок описаний в программе может быть произвольным. Для разбора мною был выбран метод прямого анализа. Разбор осуществляется последовательным сканирование цепочки лексем слева направо. По ходу сканирования происходит проваерки как синтаксических конструкций, так и ряда семантических правил, при этом происходит постепенное накопление в рабочих структурах информации об объекте, которая вслучае успешного окончания разбора заносится в таблицы общего назначения.
4.2.1 Разбор параметров областей.
Границы диапазонов при описании областей могут задаваться неявно - при помощи параметров области. Значения этих параметров должны быть определены в разделе в описании параметров области. Параметры области могут входить в арифметические выражения и константные выражения. Иных способов параметризрвать границы области нет.
Разбор параметров области осуществляет фукция razb_par_obl (см приложение 3). При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть параметр области и позиция в таблице параметров области, где будет храниться значение параметра, в случае неудачного разбора выдается сообщение об ошибке.
4.2.2.Разбор описаний индексов областей.
При описании области порядок направлений индексного пространства не фиксируется (или, что с точки зрения автора программы то же самое, фиксируется некоторым произвольным образом). Если порядок направлений индексного пространства существенен (например, необходимо согласование направлений при использовании величин на одних и тех же областях в различных разделах), то он задается при помощи описания индексов областей. Порядок направлений индексного пространства совпадает с порядком перечисления имен индексов в описании индексов (слева направо). Иначе индексы упорядочиваются в порядке появления их в различных описаниях.
Разбор описаний индексов областей осуществляет фукция razb_index (см приложение 3). При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть индекс области и в таблице индексов происходит упорядочевание в соответстии с описанием, в случае неудачного разбора выдается сообщение об ошибке.
4.2.3.Описание индексов распределения
Описание индексов распределения служит для отображения двух индексных направлений индексного пространства области задачи на матрицу процессорных элементов (ПЭ) распределенной системы. Разделы или функции, в которых присутствует это описание, называются распределенными, если оно отсутствует-нераспределенными. В распределенном разделе или функции это описание должно встречаться не более одного раза; в главном разделе оно запрещено, то есть главный раздел по определению является нераспределенным.
Данное описание приводит к распределению между ПЭ системы как данных, так и управления, и автоматической генерации операторов обмена данными между ПЭ, если это необходимо. Распределению подлежат величины, участвующие в расчетах и имеющие индексы, совпадающие с указанными в описании индексов распределения.Вычисления, описанные в нераспределенном разделе или нераспределенной функции, выполняются целиком в одном ПЭ (хотя таких ПЭ может быть и несколько). Считается, что элементы матрицы ПЭ нумеруются, начиная с 1.
Разбор индексов распределения осуществляет функция razb_ind_rasp (см. приложение 3). При успешном разборе заполняется единственная для каждого раздела таблицу индексов распределения (туда заносятся имена индексов и диапазон), в случае неудачного разбора выдается сообщение об ошибке.
4.2.4.Описание индексной конструкции
Индексная конструкция служит для сокращения записи сложных индексных выражений и является простейшим случаем макроопределения.
Разбор индексной констркции осуществляет функция razb_mac_ind (см. приложение 3). При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть индексная конструкция и в позиция в таблице индексных конструкций, в которой хранится сама конструкция в виде строки текста, в случае неудачного разбора выдается сообщение об ошибке.
4.2.5.Описание внешних имен функций и раделов.
В описании внешних имен обязательно указываются имена функций или разделов, которые являются фактическими или формальными параметрами раздела или функции. По умолчанию внешняя функция имеет тип REAL.
Разбор описание внешних имен осуществляют функции razb_ext_fun razb_ext_part соответсвенно (см. приложение 3). При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть внешняя функция или раздел и для фукции ее тип, в случае неудачного разбора выдается сообщение об ошибке.
4.2.6.Разбор описания области.
Понятие области введено в языке Норма для представления понятия индексного пространства. Область - это совокупность целочисленных наборов {i1,...,in}, n>0, ij>0, j=1,...,n, каждый из которых задает координаты точки n-мерного индексного пространства. С каждым направлением (осью координат) n-мерного пространства задачи связывается уникальное имя - имя-индекса (имя оси координат индексного пространства). Следует отметить, что область определяет значения координат точек индексного пространства, а не значения расчетных величин в этих точках.
В языке Норма область может иметь имя, над областями определены операции модификации и произведения. Индексы областей специально не описываются - они вводятся при определении областей. Область может быть условной и безусловной. Условная область состоит из точек индексного пространства, число и координаты которых могут меняться в зависимости от выполнения (или не выполнения) условий на область. Безусловная область состоит из точек индексного пространства, число и координаты которых могут быть определены на этапе трансляции. В языке различается описание области - это именованная условная или безусловная область, и использование области - синтаксически это имя-области или новая область без имени. Области используются в описаниях величин, определенных на области, при задании области вычисления в операторах ASSUME, в описания входных или выходных величин, при задании областей фактических параметров в вызовах разделов или функций, в функциях редукции.
Разбор описания области осуществляют функции razb_obl (см. приложение 3). Функция, путем нахождения “уникальных” лексем или их сочетаний, вызывает для разбора каждой разновидности области свою функцию (например razb_multobl разбирает описание многомерной области). При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть имя области и позицию в таблице областей, где хранится информация об области, в случае неудачного разбора выдается сообщение об ошибке. Таблица областей (и другие, необходимые для хранения информации об областях, таблицы) имеют структуру показанную в приложении 4.
4.2.7.Описание величин
Скалярные величины ( скаляры ) и величины на области относятся к арифметическим величинам. Описание ставит в соответствие каждой арифметической величине уникальное в текущем разделе имя-величины, а также
задает тип величины: REAL, INTEGER или DOUBLE (по умолчанию - тип REAL)
Разбор описания области осуществляют функции razb_var (см. приложение 3). Функция, путем нахождения “уникальных” лексем , вызывает для разбора величин на области функцию razb_var_obl, а для скаляров функцию razb_var_scal пример razb_multobl разбирает описание многомерной области. При успешном разборе в таблицу имен заносится информация о идентификаторе, что он есть имя величины или величины на области, а так же тип величины и номер области для величин определенных на области, в случае неудачного разбора выдается сообщение об ошибке.
5. ЗАКЛЮЧЕНИЕ
В результате проделанной работы мною были достигнуты следующие цели:
тщательное изученил раздел описаний языка программирования Норма;
разработал структуры данных и алгоритмы для разбора описаний языка программирования Норма;
написал функции разбора раздела описаний.
Программа находится на стадии доработки и отладки. Завершение работы планируется в следующем семестре. Задание на УИР и КП выполнила полностью.
Список литературы:
А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло, Н.В. Поддерюгина "Язык Норма"
А.Н. Андрианов, К.Н. Ефимкин, И.Б. Задыхайло "Непроцедурный язык Норма и методы его реализации"
А.Б. Бугеря "Реализация математических функций языка Норма для распределенных высислительных систем"
Ф.Льюис “Теоретические основы проектирования компиляторов”
|