Введение

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

Контекстно-свободной грамматикой [1] называется четверка G = < N, ∑, P, S >, где

N – алфавит нетерминальных символов (нетерминалов);

∑ – непересекающийся с N алфавит

терминальных символов (терминалов);

P – конечное множество правил вывода вида A → α,

где A ∈ N, α - цепочка символов из N ∪ ∑;

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

В последующих выкладках будем полагать, что действуют следующие соглашения:

• A, B, C обозначают нетерминалы; S - начальный символ;
• a, b, c, d — терминальные символы;
• α, β, γ, σ — цепочки символов из N ∪ ∑
• x, y, z — цепочки символов (предложения) из ∑ ;
• e — пустая цепочка нулевой длины;
• запись A → α₁ | ... | α_n, означает множество правил { A → α₁ , ..., A → α_n };
• запись α ⇒_G β означает, что α = α₁Aα₂ , β = α₁γα₂ и A → γ ∈ P; в этом случае будем говорить, что цепочка β непосредственно выводима из цепочки α в грамматике G;
• L(G) = { x | S ⇒*_G x } — язык, порождаемый грамматикой G.

Принятые соглашения позволяют, в частности, задавать КС-грамматики простым перечислением правил вывода.

КС#грамматики

Каждая контекстно-свободная грамматика G = < N, ∑, P, S > порождает семейство грамматик G(A) = < N, ∑, P, A >, где A ∈ N. Для начального символа S имеем: G(S) = G и L(G(S)) = L(G) . В общем случае КС-язык L(G(A)) есть реализация нетерминала A в классе терминальных цепочек.

В дальнейшем изложении будем рассматривать только такие КС-грамматики < N, ∑, P, S >, в которых:

• отсутствуют правила с пустой правой частью; и
• имеется правило S → #, причем терминальный символ # в других правилах не встречается.

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

С точки зрения порождаемых языков приведенные ограничения не являются существенными. Любой КС-язык L может быть получен из КС#языка L_# одним из двух способов:
 либо L = L_# \ { # } ,
 либо L = (L_# \ { # }) ∪ { e };
соответствующая КС-грамматика получается
 либо посредством удаления правила S → #,
 либо посредством его замены на правило S → e.
Вместе с тем, использование дополнительного символа # позволяет естественным образом вывести начальный символ S из-под действия многих эквивалентных преобразований.

Остановимся на одном из преобразований КС-грамматик, связанным с изменением языков L(G(A)), A ≠ S. В качестве неформально введения в задачу рассмотрим цепочки abcg, abcfg и abdсdg. Эти цепочки имеют общий префикс ab и общий суффикс g. В более изощренных случаях необходимо точно оговорить, что считать общим префиксом и/или суффиксом:

• для { a, ab, abb } префикс и суффикс отсутствуют;
• для { abc, abcc, abccс } префикс = ab, суффикс отсутствует;
• для { abc, abbc, abbbс } префикс = ab, суффикс отсутствует и пр.

В общем случае, после удаления общих префикса и суффикса не должна возникать пустая цепочка. Кроме того, будем исходить из того, что сначала определяется префикс, а затем — суффикс.

Если язык L(G(A)) имеет непустой общий префикс x,

то будем говорить, что нетерминал A имеет префикс x.

Если язык L(G(A)) имеет непустой общий суффикс z,

то будем говорить, что нетерминал A имеет суффикс z.

Продолжая неформальное введение, рассмотрим КС-грамматику

      G:   S  →  A+A  | gb 
           A  →  abcg | abcfg | abdсdg

Здесь язык L(G(A)) = { abcg, abcfg, abdcdg } задан в явном виде. У нетерминала A префикс ab и суффикс g можно изъять и передать "вышестоящему" нетерминалу S , при этом грамматика примет следующий вид

      G':  S  →  abA'g+abA'g |  gb 
           A' →  c           |  cf  |  dсd

В грамматике G' нетерминал A' не имеет ни префикса ни суффикса. Понятно, что грамматики G и G' эквивалентны. Возникает вопрос о возможности изъятия префиксов и суффиксов нетермналов для КС-грамматик общего вида. Отметим, что в данном случае изъятие рассматривается как эквивалентное преобразование грамматик.

Нетерминалы, у которых можно забирать префиксы и суффиксы, удовлетворяют естественным условиям:

L(G(A)) = конкатенация(a,L)		(L)
и/или L(G(A)) = конкатенация(L,a)		(R)
где L - некоторый язык, e ∉ L.

Однако приведенные условия являются слишком общими; можно показать алгоритмическую неразрешимость задачи изъятия префиксов и суффиксов у всех нетерминалов, удовлетворяющих условиям (L) и (R). Пойдем по пути уточнения класса нетерминалов, у которых можно "безнаказанно" забирать префиксы и суффиксы.

LD-преобразование КС#грамматик

Подмножество нетерминалов КС#грамматики G = < N, ∑, P, S >
будем называть делимым-слева относительно терминала a, и
будем будем его обозначать LD(a),
если множество правил вывода P образуют правила трех типов:
тип 1: A → aα,     где A ∈ LD(a)  и  α ≠ e;
тип 2: A → A₀α,   где A ∈ LD(a)  и  A₀ ∈ LD(a)
тип 3: B → α,       где B ∉ LD(a).

Понятно, что
если A ∈ LD(a), то L(G(A)) обязательно удовлетворяет условию (L);
если B ∉ LD(a), то L(G(B)) может удовлетворять или не удовлетворять условию (L) .

Например:

      GT:   S  →  A+A |  Bg
            A  →  ab  |  Aa 
            B  →  Dd  |  abd 
            D  →  a   |  aD

∀ x ∈ { a, b, d, g, + }    D ∉ LD(x), и, следовательно,    B ∉ LD(x).
LD(a) = { A },
правила типа 1: A → ab;
правила типа 2: A → Aa;
правила типа 3: S → A+A,   S → Bg,   B → Dd, B → abd,   D → а,   D → аD.
A ∈ LD(a);
    L(G_T(A)) = { abaⁿ | n ≥ 0 } = { ax | x = baⁿ, n ≥ 0 }.
B ∉ LD(a);
    L(G_T(B)) = { aⁿd | n ≥ 1 } ∪ { abd } = { ax | x = aⁿd / bd, n ≥ 2 }.
Предложения из L(G_T(D)) не сводимы к виду ax, где x ≠ e.
Конец примера.

Каждому делимому-слева подмножеству нетерминалов LD(a) = { A₁, A₂, ... } поставим во взаимнооднозначное соответствие подмножество ранее не использовавшихся нетерминальных символов LD'(a) = { A'₁, A'₂, ... }.

Если в контексте некоторой КС-грамматики известно множество LD(a), то можно рассматривать преобразование цепочек W, заключающееся в выполнении всевозможных подстановок aA'_i вместо A_i. Цепочка W(α) получается из цепочки α посредством замены всех символов A из LD(a) на цепочки из двух символов aА', где А' ∈ LD'(a). Обратное преобразование W ^-1 заменяет в заданной цепочке все вхождения aA'_i на соответствующие нетерминалы A_i. Обратное преобразование полностью удаляет из заданной цепочки α все символы LD'(a) только в том случае, когда непосредственно перед символом из LD'(a) располагается символ a.

Например, в грамматике G_T для LD(a) = { A } имеем:

      W(Aa+A+aBg) = &aA'a+aA'+aBg,
                W-1(&aA'a+bA'+aBg) = Aa+bA'+aBg,
                W-1(&aA'a+aA')     = Aa+A

Пусть LD(a) - подмножество делимых-слева нетерминалов некоторой
КС#грамматики G = < N, ∑, P, S >, определим грамматику G_W = < N_W, ∑, P_W, S > следующим образом:
N_W = (LD'(a) ∪ N) \ LD(a), а
P_W построено так:

• если A → aα есть правило типа 1 грамматики G, то A' → W(α) ∈ P_W;
• если A → A₀α есть правило типа 2 грамматики G, то A' → A'₀W(α) ∈ P_W;
• если B → α     есть правило типа 3 грамматики G, то B → W(α) ∈ P_W.

Например, для множества LD(a) = { A } грамматики

      G:   S  → A   |  A+A  | #
           A  → ab  |  A+A  | A-A

      GW:  S  →  aA' |  aA'+aA' |  #
           A' →  b   |  A'+aA'  |  A'-aA'

RD-преобразование КС#грамматик

Аналогично LD-преобразованию вводится RD-преобразование КС#грамматик, основанное на множестве RD-нетерминалов делимых-справа.

Подмножество нетерминалов КС#грамматики G = < N, ∑, P, S >
будем называть делимым-справа относительно терминала a, и
будем его обозначать RD(a),
если множество правил вывода P образуют правила трех типов:

тип 1':	A → αa,	где A ∈ RD(a) и α ≠ e;
тип 2':	A → αA0,	где A ∈ RD(a) и A0 ∈ RD(a);
тип 3':	B → α,	где B ∉ RD(a).

Если в КС-грамматике зафиксировано некоторое подмножество делимых-справа нетерминалов RD(a), то в такой грамматике можно рассматривать преобразование цепочек V. Цепочка V(α) получается из цепочки α посредством замены всех символов A из RD(a) на цепочки из двух символов A'a, где A' ∈ RD'(a).

Пусть RD(a) - подмножество делимых-справа нетерминальных символов КС#грамматики G = < N, ∑, P, S >, определим грамматику G_V = < N_V, ∑, P_V, S > следующим образом:
N_V = ( RD'(a) ∪ N ) \ RD(a), а
P_V построено так:

если A → αa	есть правило типа 1' грамматики G, то A' → V(α)	∈ PV;
если A → αA0	есть правило типа 2' грамматики G, то A' → V(α)A'0	∈ PV;
если B → α	есть правило типа 3' грамматики G, то B → V(α)	∈ PV.

Можно показать, что L(G) = L(G_V), то есть RD-преобразование КС#грамматики G в КС#грамматику G_V относительно некоторого непустого множества RD-нетерминалов является эквивалентным преобразованием.

Реализация эквивалентных преобразований КС-грамматик

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

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

Например, в LD-преобразовании
этап "Выявить" состоит в нахождении некоторого непустого множества LD(a);
этап "Преобразовать" состоит в построении грамматики G_W относительно найденного множества LD(a).

Фактически по успешной ветке может передаваться некоторая информация, существенная для преобразования.

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

В этот прямоугольник

• сверху входит стрелка, соответствующая исходной грамматике;
• направо выходит стрелка, соответствующая измененной грамматике; и
• вниз выходит стрелка, соответствующая исходной грамматике, оставшейся без изменений.

С использованием принятых обозначений универсальная схема управления преобразованиями грамматик выглядит так:

Нетрудно видеть, что универсальная схема

• полностью определяется последовательностью эквивалентных преобразований;
• имеет определенные достоинства; и
• порождает некоторые проблемы.

Достоинства. Универсальная схема гарантирует, что в результирующей грамматике более нельзя выполнить ни одного эквивалентного преобразования (1), (2), ..., (n).

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

По определению величина h КС-грамматики G = < N, ∑, P, S > есть
 

h(G) =	∑	min { длина(x) | x ∈ L(G(A)) }
	A ∈ N

Например, для рассмотренной ранее грамматики G_T имеем:
min { длина (x) | x ∈ L(G_T(D)) } = 1;
min { длина (x) | x ∈ L(G_T(B)) } = 2;
min { длина (x) | x ∈ L(G_T(A)) } = 2;
min { длина (x) | x ∈ L(G_T(S)) } = 3;
и окончательно имеем: h(G_T) = 1 + 2 + 2 + 3 = 8 .

Зачастую по результатам эквивалентного преобразования
1. одна часть нетерминалов сохраняет свои реализации неизменными, в том числе, начальный символ S, а
2. другая (непустая) часть нетерминалов:
    2.1 либо вообще ликвидируется,
    2.2 либо изменяет свою реализацию c L(G(A)) на L, где

L = { y | xy ∈ L(G(A) } или

L = { y | yz ∈ L(G(A) } для некоторых непустых x и z.

Преобразование, удовлетворяющее свойствам 1+2, уменьшает величину h. Факт уменьшения величины h будем обозначать h-.

Например, LD-преобразование КС#грамматик относительно некоторого LD(a) подпадает под случай 1+2.2 при x = a, z = e. Здесь первую часть нетерминалов составляют N \ LD(a), а вторую - LD(a). Нетрудно показать, что h(G) = h(G_W) - R, где R - количество нетерминалов в LD(a).

Рассмотрим подвид универсальных схем эквивалентных преобразований, представленный на следующем рисунке:

Здесь:

• преобразование (1) - необязательное устранение бесполезных² символов, в том числе:
  • нетерминалов, которые не могут порождать терминальные цепочки; и
  • правил вывода, содержащих недостижимые символы;
• преобразование (2) - необязательное устранение цепных³ правил;
• преобразования (3)..(n) - такие преобразования, которые уменьшают характеристику h.

Преобразования (1) и (2) давно и хорошо изучены, в общем случае они не изменяют характеристику грамматики h, однако их использование совместно или порознь не способно привести к зацикливанию. Что касается остальных преобразований, то их выполнение порождает монотонно убывающую последовательность положительных чисел h₁, h₂, h₃, ... . Такая последовательность не может быть бесконечной, а значит корректность подвида универсальных схем эквивалентных преобразований установлена.

К преобразованиям (3)..(n), в частности, относятся:

устранение простых нетерминалов	- случай 1+2.1 (h-);
устранение нерекурсивных4 нетерминалов	- случай 1+2.1 (h-);
устранение избыточных нетерминалов [2]	- случай 1+2.1 (h-);
ЛНФ- и ПНФ-преобразования5	- случай 1+2.2 (h-);
LD- и RD- преобразования	- случай 1+2.2 (h-).

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

Так, в некоторых случаях ЛНФ-преобразования [2] можно рассматривать как частный случай LD-преобразований. Если, например A-правила грамматики имеют вид

то ЛНФ-преобразование терминала A совпадает с LD-преобразованием относительно LD(a) = { A }. Вместе с тем ЛНФ-преобразование способно обрабатывать случаи. когда все правые части A-правил начинаются одним и тем же нетерминалом. При этом ЛНФ-преобразование действует вполне "разумно", преобразуя

LD-преобразование в этом случае действует более "топорно", преобразуя

Заключение

Настоящая работа носит исключительно теоретический характер, ее главная цель - расширить спектр возможностей при выдвижении гипотез о строении неизвестной грамматики, породившей некоторые известные предложения. Если, например, известно, что LL(1) грамматика породила два предложения abcabdd и abcbcddd, то с определенными оговорками можно считать, что оба эти предложения в искомой грамматике имеют общую сентенциальную форму abcA"dd. В самом деле:

• быть LL(1) означает наличие общей формы abcA, где A → abdd | bcddd, в общем виде известной как "дерево суффиксов" [3];
• доказанная допустимость RD-преобразований фактически означает наличие общей формы abcA''dd, где A'' → ab | bcd.

Упомянутые оговорки будут раскрыты в следующих работах.

Список литературы

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. тт. 1,2. - М.: Мир, 1978.
2. Соловьев С.Ю. Нормализация контекстно-свободных грамматик для целей грамматического вывода. // XII национальная конференция по искусственному интеллекту с международным участием КИИ-2010. Труды конференции. - М.: Физматлит, 2010, том 1, стр.218-224.
   http://www.park.glossary.ru/serios/read_09.php
3. Смит Б. Методы и алгоритмы вычислений на строках. - М.: Вильямс, 2006.