Реферат: Дерево непосредственных составляющих

выполняется для узла А, если строка соответствующая ответвлению от узла А, является w и существует анализ t вида r1pАfr2 , где r1, r2 Î V*. Контекстное условие p - f называется анализом предиката.

Наряду с контекстозависимымми правилами правилами, позволяющими специфицировать “правый” и “левый” контекст, часто необходимо иметь правила специфицирующие “верхний” и “нижний” контекст. Имеем узел А дерева t, область (p - f), p, fÎ V*, содержит узел А, если существует путь от корня до края дерева, и этот путь имеет форму

r1pАfr2 (r1, r2 Î V*).

Контекстное условие, связанное с таким “вертикальным” анализом называется “господствующим предикатом”.

В общем виде правило имеет форму

А -->w/СА

где СА - булева комбинация анализа и господствующих предикатов.

Пусть G - конечный набор правил и t(G) - набор деревьев, анализируемый G. Предполагается, что деревья t(G) - предложения; т.е. корневой узел дерева t(G) обозначен начальным символом S, а конечные узлы - терминальными символами. Покажем, что строчный язык L(t(G)) = {x½x, где х терминальная строка дерева t, и t Ît(G)} контекстно свободен (7).

Пример: Пусть V = {S, T, a, b, c, e} и S = {a, b, c, e}, и G - конечный набор строгих правил.

1. S -->e

2. S --> aT

3. T --> aS

4. S --> bTc / (a_()) Ù DOM (T_)

5. T --> bSc / (a_()) Ù DOM (S_)

Для правил 1, 2, 3 имеет место нулевой контекст и эти правила - контекстносвободные. В четвертом и пятом правиле по условию требуется а слева и узел подчиняется Т (в пятом правиле S).

Язык, порожденный G, может быть порожден G1:

S --> eS --> aT1

S --> aTT--> aS1

T --> aST1--> bSc

S1-->bTc

Грамматика G1 содержит дополнительные нетерминальные символы S1 и Т1 для проверки локального контекста при порождении. Легко заметить, что при помощи S1 и Т1, достигается гомоморфизм, позволяющий анализировать любое дерево G1 при помощи G и обратно - любое дерево G имеет гомоморфный прообраз в G1. Рассмотрим еще раз контекстно зависимое правило (10).

V --> wanted½ -VP

когда (10) интерпретируется как ложное правило, как описано выше, лексема “wanted” появляется над узлом V, только если узел VP находится справа от нее (в дереве, где появляется V). Справа от V существует строка, имеющая VP “анализ”. Контекстно-зависимые правила в КГЗ используются для анализа обычных грамматик, а не есть правила простого переписывания строк.

Терминальные символы в ГНС. До этого момента терминальные символы были представлены как нереализуемые элементы. Это было сделано для простоты изложения. Терминальные символы представляют собой наборы топологических, синтаксических и семантических признаков (4, 8). [В принципе возможно ликвидировать все эти признаки посредством введения новых нетерминальных символов. Однако их количество будет слишком велико (в соответсвии с большим количеством всех возможных комбинаций этих признаков). Это также повлечет значительное усложнение грамматики]. Например, терминальные символы в (4) заменяются на составные (комплексные) символы и получаем (4’ ).

S

NPVP

NPRVVP

NP

JohnwantedPV