Лекция №3

1.3. Грамматики и распознаватели

1.3.1. Порождающая грамматика

Определение 1. Формальной порождающей грамматикой называется грамматика, определяемая как

G = <T, N, P, S>,

где T – конечное непустое множество символов, называемое терминальным (основным) словарем грамматики G. Элементы множества T называют терминальными символами (терминалы, лексемы);

N – конечное непустое множество символов, называемое нетерминальным (вспомогательным) словарем грамматики G. V = T  N – объединенный словарь грамматики G. Элементы множества N называют нетерминальными символами (нетерминалы). Каждый символ в грамматике может быть либо терминальным, либо нетерминальным, но не может быть одновременно и тем и другим, т. е. T  N = ;

S – начальный символ (аксиома) грамматики G, S  N и обозначает главный нетерминал (цель) грамматики G;

P – конечное множество правил грамматики, т. е. цепочек вида    и называемых также правилами подстановки или продукциями, при этом  и  – цепочки в словаре V, где   V⁺, а   V^. Конечное двуместное отношение  интерпретируется как «заменить»  на  или «подставить  вместо ».

Множество правил подстановки P называют также схемой грамматики. Цепочка, стоящая в левой части правила грамматики, обязательно содержит хотя бы один нетерминальный символ. В правой же части правила в общем случае может стоять произвольная цепочка из терминальных и нетерминальных символов, включая и пустую цепочку , но при этом нетерминальный символ из правой части должен быть хотя бы один раз в левой части хотя бы одного правила.

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части:   ₁,   ₂, . . . ,   _n, тогда эти правила объединяются и записываются в виде   ₁₂…_n. Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса-Наура (БНФ), если нетерминальные символы заключить в  и принять, что знаки ::= по определению есть и  эквивалентны. Возможно обозначение нетерминалов прописными латинскими буквами.

Для того чтобы определение лучше отложилось, рассмотрим следующий пример.

Пример 1.1.

Грамматика G определяет язык целых десятичных чисел со знаком.

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, –};

N = {<число>, <чс>, <цифра>}; S = <число>;

P:

<число>  <чс>+<чс>–<чс>

<чс>  <цифра><чс><цифра>

<цифра>  0123456789

Совокупность правил начинается с S.

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

– множество терминальных символов T (терминальный словарь) содержит двенадцать элементов: десять десятичных цифр и два знака;

– нетерминальный словарь N содержит три элемента: нетерминальные символы число, чс и цифра;

– множество правил P содержит 15 правил, которые записаны в три строки, т. е. имеется только три различные левые части правил;

– целевым символом грамматики является символ число.

Примененный символ чс – это бессмысленное сочетание букв русского языка, но это приемлемый нетерминальный символ грамматики, такой же, как и два других. Названия нетерминальных символов не обязаны быть осмысленными. Осмысленными они делаются для лучшего понимания правил грамматики человеком. В принципе в любой грамматике можно полностью изменить имена всех нетерминальных символов, не меняя при этом языка, заданного грамматикой. Для терминальных символов это недопустимо. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.

Например, для языка Примера 1.1 запишем грамматику G следующим образом:

T = T, N = {S, T, F}

P:

S  T+ T– T

T  FTF

F  0123456789.

Здесь изменилось только множество нетерминальных символов: N = {S, T, F}. Язык, заданный грамматикой, не изменился, т. е. G и G эквивалентны. Используя грамматику G, попробуем записать какое-либо конкретное число, например (– 157).

S  – T  – TF  – T7  – TF7  – T57  – F57  – F57  – 157.

Такая запись называется выводом цепочки числа (– 157) главного нетерминального символа (цели) грамматики G. Чтобы показать, что это вывод цепочки используются двойные стрелки.

Особенность рассмотренных выше формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил (15 правил в примере определяют множество целых десятичных чисел от –  до + ). Такая возможность пользоваться конечным набором правил достигается за счет рекурсии, которая заключается в том, что нетерминальный символ определяется сам через себя. Рекурсия может быть либо непосредственной (явной) – когда символ определяется сам через себя в одном правиле, либо косвенной (неявной) – когда рекурсия происходит через цепочку правил.

В рассмотренном примере есть явная рекурсия:

в G чс  чсцифра, в G T  TF.

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

В грамматике G такое правило чс  цифра, а в грамматике G T  F.

Пример 1.2.

Язык aⁿbⁿaⁿ порождается следующей грамматикой:

T = {a, b, d}; N = {I, A, B, C, D}; S = {I}

P:

1) I  ABA;

2) B  ABCA;

3) B  b;

4) bC  bb;

5) AC  DC;

6) DC  DA;

7) DA  CA;

8) A  a.

Примером вывода в данной грамматике для n = 2, т. е. цепочки a²b²a², является вывод:

I  ABA  AABCAA  aABCAA  aaBCAA  aabCAA  aabbAA

  aabbaA  aabbaa = a²b²a².

Цифрами над стрелками указаны правила, используемые на каждом шаге вывода цепочки.

Вопрос слушателям. Как будет выглядеть вывод для цепочки при n = 3? Как надо изменить совокупность правил Примера 1.2, чтобы грамматика порождала язык aⁿbⁿdⁿ?