Транслятор с языка описания агрегативных

on

ВВЕДЕНИЕ. Анализ сложных, трудноформализуемых, многокомпо нентных сис тем, таких как системы имитационного моделирования ликвидации по следствий чрезвычайных ситуаций, проведения широкомасштаб ных так тических операций и др., указывает на необходимость применения универ сального подхода к их построению. Одним из таких подходов является описание модели в виде агрегативной системы ( A -схемы). Для удобства построения программных моделей на основе A-схем не обходимо иметь базовые инструменты их реализации. Ввиду того, что сложность, назначение и контекст использования моделей могут значи тельно варьироваться, должен быть разработан механизм, позволяющий создавать базовые унифицированные модели, которые могут дополняться и конкре тизироваться в зависимости от поставленных задач. Такой механизм может быть реализован в виде транслятора, позво ляющего генерировать программные заготовки на языке высокого уровня по опреде ленному описанию системы. Для описания агрегативной сис темы был разработан специальный язык. МЕТОДИКА ЭКСПЕРИМЕНТА Для задания грамматики языка необхо димо охарактеризовать ос нов ные элементы агрегативной системы. © , , 2011 При агрегативном описании производится разбиение системы на подсистемы (агрегаты) с сохранением всех внутренних и внешних коммуникационных связей. В общем случае агрегат A-схемы определяется сле дующими множествами: X ={x i = 0…N -1} — множество вход i X ных сигналов агрегата; Y ={y i = 0…NY -1} i — множество выходных сигналов агрегата; T ={ti i = 0…NT -1} — множество моментов времени; Z ={zi i = 0…NZ -1} — множество внутренних состояний агрегата; H ={h i = 0…N -1} — множество внутренних i H параметров агре гата . Коммуникационные функции характеризуют обмен информацией между агрегатами внутри агрегативной системы и между агрегативной системой и внешней средой. В соответствии с приведенным описанием был предложен следую щий синтаксис языка описания агрегативных систем: COUNT = число [AGREGATE идентификатор { X = Y = H = Z = F = [LINK идентификатор { FROM список контактов TO список контактов }] Приведенный синтаксис языка описания агрегативных систем под ра зумевает наличие трех основных частей: 1. Общее описание системы. 1. Описание агрегатов. 2. Описание коммуникационных функций. Общее описание системы подразумевает указание количества агре гатов. Описание агрегатов включает следующие элементы: 1. Определение входных сигналов. 2. Определение выходных сигналов. 3. Определение внутренних параметров. 4. Определение состояний. 5. Определение реализуемых функций. Описание коммуникационных функций подразумевает определение внутренних связей агрегативной системы, т.е. определяет, какие выходы каких агрегатов связываются с какими входами каких агрегатов. В качестве идентификаторов можно использовать любые последова тельности символов, которые удовлетворяют следующим ограничениям: 1. Идентификатор может состоять из букв латинского алфавита, цифр, знака подчеркивания; никакие другие символы в иден тификаторе недопустимы. 2. Идентификатор не может начинаться с цифры. 3. Идентификатор не может совпадать ни с одним из зарезервиро ванных слов. 4. Длина идентификатора может быть произвольной. Список идентификаторов представляет собой последовательность идентификаторов, разделенных между собой запятыми. Список контактов представляет собой разделенную запятыми после довательность синтаксических единиц вида: agr1(x1), где agr1 — на звание агрегата, x1 — контакт агрегата (входной или выходной). В разработанный язык для типового обозначения некоторых элемен тов введено 10 ключевых слов: COUNT, AGREGATE, LINK, FROM, TO, X, Y, H, Z, F. Грамматика в соответствии с нормальной формой Бэкуса (НФБ) имеет вид : программа ::= заголовок список агрегатов список связей заголовок ::= COUNT = число список агрегатов ::= агрегат | список агрегатов агрегат список связей ::= связь | список связей связь агрегат ::= AGREGATE идентификатор { список полей } связь ::= LINK идентификатор {FROM список контактов TO список контактов } список полей ::= поле | список полей поле поле ::= тип = { список идентификаторов } тип ::= X | Y | H | Z | F список контактов ::= контакт | список контактов , контакт контакт ::= идентификатор ( идентификатор ) список идентификаторов ::= идентификатор | список иденти фикаторов , идентификатор идентификатор ::= буква | идентификатор буква | иден тификатор цифра число ::= цифра | число цифра буква ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | O | P | Q | R | S | T | U | V | W | X | Y | Z | цифра ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Для приведения грамматики к единообразному виду (для упроще ния работы синтаксического и семантического анализаторов) были вве дены следующие обозначения: программа — Pr, заголовок — He, список агрегатов — La, список связей — Ll, агрегат — Ag, связь — Li, список полей — Sn, поле — No, тип — Ty, список контактов — Sc, список идентифика торов — Si, контакт — Co, идентификатор — id, число — di. Транслятор условно может быть разделен на четыре части. Первая часть — это лексический анализатор (или сканер). Задачей сканера является обнаружение и выделение из исходного текста основных символов языка, к которым можно отнести идентификаторы, служебные слова, целые числа, разделители. Существует ряд причин, по которым от деле ние лексического анализатора от других этапов транслятора является предпочтительным. Одной из причин является то, что при описании лек сем можно использовать простой тип грамматики, что позволяет построить эффектив ный алгоритм сканера. Грамматика сканера является регулярной. Каждое правило этой грамматики имеет вид U ::= T или U ::= VT, где Т — терминал, а U, V — нетерминалы: id::= буква | id буква | id цифра число ::= цифра | число цифра разделитель ::= = | ( | ) | + | — | * | / | » | | Пробел | Перевод на но вую строку | Возврат каретки буква ::=a| b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | r | s | t | q | u | w | x | y | z | A | B | C | D | E | F | G | H | I | K | L | M | N | O | P | R | S | T | Q | U | W | X | Y | Z цифра ::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Сканер, диаграмма которого представлена на рисунке 1, реализован в виде конечного автомата, выпол няющего отдельный проход, на котором выполняется полный лексический анализ исходной программы и который выдает синтаксическому анализа тору таблицу, содержащую исходную программу в форме внутренних символов. Состояния автомата определяются следующим образом: s0 — начальное состояние сканера, s1 — иденти фикатор, s2 — число, s3 — разделитель, s4 — комментарий, s5 — ошибка. Результатом работы такого сканера является образ всей программы в виде набора лексем. Символы попадают в один из следующих классов: 1. Идентификаторы. 2. Целые числа. 3. Разделители. Сканер также должен выделить ключевые слова. Они рассматрива ются как известное предопределенное подмножество идентификаторов. После того как из исходной программы был выделен идентификатор, осу ществляется проверка, которая определяет, является ли он ключевым сло вом. Рис. 1. Диаграмма состояний сканера Вторая часть транслятора — синтаксический анализатор. Его задачей является полный синтаксический контроль исходной программы, и раз биение ее на составные части, соответствующие конструкциям исходного языка. Синтаксический анализатор реализует метод восходящего разбора — расширенное предшествование. Практическое применение метода про стого предшествования затруднено ввиду встречающихся неоднозначных отношений предшествования. Существующие алгоритмы, позволяющие устранять неоднозначность, как правило, не гарантируют единственности правых частей правил модифицированной грамматики. Модифицирован ная грамматика значительно расширяется и теряет наглядность. По этой причине был использован метод расширенного предшествования (1,2)(2,1). В соответствии с выбранным типом предшествования редуцирова ние основы производится при нахождении отношения . Символы перепи сы ваются в стек до нахождения отношения между ними . Это и будет со ставлять редуцируемую основу. По ней ищется соответствующее правило в массиве грамматики, выделяется правая часть и помещается вместо редуцируемой основы. При неоднозначности отношений для выделения левого конца ос новы было заготовлено множество левых троек LT. Символы левых троек обозначим SSS. Эти тройки такие, что 123 SS начинают правую часть ка кого-либо пра 23 вила, а символ S1 образует с S2 конфликтную пару. Тогда при разборе, если символы в приводимой строке SS S равны символам одной nn+1 n+2 из троек SSS, то справедливо отношение 123 предше ствования . В противном случае берется отношение =. LT = {«He La AGREGATE «, «La Ll LINK»,»FROM Sc ,», «TO Sc ,»,»{ Sn ;»,»{ Sii,»}. Для построения матрицы предшествования были составлены множе ство LU () — множество самых левых символов относительно нетерминаль ного символа U, RU () — множество самых правых символов относительно нетер минального символа U. Указанные множества приве дены в таблице 1. Параллельно с синтаксическим анализатором работает семантиче ский анализатор, конт Таблица 1 Множества амых левых и самых правых символов относительно нетер минального символа ролирующий программу с точки зрения семантики. Когда синтаксический анализатор узнает конструкцию исходного языка, он вызывает семантический анализатор, который контролирует данную конструкцию с точки зрения семантики и затем запоминает информацию о ней в таблице символов и в таблице констант. После получения внутренней формы представления исходной про граммы происходит обращение к методам, реализующим генерацию ин терфейса и реализаций классов и функций агрегативной системы на языке C++. ЗАКЛЮЧЕНИЕ В ходе исследований был разработан язык опи сания агрегативных систем. Для перевода программы с языка описания аг рега тивных систем на язык высокого уровня C++ был разработан трансля тор, состоящий из лексического, синтаксического и семантического анали зато ров. Разработан ное программное обеспечение позволяет генери ровать ин терфейс и реали зацию базовых классов и функций на языке C++, описы вающих агрегатив ную систему. Рассмотренный транслятор может найти применение при составле нии программных моделей на основе A-схем для систем имитационного моде лирования проведения широкомасштабных тактических операций, ликвидации последствий чрезвычайных ситуаций и др. Моделирование систем: Учеб. для вузов. 4-е изд. — М.: Высш. шк., 2005. — 343с.: ил. Компьютерное моделирование и оценка эффективно сти сложных систем. — М.: Техносфера, 2006. — 280с.: ил. Моделирование сложных систем. — М.: Наука, 1968. — 356 с.: ил. Грис Д. Конструирование компиляторов для цифровых вычисли тельных машин. — М.: Мир, 1975. — 543с.