Главная > Документ


ММ = <семейство множеств данных (СМД);

семейство операций над данными (СОД);

семейство формальных языков (СФЯ)>

или с использованием сокращений: ММ = <СМД; СОД; СФЯ>, где СМД - набор типов данных, определяющий предметную область ММ (значения операндов и результатов операций) и представляющий память ММ; СОД - набор операций, определяющий проблемную область ММ и представляющий процессор ММ; СФЯ - набор ФЯ для записи входных данных (ВХД), программ и данных ММ (ЯММ) и выходных данных (ВЫД).

ММ являются логический процессор (МЛВ) для реализации логического вывода, языковый процессор (ЯП) для трансляции текстов ФЯ и др. применения. Общее определение ММ позволяет классифицировать их по различным признакам. Чаще всего нас не интересуют наборы СМД и СОД. Поэтому транслятор, написанный на языке Я1, языка Я2 на язык Я3 будем обозначать так: Тр = <; ; Я1, Я2, Я3>. Например, ППП на языке Ада примет вид: ППП = <Ада-данные; Ада-операции; язык Ада>.

ММ трансляции. Рассмотрим несколько примеров формирования ММ для системного программирования. Пусть ТЯi - текст языка Яi, тогда применение транслятора (Тр) можно записать так (две первые позиции формального определения ММ будем опускать, соответствующие нуль-семейства будем обозначать - Н):

<Н; Н; Я1, Я2, Я3>(ТЯ2) = ТЯ3 или <Я1, Я2, Я3>(ТЯ2) = ТЯ3.

Для построения новых ММ определим для троек-трансляторов операцию Г - применение одного транслятора к программе, вообще говоря, другого транслятора. Операция Г задается соотношением:

<Я1, Я2, Я3>(<Я2, Я4, Я5>) = <Я3, Я4, Я5>,

или

<Я1, Я2, Я3> Г <Я2, Я4, Я5> = <Я3, Я4, Я5>.

Операция Г - не коммутативна, не ассоциативна, имеет левый обратный элемент и левый нейтральный элемент (неравенство обозначается знаками =/=):

<Я1, Я3, Я2> Г <Я3, Я4, Я5>=/= <Я3, Я4, Я5> Г <Я1, Я3, Я2>,

(<Я1, Я2, Я3> Г <Я2, Я4, Я5>) Г <Я3, Я6, Я7> =/=

<Я1, Я2, Я3> Г (<Я2, Я4, Я5> Г <Я3, Я6, Я7>).

<Я2, Я4, Я5> = <Я1, Я3, Я2> Г <Я3, Я4, Я5>,

<Я1, Я1, Я1> Г <Я1, Я2, Я3> = <Я1, Я2, Я3>.

Левый нейтральный элемент используется для записи программ оптимизации. Нейтральный элемент можно получить в результате применения ММ:

<Я3, Я2, Я1> Г <Я2, Я1, Я1> = <Я1, Я1, Я1>.

6.1.4. Примеры проектирования ММ. Теперь рассмотрим два реальных примера проектирования трансляторов на ВМ БЭСМ-6 [Красилов67]. На БЭСМ-6 имеются трансляторы языка Фортран [Красилов72] в коды БЭСМ-6: <БЭСМ6, Фортран, БЭСМ6>. Требуется построить аналогичный транслятор для встроенной ВМ (ВВМ) языка Фортран в коды ВВМ на основе транслятора: <Фортран, Фортран, ВВМ> и осуществить перенос системы на ВВМ. Решение этой задачи системного программирования определяется равенствами:

<БЭСМ6, Фортран, БЭСМ6> Г <Фортран, Фортран, ВВМ>

= <БЭСМ6, Фортран, ВВМ>,

<БЭСМ6, Фортран, ВВМ>Г<Фортран, Фортран, ВВМ>

= <ВВМ, Фортран, ВВМ>.

Рабочие (функциональные) программы ВВМ вида <Фортран, ИД, РЕЗ> перерабатывают исходные данные ИД в результаты РЕЗ и будут создаваться системой программирования, работающей по равенствам:

<ВВМ, Фортран, ВВМ> Г <Фортран, ИД, РЕЗ> = <ВВМ, ИД, РЕЗ>.

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

<БЭСМ6, Фортран, БЭСМ6> Г <Фортран, Фортран, АК>

= <БЭСМ6, Фортран, АК>,

<БЭСМ6, Фортран, АК>Г <Фортран, Фортран, АК>

= <АК, Фортран, АК>.

Второй этап связан с переносом и адаптации системы, с учетом условия, что имеется ассемблер <ВВМ, АК, ВВМ>, выражается равенством:

<ВВМ, АК, ВВМ> Г <АК, Фортран, АК> = <ВВМ, Фортран, АК>.

Рабочие (функциональные) программы получаются в результате трансляции в соответствии с равенствами:

<ВВМ, Фортран, АК> Г <Фортран, ИД, РЕЗ> = <АК, ИД, РЕЗ>,

<ВВМ, АК, ВВМ>Г <АК, ИД, РЕЗ> = <ВВМ, ИД, РЕЗ>.

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

Другие применения ММ можно рассмотреть схематически:

<СМД; СОД; Н> - ППП или логический процессор;

<СМД; Н; СФЯ> - база данных или знаний, которые обслуживаются системами управления;

<СМД; Н; Н>- представление предметной области ММ;

<Н; СОД; Н>- абстрактная программа на основе алгебры программ;

<Н; Н; СФЯ> - трансляторы входного языка на некоторый выходной язык.

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

6.1.5. Операции конструирование ММ. По примеру теории алгоритмов можно рассмотреть операции построения ММ. Ниже указаны смысл таких операций.

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

1. Распространение ММ состоит в построении такой ММ, которая выражается тройкой: <Н; Н; Я1, Я22, Я3> из тройки <Н;Н ; Я1, Я21, Я3> при условии, что Я21 <= Я22 (Я21 включено в Я22).

2. Композиция ММ совпадает с операцией Г, которая подробно уже рассмотрена выше.

3. Объединение ММ состоит в построении текста:

(<СМД1; СОД1; СФЯ1>, <СМД2; СОД2; СФЯ2>),

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

4. Разветвление ММ строится на основе распознающего свойства машины ММ1 текста Т и альтернативного выбора одной из ММ2 и ММ3 по следующей формуле:

<СМД2; СОД2; СФЯ2>

при <СМД1; СОД1; СФЯ1>(Т) <> Ø,

<СМД1; СОД1; СФЯ1> = <СМД3; СОД3; СФЯ3>

при <СМД1; СОД1; СФЯ1>(Т) = Ø.

5. ММ повторения строится по аналогии с оператором условного цикла языков программирования с использованием распознающей свойства машины ММ текста Т. Внешне ММ повторения записывается аналогично ММ разветвления.

6. Универсальная ММ предназначена для переработки записи ММ и исходного текста в результат работы этой машины над исходным текстом:

<СМД; СОД; СФЯ>(<СМД1; СОД1; СФЯ1>, Т) = <СМД1; СОД1; СФЯ1>(Т).

Далее можно рассмотреть построение ММ декомпозиции, которая осуществляет расчленение текстов на составные части, или ММ параллельных вычислений, которая является самой сложной по конструкции. Сложность параллельной ММ связана с синхронизацией и обменами данными между частями ММ. Операция сочетания может быть связана с манипулированием тремя компонентами СМД, СОД и СФЯ. Манипулирование связывается с применением теоретико-множественных операций над такими компонентами.

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

6.2. Математическая машина диалога

В основе безбумажной технологии [Глушков82] решения самых разнообразных задач на ВМ используются многие средства: телевизионные дисплеи, алфавитно-цифровая клавиатура, микрофонно-телефонные устройства, сенсорные датчики и устройства. Общение человека с ВМ на основе подобных устройств осуществляется с помощью ЕЯ или ФЯ различного типа. Особенностью языков общения является тот факт, что по своей структуре языки напоминают диалог. Диалоговые языки подразделяются на два основных класса: языки репликового диалога и языки меню, который в другой форме реализует диалог. Языки репликового диалога состоят из текстов человека и сообщений ВМ, тесно взаимосвязанных между собой. Тексты человека набираются с помощью клавиш, кнопок, световым пером или передаются голосом. Они вводятся в память ВМ, обрабатываются некоторой ММ, инициируют работу подпрограмм, а результаты их работы передаются человеку через различные устройства индикации. Человек воспринимает результаты (сообщения) ВМ и передает для ВМ новые тексты. Этот (циклический) процесс происходит до получения окончательного результата решения задачи. Смысл задачи и смысл результата ее решения в данном рассмотрении остаются за пределами обсуждения проблем диалога. Диалог по своей сути связан с использованием относительно нового стиля программирования или информатической деятельности, отличного от стиля создания программ. Здесь главным моментом является недетерминированность процессов. Программирование таких процессов имеет отличия от программирования задач.

Диалог с помощью меню строится по принципу «выбери и укажи работу, и ВМ ее выполнит». Совокупность работ также определяет недетерминированную программу. Языки меню рассматривались в гл.3 на примере общения Интеллсист с пользователем. Отличия двух языков диалогового общения очевидны. Они проявятся точнее при рассмотрении в этом разделе языка реплик. Каким языком следует пользоваться определяет сам пользователь, область применения ВМ и совокупность решаемых задач. Главное отличие двух форм общения состоит в том, что язык меню не требует знания некоторого ФЯ. Язык меню требует знания работ или подработ, которые обозначены пиктограммами. При этом хороший язык меню сопровождается справочной системой, которая обеспечит оперативное познание свойств кнопок, пиктограмм, работ и подработ.

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

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



ММ диалога (ММД) имеет архитектуру, которая соответствует ее системе команд. Формат команд имеет следующий вид:

[метка :] имя операции, операнд1, операнд2 / имя семантической подпрограммы;

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

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

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

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

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

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

6.3. Математическая машина экрана (заметка)

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

Команды ММЭ связаны с характеристиками различных геометрических фигур (прямоугольник, овал, ромб и др.), координатами курсора или элемента фигур, обрамлением и цветом фигур, рисунком пиктограмм, указанием перемещений изображаемых элементов экрана и режимами обмена сообщениями, связанными с временными интервалами. Разнообразие информации поставляет определенную сложность системы команд ММЭ, она не приводится здесь в своем первоначальном виде. Достаточно рассмотреть операции TURBO VISION [Керниган85, Фаронов92], чтобы убедиться в технической сложности системы команд ММЭ.

Работа ММЭ тесно связана с работой ММД. На первых дисплеях обе машины проектировались и реализовывались автономно. Для ПЭВМ имеются языки Паскаль и Дельфи, которые оснащены средствами эффективного моделирования ММД и ММЭ как автономно, так и в комплексе. Относительно ММЭ ограничимся только высказанными замечаниями.

6.4. Машина грамматического разбора для лексического анализа

Практика построения транслирующих систем подсказывает рациональную организацию просмотра и преобразования входных текстов. Весь процесс трансляции разбивается на фазы: лексический анализ, синтаксический анализ, семантические преобразования и генерация выходного кода. Исторически транслирующие системы ориентировались на самые разнообразные организационные структуры [Дейкало84, Ингерман69, Касьянов86, Красилов56а, 706, 73г]. Наиболее эффективной считается указанная выше структура. Для реализации каждой из фаз применяется МГР. Они могут быть различными, поскольку грамматики, используемые на каждой фазе, разнятся сложностью или объемом.

Например, транслирующая система в Интеллсист перерабатывает тексты на ЯПП в формальное представление знаний, выполняя фазы лексического анализа, синтаксического анализа, семантического преобразования, логического и алгебраического выводов и генерации выходного кода СП. Логический вывод является методом программирования интеллекта. Итак, Интеллсист реализована по классическим схеме и структуре. Здесь рассмотрим пути реализации фазы лексического анализа.

Для программирования лексического анализа достаточно использовать систему команд МГР2. Система команд включает команды: сравнения с символом, перехода на подпрограмму, выхода из подпрограммы (подграфа), безусловного перехода по метке, индикации ошибки, сравнения с кодом (аналог команды сравнения символов), проверки принадлежности символа диапазону символов, классификации символа на букву и цифру, вызова подпрограмм семантического преобразования лексем и останова. Первоначальный вариант транслятора ЯПП реализовывался для лексического анализа с помощью МГР1 с кодовым (цифровым) представлением команд (ПГР состоит из 100 команд) . Система команд использованной МГР1 несколько отличается от описанной в гл.5. Отличия не вносят в толкование МГР ничего нового. Кажущиеся новые команда просто интерпретируются командами МГР2 и расширения (в графическом метаязыке). ПГР оказалась неудобной для изменений и сопровождения.

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

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

6.5. Машина грамматического разбора для синтаксического и семантического анализа

Синтаксический анализ сжатого после лексического анализа текста связан прежде всего с проверкой грамматической правильности текста, выполнением алгоритмов семантики и формированием лексикона и БЗ. Для программирования синтаксического анализа необходимо использовать систему команд МГР2 (ПГР состоит из 420 команд). Система команд включает команды: классификации символа константы, классификации символа переменной, условного и безусловного перехода по метке, сравнение с кодом (аналог команды сравнения символов), вызова подпрограмм семантического преобразования каждой языковой конструкции (их около 200 подпрограмм), перехода на подпрограмму, выхода из подпрограммы, перехода по номеру сорта константы, индикации ошибки и останова. Здесь также имеются отличия реализованной МГР2 и ее стандартом, представленным в гл.5. Отличия ничего нового не вносят в толкование МГР. Все «нововведения» связаны с заменой часто повторяющихся комбинаций команд одной командой.

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

Результатом синтаксического анализа являются терминологический словарь (лексикон), дополнительные словари и элементы БЗ. Здесь реализуется главная часть процесса формализации знаний и контроль за правильностью использования грамматики ЯПП (контекстные условия использования лексем). Значительная сложность этой части транслятора заключена в идентификации терминов, их описаний и использовании. Термины состоят из последовательностей слов, чисел, знаков и строк. Причем некоторые термины могут быть частью других терминов. Например, термин «АА ББ +» является частью термина «АА ББ + ВВ» (сам пользователь может составить или представить пример, близкий к реальным условиям использования ЯПП). Необходимо быть точным в подборе терминов, иначе будут возникать подчас неуловимые ошибки. Элементом БЗ является веточка двоичного дерева, с помощью которого представляются все утверждения. В Интеллсист разнообразие веточек оценивается числом более 150. Если учесть разнообразие каждой веточки, то можно представить сложность формирования элементов БЗ.

Семантический анализ кроме идентификации терминов и построения элементов БЗ реализует функции вычисления типа результата каждой операции, интерпретацию операций, операнды которых известны и оптимизацию списка веточек в БЗ. Функция вычисления типа результата усложняется числом типов величин (их 37) и числом операций (их более 110). В связи с этими данными наибольшая таблица соответствия типов операндов двухместной операции и типа результата имеет размер 37*37 = 1369, а число таких таблиц равно около 30. Подпрограммы интерпретации операций по числу совпадает с числом операций (их более 80). Каждая подпрограмма реализует распознавание возможности интерпретации и выполняет (смешанные по [Ершов77]) вычисления результата применения операции. Оптимизация веточек включает операцию сравнения веточек. Если веточки совпадают, то она не помещается в БЗ, что экономит память Интеллсист и сокращает время логического вывода и решает задачу независимости знаний. Совокупность приведенных количественных данных говорит о технической сложности реализации анализа текстов.

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

6.6. Машины логического и алгебраического выводов

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

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

1. читать символ из преобразованного исходного текста,

2. строить веточки деревьев,

3. строить наборы совместных фактов,

4. строить наборы альтернативных фактов,

5. исключать избыточные веточки,

6. формировать деревья,

7. составлять некоторые словари,

8. определять тип операнда,

9. вычислять тип результата,

10. сравнивать веточки,

11. упорядочивать веточки в наборе совместных фактов,



Скачать документ

Похожие документы:

  1. Информатика в семи томах том 3 концептуальная информатика

    Документ
    Информатика как наука имеет свой лексикон, который еще не устоялся и находится в развитии. В томе продолжается раскрытие понятие смысла текстов, используемых в информатике, через изучение смысла понятия.
  2. Информатика в семи томах том 6 методы информатики

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

    Документ
    Излагается неформальное описание представления знаний различных видов на языке профессиональной прозы. Описание дано в полном соответствии с формальным изложением языка в томе 2.
  4. А а красилов информатика в семи томах том 1 основы информатики

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

    Книга
    Книга дает начальные сведения о новом определении информатики. Они необходимы для получения представлений о возможностях СВТ и человека, использующего или желающего использовать свой компьютер для принятия интеллектуальных решений
  6. Том 7 интеллектуальные системы (системы решения проблем) москва 1997 -2003

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

Другие похожие документы..