Нормализация контекстно-свободных грамматик для целей грамматического вывода

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

Задача грамматического вывода (восстановления грамматик) [Соловьев, 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.

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

В общем случае:

ЛНФ-преобразование является эквивалентным, т. е. L (G) = L (G_A);

в грамматике G_A нетерминал A не допускает неукорачивающую левую факторизацию; но в грамматике G_A может появиться [другой] нетерминал, допускающий неукорачивающую левую факторизацию.

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

Пример 2.

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

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

h() = min{ длина(x) | _G x }.

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

h (G) = h (A) [ суммирование по всем AN ].

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

h (S) = 1, h (S) = 1, h (A) = 2, h (B) = 1, h (C) = 2, h (D) = 1 и h (G) = 8.

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

h (S) = 1, h (S) = 1, h (A) = 1, h (B) = 1, h (C) = 2, h (D) = 1 и h (G_A) = 7.

В результате ЛНФ-преобразования всегда выполняется соотношение h (G) h (G_A). В самом деле:

h (B) не изменяется для нетерминалов B A; а.

h (A) = h (A) + h () > h (A), поскольку в грамматиках без e-правил h () 0.

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

где 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.

Пример 3.

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

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

Пример 4.

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

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

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

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

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

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

R⁺(G, A) = R⁺(G, B),.

где R⁺(G, C) получается из R (G, C) заменой всех нетеминалов именами соответствующих классов эквивалентности.

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

{S}, {S, A}, {B}, {C}, {D}.

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

R⁺(G, S) = R⁺(G, A) = {B, B+S},.

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

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

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

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

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

• · в P имеется правило S > #, причем в остальных правилах вывода терминал # не встречается;
• · в P отсутствуют e-правила, за исключением, быть может, правила S > e;
• · в P отсутствуют правила, допускающие правую и левую неукорачивающую факторизацию;
• · в P отсутствуют цепные правила;
• · в P отсутствуют бесполезные правила;
• · в N отсутствуют простые нетерминалы;
• · G не является избыточной грамматикой.

• 1. [Ахо и др., 1978] Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, тт. 1,2. — М.: Мир, 1978.
• 2. [Кнут, 1978] Кнут Д. Нисходящий синтаксический анализ. // Кибернетический сборник. Вып. 15. — М.: Мир, 1978.
• 3. [Соловьев, 1985] Соловьев С. Ю. Постановка задачи грамматического вывода. // Математическое обеспечение вычислительных машин и систем. (Математические исследования, вып. 81) Кишинев: Штиинца, 1985. http://www.park.glossary.ru/serios/read₀₈.php
• 4. [Фу, 1977] Фу К. Структурные методы в распознавании образов. — М.: Мир, 1977.
• 5. [Хант, 1978] Хант Э. Искусственный интеллект. — М.: Мир, 1978.