Старый дуб заслоняет старый дом

Дерево представляет собой синтаксическую структуру предложения. Из него видно, что результирующая цепочка не зависит от порядка, в котором делались замены промежуточных элементов. Элементы грамматики, такие как подлежащее, существительное и другие, называются вспомогательными или нетерминальными символами. В контекстно-свободной грамматике может быть любое конечное число нетерминальных символов. Символы - дуб, дом, старый, заслоняет в рассмотренной грамматике играют роль слов из словаря языка и называются терминальными (основными) символами или просто терминалами. Может существовать любое конечное число терминалов в контекстно-свободной грамматике. В языках программирования терминальными являются используемые в них слова и символы: DO, IF, + и др.

В общем виде правила грамматики можно записать:

нетерминал ® любая конечная цепочка терминальных и нетерминальных символов или одних терминалов.

Цепочка справа от стрелки может быть пустой, что обозначается в

грамматике следующим образом: < F> ® e. Такое правило называется эпсилон - правилом.

В отдельных языках программированияправилавыглядят в соответствии с записью:

< оператор > ® IF < логическое выражение > THEN < оператор >

Один из нетерминальных символов всегда выделяется в качестве начального. Его называют аксиомой грамматики. С него всегда должен начинаться вывод цепочек языка.

Контекстно-свободная грамматика (КСГ) задается:

конечным множеством терминалов; - конечным множеством нетерминалов; конечным множеством правил вида < A > ® a, где А - нетерминал, a - цепочка терминальных и нетерминальных символов (возможно пустая) или цепочка терминальных символов; нетерминал А называется левой частью правила, а a - правой; одним нетерминальным символом, выделенным в качестве начального (аксиомой грамматики).

Проанализируем грамматику, правила которой имеют вид:

1. S ® a A b S 2. S ® b

3. A ® A S c 4. A ® e

Из записи следует: { A,S } - словарь нетерминальных символов;

{a, b, c} - словарь терминальных символов; e - пустая цепочка и, следовательно, не является символом грамматики. Правило 4 можно записать в виде А ®. Аксиома грамматики – символ S.

Рассмотрим еще один способ записи правил формальной грамматики, называемый формой Бэкуса-Наура:

1. <S>:= a <A> b <S> | b 2. <A>:= <A> <S> c | e