Форма Бэкуса -Наура (профильный уровень информатика)

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

При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность. В этом случае применяют форму Бэкуса-Наура (БНФ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила L  ®  EL и L ®  E записаны в символической форме, и символ L соответствует синтаксическому понятию "список", а символ E - "элемент списка", то их можно представить в форме Бэкуса-Наура так:

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

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

Чтобы сократить описание схемы грамматики, в БНФ разрешается объединять правила c одинаковой левой частью в одно правило, правая часть которого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя объединение правил, для рассматриваемого примера получаем:

<список>::=<элемент списка><список>|<элемент списка>.

Итерационная форма

Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Она предполагает введение специальной операции, которая называется итерацией и обозначается парой фигурных скобок со звездочкой. Итерация вида {a}^* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа a, и пустую цепочку.

{a}^* = {l, a, aa, aaa, aaaa,...}.

Иcпользуя итерацию для описания множества цепочек, задаваемых символическими правилами, для списка получаем:

L ® E { E }*

Например, описание множества цепочек, каждая из которых должна начинаться знаком # и может состоять из произвольного числа букв x и y, может быть представлено в итерационной форме так:

I ® #{x | y}^*

В итерационных формах описания наряду с итерационными cкобками часто применяют квадратные скобки для указания того, что цепочка , заключенная в них, может быть опущена. С помощью таких скобок правила:

A®x A y B z и A®x B z

могут быть записаны так:

A®x [ A y ] B z