Реферат: Дерево непосредственных составляющих
выполняется для узла А, если строка соответствующая ответвлению от узла А, является 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