А. А. Красилов информатика в семи томах том Информатика смысла Машинная лингвистика


Глава 6. Использование МГР и математические машины



страница19/23
Дата01.08.2016
Размер4.61 Mb.
1   ...   15   16   17   18   19   20   21   22   23
Глава 6. Использование МГР и математические машины
Проблема физической реализации ВМ любого типа усложнена технологией создания элементной базы, переходом на новые физические основы реализации электронных схем, компоновкой набора элементов в электронные схемы, построением архитектуры ВМ, обеспечение внутренних и внешних параметров производства и эксплуатации ВМ с другими средствами СВТ. Создание предварительных функционирующих моделей и отработка на них как архитектуры, так и начального программного обеспечения является очевидным и дешевым делом. В связи с большим опытом работы в этой области появилось понятие ММ, которому и посвящена глава.
ММ важны и сами по себе, поскольку ММ может выступать не только как средство моделирования, но и как окончательный программный продукт. Обсуждение понятия ММ и его применения является важным разделом информатики. С понятием ММ программисты сталкивались еще при появлении первых ВМ. Оно развивалось и находило новые области применения. Описать все области применения понятия ММ не представляется возможным. В главе использованы показательные примеры применения ММ в некоторых областях. По ним можно составить достаточно полное представление о возможностях ММ.

6.1. Концепция математических машин
6.1.1. Введение. За последние 40 лет выработано классическое представление о всех типах и видах ВМ, построенных по крайней мере на базе электроники. Их конструкция имеет стандартный вид (схема фон Неймана): память - процессор - устройства обмена. Память хранит данные и программы для преобразования этих данных, а процессор выполняет пакет операций, вызываемых для выполнения из программы, устройства обмена вводят или выводят данные и программы. В самом общем виде процессор выполняет три сорта операций: вычислительные операции преобразования данных, операции управления последовательностью команд и операции обмена по каналам связи. Производство ВМ в форме физической реализации является сложным делом, несмотря на широкое использование больших интегральных схем. Едва ли целесообразно иногда осуществлять физическую реализацию некоторой ВМ. Практика создания ВМ привела к тому, что осуществлена унификация процессоров, памяти и устройств обмена. Стандартная архитектура не всегда удовлетворяет запросам пользователей. Это относится к обработкам данных, которые формализуются нестандартным образом. В таких случаях имеется испытанный путь для реализации ВМ в форме математической модели. Это обеспечивает многие преимущества перед физической реализацией ВМ. Математическую модель ВМ именуются математическими машинами. ММ реализуется программно на инструментальной ВМ. К примеру, определенным сортом ММ является совокупность ВМ и ОС, расширяющая систему команд ВМ.
Впервые практическое осмысление ММ было достигнуто в разработках ОС - увеличение логических возможностей ВМ, Интеллсист - интерпретатор математических операций логического вывода решения логического уравнения, МГР [Красилов78а] и Р-машины [Вельбицкий80] - интерпретатор операций выполнения программ, работа которых управляется текстом, Утопист [Тыугу84] - машина решения задач по известному шаблону, ММ являются интерпретаторы ФЯ. Любая ОС является ММ расширения системы команд ВМ. Концепция ММ появилась в 30-х годах, когда были изобретены и изучены машины Тьюринга и Поста [Нильсон85], а также нормальные алгоритмы Маркова [Марков84]. Эти понятия необходимы были для установления ряда фундаментальных утверждений о вычислимости, разрешимости некоторых массовых проблем и вычислительной сложности алгоритмов. Свои теоретические функции ММ в то время выполнила. Результаты исследований еще не полностью использованы до настоящего времени. Ими будут пользоваться еще не одно столетие.
6.1.2. Общие характеристики ММ. С появлением ВМ и развитием информатики концепция ММ приобрела новые теоретические черты и практическое значение. Практика применения ВМ для построения и реализации ММ стала повсеместной. Наибольшего расцвета практика реализации ММ достигла при массовом внедрении ППП. Полная формализация ППП достигнута в языке программирования Ада [Язык88]. ППП - это модель процессора, имеющего внутреннюю память для выполнения операций-процедур. Почти каждая программа является ММ при включении в нее процедур или функций. Новыми качествами ММ стали:

  • гибкость и адаптируемость разработки и применения ММ; программу ММ изменить в развитии легче, чем техническое воплощение ВМ;

  • возможность построения физической реализаций ММ после апробации их на ВМ; отработка, например, системы команд проектируемой ВМ позволяет автоматизировать процессы физической реализации;

  • автоматизированная или автоматическая разработка интерпретаторов ВМ и ММ; этап создания ММ связан с построением интерпретаторов ВМ, с помощью которых оценивается пригодность и реализуемость архитектуры ВМ;

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

  • применение к семейству ММ операций композиции для построения новых ММ; ММ можно проектировать операционным методом;

  • построение интерпретаторов операций композиции ММ; к процессам создания новых ММ можно применить тот же подход, что и применяемый при создании исходных ММ (принцип рекурсивного проектирования);

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

  • реализация в составе ОС виртуальных ММ; этот известный путь также может быть предметом для построения ММ.


6.1.3. Формальное описание ММ. Формальное описание ММ содержит тройку множеств (здесь примем локальные обозначения):
ММ = <семейство множеств данных (СМД);

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

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

12. сохранять и передавать веточки в память,

13. управлять стеком величин,

14. управлять стеком операций,

15. упорядочивать веточки в БЗ,

16. интерпретировать операции,

17. применять правила логического вывода,

18. оптимизировать число веточек в наборе совместных фактов,

19. оптимизировать число веточек в наборах альтернативных фактов,

20. строить альтернативы предрешений,

21. обнаруживать локальные и глобальные противоречия знаний,

22. определять и идентифицировать ошибки,

23. распределять память МЛВ,

24. вести статистический подсчет некоторых параметров и величин МЛВ.

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


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

6.7. Машина генерации кода синтезируемой программы
Если БЗ не полна или неизвестны исходные данные для поиска значений искомых величин, то по команде пользователя начинает работу ММ генерации кода программы решения задания (ММГ, для Интеллсист она именуется сокращенно как ГП – генератор программ). ММГ также как и все ММ имеет память - это совокупная память Интеллсист и процессор для реализации операций формирования СП. Кратко рассмотрим обобщенные операции ММГ в следующем порядке.
Анализ БЗ для определения свойств программы. При этом осуществляется определение понятий и операций, входящих в программу (входят только те операции и величины, которые используются в запросах), анализ программных циклов и зависимости выражений от величин, построение «схемы» программы, упорядочивание формул, если есть необходимость «исправления» последовательностей операций, составляется таблица запроса исходных данных, устраняется избыточность в БЗ (оптимизация), величины классифицируются на неизвестные, заданные, известные по фактам и запросные. Важно определять внутренние противоречия, связанные с бесконечными рекурсиями. Анализ направлен практически на определение программируемых и результирующих выражений. Первые составляют команды СП, вторые – фрагменты итоговой печати.
Использование терминологического словаря. Основная работа программиста – составление словаря идентификаторов – выполняется в ГП по таким правилам. По лексикону составляются описания величин на объектном языке. При этом каждый термин заменяется на идентификатор следующего вида ZномертерминаZ, по виду которого пользователем определяется (при необходимости) сам термин. Далее, в ГП составляются таблицы памяти, формируются списки величин для резервирования и освобождения памяти с определением мест таких операций, формируются вспомогательные рабочие величины с идентификаторами zномерпсевдотерминаz.
Построение операторов. Записи каждого программируемого выражения соответствует некоторый оператор языка программирования. При этом порождаются рабочие ячейки, выбираются формулы, которые выносятся за пределы цикла, формулы упорядочиваются внутри набора совместных фактов, определяется избыточность, используются стандартные модули. Для каждой альтернативы совместных фактов строится подпрограмма, которая в динамике выполнения программы может обнаружить повторно или новые противоречивые альтернативы, или совместные факты. В процессе построения операторов программируется операторы выделения памяти; присваивания начальных значений. Если перерабатывается запись алгоритма, то некоторые операторы уже известны (переход на метку, оператор процедуры), тогда их построение является формальным. Структуру программы, которая может представлять интерес только для программиста, можно обнаружить из распечатки исходного текста СП, который является выходным для ГП.
В качестве иллюстративного примера рассмотрим задание для Интеллсист.

раздел понятий:

~X или длина~: вещественный; -- 1 величина в терминологическом словаре

~C~: вещественный; -- 2 величина в терминологическом словаре

раздел запроса ~Решение квадратного уравнения~:

-- 3 величина в терминологическом словаре

найти X или длина такой, что X или длина *X или длина =2*X или длина +C. C > 0.
Программа:

диалог: введите значение C =


program Z3Z;

{uses - интерфейс запроса значений}

begin {asm}

Z4Z := 1;

Z5Z := sqrt(1 + Z2Z);

Z1Z := Z4Z + Z5Z;

{первый вариант}

output(«X = »)

output(Z1Z);

{второй вариант}

Z1Z := Z4Z - Z5Z;

output(«X = »)

output(Z1Z);

end.


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

Section of concepts ~ value of coordinate ~, ~ size of a product ~,

~ size of a product '~: real;

~ step of integration ~: real=0.01;

~ result ~: array[1..100]of real;

Section of inquiries ~ The decision of the differential equation ~:

value of coordinate:=1;^ size of a product:=1;^ for ~i~: word(i<100;^

size of a product' := size of a product **2-3 * size of a product *

value of coordinate +5 * value of coordinate;^

value of coordinate := value of coordinate + step of integration;^

size of a product := size of a product + step of integration * size of a product';^

result[i+1]:= size of a product).


end. Конец записи задания.
Синтезированная программа.

unit MyPrograma;

interface

function Z0AZ: Boolean;

implementation

uses Z126SZ, Z178SZ, Z127SZ, Z128SZ, { Standard modules }

MyProgramp, MyPrograme, MyProgramc, MyProgramv, MyProgramt;

function Z0AZ: Boolean; { The main module addresses to it }

label Z133SZ;

var Z241Z: Word;

begin

Z0AZ:=False;



Z235Z:=1; Z236Z:=1;

Z0WZ:=True;

for Z241Z:=0 to 65535 do begin

if not (Z241Z < 100) then begin

Z0WZ:=False; Break;

end;


Z237Z:=Z51SZ(Z236Z, 2)-3*Z236Z*Z235Z+5*Z235Z;

Z235Z:=Z235Z+Z238Z; Z236Z:=Z236Z+Z238Z*Z237Z;

Z239Z[Z241Z+1]:=Z236Z; { The array is described in the module MyProgramv }

end;


if not Z0WZ then goto Z133SZ;

Z0AZ:=True; Z133SZ:



end;

end.
Для встроенной ВМ оператор write(F) использует имя в записи «Х =» значение для определения канала обмена, а значение для передачи его по каналу. Коллизии возникают при проникновении в программу операций, которые не могут интерпретироваться как работа с каналами. Например, Х > 27 не связывается с каналом, но остается в программе. А пример Х принадлежит М может интерпретироваться подпрограммами. Поэтому для встроенных программ подбирается минимально необходимый состав подпрограмм, которые включаются в общую программу для передачи на встроенную ВМ.


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

  1. . вход в меню и создание режимов и параметров работы,

  2. . трансляция текстовых программ в кодовые или использование кодовой программы,

  3. . запуск программы с исходными данными,

  4. . ввод данных (таблицы, массивы, файлы) в диалоге с пользователем или из файла,

  5. . запрос вариантов запуска (в заданном режиме),

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

  7. . работа интерфейса с каналами и учет режимов запуска (рандеву задач),

  8. . отладка программ в режимах, коррекция БЗ и запросов

  9. . исправление обнаруживаемых ошибок,

  10. . выполнение технологии выдачи результатов,

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

  12. . ложные факты выводятся с пометкой «Противоречие» с указанием причины противоречий,

  13. . для встраиваемых программ результаты передаются по каналам вместе с сигналами о противоречиях (коды ошибок),

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

Здесь затронут (правда кратко) весь спектр вопросов автоматического проектирования СП. Этим завершается рассмотрение примеров применения ММ в рамках ИП.




Каталог: files
files -> Чисть I. История. Введение: Предмет философии науки Глава I. Философия науки как прикладная логика: Логический позитивизм
files -> Занятие № Философская проза Ж.=П. Сартра и А. Камю. Философские истоки литературы экзистенциализма
files -> -
files -> Взаимодействие поэзии и прозы в англо-ирландской литературе первой половины XX века
files -> Эрнст Гомбрих История искусства москва 1998
files -> Питер москва Санкт-Петарбург -нижний Новгород • Воронеж Ростов-на-Дону • Екатеринбург • Самара Киев- харьков • Минск 2003 ббк 88. 1(0)
files -> Антиискусство как социальное явлеНИе
files -> Издательство
files -> Список иностранных песен
files -> Репертуар группы


Поделитесь с Вашими друзьями:
1   ...   15   16   17   18   19   20   21   22   23


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница