Стартовая страница G l o s s a r y   C o m m a n d e r

Служба тематических толковых словарей

glossary.ru
park.glossary.ru
Служебная библиотека
 н а  п р а в а х  р е к л а м ы 

 Чтение: 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10  | 11  | 12  | 13  | 14
freezer service thousand oaks ca . В поисках беговой дорожки? Магнитная беговая дорожка купить можно со скидкой до 5%  

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

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

Серьезное
чтение
на glossary.ru
точная ссылка

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

При этом всю грамматику можно охарактеризовать числом
h(G) = h(A)
A ∈ N
Например, для грамматики 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,  h2,  h3,  ...,  (1)
где 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" 
Факторизация 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 принадлежит одному классу если

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.
 


Точная ссылка на статью:
Соловьев С.Ю.
Нормализация контекстно-свободных грамматик для целей грамматического вывода.
// Труды XII национальной конференции по искусственному интеллекту
с международным участием КИИ-2010. Т.1.
- М.: Физматлит, 2010. стр.218-224.

Статья размещена автором на сайте www.glossary.ru - Служба тематических толковых словарей
 


П|р|о|д|о|л|ж|е|н|и|е ►



Copyright ©
2000-2014
Web-and-Press


webadmin@glossary.ru