4.5.4. Цели и задачи синтаксического анализа (са), основные проблемы, возникающие при описании синтаксических связей, а также формальные модели синтаксической структуры предложения

Приведем наиболее общее и абстрактное определение СА, позволяющее охватить весь спектр приложений синтаксических методов. СА называется процесс структурирования линейной репрезентации в соответствии с заданной грамматикой. Алгоритмы СА берут свое начало в формальных синтаксических теориях естественного языка, моделирующих механизм распознавания человеком языковых структур.

При разработке алгоритмов сегментационного, полного синтаксического анализа, особенно для языков с относительно свободным порядком слов, каким являются русский и украинский, существует ряд трудностей, поскольку формальные математические модели и их программные динамические реализации не способны охватить всю сложность и многообразие языковой системы. Кроме того, применение формализма для структурирования предложения естественного языка, учитывающего вышеперечисленные типы связей, зачастую приводит к потере правильного синтаксического представления или комбинаторному взрыву, когда программа оказывается не в состоянии просчитать все возможные варианты структур.

Проблемы, возникающие при построении синтаксической структуры

Лингвистически мотивированные причины такого «провала» – явление омонимии, длина связи между словами, сложность сегментной структуры предложения, выраженная в сочинительных конструкциях.

Среди многочисленных систем составляющих, которые могут быть выделены в предло­жении естественного языка, лишь немногие «правильны», т. е, отражают принятые в лингвистике соглашения о синтаксической структуре предложения данного языка. Предложение может иметь несколько «правильных» систем составляющих, соответ­ствующих различным толкованиям предложения. Это явление называют синтаксической омонимией.

Пример:

1. Для зависимого слова можно найти разных «хозяев»: Он умеет заставить себя слушать(заставить себя, или себя слушать);Сергей вернулся из командировки в Москву(вернулся в Москву или командировки в Москву);Мы встретили сына художника, приехавшего из Парижа(сына приехавшего или художника приехавшего);Роняет лес багряный свой убор (багряный лес или багряный убор). Такую омонимию называютстрелочной, потому что разные смыслы конструкции можно отобразить с помощью разных стрелок.

2. Пара «хозяин — слуга» выделяется единственным способом, но проинтерпре- тировать связь между этими словами можно по-разному: Преследование тигра закончилось неудачей(тигр преследует кого-то или кто-то преследует тигра). Такой вид омонимии называетсяразметочной.

3. Рядом расположенные слова могут по-разному объединяться в группы. В концерте приняли участие известные ансамбли и самодеятельные коллективы(прилагательноеизвестныеотносится только к существительномуансамблиили также кколлективы). Такая омонимия называетсяконституентной.

Рассмотренные типы омонимии могут комбинироваться между собой. Например, в словосочетании звонок любимой из Парижаесть разметочная омонимия в паре словзвонок любимой(кому? или чей?) и стрелочная омонимия: неоднозначно определяется «хозяин» для формыиз Парижа(звонок из Парижа или любимой из Парижа). Комбинация этих возможностей даёт четыре способа понимания словосочетания.

С точки зрения цели СА можно выделить два основных подхода: одноцелевой и многоцелевой. При первом подходе для фразы требуется построить одно синтаксическое представление, этот подход характерен для первых алгоритмов СА, когда считалось, что синтаксических средств достаточно для того, чтобы обеспечить правильный анализ фразы, хотя бы для большинства фраз. При втором подходе для фразы требуется получить все те синтаксические представления, которые удовлетворяют определенным соглашениям (все «правильно построенные» представления). Вопрос о том, какое из этих представлений является не только правильно построенным, но и правильным, т.е. соответствующим смыслу анализируемой фразы, в рамках СА не решается.

Одним из основных компонентов лингвистической базы знаний, осуществляющей автоматический СА, является описательная модель синтаксической структуры предложения. Такая модель в значительной степени передает концепцию разработчиков относительно синтаксического уровня анализа: какая именно информация об элементах предложения и их взаимосвязях должна выявляться в процессе анализа, присутствовать в его результатах и какие формы представления ей адекватны. Наиболее общим для разработчиков синтаксических анализаторов является взгляд, что синтаксическое строение предложения можно представить некоторым частично упорядоченным множеством бинарных связей между элементами. Виды и свойства элементов, связей и отношения порядка варьируют в разных моделях.

Формальные модели синтаксической структуры предложения

Представления о бинарных синтаксических связях используются в двух известных моделях синтаксической структуры: графах зависимостей и графах непосредственных составляющих. В настоящее время эти две формы представления синтаксической структуры остаются основными. Они используются в чистом виде или очень часто – в смешанных формах, сочетающих в себе свойства обоих графов.

Грамматика зависимостей- указание для каждого слова тех слов, которые ему непосредственно подчинены.

Дерево синтаксических зависимостей - дерево, множество узлов которого служит множеством вхождений слов в предложение. Деревом называется множество, между элементами которого (узлами) установлены бинарные отношения (отношения подчинения), графически изображаемые стрелками, идущими от подчиняющих узлов к подчиненным. Дерево обладает следующими свойствами:

• среди узлов имеется один - корень - неподчиненный никакому другому узлу;

• каждый из остальных узлов подчинен точно одному узлу;

• нельзя, отправившись из какого-либо узла вдоль стрелок вернутся в тот же узел.

Дерево зависимостей обычно используется в описаниях языков со свободным порядком слов, в частности, русского. Стрелки дерева обычно помечаются символами синтаксических отношений (предикативное, определительное и т.п.).

Метод непосредственных составляющих (НС). Для описания синтаксической структуры предложения выделяются группы слов, функционирующие как отдельные синтаксические единицы - составляющие.

Система составляющих - это множество отрезков предложения которое обладает тем свойством, что каждые два входящих в него отрезка либо не пересекаются либо один из них содержится в другом.

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

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

Три уровня описания

1) правила НС

2) трансформационные правила

3) морфологические правила

Допущения:

Синтаксическая система может быть разбита на ряд подсистем, одна из которых - исходная (ядерная), остальные - производные. Ядерная представляет собой набор предложений (утвердительных, простых, с глаголом в изъявительной форме, активного залога, настоящего времени). Ядерное предложение (ЯП) описывает элементарные ситуации, а класс ЯП - все множество элементарных ситуаций. Любой сложный синтаксический тип можно получить при применении упорядоченного набора обязательных и факультативных трансформаций к ЯП.

Представление синтаксической структуры предложения - указание ядерного типа, лежащего в основе предложения и трансформаций, которые к нему применялись, а также их последовательности.

Метод явился основой порождающей грамматики Хомского. Порождающая грамматика Хомского, представляющая собой упорядоченную систему Г =(V,W,J,R), где V и W - непересекающиеся конечные множества - основное (терминальное) и вспомогательное (нетерминальное), J - элемент W, называемый начальным символом и R - конечное множество правил вида j(r)y, где j и y - цепочки (конечные последовательности) из основных и вспомогательных символов. Множество тех цепочек из основных символов, которые выводимы в Г из ее начального символа, называют языком, порождаемым грамматикой Г и обозначают L(Г). Если все правила Г имеют вид caw(r)cyw , где a - вспомогательный символ, y - непустая цепочка, c и w - произвольные цепочки, то Г называется грамматикой составляющих или грамматикой непосредственно составляющих (ГНС).

В грамматиках составляющих на каждом шаге вывода заменяется только один символ, поэтому в них с каждым выводом ассоциируется так называемое дерево вывода. Корень дерева отвечает начальному символу. Каждому символу цепочки, на которую заменяется начальный символ на первом шаге вывода, ставится в соответствие узел дерева, и к нему проводится дуга из корня. Для тех из полученных узлов, которые помечены вспомогательными символами, делается аналогичное построение и т.д. Дерево вывода, рассматриваемое как дерево составляющих предложения, задает на нем систему составляющих. Это делает грамматики составляющих хорошим инструментом для описания естественных и искусственных языков.

Чаще всего основные символы интерпретируются как слова, вспомогательные - как символы грамматических категорий, начальный символ - как символ категории «предложение».

Для построения формальных моделей синтаксической структуры введем несколько понятий.

Произвольную (непустую) по­следовательность словоформ будем называть цепочкой. Число словоформ в цепочке ω будем называть длиной цепочки и обозначать |ω|. Если для каких-либо цепочек ω, φ, η₁, η₂, имеет место равенство ω=η₁φη₂, то будем говорить, что цепочка φ, входит в цепочку ω. Вхождения словоформ в цепочку будем называть ее точками. Если α и β — точки одной и той же цепоч­ки ω = η₁αη₂ = ξ₁βξ₂ и если при этом |η₁| < |ξ₁|, то будем писать α < β или β > α и говорить, что α расположена левее β, а β — правее α. Для любых двух точек α и β цепочки ω, таких, что α ≤ β, введем понятие отрезка цепочки ω, представляющего мно­жество точек ξ, удовлетворяющих неравенствам α ≤ ξ ≤ β.

Граф зависимости

Описание структур в форме классического графа зависимостей хорошо соответствует русской грамматической традиции: оно основывается на понятии бинарного словосочетания в предложении с выделенными главными и зависимыми элементами. Обычно ровно один узел графа в подавляющем большинстве моделей, соответствующий сказуемому, не имеет подчиняющего узла и называется вершиной. Иногда двумя вершинами представляют подлежащее и сказуемое.

Отношение подчинения задает частичный порядок на множестве узлов. Если одному узлу подчиняется сразу несколько узлов, то среди последних порядок не определен: граф зависимостей не передает информацию об относительной степени близости подчиненного слова к главному. Например, граф зависимостей для фразы «программное обеспечение вычислительной техники и автоматизированных систем » (рис.9.1).

Рисунок 9.1 - Граф зависимостей

Как правило, отношение подчинения подразделяется на ряд типов, и дуги графа помечаются индексами синтаксических отношений.

Иногда граф зависимостей одновременно с отношением подчинения задает и отношение линейного порядка следования узлов. Такой граф называется расположенным. Один из способов изображения такого графа представлен на рисунке 9.2.

Рисунок 9.2 - Расположенный граф зависимостей

В большинстве случаев отношение подчинения и отношение линейного порядка слов в предложении связаны законом проективности, который при данном способе изображения формулируется так: никакая дуга, исходящая из некоторого узла, не пересекает других дуг или перпендикуляров, опущенных из более верхних узлов.

Рассмотрим расположение графа в предложениях с подчинительной и сочинительной связями. Изображение всех связей однородных членов между собой, с подчиняющими и подчиненными элементами приводит к возникновению замкнутых контуров в графах зависимостей. Чтобы избежать этого, часто используют представление, при котором сочинительная связь включается в граф зависимостей наравне с другими синтаксическими отношениями, а подчинительные связи, общие для группы однородных членов, изображаются лишь для одного члена группы (рис.9.3).

Рисунок 9.3 - Представление однородности

Пусть х — произвольная непустая цепочка и Х — множество всех точекх.Произвольное бинарное отношениенаX,при котором граф <Х,> является деревом, называютотношением зависимости (подчинения).Само дерево <Х,> называютдеревом зависимостейдлях.Будем изображать дерево зависимостей цепочки ω в виде последовательности обра­зующих ее точек, расставленных на прямой линии. Для всякой пары точек а,bцепочки ω, для которой аb, на рисунке бу­дем проводить дугу из а вb, причем таким образом, чтобы все дуги были по одну сторону от прямой. Еслиab, то будем называть точку ауправляющей точкой(«хозяином»), аb—под­чиненной точкой(«слугой»). На рисунке 9.4 приведены два различ­ных дерева зависимостей для цепочки agbacdef.

При анализе предложений русского языка обычно использу­ют размеченные деревья зависимостей. Размеченное дерево за­висимостейдля цепочких— это четверка<Х, , Z,ψ>, где<Х,>—дерево зависи­мостей длях; Z —конечное множество, элементы которо­го называют метками, иψ— отображение множества дуг дерева<Х,> вZ.

Рисунок 9.4 - Деревья зависимостей для цепочки agbacdef

Привлекательными свойствами графа зависимостей является их экономичность, удобство использования в преобразованиях, возможность представления частичных результатов анализа в виде множества подграфов.

Дерево составляющих

Следует подчеркнуть, что деревья зависимостей дают возможность рассматривать направленные связи, но только между отдельными словами, системы составляющих характеризуют синтаксическую структуру предложения иначе — с их помощью словосочетания (или синтагмы) описываются в явном виде, но игнорируется ориентация связей (т.е. не различаются «хозяин» и «слуга»).

Синтагма — совокупность нескольких слов, объединённых по принципу семантико-грамматической сочетаемости, единица синтагматики. Объём конкретной синтагмы определяется не только реальным употреблением слов в связке, но и самой возможностью объединения предметов, признаков и процессов окружающей действительности. Минимальной длиной синтагмы следует считать простые словосочетания.

В основе модели дерева оставляющих лежит представление об устройстве предложения как о последовательном попарном синтагматическом сцеплении составляющих от минимальных - отдельных слов, до максимальной - предложения, составляющими которого в случае полного личного предложения являются группа подлежащего и группа сказуемого.

Представление синтаксической структуры в терминах дерева составляющих хорошо согласуется с традиционным «разбором» предложения, при котором подлежащее, сказуемое и их элементы описываются категориальными характеристиками – именами частей речи или групп. Например, фраза Бедный Джон убежал прочь будет представлена так , как показано на рисунке 9.5.

Отличительной особенностью модели дерева составляющих является то, что она задает порядок (степень близости между словами) во множестве слов, которые в предыдущей модели подчинялись бы одному и тому же узлу.

Рисунок 9.5 – Схема связей

Здесь  - символ предложения, А – прилагательное, N – существительное, V глагол, А_dv – наречие, NР – именная группа, VР - глагольная группа.

Дерево составляющих передает также соответствие между синтагматикой и линейной упорядоченностью слов в предложении. Нарушение прямого соответствия выражается в форме прерывных (или разрывных) составляющих, которые особенно распространены в языках со свободным порядком слов. Как и в графе зависимостей, в дереве составляющих могут использоваться условные узлы и связи.

Пусть х — произвольная непустая цепочка. Множество С отрезков це­почки х называется системой составляющих этой цепочки, если оно удовлетворяет двум условиям:

1) множество С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки x;

2) любые два отрезка из С либо не пересекаются, либо один из них содержится в другом.

Элементы С называются составляющими. Одноточечные от­резки называются точечными (тривиальными) составляющими.

При описании предложений естественного языка с помощью системы составляющих обычно используют размеченную систе­му составляющих, т. е. тройку <С, W, φ>, где С — система со­ставляющих, W — множество меток и φ — отображение С в 2^W. Поясним введенное определение на примере. Пусть цепочка ω имеет вид agbacdef. Определим на ней две системы составляю­щих C₁ и С₂. Для наглядного изображения системы составляю­щих будем заключать каждую нетривиальную составляющую в скобки, причем левую и правую скобки, отвечающие одной со­ставляющей, помечать одинаковой меткой, так чтобы разные па­ры скобок были помечены разными метками. В качестве меток можно использовать числа.

Пример:

C₁=(((ag)b)ac(de)f);

^{123 3 2 4 4 1}

C₂=(a(g(b(a(cd)e)f))).

^{1 2 3 4 5 5 4 321}

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

Система составляющих предложения указывает в нем словосочетания разных «уровней» не вводя при этом никакой иерархии среди словосочетаний од­ного уровня. Между тем в предложении естественного языка часто интуитивно ощущается «главенствование» некоторого сло­восочетания над другими, в нем не содержащимися. Для отра­жения указанного факта можно поступить следующим образом. Пусть С — система составляющих цепочки х. Для каждой пото­чечной составляющей АС выделим в множестве всех состав­ляющих, непосредственно вложенных в А, какую-либо одну со­ставляющую A', которую будем называть главной. Множество всех главных составляющих обозначим через С' и назовем иерархизацией системы С. Упорядоченную пару <С, С’> назовем иерархизированной системой составляющих.

В грамматике НС представление о двусоставности предложения сохранено. Но члены предложения (синтаксические функции) определяются в этой теории на основе формальных признаков: не по отношению к их возможному или реальному семантическому содержанию, а по отношению к тому месту, которое они занимают в дереве порождения предложения. Как уже было сказано, верхний узел дерева обозначается символом S (sentence – предложение). Предложение анализируется как конструкция, включающая две НС – именную группу (NP, noun phrase) и глагольную группу (VP, verb phrase). Подлежащее и сказуемое могут быть соответственно определены как узлы, непосредственно подчинённые узлу S. Дополнение может квалифицироваться как узел, который подчинён узлу VP. НС – структуру предложения можно представить в виде древовидного графа и в скобочной записи (значение символов: S – предложение, NP – именная группа, VP – глагольная группа, Adj – прилагательное, N – существительное, V – глагол). Например, для предложения Маленькие дети доставляют большие хлопоты скобочная запись будет иметь вид:

(((маленькие)_Adj (дети)_N)_NP ((доставляют)_V ((большие)_Adj (хлопты)_N)_NP)_VP)_S)

Дерево же составляющих показано на рисунке 9.6.

Рисунок 9.6. – Дерево составляющих для предложения

Маленькие дети доставляют большие хлопоты

Выбор того или иного способа представления синтаксической структуры в значительной степени связан с устройством алгоритма СА. Для жестко заданных процедур, вычисляющих синтаксическую структуру предложения по «формуле» правильной структуры, в качестве такой формулы плохо подходит модель типа граф зависимостей: она либо не доопределяет процедуру построения синтаксической структуры и тогда появляется слишком много вариантов анализа, либо, если использовать сильные ограничения, формула становится слишком сложной для вычисления.

В психолингвистических экспериментах доказано, что двухвершинная модель непосредственно составляющих лежит в основе механизма распознавания высказывания (в то время как в основе механизма порождения высказывания лежит модель синтаксиса зависимостей. Следует отметить, что в прикладной лингвистике, строя представления предложения, в основном, оперируют моделями синтаксиса зависимостей и синтаксиса составляющих, описанных выше.

Формальные грамматики работают, как правило, с синтаксическим представлением в виде дерева составляющих.

Грамматика деревьев служит не для порождения предложений, а для преобразования деревьев, интерпретируемых как деревья подчинения или деревья составляющих, например грамматика – система правил преобразования деревьев, интерпретируемых как «чистые» деревья подчинения предложений (без линейного порядка слов).

Грамматики синтаксического уровня

Грамматики синтаксического уровня – наиболее разработанная часть и с точки зрения лингвистики, и с точки зрения их обеспечения формализмами. Все они основаны на порождающей грамматике Хомского. Порождающая грамматика Хомского представляет собой упорядоченную систему Г =(V,W,J,R), где V и W – непересекающиеся конечные множества – основное (терминальное) и вспомогательное (нетерминальное), J – элемент W, называемый начальным символом и R – конечное множество правил вида j(r)y, где j и y – цепочки (конечные последовательности) из основных и вспомогательных символов. Множество тех цепочек из основных символов, которые выводимы в Г из ее начального символа, называют языком, порождаемым грамматикой Г и обозначают L(Г). Если все правила Г имеют вид caw(r)cyw , где a – вспомогательный символ, y – непустая цепочка, c и w – произвольные цепочки, то Г называется грамматикой составляющих или грамматикой непосредственно составляющих (ГНС). Укажем основные типы грамматик и реализующих их алгоритмов.

Цепочечная грамматика фиксирует порядок следования элементов, т.е. линейные структуры предложения, задавая их в терминах грамматических классов слов (существительное+предлог...) или в терминах функциональных элементов (подлежащее+сказуемое). Примером реализации такой языковой модели является предсказуемостный синтаксический анализ: идентифицированная грамматическая категория слова предсказывает (с определенной долей вероятности) появление грамматической категории следующего за ним слова.

Грамматика составляющих (или грамматика непосредственно составляющих – ГНС) фиксирует лингвистическую информацию о группировке грамматических элементов, например, именная группа (состоит из существительного, прилагательного и других модификаторов), предложная группа (состоит из предлога и именной группы) и т.д. до уровня предложения. Грамматика строится как набор правил подстановки, или исчисление продукций вида А →В→...С. ГНС представляют собой грамматики порождающего типа и могут использоваться как при анализе, так и при синтезе: – предложения языка порождаются многократным применением таких правил. В грамматиках составляющих на каждом шаге вывода заменяется только один символ, поэтому в них с каждым выводом ассоциируется так называемое дерево вывода. Корень дерева отвечает начальному символу. Каждому символу цепочки, на которую заменяется начальный символ на первом шаге вывода, ставится в соответствие узел дерева, и к нему проводится дуга из корня. Для тех из полученных узлов, которые помечены вспомогательными символами, делается аналогичное построение и т.д. Дерево вывода, рассматриваемое как дерево составляющих предложения, задает на нем систему составляющих. Это делает грамматики составляющих хорошим инструментом для описания естественных и искусственных языков. Чаще всего основные символы интерпретируются как слова, вспомогательные – как символы грамматических категорий, начальный символ – как символ категории «предложение».

Грамматика зависимостей задает иерархию отношений элементов предложения (главное слово определяет форму зависимых). Анализатор в такой грамматике основан на идентификации хозяев и их зависимых (слуг). Главным в предложении является глагол в личной форме, так как он определяет число и характер зависимых существительных. Стратегия анализа в грамматике зависимостей: сверху вниз, т.е. сначала идентифицируются хозяева, затем слуги; или снизу вверх, т.е. хозяева определяются процессом подстановки.

Появление исчисления высказываний, или «булевой алгебры», предоставило математический аппарат для определения значений истинности сложных утверждений на основании значений составляющих его простых компонентов, если они объединены с помощью логических связок И, ИЛИ, НЕ, импликации, тождества. Исчисление высказываний бедно выразительными средствами и не позволяет описывать дедуктивные рассуждения. Естественным развитием исчисления высказываний является исчисление предикатов.