Технология построения многовариантных объектно-ориентированных структур текстов
| Вид материала | Диссертация |
- Ландшафт области управления данными: аналитический обзор, 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.
Эти операторы соответственно задают операцию пересечения множеств и теоретико-множественной разности (все элементы из первого, которых нет во втором).
- T ("in" | "eq") T: Boolean
Эти операторы соответственно задают операцию проверки (нестрогого) вложения первого множества во второе, и операцию проверки эквивалентности (совпадения всех элементов) множеств. Возвращается скалярное логическое значение ("False" либо "True") в зависимости от результата проверки.
- "?" T: Boolean
Оператор проверки непустоты множества. Возвращается скалярное логическое значение ("False" либо "True"), соответствующее условию "множество непусто".
- "[" T ("," T)* "]": T
Оператор объединения множеств. Имеет переменное число аргументов. О приоритете этого оператора говорить некорректно, так как квадратные скобки однозначно указывают на его аргументы.
Возможны и другие формы записи этого оператора, в том числе бинарная (эффективность не пострадает, так как оптимизатор сможет заменить поддерево бинарных операторов на один n-арный, существующий только во внутреннем представлении).
Далее следует описание скалярных операторов языка ТОМАТа. Если хотя бы один аргумент — пустое множество, то и результат будет пустым множеством, причем для бинарных операторов в случае, если первый аргумент — пустое множество, то второй не вычисляется в целях оптимизации.
- ("+" | "-") Integer: Integer
Выполняется соответствующая унарная арифметическая операция.
- ^ String "[" (Integer ("," Integer)* "]": String
Оператор индексирования строки. Он записывается как оператор объединения множеств типа Integer сразу после выражения типа String.
Такая форма записи оператора индексирования является скорее интересным синтаксическим трюком, основанным на синтаксисе языка ТОМАТа, предлагаемом базовой реализацией. Разумеется, возможны и другие формы записи этого оператора.
Результатом является множество строк, где каждая строка составлена из тех символов соответствующей исходной строки, индексы которых принадлежат указанному множеству целых. Если у некоторой строки первого операнда нет символов с такими индексами, соответствующим элементом множества результата будет пустая строка. Пустое множество получится, если множество индексов либо множество строк первого аргумента пусто.
- ^ Integer ("*" | "div" | "mod") Integer: Integer
Выполняется соответствующая арифметическая операция. Знак результата оператора "div" (деление нацело) такой же, как и у обычной математической операции деления. Деление нуля на нуль дает полное множество (полная неопределенность), деление на нуль ненулевого аргумента дает пустое множество. Оператор "mod" всегда действует по формуле: "A mod B = A - A div B", в том числе и для отрицательных аргументов.
- Integer ("+" | "-") Integer: Integer
Выполняется соответствующая арифметическая операция.
- String "+" String: String
Выполняется конкатенация строк.
- T ("=" | "<>" | "<" | ">" | ">=" | "<=") T: Boolean
Эти операторы осуществляют сравнение своих аргументов, понимая множества, как недоопределенные величины.
Для целых чисел выполняется обычное сравнение, для логических значений предполагается отношение полного порядка по принципу "False < True", причем вычисление может оптимизироваться (в нектороых случаях второй аргумент не вычисляется). Токены домена считаются упорядоченными в том порядке, в котором они присутствуют в описании домена. Для строк производится лексикографическое сравнение, причем символы с кодами от 32 до 126 считаются упорядоченными по возрастанию кодов, а все дополнительные символы могут сравниваться так, как принято в реализации технологии "ТОМАТ" (в базовой реализации считается, что символы упорядочены по возрастанию их Unicode-кодов).
Необходимо отметить, что сравнение двух множеств на точное совпадение необходимо выполнять с помощью других операторов. Так, сравнение "[2, 4] = [2, 6]" дает "[False, True]".
- "not" Boolean: Boolean
Выполняется операция "логическое НЕ", воспринимающая аргумент как недоопределенное логическое значение.
- ^ Boolean "and" Boolean: Boolean
Выполняется операция "логическое И", воспринимающая аргументы как недоопределенные логические значения. Вычисление может оптимизироваться: в нектороых случаях второй аргумент не вычисляется.
- ^ Boolean "or" Boolean: Boolean
Выполняется операция "логическое ИЛИ", воспринимающая аргументы как недоопределенные логические значения. Вычисление может оптимизироваться: в нектороых случаях второй аргумент не вычисляется.
- ^ Ядро системы анализа: компилятор и исполнитель
В этом разделе описываются общие принципы организации ядра системы анализа текстов — компилятора системы классов и шаблонов и исполнителя, осуществляющего преобразование системы объектов посредством применения шаблонов.
- Компилятор
Компилятор — это компонент технологии "ТОМАТ", который отвечает за формирование внутреннего представления проекта. На этапе исполнения, под которым в ТОМАТе подразумевается собственно процесс обработки данных, приходится пользоваться представлением элементов проекта (классов, шаблонов и т.п.), которое в угоду эффективности может значительно отличаться от представления банков проекта, которое непосредственно доступно пользователю. Очевидно, например, что на этапе исполнения все связи между сущностями из банков должны осуществляться не по именам, а каким-либо более эффективным способом, например, с использованием указателей или индексов. Более того, в структуре, используемой на этапе исполнения, вообще не нужно разделять проект на банки (хотя сохранить информацию о том, из какого банка взята сущность, наверняка будет полезно). Исполнитель и планировщик видят все шаблоны (и, следовательно, классы) одновременно, безотносительно модульности проекта.
Задачей компилятора, попутно с генерацией внутреннего представления, является также и проверка корректности проекта. Дело в том, что никакой редактор банков (разумеется, если он не содержит в себе компилятора) не способен оградить пользователя, редактирующего банк, от некоторых ошибок. Невозможно (а точнее, было бы неразумно) построить редактор, не оставляющий возможности, например, записать в качестве ограничения выражение, которое ссылается на несуществующее поле, или указать в качестве базового класс, который не определен — нужные сущности могут впоследствии оказаться в каком-либо из используемых банков. Требовать же на этапе редактирования банка наличия всех используемых банков (и их корректность) вряд ли разумно, так как банки, которые впоследствии войдут в один проект, могут разрабатываться разными участниками проекта, иметь разные версии и т.п.
Компилятор решает параллельно две задачи. Во-первых, он строит внутреннее представление для сущностей проекта, приспособленное для быстрого использования на этапе исполнения. Во-вторых, он компилирует во внутреннее представление все выражения и инструкции, определяющие действия. В качестве такого представления в модельной реализации был выбран ПОЛИЗ (польская инверсная запись), причем элементы, ответственные за выполнение той или иной операции над данными, представлялись адресами соответствующих функций программы, выполняющий нужное действие. Замечено, что такое представление делает вычисление выражений почти столь же эффективным, как если бы они были частью программы компилятора.
Компиляцию действий рекомендуется проводить в три этапа. Сначала построить представление действия, удобное для анализа, например, дерево. На этом этапе осуществляется лексический анализ языка действий. Затем произвести оптимизацию этого дерева, вычислив константные подвыражения, а также заменив некоторые операторы их оптимизированными версиями при появлении дополнительной информации об их аргументах. На последнем этапе произвести генерацию кода для действия.
- Исполнитель
Исполнитель является основным "действующим лицом" технологии "ТОМАТ". Его можно рассматривать как виртуальную машину, которая выполняет пошаговое преобразование системы объектов. На каждом шаге применяется тот или иной шаблон. Никаких других действий исполнитель выполнять не умеет. В этом разделе подробно описывается механизм применения шаблонов. Следует отметить, что исполнитель не принимает решения, в каком месте системы объектов какой шаблон применять. Это прерогатива планировщика, который вызывает исполнителя.
Исполнитель "видит" (имеет доступ) систему объектов, сформированную к текущему моменту, и представление времени исполнения для классов и шаблонов, подготовленное компилятором ТОМАТа и остающееся неизменным в течение всего времени обработки данных. Также на вход исполнителю для осуществления очередного шага подается один конкретный шаблон, и список объектов, которые требуется покрыть этим шаблоном.
Задача исполнителя чисто техническая. Он должен проверить, возможно ли покрыть шаблоном указанные объекты. В случае положительного ответа на этот вопрос, создается новый объект, а покрытые объекты получают нового хозяина — помещаются внутрь только что созданного объекта. Таким образом происходит достройка деревьев объектов. В случае невозможности применить шаблон, исполнитель оставляет систему объектов в исходном состоянии и выдает отрицательный ответ.
Здесь следует особо рассмотреть поведение исполнителя применительно к неоднозначным деревьям объектов. Как уже отмечалось, в технологии "ТОМАТ" логически система объектов представляет собой список деревьев. Если добавить еще один воображаемый корневой объект, то этот список превратится в единое дерево, поэтому для краткости будем называть этот список просто деревом объектов. Но на самом деле существует возможность представить любое количество таких альтернативных деревьев, имеющих общий набор объектов в качестве вершин. Тогда изображение графа системы объектов получается наложением изображений всех деревьев на общее изображение всех вершин. Технически нет никакой необходимости помечать дуги, к какому дереву они относятся. Для корректного дальнейшего построения (достройки) деревьев достаточно знать, какие объекты состоят в биективном отношении несовместимости — это любые объекты, имеющие общих детей (любой степени вложенности, а не только непосредственных) либо находящиеся в отношении родитель-дочерний. Применение шаблона заключается в добавлении нового объекта и связывании его отношениями родитель-дочерний с теми объектами, которые покрываются узлами шаблона. При этом никакие два из покрываемых объектов не могут находиться в отношении несовместимости.
Собственно алгоритм применения шаблонов достаточно прост. Будем считать, что никакие из покрываемых узлов не находятся в отношении несовместимости. Тогда сначала проверяется соответствие классов объектов классам узлов шаблона. При этом проверка выполняется с учетом преобразования типа — объект любого класса можно рассматривать как объект класса, являющегося базовым для действительного класса объекта. При этой проверке происходит сопоставление каждому узлу шаблона нуля или более объектов, причем учитывается указанное в узле ограничение на количество покрываемых им объектов. Процесс сопоставления объектов очередному узлу заканчивается, когда нашлось количество подряд идущих покрываемых объектов нужных классов, не меньшее минимально допустимого для узла, и как можно большее, но не превышающее максимально допустимое. Если такое количество не находится, то считается, что шаблон применить не удалось.
Далее для узла выполняются действия, то есть вычисляются выражения, представляющие ограничения на узел. Эти ограничения могут формулироваться с использованием значений полей покрываемых узлом объектов. Если хотя бы одно ограничение не выполняется, то применение шаблона признается неуспешным и отменяется.
После успешной проверки ограничений для узла осуществляется переход к следующему узлу. После того, как каждый узел получил список покрываемых им объектов, осуществляется выполнение действий, указанных в шаблоне, а затем и в классе. Этими действиями может быть присваивание значений выражений полям создаваемого объекта, а также проверка ограничений, сформулированных с использованием значений как покрытых объектов (только для ограничений в шаблоне), так и уже получивших значения полей нового объекта.
- ^ Представление системы объектов
В этом разделе обсуждаются вопросы представления системы объектов, обеспечивающего эффективность программной реализации предлагаемого метода анализа текстов. Проводится сравнительный анализ альтернатив и формулируются рекомендации.
- ^ Структура объекта
Объект является объектом программы обработки текста. С концептуальной точки зрения понятие объекта может быть представлено классом объектно-ориентированного языка программирования, на котором реализовано ядро ТОМАТа. В то же время следует отметить, что технически такое представление не обязательно, особенно в языках, накладывающих значительные ограничения на устройство объектов классов, например, Object Pascal, на котором была выполнена базовая реализация, Java и др. В таких гибких языках, как C++, объекты могут быть объектами класса в любом случае, даже имея собственное распределение памяти и специфическую структуру.
Объекты могут иметь в системе несколько представлений. Одно из них (обязательное) — это внутреннее представление времени исполнения, которое используется для построения системы объектов в оперативной памяти. Другим может быть внешнее представление для хранения системы объектов в файле, например, бинарном. Еще одно представление — текстовое — может быть полезно для отладки реализации ТОМАТа, а также для непосредственного слежения за работой системы. Оно отличается от внешнего бинарного явным использованием имен.
Независимо от внутреннего представления объекта, он, как сущность предметной области, характеризуется следующей структурой.
- ^ Ссылка на класс
Объект, обязательно являясь экземпляром некоторого класса, должен знать, к какому классу он относится. Технически для внутреннего представления объекта это должна быть ссылка на внутреннее представление класса (она нужна для проведения операции приведения типа — поиск базового класса), в текстовом представлении объекта это может быть квалифицированное имя класса.
- ^ Ссылка на шаблон
Объекту может понадобиться знание о том, каким шаблоном он был построен. На практике достаточно хранить ссылку на внутреннее представление шаблона, а ссылку на класс получать через неё.
- Индекс
Для нормальной работы планировщика предлагается хранить в каждом объекте индекс, по сути представляющий собой порядковый номер объекта с точки зрения хронологии его создания, то есть первый созданный объект получает нулевой индекс, далее каждый вновь созданный объект получает на единицу больший индекс.
- ^ Список значений полей
Являясь экземпляром класса, объект должен хранить полный набор значений полей класса. Разумеется, учитываются не только поля, описанные в классе объекта, но и все унаследованные, в том числе косвенно, от базовых классов. При этом порядок перечисления этих значений должен в точности соответствовать порядку описания полей в классах при некотором фиксированном обходе графа наследования с обязательным исключением повторно встречающихся базовых классов.
Такое упорядочение списка значений полей позволяет освободиться от хранения ссылок на поля класса для каждого значения, таким образом, сделав представление объекта более компактным.
- ^ Список дочерних объектов
В силу многовариантности структур объектов этот список должен быть именно списком ссылок, а не набором вложенных объектов — один и тот же объект может входить в несколько объектов в качестве дочернего. В зависимости от представления (внутреннее, бинарное, текстовое) эти ссылки могут быть указателями в памяти, индексами в массиве объектов или идентификаторами объектов.
- ^ Списки ссылок на следующие и предшествующие объекты
Эти два списка собственно задают отношение частичного порядка на множестве всех существующих объектов. Это отношение используется планировщиком при выяснении, какие "соседние" объекты следует пытаться покрыть узлами шаблона.
- ^ Отношение несовместимости
Как отмечалось в главе, посвященной концепции технологии, многовариантное построение деревьев (точнее, сети) объектов требует рассмотрения отношения несовместимости. Это отношение накладывает ограничения на строительство сети таким образом, чтобы сеть всегда представляла собой многовариантное дерево.
Несовместимость двух объектов означает, что они не могут быть покрыты одним шаблоном, и, следовательно, не могут войти оба в качестве дочерних объектов для некоторого строящегося объекта. С точки зрения предметной области несовместимость объектов означает, что они представляют альтернативное распознавание одной и той же текстовой конструкции, либо двух пересекающихся. Если мы захотим рассмотреть один из вариантов построенного дерева, то в нем не будет несовместимых объектов, таким образом, можно считать, что отношение несовместимости означает взаимоисключаемость связанных этим отношением объектов в отношении вхождения в построенное дерево.
Реализация этого отношения должна удовлетворять нескольким критериям эффективности. Перечислим их в порядке значимости для эффективной реализации процесса анализа.
- Быстрая проверка отношения исполнителем
- Быстрое пополнение отношения
Кроме того, отношение несовместимости, само по себе, является биективным и транзитивным. Это позволяет дать рекурсивное определение случаев несовместимости объектов. Итак, два объекта несовместимы, если они имеют хотя бы один общий дочерний объект, либо если они состоят в отношении "объемлющий-дочерний", либо если они несовместимы в силу транзитивности отношения несовместимости.
Отношение несовместимости предлагается выводить из отношения частичного порядка, заданное соответствующими списками ссылок в объекте.
Не следует забывать, что препроцессор, подготавливая многовариантную начальную цепочку (или даже последовательность деревьев) объектов, должен правильно задать начальные отношения несовместимости. Впрочем, для тривиального препроцессора, просто выдающего цепочку объектов системных классов, это не сложно.
- ^ Виртуальные объекты
При решении некоторых задач с помощью предлагаемой технологии может возникнуть следующая ситуация. Предположим, уже написана часть прикладной программы, которая обрабатывает некоторую систему объектов. Возможно даже, что реализованы и некие алгоритмы, подобные используемым в технологии "ТОМАТ", но в виде жестко заданного кода на языке программирования общего назначения, на котором пишется прикладная программа. Далее возникает желание адаптировать уже написанный код для использования в качестве "двигателя" анализа ядро ТОМАТа, реализовав описание процесса анализа в виде адекватной системы классов и шаблонов.
Тривиальным решением проблемы будет использование имеющейся реализации ядра, включая представление системы объектов, и подготовка специфического препроцессора и планировщика, код которого отражает специфику анализа данных разрабатываемым приложением. Также придется программировать некий перекодировщик результирующей системы объектов в систему объектов прикладной программы. Таким образом, наличие этого перекодировщика и препроцессора существенно снизит эффективность обработки.
Возможен и другой подход, свободный от упомянутого недостатка. Он получил название "техника виртуальных объектов". Идея состоит в том, чтобы не вводить в ядре специальный класс объектов, представляющих объекты, а реализовать исполнитель, работающий с абстрактными объектами через определенный интерфейс. Одна из реализаций подобного подхода представлена в базовой реализации ТОМАТа.
Интерфейс к виртуальному объекту будет работать напрямую с внутренним объектом прикладной программы или даже с его частью, а исполнитель будет реализован именно в терминах объектов. Для планировщика же никаких объектов может не существовать, он может непосредственно работать с объектами приложения. При этом понадобится только некий механизм перевода форматов значений полей, но при близости концепций типов данных ТОМАТа и прикладной программы, этот механизм реализуется легко и эффективно.
Можно порекомендовать использование такой техники, в частности, для непосредственной обработки данных, представленных в реляционной базе данных, с помощью технологии "ТОМАТ".
- ^ Базовая реализация
В данной главе детально описывается базовая реализация предлагаемого метода анализа текстов. Прежде всего обсуждается выбор стандартов и технологий, на которые было решено опираться в реализации. Далее приводится описание представления системы классов и шаблонов, синтаксиса языка действий и представления системы объектов. Также рассматривается архитектура ядра системы и устройство морфологического препроцессора. В заключение приводится описание двух экспериментальных планировщиков.