Технология построения многовариантных объектно-ориентированных структур текстов

Вид материала

Диссертация

Содержание Роль базовой реализации Базовые технологии Кодировка символов — Unicode Язык программирования — Object Pascal Представление для системы классов и шаблонов Field*) > PClass Node*) > Pattern Синтаксис языка действий Грамматика языка ТОМАТа Имена сущностей ТОМАТа и квалификаторы имен Типы данных и константы языка ТОМАТа Инструкции языка ТОМАТа Поддержка XML-представления системы объектов языка Object Pascal Внутреннее представление системы классов и шаблонов Ссылки на другие сущности ТОМАТа организуются по указателям Шаблоны и классы не группируются по банкам, а доступны на одном уровне Поддерживаются ссылки на исходные сущности ACOM Поддерживается только сохранение системы сущностей внутреннего представления в XML Все действия на языке ТОМАТа хранятся в специальном вычислительном представлении Внутреннее представление и исполнение действий ... Полное содержание

Подобный материал:

• Ландшафт области управления данными: аналитический обзор, 531.27kb.
• Развитие объектно-ориентированных систем управления базами данных, 122.52kb.
• Лекция № Элементы управления в графических и объектно-ориентированных интерфейсах, 307.9kb.
• Сводный научный отчет за 2010 г по совместному проекту «Разработка объектно-ориентированных, 204.3kb.
• Врамках настоящей работы на примере четырех произведений будут рассмотрены некоторые, 228.04kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Рабочая программа учебной дисциплины (модуля) Объектно-ориентированное программирование, 99.17kb.
• Исследование организационных структур управления, 469.08kb.
• Темы: Введение в язык rsl, 123.68kb.
• Программа дисциплины Объектно-ориентированное программирование Рекомендуется для направления, 591.42kb.

^ Роль базовой реализации

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

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

2. ^ Базовые технологии
   

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

1. ^ Кодировка символов — Unicode
   

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

В стандарте Unicode предусматриваются несколько представлений кодировки Unicode (UTF-8, UTF-16, UTF-32). Это приводит к необходимости "понимать" тексты, закодированные согласно соответствующему представлению, и совершать многочисленные проверки допустимости последовательностей кодов символов в текстах с 16-битным представлением, пользуясь сложными громоздкими таблицами.

Для предлагаемой базовой реализации метода анализа текстов алгоритм обработки символьной информации в точном соответствии со стандартом Unicode оказался на практике неприемлемо медленным. Поэтому было принято решение расширить трактовку кодировки Unicode, в частности, для понятия "буква", принятого в стандарте Unicode (а именно, считать буквами все кодовые позиции за пределами ASCII-диапазона), и ввести 3 глобальных категории символов. Это не сужает возможности "понимания" Unicode-документов. Таким образом, мы получили совместимость с документами, закодированными по стандарту Unicode в большинстве общепринятых представлений, и возможность быстрой символьной обработки, что полностью отвечает условиям поставленной задачи. Данной базовой реализацией рассматриваются служебные символы (цифры, скобки, прочие служебные знаки), пробельные символы (первые 32 символа из символьной таблицы ASCII) и буквы, к которым приравниваются все остальные символы, в том числе не входящие в набор ASCII. Во внутреннем представлении базовой реализации текст обрабатывается в некотором абстрактном 16-битовом представлении, являющемся расширением UTF-16. При этом не поддерживаются ограничения для каких-либо последовательностей кодов символов (в том числе так называемых "суррогатов" UTF-16).

2. Формат файлов данных — XML
   

В качестве формата для внешнего представления информации (хранение файлов) был выбран язык XML. Использовалась версия 1.0 этого языка [XML 1.0, 2000], хотя предложенное решение совместимо и со стандартом 1.1 [XML 1.1, 2002]. Альтернативой было бы создание специального языка описания банков классов и шаблонов. Но такой подход затрудняет обмен данными между различными программами. Поскольку для языка XML существует множество программных компонентов, осуществляющих чтение и запись файлов, то такие компоненты, как визуальный редактор проектов или препроцессор, могут быть представлены в виде независимых программных продуктов и даже могут разрабатываться на разных языках программирования.

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

Специально для базовой реализации ядра технологии "ТОМАТ" были реализованы универсальные программные компоненты, ответственные за чтение и запись файлов в формате XML. Целью было исследовать вопрос эффективности работы с файлами в формате XML. На самом деле вполне можно было обойтись одним из распространенных компонентов, но ставилась задача сделать базовую реализацию многоплатформенной, обеспечив переносимость на уровне перекомпиляции исходных текстов. Большинство же эффективных XML-компонентов привязаны к определенной платформе или, если и переносимы, то привязаны к языку программирования С++, в то время как базовая реализация была выполнена на языке Object Pascal.

3. ^ Язык программирования — Object Pascal
   

В данной работе под языком программирования Object Pascal понимается пересечение языков, используемых в системе Borland Delphi (начиная с версии 5), Borland Kylix, а также языка, поддерживаемого свободно распространяемым мультиплатформенным компилятором Free Pascal Compiler.

В научных кругах имеет некоторую известность еще один паскалеподобный язык программирования, поддерживающий объектно-ориентированную технологию, также носящий имя Object Pascal. Краткие сведения об этом языке можно найти в книге [Буч 2000]. Этот язык разрабатывался в компании Apple Computer при участии Никлауса Вирта (автора классического языка Паскаль). Будучи достаточно примитивным, скорее учебным, объектно-ориентированным языком, он не получил должного распространения и вскоре был забыт в индустрии программирования. В то же время фирма Borland разработала систему программирования Delphi, использовав в ней развитие хорошо известного языка этой же фирмы Turbo Pascal, назвав его Object Pascal. Не следует отождествлять эти языки и, тем более, переносить на язык системы Delphi (кстати, впоследствии именно так Borland стала называть свой Object Pascal) вполне обоснованные претензии, предъявляемые к языку Object Pascal, например, в вышеупомянутой книге.

Язык Object Pascal имеет ряд привлекательных особенностей, что, однако, зачастую игнорируется любителями языка C++. Одним из ключевых моментов, весьма существенных для базовой реализации, является легкость чтения программ на этом языке. Она, в свою очередь, объясняется тем, что язык является в большой степени идиоматичным (одна и та же идея красиво реализуется небольшим количеством способов), что подтверждается похожестью кода, написанного разными программистами аналогичной квалификации.

Основным конкурентом языку Object Pascal был, конечно же, язык C++. Его недостатки — низкая скорость компиляции и значительно большая свобода выбора языковых конструкций (это, разумеется, недостаток только для исследовательских проектов). Кроме того, текущий уровень развития этого языка не удовлетворяет автора данной работы, так как не известно ни одной эффективной реализации стандартной библиотеки этого языка, что приводит к рекомендациям отказываться от использования стандартной библиотеки в индустриальных проектах. Эти соображения делают язык C++, по мнению автора, неудобным для показательных реализаций научных проектов.

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

Не так давно язык Object Pascal считался проприетарным языком фирмы Borland, так как поддерживался только в системе Delphi для Microsoft Windows. Но позже появилась система программирования, аналогичная Delphi и с тем же языком в основе, рассчитанная на платформу Linux. Более того, существует относительно популярный свободно распространяемый компилятор Free Pascal Compiler, поддерживающий тот же язык. Этот компилятор доступен в исходных текстах и работает на платформах Windows и Unix.

Изложенные выше аргументы позволяют считать предлагаемую базовую реализацию ТОМАТа на языке Object Pascal многоплатформенной.

3. ^ Представление для системы классов и шаблонов
   

Далее приводится полное описание системы сущностей ТОМАТа на языке XML DTD. В базовой реализации каждый банк хранится в виде XML-документа, соответствующего данному DTD.


ACOM (Bank) >

ACOM

  version CDATA "1.0"

  description CDATA "Alex Classes Object Model"

>


Bank (Domain*, Constant*, PClass*, Pattern*) >

Bank

  Name %String-;

  UsedBanks %StringList-; #IMPLIED

>


Domain EMPTY >

Domain

  Name %String-;

  Tokens %StringList-; #REQUIRED

>


Constant EMPTY >

Constant

  Name %String-;

  Value %String-;

>


PClass (^ Field*) >

PClass

  Name %String-;

  BaseClasses %StringList-; #IMPLIED

Action %String-;

>


Field EMPTY >

Field

  Name %String-;

DataType %String-;

  DefaultValue %String-;

Action %String-;

>


Pattern (^ Node*) >

Pattern

  Name %String-;

  PClass %String-;

  Enabled %Boolean-; "True"

Action %String-;

>


Node EMPTY >

Node

  Name %String-;

  PClass %String-;

  StrictType %Boolean-; "False"

  MinCount %Integer-; "1"

  MaxCount %Integer-; "1"

  ContextKind %ContextKind; "None"

Action %String-;

>


Пояснения к DTD:

• Атрибуты типа %String-; (строка) могут быть в документах опущены, что приравнивается к пустой строке.
  
• Пометка #IMPLIED для атрибута типа %StringList-; (список имен) означает, что если атрибут в документе опущен, то подразумевается пустой список.
  

Специально для базовой реализации был разработан язык OMML (Object Model Markup Language), являющийся подмножеством языка XML 1.0. Этот язык не является языком документов XML с грамматикой, определяемой с помощью DTD. Он является сужением языка XML, имея собственное понятие DTD (аналогичное XML DTD, но более ограниченное в выразительных возможностях) и грамматику для документов. Предлагаемое DTD на самом деле является OMML DTD. Этот язык допускает взаимно-однозначное отображение системы XML-элементов в систему объектов Object Pascal.

Подробнее о языке OMML рассказано в разделе, посвященном архитектура ядра.

4. ^ Синтаксис языка действий
   

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

1. ^ Грамматика языка ТОМАТа
   

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

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

Алфавитом языка служат символы из стандартного набора Unicode [Unicode 4.0, 2003]. Продукции грамматики описаны с использованием расширенных форм Бэкуса-Наура (EBNF) с использованием синтаксиса, принятого в описании языка XML [XML 1.0, 2000], с незначительным отличием (расширением): допустимым символом языка считается [#x1-#x10FFFF]. Вообще любая реализация ТОМАТа должна предоставить возможность работать с символами из 7-битного набора ASCII с кодами от 32 до 126. Все символы, не являющиеся пробельными и не входящие в этот набор, если таковые предоставляются реализацией технологии, называются дополнительными символами, и в продукциях обозначаются как "доп". Все такие символы приравниваются к буквам, следовательно, могут использоваться в именах.

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

Таким образом основные лексические продукции имеют вид:

комментарий ::= "{" [^}]* "}"

пробел ::= комментарий | [#x1-#x20]

действие ::= пробел* (лексема пробел*)*

доп ::= [#x80-#x10FFFF]


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

2. ^ Имена сущностей ТОМАТа и квалификаторы имен
   

Именем сущности ТОМАТа является строка, удовлетворяющая продукции:

имя ::= ( "%"? ([A-Za-z_] | доп) ([A-Za-z_] | доп | [0-9])* ) - зарезерв_слово


Имя не может совпадать с зарезервированными словами языка ТОМАТа:

зарезерв_слово ::= "False" | "True" | "MaxInt" | "Integer" | "Boolean" | "String" |
"in" | "eq" | "div" | "mod" | "and" | "or" | "not" | "if" | "then" | "begin" | "end"


имя_банка ::= имя

имя_домена ::= имя

имя_константы ::= имя

имя_класса ::= имя

имя_шаблона ::= имя

имя_токена ::= имя

имя_поля ::= имя

имя_узла ::= имя


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

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

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

квалификатор_банка ::= имя_банка? "::"

квал_имя_класса ::= квалификатор_банка? имя_класса

квал_имя_домена ::= квалификатор_банка? имя_домена

квал_имя_константы ::= квалификатор_банка? имя_константы


Каждое имя поля может предваряться квалификатором класса:

квалификатор_класса ::= квал_имя_класса ":"

квал_имя_поля ::= квалификатор_класса? имя_поля


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

квалификатор_узла ::= имя_узла "."

квал_имя_поля_узла ::= квалификатор_узла квал_имя_поля


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

3. ^ Типы данных и константы языка ТОМАТа
   

Типы данных языка ТОМАТа имеют следующие обозначения:

тип ::= "Integer" | "Boolean" | "String" | квал_имя_домена


В выражениях и некоторых других конструкциях языка ТОМАТа могут использоваться константы (явно указанные значения), называемые константами языка ТОМАТ (в отличие от именованных констант, описанных в банке).

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

конст_токен ::= квалификатор_банка? имя_токена


Константа типа Integer описывается десятичным либо шестнадцатеричным числом. Зарезервированное слово MaxInt обозначает максимальное представимое целое число, аналогично языку Паскаль.

конст_целое ::= ( [0-9]+ ) | ( "$" [0-9A-Fa-f]+ ) | "MaxInt"


Константа типа Boolean описывается ключевым словом:

конст_лог ::= "False" | "True"


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

стр ::= ("#" конст_целое) | ("'" ([^'] | "''")* "'")

конст_стр ::= стр*


Для указания константы пустого множества должна использоваться конструкция:

пустое_множ ::= тип "[]"


Для указания константы множества, содержащего все возможные элементы (полная неопределенность), используется конструкция:

полное_множ ::= тип "[*]"


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

4. ^ Инструкции языка ТОМАТа
   

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

инструкция ::= составная_инструкция | условная_инструкция | присваивание | ограничение | пустая_инструкция

пустая_инструкция ::=


составная_инструкция ::= "begin" инструкция (";" инструкция)* "end"


Условная инструкция записывается так:

условная_инструкция ::= "if" выражение "then" инструкция


Текст инструкции-присваивания должен удовлетворять продукции:

присваивание ::= (квал_имя_поля | квал_имя_поля_узла) ":=" выражение


Инструкция проверки ограничения записывается следующим образом:

ограничение ::= "!" выражение


Сами инструкции разделяются точкой с запятой:

действие ::= инструкция (";" инструкция)*

5. Архитектура ядра системы
   

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

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

1. ^ Поддержка XML-представления системы объектов языка Object Pascal
   

В соответствии с технологией объектно-ориентированного проектирования для представления сущностей ТОМАТа, составляющих систему классов и шаблонов, был разработан модуль, представляющий соответствующую систему классов языка Object Pascal. Эти классы были наделены способностью сохранять и восстанавливать состояние объекта с помощью файла в формате XML. Такая задача, безусловно, представляет интерес не только в рамках данного проекта, но поскольку на момент подготовки базовой реализации не были доступны подходящие универсальные модули, было принято решение разработать собственную универсальную систему сериализации объектов Object Pascal в формат XML. Для этого был предложен уже упомянутый язык OMML (Object Model Markup Language).

Целью разработки OMML являлось предоставление удобного средства сериализации системы классов языка Object Pascal в виде XML-документов. Не всякая система классов может быть представлена (точнее, не всякую систему классов имеет смысл представлять) в виде XML DTD. Также не для всякого DTD возможно (и целесообразно пытаться) сконструировать систему классов Object Pascal для хранения данных XML-документа. Поэтому язык OMML в терминах ограничений описывает, какие системы классов подлежат рассмотрению, и ставит таким системам во взаимно-однозначное соответствие DTD языка XML, причем на средства, используемые в DTD, также накладываются ограничения.

Неотъемлемой частью технологии использования языка OMML в программах на Object Pascal является использование модуля (в базовой реализации этот модуль был назван XMLObjects), содержащего код, выполняющий чтение/запись системы объектов из OMML-документов и помещенный в некий базовый класс TXMLObject. Все его классы-наследники автоматически наделяются возможностью сохранять и восстанавливать свое состояние в/из OMML-документа, для этого им достаточно объявить нужные свойства в разделе published. Для осуществления доступа к этим полям модуль XMLObjects пользуется информацией о типах времени исполнения (RTTI), предоставляемой языком Object Pascal.

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

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

Для чтения и записи OMML-документов можно пользоваться модулями для работы со стандартным XML, таким образом, использование языка OMML дает возможность приложениям обмениваться данными, представленными в оперативной памяти в виде системы объектов, посредством XML-представлений.

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

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

Реализованный модуль чтения XML совмещает лучшее из этих двух подходов, и при этом лишен описанных недостатков. Идея состоит в том, что в оперативной памяти строится система объектов, соответствующих XML-элементам, но для каждого элемента рекурсивно загружается только его первый вложенный элемент. Таким образом, в памяти формируется "лестница" из первых "детей" элемента. После того, как приложение обработало построенные объекты (в случае модуля XMLObjects — загрузило значения полей в объект Object Pascal), оно явно запрашивает загрузку следующего дочернего элемента, и так продолжается, пока не исчерпаются все элементы.

2. ^ Внутреннее представление системы классов и шаблонов
   

Система классов Object Pascal, представляющих сущности ТОМАТа, помещена в модуль, названный ACOM (Alex Classes Object Model). Эти классы описывают уровень представления сущностей ТОМАТа, доступный пользователю технологии — эксперту, готовящему систему классов и шаблонов для решения определенного класса задач. Все ссылки сущностей друг на друга производятся по именам, и вообще структура этих сущностей в точности соответствует описанию, приведенному в соответствующей главе.

В то же время, как уже отмечалось, для эффективной обработки данных в рамках технологии "ТОМАТ" ядро (точнее, исполнитель) нуждается во внутреннем представлении, которое приспособлено именно к этапу обработки данных. Именно компилятор ТОМАТа преобразует проект (систему банков в виде сущностей ACOM) во внутреннее представление. Построение такого представления было выполнено в виде системы классов Object Pascal, которая соответствовала следующим принципам:

• ^ Ссылки на другие сущности ТОМАТа организуются по указателям
  

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

• ^ Шаблоны и классы не группируются по банкам, а доступны на одном уровне
  

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

• ^ Поддерживаются ссылки на исходные сущности ACOM
  

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

• ^ Поддерживается только сохранение системы сущностей внутреннего представления в XML
  

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

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

• ^ Все действия на языке ТОМАТа хранятся в специальном вычислительном представлении
  

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

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

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

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

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

3. ^ Внутреннее представление и исполнение действий
   

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

Основой внутреннего представления действий является так называемая польская инверсная запись, или ПОЛИЗ. Фактически, ПОЛИЗ представляет собой стек, в который помещаются операнды и операторы. Подобная вычислительная модель используется в языке Форт [Moore, Leach 1970] , [Koopman 1989]. Обычно компилятор формирует содержимое стека во время синтаксического анализа текста программы. В предлагаемой реализации подхода этот процесс производится в несколько этапов. Вычислитель таких программ обычно достаточно прост: с вершины стека извлекается оператор, затем рекурсивно вызывается вычислитель для вычисления его операндов, оператор выполняется и результат возвращается вычислителем. В базовой реализации ТОМАТа эта схема в целом остается справедливой, однако технически реализуется более эффективным путем, рассмотренным ниже.

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

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

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

4. ^ Архитектура компилятора действий
   

Компилятор действий является составной частью компилятора ТОМАТа. Как уже говорилось, его задачей является построение стека программы для последующего многократного вычисления. Эта процедура проводится в три этапа.

• ^ Лексический анализ
  

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

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

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

• ^ Синтаксический анализ
  

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

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

• ^ Разрешение ссылок по именам
  

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

• ^ Оптимизация дерева
  

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

^ Без учета коммутативности выражения вида "Field + 2 + 3" не поддавались бы оптимизации, поскольку поддеревьев, состоящих из одних констант, в этом выражении нет.

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

• ^ Генерация кода
  

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

5. ^ Реализация исполнителя
   

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

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

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

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

6. ^ Морфологический препроцессор
   

В рамках проекта базовой реализации технологии "ТОМАТ" разработан морфологический препроцессор, который может быть использован в широком круге задач, связанных с автоматической обработкой текстов на естественном языке. На входе данный препроцессор получает текст (поддерживаются форматы Unicode Plain Text, RTF, HTML), на выходе строится система объектов на основе специально разработанной объектной модели морфологии. Данная модель морфологии разрабатывалась для русского языка.

1. ^ Обработка морфологической неоднозначности
   

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

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

1. ДЛЯ предл.

2. ДЛИТЬ гл., нсв., дееприч.


Это происходит потому, что морфологическая неоднозначность в данном случае имеет место на уровне лексемы. Аналогично, слову "книги" морфологический препроцессор поставит в соответствие объекты

1. КНИГА сущ., неодуш., ж.р., им.п., ед.ч.

2. КНИГА сущ., неодуш., ж.р., род.п., мн.ч.


Здесь это происходит потому, что омонимия затрагивает сразу две категории ­ число и падеж.

• И, наконец, третий вариант обработки омонимии морфологическим препроцессором ­ это порождение объектов специальных "сдвоенных" морфологических классов. Так, очень регулярной является, например, омонимия прилагательного и наречия в сравнительной степени (глубже может являться как формой лексемы ГЛУБОКИЙ, так и формой лексемы ГЛУБОКО). Раз это регулярное явление, то логично ввести в описание новый морфологический класс, сочетающий свойства прилагательного и наречия в сравнительной степени.
  

2. ^ Объектная модель морфологии
   

Приведем модель классов, описывающую модель русской морфологии в рамках технологии "ТОМАТ". Базовым классом модели является класс TextChunk, представляющий собой отрезок текста с координатами начала и конца:

<^ PClass Name = "TextChunk" >

<Field Name = "Text" DataType = "String" />

<Filed Name = "Start" DataType = "Integer" />

<Field Name = "Finish" DataType = "Integer" />

PClass>


От класса TextChunk наследуются служебные классы Delim и Number. Класс Delim соответствует знакам препинания в тексте, а класс Number - последовательности цифр:

<^ PClass Name = "Delim" BaseClasses = "TextChunk" />


<PClass Name = "Number" BaseClasses = "TextChunk" />

<Field Name = "Number" DataType = "Integer" />

PClass>


От класса Delim наследуется также класс Space, представляющий собой пробел или множество пробелов в тексте:

<PClass ^ Name = "Delim" BaseClasses = "Delim" />


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

<^ PClass Name = "Lexem" >

<Field Name = "Text" DataType = "String" />

<Field Name = "Homonym" DataType = "Integer" />

<Filed Name = "PoS" DataType = "TPartOfSpeech" />

PClass>


Поле PoS принадлежит типу TPartOfSpeech, который является перечислимым и задается следующим образом:

<Domain Name = "TPartOfSpeech" Tokens = "

noun

adj

adv

verb

pron

prep

conj

interj

" />


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

<^ PClass Name = "NounLexem" BaseClasses = "Lexem" >

<Field Name = "Gender" DataType = "TGender" />

<Field Name = "Animate" DataType = "Boolean" />

PClass>


Значения рода задаются перечислимым типом TGender:

<Domain Name = "TGender" Tokens = "

m

f

n

" />


Местоимение (к этому классу мы относим только личные местоимения) обладает словоклассифицирующей категорией лица:

<^ PClass Name = "PronounLexem" BaseClasses = "Lexem" >

<Field Name = "Person" DataType = "TPerson" />

PClass>


Значения лица задаются перечислимым типом TPerson:

<Domain Name = "TPerson" Tokens = "

pers1

pers2

pers3

" />


Глагол характеризуется словоклассифицирующими категориями транзитивности, вида и рефлексивности:

<^ PClass Name = "VerbLexem" BaseClasses = "Lexem" >

<Field Name = "Transitivity" DataType = "Boolean" />

<Field Name = "Aspect" DataType = "TAspect" />

<Field Name = "Reflexivity" DataType = "Boolean" />

PClass>


Значения вида задаются перечислимым типом TAspect:

<Domain Name = "TAspect" Tokens = "

compl

incompl

" />


Предложные лексемы содержат информацию о том, каким падежом данные предлоги управляют:

<^ PClass Name = "PrepLexem" BaseClasses = "Lexem" >

<Field Name = "GovernmentCase" DataType = "TCase" />

PClass>


Перечислимый тип TCase задается следующим образом:

<Domain Name = "TCase" Tokens = "

nom

gen1

gen2

dat

acc

instr

loc1

loc2

" />


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

дать сахара (gen1) vs. дать сахару (gen2)

говорить о саде (loc1) vs. находиться в саду (loc2)


Союз содержит информацию о том, какому типу принадлежит данный союз ­ сочинительному или подчинительному:

<^ PClass Name = "ConjLexem" BaseClasses = "Lexem" >

<Field Name = "Subordinative" DataType = "Boolean" />

PClass>


Остальные лексемы не имеют словоклассифицирующих категорий, поэтому представляются пустыми классами "ТОМАТа":

<PClass Name = "AdjLexem" BaseClasses = "Lexem" />

<PClass Name = "AdvLexem" BaseClasses = "Lexem" />

<PClass Name = "InterjLexem" BaseClasses = "Lexem" />


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

<^ PClass Name = "NounWordForm" BaseClasses = "TextChunk NounLexem" >

<Field Name = "Case" DataType = "TCase" />

<Field Name = "Number" DataType = "TNumber" />

PClass>


Объявление перечислимого типа TCase приведено выше при описании класса PrepLexem. Значения числа задаются перечислимым типом TNumber:

<Domain ^ Name = "TNumber" Tokens = "

sg

pl

" />


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

<^ PClass Name = "CompProp" >

<Field Name = "Compar" DataType = "TCompar" />

PClass>


Значения категории степень сравнения задаются перечислимым типом TCompar:

<Domain Name = "TCompar" Tokens = "

neutr

compar

superl

" />


От класса CompProp унаследован класс AdvWordForm и AdjWordForm. Класс AdjWordForm содержит словоизменительные свойства прилагательного: падеж, число, род, краткая форма.

<^ PClass Name = "AdvWordForm" BaseClasses = "TextChunk AdvLexem CompProp" />


<PClass Name = "AdjWordForm" BaseClasses = "TextChunk AdjLexem CompProp" >

<Field Name = "Case" DataType = "TCase" />

<Field Name = "Number" DataType = "TNumber" />

<Field Name = "Gender" DataType = "TGender" />

<Field Name = "Short" DataType = "Boolean" />

<Field Name = "Compar" DataType = "TCompar" />

PClass>


От классов AdvWordForm и AdjWordForm наследуется класс AdjAdvWordForm, представляющий собой сдвоенный морфологический класс (см. выше):

<PClass ^ Name = "AdjAdvWordForm" BaseClasses = "AdvWordForm AdjWordForm" >


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

<^ PClass Name = "PronounWordForm" BaseClasses = "TextChunk PronounLexem" >

<Field Name = "Case" DataType = "TCase" />

<Field Name = "Number" DataType = "TNumber" />

PClass>


Глагол характеризуется словоизменительными категориями времени, лица, числа, рода. Кроме того, глагол имеет ряд нефинитных форм, которые объединяют свойства глагола и другой части речи. Так, причастие объединяет свойства глагола и прилагательного, а деепричастие - свойства глагола и наречия, инфинитив - свойства глагола и имени. Нефинитные и финитные глагольные формы наследуются от общего класса VerbWordForm, который в свою очередь наследуется от классов TextChunk и VerbLexem и содержит свойство время и тип формы (финитная/нефинитная):

<^ PClass Name = "VerbWordForm" BaseClasses = "TextChunk VerbLexem" >

<Field Name = "Tense" DataType = "TTense" />

<Field Name = "Finite" DataType = "Boolean" />

PClass>


Значения времени задаются перечислимым типом TTense, объявление которого

<Domain ^ Name = "TTense" Tokens = "

fut

prs

pst

" />


Ниже приводятся описания различных форм глагола в виде классов:

<PClass Name = "FiniteVerbWordForm" BaseClasses = "VerbWordForm" >

<Field Name = "Person" DataType = "TPerson" />

<Field Name = "Number" DataType = "TNumber" />

<Field Name = "Gender" DataType = "TGender" />

PClass>


<PClass Name = "InfVerbWordForm" BaseClasses = "VerbWordForm NounWordForm" />


<PClass Name = "PartVerbWordForm" BaseClasses = "VerbWordForm AdjWordForm" />


<PClass Name = "ConvVerbWordForm" BaseClasses = "VerbWordForm AdvWordForm" />


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

7. ^ Экспериментальные планировщики
   

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

1. ^ Полный перебор
   

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

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

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

2. ^ Автоматизированный планировщик
   

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

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

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

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

Заключение

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

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

^ Основные результаты

К основным результатам данной работы можно отнести:

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

^ Применения предложенной технологии

Технология "ТОМАТ" создавалась как насущный инструмент для решения многих практически важных задач. И на момент публикации данной работы она уже успешно применяется в ряде проектов.

Одним из таких проектов является система автоматизированного построения информационной модели переводных двуязычных словарей. На вход системе подается текст словаря в том виде, в котором он попадает в издательство (текстовый файл со стилевым форматированием), на выходе получается структура объектов, представляющая всю информацию из словаря. Эта структура затем используется для генерации электронного представления словаря для использования в прикладной программе просмотра. Данная система обработки словарей используется в компании ABBYY Software House для подготовки лингвистических ресурсов, в частности, для системы электронных словарей Lingvo.

Еще одним применением предложенной технологии является использование ее реализации в качестве подсистемы подготовки исходных данных для системы Абриаль [Пацкин 2003] — распределенной сетевой базы знаний. Использование ТОМАТа в системе Абриаль позволило на порядок сократить время, затрачиваемое экспертом-лингвистом на информационное наполнение базы знаний в случае, когда знания извлекались из слабо структурированного текста на естественном языке. Более того, применение ТОМАТа расширяет круг задач, к которым применима система Абриаль, за счет включения задач, требующих динамического автоматического пополнения базы знаний информацией, извлеченной из поступающих в систему текстов.

^ Дальнейшие исследования

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

Кроме того, интерес представляет развитие метода анализа текстов за счет введения полей объектного типа (явная агрегация, описанная в классе, а не в шаблоне) — это может сделать описание предметной области в виде системы классов и шаблонов более удобным и точным.

Интересные перспективы имеет исследование вопросов адаптации ТОМАТа к некоторым задачам, для которых уже существуют относительно эффективные, но менее универсальные решения. Такие работы ведутся в рамках нескольких проектов в РосНИИ Искусственного Интеллекта, таких как InBase [Жигалов, Соколова 2001] и InDoc [Кононенко, Сидорова, 2001].

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