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

Размещено на http://www.allbest.ru/

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

C.Ю. Соловьев

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

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

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

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

Размещено на Allbest.ru