Формы Бэкуса-Наура

Термины:
Терминалы – это то, из чего состоит язык. Например, человеческий язык состоит из предложений, предложения – из слов, слова бывают подлежащими и сказуемыми. Слова же в свою очередь состоят из букв. Предложения, слова, подлежащие и сказуемые, буквы – это все терминалы. Буквы называют терминальными символами.
Нетерминал или нетерминальный символ — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Например, символы < и > обрамляют некоторые терминалы, знак |разделяет несколько альтернативных терминалов.
Текст может быть правильным (то-есть составленным по правилам этой грамматики) или неправильным. И основная задача теории – определить, правильный или неправильный этот текст. Правила «кодируются» с помощью своеобразных конструкций – форм Бэкуса-Наура.

Более сложные варианты.
Некоторые конструкции (в правой части строки), взятые в квадратные скобки
([ … ]),
означают, что конструкция может отсутствовать (то-есть или присутствует один раз, или отсутствует). А если без таких скобок – значит присутствует строго один раз.
Фигурные скобки
({ … })
означают, что «обрамленная» ими конструкция повторяется некоторое (возможно нулевое) количество раз.
{/ … /}
означает, что повторение 1 или большее количество раз (то-есть ненулевое количество).
В некоторых случаях символы для нетерминалов < и > опускают.

Рассмотрим примеры:
1) Дадим определение идентификатору с помощью БНФ:
<Буква> ::= A|B|C|…|Z
<Цифра> ::= 0|1| … |9
<Идентификатор> ::= <Буква> {<Буква>|<Цифра>}
Помните? Идентификатор начинается обязательно с буквы, а дальше идет некоторое количество букв или цифр (в принятых обозначениях A, B, A1, B2C3)
Всегда есть «самый главный» терминал (и, соответственно, главная строка, в левой части которой он находится), соответствующий тому объекту, который мы исследуем. В данном случае самый главный терминал – это «Идентификатор».

2) Грамматика целых чисел без знака:
<число> ::= <цифра>|<цифра><число>
<цифра> ::= 0|1|2|…|9
Обратим внимание, что терминал «число» встречается в первой строке 2 раза. Это важный момент. Он приводит к появлению рекурсии.
3) Формула с плюсами и минусами без скобок.
<формула> ::= <число>|<формула><знак><число>
<знак> ::= +|- (может быть и так: <знак> ::= +|-|*|/)
Другая форма записи
<формула> ::= <слаг> {
<слаг>}
<слаг> ::= <число>
::= +|-
А если и числа, и переменные, то:
<формула> ::= <слаг> {
<слаг>}
<слаг> ::= <число>|<переменная>
::= +|-

4) Формула с плюсами, минусами и скобками.
<формула> ::=
|<формула><знак><число>
::= <число>|(<формула>)
<знак> ::= +|-
Во второй строке появились скобки. «оp» – это промежуточный терминал, введенный для удобства.
5) Формула с плюсами и минусами, а также с умножением и делением без скобок. Входят в формулу не только числа, но и переменные.
<формула> ::= <слаг> {
<слаг>}
<слаг> ::= <множ>{
<множ>}
<множ> ::= <число>|<переменная>
::= +|-
::= *|/
Т.е., самые крупные блоки, которые мы выделяем из строки с формулой – это слагаемые. Этим определяется самый низший приоритет операций сложения-вычитания. Отметим, что левое слагаемое не состоит из вложенных слагаемых, в отличие от правого.

6) Формула с плюсами и минусами, с умножением и делением без скобок, а также с унарным плюсом-минусом (причем унарный знак может присутствовать перед числом или переменной лишь в единственном числе).
<формула> ::= <слаг> {
<слаг>}
<слаг> ::= <множ_со_знаком>{
<множ_со_знаком>}
<множ_со_знаком> ::= [
]<множ>
<множ> ::= <число>|<переменная>
::= +|-
::= *|/
7) Формула с плюсами и минусами, умножением и делением и со скобками.
<формула> ::= <слаг> {
<слаг>}
<слаг> ::= <множ>{
<множ>}
<множ> ::= <число>|<переменная>|(<формула>)
::= +|-
::= *|/

8) Добавляем функции (встроенные) одного переменного (например sin и cos).
<формула> := <слаг> {
<слаг>}
<слаг> := <множ>{
<множ>}
<множ> := <число>|<переменная>|(<формула>)|
(<формула>)
:= +|-
:= *|/
:= sin|cos