Методическое пособие для выполнения лабораторных работ и КР, страница 8

Формальное описание синтаксиса в БНФВо многих учебниках, пособиях, электронных справочниках и документации Выможете встретить формальное описание синтаксиса языков программирования и правилзапуска программ. Такое описание необходимо для однозначного понимания правил записи операторов и команд, исключения ошибок и, в конечном счете, снижения сроков освоения языков и написания программ. Существует много различных языков формальногоописания других, извините за тавтологию, формальных языков, в частности языков программирования.

Они делятся на две группы: текстовые и графические. В графическихязыках используются специальные диаграммы и правила их построения (пример графического языка для описания Ассемблера Вы найдете в учебнике Юрова).Более четкое описание можно получить на основе текстовых формальных языков.Одним из примеров распространенных языков формального описания является БНФ.Данная аббревиатура имеет две расшифровки: Бекуса Нормальная Форма (более ранняя) иБекуса Наура Форма (более поздняя).

Разные названия связаны с тем, что второй автор(Наур) внес уточнения в первоначальные правила. В этом пособии мы рассмотрим основные правила применения БНФ для оформления документации ЛР и изучения Ассемблера.4.1. Назначение и состав языка БНФЯзык БНФ является распространенным языком описания формализованных конструкций других языков. Такие языки называют также метаязыками. Можно дать математическое описание этого языка на основе теории множеств и теории формальных языков, ноздесь мы остановимся на более простом смысловом и текстовом его описании.

Язык БНФвключает в себя следующие основные элементы и понятия:− Понятие терминального символа и множества терминальных символов. Под терминальным символом понимается такой элемент описания, который буквальновходить в синтаксические конструкции (предложения) языка. Эти символы не могут быть раскрыты далее в виде правил. Примером терминальных символов могутслужить: знаки операций (“+” , “-“ и т.д.), ключевые слова языка ( for, loop, case идр.) и служебные символы (“=”, “;” и т.д.). Отметим, что любое правило должнобыть раскрыто (порождать), в конечном счете, цепочку терминальных символов.− Понятие нетерминального символа и множества нетерминальных символов.

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

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

Предполагается, что существует некоторое первоначальное прави-2010 год 2 курс 4-й семестр Большаков С.А.“Системное программирование”33ло, с которого должно проводиться описание грамматики и, что более важно,грамматический разбор конкретной конструкции.− Множество метасимволов языка БНФ, которые используются для записи правилграмматики описываемого формального языка. Это символы: ”:=”, “<”,“>” , “|”, “[”, “]”, “{”, “}”, “…”. Более подробно о назначении метасимволов мы поясним ниже.Отметим также, что некоторые символы (а именно, “[” , “]”, “{”, “}”, “…”) входятв расширенный вариант БНФ и не являются обязательными.4.2.

Правила, нетерминальные переменные и метасимволыНетерминальный символ на языке БНФ записывается следующим образом: в угловые кавычки (<…>) помещается произвольный текст, который используется для обозначения понятия языка. Нетерминальный символ и его обозначение должны быть уникальными в пределах описываемой грамматики, то есть не повторяться. Примерами нетерминальных символов могут служить следующие понятия:<Переменная> - понятие, описывающее переменную в программе,<Оператор> - понятие, описывающее оператор в языке программирования.Правило грамматики записывается в следующем виде (правила похожи на операторы присваивания, но нельзя их путать):<Нетерминальный символ>:= <Выражение на основе терминальных символов, метасимволов и нетерминальных символов>Для пояснения самого языка БНФ нам приходиться использовать также язык БНФ.В левой части правила должен быть расположен только один нетерминальный символ.Выражение является комбинацией терминальных и нетерминальных символов, а такжеметасимвола ”|”, который позволяет упростить написание правил и, в конечном счете, неявляется обязательным.

Так, например, два правила вида (где, НС – нетерминальный символ):<НС1>:= <НС2> и<НС1>:= <НС3> можно объединить в правило вида:<НС1>:= <НС2> | <НС3> , где НС1 ÷ НС3 нетерминальные символы.Правила на языке БДН могут быть рекурсивными, это означает, что один и тот женетерминальный символ, задаваемый правилом, может присутствовать в правом выражении этого же правила. Например:<НС1>:= <НС2> | <НС2> <НС1>В выражении правил могут располагаться терминальные символы (ТС). Они могутрасполагаться в любом порядке.

Например:<НС1>:= ТС1 <НС2> ТС2 ТС3 <НС3> ТС4При описании конструкций на языке Ассемблера возникает проблема с использованием угловых скобок, так как они являются также терминальными символами языка. Вэтом случае, либо делается словесное пояснение, либо эти символы выделяются жирнымшрифтом, либо заключаются в круглые кавычки “(“ - ”)”. Например:<Описание записи>:= <Имя записи> <Шаблон записи> (<)<Инициализация записи>(>)Заключенные в круглые скобки символы рассматриваются как терминальные символы языка. Для упрощения записи правил могут дополнительно использоваться квадратные скобки - “[” , “]”.

Применение их означает, что заключенное в них подвыражение может отсутствовать. Например, правил вида:<НС1>:= <НС2> [<НС1>]Заменяет более сложное правило вида:<НС1>:= <НС2> | <НС2> <НС1>При перечислении повторов можно также использовать и фигурные скобки метасимволы - “{”, “}”, если это не усложняет запись правила. Так, например, правило вида:2010 год 2 курс 4-й семестр Большаков С.А.“Системное программирование”34<НС1>:= {<НС2> , } …Означает сокращенную форму записи правила вида:<НС1>:= <НС2> | <НС2> , <НС2> | <НС2> , <НС2> , <НС2> и так далее.Если обратиться к строгой записи на языке БНФ, то использование круглых и фигурных скобок можно исключить. В документациях на многое программные продукты Вынайдете описания на этом языке, включая и расширенное его толкование.При формальном описании на языке БНФ необходимо помимо формальных правилдавать текстовые пояснения основных понятий – нетерминальных символов.

Это выполняется в текстовом режиме.4.3. Примеры описания на БНФРассмотрим несколько примеров описаний на языке БНФ.Пример 1. Описание в БНФ синтаксиса целого числа со знаком:<целое число со знаком>:= <целое число> | + <целое число> | - <целоечисло><целое число>:= <цифра> | <цифра> <целое число><цифра>:= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9Таким синтаксическим правилам соответствуют числа: +15, -35, 01, 12345678788 ит.д. Отметим, что для написания программ, недостаточно одних синтаксических правил,нужно еще дополнительное семантическое (понятийное или смысловое) описание языка(семантические правила). Даже в этом простом примере нужно указать максимальноечисло знаков целой константы, которое допустимо в конкретной системе программирования.

Если данная константа соответствует типу int, то для записи ее можно указать только5 значащих цифр (2∧16 = 65536).В нашем примере нетерминальными символами являются: <целое число со знаком>, <целое число> и <цифра>. Терминальными символами являются: “+”, “-”,“0”,“1”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9”.Отметим также, что один и тот же синтаксис может быть описан разными способами. Так первое правило может быть описано так:<целое число со знаком>:= <знак> <целое число>< знак >:= <пусто> | + | Где <пусто> часто используемый для описания правил нетерминальный (фактически терминальный) символ, означающий пустую строку (отметим – не пробел, которыйявляется значащим терминальным символом. Если при описании правил требуется указать терминальный символ –пробел, то его обозначают специальным символом, например,– “_”).Пример 2.

Инструкция командной строки для запуска программ.<запуск программы>:= <имя программы> _ <список параметров программы><имя программы>:= progr.exe | progr<список параметров программы>:= <Параметр 1>[_< Параметр 2 >] [_< Параметр 3 >]<Параметр 1>:= <Имя файла><Параметр 2>:= /L<Параметр 3>:= /P:<Пароль>Отметим, что и здесь необходимо пояснить смысловое (семантика правил) значениеправил синтаксиса.