Формальное определение грамматики. Форма Бэкуса—Наура

Для полного формального определения грамматики кроме правил порождения цепочек языка необходимо задать также алфавит языка.

Формально грамматика G определяется как четверка G(VT,VN,P,S), где:

Множество V - VNuVT называют полным алфавитом грамматики G.

Рассмотрим множества VN и VT. Множество терминальных символов VT содержит символы, которые входят в алфавит языка, порождаемого грамматикой. Как правило, символы из множества VT встречаются только в цепочках правых частей правил, если же они встречаются в цепочке левой части правила, то обязаны быть и в цепочке правой его части. Множество нетерминальных символов VN содержит символы, которые определяют слова, понятия, конструкции языка. Каждый символ этого множества может встречаться в цепочках как левой, так и правой частей правил грамматики, но он обязан хотя бы один раз быть в левой части хотя бы одного правила. Правила грамматики строятся так, чтобы в левой части каждого правила был хотя бы один нетерминальный символ.

Эти два множества не пересекаются: каждый символ может быть либо терминальным, либо нетерминальным. Ни один символ в алфавите грамматики не может быть нетерминальным и терминальным одновременно. Целевой символ грамматики — это всегда нетерминальный символ.

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые правые части, вида: а->β, a->β₂, ... a->β_n. Тогда эти правила объединяют вместе и записывают в виде: a->β₁|β₂|...|β_n • Одной строке в такой записи соответствует сразу п правил.

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

Рассмотрим составляющие элементы грамматики G:

--- множество терминальных символов VT содержит двенадцать элементов: десять десятичных цифр и два знака;

--- множество нетерминальных символов VN содержит три элемента: символы <число>, <чс> и <цифра>;

--- множество правил содержит 15 правил, которые записаны в три строки (то есть имеются только три различных правых части правил);

--- целевым символом грамматики является символ <число>.

Следует отметить, что символ <чс> — это бессмысленное сочетание букв русского языка, но это обычный нетерминальный символ грамматики, такой же, как и два других. Названия нетерминальных символов не обязаны быть осмысленными, это сделано просто для удобства понимания правил грамматики человеком. В принципе в любой грамматике можно полностью изменить имена всех нетерминальных символов, не меняя при этом языка, заданного грамматикой, — точно также, например, в программе на языке Pascal можно изменить имена идентификаторов, и при этом не изменится смысл программы.

Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.

Вот, например, та же самая грамматика для целых десятичных чисел со знаком, в которой нетерминальные символы обозначены большими латинскими буквами (далее это будет часто применяться в примерах):

Здесь изменилось только множество нетерминальных символов. Теперь VN= {S,T,F}. Язык, заданный грамматикой, не изменился — грамматики G и G' эквивалентны.