Задача грамматического вывода (восстановления грамматик) [Соловьев, 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 → { α1, ..., αn} означает множество правил { A→ α1, ..., A→ αn};
- запись A → α1 | ... | αn, также означает множество правил { A→ α1, ..., 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, где α, β1, β2, ...,
βn - непустые строки. По-умолчанию будем полагать, что α
- префикс максимально возможной длины.
Если нетерминал A допускает неукорачивающую левую факторизацию в
КС-грамматике G, то G можно трансформировать в грамматику GA,
применив следующее ЛНФ-преобразование:
- шаг 1 - исключить из G все A-правила;
- шаг 2 - к оставшимся правилам добавить правила A' → β1| β2| ... | β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(GA);
— в грамматике GA нетерминал A' не допускает неукорачивающую левую факторизацию; но
— в грамматике GA может появиться [другой] нетерминал, допускающий неукорачивающую левую факторизацию.
Последнее обстоятельство иллюстрирует пример 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(α) = min { длина(x) | α ⇒G x }.
При этом всю грамматику можно охарактеризовать числом
Например, для грамматики G из примера 1:
h(S) = 1, h(S') = 1, h(A) = 2, h(B) = 1, h(C) = 2, h(D) = 1 и h(G) = 8.
Для результирующей грамматики GA:
h(S) = 1, h(S' ) = 1, h(A') = 1, h(B) = 1, h(C) = 2, h(D) = 1 и h(GA) = 7.
В результате ЛНФ-преобразования всегда выполняется соотношение
h(G) > h(GA). В самом деле:
— h(B) не изменяется для нетерминалов B ≠ A'; а
— h(A) = h(A') + h(β) > h(A'),
поскольку в грамматиках без e-правил h(β) > 0.
Таким образом, применяя к некоторой исходной КС-грамматике G
ЛНФ-преобразования, одновременно получаем убывающую последовательность
положительных чисел
где h1 = h(G), h2 = h(GA), ...,
что гарантирует завершение процесса устранения нетерминалов,
допускающих неукорачивающую левую факторизацию. Для примера 2
последовательность (1) имеет вид: 6, 4, 3.
Аналогично рассматривается вопрос о неукорачивающей правой факторизации.
Будем говорить, что нетерминал A допускает неукорачивающую правую
факторизацию, если все предложения из R(G,A) могут быть представлены в виде
αiβ, где
α1,
α2, ...
αn, β
- непустые строки.
По-умолчанию будем полагать, что β - суффикс максимально возможной длины.
Если нетерминал A допускает неукорачивающую правую факторизацию в
КС-грамматике G, то G можно трансформировать в грамматику GA, применив
следующее ПНФ-преобразование:
- шаг 1 - исключить из G все A-правила;
- шаг 2 - к оставшимся правилам добавить правила
A' → α1 | α2| ... | α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" |
|
|
Свойство 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 принадлежит одному классу если
R+(G, A) = R+(G,B),
где R+(G,C) получается из R(G,C) заменой всех
нетеминалов именами соответствующих классов эквивалентности.
Так, в грамматике GA из примера 1 существует нетривиальное
разбиение нетерминалов на классы эквивалентности:
{ S }, { S' , A' },
{ B }, { C }, { D }.
Если в качестве имен классов использовать имена первых
нетерминалов каждого класса, то
R+(G, S') = R+(G,A') = { B, B+S'},
т.е. нетерминал A' оказывается избыточным, и его удаление
порождает грамматику, указанную в примере 5.
Пример 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.
- [Фу, 1977]
- Фу К. Структурные методы в распознавании образов. - М.: Мир, 1977.
- [Хант, 1978]
- Хант Э. Искусственный интеллект. - М.: Мир, 1978.
|