|
|
|
|
Дерево непосредственных составляющих (ДНС) обеспечиваает структорное описание предложений. Граматика непосредственных составляющих (ГНС) характеризует ДНС. И то и другое поэтому играют важную роль в обработке естественного языка для создания структурных описаний предложения, которые могут быть использованы в обработке систем понимания или порожления речи.
Дерево непосредственных составляющих:
ДНС кодирует иерархическую структуру предложения. Эта информация двух видов: иерархическая структура группирования и синтаксические категории этих группирований.
Предложение
John wanted to publish the paper. (1)
имеет следующую структуру:
(2)
John wanted to publish
the paper
Эта структура может быть представлена и в скобочной конструкции:
[[John][[wanted][[to][publish][[the][paper]]]]] (3)
(2) и (3) описывают группирование без идентификации составляющих. Такие конструкции называются "скелетом". Скелеты характеризуют фразу без обозначения вершин дерева. Скелет с обозначением категорий является ДНС, для фразы (1) это будет выглядеть так
S
NP VP
VP
NP (4)
NPR V P V
DET N
John wanted to publish
the paper
"John" является здесь именем собственным, которое является также группой подлежащего, "wanted" и "publish" - глаголы, "to"- предлог (точнее говоря "to" должно быть названо частицей или временем), "the" - детерминатор, "paper" - существительное, "the paper" - группа существительного, "to publish the paper" - группа сказуемого, "wanted to publish the paper" - тоже группа сказуемого, и наконец, "John wanted to publish the paper" - предложение.
Соответственно скобочная конструкция (3) будет выглядеть так:
[S[NR[NPR John]][VP[V to][V publish][NP[DET the][N paper]]]]] (5)
Конструкции (4) и (5) обычно (но не всегда) используются в системах обработки естественного языка.
Грамматика непосредственных составляющих (ГНС)
ГНС состоит из набора нетерминальных символов (таких как N, V, NP, VP, S и т.д.) и из набора терминальных символов (таки лексические единицы как John "wanted", "to", "publish", "the", "paper" и т. д. и из набора правил, которые позволяют переписывать нетерминальные символы в цепочку терминальных и нетерминальных симвлов. Если это переписывание не зависит от контекста, то это контексто-независимая грамматика (КНГ), в противном случае - это контекстозависимая грамматика (КЗГ). Правило перезаписи имеет следующую форму:
А --> Х (6)
где Х - последовательсть терминальных и нетерминальных символов, а А - нетерминальные.
КЗГ имеет иследующее правило перезаписи:
ZAW --> ZXW (7)
где X, Z, W - цепочки терминальных и нетерминальных символов, а А - нетерминальные.
В (7) А и Х находятся в окружении Z и W. Часто эта формула пишется в виде
A --> X (Z - W (8)
Деревация в КНГ начинается с начального символа S и далее идет до тех пор, пока не будет применено последнее правило. Порядок применения правил не важен.
S -> NP VP
NP -> NPR
NP -> DET N
VP -> V VP
VP -> P V NP
NPR -> John, Mary, Bill
N -> paper, man, cow
V -> wanted, meet, want
P -> to
DET -> the
Несколько формальных свойств ГНС:
Если все правила некоторой ГНС G являются контекстно сводными, то G называется контекстно свободной грамматикой (КСГ). Если некоторые правила ГНС являются контекстно зависимыми, то G разывается КЗГ.
Строчный язык некоторой ГНС G определяется как набор всех конечных строк, полученных из G и этот набор обозначается L(G). Строка w считается полученной из G, если w можно получить при последовательном переписывании начального символа S, используя правила грамматики G. Строчный язык L (т.е. набор конечнных строк) называется контексто свободным языком (КСЯ), если существует такая КСГ, что L(G)=L. L называется "строго контекстно зависимым языком", если не существует такой КСГ, что КСГ, что L(G)=L, и существунт такая КЗГ, что L(G)=L. Заметьте, что грамматика G может быть контекстнозависимой, но ее строчный язык L(G) не обязательно должен быть КЗЯ. Класс КЗЯ включает класс КСЯ. В этом смысле, КЗЯ являются более мощным чем КСЯ.
Однако есть и другой случай, когда КЗЯ не являются более мощными чем КСЯ. Если некоторая КЗГ, G, используется для "анализа", в этом случае язык анализируемый при поиощи G - контекстносвободный (6, 7). Для того чтобы объяснить использование КЗГ G для анализа данного дерева t, определим анализ t следующим образом. Груба говоря анализ t представляет собой некий срез дерева. Дадим более точное определение: Набор (Pt) для анализа дерева t определяется следующим образом
1. Если t=( (пустое дерево), тогда Pt = (
2. Если t=
A
t0 t1 .... tn
тогда Pt={A} v P(t0)P(t1)....P(tn) где t0, t1 ....tn - деревья, А " . " обозначает соединение; например:
S
A B
C d E
c e
Pt = {S, AB, AE, Ae, CdB, CdE, Cde,cdB, cdE, cde}
Пусть G - контекстно зависимая грамматика, т.е. ее правила имеют форму
А-->(/( - (
где А ( V - ( (V - алфавит, и ( набор терминальных символов), ( ( V+ (набор ненулевых строк на множестве V) и (, ( ( V* (набор всех строк на V). Если ( и ( - равны нулю, то такое правило называется контекскносвободным. Дерево t называется "анализируемым " в терминах грамматики G, если для каждого узла дерева t выполняются правила G. Контекстно зависимое правило А--> (/( - (
выполняется для узла А, если строка соответствующая ответвлению от узла А, является ( и существует анализ t вида (1(А((2 , где (1, (2 ( V*. Контекстное условие ( - ( называется анализом предиката.
Наряду с контекстозависимымми правилами правилами, позволяющими специфицировать "правый" и "левый" контекст, часто необходимо иметь правила специфицирующие "верхний" и "нижний" контекст. Имеем узел А дерева t, область (( - (), (, ( ( V*, содержит узел А, если существует путь от корня до края дерева, и этот путь имеет форму
(1(А((2 ((1, (2 ( V*).
Контекстное условие, связанное с таким "вертикальным" анализом называется "господствующим предикатом".
В общем виде правило имеет форму
А -->(/СА
где СА - булева комбинация анализа и господствующих предикатов.
Пусть G - конечный набор правил и ((G) - набор деревьев, анализируемый G. Предполагается, что деревья ((G) - предложения; т.е. корневой узел дерева ((G) обозначен начальным символом S, а конечные узлы - терминальными символами. Покажем, что строчный язык L(((G)) = {x?x, где х терминальная строка дерева t, и t ( ((G)} контекстно свободен (7).
Пример: Пусть V = {S, T, a, b, c, e} и ( = {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 --> e S --> aT1
S --> aT T--> aS1
T --> aS T1--> bSc
S1-->bTc