Формы Бэкуса-Наура. Задачи 1-5.

Расширенные формы Бэкуса-Наура.

Задача 1.

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

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

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

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

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

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

Решение:

<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

Решение:

<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

Решение:

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

Задача 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>*)
<BinUmnozhenie> ::= <Umnozhenie> ("*" | "/") <CeloeChislo>
<Umnozhenie> ::= <BinUmnozhenie> | <CeloeChislo>
<BinSumma> ::= <Summa> ("+" | "-") <Umnozhenie>
<Summa> ::= <BinSumma> | <Umnozhenie>
<Virazhenie> ::= <Summa>

Задача 5.

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

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

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

Решение:

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