Расширенные Формы Бэкуса-Наура. Пояснения и примеры

Формы Бэкуса-Наура -- подход к описанию синтаксических конструкций, при котором одни фрагменты выражения определяются через другие.

Этот подход используется для описания синтаксиса языков программирования.

Далее мы рассмотрим описание т.н. расширенных формы Бэкуса-Наура (РФБН).

Выражение РФБН

В левой части записывают название термина (выбранное слово), а справа после символа ::= его определение уже в терминах РФБН:

названиеКонструкции ::= ОпределениеКонструкции

Название конструкции может (как соглашение в некоторых реализациях) заключаться в угловые скобки, т.е.:

<названиеКонструкции> ::= ОпределениеКонструкции

Терминальные подвыражения

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

Почему это так станет ясно из примеров ниже, а пока приведем список терминальных конструкций:

1. #xN -- символ, где N -- код этого символа в Unicode
2. [a-zA-Z] или через коды [#xN-#xM] -- любой символ из указанного интервала. Например, интервалу:
   

    [a-c]

   соответствует любой символ из набора:

   a, b, c

3. [abc] или через коды [#xN#xM#xP] -- любой из перечисленных символов
4. [^a-zA-Z] или через коды ^[#xN-#xM] -- любой символ кроме, символов перечисленных в интервале
5. [^abc] или через коды [^#xN#xM#xP] -- любой символ кроме перечисленных
6. "строка" -- соответствует строке, записанной в двойных кавычка
7. 'строка' -- соответствует строке, записанной в одинарных кавычка

-- т.е. фактически мы можем описывать строковый литерал либо в одинарных кавычках либо в двойных (нет разницы).

Терминальные выражения могут использоваться в комбинации названиями конструкций (т.е. нетерминальные конструкции, т.к. они сами определяются через терминальные), а именно:

1. A? -- означает что выражение A необязательно
2. A | B -- т.н. "выбор", соответствует либо выражению A либо выражению B, но не им обои одновременно (аналогично операции "исключающее ИЛИ").
3. A B -- означает, что за выражением A следует выражение B
4. A - B -- строка соответствует A, но не соответствует B
5. A+ -- выражение A повторяется подряд один или более раз
6. A* -- выражение A повторяется подряд ноль или более раз
7. (выражение) -- круглые скобки нужны чтобы группировать выражения, так чтобы эта группа становится отдельной единицей конструкции.

   Что это означает? Например то, что к выражению в скобках также можно, например, применить знаки * и +, чтобы показать что оно входит один или более раз, скажем:

   A ::= "abc"
   B ::= (A)+
   

   -- в данном случае конструкция "B" соответствует строкам:

   abc
   abcabc
   abcabcabc
   и т.д.
   

   И не соответствует, напр., таким строкам:

   abc
   abca
   ab
   

Примеры

Пример 1

В записи будем использовать подход с угловыми скобками для определения конструкций (нетерминальных выражений) и ссылок на них из других конструкций:

<A> ::= "abc"
<B> ::= (<A>)+

-- как уже говорили выше, тут "B" соответствует строкам:

abc
abcabc
abcabcabc
и т.д.

Пример 2 -- число на основе цифры

<Cifra> ::= [0-9]
<CeloeChislo> ::= "0" | ([1-9] <Cifra>*)

-- определяем целое число (нетерминальное выражение CeloeChislo) как набор цифр в любом количестве, при этом если это число не ноль, то оно может начинаться с любой цифры, отличной от нуля.

Фактически в определении конструкции CeloeChislo записано следующее:

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

Пример 3 -- Сложение и вычитание в выражении

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

7
1+23-4+6-7+8
5+2

-- т.е. в выражении может быть как одно число, так и два для одной операции или вообще очень много (любое количество) операций.

Возможный вид такой формы:

<Cifra> ::= [0-9]
<CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
<Virazhenie> ::= <CeloeChislo> (("+" | "-") <CeloeChislo>)*

Пример 4 - рекурсивная ФБН

Выше мы уже рассмотрели формы, с помощью которых можно описать выражения вида:

2+3-4+5

(произвольное число сумм или разностей), теперь рассмотрим ещё более простой случай этого выражения, когда у нас есть только сумма:

2 + 5 + 4 и т.д

-- напишем ФБН для этого случая, но используя рекурсивный подход:

<Cifra> ::= [0-9]
<CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
<BinSumma> ::= <Summa> "+" <CeloeChislo> 
<Summa> ::=  <BinSumma> | <CeloeChislo>

-- здесь любая сумма рекурсивно расписывается как вложенные друг в друга бинарные суммы.
Для такого простого выражения рекурсивный подход может показать сложным, но без него не обойтись в более сложных примерах (напр. для поддержания скобок произвольной вложенности блоков).

Как проверять/запускать ФБН

Самым простым вариантом является запуск онлайн на https://bnfplayground.pauliankline.com/ -- см. видео-пояснение по проверке выражений на это сайте сайте.

Задачи для самостоятельного решения

1. Для описания выражений вида:
   

   7
   1+23-4+6-7+8
   5+2

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

   Можно использовать форму Бэкуса-Наура:

   <Cifra> ::= [0-9]
   <CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
   <Virazhenie> ::= <CeloeChislo> (("+" | "-") <CeloeChislo>)*
   

   
   Задача: Модифицируйте это выражение таким образом, чтобы была возможна поддержка операции умножения, т.е. чтобы форма соответствовала выражениям:

   3
   23*4
   1
   1+23*4*7+6-7+8*9

2. Для описания выражений вида:
   

   7
   1+23-4+6-7+8
   5+2

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

   Можно использовать форму:

   <Cifra> ::= [0-9]
   <CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
   <Virazhenie> ::= <CeloeChislo> (("+" | "-") <CeloeChislo>)*
   

   
   Задача: Модифицируйте это выражение таким образом, чтобы была возможна поддержка, т.н. "Унарного минуса" (т.е. минуса который может быть перед числом, даже если оно одно или если уже есть знак другой операции после предыдущего числа), т.е. чтобы форма соответствовала выражениям:

   -3
   -1+-23*5/7-4
   -5+-2+8

   и при этом по-прежнему не соответствовала выражениям типа:

   +3
   +1++22*4-4
   +5+2

   Подсказки: если не получается решить самостоятельно более 20-60 минут, смотрите Подсказку 1

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

   <Cifra> ::= [0-9]
   <CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
   <Mnogitel> ::= <CeloeChislo> 
   <Slogaemoe> ::= <Mnogitel> (("*" | "/")  <Mnogitel>)*
   <Virazhenie> ::= <Slogaemoe> (("+" | "-") <Slogaemoe>)*
   

   Примечание: форма "множителя" вынесена отдельно не потому что без этого не получится (выше есть более простой пример, без отдельной подформы "множитель"), но т.к. это соответствует порядку разбора подвыражений (правильно "умножение выполняется первым"), напр. в интерпретаторе pascal.js

   Задача: добавьте поддержку унарного минуса, так, чтобы форма соответствовала выражениям:

   -3
   -1+-23-4
   -5+-2+8

   и при этом по-прежнему не соответствовала выражениям типа:

   +3
   +1++22-4
   +5+2

4. Выше мы рассмотрели пример, где выражение вида (только суммы):

   2 + 5 + 4 и т.д

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

   <Cifra> ::= [0-9]
   <CeloeChislo> ::= "0" | ([1-9] <Cifra>*)
   <BinSumma> ::= <Summa> "+" <CeloeChislo> 
   <Summa> ::=  <BinSumma> | <CeloeChislo>

   Задача: Напишите ФБН для поддержки (помимо операции сложения) операций вычитания, умножения и деления:

   2+3*5+7/2-3 

   -- описывая умножение/деление рекурсивно через бинарное умножение/деление (по аналогии с тем, как это выше сделано для суммы через бинарную сумму).

5. Напишите ФБН для описания выражений вида:

   ((2+3)*5)/2 + 7*4

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

6. Добавим поддержку переменных.
   Напишите ФБН для описания выражений вида):

   ((2+3)*5)/2 + 7*4
   b = ((2+3)*5)/2 + 7*4
   a = b + 1

   -- т.е. строка может быть любой из этих трех, а именно:

   1. Просто выражение (с произвольным вложением скобок)
   2. Выражение с присваиваем (в котором участвуют либо числа, либо переменные)

Используемая литература

• Валиков А.Н. Технология XSLT. -- СПб.: БХВ-Петербург, 2002. -- 544 c.: ил. ISBN 5-94157-129-1
• Где проверить/запустить выражения:
  • Ограниченная поддержка синтаксиса есть на сайте: https://bnfplayground.pauliankline.com/ (см. видео о том, как проверять формы на этом сайте)