2.3 Грамматики

В п. 2.2 язык был определен как некоторое множество цепочек в заданном алфавите S. Очевидно, что такое определение не конструктивно, так как ничего не говорит о свойствах самого языка. В теории формальных языков имеется несколько способов более детального описания языков.

Первый способ основан на использовании грамматик. Грамматика -это система правил, позволяющая строить "правильные" или допустимые цепочки языка.

Определение. Грамматикой называется четверка G=(N,S,P,S), где N- конечное множество нетерминальных символов;

S- конечное множество терминальных символов, причем ;

P- конечное подмножество множества . Элементами этого подмножества являются пары , называемые правилами грамматики (правилами подстановки, продукциями). Обычно правила записываются в форме ;

S- выделенный из множества N символ, называемый начальным символом. ¨

Пример 2.9. G₁= ( {S,A},{0,1}, {S® 0A1, 0A® 00A1, A® e}, S).

Здесь нетерминальными символами являются S и A , терминальными

0 и 1, е - обозначает пустую цепочку, а множество Р состоит из правил:

S® 0A1;

0A® 00A1;

A® e.

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании цепочек, называемых выводимыми цепочками грамматики G, посредством следующих утверждений :

а) S - выводимая цепочка;

б) если - выводимая цепочка и правило , то тоже выводимая цепочка.

Выводимая цепочка грамматики G, состоящая только из терминальных символов, называется терминальной цепочкой, порождаемой грамматикой G.

Язык, порождаемый грамматикой G (обозначается: L(G)), определяется как множество терминальных цепочек, которые могут быть выведены из начального символа S грамматики G.

Пример 2.10. Приведем примеры выводов для грамматики G из примера 2.9:

SÞ 0A1Þ 00A11Þ 0011;

SÞ 0A1Þ 01;

SÞ 0A1Þ 00A11Þ 000A111Þ 000111.

Эта грамматика порождает цепочки, состоящие из одинакового количества подряд идущих нулей и единиц. Использованный в примере символ " " обозначает бинарное отношение между цепочками, участвующими в выводе, и соответствует одному шагу вывода.

Определение. Пусть задана грамматика . Определим отношение на множестве следующим образом:

если abg - цепочка из (N ÈS) ^* и (b®s)ÎP, то abgÞasg. ¨

Если мы имеем ,то говорят, что y непосредственно выводима из j.

Над отношением обычным образом вводятся операции нахождения k-й степени отношения , транзитивного замыкания и рефлексивного и транзитивного замыкания :

означает, что y выводима из j за k шагов, т.е.

;

j Þ⁺y , читается как “ y выводима из j нетривиальным образом” (т.е. за некоторое число шагов, отличное от нуля);

читается как "y выводима из j" (за некоторое число шагов).

Для рассмотренных в примере выводов будут справедливы следующие утверждения:

С использованием введенных определений язык L(G) можно определить более формально:

Соглашения об обозначениях:

1. Для обозначения терминальных символов преимущественно будут использоваться символы - a,b,c,d,0...9 и спецсимволы;

для нетерминальных -S,A,B,C,...;

для обозначения цепочек, состоящих из терминалов и нетерминалов,- .

2. Нетерминальный символ может обозначать некоторое синтаксическое понятие и состоять из нескольких символов или слов, например: <переменная>, <целое число> и т.п.

3. Если грамматика содержит несколько правил с одинаковой

левой частью, типа то можно использовать запись в одну строку:

Пример 2.11. Пусть

G=({<цифра>},{0,1,...,9},{<цифра> 0|1|....|9},<цифра>),

Очевидно, что L(G) - это множество, состоящее из десяти цифр.

Пример 2.12: Пусть G=({E,T,F},{a,+,*,(,)},P,E), где

P:

Пример вывода:

E Þ E+T Þ T+T ÞF+T Þ a+T Þ a+T*F Þ a+F*F Þ a+a*F Þ a+a*a.

Очевидно, что язык L(G) представляет собой множество арифметических выражений, построенных из терминальных символов: a,+,*,( и ).

Пример 2.13. Пусть G определяется правилами:

В этой грамматике возможен вывод:

Эта грамматика порождает язык:

.

Классификация грамматик и языков. Грамматики классифицируют по виду их правил. Выделяют четыре основных класса грамматик (классификация Холмского):

1. Грамматика G называется праволинейной, если каждое правило из множества P имеет вид:

_.

Частным случаем праволинейных грамматик являются регулярные

грамматики, имеющие правила вида

_.

Эти грамматики имеют большое прикладное значение, как в разработке языков, так и в конструировании компиляторов.

2. Грамматика G называется контекстно-свободной (КС), если каждое правило из множества Р имеет вид

.

3. Грамматика G называется контекстно-зависимой (КЗ), если каждое правило из множества P имеет вид

a®b, где a,bÎ(NÈS) ^* и |a| £ | b| .

4. Грамматика, не удовлетворяющая ни одному из ограничений (1-3), называется грамматикой общего вида.

Заметим, что согласно этим ограничениям, праволинейные и регулярные грамматики входят в класс КС -грамматик. В литературе для обозначения этих классов грамматик используют также следующие названия:

грамматика общего вида-грамматика типа-0;

КЗ - грамматика -грамматика типа-1;

КС-грамматика-грамматика типа-2;

регулярная грамматика-грамматика типа-3.

Язык, порождаемый грамматикой типа - k, называется языком

типа - k (k=0,1,2,3). В прикладных задачах разработки языков программирования и проблемно-ориентированных языков наибольшее применение находят КС-грамматики. Это объясняется тем,что соответствующие языки имеют сравнительно простые синтаксисы и для них могут быть построены достаточно эффективные языковые процессоры(компиляторы, интерпретаторы и т.п.).