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

На правах рукописи

005018966

Манушкин Евгений Сергеевич

Метод автоматического предсинтаксического анализа проектной документации с использованием КС-грамматик

Специальность 05.13.12 Системы автоматизации проектирования (информатика) (технические науки)

Автореферат

диссертации на соискание ученой степени кандидата технических наук

3 МАП 2012

Москва 2012

005018966

Работа выполнена на кафедре «Информационные технологии и автоматизированные системы» Московского государственного института электроники и математики (технический университет)

Научный руководитель: кандидат технических наук, доцент

Клышинский Эдуард Станиславович

Официальные оппоненты: доктор технических наук, профессор

Майков Константин Анатольевич

Ведущая организация:

кандидат технических наук, старший

преподаватель

Лебедев Андрей Сергеевич

Учреждение Российской Академии Наук Институт прикладной математики им. М.В. Келдыша РАН

Защита состоится «22» мая 2012 г. в «14» часов на заседании диссертационного совета Д 212.133.03 при Московском государственном институте электроники и математики (техническом университете) по адресу: 109028, г. Москва, Б. Трехсвятительский пер., д.З.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технический университет)

Автореферат разослан: «"2 (» 09 2012 г.

Ученый секретарь диссертационного совета д.т.н., доцент Леохин Ю.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Одной из задач систем автоматизированного проектирования является систематизация хранения данных об изделии и приведение всей документации к единому стандарту. В этой области широко используются CALS-технологии. Составными частями CALS являются такие технологии, как ILM (Information Lifecycle Management) и PDM (Product Data Management). Основной задачей ILM-систем является хранение документации на изделие. Кроме того, ILM-системы отвечают за процессы хранения, распределения, миграции, архивировании и удаления данных в инфраструктуре предприятия. PDM системы позволяют управлять данными об изделии и информационными процессами жизненного цикла изделия, которые создают и используют эти данные.

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

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

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

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

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

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

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

Задачи исследования:

1. Анализ существующих методов синтаксического анализа и систем, использующих этап синтаксической сегментации.

2. Разработка алгоритма преобразования правил в формате расширенных БНФ в правила в формате расширенных сетей переходов (АТЫ).

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

4. Разработка метода автоматического предсинтаксического анализа проектной документации с использованием КС-грамматик.

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

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

На защиту выносятся следующие основные положения:

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

• Метод автоматического предсинтаксического анализа проектной документации с использованием КС-грамматик

Научная новизна выполненной работы.

1. Предложен алгоритм эквивалентного преобразования грамматики расширенных БНФ в грамматику ЛТГЧ.

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

3. Предложен новый метод, позволяющий проводить этап предсинтаксического анализа в системах анализа проектной документации, использующих грамматики расширенных БНФ и АТО.

4. Разработан метод тестирования качества и производительности результатов, полученных в диссертационной работе.

Практическая значимость результатов. Предложено новое техническое решение, позволяющее ускорить работу этапа синтаксического анализа текстов проектной документации. Решение использует только информацию о правилах синтаксического анализа, записанных в форме БНФ или А'ГЫ. Это позволяет разработчикам систем синтаксических анализаторов реализовывать этап синтаксической сегментации текста практически без затрат времени на разработку правил сегментации и без обязательного привлечения профессионалов в области компьютерной лингвистики, что в результате сокращает финансовые затраты и время, необходимые на разработку системы. В свою очередь проведение этапа синтаксической сегментации позволяет значительно увеличить производительность систем анализа проектной документации.

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

Достоверность и обоснованность полученных результатов подтверждается:

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

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

■ • результатами внедрения разработанных методов и рекомендаций в практику.

Реализация и внедрение результатов. Алгоритмы и методы, описанные в данной работе, реализованы автором в компьютерной программе. Программа создавалась как с целью апробации и совершенствования разрабатываемых методов и алгоритмов, так и с целью практического использования в машинном переводчике "Кросслейтор", разрабатываемом в ИПМ им. М.В. Келдыша РАН и при выполнении гос. контракта П-261 в рамках ФЦП "Научные и научно-педагогические кадры инновационной России" на 2009-2013 гг., заключенного между Министерством образования и науки и МИЭМ. Результаты работы обсуждались на научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» в 2009 и 2010 гг.

Публикации. Всего автором опубликовано 8 научных работ из них 2 в журналах из перечня ВАК.

СОДЕРЖАНИЕ РАБОТЫ Во введении дается обоснование актуальности темы диссертационной работы, определяется направленность исследования, формулируются цели и задачи исследования, определяется научная новизна и практическая значимость результатов.

В первой главе рассмотрены некоторые задачи, в которых необходим анализ текстов проектной документации, а также роль и задачи синтаксического анализа, без которого не может обойтись практически ни одна система полного анализа текста на естественном языке. Также в первой главе рассмотрены методы и подходы к синтаксическому анализу, в том числе в системах, выполняющих синтаксическую сегментацию. Для внедрения новых способов интеллектуальной обработки данных в рамках CALS-идеологии необходимо использовать методы автоматической обработки текстов (АОТ) на естественном языке. Это в первую очередь связано с тем, что большая часть документации на изделие состоит из текстового описания проекта. Применение таких методов позволяет переработать текстовую информацию, содержащуюся в

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

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

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

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

производительностью, однако, к сожалению, не обладает высокой точностью, которой обладает полный синтаксический анализ.

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

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

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

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

На данный момент системы, позволяющие проводить полный синтаксический анализ, можно условно разделить на две категории: системы, использующие традиционную технологию, в основе которой лежит порождающая теория Н. Хомского, и системы, использующие правила, основанные на взаимоотношениях слов. Предложенный метод автоматического предсинтаксического анализа может быть применен лишь в системах, использующих традиционную технологию синтаксического анализа, поскольку в основе метода лежит использование элементов LL(1) и ЬЦ2)-разборов, которые могут быть применены только в контекстно-свободных грамматиках.

Во второй главе определяется формальная основа для разработанного метода автоматического предсинтаксического анализа проектной документации с использованием КС-грамматик.

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

языке (лексема) рассматривается как множество словоформ (омонимов): w={d¡,d2.....d„},

где d¡ — словоформа слова и>. Каждая словоформа d некоторого слова представлена в виде

набора атрибутов d={a¡,a2.....Ok¡, где каждый атрибут а представляет собой пару

a=<na,va>, в которой па- имя атрибута (например, часть речи, род, число, падеж и т.д.), а va - значение атрибута. Предполагается, что у любой словоформы не бывает двух атрибутов с одинаковыми именами.

В качестве входных данных предложенный метод использует грамматику, записанную в формате расширенных БНФ либо ATN. Для начала рассмотрим спецификацию грамматики расширенных БНФ.

Любой символ грамматики расширенных БНФ содержит набор параметров, которые являются, по сути, шаблонами атрибутов словоформы. Набор параметров некоторого символа грамматики s будем обозначать Ps-{pi,p2,...,pk}, где каждый параметр р представляет собой четверку p=<np,rp,gp,vp> в которой:

пр - имя параметра (например, род, число, падеж и т.д.);

гр - отношение, которое может принимать значение «=», «!=» и «+» (равно, не равно, совпадает, соответственно);

gp - номер (идентификатор) группы; ур - значение параметра. Каждое значение гр имеет приоритет (в данном определении значения перечислены в порядке уменьшения приоритета). Предполагается, что во множестве Р* не может быть двух параметров с одинаковыми именами.

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

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

Определим операцию соответствия. Словоформа с/ соответствует (удовлетворяет) терминалу / (и мы будем обозначать этот факт следующим образом: если для любого параметрар=<пр,г^г,хр> терминала / найдется атрибут а-<пауа> словоформы <1 с таким же именем (па=пр), при этом:

• если гр- '=', то уа=ур;

• если гр= '!=', то га ф- \р\

• если гр = '+', то для каждой пары ' из ячейки памяти текущей продукции, где у символа 5' есть параметр р' с тем же именем и номером группы что и у р (то есть р'=<Пр,гр ^р,ур >), должно выполняться равенство: уа=уа-, где а '=<пр,\'а> является атрибутом словоформы с!'.

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

Для вычисления словоформы, которая получается в результате применения правила, левая часть правила содержит набор пар вида <п,£>, где g - идентификатор группы, а п - имя атрибута. Набор атрибутов А1 новой словоформы (I формируется следующим образом. Для каждой пары <и,£> данного правила в А1 попадают такие атрибуты а=<па,\'и> с Л11, для которых найдется такой параметр р — <пр,гр^р,ур> еР\ что пр-па-п и gp=g, где с/'~5 - пара из ячейки памяти успешно разобранной продукции, А1 -набор атрибутов словоформы с/', Р* — набор параметров символа

Перейдем к описанию грамматики А"Ш, которая так же, как грамматика расширенных БНФ, может быть использована в качестве входных данных для предложенного метода.

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

Проход по дуге будет успешным только в том случае, если текущая словоформа либо словоформа фрагмента предложения, разобранного по нетерминалу, будет соответствовать параметрам символа, приписанному дуге. Операция соответствия словоформы <1 и символа грамматики 5 (будем обозначать это так же, как для расширенных БНФ: определяется следующим образом. Словоформа с! удовлетворяет символу .V, если для любого параметра р=<пр,гр^р,ур> символа 5 найдется атрибут а=<па,\'„> словоформы с/ с таким же именем (п„-пг), при этом: если гр= '=', то уа=гр; если гр= '/=', то уя ф хр\

если rp-'+ то для каждой пары d'~s' из стека графа, в которой у символа .v' есть параметр р' с тем же именем и номером группы что и у р (то есть p'=<np,rp-,gp,vp>), должно выполняться равенство: va=v„ , где а'=<иЛу„ > является атрибутом словоформы d'.

Так же, как и правила расширенных БНФ, автоматы сети ATN содержат набор пар <n,g> для вычисления словоформы разобранного фрагмента текста. Набор атрибутов AJ новой словоформы d формируется следующим образом. Для каждой пары <n,g> графа G в Ad попадают такие атрибуты a=<na,va> eAd, для которых найдется такой параметр P=<np,rp,gp,vp> еР*, что пр=па=п и gp=g, где d'~s - пара из стека графа, Ad- набор атрибутов словоформы d', Р' — набор параметров символа s.

Помимо спецификаций грамматик расширенных БНФ и ATN во второй главе показана связь между данными грамматиками и описан алгоритм эквивалентного преобразования грамматики расширенных БНФ в грамматику ATN.

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

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

Исходя из этого для определения границ фрагментов можно использовать модифицированные множества FIRST, LAST, FIRST2 и LAST2. В теории формальных языков данные множества определяются для цепочек терминальных и нетерминальных символов в правилах, описывающих 1Х(2)-грамматику. Элементами этих множеств являлись терминальные символы (в случае FIRST и LAST) либо упорядоченные пары

терминальных символов (в случае FIRST2 и LAST2), с которых могут начинаться (FIRST, FIRST2) либо заканчиваться (LAST, LAST2) терминальные цепочки символов, выводимые из правил грамматики.

Грамматика, описываемая расширенной сетью переходов относится к расширенным КС-грамматикам, обладающим мощностью контекстно-зависимых грамматик и, следовательно, не является КС-грамматикой в чистом виде. В частности символы грамматики, в которых присутствуют параметры с отношением типа «+», являются зависимыми от других символов графа, внутри которого они записаны. В связи с большим количеством отличий используемой грамматики от КС-грамматики, придется переопределить множества FIRST, LAST, FIRST2 и LAST2 для используемой грамматики (новые множества будут помечены штрихами: FIRST, LAST', FIRST2' и LAST2' соответственно). Рассмотрим алгоритм вычисления множества FIRST(G) графа G на примере.

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

Предположим теперь, что в одной из таких дуг содержится нетерминал и, который ссылается на граф G', для которого множество FIRST'(G') уже вычислено. В этом случае в FIRST'(G) мы должны поместить терминалы из FIRST'(G') сделав их зависимыми только от символов графа G и нетерминала и. Для этого сначала рассмотрим все параметры у каждого терминала из FIRST(G'), которые не участвуют в формировании разобранного по графу G' фрагмента текста. Те из них, которые имеют отношение «+», мы отсеем, а остальным (у которых отношение равно «=» либо «!=») присвоим фиктивный номер группы, например 0. Обозначим эту операцию функцией sieve(G',t'), которая возвращает терминал, полученный описанным выше способом, и принимает в качестве аргументов некоторый граф G' и терминал /' графа G'.

Теперь рассмотрим терминал t - sieve(G',t'), где t'eFIRST'(G'). Чтобы поместить терминал t в FIRST(G) необходимо:

• убрать из t такие параметры P=<np,rp,gp,vp> у которых gp=0, если у нетерминала и найдется параметр p'~<nP\rl,-,gp',vI/> с таким же именем, как у р (пр'=пр);

• для тех параметров P=<np,rp,gp,vp> у которых gpf0 и у нетерминала и нет параметра с именем пр, присвоить gp~ 0 если гр=«=» либо гр=«!=»; если гр=«+», то параметр р необходимо убрать из терминала V,

• у оставшихся параметров p=<np,rp,gp,vp> для которых найдется параметр р'-<пр,грgpvp■> нетерминала и положить gP=gP' и, если отношение гр- имеет больший приоритет чем Гр, то гр=гр- и v/,=v;,'.

Обозначим эту операцию функцией trail(t,u), которая возвращает терминал, полученный описанным выше способом, и принимает в качестве аргументов некоторый нетерминал и и терминал t. Будем говорить, что для пары t и и функция trail(t, и) не определена, если найдутся такие параметры p=<np,rp,gp,vp> и p'=<np-,rp-,gp-,vp> из (и и соответственно, которые противоречат друг другу, то есть пр= пр-, грФ «+», грФ«+» и

1) гр= гр■ и урФ vp•, либо

2) Грфгр- и vp=Vp-.

Если для пары t пи функция trail не определена, то это значит, что терминалу t соответствуют такие словоформы, которые могли бы присутствовать в цепочках, выводимых из графа нетерминала и, но не могут присутствовать в цепочках, выводимых из графа, в котором встретился нетерминал и. Например, предположим, что у некоторого терминала t присутствует параметр p=<gender,"=",I,"male">, а в списке параметров нетерминала и присутствует параметр p'=<gender,"=",l,"female">. Терминал t описывает словоформы мужского рода, тогда как нетерминал и требует, чтобы словоформа была женского рода, следовательно, терминал t никак не может быть использован в контексте и.

Теперь, когда мы описали функции sieve и trail, мы можем дать формальное определение множеству FIRST(G). Рассмотрим все дуги графа G, исходящие из его начальной вершины. Пусть а - символ, приписанный одной из таких дуг. Тогда:

• если а является терминалом, то а входит в FIRST'(G);

• если а является нетерминалом и ссылается на граф G', тогда для каждого терминала Г' из FIRST'(G') в FIRST'(G) входит терминал t=trail(sieve(G',t'),a), если для sieve(G',t') и а функция trail определена.

Будем называть операцию t=trail(sieve(G\t'),a) преобразованием контекста терминала t' в контекст нетерминала а.

Далее определим еще два множества терминальных символов LAST(G) и ONLY(G), которые необходимы для вычисления множеств FIRST2'(G) и LAST2'(G).

В множество LAST(G) помещаются те терминальные символы, которым удовлетворяют всевозможные словоформы, на которых парсер мог бы закончить разбор графа G. Пусть а - символ, приписанный дуге, которая ведет в один из конечных узлов графа G. Если а - терминал, то ае LAST'(G). Если а - нетерминал, который ссылается на граф G', то для каждого терминала t'eLAST'(G') в LAST'(G) входит терминал t=trail(sieve(G',t'),a), если для sieve(G',t') и а функция trail определена.

В множество ONLY(G) помещаются терминалы, которым удовлетворяют всевозможные словоформы, с которых парсер может начать и одновременно закончить разбор графа G. Данное множество определяется аналогично множествам FIRST'(G) и LAST'(G) с той разницей, что в определении рассматриваются дуги графа G ведущие из стартового узла в любой конечный узел.

Для сокращения записи удобно определить множества FIRST, LAST' и ONLY для произвольного символа грамматики а. В случае, если а — терминал, тогда любое из перечисленных множеств состоит из единственного элемента, которым является а. Если а- нетерминал, то мы будем считать, что любое из перечисленных множеств для а будет равно соответствующему множеству графа, на который ссылается а.

Теперь определим множество пар терминальных символов FIRST2'(G), которым удовлетворяют всевозможные пары словоформ, с которых парсер может начать разбор некоторого графа G. Рассмотрим все пары дуг с/ и с2 такие, что с\ исходит из начальной вершины, а с2 исходит из вершины, в которую ведет первая дуга. Пусть ч\ и а2 - символы, приписанные соответственно дугам с/ и с2, и пусть л'eONLY(ai) и х" eFIRST'(a2). Положим t'=x', если «/ - терминал и t'=trail(sieve(G',x'),a.i), если ai — нетерминал и G' -граф, на который ссылается ah Аналогично t"=x", если а2 терминал и t"=trail(sieve(G",x"),a2), если а2— нетерминал. Тогда в FIRST2'(G) входят такие пары терминалов ab, что:

1) в множество параметров а и Ь входят соответственно все параметры терминалов /' и t", у которых номер группы равен 0;

2) в множество параметров а входят такие параметры р'= <пр\гр\£рфО, vp-> терминала t', для которых в t" найдется параметр p"=<np«,rp~,gp",vp"> у которого пр'=пр' и gp=gp»; если такой параметр не нашелся и /у /«+», то в а входят параметры p=<np-,rp>,(),vp-> (аналогично для параметров Ь);

3) Ни один параметр терминала а с группой отличной от нуля не противоречит ни одному параметру Ъ, имеющему ту же группу, и наоборот.

Аналогично определяется множество LAST2'(G), с той разницей, что С/ будет обозначать дугу, ведущую в один из конечных узлов графа G, а с2 - дугу, ведущую в вершину, из которой исходит с/. Символы х' и х" будут браться соответственно из множеств ONLY(ai) и LAST'(a2).

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

цепочек словоформ, выводимых из графа G. Для определения множества MIDDLE(G) нам понадобятся два вспомогательных множества FIRST"(a) и LAST'(a).

Пусть а - символ, приписанный некоторой дуге графа G. Если а приписан дуге, которая ведет в узел, из которого исходит хотя бы одна дуга, то FIRST"(a)=FIRST(a). В противном случае, если а является терминалом, то FIRST"(a)=0; если а - нетерминал, который ссылается на граф G', то FIRST"(a)=FIRST"(G'), где FIRST'(G') определяется аналогично множеству FIRST(G') с той разницей, что для FIRST'(G') рассматриваются дуги, которые исходят из начального узла G' и ведут в вершины из которых исходит хотя бы одна дуга.

Если а приписан дуге, которая исходит из узла, в который ведет хотя бы одна дуга, то LAST'(a)=LAST'(a). В противном случае, если а является терминалом, то LAST"(a)= 0; если а - нетерминал, который ссылается на граф G', то LAST"(a)=LAST'(G'), где LAST'(G') определяется аналогично множеству LAST(G') с той разницей, что для LAST'(G') рассматриваются дуги, которые ведут в конечные вершины и при этом исходят из вершин в каждую из которых ведет хотя бы одна дуга.

Теперь дадим формальное определение множества MIDDLE(G) некоторого графа G. Рассмотрим все пары дуг с] и С2 такие, что ci исходит из произвольной вершины графа G, а С2 исходит из вершины, в которую ведет дуга С]. Пусть а/ и — символы, приписанные соответственно дугам с, и с2. Пусть х' eLAST'(а ¡)ф<Л и х" е FIRST Taj / 0. Положим t'=x', если ai - терминал и t'=trail(sieve(G',x'),ai), если ai — нетерминал и G' — граф, на который ссылается а;. Аналогично t"=x", если а2 терминал и t"=trail(sieve(G",x"),a2), если а2 — нетерминал и G" — граф, на который ссылается а2. Тогда в MIDDLE(G) входят такие пары терминалов аЪ, что:

1) в множество параметров а и Ъ входят соответственно все параметры терминалов t' и i", у которых номер группы равен 0;

2) в множество параметров а входят такие параметры р'= <пр\гgpФ0,vp■ > терминала t', для которых в t" найдется параметр p"=<np",rp«,gpvy-> у которого и gp^gp~; если такой параметр не нашелся и гр< ф«+», то в а входят араметры P=<np',rp',0,vp;> (аналогично для параметров А);

3) Ни один параметр терминала а с группой отличной от нуля не противоречит ни одному параметру 6, имеющему ту же группу, и наоборот.

На этапе синтаксической сегментации для каждого слова во входном предложении вычисляется два набора графов, назовем их Ni и N2. В Л'у входят те графы, разбор которых парсер мог бы начать, а в N2 входят графы, разбор которых парсер мог бы закончить, находясь в данном месте предложения. Набор Ni для некоторого слова w, вычисляется

следующим образом. Рассмотрим соседнее справа слово и>,. /. Рассмотрим всевозможные пары словоформ d'd", где d' - одна из словоформ и1,, a d" - одна из словоформ и',,/. Если пара словоформ d'd" удовлетворяет хотя бы одной из пар терминалов из MIDDLE(G) для любого графа G, то набор Nj пуст. В противном случае в Nj помещаются такие графы G, для которых выполняется условие d'~t\ d"~t" и t't"eFIRST2'(Gj.

Для вычисления N2 слова w, рассмотрим соседнее слева слово w,-]. Рассмотрим всевозможные пары словоформ d'd", где d' - одна из словоформ и'„ a d" - одна из словоформ Wi-i. Если для любого графа G грамматики выполняется условие d"~t", d'~t' и l"l'eMIDDLF.(G), to набор N2 пуст. В противном случае в N2 помещаются такие графы G, для которых выполняется условие d"~t", d'~t' и t"t'eLAST2'(G).

Для проведения предсинтаксического анализа некоторого предложения с использованием предложенного метода необходимо выполнить следующие действия:

• Если для синтаксического анализа используется грамматика БНФ, то до начала анализа текста преобразовать ее в грамматику ATN;

• До начала анализа текста провести расчет множеств FIRST2'LAST2' и MIDDLE для используемой ATN грамматики.

• Во входном предложении для каждого слова вычислить наборы Nj и Л^;

• Каждое слово пометить как начинающее разбор по всем синтаксическим правилам из Ni данного слова и заканчивающее разбор правил по всем правилам из N2.

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

Для тестирования предложенного метода был разработан программный комплекс, который использует модуль лексического анализа системы "Crosslator" и позволяет проводить синтаксический анализ предложением с использованием различных методов оптимизации. Предложенный метод тестировался на корпусе, составленным из технических текстов, и на корпусе литературного текста. Для тестирования была использована грамматика русского языка, записанная в формате расширенных БНФ и состоящая из 129 правил, которая конвертировалась в формат ATN. Для сравнения с существующими методами оптимизации анализа, корпусы тестировались также с использованием метода LL(1) разбора.

В результате тестирования первого корпуса установлено, что применение предложенного метода дало прирост производительности на 4%, тогда как применение LL(1) разбора только понизило производительность анализа. В результате тестирования второго корпуса было установлено, что применение предложенного метода дало прирост

производительности на 7%, тогда как комбинация предложенного метода с методом 1Х(1) разбора дало прирост на 8,7%.

Исходя из проведенного эксперимента можно установить следующее:

• Предложенный метод дает преимущество перед использованием метода 1Х(1) разбора для небольших корпусов текста.

• Для больших корпусов текста оптимальным является использование предложенного метода в сочетании с методом 1А(1) разбора.

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

При экспериментах с системой "СгозбЫог" (использующей правила в формате БНФ) было установлено, что ускорение этапа анализа отдельных предложений увеличивалось как минимум в два раза и колебалось в среднем между 10 и 20 процентами. В заключении содержится описание основных результатов работы. АОД позволяет решать такие задачи, как, например, поддержка документации на нескольких языках и автоматическое исправление ошибок в тексте, информационный поиск и составление баз знаний о проектах. Для выполнения этих задач требуется использование методов компьютерной лингвистики, в частности, проведение полного синтаксического анализа текстов. Среди подобных методов, методы классической школы являются наиболее изученными и обладают широкими возможностями. Однако производительность подобных систем значительно ниже производительности систем неполного анализа. Внедрение этапа сегментации в системы полного анализа текстов позволит ускорить процесс обработки проектной документации, что в результате позволит сократить общее время на разработку изделия. На основании анализа существующих систем, использующих синтаксическую сегментацию, сделан вывод, что ни в одной системе, использующей сегментацию, не проработан вопрос автоматического пополнения базы правил сегментации. Вследствие этого правила сегментации добавляются лингвистами вручную, что является трудоемким процессом и представляет собой препятствие для разработки систем обработки документации для широкого спектра предметных областей.

В диссертационной работе предложен метод автоматического предсинтаксического анализа текстов проектной документации, который может быть использован для проведения этапа сегментации в системах, использующих КС-грамматики для полного анализа текстов на естественном языке. В качестве входных данных метод использует грамматики, записанные в формате расширенных БНФ или А'ГЫ. Предложенный метод

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

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

Для тестирования предложенного метода бьи разработан программный комплекс, который использует модуль лексического анализа системы "Crosslator" и позволяет проводить синтаксический анализ предложением с использованием различных методов оптимизации. В результате проведенных экспериментов с использованием разработанного программного комплекса, а также с использованием системы "Crosslator", было установлено, что сокращение времени разбора отдельных предложений в результате применения разработанного метода превышает 80%, тогда как среднее ускорение находится на уровне 10%.

Публикации по теме диссертации:

1. Манушкин Е.С., Клышинский Э.С. Метод автоматического порождения правил синтаксической сегментации для задач анализа текстов на естественном языке // Информационные технологии и вычислительные системы, 4, 2009 г., С. 57-66.

2. Манушкин Е.С., Клышинский Э.С. Метод автоматического порождения правил синтаксической сегментации для расширенных сетей переходов // Информационные технологии и вычислительные системы, № 2, 2011г., С. 5867.

3. Манушкин Е.С. Метод автоматической генерации правил синтаксическо сегментации // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. - М. МИЭМ, 2009, С. 147.

4. Клышинский Э.С., Манушкин Е.С. Метод автоматической генерации правил синтаксической сегментации // Сб. трудов двенадцатого научно-практического семинара «Новые информационные технологии», М. 2009, С. 135-148.

5. Клышинский Э.С., Манушкин Е.С. Математическая модель порождения правил синтаксической сегментации // Сб. трудов второй Всероссийской конференции «Знания - Онтологии - Теории», Новосибирск 2009, Том 2, С. 182-186.

6. Манушкин Е.С. Выделение правил синтаксической сегментации в нотации расширенных сетей переходов // Материалы ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. - М. МИЭМ, 2010, С. 204.

7. Манушкин Е.С. Применение метода автоматической генерации правил синтаксической сегментации для расширенных сетей переходов // Сб. трудов тринадцатого научно-практического семинара «Новые информационные технологии», М. 2010, С. 93-106.

8. Манушкин Е.С. Метод автоматической разметки предложения для этапа синтаксической сегментации // Сб. трудов пятнадцатого научно-практического семинара «Новые информационные технологии», М. 2012, С. 191-198.

Подписано в печать 19.04.2012г. Тираж 120 экз. Заказ № 197 Отпечатано в типографии «ДЦ «Каретный Двор»» 101000, Москва, Лубянский пр., д.21, стр.5-5а Тел.: (495) 621-70-09 \у\улу.а11аргт1п.1

61 12-5/3858

Министерство образования и науки Российской Федерации Московский государственный институт электроники и математики

На правах рукописи

Манушкин Евгений Сергеевич

МЕТОД АВТОМАТИЧЕСКОГО ПРЕДСИНТАКСИЧЕСКОГО АНАЛИЗА

ПРОЕКТНОЙ ДОКУМЕНТАЦИИ С ИСПОЛЬЗОВАНИЕМ КС-ГРАММАТИК

Специальность 05.13.12. - "Системы автоматизации проектирования (информатика) (технические науки)"

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н., доцент Э.С. Клышинский

Москва - 2012

Оглавление

Введение.........................................................................................................................................3

Глава 1. Обзор методов синтаксического анализа...................................................................12

1.1. Автоматическая обработка проектной документации..................................................12

1.2. Роль и задачи синтаксического анализа в полном анализе текста..............................14

1.3. Методы повышения производительности синтаксического анализа..........................16

1.4. Системы синтаксического анализа, использующие синтаксическую сегментацию. 19

1.4.1. Поверхностный синтаксический анализатор STP..................................................19

1.4.2. Поверхностный синтаксический анализатор группы "Диалинг".........................21

1.4.3. Поверхностный синтаксический анализатор польского языка Spajd..................24

1.5. Формализмы основанные на порождающей теории Н. Хомского..............................27

1.5.1. Расширенные сети переходов..................................................................................28

1.5.2. Head Driven Phrase Structure.....................................................................................30

1.5.3. Расширенные формы Бэкуса-Наура........................................................................32

1.5.4 Affix Grammar over Finite Lattices (AGFL)...............................................................33

1.6. Формализмы использующие взаимоотношения слов...................................................35

1.6.1 Treeton..........................................................................................................................36

1.6.2. Link Grammar.............................................................................................................38

1.7. Выводы..............................................................................................................................41

Глава 2. Формальная основа предложенного метода автоматического предсинтаксического анализа....................................................................................................43

2.1. Спецификация грамматики расширенных БНФ...........................................................43

2.2. Спецификация грамматики ATN....................................................................................50

2.3. Алгоритм преобразования грамматики расширенных БНФ в грамматику ATN.......51

2.4. Выводы..............................................................................................................................60

Глава 3. Метод автоматического предсинтаксического анализа проектной документации61

3.1. Вычисление терминальных множеств, необходимых для проведения синтаксической сегментации.................................................................................................61

3.2. Метод автоматического предсинтаксического анализа проектной документации ...69

3.3. Алгоритм интерпретации разметки текста, полученной на этапе предсинтаксического анализа................................................................................................70

3.4. Выводы..............................................................................................................................79

Глава 4. Практическая реализация и тестирование предложенного метода.........................81

4.1. Описание модуля морфологического анализатора системы "Crosslator"...................81

4.2. Описание тестирующего комплекса...............................................................................86

4.3. Описание эксперимента...................................................................................................87

4.4. Выводы..............................................................................................................................93

Заключение..................................................................................................................................96

Список используемой литературы...........................................................................................100

Введение

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

Одной из задач систем автоматизированного проектирования является систематизация хранения данных об изделии и приведение всей документации к единому стандарту. В этой области широко используются СALS-технологии. CALS (Continuous Acquisition and Life cycle Support) — "совокупность базовых принципов, управленческих и информационных технологий, обеспечивающая поддержку жизненного цикла изделий (преимущественно машиностроительных) на всех его стадиях" [45]. Использование данных технологий предполагает наличие некоторой интегрированной информационной среды (единого информационного пространства [45]), в которой, по средствам электронной передачи данных, происходит взаимодействие между всеми участниками жизненного цикла изделия: от разработчиков и поставщиков до заказчиков изделия.

Составными частями CALS являются широко распространенные технологии ILM (Information Lifecycle Management) [15, 48, 26] и PDM (Product Data Management) [14, 31]. Основной задачей ILM-систем является хранение документации на изделие. Кроме того, ILM-системы отвечают за процессы хранения, распределения, миграции, архивировании и удаления данных в инфраструктуре предприятия. PDM системы позволяют управлять данными об изделии и управлять информационными процессами жизненного цикла изделия, которые создают и используют эти данные. Для построения единого информационного пространства PDM используются в интеграции с Computer Aided Design / Manufacturing (CAD/CAM) системами, которые предназначены для проектирования, разработки технологий, расчета

материальных и трудовых нормативов и т.д., а также в интеграции с системами Enterprise Resource Planning System (ERP), которые обеспечивают функции управления продажами, снабжением, производством и т.д. На рис. 1 представлена общая схема интеграции CAD/CAM, PDM и ERP систем.

(Сдаетрукгершй

состав иэдеямя

Управление документооборотом

Конструкторская Технолсгичеек документация

произв.

Справочник мтвриагшв

Нормы расхода

Техпроцессы,

маршруты

Планирование,

Номенклатура. Спецификация Маршрут '

Список отступлений от норм . Щ | .

Рис. 1. общая схема интеграции CAD/CAM, PDM и ERP систем Использование единого информационного пространства предприятия позволяет перейти к безбумажной обработке проектной документации. Однако подобные технологии не производят интеллектуальную обработку данных, которая могла бы еще больше ускорить процесс разработки. Современное развитие науки и компьютерных технологий позволяют перейти на качественно иной уровень работы с документацией. На данный момент ведется переход от электронного хранилища к автоматической обработке документации. Автоматическая обработка документации позволяет выполнять такие задачи, как, например, поддержка документации на нескольких языках и автоматическое исправление ошибок в тексте, информационный поиск и составление баз знаний о проектах. Для выполнения этих и многих других задач автоматической обработки документации требуется использование методов компьютерной лингвистики, которые занимаются непосредственно обработкой текстов на естественном языке.

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

перевода) была поставлена Уорреном Уивером, который предложил рассматривать задачу перевода как процесс дешифрования [102]. Знаменитый Джорджтаунский эксперимент [80], в котором компьютер перевел 60 довольно простых предложений с русского языка на английский, подавал большие надежды и привлек значительные средства в машинную лингвистику. Через десять лет в 1966 комиссия Национальной Академии Наук ALPAC (Automatic Language Processing Advisory Committee) сделала вывод о том, что за десять лет в области машинной обработки текстов не было достигнуто ни одного серьезного результата и исследования в области машинной лингвистики были приостановлены. Однако в 1968-1970 году Тери Виноград, работавший в то время в MIT, разработал первую диалоговую систему SHRDLU, которая по командам оператора осуществляла изменения в мире геометрических фигур [104]. Одним из самых серьезных достижений в компьютерной лингвистики американской школы является исследование формальных грамматик, проведенное Н. Хомским [72, 74, 64]. Практически все дальнейшие исследования американской школы берут свою основу в порождающей теории Хомского.

В то же время в Советском союзе исследования велись намного активнее, чем в США. 1954 году начались работы по созданию систем машинного перевода в Институте точной механики и вычислительной техники Академии наук СССР. Вскоре были получены первые успехи, и работы в этой области стали вестись в различных научно-учебных центрах. Уже в 1955 году был проведен эксперимент со словарём в 2300 слов. В Институте прикладной математики АН СССР под руководством О.С. Кулагиной и И.А. Мельчука исследования велись в двух направлениях -англо-русский и франко-русский перевод.

Одними из выдающихся достижений советских исследователей в области компьютерной лингвистики являются модель «Смысл<-»Текст», разработанная И.А. Мельчуком в системе автоматического перевода технических текстов ЭТАП [3, 4], система французско-русского перевода

"ФРАП" [33, 6] и система машинного перевода политических текстов "ПОЛИТЕКСТ" [34].

На сегодняшний день существует огромное количество коммерческих компаний, занимающиеся машинной лингвистикой. Примером отечественных компаний, достигнувших результатов и находящихся на мировом уровне являются Yandex [95], Promt [60] и многие другие. Таким образом скромные лабораторные системы машинного перевода превратились сегодня в целую отрасль науки и промышленности.

Для автоматической обработки текстовой документации зачастую требуется проводить полный анализ текста, который требует существенных временных затрат. Синтаксический анализ является самым ресурсоемким этапом анализа текста. Это связано как с неоднозначностью естественного языка так и с неоднозначностью правил синтаксического анализа. На сегодняшний день существует огромное количество теоретических методов проведения синтаксического анализа и их практических реализаций. Как показывает практика, системы, использующие базы правил анализа, по качеству не уступают самым современным системам, которые используют статистические подходы. Довольно популярными в этой области являются теории американской школы, основанные в большинстве своем на порождающей теории Н. Хомского [72, 74, 64]. Яркими примерами таких теорий являются расширенные сети переходов (ATN - Augmented Transition Networks) [107, 105, 101] и AGFL (Affix Grammar over Finite Lattices -грамматика аффиксов) [76, 103].

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

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

или составных конструкций [108, 88]. Синтаксический анализатор будет проводить разбор исходя из того, что найденные слова принадлежат той или иной синтаксической категории и не будет предпринимать заведомо ложные попытки разобрать предложение по-другому. За счет этого количество итераций разбора заметно сокращается и, как результат, существенно уменьшаются вычислительные затраты.

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

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

Цель работы. Целью диссертационной работы является повышение эффективности построения систем анализа проектной документации за счет автоматизации труда разработчиков таких систем. Задачи исследования

1. Анализ существующих методов синтаксического анализа и систем, использующих этап синтаксической сегментации.

2. Разработка алгоритма преобразования правил в формате расширенных БНФ в правила в формате расширенных сетей переходов (АТ1Ч).

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

4. Разработка метода автоматического предсинтаксического анализа проектной документации с использованием КС-грамматик.

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

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

1. Предложен алгоритм эквивалентного преобразования грамматики расширенных БНФ в грамматику АТМ.

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

3. Предложен новый метод, позволяющий проводить этап предсинтаксического анализа в системах анализа проектной документации, использующих грамматики расширенных БНФ и АТ1Ч.

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

техническое решение, позволяющее ускорить работу этапа синтаксического анализа текстов проектной документации. Решение использует только информацию о правилах синтаксического анализа, записанных в форме БНФ или АТ1Ч. Это позволяет разработчикам систем синтаксических анализаторов реализовывать этап синтаксической сегментации текста практически без

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

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

Реализация и внедрение результатов. Алгоритмы и методы, описанные в данной работе, реализованы автором в компьютерной программе. Программа создавалась как с целью апробации и совершенствования разрабатываемых методов и алгоритмов, так и с целью практического использования в машинном переводчике "Кросслейтор", разрабатываемом в ИПМ им. М.В. Келдыша РАН и при выполнении гос. контракта П-261 в рамках ФЦП "Научные и научно-педагогические кадры инновационной России" на 2009-2013 гг., заключенного между Министерством образования и науки и МИЭМ. Результаты работы обсуждались на научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» в 2009 и 2010 годах.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

1. «Международная конференция Ме§а1лп§'08», Партенит, 2008 г.

2. «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», М., МИЭМ, 2009 г.

3. «Новые информационные технологии в автоматизированных системах», М. 2009

4. Всероссийская конференция «Знания - Онтологии - Теории», Новосибирск 2009 г.

5. «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», М., МИЭМ, 2010 г.

6. «Новые информационные технологии в автоматизированных системах», М. 2010 г.

7. «Новые информационные технологии в авто