V (кдс-прививка)

^ (Корь]

Информационная секции с правилом "несколько из” будет конкретизо- вана, если выполнена интерпретация ее атрибута на множестве ее слотов, при которой могут быть выбраны как один, так и несколько слотов (и даже все), и выбранные элементы (слоты) является конкретизованными.

Конкретизация ИнС с правилом "ГГ ("повтор") предполагает указание требуемого количества повторений единственного слота такой секции. На­пример, секция вида

(приветствие!

П

I— fyp*]

можег быть конкретизована как

I приветствие]

I— (Ура] j— (Ура]

¹— (Ура) .

Конкретизация ИнС с правилом "Н" ("необязательно") предполагает либо указание необходимости сохранить слот секции, либо удалить его (за­менив "пустой" константой). Например, конкретизация секции вида

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

в "И".

Метод перевода как меюд конкретизации КМИ предполагает наличие формальной модели процесса перевода. Учитывая, что исходный и результи­рующий КМИ должны отвечать определенным синтаксическим правилам (определяемым базовой моделью представления метаинформации и правила­ми конкретизации), процесс конкретизации можно было бы рассматривать как процесс синтаксически управляемого перевода, для которого в теории компиляции разработан целый ряд схем и моделей /14, 15,233,234/. Однако, благодаря наличию неконкрстизованных слотов и секций, исходный КМИ имеет вариантную структуру, недетерминизм которой может бьггь устранен только на основании внешней информации, задаваемой пользователем (чело­веком, осуществляющим управление процессом перевода). Строго говоря, не­обходимые данные могут поступить и из другого источника - например, от какой-то другой программы, или специальных процедур, вычисляющих эти данные по определенным решающим правилам и т. д. Эти варианты далее не рассматриваются как несущественные для построения модели процесса пере­вода - в приведенной далее модели достаточно переопределить пользователя

как поток конкретизирующих данных. Тем не менее, весьма примечательно, что запоминание один раз заданного пользователем потока конкретизирую­щих данных позволят получить такой же конкретизовапиый КМИ уже без участия пользователя. Эта особенность используется в методике, описанной в п. 4.Э.

Таким образом, конкретизация не может быть представлена как класси­ческий перевод, управляемый только синтаксисом. Учитывая управляющий характер потока конкретизирующих данных, процесс конкретизации можно считать переводом, управляемым синтаксисом и данными (СДУ-переводом - по аналогии с термином СУ-псрсвод, используемым в /14,15/).

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

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

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

Поскольку никакой зависимости требований в содержанию информаци­онной секции или элемента от его места в ИСФ не существует (что подтвер­ждается фактом принадлежности грамматик приведенных в п. 3.2 лингвисти­ческих средств представления МИ к классу контекстно-свободных грамма­тик), грамматика, задаваемая подлежащим переводу КМИ (далее - описы­вающая грамматика (ОГ)) будет контекстно-свободной.

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

Формальную модель указанного выше преобразователя можно считать абстрактным процессором СДУ-перевода (далее - СДУ-процессором).

Пусть переводу подлежит некоторый (произвольный) КМИ S_u для ко­торого имеются S₂, S3,..., S„, (m > 0) достижимые из него КМИ.

Отношение "достижим" рассматривается как транзитивное замыкание отношения "непосредственно достижим": а непосредственно достижим Ь, ес­ли if и Ь- ИСФ, ива имеется внешняя ссылка, объект которой принадлежит Ь.

Очевидно, что для осуществления перевода КМИ Si управляющая таб­лица (УТ) СДУ-процессора должна содержать описывающие грамматики для каждого КМИ из множества что может быть достигнуто по­

средством применения следующего специально разработанного алгоритма.

Алгоритм Формирования управляющей таблицы СДУ-процессора Вхрл: S = {$i,$2»---,Sni} - множество КМИ, из которых переводу подлежит Si, а остальные (S2.• -• »S_m) - достижимы из него.

Выход: U - управляющая таблица СДУ-лроцессора, способного осуществить перевод Si в конкретизированную форму.

Процесс:

Шаг I

Каждый КМИ будем идентифицировать его номером в множестве $. Начиная с КМИ с номером "Г и далее - произвольном порядке, выполнить идентифи­кацию элементов каждого компонента - путем нисходящего обхода дерева фреймов (порядок обхода безразличен) и назначения идентификаторов каж­дому имени фрейма и каждому слоту-константе (внешние ссылки не обраба­тываются). Идентификатор любого элемента определяется как точечная пара х.у, где х - номер компонента (индекс шаблона в множестве S), у - номер эле­мента в компоненте (значение счетчика элементов компонента) при обходе ИСФ. Нумерация элементов в ИСФ начинается с корневого имени, которому присваивается номер " I".

Шаг 2

Начиная с КМИ с номером ”1" и далее - произвольном порядке, выполнить идентификацию внешних ссылок. Каждая ссылка получает идентификатор в виде 3D.А, где А - имя объекта ссылки, вычисляемое по значению слота- ссылки, ID - его идентификатор в виде точечной пары в том КМИ, где он на­ходится.

ШагЗ

1. i:=l;

2. Множества Nj, T_it Р* := 0 (Nj, T*, P, - множества нетерминальных симво­лов, терминальных символов и правил продукции КМИ с номером i).

3. Выполнить нисходящий обход дерева фреймов ИСФ, являющейся ком­понентом с номером i (порядок обхода безразличен), осуществляя обработку каждого фрейма следующим образом:

если фрейм - ИЭ с именем Ш_Л.А и слотом IDn-B, то добавить в Pj правило вида ID_a.A -> IDn.B; добавить в Nj нетерминальный символ ID_a.A; если слот В - слот-константа, то

добавить в Tj терминальный символ ID».В иначе (В - слот-ссылка, над которым произведена операция замены на шаге 2) добавить в N, нетерминальный символ ID_B.B если фрейм - ИнС с именем ID_a.A. множеством слотов В={Шв|.В_ь Ювг-Вг,..., IDba-Bq} и правилом конкретизации Рс, то

добавить элементы множества В в множества Tj (слоты-константы) и N, (результаты замены слотов-ссылок) добавить в Nj нетерминальный символ ГОд.А; если Рс = "И", добавить в Pj правило вида 1D,|.A -> ID₀₁.B, ГОвЛ ... ID_Bn.B_n; если Рс = ’ИЛИ", добавить в Р, п правил вида Ю_АЛ —> Ш|ц.В| |IDb2-B> | ••• I IDbh-Br; если Рс ^в "МИЛИ", добавить в Р, все возможные правила вида ГО_л.А -> aia₂...«P., где а, либо равно ID_Bi.Bj, либо пусто, если Рс = "Н", добавить в Pj правила вида

Шд.А -> ID_B| B| | С, где С - "пустая^и константа 1D - се иден­тификатор х.у, где х • номер компонента спецификатора, у - зна­чение счетчика элементов в ИСФ, увеличенное на 1 если Рс = "ГГ, добавить в Pi правила ID_a.A->ID_b,.B,|IDb..B, ID_a.A

4. Vj:=(i.l,Aj.i) - начальным символом Vj грамматики для i-ro КМИ считать пару из идентификатора и имени корневого элемента.

5. ty:=(NbTi,Pi,Vi) - зафиксировать ОГ Ц, соответствующую i-му КМИ.

6. Если i<m, то i:=i+l; переход на шаг 3.2; иначе переход на шаг 4.

Щаг4

Сформировать управляющую таблицу СДУ-процессора как множество, эле­ментами которого являются все полученные ОГ: U = {Ui, ЧЬ,..., U_m }•

Управляющая таблица, полученная в результате применения приведен­ного алгоритма, представляет собой множество ОГ. С позиций абстрактного СДУ-процессора УТ можно рассматривать и как объединение множеств U|, U* ..., U_m - введенная система идентификаторов это позволяет. Однако с точ­ки зрения программной реализации процессора нецелесообразно одновре­менно хранить в оперативной памяти ЭВМ ОГ всех компонентов специфика­тора, так как в любой момент перевода активной будет только одна ОГ, а сис­тема идентификации элементов ИСФ дает возможность выявлять все момен­ты перехода от одной ОГ к другой и осуществлять процессы загруз­ки/выгрузки элементов множества U (фрагментов УТ) с переключением про­цессора с одного фрагмента на другой. Кроме того, наличие ссылки из ком­понента а на объект в компоненте b еще не означает обязательного использо­вания КМИ b в процессе перевода — эта ссылка может оказаться вершиной, которая будет отброшена при конкретизации одной из секций на пути к ней из корня КМИ.

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

Процессор, осуществляющий СДУ-перевод При синтезе СДУ-процессора за основу взят автомат с магазинной па­мятью (МПА), реализующий нисходящий разбор (вывод) /14,15/, существен­но модифицированный с учетом изложенных выше особенностей процесса конкретизации КМИ. Структура процессора изображена на рис. 3.8.

Рис. 3.S. Структура СДУ-процессора

В сравнении с классическими синтаксическими распознавателями, реа­лизуемыми как МПА, СДУ-процессор имеет следующие особенности: входная лента отсутствует;

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

По аналогии с описанием МПА в /14/ с учетом внесении^ изменений СДУ-процессор может быть представлен в виде формальной системы Р = (Q, Г, a, q₀, mo, F, U, u₀, Z, R, D), где Q - множество состояний УУ;

Г - алфавит магазина;

а - правила отображения вида Q х Г xZxR->QxPxZ*x R*x D*, формирование которых описано ниже;

<1о - начальное состояние УУ (q₀ е Q); т₀ - символ дна магазина (то € Г)>

F - множество заключительных состояний УУ (F с Q);

U - управляющая таблица, состоящая из ш фрагментов; uo - начальный номер активною фрагмента УТ;

Z - алфавит запросов к пользователю;

R - алфавит ответов пользователя;

D - алфавит выходной ленты. ,

Под конфигурацией СДУ-процессора понимается совокупность

(q, i, aw, о, у, г),

где q - состояние У У; i - номер активного фрагмента УТ;

aw - содержимое магазина (а е Г, w е Г*, а - символ в вершине магази­на);

<о - содержимое выходной ленты (0) € D*); у запрос к пользователю (7 е z и {е}); к - ответ пользователя (se Ru {е}); с — пустая цепочка (цепочка нулевой длины).

11онятие отношения "такт" для СДУ-процессора совпадает с аналогич­ным понятием для МПА, описанного в /14/, а условия выполнения такта рас­ширено следующим образом:

если у = у, то в данном такте запрос к пользователю не формируется;

если £ = е, то в данном такте ответ пользователя не анализируется.

Формирование СДУ-процессора, обеспечивающего перевод (конкрети­зацию) КМИ Si, осуществляется в виде следующей последовательности дей­ствий:

1. Сформировать УТ U={U|,U2,...Um) по SI и достижимым из него S2, S3» •••> S_m (m 2 0), используя приведенный выше алгоритм.

2. Положить Q = {q, г, z, f} (где q, г, z, f - фиксированные имена состоя­ний УУ), Г = N v Т \J {@}, где @ - символ (маркер) дна магазина, N = N10 N2и ... u N_m и Т ■ Tj u Т2 vj ... u T_m- соответственно объединения множеств нетерминальных и терминальных символов ОГ, составляющих УТ U.

3. Положить qo=q,mo=@,F = { f },uo= 1.

4. Положить Z = N* vj Т* u {l,2,...,n}, где п - максимальное количество слотов в фрейме, R - {1, 2, ..., п ) и А_р> где А_? - алфавит, допустимый при конкретизации пользователем неконкретизованных констант, D = N и Т и А_р.

5. Определить отображение о.

Отображение ст представляет собой совокупность правил, определяю­щих выполнение тактов СДУ-процсссором и формируемых следующим обра­зом:

1. (Va)(a€?T)(a^"?"): o(q, i, (i.y,a), со, e, e) = (q, i, e, ©a, e, e) - терминаль­ный символ, соответствующим конкретизованной константе, переносится из вершины магазина на выходную ленту;

2. (Уа)(аеТХа^=,,?^п): a(q, i, (i.y,a), со, е, е) = (z, i, е, (о, а, е) - если в вер­шине магазина находится терминальный символ, соответствующий неконкре- тизованной константе, то он выбрасывается из магазина, УУ переход в со­стояние Z, а в блок интерфейса поступает запрос к пользователю на конкрети­зацию этой константы;

3. (Va)(aeT)(a="?"): o(z, i, w, со, a, e) = (r, i, w, со, a, b) - поступление от блока интерфейса ответа пользователя (Ь) на запрос о конкретизации иекон- кретизованной константы (а) переводит УУ в состояние г;

4. (Va)(a€T)(a="?"): c(r, i, w, со, a, b) = (q, i, w, cob, с, e) - значение (b), приписанное пользователем неконкретизованной константе (а), заносится на выходную ленту, а У У переходит в состояние q;

5. (VAXAeN): 0(2, i, (х.у,А), о>, е, е) * (q, х, (х.у,А), со, е, е) - если на вершине магазина находится нетерминальный символ, идентификатор кото­рого содержит номер фрагмента УТ (х), отличный от номера активного фраг­мента УТ (i), то происходит смена номера активного фрагмента на х;

6. (Vi)(VA)((i.y,A)€N,) ( \{ р| А a }j = 1 ): o(q, i, (i.y,A), со, e, e) = (q,

1. а’¹, со, e, e) — для всех нетерминальных символов, имеющих только одно правило продукции, появление такого символа на вершине магазина приводит к его замене на правую часть соответствующего правила продукции, записан­ную в обратном порядке;

7. (Vi)(VA)((i.y,A)€Ni) (| ГР,! А -» a }| > 1): a(q, i, (i.y,A), <о, е, е) = (z, i, е, о, {(i.y,A)} и {(k,aO | Л -> at ePj), е) - для всех нетерминальных символов, имеющих альтернативные правила продукции, символ выбрасывается из ма­газина, в блок интерфейса помещается запрос к пользователю на выбор одно­го из правил (будем считать, что запрос представляет собой нетерминальный символ и множество пронумерованных от I правых частей альтернативных правил продукции), У У переходит в состояние z;

8. (Vi)(VA)((i.y,A)€Ni) ( |{Р_{ I А -> a }| > 1): a(z, i, w, со, {(i.y,A)} u {(k,«k) J A-m_k €Pj}, e) = (r, i, w, ©, {(i.y,A)} u {(k,a_fc) | A-»a_k €P;}, p) - полу­чение на запрос о выборе альтернативного правила ответа (р) от пользователя переводит У У в состояние г;

9. (Vi)(VA)((i.y,A)eN,) ( |{Р; | А -» a }| > 1): o(r, i, w, со, {(i.y.A)} kj {(k,«k) I A -> a% еР;}, p) - (q, i, a_p''w, со, e, e) - в магазин помещается правая

часть (записанная в обратном порядке) того правила продукции* номер кото­рого содержится в ответе пользователя (р), а УУ переходит в состояние q;

10. a(q, I, о, е, е) = (f, i, е, со, е, е) - если при У У в состоянии q в ма­газине находится только маркер дна магазина, то УУ переходит в заключи­тельное состояние f и процессор завершает свою работу.

Начальной конфигурацией СДУ-процессора является (q, 1, (l.l,A_u)@, е, е, е), а заключительной - (f, i, е, to, е, е).

Функционирование СДУ-процессора представляет собой последова­тельность тактов, соответствующих переходу процессора из начальной кон­фигурации в заключительную: (q, 1» (1.1 ,Ai i)@, е, е, е) |—* (f, i, е, (о, е, е).

Используя аппарат, приведенный в /14/, можно показать, что СДУ- процессор реализует левый вывод в рамках грамматики U. Аналогичный МПА с одним магазином, реализующий нисходящий вывод без возвратов, в общем случае был бы недетермниирован в силу наличия хотя бы одного не­терминального символа, имеющего несколько альтернативных правил вывода

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

Другим источником недетерминизма в процессе вывода может служить неопределенность в выборе нетерминального символа текущей сентенциаль­ной формы для выполнения следующего шага вывода. В описанном выше СДУ-процсссоре для вывода всегда выбирается самый левый нетерминаль­ный символ (замена а'¹ на а в правилах вида 6 и 9 приведет к тому, что про­цессор будет выполнять правый пывод).

Наложенное выше ограничение на порядок выполнения вывода не явля­ется принципиальным и может быть снято путем введения дополнительных n-1 магазинов,

где n - максимальная ширина кроны дерева выводами хранением дополнительных сведений о навигации фокуса.

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

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

расширить алфавить: Г и Г) символами ")” и "(";

добавить правило переноса символа ")" из магазина на выходную ленту n(q, i,), о, е, е) = (q, i, е, со), е, е); правила вида 6 изменить на a(q, i, (i.y.A), о>, е, е) = (q, i, а'¹), й>(А, е, е); правила вида 7 изменить на a(q, i, (i.y,A), со, е, е) = (z, i, е, со(А, {(i.y,A)} ^ KMk) IЛ а_к еРЛ, е);

правила вида 9 изменить на a(r, i, w, со, {(i.y,A)} vj {(к,ак) | А —> ос^ ePj}» р) = (q, i, а_р'' )w, «(А, е, е).

После внесения указанных изменений содержимое выходной ленты бу­дет представлять собой запись ИСФ в скобочной нотации, совпадающей с но­тацией базового языка представления метаинформации, описанного в прило­жении 1 - за исключением того, что тип секций (символ ^ИИ^И) будет опущен, а различий между записью ИнС и ИЭ не будет. Если это вызывает какие-либо

затруднения с позиций реализации вычислительной семантики копкретизо- ванного КМИ, то достаточно ввести в идентификаторы атрибутов ИЗ некий признак, при наличии которого будет использоваться правило б, а при отсут­ствии - правило 7 и еще одно правило, полученное из правила номер 6. В двух последних правилах на выходную ленту вместо ”w(A" должны записываться символы "w(H А^н - тогда совпадение с базовым языком будет полным.

Возможность наличия ИС с правилом конкретизации "повтор из" при­водит к возможности появления рекурсивных правил в ОГ (в соответствии с алгоритмом, приведенным выше - праворекурсивных, хотя вид рекурсии в данном случае несущественен). В свою очередь, наличие рекурсивных правил порождает в результирующем дереве кшпи идентичных вершин. Выявление и устранение кистей в дереве спецификаций может быть выполнено с помощью соответствующего алгоритма (см., например, /14, 80/). Такое преобразование, пример которого приведен на рис. 3.9, снижает сложность результирующего дерева, характеризуемую оценкой дерева, за счет уменьшения количества внутренних вершин.

Рис. 3.9. Пример устранения ассоциативных вершин

Описанные алгоритм и процессор не только уникальны сами по себе - демонстрация возможности применения МПА для описания вывода на ИСФ (тем более - в интерактивном режиме) и использованная система идентифи­кации символов алфавита как элементов сети фреймов являются оригиналь­ным подходом к

формализации описания процессов вывода на иерархических структурах.

Программная реализация СДУ-процессора может быть самой различ­ной. В качестве демонстрационного примера в приложении 3 приведено опи­сание процесса формирования УТ, синтеза СУД-npoiicecopa, его программной реализации на языке Пролог (в силу выразительности этого языка при описа­нии тактов и состояний) и результатов его функционирования.

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

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

Описание способа задания вычислительной семантики предполагает определение:

способа перебора (последовательности обработки) элементов компо­нента метаинформации;

правил вычисления значений для каждого вида элементов КМИ (слота, фрейма);

правил использования вычисленных знамений.

В целом интерпретация КМИ как процесс вычисления значений его элементов может рассматриваться как процесс вывода (синтеза) по иерархи­ческим структурам /219/.

Благодаря разработанной модели представления МИ любой КМИ имеет древовидную структуру, способы перебора элементов которых хорошо известны

- это всевозможные разновидности обхода дерева (в глубину, в шири­ну, нисходящий, восходящий, левосторонний, правосторонний и т. д. - /164, 235-237/и др.).

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

Композиция содержимого атрибутов и слотов фреймов. Данный способ предполагает, что результатом интерпретации является последовательность значений вершин КМИ, формируемая в процессе обхода его дерева. Значе­ниями листьев дерева интерпретируемого КМИ являются значения конкрети­зированных констант и внутренних ссылок (как значения объектов ссылки), а внутренних вершин - атрибуты соответствующих фреймов (имена ИнС и ИЭ).

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

{Сервисное обслуживание жесткого диска]

|—-[Проверка файловой системы]

I—[scandisk.exe]

|—[дефрагментация диска]

*—ldefra9.exe]

I—[архивация содержимого каталогов]

I—'[c:\mai и]

;—[c:\workJ ^L [d:\mail]

можно получить результирующую последовательность вида [scandisk.exe][defrag.exe][c:\main][c:\work][d:\mail] пьшолнив левосторонний восходящий обход этого КМИ. Полученную последовательность можно обработать (выполнить) далее - с учетом семан­тики ее элементов. Для приведенного примера такая обработка может пред­полагать либо непосредственный вызов соответствующих сервисных про-

грамм,

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

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

[*]

И

М3)

4+1

и

|—I5J

Мб]

постфиксный обход ласт результат вида [356+*], который является об­ратной польской записью арифметического выражения, и по этой записи мо­гут быть выполнены как непосредственно вычисление искомого значения, так и генерация кода для подобного вычисления. В этого обхода вершинам [3], [5], [6] будут присвоены (поставлены в соответствие) значения (3), (5) и (6), а вершинам [+] и [*] - (56+) и (356+*) соответственно. Несмотря на кажущуюся простоту, приведенный пример достаточно важен - на месте операндов могли бы быть ссылки на сколь угодно сложные структуры данных, а на месте арифметических операций - любые функции обработки.

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

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

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

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

По аналогии с языком LISP /238, 239/ пусть значением любой вершины КМИ могут быть атомы (в том числе "пустой" атом nil) и списки. Список оп­ределяется как последовательность атомов и (или) списков (возможно, пус­тая), заключенная в скобки.

Преобразование вида значений выполняется с помощью операций "при­ведение к атому" и "приведение к списку".

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

(5) 5, ((2)) 2, () -> nil, (2 3) -> ошибка.

Операция "приведение к списку" заключается в построении списка, со­держащего параметр операции (список или атом), например:

5 (5), (2) -> ((2)), (2 3) -> ((2 3)), nil ( ).

Вычисление значений элементов ИСФ производится "снизу-вверх" по следующим правилам:

значением константы вида "(текст)" является атом ' [текст]"; значением слота вида "?" является приобретенное им в ходе конкрети­зации значение (значение, которым конкретизован этот слот);

для слота-ссылки значением является значение объекта ссылки; для слота-перехода значением является значение фрейма (ИЭ или ИнС), на который указывает этот переход;

для фрейма его значение сопоставляется с его атрибутом - можно счи­тать, что атрибут фрейма есть имя (идентификатор) переменной, а значение фрейма - значение этой переменной;

вид значения фрейма определяется видом самого фрейма - является ли он ИЭ или ИнС: в качестве значения фрейма - информационного элемента выступает значение его единственного слота (атом или список), а значением фрейма - информационной секции является список значений его слотов (даже если такой слот - один).

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

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

по ссылке выполняется вызов функции, и вычисленное значение запо­минается в качестве значения переменной-атрибута ИнС.

Для демонстрации некоторых возможностей практического использо­вания форм-элементов можно привести следующий пример. Пусть имеются функции, осуществляющие вывод строки (print), вывод пустой строки (newline) и формирование строки путем повтора некоторого символа, зада­ваемого в качестве аргумента (repeat).

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

(заголовок]

, ■ [текст заголовка]

• [строка I]

• [пропуск строки]

*- /ф [ncwlinc]\

• [пробелы]

I- /ф [repeat]\ ^L [50]

(номер таблицы]

|- /ф [print ]\

[табл. 2.5]

• [строка 2] h ‘‘Ф lpnnt]\

L [Таблица частоты заболеваний по району]

Подобная интерпретация весьма похожа на интерпретацию S- выражений языка LISP - достаточно сравнить S-выражение (PLUS 3 (TIMES 5 8)) и секцию со ссылкой на функции TIMES и PLUS:

[Сумма]

(-/ф [PLtJSiV

[Произведение]

TIMESJV

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

алгоритмического языка - в рамках ограничений, налагаемых требованием к функциям по формированию ими "чистого результата" /239, 240/. Как показа­но в /239/, для этого достаточно ввести функциональные аналоги императивов "ветвление", "цикл” и "опустошение".

Ветвление представляют собой возможность описания (и выполнения) процесса, предусматривающего блокировку интерпретации фрагментов КМИ в зависимости от какого-либо условия, выполнение которого проверяется при обработке ссылки на функцию [COND]. Контекст ссылки на такую форму должен иметь вид

имя секции

• /ф [COND]\ слот 2 слот 3 слот 4.

Порядок выполнения подобного вызова следующий: вычисление слота 2;

если значение слота 2 отлично от NIL, то вычислить слот 3 и получен­ное значение считать результатом вычисления секции и присвоить атрибуту «имя секции» - без вычисления значения четвертого слота;

в противном случае указанные выше действия выполняются над слотом 4 - без вычисления значения слота 3.

Следует отметить, что COND (а также описанные ниже функции WHILEDO и SKIP) является "псевдофункцией" - функцией, наличие и тем более реальный вызов которой не требуются, то есть обработку конструкции COND должен обеспечивать интерпретатор метаинформации.

Цикл представляет собой возможность описания совокупности дейст­вий. повторяемых до тех пор, пока выполняется некоторое условие. Цикл I- слот2

Интерпретация ссылки на функцию WHILEDO заключается в следую­щем:

вычисляется значение слота 2;

если полученное значение равно NIL, то оно принимается в качестве значения секции "имя секции";

если результат вычисления слота 2 отличен от NIL, то вычисляются слоты 3,4,5 п, после чего описанный выше процесс повторяется.

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

В приведенном выше описании собственно атрибуты фреймов играли роль идентификаторов переменных. Возможен и несколько иной вариант их использования, еще более близкий к языку LISP: не вводить ссылки на функ­ции, а рассматривать в качестве таковых атрибуты фреймов. Если атрибут не является именем функции, то значением фрейма становится список, "голову" которого составляет атом-атрибут, а "хвост" - список вычисленных значений слотов фрейма. В противном случае осуществляется вызов соответствующей функции, и результат этого вызова заменяет атрибут фрейма. Существенным отличием данного подхода от классического функционального программиро­вания является невозможность организации рекурсивных вычислений и ис­пользования л-выражений.

Общими существенными недостатками приведенного способа являют­ся:

появление дополнительных разного рода структурных ограничений на содержимое ИСФ (например, см. контскст вызова COND), которые не реали­зуются на уровне БМПМИ и базового языка ее представления;

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

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

Так, для примера, приведенного в начале» при наличии таблицы соот­ветствия вида

Имя вершины	Процедура
[Проверка файловой системы]	scandisk.exe
[дефрагментация диска]	defraq.exe
[архивация содержимого Kaia>ioionJ	Процедура, выполняющая архивации» содержимого каталогов, имена кото­рых есть значения потомков обраба­тываемой вершины

интерпретируемый КМИ мог бы выглядеть так:

[Сервисное обслуживание жесткого диска]

|—[Проверка файловой системы] j—[дефрагментация диска]

¹—[архивация содержимого каталогов]

I—[сЛтат]

I—(c:\work]

¹—ld:\mail].

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

Рис. 3.10. Пример формирования SQL-запроса на выборку данных по метаинформации

реляционной базы данных с таблицами, содержащими сведения о паци­ентах (Рас), врачебном персонале (Doctor) и о приеме пациентов (Pricm);

онтологии домена предметной области, представленной в виде КМИ, вершинам которого поставлены в соответствие процедуры Рг1 - Рг9;

некоторого шаблона КМИ выборки, содержащего ссылки на ИнС онто­логии, двум вершинам которого поставлены в соответствие процедуры РгЮ и Prll.

Процедуры Рг1 — Рг7 возвращают в качестве значений идентификаторы таблиц и полей базы данных, в которых хранятся значения тех атрибутов, ко­торым поставлены в соответствие эти процедуры;

процедуры Рг8 и Рг9 осуществляют формирование условий к данным, подлежащим включению в выборку;

процедуры РгЮ и Prll выполняют формирование компонентов SQL- запроса.

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

Рг1 и Рг7, результатом чего будут строки "Pac.Fam^H и "Priem.Date^H;

РгЮ, которая сформирует первую часть SQL-запроса;

Рг9. формирующей совокупность условий в терминах полей базы дан­ных;

Prl 1, которая сформирует всю вторую часть SQL-запроса.

В результате будет сформирован SQL-запрос, выполнение которого по­зволит получить требуемую выборку. Очевидно, что аналогичным образом могу г быть сформированы не только запросы типа SELECT, но и CREATE и др.

Приведенный пример во многом показателен и с точки зрения демонст­рации метауправления - в данном случае пользователь используя только он­тологию фактически управляет формированием SQL-запроса (возможно, даже и не зная об SQL). С другой стороны, изменение онтологии затронет только ассоциированные процедуры: алгоритм интерпретации останется неизмен­ным.

Таким образом, существует множество различных способов определе­ния задания вычислительной семантики метаинформации и их возможных модификаций, допустимых в рамках разработанной базовой модели пред­ставления метаинформации. Конкретный способ определяется (выбирается) при создании ИСМУ и зависит, прежде всего, от выбранной вычислительной схемы использования компонентов метаинформации (см. п. 2.2). Реализация выбранного способа, как правило, затруднений не вызывает - благодаря ши­рокой известности алгоритмов обработки древовидных структур.

4. Метод построения синтаксически управляемых средств формирования компонентов метаипформации на основе контекст- но-свободных описаний их структуры

1. Формирование компонентов метаинформации с использованием структурных шаблонов

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

В n. 3.2 описаны лингвистические средства представления мета инфор­мации. Поскольку любая допустимая цепочка терминальных символов (то есть предложение) языка представления МИ есть ИСФ, простейший вариант построения и организации функционирования средств формирования КМИ очевиден - это сочетание текстового редактора, не налагающего каких-либо ограничений на редактируемый текст, и средств синтаксического анализа тек­стов на предмет их принадлежности к языку представления метаинформации. В этом случае пользователь формирует метаинформацию произвольным об­разом (без какого-либо контроля его действий), а факт соответствия или несо­ответствия содержимого того или иного файла с метаинформацией принятым модели и языку представления устанавливается отдельным средством, вызы­ваемым по инициативе пользователя.

Такой подход аналогичен используемому в современных интегрирован­ных средах разработки современных систем программирования, в которых редактирование текста программы и его компиляция представляют собой раз­личные режимы функционирования интегрированной среды - см, например, /144/. Недостатки подобного подхода хорошо известны:

пользователь (лицо, осуществляющее формирование КМИ) должен знать правила записи метаинформации на используемом языке представле­ния;

результаты работы пользователя по определению (записи) содержимого КМИ потенциально могут содержать ошибки синтаксического характера, ко­торые MOtyr быть выявлены только при отдельном, явном вызове средств синтаксического анализа;

пользователь вынужден работать с КМИ в форме записи на языке пред­ставления, эргономичность которой крайне низка (см., например, скобочную нотацию БЯ или содержимое любого файла на XML) по сравнению с возмож­ностями

визуализации информации, обеспечиваемыми современными уст­ройствами отображения;

какой-либо сервис в интересах формирования КМИ (например, уста­новление значения ссылки и внедрение объектов ссылки и т. д.) л среде тек­стового редактора общего назначения реализовать невозможно.

В силу указанных недостатков процесс формирования КМИ при ис­пользовании данного подхода крайне специфичен и трудоемок, и по своей эффективности приближается к эффективности попыток предоставления пользователям разного рода языков программирования - как, например, в продуктах 1С:Бухгалтерия /176/ и им аналогичных.

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

Осуществление предлагаемого подхода базируется на двух основных составляющих - определении расширенного языка представления метаии- формаиии и понятии фиксированности КМИ, описанных ниже на примере представления КМИ с использованием базового языка (см. п. 3.2.1).

Любую правильную (допустимую) ИСФ можно рассматривать как це­почку символов БЯ, выведенных из начального символа грамматики (символа ^,|<понятие>"). Соответственно, каждая такая цепочка имссг, по крайней мере, одно дерево вывода.

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

На рис. 3.11 приведен пример последовательности смены сентенциаль­ных форм при выводе из начального символа грамматики фрагмента ИСФ, описывающей некоторое понятие. Только последняя из сентенциальных форм является фиксированной ИСФ (то есть предложением на БЯ), а все остальные

• нефиксированными.

Любую фиксированную ИСФ можно преобразовать в нефиксированную путем замены какого-либо ее элемента (фрагмента) нетерминальным симво­лом, из которого выводим этот элемент (фрагмент), с помощью выполнения операции редукции (свертки). К любому нетерминальному символу в нефик­сированной ИСФ может бьгть применена операция вывода; а в любой ИСФ, отличной от ИСФ с единственным нетерминальным символом "<понятие>^п, есть цепочка, к которой применима операция редукции. В процессе формиро­вания (создания, модификации) ИСФ может принимать как фиксированный, так и нефиксированный вид.

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

Разверткой будем называть непустую последовательность замен нетер­минального символа, содержащегося в ИСС, цепочками выводимых символов. Развертка примеиима к любому нефиксированному компоненту (фрагмент)', элементу). Если в цепочку, используемую для замены исходных нетерминаль­ных символов, входит терминальный символ БЯ [текст] или [значениессылки],

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

Рис. 3.11. Пример последовательности сентенциальных форм при выводе предложения на БЯ

Процесс свертки имеет обратный характер - с точки зрения пользовате­ля это означает возможность "отсечь" часть ИСФ (а более строго - ее лист или куст) с заменой цепочки нетерминальным символом <нонятие>, <элемент>, <значение> или <атрибут>.

Для того, чтобы иметь возможность представления (записи) создавае­мого КМИ в его нефиксированном состоянии, необходимо использовать та­кой язык, множество терминальных символов которого образуют терминаль­ные и нетерминальные символы базового языка. Следовательно, необходимо ввссти метаязык (в классическом понимании метаязыка в теории компиляции - /200, 234/). Такой язык, построенный для базового языка, будем называть расширенным базовым языком (РБЯ) - поскольку процесс его построения ос­новывается на расширении исходного языка и может быть выполнен с ис­пользованием следующего алгоритма.

Алгоритм построения грамматики расширенного языка представления МИ Вход: Обя⁼ (Ибя, Тбя, Рбя> Sbs) - грамматика базового языка (Ывя - множество нетерминальных символов, Тбя - множество терминальных символов, Рвя - множество правил продукции, $вя - начальный символ грамматики.

Выход: Срся “ Триь Ррвя» Spba) — грамматика расширенного базового

языка.

Процесс:

1. Положить Ырвк = Квя. Т_РБя = Т_БЯ и Ы_БЯ', где Ы_Бя' = { а | (а = <х>) л (х е ^Бя)}> РрБЯ ⁼ Рвя» $1'КЯ ⁼ 5бя-

2. Для каждого символа х е Кбя, добавить в Ррвя правило вида ( х -> а ), где а

• <х>.

3. (Vi)(P, € Рр_БЯ: U .\| х?.. .Xj.. .x_r,)(Bj)(x, е Ы_5Я) добавить в правила вида U х_|х_г...ху...х_п, где х/ = <Xj>.

В приведенном алгоритме для записи терминальных символов грамма­тики РБЯ, соответствующих нетерминальным символам грамматики БЯ,

ис­пользуется обрамление исходных нетерминальных символов символами *< и *>', хотя может быть использован и любой другой прием. Пример РБЯ, полу­ченного для БЯ с использованием приведенного выше алгоритма, приведен в приложении 1.

Любая сентенциальная форма БЯ является предложением в грамматике

РБЯ:

(VwXSba “>* w, w е {М_БЯ* и Тбя’}) (w € 1*бя(Орбя)) где Ьрбя - РБЯ, порождаемый грамматикой Gpe*<

Благодаря этому операция развертки как операция вывода в грамматике БЯ есть композиция операций редукции и вывода в грамматике РБЯ

Gia(xUy -> xuy, где (U и) € Р_Бя, U е К_Бя, х,у,и е {N_M* и Тбя* vj е}) = GpBfl(xu'y xlly, xUy хиу, где {(U u),(U и')} e Р_РБЯ, U e N_PM> U € Ибя» X^,u,u‘ € {Мея* и Т_Бя*и e}. и' = <U>)

н операция свертки как операция редукции в грамматике БЯ также яв­ляется композицией операций редукции и вывода в грамматике РБЯ

Gitf(xuy xUy, где (IJ и) ь Р_Бя, U е Ы_БЯ, х,у е {Ы_БЯ* и Т_БЯ*и е>, и е {1М_БЯ и Т_БяГ) — G_PBfl(xuy xUy, xlly 4 хи'у, где {(U u),(U и')} e Р_РБЯ, U € Ырбя, и € Ыбя, х,у, € {М₆я‘ и Т_БЯ‘и е}, и,и' € {Ывя и Т_Бя}⁺, и' = <U>).

Тогда процесс создания КМИ в рамках грамматики РБЯ может быть представлен как непустая последовательность предложений РБЯ, в которой первый элемент есть <8_Бя^>» в последний - предложение на БЯ. Если какое- либо предложение в этой последовательности не является предложением на БЯ, то оно есть содержимое нефиксированного КМИ; в противном случае имеет место содержимое фиксированного КМИ. В свою очередь, модифика­ция КМИ также есть последовательность предложения на РБЯ, в которой пер­вое и последнее предложения одновременно являются предложениями на БЯ, а остальные могут таковыми не являться.

Таким образом, применение расширенного языка позволяет перевести действия по формированию КМИ в плоскость действий по замене терминаль­ных цепочек, образуемых алфавитом РБЯ. Конечное множество правил заме­ны однозначно определяется по правилам продукции грамматики БЯ, а воз­можность и результаты их применения - по правилам продукции грамматики РБЯ.

Описанный выше подход позволяет:

организовать работу пользователя с древовидным (или иным, наиболее целесообразным в данном приложении) отображением структуры формируе­мого КМИ (рис. 3.12), обеспечивая сохранение и считывание КМИ в фиксиро­ванной и нефиксированной форме с использованием полной нотации языка представления (для БЯ - скобочной нотации);

достаточно легко реализовать разного рода сервисные операции по фор­мированию КМИ (например, установление значения ссылки, информирование

о допустимых альтернативах свертки/развертки и т. д.).

Рис. 3.12. Пример организации интерфейса средства формировании КМИ на БЯ

Однако применение описанного подхода в рамках БЯ имеет существен­ный недостаток, обусловленный тем, что синтаксис БЯ строго соответствует правилам композиции элементов ИСФ базовой модели представления мета­информации). Суть этого недостатка состоит в том, что при необходимости введения дополнительных ограничений на допустимую структуру КМИ како- го-либо типа и (или) их фрагментов (например, паспорт КМИ или секции, связанные с вызовом функций и передачей им лараметрои, контексты псев­дофункций и т. д. - см. п. 3.4) средств только БЯ недостач очно.

Дополнительная структуризация содержимого КМИ при использовании БЯ может быть осуществлена посредством использования специальных шаб­лонов.

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

как организующей структуры, фиксирующей часть структуры какого- либо КМИ с целью унификации этой части у всех однотипных КМИ;

как макроса (макроопределения), призванного упростить процесс фор­мирования нлменклаторов и спецификаторов путем сокращения временных затрат на описание различных фрагментов ИСФ с одинаковой структурой.

Например, пусть имеется следующий шаблон

[Адрсс]

• (Индекс]

I* <значеиие>

• [Город]

** <значснис>

• [Улица]

*- <значение>

• [Дом]

I* <значение>

• [Квартира]

I- <значеиие>

Тогда можно сформировать шаблон "Учетные данные", используя ссыл­ку на шаблон "Адрес":

[Учетные данные]

МИЛИ

• [Фамилия]

*"<значс1жс>

-[Имя]

*-<Значсиис>

• [Отчество]

(<значение>

ссылка на шаблон Адрес .

В приведенном примере шаблон фиксирует понятие "Учетные данные" как одно или несколько понятий из числа ("фамилия", "имя", "отчество", "ад­рес"), причем первые три понятия определяются как "<значение>", а понятие "адрес" определяется путем ссылки на шаблон, в котором имеется требуемое описание.

Пусть в рамках какого-либо КМИ необходимо описать понятие "Паци­ент", которое должно включать в себя учетные данные о пациенте. Пример подобного описания приведен на рис. 3.13. При описании понятия "Пациент" в качестве второго элемента ИС "[Пациент]" внедрен (скопирован) шаблон [Учетные данные], а к имевшейся в нем ссылке на шаблон [Адрес] применена операция внедрения (копирования объекта ссылки). Существенно, что нетер­минальные символы "<значение>", имеющиеся в полученной ИСФ, могут (и должны) разворачиваться (доопределяться) дальше.

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

/

Рис. 3.13. Пример построения КМИ с внедрением шаблонов

Применение шаблонов в интересах формирования КМИ является разви­тием понятия и способа применения контекстных шаблонов в системах авто­матизированного специфицирования, приведенных в /9/.

Использование шаблонов позволяет создать целостный инструментарий формирования КМИ, поддерживающий любой из способов задания вычисли­тельной семантики метаинформации, описанных в п. 3.4 (по крайней мере такой инструментарий реализован для предложенных БЯ и РБЯ).

Важнейшую роль в построении подобных инструментальных средств формирования КМИ играет понятие фокусного элемента (ФЭ), определяемого как лексема РБЯ, по отношению к которой будет выполняться операция, зада­ваемая пользователем. Операционный базис средств формирования КМИ в

этом случае может быть определен как множество операций, которые потен­циально применимы к ФЭ и объединяются в следующие группы:

навигации - перемещения фокуса, то есть изменение указаний о том, какой элемент считать фокусным; развертки фокусного элемента;

свертки фокусного элемента или ФЭ и ряда обрамляющих его элемен­тов;

установление (задание, изменение) значения ссылки; задание и изменение значения терминальных символов [текст].

Кроме того, в операционный базис могут входить операции конкрети­зации (информационных секций и неконкретизованных констант), которые для средств формирования КМИ носят факультативный характер - в отличие от средств перевода КМИ, где конкретизация обязательна (см. п. 3.3).

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

как обеспечить, чтобы та часть КМИ, которая сформирована по шабло­ну, имела неизменную структуру;

может ли шаблон содержать ссылки на объекты в других КМИ и как от­следить изменение объектов ссылки;

может ли часть шаблона быть объектом ссылки и т. д.

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

2. Синтаксически управляемый редактор КМИ как XML- приложений

Применение подхода, описанного в п. 3.5.1 и заключающегося в жест­кой регламентации возможных действий пользователя в процессе формиро­вания КМИ синтаксисом языка представления метаинформации, к формиро­ванию КМИ как XML-файлов позволяет создать синтаксически управляемый XML-редактор (далее - редактор), который:

позволяет пользователю манипулировать с содержимым формируемого КМИ в древовидной (а в принципе - любой приемлемой) форме его отобра­жения с использованием предметных синонимов тегов и атрибутов тегов в рамках любого XML-приложения (языка, сформированного в рамках XML- стандарта для какого-либо прикладного применения, в качестве которого мо­жет выступать и представление МИ, причем для разных типов КМИ могут использоваться разные XML-приложения) - рис. 3.14;

дает возможность формирования состоятельных XML-файлов без зна­ния пользователем содержимого соответствующего DTD;

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

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

Учитывая, что описываемый метод построения XML-редакторов не ограни­чивается только редакторами КМИ, а также тот интерес, который в настоящее время вызывает применение XML в самых различных областях и

Рис. 3.14. Внешний вид и цикл редактирования а XML-Редакторе

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

В основе создания редактора лежат те же основополагающие принципы, которые описаны в п. 3.S.1 — разделение внешнего и внутреннего представле­ния редактируемой информации» контекстное определение допустимых опе­раций для любого положения фокусного элемента, и синтаксическая пра­вильность редактируемого XML-файла в любой момент времени в рамках грамматики языка, расширенного по отношению к языку представления ре­дактируемой информации.

Суть алгоритма построения управляющей таблицы сводится к следую­щему:

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

А -> а - А порождает цепочку а;

А (+) а - А порождает одну или несколько цепочек а;

А а - А порождает одну или несколько цепочек а либо пустую це­почку (е).

2. Полученные правила минимизируются по определенному алгоритму, и результат минимизации фиксируется как первая часть УТ ШТ[тег] - поро­ждающая грамматика тега "тег".

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

4. По второй части УТ формируется ее третья часть (иТЗ[тег]), пред­ставляющая собой таблицу "перенос-свертка" для распознавателя с магазин­ной памятью, способного выполнять редукцию цепочек в рамках порождаю­щей грамматики данного тега.

5. Специальным образом вычисляется матрица "вставки"» характери­зующая возможность помещения символов порождающей грамматики между различными символами этой грамматики - четвертая часть УТ (ЦТ4[тег]).

Полученная таким образом УТ дополняется пятой частью» в которой пользователь, выполняющий ее формирование, имеет возможность указать предметные синонимы тегов и их атрибу тов, а также задать имена так назы­ваемых UDP (User Defined Procedure) - процедур, определяемых пользовате­лем. Эти процедуры представляют собой программные коды (конструктивно собранные, например, в Dinamic Link Library (DLL)), осуществляющие вы­полнение операций, специфичных для данного XML-приложения. UDP через специальный Application Program Interface (API) доступен весь редактируе­мый XML-файл. Для КМИ в XML-нотации, приведенной в приложении 3, та­кими процедурами, задаваемыми для отдельных тегов и их атрибутов, могут быть:

назначение глобальных и локальных идентификаторов;

установка значения ссылки и внедрение объекта ссылки с коррекцией идентификаторов;

конкретизация информационных секций и неконкретизованных кон­стант.

Более того, действия по принудительной конкретизации всего КМИ и его предметной интерпретации также могут быть реализованы через UDP, что позволяет применять редактор как единое средство формирования, перевода и интерпретации КМИ.

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

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

Однако зачастую операции свертки, замены и удаления не применимы только к ФЭ. Если фокусный элемент (обозначим его X) в хотя бы одном пра­виле продукции порождающей грамматики старшего по отношению к нему тега имеет контекст (то есть существует правило вида U (хХ{?), то операция редукции или замены (которая есть редукция и следующий за ней вывод по другому правилу, содержащему в левой части U) должна применяться ко всей цепочке аХр. В свою очередь, весь редактируемый XML-файл есть цепочка, состоящая из терминальных и нетерминальных символов порождающих грам­матик тегов (причем границы применения каждой грамматике имеют много­уровневое вложение - рис. 3.15), и выделение в ней подцепочки <хХ(5 является весьма нетривиальной задачей. Так, например, при наличии правил U «ЛХр и Л у в цепочке бауХре (причем 5, а, у, (3, е - не единичные сим­волы, а цепочки нетерминальных и терминальных символов, в том числе воз­можно пустые) если ФЭ есть X, то выделить необходимо ауХр, а если у, то только у.

Кроме того, ряд операций редактирования являются контекстно- зависимыми. Например, если сентенциальная форма имеет вил аууР и имеется правило U(*) у, то можно удалить как любую из цепочек у, так и обе эти це­почки, а если это правило имеет вид U(+) -> у, то только одну из них. Также при наличии любого из приведенных выше правил цепочку у можно повторить произвольное количество раз, добавляя новые цепочки между а и у, у и у или у и р. Следовательно, помимо собственно поиска минимальной цепочки, до­пускающей свертку, необходимо иметь возможность нахождения ее контекста

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

Фрагмент DTD: Порождающие грамматики:

Ut[A|	uipj
А ^ е	D-»e
А (*)-» В • С	D (+)•» II
ицв|	U1(EJ
В -> D F. ml) •	E «PCDATA
niO ■> F | О | е	UlfFJ
UIIC1	F -> «PCDATA
с-» мои	U1IGJ
мо -> F | е	G->« UIIHJ H -> с

Фрагмент редактируемого XMI.-файлa:

<! element А (В|С)*>

<! element В (D,E,(F|G)?)>

<! element С (F?,H)>

<! element D (H)*>

«element E (PCDATA)^

<! element F (PCDATA)>

«element G (EMPTY)>

«element H (EMPTY)>

(A]

—HBJ

Область действие U 1(B) Область действия UI [В | Область действия U1(C|

Область дактюкя U1|A)

-ID1 j

• f-flHJf-

-4-j ie] i —4nt0]|«

[C)j

H—

¹—i—HH] r

Рис. 3.15. Пример иерархии границ порождающих грамматик в сентенциальной форме

Задача поиска минимальной цепочки, содержащей X, с учетом правил грамматики в теории компиляции является задачей поиска основы (самой ле­вой простой фразы) /14, 15, 241, 242/ - она решается, в частости, в анализа­торах, осуществляющих левосторонний восходящий разбор по алгоритму "пе­ренос-свертка" для предложений на языке, грамматика которого является грамматикой предшествования. Однако в таких анализаторах порядок выделе­ния основ всегда фиксирован - в приведенных выше терминах можно считать, что на каждом такте работы распознавателя фокус (роль которого в подобных однопроходовых анализаторах играет читающая головка на входной ленте) либо остается на месте (такт свертки), либо сдвигается на один символ вправо (такт переноса). Задача же выделения простых фраз по отношению к любому символу анализируемой цепочки при произвольных перемещениях фокуса не ставилась и, естественно, не решалась - в транслирующих системах, осущест­вляющих автоматический перевод, она не возникает.

С учетом вышеизложенного можно уточнить понятие группы фокусного элемента (ГФЭ) - это простая фраза, содержащая фокусный элемент, а также определить левый и правый контекст ГФЭ как простые фразы непосредствен­но слева и справа от ГФЭ в текущей сентенциальной форме.

Тег, в рамках порождающей грамматики которого необходимо опреде­лять ГФЭ и ее контексты, находится достаточно легко: подъем вверх, и пер­вый найденный тег и будет искомым, указывающим на подлежащий исполь­зованию фрагмент управляющей таблицы, все части которой разбиты на фрагменты, индексированные по имени тега. Поскольку имена тегов в DTD имеют глобальные описания, коллизий имен тегов при этом не возникает.

Ввиду того, что любая основа является простой фразой, но не наоборот, для выделения простых фраз при произвольных перемещениях фокуса отно­шения предшествования Вирта-Вебера /14, 15, 242/, используемые для выде­ления основ,

неприменимы, их необходимо переопределить и ввести еще одно отношение - отношение "другая основа".

Предложенный вариант определения отношений предшествования, по­лученный в результате анализа особенностей определения границ и выделения простых фраз в контекстно-свободных языках, выглядит следующим образом: отношение "одноосновноеть" (или "есть основа, в которой X непосред­ственно предшествует Y⁴): X = Y > А -> aXY(3 - имеется правило, в пра­вой части которого за X непосредственно следует Y (а, 0 - произвольные, возможно пустые, цепочки);

отношение "начало основы" (или “появление Y после X означает, что Y начинает новую основу"): X < Y А аХВр, В Yy - Y начинает це­почку, выводимую из В, который следует за X в каком-либо правиле;

отношение "конец основы" (или "появление Y после X означает, что X является последним символом некоторой основы"): X > Y А -> aBY|3, В ■>⁺ уХ - X заканчивает цепочку, выводимую из В, который следует перед X в каком-либо правиле;

отношение "друод основа" (или "появление Y после X означает, что X заканчивает одну основу, а Y начинает другую основу¹'): X # Y А -> aBR(3, В уХ> R ■♦* Y5 - X заканчивает цепочку, выводимую из В, который в каком-либо правиле следует перед R, in которого выводится цепочка, начи­нающаяся с Y.

Для вычисления этих отношений необходимо наличие булевых матриц отношений HIRST и LAST, а также их транзитивных замыканий FIRST и LAST*! Д^анные отношения определены в теории компиляции, и алгоритмы построения их булевых матриц известны (см., например, /14,214/):

FIRST(A,b) = 1, если есть правило вида А -> ba, то есть b есть крайний левый символ цепочки, непосредственно выводимой из А;

LAST(A,b) = 1, если есть правило вида А ab, то есть b есть крайний правый символ цепочки, непосредственно выводимой из А.

Булевы матрицы [FIRST*] и [LAST*] есть результат транзитивною замы­кания матриц FIRST и LAST соответственно, для нахождения которых можно применить алгоритм Воршалла, описание которого и примеры применения (в том числе для нахождения именно [FIRST*] и [LAST*]) приведены, в частно­сти, в/14/.

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

матрица [“] строится путем просмотра правых частей всех правил - если в правой части есть символ а, непосредственно за которым следует символ Ь, то (^в](а,Ь):=1;

матрица [<] := [=] • [FIRST*] — произведение матрицы [=] на матрицу [FIRST⁴];

матрица [>] := [LAST]'¹ * [-], где [LAST*]*¹ - транспонированная матри­ца (LAST*);

матрица [#) yr [LAST*]'¹ * [=] * [FIRST*].

Наличие отношений следования, вычисленных на множестве символов порождающих грамматик тегов и представленных в виде обобщенной матри­цы отношений предшествования во второй части УТ, позволяет выполнять на­хождение ГФЭ. и его контекстов по алгоритму, краткое описание которого приведено ниже (полное описание дашюго алгоритма приведено в приложе­нии 4).

Алгоритм нахождения ГФЭ и ее контекстов Вход: X - фокусный элемент, S = aia₂.. а„ХЬ)Ьг.. b_m (п £ 0, m > 0) - текущая сентенциальная форма редактируемого XML-файла, ограниченная областью действия грамматики тега, старшего для X.

Выход: А - группа фокусного элемента; LA - левый контекст ГФЭ; RA - пра­вый контекст ГФЭ; SA, NLA, NRA - нетерминальные символы, для которых соответственно A, LA и RA являются простыми фразами.

Процесс:

1. Найти для X старший тег NA и далее использовать соответствующий ему фрагмент УТ - U[NA].

2. Положить А = X.

3. Двигаясь в S влево от X, добавлять слева к А каждый символ из последова­тельности а„, an.i,...ai, пока не будет добавлен такой символ aj, что aj U аи (для X - а„), либо не будет добавлен aj.

4. Двигаясь в S вправо от X, добавлять справа к А каждый символ из последо­вательности bi, Ьг, b_m, пока не будет добавлен такой символ bj, что bj # Ь,_н (для X - bi), либо не будет добавлен b_m-

5. Используя МПА, реализующий алгоритм "перенос-свертка" в рамках поро­ждающей грамматики тега NA, выполнить свертку А к нетерминальному сим­вол)'. Полученный результат свертки запомнить в SA.

5. Повторить действия 2*4, выбрав в качестве ФЭ сначала а^ а затем bj. В пер­вом случае будут найдены LA и NLA, а во втором - RA и NRA. Если а1 или bm входит в ГФЭ, то соответствующие контекст и нетерминальный символ есть пустая цепочка.

Функционирование МПА, осуществляющего свертку, выполняется пол управлением обобщенной матрицы отношений следования, в которую сведены отношения '*=’ и Детальное описание приведенного выше алгоритма существенно сложнее (в частности, при выделении ГФЭ и контекстов надо учитывал, уровни вложенности отношений '<* и ’>'), и в полном объеме пред­ставлено в приложении 4.

Таким образом, введенные отношения '<*, '=' и играют двоякую роль - они используются как для выделения простых фраз для ФЭ и его кон­текста,

так и при свертке этих простых фраз. В случае, если при вычислении этих отношений для порождающей грамматики какого-либо тега обнаружива­ется, что между двумя или более символами алфавита существует более одно­го из указанных выше отношений, то такая порождающая грамматика не явля­ется грамматикой предшествования, и приведенный алгоритм для нее будет неприемлем. В этом случае необходимо изменить соответствующее описание тега в DTD. На основании теорем, доказанных в /14/, можно утверждать, что описание любого тега в DTD может быть преобразовано в эквивалентное опи­сание, которому соответствует грамматика предшествования. Однако задача синтеза алгоритма подобного преобразования не решалась - на практике ока­залось достаточно формировать DTD-описания XML-приложений так, чтобы выполнялось следующее правило' Для описания вида <!element А В>, где В - модель содержимого для А, матрица отношений следования всегда может быть построена, если ни одно имя элемента не повторяется в В, либо все по­вторы имени одного и того же элемента относятся к разным альтернативам содержимого - например, <!element А ((С, D) | С)>. Это правило является бо* лее жестким ограничением, чем необходимо для получения грамматик пред­шествования, однако опыт показат, что его выполнение затруднений не вызы­вает (хотя, возможно, иногда и приводит к увеличению количества тегов).

Для нахождения матрицы вставки (матрицы ''МЕЖДУ") можно исполь­зовать следующее определение отношения "перед" (или "X может находиться непосредственно перед Y"): X перед Y А aBCd, В {LAST*] X, В [=] С, С [FIRST*] Y - может существовать сентенциальная форма, в которой X непо­средственно предшествует Y. Тогда матрица [перед]:= [LAST*]*¹ * [=] * [FIRST*], то есть если "X перед Y", "Y перед Z", и "Y е", то МЕЖДУ(Х,г):-У. Следует заметить, что задача определения возможности вставки символов в сентенциальную форму в теории компиляции также не возникает.

При использовании описанного выше подхода для контекстного опреде­ления допустимых операций редактирования в редакторе при каждом переме­щении фокуса выполняются (рис. 3.16):

выделение ГФЭ и ее правого и левого контекста и свертка их к нетерми­нальным символам;

определение перечня операций, допустимых по отношению к данному ФЭ с учетом его группы и контекста;

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

Благодаря этому пользователь и получает возможность осуществлять только те операции, которые не нарушают синтаксис редактируемого файла, не зная при этом правил, определяющих данный синтаксис (пример такого оп­ределения приведен на рис. 3.17). Если редактируемый файл состоятелен (в терминологии п. 3.5.1 - фиксирован), то он соответствует синтаксису, задан­ному в DTD; в противном случае он соответствует синтаксису, заданному в DTD и расширенному порождающими грамматиками тегов.

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

приложений (а точнее - их DTD-описаний). В этом случае выстраивается сле­дующая цепочка (которая может быть продолжена): DTD-описание XML- приложения, которое позволяет создавать DTD-описания для XML- приложений. Данная возможность и соответствующий пример настройки ре­дактора также описаны в приложении 4.

Рис. 3.16. Основные элементы механизма контекстного определения допустимых операций редактирования

Рис. 3.17. Пример контекстного определения допустимых операций

Выводы по третьей главе

1. В качестве базовой модели представления метаинформации целесооб­разно использовать иерархические сети фреймов, дополненные средствами, обеспечивающими межсетевые связи (внешние ссылки) и вариантность струк­туры метаописаний (правила конкретизации фреймов - "И", "ИЛИ"» "множест­венное ИЛИ", "необязательно" и "повтор").

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

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

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

181

вершин дерева метаинформации, а также использование механизма ассоции­рованных процедур.

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

6. Разработанные модели и методы представления, формирования и об­работки метаинформации не только составляют методологический базис по­строения информационных систем с метауправлением, но и имеют самостоя­тельное практическое значение для различных приложений иерархических се­тей фреймов, вывода (синтеза) на иерархических структурах, а также приме­нения XML-тсхнологии.