© Elijah Koziev 2010
Грамматический словарь русского языка
Поисковая система
SDK Поисковой системы
Экранный переводчик
|
|
изменено 16-Aug-11 | ||||||||||||||||||||||||||||||||||||||||||||||||||
Что такое продукционные правила
Конструктор результирующих пачек
Класс для хранения скомпилированного образа правила - PM_Rule (файл pm_rule.h), объявленный в пространстве имен Solarix.
Акторы (см. далее) - наследники класса PM_Actor (см. хидеры pm_actor.h и pm_actors.h).
Кондикторы (см. далее) - наследники класса PM_Condictor (см. хидеры pm_condictors.h).
Как работают продукционные правила при синтаксическом анализе? Очень просто. Допустим, мы хотим, чтобы предложение
спит кошка сладко
преобразовывалось (для чего - сейчас не важно) к виду:
кошка сладко спит
Если опустить несущественные детали, правило для преобразования будет иметь вид
если глагол существительное наречие то существительное наречие глагол
То есть условие - это комбинация в исходном предложении, при нахождении которой правило срабатывает и происходит создание (продукция) результирующего контекста. Левая часть - условие - называется кондиктором, правая - актором. Синтаксис кондикторов и акторов достаточно разнообразен, но в основном реализуется вышеописанная ситуация.
Общий форматпродукционных правил:
operator name [ : имя_категории ]
{
actor
}
Здесь name – произвольное имя, может включать кириллицу т любые допустимые в Unicode буквы.
Тело оператора состоит из единственного актора. Обычно это условный актор if-then-else, но в итераторах могут применяться и другие акторы (например, iterate и pass).
Опциональный параметр имя_категории используется для группировки правил. В дальнейшем можно вызвать (применить) все правила из некоторой категории, указав только имя этой категории (см. актор pass). О том, как объявляются категории, см. здесь.
Фигурные скобки, обрамляющие тело правила, обязательны.
Пример:
operator
Quest_10 : QUESTION_RULE
{
if context {
Вопрос }
then predicate it_is_quest. ->
local_var
}
Вообще говоря, существует два главных вида правил: собственно правила продукции и итераторы. Правила продукции определяют, как меняются вариаторы в ходе грамматического анализа. Итераторы контролируют общий ход грамматического анализа, вызывая определенные категории правил и заставляя крутится циклы до удовлетворения определенных критериев.
Внешне отличие между ними заключается только в том, что итераторы не имеют категории (она просто не имеет для них смысла).
Для удобства применения правила группируются в множества (далее - группы правил). Каждое правило может принадлежать только к одной группе.
Каждая группа должна быть явно объявлена (точнее говоря, должно быть объявлено ее имя) оператором
rulegroup произвольное_имя
В имени можно использовать кириллицу. Пример объявлений групп - в файле aa_rules_groups.sol в исходных текстах словаря.
Акторы – операторы, выполняющие определенные действия, например в then-ветке условного оператора (актора) if. Они реализованы классами-потомками базового класса PM_Actor (см. файлы pm_actr.h и pm_actrs.h).Каждый производный класс реализует один вид актора (например, класс PM_ActorContext реализует актор context, который создает и добавляет в текущую пачку решений новый вариатор).
1. actor ::= if condictor then actor1 [ else actor2 ]
Условный оператор. В зависимости от успешности выполнения кондиктора исполняется одна из веток. Реализован классом PM_ActorIf. Обратите внимание на обязательность использования ключевого слова then (в отличие от С).
Пример:
if context { ЕСЛИ* }
then context { Logic:If{} 1}
В данном примере первый context – это кондиктор, а второй – актор.
В зависимости от успешности проверки условия (кондиктора) выполняется один из двух акторов. Акторы в ветках then и else – любые (в том числе – условные).
Более сложный пример:
if context { ЕСЛИ* }
then
{
context { Logic:If{} 1}
context { Logic_2:If_2{} }
}
else
{
// пустая
ветка...
}
2. actor::= {actor1 actor2…actorn }
Группа акторов в фигурных скобках также фактически является одним актором. Реализован классом PM_ActorGroup.
Как и для языка C++, фигурные скобки позволяют с одной стороны создавать составной актор в случаях, когда синтаксически необходим один актор (например, для цикла while(...)), а семантически требуется много акторов. Кроме этого, фигурные скобки вводят новую область видимости локальных переменных - с обычными для C++ синтаксисом и семантикой.
3. actor::= context pack_builder
pack_builder– это описание конструктора результирующих пачек.
Создается пачка решений (обычно это все-таки один вариатор) и добавляется в текущую пачку решений. С помощью этого актора (вместе с условным актором) происходит продукция вариантов решения (вариаторов) в обрабатываемой пачке решений.
Реализован классом PM_ActorContext.
4. actor::= say pack_builder
pack_builder– это описание конструктора результирующих пачек.
Результат построения пачки помещается в очередь на вокализацию Голосового автомата. Практически это означает, что будет произнесена некоторая фраза. Принципы вокализации обсуждаются в разделе для Голосового автомата.
Реализован классом PM_ActorSay.
5. actor::= predicate description suffix [->base_name]
5.1 suffix::= .
5.2 suffix::= !
5.3 suffix::= ?
Правила описания предиката description следует смотреть в разделе о Прологе.
Имя базы данных base_name задается в случае, если предикат должен быть добавлен или исполнен в базе данных, отличной от принимаемой по умолчанию (глобальной).
Суффикс . (точка) означает, что предикат будет построен (но не выполнен) и добавлен в базу данных.
Суффикс ? (знак вопроса) означает, что предикат будет построен и выполнен (осуществлено его доказательство).
Пример:
predicate it_is_query.->local_var
Данный актор добавляет простой предикат (состоящий из одного атома) в локальную базу данных вариатора (с именем local_var).
Реализован классом PM_ActorPredicate.
Ключевое слово predicate необязательно, то есть если актор не распознан как один из прочих видов акторов, то выполняется его трансляция как актора predicate.
Реализован классом PM_ActorIterate.
Правила из указанной категории применяются в определенном порядке - от частных случаев к общим. Во-первых, это означает, что сначала применяются правила с более длинным проверочным контекстом. То есть, из двух правил одинаковой категории:
operator Rule_1 : 10
{
if context { СУЩЕСТВИТЕЛЬНОЕ ПРИЛАГАТЕЛЬНОЕ } then ...
}
operator Rule_2 :10
{
if context { СУЩЕСТВИТЕЛЬНОЕ ПРИЛАГАТЕЛЬНОЕ
ПРИЛАГАТЕЛЬНОЕ } then ...
}
сначала выполняется Rule_2, а затем - Rule_1, независимо от порядка объявления этих правил в тексте программы. После компиляции описания словаря транслятор выполняет пересортировку правил, причем принцип "сначала применяется частный случай" универсально. Для каждого правила вычисляется его сложность, причем это - целый набор чисел (см. структуру PM_RuleComplexity в файле pm_rule.h). Кроме числа узлов в проверочном контексте оценивается глубина деревьев, число проверяемых координатных пар, число конкретно заданных (в отличие от заданных полностью квантором или грамматическим классом) опорных точек.
Этот актор реализован классом PM_ActorPass.
8. actor ::=do arg0 arg1
Реализован классом PM_ActorDo.
9. actor ::= typename var1[="initialization" [, var2 ...]] ;
где typename ::= { string, int, tree }
Актор объявления и инициализации локальных переменных. Синтаксис максимально близок C++. Список возможных типов короток, и более того - он закрыт, то есть вводить новые типы нельзя (в этом собственно, нет и смысла).
Примеры:
string s1, s2="text_2";
int id_1=100;
tree tree_A = ИНФИНИТИВ:СПАТЬ{}.СУЩЕСТВИТЕЛЬНОЕ:КРОВАТЬ{};
Локальные переменные существуют в определенной области видимости, от объявления до конца текущего блока (внешнего актора). Правила существования и видимости локальных переменных соответствуют стандарту C++.
10. actor ::= while(prolog_query) loop_body;
Актор для организации цикла. Специфика заключается в том, что условием продолжения исполнения цикла служит успешность доказательства Пролог-выражения.При первом проходе цикла создается структура для доказательства запроса, и при каждом новом проходе цикла выполняется откат (backtrace) доказательства и поиск нового. В результате этого могут быть получены конкретизации локальных переменных пролог-выражения. Если эти локальные переменные ранее объявлены, то их значения доступны для использования в теле цикла.
Поясним вышесказанное на примере.
Допустим, в глобальной базе данных объявлена процедура из нескольких клозов:
prime(1).
prime(2).
prime(3).
prime(5).
Тогда актор
{
int Prime_value;
while( prime(Prime_value) )
{
... некие акторы
}
}
выполнит 4 прохода цикла с соответствующими значениям переменной Prime_value.
Более сложный пример показывает, как можно работать с грамматической информацией.
Итак, пусть в базе данных объявлена процедура modal_verb:
modal_verb( ПРЕДИКАТ:МОЧЬ{} ).
modal_verb( ПРЕДИКАТ:ДОЛЖЕНСТВОВАТЬ{} ).
modal_verb( ПРЕДИКАТ:ХОТЕТЬ{} ).
Фактически, таким образом объявляется список деревьев.
Акторы:
tree Verb;
while( modal_verb(Verb) )
{
context { Verb }
}
позволяют создать и добавить в текущую пачку решений три вариатора, каждый из которых содержит по одной опорной точке - с модальным глаголом. Следует привыкнуть к реализованному способу смешения процедурного языка C++ и декларативного языка Пролог. Если попробовать реализовать процедуру modal_verb посредством C++, то (одно из решений) нужно вводить статическую переменную - номер вызова процедуры, чтобы при каждом вызове возвращать очередное значение. Пролог позволяет те же действия выполнять с более кратким синтаксисом и с привлечением специальных оптимизированных механизмов поиска и извлечения данных из базы. Действительно, ничто не мешает запрос в заголовке while-цикла делать весьма сложным, с вызовом вспомогательных процедур (то есть с генерацией подцелей).
Конструктор результирующих
пачек
Кондикторы – это операторы проверки разнообразных условий для условного актора if.
Элементарные кондикторы:
1.1 condictor ::= context arg_list [ correlate corr_ist ]
где arg_list – описание опорного паттерна, с которым производится сравнение, corr_list – список требований к грамматическому согласованию координат в поступивших на вход словоформах.
1.2 condictor ::= do arg0
где arg – число.
1.3condictor ::= predicate description ?[->base_name]
Запрос к базе данных с помощью прологовского предиката (о синтаксисе пролога см. соответствующий раздел).
По умолчанию принимается база данных global.
Ключевое слово predicate может быть пропущено.
Кондиктор считается успешным, если предикат доказан (хотя бы один вариант).
При компиляции правила строится структура с объектами, соответствующими отдельным операторам (акторам). Сам код, выполняющий предписанные акторами действия, содержится в C++ классах (производные от PM_Actor и PM_Condictor). В принципе, именно так происходит с Java-программами - они тоже компилируются в некий промежуточный язык (байт-код). Конечно, ни о какой виртуальной машине в случае Solarix речи нет. Однако проблема эффективности кода стоит очень остро - при каждом анализе предложения на естественном языке вызываются и исполняются тысячи продукционных правил.
С другой стороны, компиляция кода в промежуточное представление имеет свои преимущества. Кроме малозначительных (типа высокой портабельности получаемого кода - можно скомпилировать правила транслятором под Linux и затем исполнять их под Windows XP), есть одно принципиальное: становится возможным манипулировать кодом при исполнении системы, в частности динамически создавать и удалять правила.
Чтобы не отказываться от концептуальных преимуществ динамической компиляции и увеличить эффективность кода, в систему введена частичная компиляция в машинный код. Рассмотрим на примере.
Допустим, есть правило:
operator Some_action : Some_category
{
if context { СУЩЕСТВИТЕЛЬНОЕ:*{} }
then ...некоторые
действия
}
При трансляции выясняется, что структура правила достаточно проста, в частности - кондиктор оператора if может быть преобразован в C++ код (см. метод PM_Rule::AllowsCompilation). В файл _aa_rulz.cpp будет добавлена процедура примерно такого вида:
static bool _aa_rule_Some_action( PM_SupContext
&context, const SynGram &gram, const vector<PA_PrologSpace*> &dbs )
{
if( ICLASS(0) != 6 )
return false;
}
Указатель на процедуру _aa_rule_Some_action запоминается (он хранится в объекте кондиктора). Файл _aa_rulz.cpp присоединяется к проекту и компилируется вместе с исполнимым кодом Системы. Наконец, при исполнении правила Some_action в грамматическом движке обнаруживается, что объект кондиктора хранит указатель на процедуру (если скомпилировать код не удалось, этот указатель будет равен NULL) и процедура вызывается.
В результате за счет такой глубокой компиляции самых часто выполняемых правил удается повысить эффективность кода в несколько раз. Кроме того, остается возможность удалить даже скомпилированное правило - так как объект, хранящий описание (кстати полное - включая структуру объектов для глубоко скомпилированных частей) остается обычным C++ объектом. Поэтому если правило будет изменено (с применением методов метапрограммирования), то не потребуется остановки работы Системы, вызова C++ компилятора и так далее - просто неактуальный машинный код не будет исполняться, а будет работать внутреннее представление правил.
В настоящее время глубокая компиляция реализована только для некоторых частей правил, где ее внедрение позволило получить сразу сильный эффект. В планах - реализация глубокой компиляции для других частей Системы.
Внутренний язык грамматической машины
API синтаксического анализатора
© Elijah Koziev 2010
Грамматический словарь русского языка
Поисковая система
SDK Поисковой системы
Экранный переводчик
|
|
изменено 16-Aug-11 | ||||||||||||||||||||||||||||||||||||||||||||||||||
