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

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

Дерево непосредственных составляющих: ДНС кодирует иерархическую структуру предложения. Эта информация двух видов: иерархическая структура группирования и синтаксические категории этих группирований.

Предложение 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=f (пустое дерево), тогда Pt = f 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 - контекстно зависимая грамматика, т.е. ее правила имеют форму А-->w/p - f где А V - S (V - алфавит, и S набор терминальных символов), w V+ (набор ненулевых строк на множестве V) и p, f V* (набор всех строк на V). Если p и f - равны нулю, то такое правило называется контекскносвободным.

Дерево t называется “анализируемым ” в терминах грамматики G, если для каждого узла дерева t выполняются правила G. Контекстно зависимое правило А--> w/p - f выполняется для узла А, если строка соответствующая ответвлению от узла А, является 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 --> e S --> aT1 S --> aT T--> aS1 T --> aS T1--> 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 NP VP NPR V VP NP John wanted P V +N +V DET N -DET- + - NP [to] publish +Animate . +V the paper + - NP + DET +N +Definite + DET - + Singilar Здесь не обсуждается возможность связи комплексных символов и промежуточных узлов. Форма (4’) является структурным описанием (СО) предложения (1): John wanted to publish the paper ГНС в трансформационной грамматике (ТГ). ТГ также не обсуждаются в этой статье.

Однако важно заметить, что ГНС (и деревья НС) играют важную роль в ТГ. Основная идея заключается в том, что некоторые структурные описания (СО)описываются в базовом компоненте ТГ, а все остальные выводятся из них при помощи специальных правил, называемых трансформациями.