Способы описания синтаксиса

Для того, чтобы описать синтаксис алгоритмического языка, также необходим какой-то язык. Речь идет не о языке программирования, на котором будут записываться алгоритмы решения тех или иных задач, а о языке, на котором будет описываться сам этот язык программирования. Другими словами, речь идет о метаязыке ("надъязыке"), предназначенном для описания других языков. Для строгого и точного описания синтаксиса алгоритмических языков используются специально разработанные для этой цели способы. Наиболее распространенными из них являются металингвистические формулы Бэкуса-Наура (язык БНФ).

Для каждого понятия языка должная существовать единственная метаформула, в левой части которой указывается определенное понятие, т.е. метапеременная языка БНФ, а правая часть формулы тем или иным способом задает все множество значений этой переменной, т.е. все допустимые конструкции, которые объединяются в это понятие. Для большей наглядности все метапеременные обычно заключаются в угловые скобки "<" и ">" (предполагается, что эти скобки не принадлежат алфавита определяемого языка, т.е. являются метасимволами), например <число>. Левая и правая части метаформулы разделяются метасимволом "::=", смысл которого эквивалентен словам "по определению есть".

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

Допустим, например, что мы хотим ввести в употребление понятие <двоичный код>, под которым понималась бы любая непустая последовательность цифр 0 и 1. В этом случае можно поступить следующим образом. Сначала сказать, что любая отдельная цифра 0 или 1 по определению является двоичным кодом — тем самым выделить частный случай, когда двоичный код состоит из одной цифры. А затем сказать, что если к любому двоичному коду приписать справа еще одну, любую из этих цифр, то по определению это тоже должно считаться двоичным кодом. То, что было сказано выше словами, можно просто и компактно выразить с помощью метаформул:

<двоичная цифра> ::= 0 | 1

<двоичный код> ::= <двоичная цифра> | <двоичный код> <двоичная цифра>

Определение можно выразить и в одной строчке без определения дополнительной метапеременной <двоичная цифра>:

<двоичный код> ::= 0 | 1 | <двоичный код>0|<двоичный код>1

Как видно, в правой части метаформулы, определяющей понятие <двоичный код> используется само это определяемое понятие. Подобного рода определения называются рекурсивными. Чтобы при этом не получилось "порочного круга", правая часть формулы должна содержать по крайней мере одно частное определение, в котором определяемый термин не используется.

Для задания синтаксических конструкций произвольной длины часто используется и другой способ: вводятся еще два метасимвола, например фигурные скобки "{" и "}", и заключение в эти скобки какой-либо конструкции в метаформуле означает, что эта конструкция может повторяться нуль или более раз. С использование этого способа можно дать простое эквивалентное определение понятия < двоичный код>:

<двоичный код> ::= <двоичная цифра>{<двоичная цифра>}