Синтаксический анализ языка НОРМА. Разбор описания
МОСКОВСКИЙГОСУДАРСТВЕННЫЙИНЖЕНЕРНО-ФИЗИЧЕСКИЙИНСТИТУТ
(ТЕХНИЧЕСКИЙУНИВЕРСИТЕТ)
Кафедра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
c2
51 c1
1 10 i i
Так какполучаетсясхожая с таблицейобластей картина,а именно, записив таблицедиагональныхобластей могутиметь различнуюдлину, решенобыло использоватьтот же механизмхранения информации.
В-третьих,таблица условныхобластей, вкоторой хранитсяномер положительно-условнойобласти,отрицательно-условнойобласти, родительскойобласти, ключдля поискаусловия в таблицеусловий. Таккак поля даннойтаблицы однородны,то она легкохранится вструктуремассива. В основномданная таблицабыла заведенас целью сохранениясвязи положительно-и отрицательно-условныхобластях, имеющихобщую родительскуюобласть. Этовпоследствииоблегчаетпроведениетаких операций,как пересечениенад условнымиобластями.
В-четвертых,на основе механизма,использовавшегосядля хранениятаблицы областей,была созданатаблица условий,в которой хранятсялогическиевыражения,заданные приописании условныхобластей.
4.3 Разработкаалгоритмови реализацияфункций разбораописаний областей
В языкеразличаетсяописаниеобласти -это именованнаяусловная,прямоугольнаяили диагональнаяобласть, ииспользованиеобласти- синтаксическиэто имя-областиили описаниеобластибез имени. Областииспользуютсяв описанияхвеличин, определенныхна области, призадании областивычисленияв операторахASSUME,в описаниявходных иливыходных величин,при заданииобластей фактическихпараметровв вызовах разделовили функций,в функцияхредукции.
Чтобыучесть эти дваслучая приописании областибез имения решил заводитьновые именав таблице имени отождествлятьих с этими областями.Для этого строитсярасширениеуже существующейтаблицы имен.При разборемною был использовалсяметод прямогоанализа. Разборосуществляетсяпоследовательнымсканированиецепочки лексемслева направо.По ходу сканированияпроисходитпроверки каксинтаксическихконструкций,так и рядасемантическихправил, приэтом происходитпостепенноенакоплениев рабочих структурахинформацииоб объекте,которая в случаеуспешногоокончанияразбора заноситсяв таблицы общегоназначения.Разбор описанияобласти осуществляетфункция razb_obl (см.приложение3). Функция, путемнахождения“уникальных”лексем или ихсочетаний,вызывает дляразбора каждойразновидностиобласти своюфункцию (например,razb_multobl разбираетописание многомернойобласти). Затемкаждая отдельнаяфункция разбираетописание своейобласти и приуспешном окончаниизаполняетнужные таблицы(областей,диагональныхобластей ит.д.), а так жетаблицу имен.В случае неудачногоразбора выдаетсясообщение обошибке.
4.4 Разработкаалгоритмовдля фукцийработы с областями
Помимозадания вычисляемогопространствадля величинына области,понятие и описаниеобласти используютсяв Норме во многихместах. Например,в операторахFOR ASSUME илив операторахввода и вывода.Очень частонеобходимопроизвестинад областямипроверку, являетсяли их пересечениепустым множествомили нет. Например,при определенииинформационныхзависимостеймежду опреаторамии определениемпорядка вычислеий.В данном примеренеобходимоустановитьдает ли пересечениетребуемойобласти Sтреб и
FORB ASSUME X=F(Z,Y[i+1,j]...)
Sтреб
FORC ASSUME Y=F(P,K[i-1,j]...)
областиС пустое множество.Если дает, тоданные операторыне связанымежду собой,иначе второйоператор необходимовычислитьраньше первого.Пересечениеобластей япланирую проводитьследующимобразом. Дляслучая прямоугольныхобластей необходимопо каждомунаправлениюсравнить верхниеи нижние границыиндексов. Длядиагональныхобластей помимосравнениядиапазоновиндексов необходимоаналогичнымобразом сравниватьдиагональныедиапазоны. Еслимы имеем делос условнымиобластями тонеобходиморассматриватьдва случая.Первый - этокогда две этиобласти имеютобщего (пускайне ближайшего)родителя. Тогданеобходимонайти первоготакого родителяи от него провестипроверку, какиееще предки,положительноили отрицательно-условные,находятся напути от этогородителя кданным областям,и если естьразличия, топересечениепусто, иначенет. Это можнопроиллюстироватьс помощьюпредставленияусловных областейв виде бинарногодерева, где водну сторонуидут положительно-условныеобласти,
 ав другуюотрицательно-условные.На рисункепересечениедвух темнозакрашенныхобластей непусто , а пересечениетемно и светлозакрашенных- пусто. Другойслучай возникает,если областине имеют ниодного общегопредка (хотятакой случайочень страненв смысле логикипрограммы).Тогда мы можемпроверить напересечениесамых первыхпредков этихобластей (ониявляютсяпрямоугольными).Если они непересекаются,то и условныене пересекаются,иначе мы считаем,что они могутпересечься. |
Помимопересеченияобластей частотребуется найтиобъединение.Эту задачуаналитическимиметодами решитьочень сложно,поэтому планируетсяреализоватьее методомперебора
5. ЗАКЛЮЧЕНИЕ
В результатепроделаннойработы мноюбыли достигнутыследующие цели:
разработанысновные структурыдля храненияданных, полученныхв результатеразбора описанийобластей;
разработаныалгоритмы инаписаны функцииразбора описанийобластей;
разработаныалгоритмы длянаписанияфункций пересеченияобластей
Некоторыефункции находитсяна стадии доработкии отладки. Завершениеработы над нимипланируетсяв следующемсеместре. Заданиена УИР и КП выполнилпрактическиполностью.
Списоклитературы:
А.Н. Андрианов,К.Н. Ефимкин,И.Б. Задыхайло,Н.В. Поддерюгина"Язык Норма"
А.Н. Андрианов,К.Н. Ефимкин,И.Б. Задыхайло"Непроцедурныйязык Норма иметоды егореализации"
А.Б. Бугеря"Реализацияматематическихфункций языкаНорма дляраспределенныхвысислительныхсистем"
Ф.Льюис“Теоретическиеосновы проектированиякомпиляторов”
*Квант - семантическизаконченныйфрагмент текстапрограммы(например,описание области)
Приложение1Структуратрансляторас языка программированияНорма
Вход: Диагностика,ошибки Исходный текст Лексическийи частично Синтаксическийанализ
программы + синтаксическийанализ ичастичносемантический
опции командной Выделение Групприровка анализописаний иоператоров
строки лексем лексем заполнениевсех таблиц
начальноезаполнениетаблиц
Интерфейсныефункции 
ТАБЛИЦЫ ТАБЛИЦЫ
(имен, констант, (Имен,констант,
ключевых слов областей,индексови т. п.)
МЕНЕДЖЕРПАМЯТИ
Выход:
Текст Генерация Организация Построениеграфа
программы Фортран параллельных информационных
на Фортране программы вычислений зависимостейопеаторов
программы
Приложение2 Синтаксисописаний языкаНорма
Нотация синтаксиса
В нотациисинтаксиса,используемойв данном описании,применяетсярасширеннаяформа Бэкуса-Наура.
Обозначения{A}*,{A}+,{A1...,An},[A]означают
-
{A}*
::= Ж|A|AA...
{A}+
::= A|AA...
{A1...,An}
::= A1|...|An
[A]
::= Ж|A
где A-некоторыйобъект языка,Ж- пусто,|- выбор однойиз альтернатив,...- и так далее.
При определенииправил языкасинтаксическиепонятия набираютсякурсивом, аслова и литеры,воспринимаемыебуквально,прямым шрифтом.Альтернативныеконструкцииперечисляются,как правило,в столбик, каждаяальтернативана отдельнойстроке.
Иногда используютсячастичноподчеркнутыеобозначениясинтаксическихконструкций,например,имя-множества.Синтаксическиэто обозначениеидентичнообозначениюимя, а подчеркнутаячасть конструкциинесет дополнительнуюсемантическуюинформацию.
Обозначениесписок-элементзаменяет непустойсписок элементов,перечисленныхчерез запятую:
список-элемент
элемент{,элемент}*
Вкаждом конкретномслучае определениеэлементаприводится.
Описания
описание:
описание-области
описание-индексов-областей
описание-скалярных-величин
описание-величин-на-области
описание-индексной-конструкции
описание-индексов-распределения
описание-параметров-области
описание-входных
описание-выходных
описание-внешних
Описание областей
описание-области:
описание-безусловной-области
описание-условной-области
описание-безусловной-области
описание-прямоугольной-области
описание-диагональной-области
область
новая областьбез имени
имя-области
безусловная-область
новая областьбез имени
имя-безусловной-области
имя-области
имя-безусловной-области
имя-условной-области
имя-безусловной-области
имя-прямоугольной-области
имя-диагональной-области
Описаниепараметровобласти
описание-параметров-области
DOMAIN PARAMETERS список-значение
значение
имя-параметра-области=целоебез знака
Описание индексовобластей
описание-индексов-областей
INDEX список-имя-индекса
Описание индексовраспределения
описание-индексов-распределения
DISTRIBUTION INDEX имя-индекса= простой-диапазон
[имя-индекса=простой-диапазон]
простой-диапазон
цел-константа[..цел-константа]
Описаниеиндекснойконструкции
описание-индексной-конструкции
MACRO INDEX имя-индексной-конструкции
[список-явное-инд-выражение]
явное-инд-выражение
имя-индекса[{+,-}конст-выражение]
имя-индекса= конст-выражение
имя-индекса= имя-индекса[{+,-}конст-выражение]
Описание внешнихимен
описание-внешних-имен
EXTERNAL FUNCTION список-имя-функции [тип]
EXTERNAL PART список-имя-раздела
Описание областей
описание-области
описание-безусловной-области
описание-условной-области
описание-безусловной-области
описание-прямоугольной-области
описание-диагональной-области
область
новая областьбез имени
имя-области
безусловная-область
новая областьбез имени
имя-безусловной-области
имя-области
имя-безусловной-области
имя-условной-области
имя-безусловной-области
имя-прямоугольной-области
имя-диагональной-области
Описаниебезусловнойобласти
описание-прямоугольной-области
многомерная-область
новая-область
многомерная-область
одномерная-область
[ имя-многомерной-области]: ( область-произведение)
область-произведение
составляющая-область{ ; составляющая-область}+
составляющая-область
многомерная-область
имя-прямоугольной-области
одномерная-область
[ имя-одномерной-области] : ( имя-индекса= значение)
значение
диапазон
конст-выражение
диапазон
конст-выражение.. конст-выражение
новая-область
[имя-нов-области:] новая-область-без-имени
новая-область-без-имени
имя-безусл-области/ список-модификация
модификация
имя-индекса=значение
имя-одномерной-области{{+,-} функция-границ}+
функция-границ
LEFT (конст-выражение)
RIGHT (конст-выражение)
имя-прямоугольной-области
имя-одномерной-области
имя-многомерной-области
имя-нов-области
описание-диагональной-области
имя-диагональной-области:
имя-безусловной-области/ список-условие-на-индекс
Описание условнойобласти
описание-условной-области
имя-условной-области, имя-условной-области:
имя-области/ условие-на-область
Описание величин
описание-скалярных-величин
VARIABLE список-имя-скаляра[тип]
описание-величин-на-областях
VARIABLE список-определение-величин-на-област[тип]
определение-величин-на-области
список-имя-величины-на-области
DEFINED ON безусловная-область
тип
{REAL , INTEGER , DOUBLE}
Приложение4 Схема информационныхтаблиц областей.
ТАБЛИЦА ОБЛАСТЕЙ
-
2 i 1 5 j 10 40 ... 1 
1k 0 100 ... ... ... ... 3 
5j 5 15 t 1 50 ... 2 .... ... ... ... ... ... ... ... ...
Таблица условий
   jc1 c2 i     | Eps>1/2*(i-j)... |
Таблицадиагональныхобластей-
2 i j c1 c1
... 
...... ...
Таблица условныхобластей
-
2523 30 1 
...... ... ...