Определение грамматики

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

Нетерминалы –это конструкции языка.

Такие элементы как дуб, заслоняет играющие роль слов – символов языка – называются терминальными (основными) символами, или просто терминалами.

Грамматика может содержать любое количество терминалов. В языках программирования терминалами являются используемые в них слова и символы, BEGIN, DO, + и т.д. Терминалы – это символы предложений порождаемого языка.

Правила грамматики (продукции) показывают как конструкция языка строится из других конструкций и символов.

Простейший вид продукции:

< один нетерминал>® любая конечная цепочка из терминалов и нетерминалов.

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

Пример такого правила: <A>® e.

Правило с пустой правой частью будем называть эпсилон-правилом. Грамматика может содержать любое количество правил.

Пример: продукция языка программирования:

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

Один из нетерминалов выделяется как начальный нетерминал или начальный символ (или аксиома), с которого должны начинаться выводы цепочек языка. Для естественных языков таким нетерминалом может быть <предложение>, для языков программирования - <программа>. Один и тот же язык может быть определен бесконечным множеством различных грамматик.

Таким образом, порождающая грамматика Хомского определяется как четверка:

G= (Т, N, S, R), где

Т – конечное непустое множество символов (терминалов),

N – конечное непустое множество символов (нетерминалов),

причем ТÇN= Æ,

S – начальный символ грамматики (выделенный элемент нетерминального словаря),

R – конечное непустое множество продукций, каждая из которых имеет вид a®b. Здесь a и b – это цепочки из символов объединенного словаря, ® – разделитель правила на правую и левую части.

Ограничения:

1. Символ «®» не входит в объединенный словарь U= ТÈN,

2. a не должна быть пустой цепочкой.

Пример: G₀= (Т₀, N₀, S, R₀), Т₀= {a, b, c}, N₀= {A, B, S},

R₀: S®caS

bA®abc

aS®bAc

bAB®ab

В литературе часто используется еще один способ записи грамматики, называемый формой Бекуса-Наура или БНФ. В этих обозначениях стрелка заменяется знаком ::=, за которым может следовать любое количество правых частей, разделенных вертикальной чертой. Обычно нетерминалы заключаются в угловые скобки или выделяются другим шрифтом. БНФ были впервые применены при описании языка программирования в сообщении об АЛГОЛе-60.