3.1. Язык Бэкуса-Наура

                    - Благодаря чему? Ах, Эйнштейн... Да-да, помню.
                    Я проходил это в школе во втором классе.
                                   Понедельник начинается в субботу


   Язык, при помощи которого описывают другие языки, называется
метаязыком. Понятно, что русский язык является метаязыком. Ведь
на этом языке мы описываем, например,  язык исполнителя Кукара-
ча. Однако русский  язык, как и любой другой естественный язык,
слишком неточен и словообилен для строгих формальных описаний.
   В программировании очень часто применяют метаязык Бэкуса-На-
ура для описания формальных конструкций. Впервые  этот язык был
использован для описания языка программирования Алгол-60.
   В языке Бэкуса-Наура используются  следующие  символы (мета-
символы):
<>    - скобки, выделяющие определяемое понятие;
::=   - составной символ, который читается "по определению есть";
|     - символ, обозначающий альтернативу, читается "или".

   Примеры определений.

   Пример 1
    <знак сложения> ::= +
Знак сложения по определению есть символ "+".

   Пример 2.

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

   Цифра по определению есть 0 или  1, или 2, или 3, или 4, или
5, или 6, или 7, или 8, или 9.

   Наиболее интересным является  использование языка Бэкуса-На-
ура для создания рекурсивных определений.

   Пример 3.

  <слово> ::= <буква> | <слово><буква>             (1)
  <буква> ::= а | м                                (2)

   Прочитать это определение можно так:
   "Слово"  по  определению есть: или "буква", или объект,  про
который мы знаем, что он "слово",  вслед  за  которым  записана
"буква".
   "Буква" - это либо символ "а", либо символ "м".
   Как видите, первая строка в определении содержит рекурсию!
   Проверим,  соответствуют ли  определению  "слово"  следующие
объекты: "а", "ма", "ав".
   1) Объект "а" - слово, потому что:
   а - буква (правило 2), а буква является словом (правило 1).
   2) Объект "ма" - слово, потому что:
   "м" - это слово (так  как  "м"  -  это буква по правилу 2, а
значит, слово по правилу  1).  Слово, за которым следует буква,
является словом (правило 1), значит, "ма" - слово.
   3) Объект "ав" - не слово, потому что за  словом "а" следует
не буква в смысле правила 2.

   Как проверить соответствие объекта определению? Нужно следо-
вать правилам, заданным в этом определении. Если правила рекур-
сивные, значит  и  проверка будет содержать рекурсию. Проверим,
например, что объект "мама" является словом.

   Объект "мама" - слово, если словом является "мам" (правила 1
и 2).
   Объект "мам" -  слово, если словом является "ма"(правила 1 и
2).
   Объект "ма"  - слово, если  словом является "м" (правила 1 и
2).
   Объект "м" - слово (правило 2).

   Заметим, что по определению 1 словом является любая (не пус-
тая!)  последовательность  из букв "а" и "м". Наблюдение  легко
доказать используя метод математической индукции.

   Напоминание.  Математическая индукция  -  это  универсальный
способ доказательства утверждения F, содержащее зависимость  от
целого числа n. Зависимость обозначается как F(n).
   Доказательство методом математической  индукции проводится в
три шага.
  1) База индукции.
   Утверждение F(n) проверяется при некотором начальном  n = n0
(например, при n0 = 1).
  2) Индуктивное предположение.
   Выдвигается  индуктивное предположение.  Оно  заключается  в
том, что утверждение F(n-1) считается справедливым (n > n0).
  3) Индуктивный переход.
   Доказывается справедливость F(n) с учетом индуктивного пред-
положения, то есть предположения о справедливости F(n-1). Дока-
зательство основывается на попытке представить зависимость F(n)
через F(n-1).
   Итак, пользуясь методом математической индукции, мы  доказы-
ваем, что F(n) справедливо, если справедливо  F(n-1). Это дока-
зательство, наряду с проверкой F для  одного конкретного значе-
ния n0 позволяет утверждать, что F(n) справедливо всегда. Поче-
му?
   Мы доказали, что утверждение F(n) справедливо, если справед-
ливо F(n-1). Этого достаточно чтобы утверждать,  что F(n) спра-
ведливо для любого  n > n0, если F(n0) проверено непосредствен-
но.

....
F(5) справедливо, если справедливо F(4)
F(4) справедливо, если справедливо F(3)
F(3) справедливо, если справедливо F(2)
F(2) справедливо, если справедливо F(1)
F(1) - база индукции, справедливость проверена непосредственно.

   Мы как  будто заставляем работать некоторого исполнителя для
проверки справедливости утверждения F для каждого конкретного n
по следующей рекурсивной программе:

ЭТО Индукция (n)
 ЕСЛИ n = 1
  ТО ОТВЕТ ("F - справедливо для любого n")
  ИНАЧЕ Индукция (n-1)
КОНЕЦ

   Например, процедура Индукция(3) рекурсивно выполнит процеду-
ру Индукция(2). Ведь из  доказательства  индукционного перехода
следует, что F(3) справедливо, если справедливо F(2). Процедура
Индукция(2), аналогично, выполнит процедуру Индукция(1). В пос-
ледней процедуре рекурсия заканчивается: ведь F(1)  справедливо
- это проверенная база индукции.
   Приведенная программа, конечно, лишена всякого практического
смысла. Она  просто  демонстрирует  математическую индукцию как
рекурсивный процесс, который,  пользуясь доказанным индуктивным
переходом сводит проверку F(n) к проверке F(1).

   Вернемся к  нашей  задаче. Докажем, что любая последователь-
ность F(n), состоящая из n символов, каждый из которых принима-
ет значение "а", либо  "м",  является словом в смысле заданного
определения.

   1) База индукции. F(1) состоит из одного символа "а" или "м"
и в  силу правила (2) является буквой, а  значит в силу правила
(1) - словом.
   2) Индукционное предположение. Считаем, что F(n-1) - слово.
   3) Индукционный переход. Докажем, что F(n) - тоже слово.
   Представим F(n) в виде  двух  частей: последний символ и все
остальное. Тогда F(n) можно записать как:

                     F(n)  = F(n-1) s                 (*)

   Здесь s  - это последний символ  в F(n), он  может принимать
значение "a" или "m", то есть является буквой в силу (2).
   Итак, мы представили F(n) как слово F(n-1) за которым следу-
ет буква. Но тогда в силу (1) - F(n) тоже слово.

   Ниже следует список задач  с  ответами. Эти задачи можно ис-
пользовать на занятиях со школьниками для практической работы с
определениями, заданными в нотации Бэкуса-Наура.

 Задача 1.
   Определение 1
   -------------
<имя> ::= <буква> | <имя><буква> | <имя><цифра>
<буква> ::= x | y
<цифра> ::= 1 | 2

   Проверить, являются  ли  приведенные  ниже объекты именами в
смысле определения 1.

1) x   2) xy    3) x1    4) 2y    5) xxxxxxx  6) y321  7) 1212
8) x21    9) X21

Ответ: именами не являются объекты 4), 6), 7), 9)

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

 Задача 2.
   Определение 2
   -------------
<имя> ::= <буква> | <имя><буква> | <имя><цифра>
<буква> ::= <пусто> | x | y
<цифра> ::= 1 | 2
<пусто> ::=
   Проверить, являются  ли  приведенные  ниже объекты именами в
смысле определения 2.

1) x   2) xy    3) x1    4) 2y    5) xxxxxxx  6) y321  7) 1212

Ответ: именем не является объект 6)

   Верно ли следующие утверждения.
   а) Любая последовательность  из  символов "x" и "1" является
именем в смысле определения 2.
   б) Совпадает ли  множество  таких "имен" со множеством имен,
задаваемых определением 2?

Задача 3.
   Определение 3
   -------------
<выражение> ::= <число> |(<выражение>) | <число> + <выражение>
<число> ::= 20 | 30
   Проверить, являются ли приведенные ниже объекты  выражениями
в смысле определения 3.
1) 2  2) 20  3) 2030 4) 20+30 5) (20) 6) (20+30) 7) 20 + (30+30)
8) 20 +
9) + 30
10) (20+(30+(20+20)))

Ответ: выражениями не являются объекты 1), 3), 8), 9)

Задача 4.
   Запишите следующее определение при  помощи  языка Бэкуса-На-
ура.
   Пример - это несколько цифр, соединенные  между собой знаком
"-".

Ответ:
<пример> ::= <цифра> - <цифра> | <пример> - <цифра>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Задача 5.
   Запишите при помощи языка Бэкуса-Наура определение натураль-
ного числа.

Ответ:
<натуральное число> ::= <ненулевая цифра> |
                        <натуральное число> <цифра>
<ненулевая цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<цифра> ::= 0 |<ненулевая цифра>

Задача 6.
   Запишите при  помощи  языка  Бэкуса-Наура определение целого
числа.

 Ответ:
<целое> ::= <целое без знака> | +<целое без знака> | -<целое без знака>
<целое без знака> ::= <цифра> | <целое без знака><цифра>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Задача 7.
Определение 4
-------------
<выражение> ::= <терм> | <выражение> + <терм>
<терм> ::= <первичный> | <терм> * <первичный>
<первичный> ::= x | y | z
   Проверить, являются ли приведенные ниже объекты  выражениями
в смысле определения 4.
1) z   2) x*y+z  3) x+y+z  4)  (x+y)*z  5) x*x  6) y+y*y+y
7) xy  8) +x     9) z+

Ответ: выражениями не являются объекты 4), 7), 8), 9)

Задача 8.

Определение 5
-------------
<объект> ::= <простой> | <составной>
<простой> ::= <объект из СКИ> | <вызов процедуры> | <развилка> | <цикл>
<составной> ::= { <пробел> <цепочка объектов> <пробел> }
<цепочка объектов> ::= <объект> | <цепочка объектов> <пробел> <объект>
...

   Что за объект задает определение 5 (определение не полное)?

   Ответ. Объект - это описание понятия  "команда" языка управ-
ления исполнителями (язык Кукарачи или Корректора).
