Задача грамматического вывода (восстановления грамматик) [Соловьев, 1985] в искусственном интеллекте и распознавании образов исследуется давно [Хант, 1978; Фу, 1977]. Считается, что построение грамматики по конечному множеству порожденных ею предложений соответствует построению базы знаний или решающего правила. Обычно конструктивные методы грамматического вывода разрабатываются для отдельных классов грамматик -суть- отдельных классов формальных языков. При этом существенно используются "тонкие" свойства порождающих грамматик. В настоящей работе показывается, что при восстановлении контекстно-свободных грамматик (КС-грамматик) можно использовать свойство факторизуемости правых частей правил вывода. Причем факторизуемость не сказывается на других важных свойствах КС-грамматик.

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

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

∑ – непересекающийся с N алфавит терминальных символов (терминалов);

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

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

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

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

• A, B, C обозначают нетерминалы; S – начальный символ;
• α, β обозначают непустые цепочки символов из N ∪ ∑;
• x, y обозначают непустые цепочки-предложения символов из ∑;
• R(G,A) = { α | A → α ∈ P } – множество всех правых частей A-правил из P;
• запись A → { α₁, ..., α_n} означает множество правил { A→ α₁, ..., A→ α_n};
• запись A → α₁ | ... | α_n, также означает множество правил { A→ α₁, ..., A→ α_n};
• запись α ⇒_G β означает, что цепочка β выводима из цепочки α в грамматике G, т.е. β может быть получена из α применением конечного числа правил;
• L(G) = { x | S ⇒_G x } – язык, порождаемый грамматикой G.

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

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

Последнее ограничение фактически означает, что множество заданных для грамматического вывода предложений "насильно" пополнено предложением из одного уникального символа #. Использование дополнительного символа позволяет обособить начальный символ S и избежать большого числа оговорок. В частности:
— S не является рекурсивным;
— S не является простым, то есть R(G,S) содержит более одной цепочки;
— цепочки из R(G,S) не имеют общих префиксов и суффиксов.
Вместе с тем удалить в восстановленной грамматике правило S → # труда не составляет.

Будем говорить, что нетерминал A допускает неукорачивающую левую факторизацию, если все предложения из R(G,A) могут быть представлены в виде αβ_i, где α, β₁, β₂, ..., β_n - непустые строки. По-умолчанию будем полагать, что α - префикс максимально возможной длины.

Если нетерминал A допускает неукорачивающую левую факторизацию в КС-грамматике G, то G можно трансформировать в грамматику G_A, применив следующее ЛНФ-преобразование:
- шаг 1 - исключить из G все A-правила;
- шаг 2 - к оставшимся правилам добавить правила A' → β₁| β₂| ... | β_n;
- шаг 3 - во всех правилах на местах нетерминала A разместить строку α A'.

Пример No.1. Пошаговое выполнение ЛНФ-преобразования.
 

Грамматика G S → S'| # S' → B | BA A → +B | +BA B → D | DC C → *D | *DC D → (S') | a

Шаг 1. S → S'| # S' → B | BA   B → D | DC C → *D | *DC D → (S') | a

Шаг 2. S → S'| # S' → B | BA A' → B | BA B → D | DC C → *D | *DC D → (S') | a

Шаг 3. = GA S → S'| # S' → B | B+A' A' → B | B+A' B → D | DC C → *D | *DC D → (S') | a

В общем случае:
— ЛНФ-преобразование является эквивалентным, т.е. L(G) = L(G_A);
— в грамматике G_A нетерминал A' не допускает неукорачивающую левую факторизацию; но
— в грамматике G_A может появиться [другой] нетерминал, допускающий неукорачивающую левую факторизацию.

Последнее обстоятельство иллюстрирует пример 2, в котором S' получает статус нетерминала, допускающего левую факторизацию, по результатам ЛНФ-преобразования для нетерминала A.

Пример No.2
 

Грамматика G S → S'| # S' → aa | Ab A → aba | abA

ЛНФ для A S → S'| # S' → aa | abA'b A' → a | abA'

ЛНФ для S' S → aS'| # S' → a | bA'b A' → a | abA'

В связи с этим возникает вопрос: можно ли в КС-грамматиках, последовательно применяя ЛНФ-преобразования, полностью избавиться от нетерминалов, допускающих неукорачивающую левую факторизацию?

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

При этом всю грамматику можно охарактеризовать числом

h(G) =	∑	h(A)
	A ∈ N

Например, для грамматики G из примера 1:

Для результирующей грамматики G_A:

В результате ЛНФ-преобразования всегда выполняется соотношение h(G) > h(G_A). В самом деле:
— h(B) не изменяется для нетерминалов B ≠ A'; а
— h(A) = h(A') + h(β) > h(A'), поскольку в грамматиках без e-правил h(β) > 0.

Таким образом, применяя к некоторой исходной КС-грамматике G ЛНФ-преобразования, одновременно получаем убывающую последовательность положительных чисел

h1,  h2,  h3,  ...,

(1)

где h₁ = h(G), h₂ = h(G_A), ..., что гарантирует завершение процесса устранения нетерминалов, допускающих неукорачивающую левую факторизацию. Для примера 2 последовательность (1) имеет вид: 6, 4, 3.

Аналогично рассматривается вопрос о неукорачивающей правой факторизации. Будем говорить, что нетерминал A допускает неукорачивающую правую факторизацию, если все предложения из R(G,A) могут быть представлены в виде α_iβ, где α₁, α₂, ... α_n, β - непустые строки. По-умолчанию будем полагать, что β - суффикс максимально возможной длины.

Если нетерминал A допускает неукорачивающую правую факторизацию в КС-грамматике G, то G можно трансформировать в грамматику G_A, применив следующее ПНФ-преобразование:
- шаг 1 - исключить из G все A-правила;
- шаг 2 - к оставшимся правилам добавить правила A' → α₁ | α₂| ... | α_n;
- шаг 3 - во всех правилах на местах нетерминала A разместить строку A' β.

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

Для определенности будем считать, что общий процесс неукорачивающей факторизации (НФ-преобразования) заданной грамматики состоит из последовательности процессов
— устранения нетерминалов, допускающих неукорачивающую левую факторизацию; и
— устранения нетерминалов, допускающих неукорачивающую правую факторизацию.

Рассмотрим влияние неукорачивающей факторизации на другие свойства КС-грамматик.

Свойство 1. Процесс устранения нетерминалов, допускающих неукорачивающую факторизацию, принципиально не порождает e-правила.

Заметим, что в традиционной задаче нисходящего синтаксического анализа [Кнут, 1978] процесс [левой] факторизации допускает порождение e-правил. Однако комбинация [левой] факторизации и удаление e-правил может породить бесконечный процесс преобразования исходной грамматики. Пример такого процесса приводится в примере 3.

Пример No.3.
 

Грамматика G S → S'| # S' → a | aS'

Факторизация S' S → aS" | # S" → e | aS"

Удалить S" → e S → a | aS" | # S" → a | aS"

Факторизация S"   и т.д.

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

Свойство 3. Процесс устранения нетерминалов, допускающих неукорачивающую факторизацию, может породить цепные правила вида A → B. Если исходная грамматика не содержала цепные правила (за исключением быть может некоторых S-правил), то это свойство можно сохранить, включив в цепочку НФ-преобразований удаление цепных правил (см. пример 4).

Пример No.4.
 

Грамматика G S → S'| # S' → aA | Ab A → aab | aaB A → (b) | aS'b

>> ЛНФ для A S → S'| # S' → aaaA'| aaA'b A' → b | B B → (b) | aS'b

>> Удалить A' → B S → S'| # h(S) = 1 S' → aaaA'| aaA'b h(S')= 4 A' → b | (b) | aS'b h(A')= 1 B → (b) | aS'b h(B) = 3

Очевидно, что удаление цепных правил не изменяет характеристику h преобразованной грамматики.

Свойство 4. Описанное в свойстве 3 удаление цепных правил может породить недостижимые нетерминалы и, соответственно, бесполезные правила вывода. Так, в примере 4 после удаления цепного правила A' → B нетерминал B становится недостижимым. В соответствии с принятыми ограничениями исходная грамматика не содержала бесполезных правил вывода. Это свойство можно сохранить, включив в цепочку НФ-преобразований удаление недостижимых нетерминалов.

Пример No.4 (продолжение).
 

Удалить B S → S'| # h(S) = 1 S' → aaaA'| aaA'b h(S')= 4 A' → b | (b) | aS'b h(A')= 1

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

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

В общем случае избыточность связана с существованием нетривиального разбиения множества нетерминалов на такие классы эквивалентности, при котором пара нетерминалов A и B принадлежит одному классу если

Так, в грамматике G_A из примера 1 существует нетривиальное разбиение нетерминалов на классы эквивалентности:

Если в качестве имен классов использовать имена первых нетерминалов каждого класса, то

Пример No.5 (продолжение примера No.1)
 

Грамматика GA S → S'| # S' → B | B+A' A' → B | B+A' B → D | DC C → *D | *DC D → (S') | a

Удалить A' S → S'| # h(S) = 1 S' → B | B+S' h(S')= 1   B → D | DC h(B) = 1 C → *D | *DC h(C) = 2 D → (S') | a h(D) = 1

Если исходная грамматика не содержала избыточные нетерминалы, то это свойство можно сохранить, включив в цепочку НФ-преобразований удаление избыточных нетерминалов. Очевидно, что такая операция уменьшает характеристику h преобразованной грамматики.

Свойство 6. Если исходная грамматика принадлежит классу LL(1) [Ахо и др., 1978], то результирующая грамматика, полученная в результате НФ-преобразований, также принадлежит классу LL(1).

Таким образом, для целей грамматического вывода можно использовать нормализованные КС-грамматики G = < N, ∑, P, S >, удовлетворяющие всем или некоторым свойствам из перечисленного списка:
— в P имеется правило S → #, причем в остальных правилах вывода терминал # не встречается;
— в P отсутствуют e-правила, за исключением, быть может, правила S → e;
— в P отсутствуют правила, допускающие правую и левую неукорачивающую факторизацию;
— в P отсутствуют цепные правила;
— в P отсутствуют бесполезные правила;
— в N отсутствуют простые нетерминалы;
— G не является избыточной грамматикой.

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

[Ахо и др., 1978]

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. тт. 1,2, М.: Мир, 1978.

[Кнут, 1978]

Кнут Д. Нисходящий синтаксический анализ. // Кибернетический сборник. Вып. 15. М.: Мир, 1978, с.101-142.

[Соловьев, 1985]

Соловьев С.Ю. Постановка задачи грамматического вывода. // Математическое обеспечение вычислительных машин и систем. (Математические исследования, вып. 81) - Кишинев: Штиинца, 1985. с.135-143.

http://www.park.glossary.ru/serios/read_08.php

[Фу, 1977]

Фу К. Структурные методы в распознавании образов. - М.: Мир, 1977.

[Хант, 1978]

Хант Э. Искусственный интеллект. - М.: Мир, 1978.