Форма Бэкуса-Наура (БНФ)
БНФ - это формальный способ описания синтаксических единиц, при котором они определяются через другие единицы или через элементарные символы.
В некоторых задачах на разбор выражений часть условия может быть представлена в форме БНФ, поэтом ниже приведем несколько примеров такого описания с комментариями.
Имена синтаксических единиц заключаются в угловые скобки. После имени следует знак ::= (читается как "это есть" или "по определению есть"), после него следует описание данной единицы. В приведенном примере сказано, что есть единица, называемая "цифра", которая может быть одним из следующих символов. Знак '|' означает "или".
В фигурных скобках записывается фрагмент, который может (но не обязан) повторяться либое число раз. Данное описание означает, что число без знака начинается с цифры, за которой могут следовать (а могут и нет) другие цифры в любом количестве.
Последовательное упоминание двух или более синтаксических единиц говорит, что более крупная единица состоит из более мелких, идущих именно в том порядке, как они описаны в БНФ. Так, в примере, "число со знаком" начинается с одного знака, который должен быть указан, за которым следует число без знака.
Сумма состоит как минимум из одного числа, за которым может следовать произвольное (в том числе нулевое) количество знаков сложения, после каждого из которых обязательно есть число.
Также возможны рекурсивные описания, когда некоторая синтаксическая единица определяется через аналогичные, но более короткие.