Определение 1.3.1. Формальной порождающей грамматикой называется четверка G = <N, T, P, S>,

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

T – конечное непустое множество символов, называемое терминальным (основным) словарем грамматики G; TN =, V = TN – объединенный словарь грамматики G, элементы множества Т называют терминальными символами (терминами);

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

P – конечное множество правил грамматики, т.е. цепочек вида  и называемых так же правилами подстановки или продукциями, при этом ,  — цепочки в словаре V = TN и (TN)*N(TN)*,  (NT)*. Конечное двуместное

отношение  интерпретируется как «заменить»  на  «или подставить  вместо ».

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

В дальнейшем элементы из нетерминального словаря N будем обозначать прописными латинскими буквами А, В, С,…, элементы из Т (терминальные символы) – строчными латинскими буквами a, b, c, …, произвольные цепочки – греческими буквами , , …

Будем говорить, что цепочка  непосредственно выводима из цепочки  в грамматике G(), если =₁₂, =₁₂ и в множестве правил подстановки Р найдется правило .

Будем говорить, что цепочка  выводима из цепочки  в грамматике G(), если найдется последовательность цепочек =₀, ₁,…, _n= такая, что цепочка _i+1 непосредственно выводима в грамматике G из цепочки _i, т.е. _i(_ii+1) при i = 0, 1, … n-1, либо  = . Всюду  — произвольная цепочка, т.е. _i (NT)*.

Отношение  называется транзитивным замыканием, а последовательность цепочек ₀, ₁,…,_n – выводом цепочки _n из цепочки ₀ в грамматике G.

Определение 1.3.2. Множество всех цепочек терминальных символов, выводимых из аксиомы грамматики, называется языком, порождаемым этой грамматикой, т.е. L(G)={x | Sx, xT*}.

Пример 1.3.1.

Рассмотрим грамматику G = <N, T, P, S> у которой:

N = {I},

T = {a, b, c, V, &, ¬, (, )},

S = {I},

P = {      I(IVI)

               I(I&I)

               I¬I

               Ia

               Ib

               Ic}

Эта грамматика описывает язык булевых формул с переменными a, b, c и логическими функциями V, &, ¬. Примером вывода в этой грамматике является вывод цепочки ((a&b)Vc):

I (IVI) ((I&I)VI) (a&I)VI) ((a&b)VI) ((a&b)Vc).

Пример 1.3.2. Язык aⁿ bⁿ aⁿ порождается следующей грамматикой G=<N, T, P, S>, у которой: N={I, A, B, C, D}, T={a, b, c}, S = {I},

P = {      IABA

               BABCA

               Bb

               bCbb

               ACDC

               DCDA

               DACA

               Aa}

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

I ABAAABCAAaABCAAaaBCAAaabCAAaabbAA

aabbaAaabbaa.

Необходимо отметить, что хотя порождающая грамматика и описывает процесс порождения цепочек языка L(G), но описание это не является алгоритмическим – в грамматике отсутствуют одно из главных свойств алгоритма — детерминированность, т.е. не фиксируется конкретный порядок применения правил подстановки грамматики. За счет этого обеспечивается компактность описания языка.

Порождающая грамматика в том виде, как она была определена выше, является мощным описательным средством, но все еще очень общего характера. Практическое применение грамматик связанно с решением проблемы распознавания. Проблема распознавания разрешима, если существует такой алгоритм, который за конечное число шагов дает ответ на вопрос, принадлежит ли произвольная цепочка над основным словарем грамматики языку, порождаемому этой грамматикой. Если такой алгоритм существует, то язык называется распознаваемым. Если к тому же число шагов алгоритма распознавания зависит от длины цепочки и может быть оценено до выполнения, язык называется легко распознаваемым [8]. В противном случае не имеет смысла вести речь о построении транслятора для нераспознаваемого языка программирования. Поэтому на практике рассматриваются такие частные классы порождающих грамматик, которые соответствуют распознаваемым, а в большинстве случаев и легко распознаваемым языкам.