Способы описания грамматики алгоритмического языка. Синтаксические диаграммы. Метаязык Бэкуса-Наура. Приведите примеры.

нет
...

Введение 3
1 Форма Бэкуса-Наура 5
1.1 История развития теории и практики синтаксиса языков программирования 5
1.2 Определение и пример БНФ 6
1.3 Расширенная форма Бэкуса-Наура 7
2 Синтаксические диаграммы 9
2.1 Понятие синтаксической диаграммы 9
2.2 Правила построения синтаксических диаграмм 10
3 Описание синтаксиса языков семейства Си 13
3.1 Описание синтаксиса языка Си 13
3.2 Особенности синтаксиса языка Си 15
4 Описания синтаксиса языка Ада 16
4.1 Описания языка Ада 16
4.2 Особенности синтаксиса языка Ада 17
Список литературы 19

 

В любом языке программирования определяются способы, которыми организованы данные и способы, которыми организованы действия над ними. Кроме этого, существует такое понятие, как «элементы языка», которое включает в себя такие элементы, как алфавит (множество символов), лексемы, а так же иные изобразительные средства, которыми располагает язык программирования.
Несмотря на существующее разнообразие языков программирования, тем не менее, их изучение можно произвести примерно по одной схеме. Такое положение вещей связано с присутствием общности в структуре разных языков программирования, объединенных общим признаком – тем, что все они являются языками высокого уровня.

Соглашения относительно обозначений терминалов и нетерминалов также подверглись изменению, хотя это и не столь принципиально. Вот как определена РБНФ в спецификации Оберона-2:«Варианты разделяются знаком |. Квадратные скобки [ и ] означают необязательность записанного внутри них выражения, а фигурные скобки { и } означают его повторение (возможно, 0 раз). Нетерминальные символы начинаются с заглавной буквы (например, Оператор). Терминальные символы или начинаются малой буквой (например, идент), или записываются целиком заглавными буквами (например, begin), или заключаются в кавычки (например, ":=")».К этому можно добавить, что в качестве знака «есть по определению» в РБНФ применяется знак «=», а каждое правило оканчивается точкой. Вот как можно определить синтаксис идентификатора (имени) при помощи РБНФ:Имя = Буква { Буква | Цифра }.Поскольку РБНФ представляет собой метаязык, она должна быть применима в целях описания языков, которые имеют практический интерес. В том числе, ее можно использовать для определения синтаксиса самой РБНФ:Синтаксис = { Правило }.Правило = Имя "=" ВыражениеВыражение = Вариант { "I" Вариант }.Вариант - Элемент { Элемент }.Элемент = Имя | Цепочка | "{" Выражение "}" |"[" Выражение "]" | "{" Выражение "}".Цепочка = "'" { символ ) "'" | '"'{ символ } '"'.В этих определениях нет разницы между именами, которые обозначают терминалы и нетерминалы, хотя подобная формулировка при помощи РБНФ не вызвала бы затруднений. Различение имен было вынесено за рамки синтаксиса и может быть специфицировано (и специфицируется) отдельно. Таким же образом зачастую поступают и при определении языков программирования.2 Синтаксические диаграммы2.1 Понятие синтаксической диаграммыСинтаксическая диаграмма представляет собой направленный граф, имеющий одно входное ребро и одно выходное ребро с помеченными вершинами. При помощи синтаксической диаграммы задаётся Формальный язык.Цепочка пометок, размещенных у вершин на любом пути от входного ребра к выходному представляет собой цепочку языка, который задается этой синтаксической диаграммой. Поэтому есть основания считать, что синтаксическая диаграмма является одной из форм порождающей грамматики автоматных языков.Синтаксические диаграммы обладают достаточно тесной связью с конечными автоматами: всякий автоматный язык может быть задан при помощи синтаксической диаграммы, и напротив, любая синтаксическая диаграмма позволяет построить на ее основе конечный автомат (в общем случае недетерминированный), который будет способен распознавать тот же язык, который задаётся диаграммой.Если по синтаксической диаграмме построить соответствующий распознающий конечный автомат, появляется возможность в дальнейшем реализовать этот автомат как аппаратно, так и программно.Сказанное позволяет сделать вывод, что синтаксические диаграммы могут использоваться не только для порождения, но так же и для распознавания автоматных языков. Диаграммы обрели повсеместную известность вскоре после выхода книги К. Йенсен и Н. Вирта «Паскаль». Они использованы в ее первой части – «Руководстве» – которое представляет собой компактный учебник языка. На REF _Ref358791520 \h Рис. 2 показана одна из имеющихся там диаграмм.Рис. 2. Синтаксическая диаграмма слагаемого (языка Паскаль)2.2 Правила построения синтаксических диаграммПредставление правил грамматики в виде синтаксических диаграмм применяется с целью улучшения зрительного восприятия и облегчения понимания сложных синтаксических описаний. Эти правила могут быть сформулированы в таком виде:Каждому правилу вида <A>  a1 | a2 |...| ak обязательно поставлена в соответствие диаграмма, структура которой определяется правой частью правила.Каждое появление терминального символа x в цепочке ai изображается на диаграмме дугой, помеченной этим символом x, заключенным в кружок.Рис. 3Каждому появлению нетерминального символа <A> в цепочке ai ставится в соответствие на диаграмме дуга, помеченная символом, заключённым в квадрат.Рис. 4Порождающее правило, которое имеет вид:<A>  a1a2...anможет быть изображено на диаграмме следующим образом:Рис. 5Что такое порождающее правило? Когда для совокупности цепочек Ω=(ω0, ω1, ..., ωn) найдется последовательность непосредственных выводов ω0 ⇨ ω1, ..., ωn-1 ⇨ ωn, такая последовательность будет называться выводом ωn из ω0 и обозначается ω0 ⇨ *ωn.Порождающее правило, которое имеет вид:<A>  a1 | a2 | ... | anизображается на диаграмме так:Рис. 6Если порождающее правило задается как итерация:<A>  {a}*,то ему будет соответствовать диаграмма:Рис. 7Количество синтаксических диаграмм, возможных к построению для заданной схемы грамматики, может быть определено числом правил. Для того, чтобы уменьшить число диаграмм, выполняют их объединение, заменяя при этом нетерминальные символы, которые входят в диаграмму на построенные для них диаграммы.Правилами 3-6 предусматривается, что в качестве цепочки a1 на объединенной диаграмме можно использовать диаграммы, которые были построены для этих цепочек. Для примера можно рассмотреть такую грамматику с начальным символом <A>:Vт = { x, +, (, ) }, VA = {<A>, <B>, <C>},R = {<A>  x | (<B>),<B>  <A><C>,<C>  {+<A>}*}Рис. 8Заменив нетерминальные символы на диаграммы, им соответствующие, мы получим объединенную диаграмму вида:Рис. 93 Описание синтаксиса языков семейства Си3.1 Описание синтаксиса языка СиСи (англ. C) представляет собой ни что иное, как стандартизированный процедурный язык программирования, который был разработан в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Денисом Ритчи как развитие языка Би. Си создавался для использования в операционной системе UNIX. С тех пор его портировали и на многие другие операционные системы, в результате чего он превратился в один из самых популярных языков программирования. Си ценим по причине его эффективности; это один из самых популярных языков программирования, предназначенных для разработки системного программного обеспечения. Также он часто используется, чтобы создавать прикладные программы.Хотя Си разрабатывался отнюдь не для новичков, его повсеместно используют в целях обучения программированию. В дальнейшем его синтаксис послужил основой для целого ряда иных языков.Язык Си можно охарактеризовать лаконичностью, современным набором конструкций управления потоком выполнения, структур данных и обширный набор операций.В знаменитой книге Б. Кернигана и Д. Ритчи синтаксиса языка Си описывается в нотации, эквивалентной БНФ, но использующей иные соглашения об обозначениях терминалов и нетерминалов, альтернативных правых частей правил, необязательных конструкций.Запись нетерминалдов ведется курсивом, терминалов – прямым шрифтом. Альтернативные части правил выписываются в столбик по одному в строке или помечаются словами «one of» (один из). Необязательные части сопровождаются подстрочным индексом «opt (от optional) — необязательный; «необ» — в некоторых русских пере- водах). Левая часть правила записывается отдельной строкой с отступом влево.