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

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

<целое число>::= <целое без знака> |+<целое без знака> | –<целое без знака>

<целое без знака>::= <цифра> | <целое без знака ><цифра>

<цифра>::=0|1|2|3|4|5|6|7|8|9

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

Наличие рекурсивных определений затрудняет чтение и понимание БНФ, хотя и является наиболее удобным способом описания бесконечных языков с помощью конечного числа правил. На практике для описания синтаксиса языков программирования часто используют расширения БНФ, позволяющие более естественно представлять альтернативные, необязательные и покоряющиеся части металингвистических формул. Так, одно из расширений БНФ (РБНФ) разрешает использовать следующие упрощения:

□ необязательные элементы синтаксической конструкции заключаются в квадратные скобки '[' и ']';

□ альтернативные варианты могут в случае необходимости заключаться в круглые скобки для образования многовариантного выбора;

□ элементы синтаксической конструкции, повторяющиеся нуль и более раз, заключаются в фигурные скобки '{' и '}'.

С учетом указанных расширений приведенное ранее определение множества целых чисел можно записать в таком виде:

<целое число>::= [ + | – ] <целое без знака>

<целое без знака>:: <цифра> { <цифра> }

<цифра>::=0|1|2|3|4|5|6|7|8|9

Оба описания эквивалентны, но второе описание более компактно и естественно. Любая синтаксическая конструкция, полученная с помощью РБНФ, Может быть получена с помощью БНФ и наоборот.