Деревонепосредственных составляющих ДНС обеспечиваает структорное описаниепредложений.Граматика непосредственных составляющих ГНС характеризует ДНС. Ито и другое поэтому играют важную роль в обработке естественного языка длясоздания структурных описаний предложения, которые могут быть использованы в обработке систем понимания илипорожления речи. Дерево непосредственных составляющих ДНСкодирует иерархическую структуру предложения. Эта информация двух видов иерархическая структура группирования исинтаксические категории этих группирований.
Предложение John wanted to publish the paper. 1 имеет следующую структуру 2 John wanted to publish the paperЭта структура может бытьпредставлена и в скобочной конструкции John wanted to publish the paper 3 2 и 3 описывают группирование без идентификации составляющих.Такиеконструкции называются скелетом . Скелеты характеризуют фразу без обозначениявершин дерева. Скелет с обозначением категорий является ДНС, для фразы 1 этобудет выглядеть так SNP VP VP NP 4 NPR V P V DET NJohn wanted to publish the paper John является здесь именем собственным, которое является также группой подлежащего, wanted и publish - глаголы, to - предлог точнее говоря to должно быть названо частицей или временем , the - детерминатор, paper - существительное, thepaper - группа существительного, to publish the paper - группа сказуемого, wanted to publish the paper - тоже группа сказуемого, и наконец, John wantedto publish the paper - предложение.
Соответственно скобочнаяконструкция 3 будет выглядеть так S NR NPR John VP V to V publish NP DETthe N paper 5 Конструкции 4 и 5 обычно но не всегда используются в системах обработки естественного языка.Грамматиканепосредственных составляющих ГНС ГНСсостоит из набора нетерминальных символов таких как N, V, NP, VP, S и т.д. и из набора терминальныхсимволов таки лексические единицы какJohn wanted , to , publish , the , paper и т. д. и из набора правил, которые позволяют переписыватьнетерминальные символы в цепочку терминальных и нетерминальных симвлов.
Еслиэто переписывание не зависит от контекста, то это контексто-независимаяграмматика КНГ , в противном случае - это контекстозависимая грамматика КЗГ .Правило перезаписи имеет следующую форму А gt Х 6 гдеХ - последовательсть терминальных и нетерминальных символов, а А -нетерминальные.КЗГимеет иследующее правило перезаписи ZAW gt ZXW 7 гдеX, Z, W - цепочки терминальных и нетерминальных символов, а А - нетерминальные.В 7 А и Х находятся в окружении Z и W. Часто эта формула пишется в виде A gt X Z W 8 Деревацияв КНГ начинается с начального символа S и далее идет до тех пор, пока не будетприменено последнее правило.
Порядокприменения правил не важен.
S gt NP VP NP gt NPR NP gt DET N VP gt V VP VP gt P V Несколькоформальных свойств ГНС Есливсе правила некоторой ГНС 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 f2.Если t A t0 t1 tnтогдаPt A vP t0 P t1 P tn где t0, t1 tn - деревья, А . обозначает соединение например S A B C d E c ePt S, AB, AE, Ae, CdB, CdE, Cde,cdB, cdE, cde ПустьG - контекстно зависимая грамматика, т.е. ее правила имеют форму А gt w p - fгдеА V - S V - алфавит, и S набор терминальных символов , w V набор ненулевых строк на множестве V и p, f V набор всехстрок на V . Если p и f - равны нулю, то такое правило называетсяконтекскносвободным.
Дерево t называется анализируемым в терминах грамматики G, если для каждого узла дерева tвыполняются правила G. Контекстно зависимое правило А gt w p - fвыполняетсядля узла А, если строка соответствующая ответвлению от узла А, является w и существует анализ t вида r1pАfr2 , где r1, r2 V . Контекстное условие p - f называется анализом предиката. Нарядус контекстозависимымми правилами правилами, позволяющими специфицировать правый и левый контекст, часто необходимо иметь правила специфицирующие верхний и нижний контекст.
Имеем узел А дерева t, область p - f , p, f V , содержит узел А, если существует путь от корня докрая дерева, и этот путь имеет форму r1pАfr2 r1, r2 V . Контекстноеусловие, связанное с таким вертикальным анализом называется господствующимпредикатом .Вобщем виде правило имеет формуА gt w САгдеСА - булева комбинация анализа и господствующихпредикатов.ПустьG - конечный набор правил и t G - набор деревьев, анализируемый G. Предполагается, что деревья t G - предложения т.е. корневой узел дерева t G обозначен начальным символом S, а конечные узлы -терминальными символами.
Покажем, что строчный язык L t G x frac12 x, где х терминальная строка дерева t, и t t G контекстно свободен 7 .Пример Пусть V S, T, a, b, c, e и S a, b, c, e , и G - конечный набор строгих правил.1.S gt e2.S gt aT3.T gt aS4.S gt bTc a DOM T 5.T gt bSc a DOM S Дляправил 1, 2, 3 имеет место нулевой контекст и эти правила -контекстносвободные.
В четвертом и пятом правиле по условию требуется а слева иузел подчиняется Т в пятом правиле S .Язык,порожденный G, может быть порожден G1 S gt e S gt aT1S gt aT T gt aS1T gt aS T1 gt bSc S1 gt bTcГрамматикаG1содержит дополнительные нетерминальные символы S1 и Т1 для проверкилокального контекста при порождении.
Легко заметить, что при помощи S1 и Т1, достигаетсягомоморфизм, позволяющий анализировать любое дерево G1 при помощи G иобратно - любое дерево G имеет гомоморфный прообраз в G1. Рассмотрим еще раз контекстно зависимоеправило 10 . V gt wanted frac12 -VP когда 10 интерпретируется как ложноеправило, как описано выше, лексема wanted появляется над узлом V, только еслиузел VP находится справа от нее в дереве, где появляется V . Справа от Vсуществует строка, имеющая VP анализ . Контекстно-зависимые правила в КГЗиспользуются для анализа обычных грамматик, а не есть правила простогопереписывания строк.
Терминальныесимволы в ГНС. До этого моментатерминальные символы были представленыкак нереализуемые элементы.
Это было сделано для простоты изложения.Терминальные символы представляют собой наборы топологических, синтаксических исемантических признаков 4, 8 . В принципе возможно ликвидировать все этипризнаки посредством введения новых нетерминальных символов.
Однако ихколичество будет слишком велико в соответсвии с большим количеством всехвозможных комбинаций этих признаков . Это также повлечет значительноеусложнение грамматики . Например, терминальные символы в 4 заменяются насоставные комплексные символы и получаем 4 . SNP VP NPR V VP NPJohn 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ГНСв трансформационной грамматике ТГ .ТГтакже не обсуждаются в этой статье.
Однако важно заметить, что ГНС и деревья НС играют важную роль в ТГ.Основная идея заключается в том, что некоторые структурные описания СО описываются в базовом компоненте ТГ, а все остальные выводятся из них припомощи специальных правил, называемыхтрансформациями.
Базовым компонентом является ГНС, которая определяет набордеревьев НС. Деревья, полученные при помощи трансфомаций также являютсядеревьями НС. Такой взгляд на ТГ является классическим и, конечно, упрощенным,хотя и достаточен для данного описания.
Так, например, дерево НС для предложения 11 , показанное на диаграмме 12 -является базовым. Дерево НС 14 для предложения 13 , получается приприменении трансформационного правила. John saw Mary SNP AUX VPNPR V NPJohn past see NPK MaryMarywas seen by John. SNP AUX VPNPR.