Source: http://public.uic.rsu.ru/~skritski/scourses/Transl

3. ГРАММАТИКИ

3.1. Порождающие грамматики Хомского

Порождающие грамматики были введены Н. Хомским в конце 1950-х годов как средство описания формальных языков (точнее, как средство описания формальных моделей естественных языков). Хомским определена так называемая "иерархия" классов грамматик и языков по степени сложности - грамматики и языки "типа 0, 1, 2 и 3".

3.1.1. Грамматики общего вида

Грамматикой общего вида (типа 0) называется набор G = (N,T,P,S), где
N - алфавит нетерминальных символов; будем обозначать их большими латинскими буквами;
T - алфавит терминальных символов, T З N = Ж ; терминальные символы будем обозначать малыми буквами из начала латинского алфавита;
P - конечное множество правил (или продукций); правило имеет вид a ® b, где a,b О (T И N)^*, причем a  содержит хоть один нетерминальный символ;
S - начальный нетерминальный символ, S О N.

Символы объединенного алфавита V = T И N  будем обозначать малыми буквами из конца латинского алфавита (u, v, w, ...).

Основным понятием грамматик является понятие вывода и выводимости. Если в грамматике есть правило a ® b, то из цепочки gad  за один шаг выводима цепочка gbd  (говорят также непосредственно выводима). Это отношение обозначается gad ®_G gbd. Отношение выводимости за 0 или более шагов обозначается a ®_G^* b  (рефлексивно-транзитивное замыкание отношения ®_G) и называется просто отношением выводимости. Последовательность цепочек a₀ ®_G a₁ ®_G ... ®_G a_n называется выводом длины n і 0. Вывод также будем обозначать иногда a ®_G^* b . В случае, когда понятно, в какой грамматике рассматривается вывод, индекс _G можно опускать.

Языком, порождаемым грамматикой G называется множество терминальных цепочек, выводимых из S, т.е. множество L(G) = {a | a О T^*, S ®^*a}. Класс языков, порождаемых грамматиками общего вида называется классом языков типа 0.

Пример 3.1. Грамматика, порождающая арифметические выражения из п. 2.6 (пример 2.4), имеет терминальный алфавит T = {i,n,(,),+,*}, нетерминальный алфавит N={E,T,F}, главный нетерминальный символ E и правила

Выводом в этой грамматике является, например, последовательность

E ® E+T ® E+T*F ® E+T*(E) ® T+T*(E) ® 
F+T*(E) ® i+T*(E) ® i+T*(E+T) ® 
i+T*(T+T) ® i+F*(T+T) ® i+F*(F+T) ® i+F*(F+F) ®   
i+n*(F+F) ® i+n*(i+F) ® i+n*(i+n)
Ђ

Очевидно, что порождающая грамматика G типа 0 является недетерминированным алгоритмом (исчислением), множеством результатов которой является L(G). Поэтому язык L(G) - рекурсивно перечислимое множество. На самом деле справедливо следующее утверждение.

Т е о р е м а  3.1. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.

Доказательство. Благодаря только что сказанному и утверждению 1.9, достаточно доказать, что множество L-выходов любой машины Тьюринга является языком, порождаемым некоторой грамматикой типа 0.

Пусть задано машина Тьюринга M = (S,Q,P,q₀,q_f). Построим грамматику G = (N,T,P',S), у которой N = {S, X,Y,Z,W}И Q, T = {[,]}И S, а P' определяется по P следующим образом:

• для S включается правило S ® [q₀L], создающее начальную конфигурацию машины с пустой лентой, ограниченную прямыми скобками; пользуясь этими скобками, правила для  q имитируют работу машины (ср. с формальным определением отношения перехода для машины Тьюринга в п. 1.2.4),
• для правила машины (q,a) ® (q',a',N) - правило грамматики qa ® q'a',
  для правила (q,a) ® (q',a',L) - правила грамматики bqa ® q'ba' для всех b из S и правило [qa ® [q'La',
  для правила (q,a) ® (q',a',R) - правила грамматики qab ® q'ba' для всех b из S и правило qa] ® a'q'L],
• для q_f  включаются правила грамматики, обеспечивающие сдвиг q_f  к левой границе конфигурации: 
  aq_f  ® q_f a  для всех a из S,
  [q_f  ® [X,
• для X, Y, Z и W включаются правила грамматики:
  XL ® X  (X уничтожает все L, примыкающие к левой границе),
  Xa ® Ya для всех a из T, не равных L и [,
  Ya ® aY для всех a из S  (Y перемещается к правой скобке и уничтожает её),
  Y] ® Z,
  LZ ® Z  (Z уничтожает все L, примыкающие к правой границе),
  aZ ® W для всех a из S, не равных L и ],
  aW ® Wa для всех a из S  (W перемещается к левой скобке и уничтожает её и себя),
  [W ® e .

Так как в каждой цепочке вывода из S содержится не более одного нетерминального символа, правила для q в точности имитируют поведение машины, а правила для X, Y, Z и W  применяются однозначно и оставляют точно L-выход машины.
Ђ

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

Грамматики G и G' называются эквивалентными, если они порождают один и тот же язык, т.е. L(G) = L(G'). Ниже мы докажем, что грамматика (1) из примера 3.1 эквивалентна грамматике

Грамматики общего вида могут порождать языки, которые нельзя определить регулярными уравнениями. 

Пример 3.2. Язык L = {aⁿbⁿcⁿ | n > 0} порождается грамматикой с правилами

Для вывода терминальной цепочки здесь можно применять правила в любом порядке, только нужно обязательно применить правило S ® aBC (для фиксации числа n), а правило bC ® bc применять только после того, как справа от C не останется ни одного B (иначе этот B не сможет замениться на b и вывод не завершится терминальной цепочкой).
Ђ

3.1.2. Контекстно-зависимые грамматики

Контекстно-зависимой (или типа 1) называется грамматика с правилами вида a ® b, где |a | Ј |b |. Благодаря этому неравенству эти грамматики называются ещё неукорачивающими. Грамматика (3) из примера 3.2 является неукорачивающей. Язык, порождаемый контекстно-зависимой грамматикой, называется также контекстно-зависимым (или типа 1). Очевидно, что такой язык не содержит e.

Т е о р е м а  3.2.  Контекстно-зависимые языки рекурсивны.

Доказательство. Пусть задана неукорачивающая грамматика G и произвольная цепочка a О T ⁺. Чтобы проверить, принадлежит ли a языку L(G), достаточно построить множество всех цепочек из V ⁺, не превосходящих по длине a, и построить из этих цепочек последовательности, в которых цепочки не повторяются, упорядочены по длине (каждая следующая не короче предыдущей) и первая цепочка всегда S, а последняя - a. Таких последовательностей конечное множество. Остаётся проверить каждую из них, не является ли она выводом в G. Такая проверка завершается за конечное число шагов. Если вывод найден, то a О L(G), в противном случае - нет.
Ђ

Отсюда следует, что любой рекурсивно перечислимый, но нерекурсивный язык (например, множество программ самоприменимых машин Тьюринга) является языком типа 0, но не языком типа 1.

Контекстно-зависимые грамматики содержат важный подкласс НС-грамматик. НС-грамматикой (или грамматикой непосредственно-составляющих) называется грамматика, правила которой имеют вид aAb ® agb, где A О N, a, b О V^*, g О V ⁺. Цепочки a и b  задают контекст, в котором A можно заменять на g. Языки, порождаемые НС-грамматиками, называются НС-языками.

Пример 3.3. НС-грамматикой является грамматика, полученная из грамматики (3) примера 3.2 заменой правила CB ® BC совокупностью правил

CB ® VB,  VB ® VW,  VW ® BW,  BW ® BC.

Эта грамматика порождает тот же язык {aⁿbⁿcⁿ | n > 0}.
Ђ

Т е о р е м а  3.3. Контекстно-зависимые языки являются НС-языками (т.е. эти классы языков совпадают).

Доказательство состоит в указании способа преобразования произвольной контекстно-зависимой грамматики в эквивалентную НС-грамматику. Этот способ подобен тому, который был использован в примере 3.3. Но более подробно мы это доказательство не рассматриваем.
Ђ

3.1.3. Контекстно-свободные грамматики

КС-грамматикой (или контекстно-свободной грамматикой и грамматикой типа 2) называется грамматика с правилами вида A ® a, где A О N, a О V^*. Язык, порождаемый КС-грамматикой, называется КС-языком (языком типа 2). 

Грамматика (1) из примера 3.1 является примером КС-грамматики. Другим примером является грамматика языка {aⁿbⁿ | n і 0}:

Пример 3.4. Язык {aⁿbⁿ | n і 0} порождается КС-грамматикой с правилами

S ® aSb,    S ® e.

Это вытекает из того, что все выводы в этой грамматике имеют вид

S ® aSb ® aaSbb ® ... ® aⁿSbⁿ ® aⁿbⁿ.
Ђ

Поскольку вывод из нетерминального символа теперь не зависит от контекста, правомерно также для каждого A О N рассматривать порождаемый им язык L_G(A) = {a | a О T^*, A ®^*a}. 

Каждому выводу в КС-грамматике можно сопоставить дерево вывода. Деревом вывода в грамматике G называется дерево следующего вида:

• корнем является нетерминальный символ;
• вершинами являются символы из V;
• если вершина A имеет непосредственных потомков X₁, ..., X_n (или e), то в грамматике есть правило A ® X₁...X_n (или A ® e). Порядок потомков совпадает с порядком символов в правиле.

Пример 3.5. Дерево вывода цепочки i+n*(i+n) в грамматике выражений (1) из примера 3.1

(См. также пример 2.5).
Ђ

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

E ® E+T ® T+T ® F+T ® i+T ®
i+T*F ® i+F*F ® i+n*F ® i+n*(E) ®
i+n*(E+T) ® i+n*(T+T) ® i+n*(F+T) ®
i+n*(i+T) ® i+n*(i+F) ® i+n*(i+n)

КС-грамматика G называется однозначной, если у каждой цепочки языка L(G) имеется только одно дерево вывода (и, следовательно, один левый вывод). КС-язык называется однозначным, если он порождается какой-нибудь однозначной грамматикой. Предыдущий язык выражений является однозначным.

Легко построить примеры неоднозначных грамматик. Достаточно, например, в произвольную КС-грамматику ввести правило A ® A для какого-нибудь нетерминального A. Сложнее найти неоднозначный язык. Справедлива следующая теорема (мы приводим её без доказательства).

Т е о р е м а  3.4. Проблемы однозначности КС-грамматик и КС-языков алгоритмически неразрешимы.
Ђ

Неоднозначные грамматики могут использоваться для описания и трансляции языков программирования.

Пример 3.6. Построим модель условного оператора языка Паскаль. Пусть терминальный символ a соответствует конструкции if <выражение> then, терминальный символ b соответствует конструкции else <оператор>, нетерминальный символ S соответствует конструкции <условный оператор>, а нетерминальный символ B - конструкции <возможный else>. Тогда типичная грамматика условного оператора (если отвлечься от других операторов) может быть промоделирована КС-грамматикой с правилами:

S ® aSB | e,  B ® b | e

Эта грамматика порождает язык {aⁿb^m | n і m і 0}, приписывая цепочке aab два дерева вывода

В Паскале принято соглашение о связывании else с ближайшим слева if, что соответствует дереву, изображённому слева. Этот язык однозначен, так как порождается однозначной грамматикой

S ® AX | e,  A ® aA | e,  X ® aXb | e,

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

Если в КС-грамматике имеется n правил A ® a_i (1Ј i Ј n) для нетерминального символа A, то их можно объединять в записи 

(4)            A ® a₁ | ... | a_n.

Каждой КС-грамматике G = (N,T,P,S) поставим в соответствие БНФ над алфавитом T и множеством переменных N, в которой каждому правилу вида (4) соответствует уравнение

A = a₁ | ... | a_n.

Если для A О N  в грамматике нет правила, соответствующее уравнение должно иметь вид A = Ж . Очевидно, что такое соответствие взаимнооднозначно. 

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

Т е о р е м а  3.5. Если N = {X₁,...,X_n}, то кортеж порождаемых грамматикой G языков (L(X₁),...,L(X_n)) является наименьшим решением соответствующей системы уравнений.
Ђ

Отсюда следует, в частности, что наименьшее решение регулярной системы уравнений есть кортеж КС-языков, и что {aⁿbⁿcⁿ | n > 0} - пример НС-языка, не являющегося контекстно-свободным.

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

Пример 3.7. Докажем эквивалентность грамматик (1) и (2). Соответствующие БНФ имеют вид

Первая система эквивалентна системе
E = T{+T}^*,  T = F{*F}^*,
или уравнению 
E = F{*F}^*{+F{*F}^*}^*,
в свою очередь эквивалентному уравнению
E = F{+F | *F}^*.
Последнее же эквивалентно (2').
Ђ

КС-грамматики "слегка не укладываются" в класс неукорачивающих грамматик - они допускают правила вида A ® e. Такие правила называются e -правилами. Очевидно, что КС-грамматика без e -правил является неукорачивающей и порождает рекурсивный язык. Попробуем, насколько это возможно, исключить из КС-грамматики e -правила.

A О N  называется исчезающим, если e О L(A). Множество всех исчезающих символов грамматики G обозначим E(G).

У т в е р ж д е н и е  3.1. Следующий алгоритм строит E(G).
Алгоритм строит возрастающую последовательность множеств
E⁽⁰⁾ Н E⁽¹⁾ Н ... Н E⁽ⁱ⁾ Н ... Н N.

Алгоритм 3.1 (построения множества исчезающих символов).

1. E⁽⁰⁾ = {A | P содержит правило A ® e}. Если e -правил нет, алгоритм завершается с E(G) = Ж .

2. E⁽ⁱ⁺¹⁾ = E⁽ⁱ⁾ И {A | P содержит правило A ® X₁...X_m, где все X_kО E⁽ⁱ⁾}. Если E⁽ⁱ⁺¹⁾ = E⁽ⁱ⁾, алгоритм завершается с E(G) = E⁽ⁱ⁾.

Доказательство. Нетрудно проверить, что A О E⁽ⁱ⁾ тогда и только тогда, когда существует дерево вывода e из A высоты не более i + 1. 

Т е о р е м а  3.6. КС-язык, не содержащий e, порождается некоторой КС-грамматикой, не содержащей e-правил.

Доказательство. Пусть G = (N,T,P,S) - КС-грамматика с e-правилами и e П L(G), т.е. S не является исчезающим символом. Следующий алгоритм преобразует грамматику в эквивалентную КС-грамматику  = (N,T,P',S), не содержащую e-правил.

Алгоритм 3.2 (устранения e-правил). P' получается из P следующими преобразованиями: 

1. Строится множество исчезающих символов E(G).

2. В P каждое правило вида A ® a₀A₁a₁...A_ma_m, где все A_iО E(G), а все a_j не содержат исчезающих символов, заменим множеством мощности 2^m правил вида A ® a₀X₁a₁...X_ma_m, где каждый X_i равен либо A_i, либо e. При этом для всех A сохранится язык L(A).

3. Удалим все e-правила. При этом для всех A язык L(A) теряет e, т.е. L_G' (A) = L_G(A) \ e.

Так как S П E(G), то L(G') = L(G).
Ђ

 Следствия.

1. После применения алгоритма устранения e-правил грамматика G преобразуется в грамматику G', такую что L(G') = L(G) \ e. Вытекает непосредственно из доказательства теоремы 3.6.

2. КС-языки рекурсивны. Действительно, если язык задан КС-грамматикой G и a = e, то a О L(G) Ы  S О E(G). Если a № e, то к G применяется алгоритм устранения e-правил и к полученной неукорачивающей грамматике G' применяется алгоритм проверки a О L(G').
   Ђ

Пример 3.8. Применим алгоритм устранения e-привил к грамматике G с правилами

S ® aSb,    S ® e.

Получим грамматику G' с правилами

S ® aSb,    S ® ab.

Так как L(G) = {aⁿbⁿ | n і 0}, то L(G') =  {aⁿbⁿ | n > 0}.
Ђ

Для КС-языков существуют намного более эффективные разрешающие алгоритмы, широко применяемые в практике трансляции языков программирования вместе с КС-грамматиками. Они рассматриваются в главе "Синтаксический анализ для КС-грамматик".

3.1.4. Эквивалентные преобразования КС-грамматик

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

Т е о р е м а  3.7. Проблема эквивалентности КС-грамматик алгоритмически неразрешима.
Ђ

Рассмотрим ещё некоторые полезные преобразования КС-грамматик.

Приведённые грамматики.

КС-грамматика G называется приведённой, если каждый её нетерминальный символ A используется в выводе какой-нибудь цепочки a О L(G), т.е. S ®^*bAg ®^*a.

Нетерминальный символ A КС-грамматики G называется продуктивным, если L(A) № Ж , и достижимым, если существует вывод S ®^*bAg. Очевидно, что грамматика является приведённой, если каждый её нетерминальный символ продуктивен и достижим.

Алгоритм 3.3 (построения множества продуктивных нетерминальных символов Pr(G)).
Алгоритм строит возрастающую последовательность множеств
Pr⁽⁰⁾ Н Pr⁽¹⁾ Н ... Н Pr⁽ⁱ⁾ Н ... Н N.

1. Pr⁽⁰⁾ = {A | P содержит правило A ® a, a О T^*}. Если таких правил нет, алгоритм завершается с Pr(G) = Ж .

2. Pr⁽ⁱ⁺¹⁾ = Pr⁽ⁱ⁾ И {A | P содержит правило A ® X₁...X_m, где все X_kО Pr⁽ⁱ⁾ И T}. Если Pr⁽ⁱ⁺¹⁾ = Pr⁽ⁱ⁾, алгоритм завершается с Pr(G) = Pr⁽ⁱ⁾.

Доказательство корректности алгоритма такое же как и для алгоритма 3.1.
Ђ

Определим отношение непосредственной достижимости Й : N ґ (N И T )

A Й X  Ы   существует правило A ® aXb, где a,b О (N И T )^*.

Очевидно, что рефлексивно-транзитивное замыкание этого отношения Й^* есть отношение достижимости:

A Й^*X  Ы   A ®^*aXb, где a,b О (N И T )^*.

Эти отношения рекурсивны.

Т е о р е м а  3.8. Следующий алгоритм преобразует произвольную КС-грамматику в эквивалентную приведённую грамматику.

Алгоритм 3.4 (преобразование КС-грамматики в приведённую форму).

1. Найти все непродуктивные символы и удалить все содержащие их правила.

2. Найти все недостижимые (из S) нетерминальные символы и удалить все правила для них.

Доказательство. Так как непродуктивные символы не используются в выводе терминальных цепочек, первый шаг сохраняет все непустые языки L(A). Все оставшиеся нетерминальные символы будут продуктивны. Аналогично, второй шаг сохраняет язык L(S) и все оставшиеся нетерминальные символы будут достижимы из S, т.е. алгоритм выполняет эквивалентное преобразование исходной грамматики. Остаётся проверить, что полученная грамматика не содержит непродуктивных символов. Если бы после второго шага некоторый продуктивный и достижимый символ A стал непродуктивным, это означало бы, что из него был достижим недостижимый из S нетерминальный символ, после удаления которого A и стал непродуктивным. Но тогда A сам был бы недостижимым. Полученное противоречие завершает доказательство.
Ђ

Замечание. Применение шагов алгоритма 3.4 в обратном порядке сохраняет язык L(G), но может привести к появлению недостижимых символов, как показывает следующий

Пример 3.9. Пусть грамматика имеет правила

S ® A | B,   A ® a,  B ® CD,  D ® d.

После удаления непродуктивных B и C останутся правила

S ® A,   A ® a,  D ® d,

а после удаления недостижимого (в новой грамматике) D останутся правила

S ® A,   A ® a.

Поскольку в исходной грамматике нет недостижимых символов, применение шагов алгоритма в обратном порядке даст эквивалентную, но неприведённую грамматику

S ® A,   A ® a,  D ® d.
Ђ

Устранение цепных правил.

Цепным называется правило вида A ® B, где A,B О N. Отношение непосредственной цепной зависимости Ї определим, как

A Ї B  Ы   есть правило A ® B и A,B О N.

Отношением цепной зависимости Ї^* назовём рефлексивно-транзитивное замыкание отношения Ї. Очевидно, что оба отношения рекурсивны.

Т е о р е м а  3.9. Для каждой КС-грамматики G следующий алгоритм строит эквивалентную КС-грамматику G' без цепных правил.

Алгоритм 3.5 (устранение цепных правил).

1. Строится отношение цепной зависимости Ї^* для G.

2. Для каждого A О N  в G' включаются все правила вида A ® a, где  A Ї^*B   и B ® a  - нецепное правило в G (в частности, включаются все нецепные правила для A). Очевидно, что L_G' (A) = L_G(A).

Доказательство очевидно.
Ђ

Пример 3.10. Устранение цепных правил в грамматике (1) даёт грамматику

3.1.5. Автоматные грамматики

А-грамматикой (автоматной грамматикой или грамматикой типа 3) называется КС-грамматика с правилами вида A ® aB или A ® e, где A,B О N, a О T. Порождаемый такой грамматикой язык называется А-языком (автоматным, типа 3).

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

Система уравнений, соответствующая А-грамматике, праволинейна. Поэтому А-языки регулярны. Обратное утверждение даёт следующая

Т е о р е м а  3.10. Каждый регулярный язык является А-языком.

Доказательство. Покажем индукцией по построению регулярных языков, что любой регулярный язык порождается некоторой А-грамматикой.

1) Язык Ж  порождается А-грамматикой с одним правилом S ® aS, где a - любой символ из T. Символ S в такой грамматике непродуктивен.

2) Язык {a}, где a О T, порождается А-грамматикой с двумя правилами S ® aA, A ® e.

3) Язык {e } порождается А-грамматикой с одним правилом S ® e.

Остальные регулярные языки получаются из этих с помощью операций объединения, произведения и итерации. Пусть языки L и M порождаются А-грамматиками G₁ = (N₁,T,P₁,S₁) и G₂ = (N₂,T,P₂,S₂), соответственно, причем N₁ З N₂ = Ж  (этого всегда можно добиться, переименовав нетерминальные символы). Пусть также правила для S₁ и S₂ имеют вид S₁ ® a₁ | ... | a_n, S₂ ® b₁ | ... | b_m.

4) Язык L И M порождается КС-грамматикой G = (N,T,P,S), где N = N₁ И N₂ И {S}, S П N₁ И N₂, P = P₁ И P₂ И {S ® S₁ | S₂}. Новые правила для S являются цепными. Устраняя их с помощью  алгоритма 3.5, получим правила S ® a₁ | ... | a_n | b₁ | ... | b_m. Полученная теперь грамматика является автоматной.

5) Язык LM порождается КС-грамматикой G = (N,T,P,S), где N = N₁ И N₂ И {S}, S П N₁ И N₂, P = P₁ И P₂ И {S ® S₁S₂}. Будем рассматривать эту грамматику как систему уравнений и умножим все уравнения из P₁ справа на S₂. Хотя полученная система уравнений и не регулярна, но оно имеет те же решения, что и исходная. Каждый символ A О N₁ входит в новые уравнения P₁' только в составе произведения AS₂, поэтому каждое такое произведение в P₁' и в правиле S ® S₁S₂ можно заменить соответствующей переменной A. Тогда все правила из P₁, кроме e-правил, останутся без изменений и в P₁', правило S ® S₁S₂ заменится на S ® S₁ (и может быть удалено, если в G в качестве главного нетерминального символа использовать не S, а S₁), а правилу A ® e  из P₁ в P₁' будет соответствовать правило A ® S₂. Устраняя такие цепные правила, получим вместо них правила A ® b₁ | ... | b_m. Таким образом, язык LM порождается А-грамматикой
G' = (N₁ И N₂,T,P₁" И P₂ И {A ® b₁ | ... | b_m  | правило A ® e  входит в P₁},S₁),
где P₁" получается из P₁ вычёркиванием e-правил.

6) Язык L^* порождается КС-грамматикой G = (N₁ И {S},T,P₁ И {S ® S₁S | e },S). Умножая все правила из P₁ справа на S, заменяя в правилах грамматики G каждое произведение AS, A О N₁, на A, так же, как в предыдущем случае получаем, что язык L^* порождается КС-грамматикой
G' = (N₁ И {S},T,P₁' И {S ® S₁ | e } И {A ®  S | правило A ® e  входит в P₁},S),
где P₁' получается из P₁ вычёркиванием e-правил. После исключения цепных правил с помощью алгоритма 3.5 получаем эквивалентную А-грамматику языка L^*:
G" = (N₁ И {S},T,P₁' И {S ® a₁ | ... | a_n | e } И {A ®  a₁ | ... | a_n  | правило A ® e  входит в P₁},S).
Ђ

Пример 3.11. В примере 2.1 была построена система уравнений, определяющая множество чисел:
R = SNFP
S = {+,-,e}
N = DD^*
D = {0,1,2,...,9}
F = .N  И e 
P = eSN  И e ,
из которой, на самом деле легко выводится регулярное выражение для R. Заменяя для простоты все цифры одним терминальным символом d, получим праволинейное уравнение:

R = {+,-,e}dd^*(.dd^*  И e )(e{+,-,e}dd^*  И e)

Используя теорему 3.10 и другие более простые преобразования, построим А-грамматику по этому регулярному выражению.

Ђ

Примером КС-языка, не порождаемого никакой А-грамматикой (в силу его нерегулярности), является язык {aⁿbⁿ | n і 0}.

В примере 3.11 для регулярной системы уравнений было найдено решение в виде регулярного выражения. В общем случае это невозможно, даже если система определяет регулярные языки.

Т е о р е м а  3.11. Проблема регулярности КС-языка алгоритмически неразрешима.

Доказательство здесь не приводим.
Ђ

3.2. Предикативные грамматики

Предикативные грамматики относятся к широкому классу логических грамматик, названных так за возможность логической интерпретации их правил. Первые логические грамматики были введены в России В.Б. Борщёвым и М.А. Хомяковым (1973 г.) и во Франции А. Кольмероэ (1975 г.). Однако, ближайшими предшественниками были атрибутные грамматики Д. Кнута (1968 г.) и грамматики А. ван Вейнгаардена, впервые использованные для определения языка Алгол-68 (1969 г.).

Термин "предикативные грамматики" вводится здесь для обозначения нескольких разновидностей логических грамматик, близких к DC-грамматикам (Definite Clause Grammars) Ф. Перейры и Д. Уоррена (1980 г.), включённым ими в систему логического программирования Пролог. С тех пор DC-грамматики неизменно включаются во все развитые Пролог-системы.

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

3.2.1. Простые предикативные грамматики

Простые предикативные грамматики (ПП-грамматики) являются расширением КС-грамматик посредством допущения параметров у терминальных и нетерминальных символов (из-за чего их можно рассматривать как предикаты). Параметры являются термами, а при применении правил используется унификация термов. Дадим теперь точное определение.

ПП-грамматикой называется набор G = (F,N,T,P,S), где
F - счётное множество термов, образованных с помощью конечного множества конструкторов C и объектных переменных из конечного множества W (значением объектной переменной могут быть только термы из F, сама переменная также является термом); алгебра термов может быть многосортной;
N - конечный алфавит нетерминальных символов, для каждого из которых задан тип, определяющий допустимый набор параметров из F;
T - конечный алфавит терминальных символов, которые также могут иметь параметры из F в соответствии с заданным типом; терминальные символы с параметрами позволяют ввести лексические классы и их представителей, например, number(5);
P - конечное множество правил (или продукций); правило имеет вид A ® a, где A О N, a О (T И N)^*, причем A и символы из a  содержат необходимые параметры;
S - начальный нетерминальный символ, S О N.

Определим отношение выводимости на (T И N)^*.
Из цепочки aA(t)b, где A О N, a,b О (T И N)^*, t = (t₁,...,t_n), n і 0, t_i - параметры A, непосредственно выводима цепочка (agb)q, если есть правило A(s) ® g, где s = (s₁,...,s_n), s_i - параметры A, и q - наиболее общее решение (НОР) системы уравнений t = s. Отношение обозначается aA(t)b ®_G (agb)q, а его рефлексивно-транзитивное замыкание ®_G^*  называется отношением выводимости. 

Замечание. Перед применением правила A(s) ® g (ещё до решения системы t = s) все объектные переменные, входящие в это правило, переименовываются так, чтобы они не входили в цепочку aA(t)b.

Вывод в ПП-грамматике определяется так же, как в КС-грамматике. Множество подстановок {q₁, ..., q_n}, использованных в выводе, определяет значения переменных первой цепочки вывода, при которых этот вывод возможен.

Языком, порождаемым ПП-грамматикой G, называется множество цепочек 
L(G) = {a О T^* | S(X) ®_G^* a, где X - вектор объектных переменных}.

Дерево вывода для ПП-грамматик определяется так же, как и для КС-грамматик, только в его нетерминальных вершина могут записываться ещё и НОР q.

Пример 3.12. Язык {aⁿbⁿcⁿ | n > 0} порождается ПП-грамматикой с правилами

Конструкторами термов здесь являются 0, 1 (константы) и +1 (одноместная функция).

Левый вывод цепочки aabbcc имеет вид:

Ниже приводится дерево этого вывода:

Ђ

Отношение достижимости Й^* на N определяется так же, как и для КС-грамматик (без учёта параметров). Свойство же продуктивности для ПП-грамматик является неразрешимым.

Важную роль играют семантические нетерминальные символы. Символ A О N называется семантическим, если из него недостижим никакой терминальный символ. Остальные нетерминальные символы называются синтаксическими.

Очевидно, что продуктивные семантические нетерминальные (только они и могут встречаться в выводе правильных цепочек) порождают только одну терминальную цепочку - e. Они играют роль семантических процедур, определяющих и реализующих те или иные аспекты семантики и трансляции языка. Правила для семантических символов называются семантическими правилами. Они являются правилами логической программы, определяющей соответствующие семантические предикаты. 

Т е о р е м а  3.12. Класс языков, порождаемых ПП-грамматиками, совпадает с классом рекурсивно перечислимых языков.

Доказательство следует из того, семантические правила являются правилами "чистого" Пролога - рекурсивно полного языка программирования.
Ђ

Но, как показывает пример 3.12, даже без использования семантических правил ПП-грамматики могут порождать более широкий класс языков, чем КС-грамматики.

Пример 3.13. Следующая грамматика не только порождает арифметические выражения (без идентификаторов переменных), но и вычисляет их значение (множество F то же, что и в примере 3.12):

Здесь A и M - семантические символы, обозначающие предикаты сложения и умножения, соответственно, на натуральных числах. У них первые два параметра - операнды, третий - результат операции. Ниже показано дерево вывода цепочки n(2)*n(2) (в нём термы обозначены соответствующими числами, а подстановки применены):

Ђ

3.2.2. DCG-нотация и DC-грамматики

DC-грамматики, встроенные в Пролог, и применяемая для них нотация предназначены для решения реальных языковых задач на Прологе, поэтому мы будем использовать DCG-нотацию для примеров, приближенных к реальным. К тому же эти примеры могут быть реализованы в какой-нибудь Пролог-системе. Тем не менее, мы не будем использовать все синтаксические возможности Пролога.

Терм строится из констант и переменных (объектных) с помощью конструкторов; все термы считаются одного сорта.
Константа - атом, число, строка (в долларах), ссылка (генерируется автоматически при использовании баз данных, см. ниже).
Атом - идентификатор, начинающийся с маленькой буквы, или последовательность знаков (например, := или []).
Переменная - идентификатор, начинающийся с большой буквы.
Конструктор - атом с заданной арностью (в Прологе он называется функтором).

Специальным видом терма является список - последовательность вида [t₁,...,t_n] или [t₁,...,t_n|X], где t_i - термы, X - переменная, обозначающая остаток списка. Пустой список обозначается атомом [].

Нетерминальный символ - атом с (возможно) следующими за ним параметрами в круглых скобках.
Терминальный символ - атом с (возможно) следующими за ним параметрами в круглых скобках (лексема) или просто символ.

Синтаксическое правило грамматики - для синтаксического нетерминального символа - имеет вид:

<нетерминальный символ> --> <правая часть>.

Правая часть синтаксического правила - непустая последовательность элементов, разделяемых запятой (,) или точкой с запятой (;). Запятая играет роль произведения языков, а точка с запятой - объединения.

Элементом правой части может быть:

• нетерминальный символ (с параметрами, как в левой части),
• терминальная цепочка,
• семантическая цепочка.

Терминальная цепочка - простые символы или цепочки берутся в кавычки (без разделителей), лексема или цепочка лексем берётся в квадратные скобки и разделяется запятой. Пустая цепочка обозначается "" или [].

Семантическая цепочка - последовательность семантических нетерминальных символов с параметрами, взятая в фигурные скобки с разделителями , и ;.

Семантическое правило грамматики - для семантического нетерминального символа - имеет вид обычного правила Пролога:

<нетерминальный символ> :- <правая часть>.

Правая часть семантического правила содержит только семантические нетерминальные символы (без фигурных скобок).

Большие грамматики, как и программы, требуют комментариев. Комментарий начинается символом %, а кончается концом строки.

В отличие от ПП-грамматик DC-грамматики могут использовать в качестве семантических нетерминальных символов все встроенные "предикаты" Пролога, которые сразу порождают e  при определённых значениях параметров. Мы будем использовать встроенный предикат true, играющий в семантических правилах роль e.

DC-грамматики будем записывать шрифтом фиксированной ширины.

Пример 3.14. ПП-грамматика из примера 3.13 в DCG-нотации:

expr(V) --> expr(X),"+",term(Y),{add(X,Y,V)};
            term(V).
term(V) --> term(X),"*",factor(Y),{mult(X,Y,V)};
            factor(V).
factor(V) --> [n(V)] ; "(",expr(V),")".

add(0,Y,Y).
add(X+1,Y,Z+1) :- add(X,Y,Z).
mult(0,Y,O).
mult(X+1,Y,Z) :- mult(X,Y,V),add(V,Y,Z).

Недостатком этой грамматики является то, что Пролог-система на ней зацикливается. Причиной является то, что Пролог-системы строят только левый вывод, пытаясь применять правила в том порядке, в котором они записаны. (см. п. 5.1.2). Используемая в определении предикатов expr и term так называемая "левая рекурсия" приводит к зацикливанию. 

Применим для той же цели другую грамматику выражений (без левой рекурсии) и встроенный предикат is (вместо add и mult):

expr(V) --> term(X),"+",expr(Y),{V is X+Y};
            term(V).
term(V) --> factor(X),"*",term(Y),{V is X*Y};
            factor(V).
factor(V) --> [n(V)] ; "(",expr(V),")".

Пролог-система успешно справляется с этой грамматикой, но при добавлении в порождаемые ею выражения операций вычитания и деления, она будет неправильно вычислять значение выражения, т.к. выполняет операции не слева направо, справа налево. Для сложения и умножения это несущественно, т.к. эти операции ассоциативны, а для неассоциативных операций вычитания и деления порядок выполнения важен. Грамматика, обеспечивающая правильный порядок выполнения арифметических операций, будет приведена в п. 3.2.3 (пример 3.15).

Ђ

3.2.3. Структурные предикативные грамматики (СП-грамматики)

Как мы видели, ПП-грамматики дают структурное представление выводимой цепочки в виде так называемого атрибутированного дерева вывода (в его вершинах символы с  значениями параметров - атрибутами). Однако такое дерево не всегда адекватно отражает семантические связи и свойства (т.е. отношения, используемые для определения семантики языка), особенно, когда грамматика задана в виде, обеспечивающем эффективный разрешающий алгоритм. 

DC-грамматики могут использовать встроенные в Пролог средства для работы с реляционными и сетевыми базами данных. С их помощью очень удобно в процессе грамматического вывода строить необходимую семантическую структуру, представленную термами и отношениями на них, и анализировать накопленную информацию.

Структурные предикативные грамматики (СП-грамматики) являются расширением ПП-грамматик средствами построения и анализа семантической структуры. Эти средства являются формализацией соответствующих встроенных предикатов Пролога. Они представляют собой специальные структурные нетерминальные символы, которые при определённых значениях параметров порождают e, а также выполняют некоторые действия с семантической структурой:

Ю A(t₁,...,t_n), где n і 0, t_i - параметры семантического нетерминального символа A. При выводе из символа Ю в грамматику включается правило A(t₁,...,t_n) ® e  (в DCG-нотации - A(t₁,...,t_n)). Такое правило называется фактом. Дальше A можно использовать, как обычный семантический символ, осуществляя таким образом запрос к реляционной базе данных. В Прологе этому символу соответствует встроенный предикат assert.

Я(k,t,R) - терм t включается в базу данных, в набор с ключом k (k - атом), и ссылка на него присваивается объектной переменной R. В дальнейшем эта ссылка может использоваться в любом терме, который таким образом будет ссылаться на терм t. Используется обычно для построения базы данных в виде так называемой семантической сети, удобной для перемещения в ней по ссылкам. В Прологе этому символу соответствует встроенный предикат record.

Э(R,T) - по ссылке, заданной значением объектной переменной R, в базе данных выбирается терм t и присваивается объектной переменной T. Если в этот терм входят ссылки на другие термы, то переход к ним также осуществляется символом Э. В Прологе этому символу соответствует встроенный предикат instance.

Перечисленные структурные символы относятся к числу средств так называемых монотонных рассуждений и имеют простую логическую интерпретацию. Немонотонные рассуждения представляются следующими символами (мы намеренно ограничиваем их количество по сравнению с Прологом):

ґ(A), ґ(k) - удаляет из базы данных все правила для нетерминального A или весь набор с ключом k. Рекомендуется использовать для начальной очистки базы данных. В Прологе соответствует встроенным предикатам abolish, retractall, eraseall.

Ы (R,t) - терм, хранящийся по ссылке R, заменяется термом t. Рекомендуется для уточнения значения терма (тогда сохраняется монотонность рассуждений). В Прологе соответствует встроенному предикату replace.

Пример 3.15. Рассмотрим язык, состоящий только из описаний идентификаторов числовых констант. Значение константы может задаваться выражением описанного выше типа, в котором допускается использование описанных ранее констант. Не допускается переопределение константы. С целью проверки последнего условия мы вводим непродуктивный семантический нетерминальный символ error. Результатом порождения терминальной цепочки в этой грамматике является множество фактов вида const(<идентификатор>,<значение>). При выводе выражения сначала с ключом e строится его дерево с операциями в качестве вершин (такое дерево значительно удобнее, чем дерево вывода), а затем по нему вычисляется значение выражения. Грамматика приводится в DCG-нотации.

declarations -->
   {ґ(const),ґ(e)},   % начальные очистки
   constants.
constants -->
   [id(I)],
   {const(I,V),error  % проверка, что идентификатор ещё не описан
    ;
    true},
   "=",expr(T),
   {eval(T,N),        % вычисление и присваивание значения
    Ю const(I,N)},
   constants ; [].    % повторение и окончание списка констант
expr(E) -->
   term(T),terms(T,E).
terms(T1,E) -->
   "+",term(T2),{Я(e,+(T1,T2),T)},
   terms(T,E)
   ;
   [].
term(T) -->
   factor(F),factors(F,T).
factors(F1,T) -->
   "*",factor(F2),{Я(e,*(F1,F2),F)},
   factors(F,T)
   ;
   [].
factor(T) -->
   [n(N)],{Я(e,n(N),T)}
   ;
   [i(I)],
   {const(I,N),Я(e,i(I),T)  % проверка, что идентификатор описан
    ;
    error},
   "(",expr(T),")".

error :-      % непродуктивный семантический предикат
   error.

eval(T,N) :-
   Э(T,Term),ev(Term,N).
ev(n(N),N).
ev(i(I),N) :-
   const(I,N).
ev(+(T1,T2),N) :-
   eval(T1,N1),eval(T2,N2),N is N1+N2.
ev(*(T1,T2),N) :-
   eval(T1,N1),eval(T2,N2),N is N1*N2.

Ђ