Формальное определение грамматики

Грамматики

Для нас наибольший интерес представляет одна из систем генерации языков – грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков программирования при помощи БНФ – формы Бэкуса­Наура,которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила <L> ® <L> и <L> ® <E>записаны в символической форме, и символ <L> соответствует синтаксическому понятию "список", а символ <E> - "элемент списка", то их можно представить в форме Наура-Бэкуса так:

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

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

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

Декартовым произведением A ´ B множеств A и B называется множество {(a,b) | a Î A, b Î B}.

Порождающая грамматикаG - это четверка (VT, VN, P, S), где

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

VN - алфавит нетерминальных символов(нетерминалов), не пересекающийся с VT, то есть множество таких символов, которые требуют определения в грамматике;

P - это конечное подмножество множества (VT È VN)⁺ ´ (VT È VN)^*;

Р является множеством правил или продукций (то есть способов определения нетерминальных символов) вида {a ® b } (из некоторой цепочки a следует цепочка b), где b образована из терминальных или нетерминальных символов, а также может быть пустой: b Î ( VTÈVN )*, а a - цепочка, которая в общем случае содержит как терминалы, так и нетерминалы, но в ней обязательно должен быть один нетерминал.

Элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b,

S - начальный символ (цель)грамматики, нетерминал, S Î VN.

Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из VT^* и, наконец, малые греческие буквы для обозначения цепочек из ( VTÈVN )*.

Для записи правил вывода с одинаковыми левыми частями

a ® b₁ a ® b₂ ... a ® b_n

будем пользоваться сокращенной записью

a ® b₁ | b₂ |...| b_n.

Каждое b_i , i= 1, 2, ... ,n , будем называть альтернативойправила вывода из цепочки a.