АНАЛИЗ ПРЕДЛОЖЕНИЯ В ФОРМАЛЬНОМ СИНТАКСИСЕ

Мирзабеков Яхья Мирзабекович

преподаватель кафедры дискретной математики и информатики ДГУ,

г. Махачкала

E-mail: yash831@mail.ru

Магомедова Римма Магомедовна

студентка 4 курса 4 группы факультета математики и компьютерных наук ДГУ, г. Махачкала

E-mail: rimma069650@yandex.ru

ANALYSIS OF SENTENCE IN FORMAL SYNTAX

Yakhya Mirzabekov

 lecturer of department «Discrete mathematics and informatics» of faculty of Mathematics and computer sciences of DSU, Makhachkala

Rimma Magomedova

student 4 rotes 4 groups of faculty of Mathematics and computer sciences

 of DSU, Makhachkala

АННОТАЦИЯ

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

ABSTRACT

In article is considered a task, in which syntax analysis of sentence comes to tree’s search in given graph. By narrow place in algorithm of solution of this task is fragmentation of members of sentences through branches of sought for tree. In article is suggested rules of placing of commas in sentence, which particularly makes easy the solution of task.

Ключевые слова: синтаксис; граф; дерево; предложение.

Key words: syntax; graph; tree; sentence.

Компьютерный анализ текста начинается с анализа предложений текста. Анализ предложения начинается с морфологического анализа членов предложения: для каждой словоформы определяется ее исходная форма и морфологический признак. Например, результатом анализа словоформы «анализам» будет пара (анализ, 01 12 21 33), где 01 — код имени существительного (ИС), за которым расположен его морфологический признак из четырех морфологических операторов — двузначных чисел, у которых старшая цифра — код морфологической категории (1 — число, 2 — род, 3 — падеж), а младший разряд — значение категории (1 — единственное число, 1 — мужской род, 3 — дательный падеж).

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

Синтаксис начинается с построения словосочетаний — выделения правильно построенных пар из словоформ этого языка. На этом этапе важно одно: сколько форм у каждого слова. Морфология словоформы может быть интересна только для их классификации при оптимизации работы анализатора. Морфологические анализаторы для лексики русского и английского языков имеют разного порядка сложности.

С другой стороны, моделирование языка — один из способов его изучения. Упрощая грамматику от несущественных для языка особенностей, можно принципиально облегчить и ускорить процесс исследования языка путем моделирования и имитации на компьютере основных конструкций языка. Под упрощением морфологии русского языка подразумевается не сокращение числа морфологических категорий и их значений, упрощаются правила распознавания словоформ путем включения информации о ее морфологическом признаке в состав самой словоформы. Например, замена словоформы «анализам» словом «анализ01122133» непрактична. Можно деформировать окончания слов таким образом, что все формы имен с морфологическим признаком «01122133» имели окончание «ам», морфологическому признаку «01122135», чтобы соответствовало окончание «ами» и т. д.

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

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

От такого упрощения морфологии не упрощает синтаксис языка. Для упрощения синтаксиса можно использовать иные приемы. Например, с категориями удобно работать, если их кодировать. Например, число (единственное, множественное)=1(1,2)=(11,12) или падеж (И, Р, Д, В, Т, П)=3(1,2,3,4,5,6)=(31, 32, 33, 34, 35, 36). Формы ИС определяются 12 функциями суперпозиции двух категорий 1 и 3: 1*3=(11, 12)*(31, 32, 33, 34, 35, 36)=(1131, 1132, 1133, 1134, 1135, 1136, 1231, 2232, 1233, 1234, 1235, 1236). Например, 1235(дом)=домами или (дом, 1235)= домами. Для полноты кода признаки словоформ дополняются кодом части речи, Например 1235 будет расширен до 011235, где 01 — код ИС.

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

Признак (код) словоформы определяет лексическую группу словоформ. Например, 011235 — множество ИС в форме множественного числа и творительного падежа.

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

Произведение двух лексических групп определяет множество словосочетаний (связанных пар). Например, произведением 011131 x 011132 обозначается множество словосочетаний, главными членами которых являются ИС в именительном падеже, а зависимыми членами - ИС в родительном падеже. Оба члена имеют форму единственного числа. Информативность выражения «011131 x 011132» не пострадает, если знак умножения удалить, так как признак словоформы имеет единственный нуль в начале кода. Пара признаков X и Y может задавать синтаксическое отношение, то есть множество XY, словосочетания из которого являются допустимыми для данного языка.

Конечный набор синтаксических отношений WR определяет ориентированный граф Sint=(FW, R)на множестве словоформ FW, где R— объединение множеств из WR. Этот граф называется синтаксическим графом или синтаксисом. Синтаксис порождает предложения. Предложениями в синтаксисе Sint называются корневые деревья, удовлетворяющие следующим условиям.

В лексике выделены две группы словоформ subject и predicate. Корневое дерево T в графе Sint называется синтаксически правильно построенным предложением (далее называется, просто, предложением), если из каждого множества subject и predicate присутствует в T по одному элементу (главные члены предложения), которые связаны между собой дугой. Корнем предложения является слово из subject.

Пусть предложение-дерево задано в скобочной форме, например, T=a(b(c), d(e, f(g)), h). Язык трансформирует двумерную структуру дерева T в линейную цепь словоформ в виде предложения-последовательности (или, просто, предложения): a b c d e, f g h. Задача синтаксического анализа предложения заключается в построении предложения-дерева по заданному предложению. Она сводится к нахождению в графе Sint корневого дерева с заданным множеством вершин и является NP-полной задачей [2].

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

Для упрощения алгоритма анализа предложения можно воспользоваться процедурой одностороннего обхода дерева. Пусть вершины корневого дерева нумерованы натуральными числами. Обход дерева начинается с корня и состоит из следующих перемещений по дереву. Выход из текущей вершины vв соседнюю вершину w по дуге (v, w). Если вершина w— висячая, то возврат к соседней вершине vи удаление из дерева дуги (v, w). Обход завершается в корне, из которого уже не выходит ни одна дуга.

Результатом обхода дерева является последовательность чисел: при выходе из вершины в последовательность добавляется ее номер, при возвращении в вершину в последовательность добавляется ее номер со знаком минус. При обходе дерева a(b(c), d(e, f(g, r)), h)получится последовательность:

a, b, c, -b, -a, a, d, e, -d, d, f, g, -f, f, r, -f, -e, -d, -a, a, h, -a                                            (1)

Если удалить из последовательности (1) номера с минусом и запятые между номерами без минуса, то полученная таким образом последовательность

a b c, a d e, d f g, f r, a h                                                                      (2)

однозначно определяет обход (1). Если в грамматике русского языка пересмотреть правила расстановки запятых, то синтаксический анализ предложения из NP-полной задачи превратится в задачу линейной сложности.

Предложение

Прилежный ученик шестого класса пишет диктант в светлом, уютном классе

имеет структуру, изоморфную дереву a(h, b(c), d(e, f(g, r))). Обход данного предложения-дерева в виде (2) имеет вид:

Ученик прилежный, ученик класса шестого,

пишет диктант в классе светлом, в классе уютном

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

Список литературы:

1. Грамматика русского языка — М.: Издательство Академии Наук СССР, т. т. 1—3,1960.
2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. — М.: Мир, 1982. — 416 с.
3. Шихиев Ф.Ш. Формализация и сетевая формулировка задачи синтаксического анализа. Диссертация на к.ф.-м.н.: — СПб.: СпбГУ, 2006.— 16 с.