Металингвистические формулы Бэкуса-Наура

Метаязык БНФ является стандартным языком для описания синтаксиса языков программирования. БНФ была предложена в 1959 г. Дж. Бэкусом, одним из 13 членов комитета по Алголу-60, для описания синтаксиса этого языка. С этой формой также связывается имя П. Наура (Копенгагенский университет), благодаря предложенным им изменениям и интенсивному использованию БНФ в сообщении об Алголе-60, редактором которого он был. К идее такой формы независимо пришел еще в 1956 г. американский лингвист Н. Хомский.

Металингвистические формулы похожи на обычные математические, поэтому они и называются формулами. Для каждого понятия языка существует единственная метаформула (нормальная формула).

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

Метапеременные заключаются в угловые скобки (< и >). При использовании элементов языка можно условно считать, что метапеременные по смыслу определяет программист.

Метаконстанты при определении языка программирования – это элементы алфавита и служебные слова (т.е. строго определенные понятия). В конструкциях языка метаконстанты необходимо писать так, как они записаны в определении.

Метазнаки:

| – логическая связка ИЛИ

[ ] – выделение необязательной части метаформулы

( ) – группировка сложных конструкций БНФ внутри простых

{ } – повторение части определения произвольное число раз (в том числе ни одного раза)

Примеры метаформул

1) Цифры и числа

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

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

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

<число с фиксированной точкой> ::= <целое> . <целое без знака>

<число с плавающей точкой> ::=

<целое> E <целое> | <число с фикс. точкой> E <целое>

2) Буквы и имена

<буква> ::= A | B | C | … X | Y | Z | a | b | c | … x | y | z

<идентификатор> ::= <буква> {<буква> | <цифра> | <_>}

3) Бинарные операции

<знак арифметической операции> ::= + | - | * | /

<знак операции сравнения> ::= = | < | > | <> | <= | >=

4) Непустой список, состоящий из произвольного числа элементов, разделенных запятой:

<список> ::= <элемент списка> {, <элемент списка>}

5) <условный оператор> ::= if <логическое выражение> then <оператор> [ else <оператор>]

6) <вызов процедуры> ::= <имя> [( <параметр> {, <параметр>} )]

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

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

<двоичное число> ::= <двоичная цифра>|<двоичное число><двоичная цифра>

По принятым правилам при первом обращении к рекурсивно определяемому понятию следует ограничиться нерекурсивной частью формулы, т.е. под двоичным числом понимается двоичная цифра – 0 или 1. Но при втором обращении к метаформуле, определяющей двоичное число, можно применить рекурсию, которая даст следующие варианты этого понятия : 0 1 00 01 10 11, т.е. всевозможные одно- и двухцифровые двоичные числа. Очевидно, что при следующих применениях рекурсии можно получить любое возможное двоичное число.

Также можно дать рекурсивное определение идентификатора:

<идентификатор> ::=

<буква> | <идентификатор> <буква> | <идентификатор> <цифра> | <идентификатор>_