Способы описания грамматики.

Формальное определение грамматики. Форма Бэкуса—Наура

Грамматика — это описание способа построения предложений некоторого языка. Иными словами, грамматика — это математическая система, определяющая язык. Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика — это генератор цепочек языка. Она относится ко второму способу определения языков — порождению цепочек символов.

Грамматику языка можно описать различными способами. Например, грамматика русского языка описывается довольно сложным набором правил, которые изуча­ют в начальной школе. Для некоторых языков (в том числе для синтаксических конструкции языков программирования) можно использовать формальное опи­сание грамматики, построенное на основе системы правил (пли продукций). Правило (пли продукция) — это упорядоченная пара цепочек символов (α, β). В пра­вилах важен порядок цепочек, поэтому их чаще записывают в виде α → β (или α::=β). Такая запись читается как «α порождает β» или «β по определению есть α». Грамматика языка программирования содержит правила двух типов; первые (определяющие синтаксические конструкции языка) довольно легко поддаются фор­мальному описанию; вторые (определяющие семантические ограничения языка) обычно излагаются в неформальной форме. Поэтому любое описание (или стан­дарт) языка программирования обычно состоит из двух частей: вначале фор­мально излагаются правила построения синтаксических конструкции, а потом на естественном языке дается описание семантических правил.

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквива­лентными, если заданные ими языки различаются не более чем на пустую цепоч­ку символов:

Формально грамматика G определяется как четверка G(VT,VN, P, S), где: VT — множество терминальных символов или алфавит терминальных символов; VN — множество нетерминальных символов пли алфавит нетерминальных сим­волов;

P — множество правил (продукций) грамматики, вида α → β, где ;

S — целевой (начальный) символ грамматики .

Алфавиты терминальных и нетерминальных символов грамматики не пересека­ются: . Это значит, что каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть терминальным и нетерминальным одновременно. Целевой символ грамматики — это всегда не­терминальный символ. Множество называют полным алфавитом грамматики G.

Во множестве правил грамматики может быть несколько правил, имеющих оди­наковые левые части, вида: α → β₁, α → β₂,.. α → β_n. Тогда эти правила объеди­няют вместе и записывают в виде: α → β₁| β₂|…| β_n. Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса—Наура. Форма Бэкуса—Наура предусматривает, как правило, также, что нетерминальные симво­лы берутся в угловые скобки: < >.

Ниже приведен пример грамматики, которая определяет язык целых десятичных чисел со знаком:

G({0,1,2,3,4,5,6,7,8,9,+,-}, {<число>, <чс>, <цифра>}, P, <число>)

P:

<<число> → <чс> | +<чс> | -<чс>

<<чс> → <цифра> | <чс><цифра>

<<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Запись правил грамматик с использованием метасимволов

Запись правил грамматик с использованием метасимволов предполагает, что в строке правила грамматики могут встречаться специальные символы — мета­символы, — которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы: ( ) (круглые скобки), [ ] (квадратные скобки), { } (фигурные скобки), " " (кавыч­ки) и , (запятая). Эти метасимволы имеют следующий смысл:

· круглые скобки означают, что из всех перечисленных внутри них цепочек сим­волов в данном месте правила грамматики может стоять только одна цепочка;

· квадратные скобки означают, что указанная в них цепочка может встречать­ся, а может и не встречаться в данном месте правила грамматики (то есть мо­жет быть в нем один раз или ни одного раза);

· фигурные скобки означают, что указанная внутри них цепочка может не встречаться в данном месте правила грамматики ни одного раза, встречаться один раз или сколь угодно много раз;

· запятая служит для того, чтобы разделять цепочки символов внутри круглых скобок;

· кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом — то есть когда одна из скобок или за­ пятая должны присутствовать в цепочке символов языка (если саму кавычку нужно включить в цепочку символов, то ее надо повторить дважды — этот принцип знаком разработчикам программ).

Вот как должны выглядеть правила рассмотренной выше грамматики G, если их записать с использованием метасимволов:

<число> → [(+, -)]<цифра>{<цифра>}

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Вторая строка правил не нуждается в комментариях, а первое правило читается так: «число есть цепочка символов, которая может начинаться с символов + или -, должна содержать дальше одну цифру, за которой может следовать любое количество цифр». В отличие от формы Бэкуса—Наура, в форме записи с помо­щью метасимволов, как видно, во-первых, убран из грамматики малопонятный нетерминальный символ <чс>, а во-вторых — удалось полностью исключить ре­курсию. Грамматика в итоге стала более понятной.

Форма записи правил с использованием метасимволов — это удобный и понят­ный способ представления правил грамматик. Она во многих случаях позволяет полностью избавиться от рекурсии, заменив ее символом итерации { } (фигур­ные скобки). Как будет понятно из дальнейшего материала, эта форма наиболее употребительна для одного из типов грамматик — регулярных грамматик. Кроме указанных выше метасимволов в целях удобства записи в описаниях грамматик иногда используют и другие метасимволы, при этом предварительно дается разъяснение их смысла. Принцип записи от этого не меняется. Также иногда дополняют смысл уже существующих метасимволов. Например, для ме­тасимвола { } (фигурные скобки) существует удобная форма записи, позво­ляющая ограничить число повторений цепочки символов, заключенной внутри них:{ }n, где и n > 0. Такая запись означает, что цепочка символов, стоящая в фигурных скобках, может быть повторена от 0 до n раз (не более n раз). Это очень удобный метод наложения ограничений на длину цепочки. Для рассмотренной выше грамматики G таким способом можно, например, запи­сать правила, если предположить, что она должна порождать целые десятичные числа, содержащие не более 15 цифр:

<<число> → [(+, -)]<цифра>{<цифра>}14

<цифра> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Для записи того лее самого ограничения в форме Бэкуса—Наура или в форме с ме­тасимволами потребовалось бы 15 правил.

Запись правил грамматик в графическом виде

При записи правил в графическом виде вся грамматика представляется в форме набора специальным образом построенных диаграмм. Эта форма была предло­жена при описании грамматики языка Pascal, а затем она получила широкое распространение в литературе. Она доступна не для всех типов грамматик, а только для тех типов, где в левой части правил присутствует не более одного символа, но этого достаточно, чтобы ее можно было использовать для описания грамма­тик известных языков программирования.

В такой форме записи каждому нетерминальному символу грамматики соответ­ствует диаграмма, построенная в виде направленного графа. Граф имеет следую­щие типы вершин:

· точка входа (на диаграмме никак не обозначена, из нее просто начинается входная дуга графа);

· нетерминальный символ (на диаграмме обозначается прямоугольником, в ко­торый вписано обозначение символа);

· цепочка терминальных символов (на диаграмме обозначается овалом, кругом или прямоугольником с закругленными краями, внутрь которого вписана цепочка);

· узловая точка (на диаграмме обозначается жирной точкой или закрашенным кружком);

· точка выхода (никак не обозначена, в нее просто входит выходная дуга графа).

Каждая диаграмма имеет только одну точку входа и одну точку выхода, но сколько угодно вершин других трех типов. Вершины соединяются между собой направленными дугами графа (линиями со стрелками). Из входной точки дуги могут только выходить, а во входную точку — только входить. В остальные вершины дуги могут как входить, так и выходить (в правильно построенной грам матике каждая вершина должна иметь как минимум один вход и как минимум один выход).

Чтобы построить цепочку символов, соответствующую какому-либо нетерми­нальному символу грамматики, надо рассмотреть диаграмму для этого символа. Тогда, начав движение от точки входа, надо двигаться по дугам графа диаграммы через любые вершины вплоть до точки выхода. При этом, проходя через вершину, обозначенную нетерминальным символом, этот символ следует поместить в ре­зультирующую цепочку. При прохождении через вершину, обозначенную цепочкой терминальных символов, эти символы также следует поместить в результирую­щую цепочку. При прохождении через узловые точки диаграммы над результи­рующей цепочкой никаких действий выполнять не надо. Через любую вершину графа диаграммы, в зависимости от возможного пути движения, можно пройти один раз, ни разу или сколь угодно много раз. Как только мы попадем в точку выхода диаграммы, построение результирующей цепочки будет закончено. Результирующая цепочка, в свою очередь, может содержать нетерминальные символы. Чтобы заменить их на цепочки терминальных символов, нужно, опять же, рассматривать соответствующие им диаграммы. И так до тех пор, пока в цепоч­ке не останутся только терминальные символы. Очевидно, что для того, чтобы построить цепочку символов заданного языка, надо начать рассмотрение с диа­граммы целевого символа грамматики.

Это удобный способ описания правил грамматик, оперирующий образами, а по­тому ориентированный исключительно на людей. Даже простое изложение его основных принципов здесь оказалось довольно громоздким, в то время как суть способа довольно проста. Это можно легко заметить, если посмотреть на описа­ние понятия «число» из грамматики G с помощью диаграмм на рисунке. Как уже было сказано выше, данный способ в основном применяется в литерату­ре при изложении грамматик языков программирования. Для пользователей — разработчиков программ — он удобен, но практического применения в компиля­торах пока не имеет.

Существуют и другие способы описания грамматик, но они не так часто встречаются в литературе.

Графическое представление грамматики целых десятичных числе со знаком

6.30. Унифицированный язык моделирования UML: общая характеристика.

UML — стандартный язык для написания моделей анализа, проектирования и реализации объектно-ориентированных программных систем. UML может использоваться для визуализации, спецификации, конструирования и до­кументирования результатов программных проектов. UML — это не визуальный язык программирования, но его модели прямо транслируются в текст на языках программирования (Java, C++, Visual Basic, Ada 95, Object Pascal) и даже в таблицы для реляционной БД.

Словарь UML образует три разновидности строительных блоков: предметы, отношения, диаграммы.

Предметы – это абстракции, которые являются основными элементами в модели, отношения связывают эти предметы, диаграммы группируют коллекции предметов.

Предметы в UML

В UML имеются четыре разновидности предметов:

· структурные предметы;

· предметы поведения;

· группирующие предметы;

· поясняющие предметы.

Структурные предметы являются существительными в UML-моделях. Они представляют статические части модели – понятийные и физические элементы. Перечислим 8 разновидностей структурных предметов.

1. Класс – описание множества объектов, которые разделяют одинаковые свойства, операции, отношения и семантику (смысл). Класс реализует один или несколько интерфейсов. Как показано на рисунке, графически класс отобра­жается в виде прямоугольника, обычно включающего секции с именем, свой­ствами (атрибутами) и операциями.

2. Интерфейс — набор операций, которые определяют услуги класса или компонента. Интерфейс описывает поведение элемента, видимое извне. Интерфейс может представлять полные услуги класса или компонента или часть таких услуг. Интерфейс определяет набор спецификаций операций (их сигнатуры), а не набор реализаций операций. Графически интерфейс изображается в виде кружка с именем, как показано на рисунке. Имя интерфейса обычно начинает­ся с буквы «I». Интерфейс редко показывают самостоятельно. Обычно его при­соединяют к классу или компоненту, который реализует интерфейс.

3. Кооперация (сотрудничество) определяет взаимодействие и является совокупностью ролей и других элементов, которые работают вместе для обеспе­чения коллективного поведения более сложного, чем простая сумма всех элементов. Таким образом, кооперации имеют как структурное, так и пове­денческое измерения. Конкретный класс может участвовать в нескольких кооперациях. Эти кооперации представляют реализацию паттернов (образ­цов), которые формируют систему. Как показано на рисунке, графически кооперация изображается как пунктирный эллипс, в который вписывается ее имя.

4. Актер — набор согласованных ролей, которые могут играть пользователи при взаимодействии с системой (ее элементами Use Case). Каждая роль требует от системы определенного поведения. Как показано на рисунке, актер изобража­ется как проволочный человечек с именем.

5. Элемент Use Case (Прецедент) — описание последовательности действий (или нескольких последовательностей), выполняемых системой в интересах отдель­ного актера и производящих видимый для актера результат. В модели элемент Use Case применяется для структурирования предметов поведения. Элемент Use Case реализуется кооперацией. Как показано на рисунке, элемент Use Case изображается как эллипс, в который вписывается его имя.

6. Активный класс — класс, чьи объекты имеют один или несколько процессов (или потоков) и поэтому могут инициировать управляющую деятельность. Активный класс похож на обычный класс за исключением того, что его объекты действуют одновременно с объектами других классов. Как показано на рисунке активный класс изображается как утолщенный прямоугольник, обычно включающий имя, свойства (атрибуты) и операции.

7. Компонент — физическая и заменяемая часть системы, которая соответствует набору интерфейсов и обеспечивает реализацию этого набора интерфейсов. В систему включаются как компоненты, являющиеся результатами процесса разработки (файлы исходного кода), так и различные разновидности исполь­зуемых компонентов (СОМ+-компоненты, Java Beans). Обычно компонент — это физическая упаковка различных логических элементов (классов, интерфей­сов и коопераций). Как показано на рисунке, компонент изображается как пря­моугольник с вкладками, обычно включающий имя.

8. Узел — физический элемент, который существует в период работы системы и представляет ресурс, обычно имеющий память и возможности обработки. В узле размещается набор компонентов, который может перемещаться от узла к узлу. Как показано на рисунке, узел изображается как куб с именем.

Предметы поведения — динамические части UML-моделей. Они являются глаголами моделей, представлением поведения во времени и пространстве. Существу­ет две основные разновидности предметов поведения.

1. Взаимодействие — поведение, заключающее в себе набор сообщений, которыми обменивается набор объектов в конкретном контексте для достижения оп­ределенной цели. Взаимодействие может определять динамику как совокупно­сти объектов, так и отдельной операции. Элементами взаимодействия являются сообщения, последовательность действий (поведение, вызываемое сообщением) и связи (соединения между объектами). Как показано на рисунке, сообще­ние изображается в виде направленной линии с именем ее операции.

2. Конечный автомат — поведение, которое определяет последовательность состояний объекта или взаимодействия, выполняемые в ходе его существования в ответ на события (и с учетом обязанностей по этим событиям). С помощью конечного автомата может определяться поведение индивидуального класса или кооперации классов. Элементами конечного автомата являются состояния, пе­реходы (от состояния к состоянию), события (предметы, вызывающие перехо­ды) и действия (реакции на переход). Как показано на рисунке, состояние изображается как закругленный прямоугольник, обычно включающий его имя и его подсостояния (если они есть).

Эти два элемента — взаимодействия и конечные автоматы — являются базисными предметами поведения, которые могут включаться в UML-модели. Семантически эти элементы ассоциируются с различными структурными элементами (прежде всего с классами, кооперациями и объектами).

Группирующие предметы. — организационные части UML-моделей. Это ящики, по которым может быть разложена модель. Предусмотрена одна разновидность груп­пирующего предмета — пакет.

Пакет — общий механизм для распределения элементов по группам. В пакет мо­гут помещаться структурные предметы, предметы поведения и даже другие груп­пировки предметов. В отличие от компонента (который существует в период выполнения), пакет — чисто концептуальное понятие. Это означает, что пакет су­ществует только в период разработки. Как показано на рисунке, пакет изображает­ся как папка с закладкой, на которой обозначено его имя и, иногда, его содержание.

Поясняющие предметы — разъясняющие части UML-моделей. Они являются за­мечаниями, которые можно применить для описания, объяснения и комментиро­вания любого элемента модели. Предусмотрена одна разновидность поясняющего предмета — примечание.

Примечание — символ для отображения ограничений и замечаний, присоеди­няемых к элементу или совокупности элементов. Как показано на рисунке примечание изображается в виде прямоугольника с загнутым углом, в который вписывается текстовый или графический комментарий.

Отношения в UML

В UML имеются четыре разновидности отношений:

· зависимость;

· ассоциация;

· обобщение;

· реализация.

Эти отношения являются базовыми строительными блоками отношений. Они ис­пользуются при написании моделей.

1. Зависимость — семантическое отношение между двумя предметами, в котором изменение в одном предмете (независимом предмете) может влиять на семан­тику другого предмета (зависимого предмета). Как показано на рисунке, за­висимость изображается в виде пунктирной линии, возможно направленной на независимый предмет и иногда имеющей метку.

2.Ассоциация — структурное отношение, которое описывает набор связей, явля­ющихся соединением между объектами. Агрегация — это специальная разно­видность ассоциации, представляющая структурное отношение между целым и его частями. Как показано на рисунке, ассоциация изображается в виде сплошной линии, возможно направленной, иногда имеющей метку и часто вклю­чающей другие «украшения», такие как мощность и имена ролей.

3. Обобщение — отношение специализации/обобщения, в котором объекты спе­циализированного элемента (потомка, ребенка) могут заменять объекты обоб­щенного элемента (предка, родителя). Иначе говоря, потомок разделяет структуру и поведение родителя. Как показано на рисунке, обобщение изображается в виде сплошной стрелки с полым наконечником, указывающим на родителя.

4. Реализация — семантическое отношение между классификаторами, где один классификатор определяет контракт, который другой классификатор обязуется выполнять (к классификаторам относят классы, интерфейсы, компоненты, элементы Use Case, кооперации). Отношения реализации применяют в двух случаях: между интерфейсами и классами (или компонентами), реализующими их; между элементами Use Case и кооперациями, которые реализуют их. Как показано на рисунке, реализация изображается как нечто среднее между обобщением и зависимостью.

Диаграммы в UML

Диаграмма — графическое представление множества элементов, наиболее часто изображается как связный граф из вершин (предметов) и дуг (отношений). Диа­граммы рисуются для визуализации системы с разных точек зрения, затем они ото­бражаются в систему. Обычно диаграмма дает неполное представление элементов, которые составляют систему. Хотя один и тот же элемент может появляться во всех диаграммах, на практике он появляется только в некоторых диаграммах. Теоретически диаграмма может содержать любую комбинацию предметов и отно­шений, на практике ограничиваются малым количеством комбинаций, которые соответствуют пяти представлениям архитектуры ПС. По этой причине UML вклю­чает девять видов диаграмм:

1. диаграммы классов;

2. диаграммы объектов;

3. диаграммы Use Case (диаграммы прецедентов);

4. диаграммы последовательности;

5. диаграммы сотрудничества (кооперации);

6. диаграммы схем состояний;

7. диаграммы деятельности;

8. компонентные диаграммы;

9. диаграммы размещения (развертывания).

Диаграмма классов показывает набор классов, интерфейсов, сотрудничеств и их отношений. При моделировании объектно-ориентированных систем диаграммы классов используются наиболее часто. Диаграммы классов обеспечивают стати­ческое проектное представление системы. Диаграммы классов, включающие ак­тивные классы, обеспечивают статическое представление процессов системы.

Диаграмма объектов показывает набор объектов и их отношения. Диаграмма объек­тов представляет статический «моментальный снимок» с экземпляров предметов, которые находятся в диаграммах классов. Как и диаграммы классов, эти диаграммы обеспечивают статическое проектное представление или статическое представление процессов системы (но с точки зрения реальных или фототипичных случаев).

Диаграмма Use Case (диаграмма прецедентов) показывает набор элементов Use Case, актеров и их отношений. С помощью диаграмм Use Case для системы создается статическое представление Use Case. Эти диаграммы особенно важны при орга­низации и моделировании поведения системы, задании требований заказчика к системе.

Диаграммы последовательности и диаграммы сотрудничества — это разновиднос­ти диаграмм взаимодействия.

Диаграмма взаимодействия показывает взаимодействие, включающее набор объек­тов и их отношений, а также пересылаемые между объектами сообщения. Диа­граммы взаимодействия обеспечивают динамическое представление системы.

Диаграмма последовательности — это диаграмма взаимодействия, которая выде­ляет упорядочение сообщений по времени.

Диаграмма сотрудничества (диаграмма кооперации) — это диаграмма взаимодей­ствия, которая выделяет структурную организацию объектов, посылающих и при­нимающих сообщения. Диаграммы последовательности и диаграммы сотрудниче­ства изоморфны, что означает, что одну диаграмму можно трансформировать в другую диаграмму.

Диаграмма схем состояний показывает конечный автомат, представляет состоя­ния, переходы, события и действия. Диаграммы схем состояний обеспечивают ди­намическое представление системы. Они особенно важны при моделировании по­ведения интерфейса, класса или кооперации. Эти диаграммы выделяют такое поведение объекта, которое управляется событиями, что особенно полезно при мо­делировании реактивных систем.

Диаграмма деятельности — специальная разновидность диаграммы схем состоя­ний, которая показывает поток от действия к действию внутри системы. Диаграм­мы деятельности обеспечивают динамическое представление системы. Они осо­бенно важны при моделировании функциональности системы и выделяют поток управления между объектами.

Диаграмма размещения (диаграмма развертывания) показывает конфигурацию обрабатывающих узлов периода выполнения, а также компоненты, живущие в них. Диаграммы размещения обеспечивают статическое представление размещения системы. Они связаны с компонентными диаграммами в том смысле, что узел обыч­но включает один или несколько компонентов.

Механизмы расширения в UML

UML — развитый язык, имеющий большие возможности, но даже он не может отразить все нюансы, которые могут возникнуть при создании различных моделей. Поэтому UML создавался как открытый язык, допускающий контролируемые расширения. Механизмами расширения в UML являются:

· ограничения;

· теговые величины;

· стереотипы.

Ограничение (constraint) расширяет семантику строительного UML-блока, позво­ляя добавить новые правила или модифицировать существующие. Ограничение показывают как текстовую строку, заключенную в фигурные скобки {}.

Теговая величина (tagged value) расширяет характеристики строительного UML-блока, позволяя создать новую информацию в спецификации конкретного элемен­та. Теговую величину показывают как строку в фигурных скобках {}. Строка име­ет вид

имя теговой величины = значение.

Иногда (в случае предопределенных тегов) указывается только имя теговой величины.

Стереотип (stereotype) расширяет словарь языка, позволяет создавать новые виды строительных блоков, производные от существующих и учитывающие специфику новой проблемы. Элемент со стереотипом является вариацией существующего элемента, имеющей такую же форму, но отличающуюся по сути. У него могут быть дополнительные ограничения и теговые величины, а также другое визуальное пред­ставление. Он иначе обрабатывается при генерации программного кода. Отобра­жают стереотип как имя, указываемое в двойных угловых скобках (или в угловых кавычках). <<call>>