Расширенные Формы Бэкуса-Наура. Задачи 1-6.

Задача 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

Решение

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

Задача 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

Решение

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

Задача 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

Решение

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

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

2 + 5 + 4 и т.д

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

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

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

2+3*5+7/2-3 

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

Решение

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

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

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

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

Решение

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

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

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

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

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

Решение

<Cifra> ::= [0-9]
<CeloeChislo> ::= "0" | ([1-9] <Cifra>*) | "(" <Virazhenie> ")" | [a-z]
<Umn> ::= <CeloeChislo> (("*" | "/") <CeloeChislo>)*
<Virazhenie> ::= <Umn> (("+" | "-") <Umn>)*
<Resultat> ::= <Virazhenie> | [a-z] "=" <Virazhenie>