Расширенные формулы Бэкуса-Наура

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

<формула> -->

<нетерминал> ::= <сложная цепочка>

<нетерминал> -->

<нетерминал><нетерминальный символ>

<нетерминал> -->

<нетерминальный символ>

<сложная цепочка> -->

<сложная цепочка> | <элемент>

<сложная цепочка> -->

<элемент>

<элемент> -->

<простая цепочка>

<элемент> -->

<расширение>

<расширение> -->

[ <сложная цепочка> ]

<расширение> -->

{ <сложная цепочка> }

<простая цепочка> -->

*

<простая цепочка> -->

<простая цепочка><нетерминал>

<простая цепочка> -->

<простая цепочка><терминал>

<простая цепочка> -->

<простая цепочка><расширение>

<терминал> -->

<терминал><терминальный символ>

<терминал> -->

<терминальный символ>

При этом <терминальный символ> принадлежит конечному множеству терминальных символов описываемого языка, а <нетерминальный символ> принадлежит множеству нетерминальных символов описываемого языка. Это может быть выражено добавлением соответствующего количества правил по одному на каждый возможный символ. Символ * используется как метасимвол для обозначения пустой цепочки. Метасимвол | обозначает, что данная формула является сокращенной записью нескольких формул с одинаковыми левыми частями и различными цепочками в правой части (т. е. возможен один из разделенных этим символом вариантов). Пара метасимволов [ ] используется для обозначения того, что находящаяся между ними цепочка может содержаться, а может и не содержаться в правой части формулы. Пара { } означает, что содержащаяся между ними цепочка может повторяться ноль или более раз.

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

Примечание

Обратите внимание, что в документации Informix, используются синтаксические диаграммы. Выбранный нами вариант расширенных БНФ проще для набора и чаще используется в общедоступной литературе.

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