1. Грамматики

Грамматики образуют наиболее важный класс генераторов языка. Грамматика – это математическая система, определяющая вид языка. Одновременно она является устройством, которое придаёт цепочкам (предложениям) языка полезную структуру. Мы будем пользоваться формализмом грамматик Хомского.

В грамматике, определяющей язык L, используются два конечных непересекающихся множества символов – множество нетерминальных символов, которое обычно обозначается буквой , и множество терминальных символов, обозначаемое . Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для порождения слов языка L определённым способом.

Сердцевину грамматики составляет конечное множество Р правил образования, которое описывает процесс порождения цепочек языка. Правило – это просто пара цепочек или элемент множества, иначе говоря, ()^*  ()^*  ()^. Первой компонентой правила является любая цепочка, содержащая хотя бы один нетерминал, а второй компонентой – любая цепочка.

Пример.

Например, правилом может быть пара (AB, CDE). Если уже установлено, что некоторая цепочка  порождается грамматикой и  содержит AB, т.е. левую часть этого правила, в качестве своей подцепочки, то можно образовать новую цепочку , заменив одно вхождение AB в  на CDE.

Язык, определяемый грамматикой, - это множество цепочек, которые строятся только из терминальных символов и выводятся, начиная с одной особой цепочки, состоящей из одного выделенного символа, обычно обозначаемого S.

Соглашение. Правило (, ) будем записывать .

Определение.

Грамматикой называется четвёрка G=(N, Σ, P, S),

где

N – конечное множество нетерминальных символов или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);

 - непересекающееся с N конечное множество терминальных символов (терминалов);

P – конечное подмножество множества ()^*()^*()^ , элемент (, ) множества P называется правилом (или продукцией) и записывается ;

S – выделенный символ из N, называемый начальным (исходным) символом.

Примером грамматики служит четвёрка G₁ = ({A, S}, {0, 1}, P, S), где P состоит из правил

S→0A1

0A→00A1

A→C.

Нетерминальными символами являются А и S, а терминальными - 1 и 0.

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании особого рода цепочек, называемых вводимыми цепочками грамматики G=(N,Σ,P,S), где

1. S - вводимая цепочка;

2. если αβγ – выводимая цепочка и β→ содержится в Р, то  – тоже выводимая цепочка.

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

Терминология.

Пусть G=(N, Σ, P, S) – грамматика. Отношение _G на множестве ()^* (φ_GΨ означает Ψ, непосредственно выводимая из φ ) и практикуется: если αβγ – цепочка из ()^* и β→δ – правило из Р, то αβγ _G αδγ.

Транзитивное замыкание отношения _G обозначим через _G+ и трактуется – Ψ, выводимая из φ нетривиальным образом.

Рефлексивное и транзитивное замыкание отношения _G (_G*) φ_G* Ψ, Ψ, выводимая из φ.

Далее, если ясно, о какой грамматике идёт речь, то индекс G будет опускаться.

Таким образом, L(G) = {w | w^,S^w} через будем обозначатьk-ю степень отношения . Иначе говоря , если существует, состоящая изk+1 цепочек, для которых при 1i  к и =. Эта последовательность цепочек называется выводом длиныk цепочки  из цепочки  в грамматике G.

Отметим, что ^* тогда и только тогда, когда  для некоторогоi≥0, и ⁺ тогда и только тогда, когда  для некоторогоi≥1.

Пример.

Рассмотрим грамматику G₁ из ранее приведённого примера

S.

На первом шаге S заменяется на А01 в соответствии с правилом S→A01.

На втором шаге 0A заменяется на 00A1.

На третьем шаге A заменяется на e.

Можно сказать, что S³

S⁺

S^*,

и что 0011 принадлежит языку L(G₁).

Соглашение: ₁

₂

…….

_n

обозначим ₁ ₂ …._n .

Кроме того, примем ещё следующие соглашения относительно символов и цепочек, связанных с грамматикой:

1. a, b ,c, d и цифры 0,1,2,..,9 обозначают терминальные символы;

2. A, B, C, D, S обозначают нетерминалы, S – начальный символ;

3. U, V,...,Z обозначают либо нетерминалы, либо терминалы;

4.   обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы;

5. u, v,...,z обозначают цепочки, состоящие только из терминалов.

Пример.

Пусть G₀ = ({E, T, F},{a, +, * (, )}, P, E), где P состоит из правил:

E→E+T | T

T→T*F | F

F→(E) | a.

Пример вывода в этой грамматике:

EE+T

T+T

F+T

a+T

a+T*F

a+F*F

a+a*F

a+a*a,

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