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


Графический метаязык. Алгоритмы порождения и распознавания



страница18/23
Дата01.08.2016
Размер4.61 Mb.
1   ...   15   16   17   18   19   20   21   22   23

5.2. Графический метаязык. Алгоритмы порождения и распознавания
В результате аналитического анализа текстов языка формируются графы с большим или бесконечным числом узлов. необходимо обеспечить конечность числа узлов, что было продемонстрировано выше. Кроме этого, для обеспечения внешней наглядности необходимо принять ряд соглашений о способах вычерчивания графов. Сами соглашения представлены в форме правил замены одних фрагментов графа на другие, не меняющие смысл графа языка.
5.2.1. Графический метаязык. На примерах предыдущего раздела показана необходимость преобразования исходного графа с целью сокращения (элиминации) числа вершин (и дуг соответственно) и приведения графа к читаемому виду. Для преобразования графов введем несколько правил, совокупность которых определяет метаязык построения ГЯ. Так как метаязык относится к графическим объектам, то будем называть его графическим метаязыком. Рассмотрим правила сокращения графа языка путем сопоставления двух форм подграфов.
Правило 1. Пучок выходных дуг будем изображать для наглядности гребенкой:



Это правило вводит дополнительную вершину Х с r(Х) = nil, что не изменяет исходного языка ни по существу, ни по составу слов.


П
равило 2.
Пучок входных дуг будем изображать гребенкой:
Это правило также вводит дополнительную вершину без внесения ничего нового в сам язык.
П
равило 3.
Замена катенации символов соответствующим словом. Граф из цепочки символов заменяется графом с одной вершиной – прямоугольником.
Обратим внимание на тот факт, что на месте вершины в примере графа слово состоит из терминальных символов. Это правило ничего нового в язык не вносит. Нагруженность вершины (по r(Х)) можно указывать совмещением вершины и терминального символа (вспомогательное правило).
П
равило 4
. Альтернативный выбор в пучке дуг заменяется одной вершиной - прямоугольником с последовательностью альтернативных символов. Граф с альтернативным выбором заменяется прямоугольником, в котором должны быть перечислены все альтернативы. Правило несколько сокращает объем графа и делает его более наглядным для изучения и восприятия.
П
равило 5
. Пусть имеется набор альтернативных символов таких, что их значения образуют непрерывный отрезок натурального ряда. Правило замены диапазона альтернативных символов прямоугольником с двумя отделениями для указания концов диапазона можно представить так:
Правило 6. Замена подграфа одной вершиной сокращает общий графический объем ГЯ, если в нем имеются по крайней мере два одинаковых подграфа. Образец правила имеет вид овала с именем подграфа, которое фактически именует подъязык исходного языка. Подграф выступает в роли подпрограммы для всего ГЯ. Имя подграфа по своему существу является нетерминальным символом в ГЯ. Под этим именем изображается подграф, который формально определяется рекурсивно как любой ГЯ.





П
равило 7
. Игнорирование символа связано с принятым в некоторых ФЯ игнорированием символа (например пробела). В языке Алгол 60 символы пробела игнорируются в текстах программ, они не влияют на выполнение алгоритма. Однако, разделителем слов является пробел. Этим пробелом игнорировать нельзя, он играет важную роль для алгоритма. Пробел существен также в кавычках, где его пропуски невозможны. Граф с игнорированием символа можно представить следующим образом (первый граф):
П
равило 8.
Отмена игнорирования символа (см. выше, второй граф) связана с предыдущим правилом игнорирования символа. Там, где игнорируемый символ вновь приобретает значение, необходимо произвести отмену игнорирования. Роль 7 и 8 правил видна на примере полного графа без игнорирования символа пробела:
Этот граф эквивалентен следующему графу:




Правило 9. Обозначение прагматического ограничения на число используемых символов. Сошлемся на пример языка Фортран, в котором разрешается использовать в идентификаторах не более шести букв или цифр. Это прагматическое ограничение сложно представить в порождающей грамматике. Распознающие грамматики предоставляют возможность введения подобных ограничений. В ГЯ на дугу навешивается функция, а точнее - число, которые показывают на число допустимых прохождений дуги при распознавании или порождении текста подграфа, охваченного этой дугой. Пример с идентификатором языка Фортран можно представить так:





Правило 10. Указание границ для позиций записи. Прежде всего построим описание одного класса языков, которые связаны с использованием форматного листа (бланка) для представления программ. Примерами могут служить бланки для записи программ на ассемблерном языке, на языке Фортран или на языке РПГ. Особенность таких записей состоит в том, что значение языкового символа в записи зависит от позиции текста. В языке Фортран 1 может значить в одной и той же строчке метку оператора, признак продолжения формулы, целое число или номер перфокарты. Языки подобного сорта называются форматными.
Ф
орматным языком называется ФЯ, у которого значение символа зависит от позиции текста, в котором помещен этот символ. Форматные языки постепенно исчезают, поэтому здесь только будут показаны средства для представления таких языков, не заботясь об иллюстрациях. Форматные языки не могут быть представлены порождающими грамматиками. Многие свойства форматных языков могут представляться распознающими грамматиками. Правило 10 вводит условное обозначение для указания в ГЯ позиций текста, в которых используются те или иные подграфы. Указания границ не изменяют существа языка, но изменяют значения (смысл) символов в некоторых подграфах. Форма вершины в графе для указания границ такова:
где НГ - целое число, указывающее номер нижней границы фрагмента форматной записи, ВГ - целое число для верхней границы.
Правило 11. Распределение переходов на подграфы. Граф графически емкого языка не изображается на одном листе. Поэтому необходимо иметь средства для «соединения листов», чтобы ГЯ имел общую структуру. Вначале приводится правило для указания ссылки перехода на другой лист. Ссылка имеет вид:





П
равило 12.
Обозначение входа в подграф (в смысле листа бумаги или экрана) совпадает с именем вершины, поэтому оно используется в том случае, когда на него ссылаются другие вершины. Входы в подграф имеют вид:
П
равило 13.
Сохранение имени вершины в магазине. Для раскрутки рекурсии используется магазин (стек). В нем сохраняются имена вершин, на которые будет переход из некоторого места в ГЯ. Сохранение имени вершины графически изображается так:
Х ▬► m обозначает сохранение в стеке m имени вершины Х.
Правило 14. Вызов перехода из магазина. При переходе на подграф обычно в магазине запоминается место возврата. Наступает момент в распознавании, когда необходима реализация перехода в основной граф по исчерпании элементов подграфа. Переход по магазину представляется так:

где m - номер стека для выборки из него адреса возврата или имени вершины для возврата. Эта вершина является дополнительной, но не приносящей ничего нового в язык.



Все перечисленные правила существенно сокращают число вершин и дуг в ГЯ. Это приводит к такому же сокращению размеров программы грамматического разбора, что в свою очередь сокращает объем используемой памяти для ее хранения. Одновременно решается задача обеспечения наглядности в представлении ГЯ для человека. Набор правил завершен, теперь переходим к разбору алгоритмов порождения и распознавания.
5.2.2. Алгоритмы порождения и распознавания. Чтобы убедиться в том, что граф языка в одинаковой мере пригоден для порождения и распознавания текстов, рассмотрим алгоритмы на графе, которые генерируют текст данного языка и определяют принадлежность заданного текста данному языку. Начнем с алгоритма порождения (АП), чтобы сопоставить его с алгоритмом реализации формул подстановок порождающей грамматики, затем рассмотрим алгоритм распознавания (АР) и отличия его от алгоритма порождения.
Алгоритм порождения. Пусть задан ГЯ. Требуется получить слово этого языка. Алгоритм АП состоит из трех простых шагов. Но прежде рассмотрим общий процесс порождения. Пусть представляет состояние процесса порождения (или распознавания), С - текущее состояние слова после предыдущего выбора букв, Х - некоторая вершина. Тогда порождение представимо переходами () из одного состояния в другое: , где s = r(Хi), (Хk,Хi) - дуга в графе языка, Хi - определяется произвольным выбором некоторой дуги. Совокупность переходов определяет автомат порождения, который циклически выполняет следующие шаги.
Шаг 1: Рассмотрим входную вершину Х0 и дуги (Х0,Хi). По отображению r имеем Ø = r(Х0). Пустой символ не записывается в результат. Произвольно выберем дугу, например с вершиной Хi, и переходим к Шагу 2.
Шаг 2: Рассмотрим данную вершину Хi и произвольно выделим одну дугу из набора (Хi, Хk), в результат работы алгоритма запишем символ s = r(Хk) в результат так, что текущее слово С перейдет в слово С ^ s. Переходим к Шагу 3.
Шаг 3: Если вершина Хk = Х1, то процесс порождения завершается успешно, в противном случае переходим к шагу 2 с новой вершиной Хk (вместо вершины Хi).
Основная особенность АП заключается в использовании на шагах 1 и 2 процедуры произвольного выбора дуги. АП является недетерминированным алгоритмом. Конечно, в практической реализации имеются трудности зацикливания по одному и тому же пути. Реальный алгоритм должен учитывать такие ситуации и предпринимать эффективные меры по исключению зацикливаний. Мерой может быть заказ числа возможных повторений циклов. АП можно применить к порождению тестов для контроля трансляторов, а также к определению корректности грамматического разбора (об этом можно прочитать в томе 7).
Алгоритм распознавания. Второй алгоритм также состоит из трех шагов. В принятых выше обозначениях распознавание представимо переходами из одного состояния в другое: , где r(Хi) = s, (Хk,Хi) - дуга в графе языка, Хi выбирается из условия совпадения символа s из текста и символа r(Хi). Распознавание прошло удачно, если исходное слово С привело в результате цепочки переходов (==>) к слову Ø с вершиной Х1: ==> < Ø, Х1>. АР можно представить так.
Шаг 1: Рассмотрим входную вершину Х0, дуги (Х0,Хi) и первый символ s заданного распознаваемого слова-текста С. Вначале по отображению r имеется символ Ø = r(Х0), который входит в слово С. Из вершин xi выбираем ту, для которой r(Хi) = s. Если равенства невозможно получить, то объявляется синтаксическая ошибка, в противном случае переходим к Шагу 2.
Шаг 2: Рассмотрим данную вершину Хi, дуги (Хi, Хk) и следующий символ s заданного текста С. Сравниваем s = r(Хk). Если они равны для некоторой вершины Хр, то переходим к Шагу 2 с вершиной Хр вместо Хi, иначе переходим к Шагу 3. Если перебор всех Хк реализован и равенство s = r(Хk) не достигнуто, то объявляется синтаксическая ошибка.
Шаг 3: Осуществляется разбор случаев.

Хk = Х1, достигнуто состояние (C ^ Ø, Хk), следовательно, распознавание завершено успешно, АР завершил работу;

Хk =/= Х1 и достигнуто состояние (C ^ Ø, Хk), объявляется синтаксическая ошибка «текста недостаточно»;

Хk = Х1 и не достигнуто состояние (C ^ Ø, Хk) ), объявляется синтаксическая ошибка «лишний текст»;

Хk =/= Х1 и не достигнуто состояние (C ^ Ø, Хk), следует перейти к Шагу 2.
Итак, полный маршрут в ГЯ от Х0 до Х1 соответствует слову (тексту вообще), которое принадлежит языку. Совокупность полных маршрутов определяет весь язык.
5.2.3. Применения алгоритмов. АР находит применение в трансляторах формальных и формализованных языков. Схематически применение АР можно представить так. Пара <АР,ГЯ> является алгоритмическим представлением грамматического анализатора текстов данного языка, соответствующего ГЯ. Реализация АР называется машиной грамматического разбора. Реализация ГЯ, вводимой распознающей грамматики в память ВМ, называется программой грамматического разбора (ПГР). Пара <МГР,ПГР> является реализацией пары <АР,ГЯ>, что представляет собой грамматический анализатор текстов данного языка. Можно построить интерпретатор МГР (ИМГР) и коды ПГР (КПГР), тогда пара <ИМГР,КПГР> является транслятором данного языка. Если ГЯ является синтаксическим, то транслятор будет выполнять функции синтаксического анализатора. Если ГЯ является семантическим, то транслятор выполняет свои собственные функции перевода входного слова или текста в выходной текст.
АР находит применение в программах управления, когда необходимо распознать входное слово или входной текст и выработать команду управления. Это важное применение во встроенных ВМ.
МГР классифицируется на 4 класса. Классификация Хомского имела 3 класса грамматик и в качестве четвертого класса рассматривались все остальные грамматики, которые не укладывались в первые три класса. Классификация МГР связана с числом синхронизуемых символов (слов или подграфов языка) и с установлением соотношений анализируемых символов и состояний памяти МГР. Возможны случаи: синхронизация отсутствует (МГР1), имеется синхронизация пар символов (МГР2), имеется хотя бы одна синхронизация двух и большего числа символов (МГР3) и имеется «синхронизация» символов и состояний (имен вершин) графа языка (МГР4). Классификация становится более понятной при рассмотрении системы команд МГР каждого из четырех номеров, построенной на основе АР.
Структура транслятора ФЯ на базе МГР дана ниже в форме блок-схемы.



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


Для определения свойств четырех типов МГР рассмотрим системы команд.

5.3. Система команд МГР типа 1
ГЯ - это объемный рисунок, легко воспринимаемый человеком для понимания языка. Для работы АР (да и АП) необходимо выполнить операцию ввода ГЯ в память МГР. При этом нужно иметь в виду, что память МГР (как и память ВМ) является линейной - последовательность ячеек, адресованных номерами из отрезка натурального ряда. При рассмотрении ГЯ можно определить ту информацию, которую необходимо ввести, чтобы отобразить все атрибуты ГЯ. Из определения ГЯ видны все атрибуты:

1. имя данной вершины,

2. сорт вершины (код операции),

3. терминальный символ (имя вершины),

4. имя вершины, на которую ссылается данная вершина,

5. число выходных дуг,

6. метка семантической подпрограммы p из множества М (имя вершины).

При этом необходимо каким-либо образом отметить начальную вершину Х0 и конечную вершину Х1 в ГЯ. Этой информации достаточно для отображения распознающей грамматики в памяти МГР. Заметим, что графический метаязык вводит новые сорта вершин, которые также должны быть отражены при вводе ГЯ. Некоторые правила графического метаязыка требуют добавления двух атрибутов: номер магазина и имя вершины для возврата из подграфа. Единица кода ГЯ, содержащая указанные атрибуты называется командой МГР, а последовательность команд - программой грамматического разбора.


Процессор МГР выполняет все примитивы, определяемые АР и графическим метаязыком. Они будут ясны из объяснения алгоритмов выполнения команд ПГР. Ячейки памяти ИМГР перенумерованы от 0 до некоторого конечного N+1, N равно числу вершин ГЯ. В каждой ячейке помещается информация об одной вершине - одна команда ПГР. Примем соглашение о том, что в ячейке с номером 0 содержится информация о вершине Х1, а в ячейке с номером 1 - о вершине Х0. Как сказано информация о вершине определяет команду ПГР, так как вершина - это указатель продолжения пути выбора полного маршрута в ГЯ. Совокупность разновидностей команд (кодов операций) определяет систему команд МГР. Форма и состав команды определяется кодом команды.
Традиционно язык системы команд определяется либо кодами (в некоторой системе счисления), либо он является ассемблерным языком, либо он является языком высокого уровня. Первый метод представления не эффективен (малопознаваем), поэтому его рассматривать не будем. Второй метод выберем в качестве образца для описания системы команд МГР. Третий метод избыточен, так как всего необходимы две команд и их модификации для представления системы команд МГР (мало разнообразие операций). Третий метод применен в инструментарии программного комплекса «Галактика» Красиловым Н.А., реализация ГЯ представляется средствами ФРАК. С помощью ассемблера можно породить кодовое представление ПГР, но при этом естественно уменьшается наглядность программы.
Рассмотрим систему команд МГР1 на языке ассемблера. В системе определяется две главные команды (квадратные скобки используются для указания возможности опускания их содержимого) и алгоритмы их выполнения:
[имя вершины 1 :] ЕСЛИ символ, ТО имя вершины 2 [(число дуг)];
Имя вершины 1 (термин) можно опускать, как указывалось ранее в примерах, если на это имя нет ссылок в ПГР. Число дуг опускается, если оно равно единице. Каждая команда завершается символом точки с запятой. Если текст команды рассматривать в целом, то она примет вид продукции языка знаний ЭС. Можно считать, что <МГР,ПГР> является своеобразной ЭС: МГР - оболочка ЭС, ПГР - знание о языке, представленное продукциями. Разнообразие продукций образует наборы команд МГР.
Первая команда называется командой условного перехода. Она выполняется так. Текущий символ анализируемого текста сравнивается с символом из команды. Если в наличии совпадение, то следующей командой является та, которая помещена по адресу «имя вершины 2», при этом запоминается «число дуг» и выбирается очередной символ из анализируемого текста. Если обнаружено несовпадение, то по числу дуг от предыдущей команды определяется «все ли команды для анализа рассмотрены». Если все команды рассмотрены (при выполнении их не получено совпадение), то объявляется синтаксическая ошибка. В противном случае рассматривается очередная команда для сравнения символов из команды и выбранного символа из текста. В другой системе команд число дуг может опускаться, если вслед за группой команд поставить специальную команду печати ошибок. Сказанное является повторением АР.
Вторая команда имеет следующий формат:
[имя вершины 1 :] НА имя вершины 2 [(число дуг)];
Эта запись именуется командой безусловного перехода, в ней отсутствует «символ» (или точнее сказать - в наличии пустой символ). Здесь также следует принимать во внимание замечания к первой команде. Выполнение команды состоит из безусловного перехода к рассмотрению группы команд из «числа дуг», размещенной после метки «имя вершины 2». При этом никаких ошибок в анализируемом тексте не обнаруживается. Ячейка с адресом 1 используется для команды безусловного перехода на начало ПГР.
Эти две команды полностью определяют систему команд МГР1. Однако для удобства программирования ФЯ введена команда останова. Путь выполнения ПГР в данный момент должен обязательно привести к вершине Х1. В ячейке с адресом 0 обычно помещается команда останова и выхода из ПГР. Чтобы программист не думал над путями выполнения ПГР, введена команда следующего вида:
[имя вершины :] СТОП;
Система команд МГР1 позволяет программировать ГЯ, представленный конечным числом вершин. Однако бесконечные слова могут обрабатываться с помощью конечного ГЯ, так как в ГЯ могут быть циклы, образованные безусловными переходами «вверх».
Мощность МГР1 приблизительно равна мощности линейных грамматик по Хомскому, если под мощностью понимать число языков, которые представляются ГЯ и средствами МГР1. «Приблизительность» равенства точно не исследовалась. Такая квалификация получена на основе рассмотрения примеров и некоторых интуитивных соображений относительно свойств линейных грамматик и МГР1. К примеру, порождающая грамматика <{a, b}, {L}, {Lab, LaLb}, L> не может быть запрограммирована на МГР1, она программируется на МГР2.

5.4. Система команд МГР типа 2 и Расширение системы команд МГР
Если язык содержит слова типа приведенного в примере 2, то возникает проблема одинарной синхронизации двух символов. Порождающая грамматика приведена в конце предыдущего раздела. Пример языка а**К^в**К подсказывает пути расширения системы команд МГР1 введением понятия подграфа по аналогии с понятием подпрограммы. Система команд МГР2 составляется из команд МГР1 добавлением двух новых команд. Кроме этого расширения системы команд МГР1 рассмотрим дополнительные команды, соответствующие графическому метаязыку и не расширяющие системы команд МГР1 и МГР2.
Известно, что подпрограммы реализуются с помощью стека, в котором запоминается адрес возврата из подпрограммы. ПГР составляется по таким же принципам. В ГЯ выделяются подграфы (подъязыки), которые программируются автономно и к которым осуществляется обращение по мере надобности. Две новые команды имеют формат следующего вида:
[имя вершины 1 :] ЕСЛИ символ, ТО имя вершины 2 (число дуг), имя вершины 3;
Первая команда выполняется аналогично команде условного перехода для МГР1, но при удачном сравнении и переходе по метке «имя вершины 2» в стеке (магазине) запоминается метка для возврата «имя вершины 3». Остальные части алгоритма выполнения команды аналогичны. Метка из вершины стека используется второй командой.
[имя вершины :] ВОЗВРАТ;
ВОЗВРАТ означает переход на одну команду по метке, которая выбирается из верхушки стека, или магазина. Содержимое магазина продвигается для размещения в верхушке магазина метки, помещенной туда ранее (принцип «последний пришел - первый обслужись»). Если в первой команде опустить ее часть «, имя вершины 3», то получается известная команда ИГР1.
Первая новая команда превращается в команду безусловного перехода, если опустить слово «символ» и воспользоваться обозначениями второй команды МГР1. Можно легко увидеть различие команд безусловного перехода для МГР1 и МГР2:
[имя вершины 1 :] НА имя вершины 2 (число дуг), имя вершины 3;
Итак, констатируем: МГР1 <= МГР2, всего введено 2+2 = 4 команды. Мощность МГР2 приблизительно (вопрос равносильности рассмотрен только на примерах, не найдена порождающая контекстно-свободная грамматика, которая не программируется на МГР2) равна мощности контекстно-свободных грамматик по Хомскому Теперь рассмотрим расширение системы команд МГР1 и МГР2, связанное с графическим метаязыком ГЯ. Расширение не привносит ничего нового в возможности процесса распознавания и увеличения мощности МГР. Правила графического метаязыка с номерами 1, 2 и 12 формальны, они только создают графическое удобство, не внося ничего нового в систему команд МГР. Правила с номерами 6, 13 и 14 уже учтены при формировании команд МГР2 и, следовательно, МГР3 и МГР4. Остальные правила метаязыка рассматриваются ниже. Правила 1, 2 и 12 не нуждаются в пояснениях, они являются введением условного обозначения.
Правило 3 реализуется командой условного перехода после совпадения каждого символа из анализируемого текста и каждого символа из анализируемого текста в приводимой ниже команде совместного сравнения:
ЕСЛИ строка, ТО имя вершины 1 ( число дуг ), имя вершины Д;
Здесь имя вершины-метки для наглядности опущено. Эта команда является сокращением следующей последовательности команд (что показывает на неизменность систем команд МГР):
ЕСЛИ строка[1], ТО имя вершины 2;

имя вершины 2: ЕСЛИ строка[2], ТО имя вершины 3;

.............................................................................................................

имя вершины К: ЕСЛИ строка[К], ТО имя вершины 1 ( число дуг ),

имя вершины Д;

где строка[Н] - символ с номером позиции Н в строке команды, Н = 1, 2,.., К.


Правило 4 реализуется командой условного перехода после совпадения одного символа из анализируемого текста и очередного символа из списка символов в следующей команде альтернативного сравнения и перехода при совпадении:
ЕСЛИАЛЬТ строка, ТО имя вершины 1 ( число дуг ), имя вершины 2;
Эта команда представляет сокращенную запись последовательности команд МГР с аналогичными атрибутами:
ЕСЛИ строка[1], ТО имя вершины 1 ( число дуг ), имя вершины 2;

ЕСЛИ строка[2], ТО имя вершины 1 ( число дуг ), имя вершины 2;

..........................................................................................................

ЕСЛИ строка[К], ТО имя вершины 1 ( число дуг ), имя вершины 2;


Правило 5 реализуется командой условного перехода после совпадения одного из символов диапазона, указанного в квадратных скобках и символа из анализируемого текста. Такая команда сравнения также представляет сокращенную запись последовательности команд с аналогичными атрибутами, как для команды ЕСЛИАЛЬТ. Общий вид команды приведен ниже:
ЕСЛИДИАП символ .. символ, ТО имя вершины 1 ( число дуг ), имя вершины 2;
Правило 7 реализуется командой МГР1 или МГР2 безусловного перехода с одновременным запоминанием указанного в команде символа в особом регистре или в специальном стеке:
ИГНОРИРОВАНИЕ символ, имя вершины 1 ( число дуг ), имя вершины 2;
Правило 8 реализуется командой отмены игнорирования символа и безусловного перехода к следующей команде. Команда отмены имеет вид:
ОТМЕНА символ;
Правило 9 реализуется командой указания числа допустимых циклов (функция, нагруженная на дугу) следующего вида:
НА имя вершины, { число циклов };
Правило 10 реализуется командой указания пар чисел - номеров позиций форматного текста (форматного языка), в пределах которых реализуются данный подграф (нагруженные на дуги функции). Команда имеет следующий вид:
ГРАНИЦЫ число 1 .. число 2;
Правило 11 реализуется командой указания числа допустимых переходов при достижении соответствующего номера позиции форматного текста (нагруженные на дуги функции). Команда имеет следующий вид:
НА [ номер позиции 1, имя вершины 1,

номер позиции 2, имя вершины 2,

.....................................................

номер позиции К, имя вершины К ];


Все рассмотренные команды реализации правил графического метаязыка, представляющие расширение системы команд МГР1 и МГР2, переносятся в системы команд МГР3 и МГР4. Для переноса их достаточно сделать необходимые добавления в командах, касающиеся включения номеров магазинов, в которых следует сохранять метки для возврата из подпрограммы в основную ПГР.

5.5. Система команд МГР типа 3
Для программирования синхронизации двух и более текстов (или символов) необходимо ввести соответствующее число магазинов. Выше был рассмотрен пример контекстно-зависимого языка а**К^в**К^с*к. Для распознавания двух зависимостей «а» и «в» необходимы два магазина. Система команд МГР2 расширяется еще на две команды введением в команду указания номера магазина. Система команд с таким расширением образует систему команд МГР3. Таким образом символически МГР3 = МГР2 + две команды. Одна команда условного перехода после совпадения очередного символа анализируемого текста и символа команды осуществляет запоминание метки перехода в магазине с заданным номером, другая команда осуществляет возврат по содержимому верхушки магазина с заданным номером.
[имя вершины 1 :] ЕСЛИ символ, ТО имя вершины 2 (число дуг),

имя вершины 3 (номер магазина);


Для этой команды имеется аналогичная команда безусловного перехода, если необходимо реализовать сравнение с пустым символом, она почти отличается от команда условного перехода отсутствием символа, с которым осуществляется сравнение. Команда имеет вид:
[имя вершины 1 :] НА имя вершины 2 (число дуг),

имя вершины 3 (номер магазина);

она эквивалентна команде:

[имя вершины 1 :] ЕСЛИ Ø, ТО имя вершины 2 (число дуг),



имя вершины 3 (номер магазина);
Вторая команда МГР3 реализует возврат из подпрограммы (подграфа) на метку, хранящуюся в магазине с известным номером:
[имя вершины :] ВОЗВРАТ (номер магазина);
Мощность МГР3 приблизительно равна мощности контекстно-зависимых порождающих языков Хомского. Не было найдено ни одного такого языка, который бы не был программирован на МГР3.
Практика программирования ФЯ указывает метод реализации числа магазинов, более одного. Действительно, выделение памяти для многих магазинов (или стеков) требует резервирования памяти по каждому магазину, что является не очень экономным методом. Можно использовать один магазин, в каждой ячейке которого кроме метки возврата сохраняется еще и номер магазина. В этом случае память резервируется только для одного магазина, но несколько усложняется алгоритм поиска и выбора метки возврата, находящейся в верхушке магазина с известным номером.
Ниже представлена таблица обзора применения МГР для сравнения реализации практически полезных ФЯ, представленных порождающими и распознающими грамматиками. Поскольку аппарат МГР оказался эффективным в практических работах по реализации трансляторов, были проанализированы различные и конкретные трансляторы. Результаты анализа представлены в таблице. Число правил порождающих грамматик не подразумевает объединение правил-альтернатив (применение операции | по Бэкус-Науру или «;» по метаязыку Марков), все они считаются различными.


Пункт

Язык порождения

Число правил

Число команд распознавания

Литература с описанием языка

1

КС-грамматика

83

45

[Красилов75]

2

Алгол 60

360

540

[Лавров64]

3

Алгол 60*

360

380

[Красилов67]

4

Фортран

-

450

[Языки72]

5

Анализ

325

800

[Красилов73в]

6

ФРАК

340

530

[Красилов78б]

7

Диалог

-

100

[Красилов86а]

8

Ляпас-М

-

400

[Закревский]

9

Модель

300

360

[рукопись]

10

Логика-0

210

230

[рукопись]

11

Ада

500

1800

[Джехани88]

Комментарии к таблице содержит краткую характеристику известных и мало известных языков программирования:


КС-грамматика - это порождающая грамматика для описания КС-грамматик (см. метаязык Марков), он необходим был для построения конструктора или транслятора программ грамматического разбора (конструктор ПГР). Число команд распознавания вдвое меньше числа правил КС-грамматики, что обусловлено использованием команд альтернативного сравнения.
Алгол 60* - язык Алгол 60, для которого ключевые (зарезервированные) слова (или терминальные символы языка) являются и терминальными символами устройства ввода текстов программ на этом языке. Например, для ключевого символа begin на специальном клавишном устройстве существовала клавиша с таким терминальным символом.
Анализ - язык для записи алгоритмов аналитических выкладок на машине. В языке введено понятие определения типа данных (по образцу языка Алгол 68), что привело к увеличению размеров ПГР за счет распознавания новых типов данных по сравнению с размерами порождающей грамматики.
ФРАК - формульный автокод (см. разделы 1.2 и 1.3), машинно-ориентированный язык высокого уровня, построенный по принципам языка высокого уровня, но содержащий только машинные операции, представленные текстуально в формулах. Таких языков составлялось для четырех типов встроенных ВМ и шести их модификаций.
Диалог - простейший язык меню на ЭВМ М-222. Простейшее одно из первых меню на этой машине реализовал Горельков А.Л. Транслятор переводил запросы пользователя и осуществлял вызов запрашиваемой работы.
Ляпас - язык Закревского А.Д. предназначен для описания электронных схем при автоматизации моделирования и проектирования радиоаппаратуры. Этот язык описан неформально, а соответствующая программа МГР явилась первой формализацией распознающей грамматикой для языка Ляпас-М.
Модель - язык описания микропроцессоров для автоматического построения интерпретаторов и микропрограмм. На основе языка была реализована система моделирования электронных схем, транслятор - ассемблер микропроцессора и документатор рабочих программ управления.
Логика-0 - язык описания произвольных исчислений высказываний для доказательства теорем этого исчисления на машине. На этом языке описывалась исследуемая аксиоматика и доказываемые теоремы. Результатом работы системы было подтверждение правильности формулировки теоремы или условие, при котором исходное утверждение являлось бы теоремой.
Ада - алгоритмический язык для программирования встроенных ВМ специального назначения [Красилов83а, 86б, 87а, 88б, 89в]. Число команд программы грамматического разбора увеличено за счет программирования семантического распознавания назначения идентификатора.
Рассмотрим примеры другого сорта. Именно, ниже будут показаны четыре академических примера для характеристики сложности программ грамматического разбора (сами программы не приводятся). Примеры программ разрабатывались студентами. Основной и важной характеристикой программы (в ней содержится интеллектуальность языка) является количество используемых магазинов.
Пример 1. В трехбуквенном алфавите {a, b, c} разрешено строить слова, содержащие одинаковое число каждой буквы в любом порядке, размер слова языка определяется как C = 3*k. Программа для МГР3 имеет 30 команд, 9 магазинов. Для n-буквенного алфавита число команд равно А*n, а число магазинов равно n*n.
Пример 2. Линейный КС-язык состоит из слов XY n-буквенного алфавита, где Y - обращение X (запись Х выполнена посимвольно в обратном порядке относительно порядка символов в Y). Программа грамматического разбора МГР3 состоит из 8*n + 8 команд и использует n + 3 магазина.
Пример 3. В двухбуквенном алфавите распознавание слова ХХ (двойное повторение слова Х) программируется 28 командами МГР3 и 7 магазинами. Порождающая грамматика состоит из 17 формул подстановки НС-грамматики.
Пример 4. Язык состоит из слов однобуквенного алфавита длиною n*n. Программа МГР3 состоит из 17 команд, использующих 3 магазина. Порождающая грамматика состоит из 11 формул подстановок НС-грамматики.
Самый общий вывод, к которому можно прийти после анализа примеров, состоит в том, что число команд ПГР приблизительно равно числу формул подстановок порождающей грамматики (одинаковая информативность). Другой вывод: конструирование ГЯ значительно проще конструирования порождающих грамматик, а построение ПГР осуществляется автоматизировано по ГЯ.

5.6. Система команд МГР типа 4
Можно установить, что возможностей МГР3 еще недостаточно для реализации любого ГЯ. Поэтому рассматривается следующий тип МГР с добавлением еще двух команд к МГР3 так, что МГР4 = МГР3 + две команды. Первая команда заносит в магазин с известным номером метку (своеобразный символ), она имеет следующий вид, напоминающий вид команд МГР2 и МГР3:
[имя вершины 1 :] МАГАЗИН имя вершины 2 (число команд),

имя вершины 3 (номер магазина);


Вторая команда МГР4 связана со сравнением содержимого верхушки магазина с меткой в команде и переходом на группу команд при совпадении меток из команды и из магазина. Формат команды таков:
[имя вершины 1 :] СРАВНЕНИЕ содержимое магазина (номер магазина),

имя вершины 2 (число дуг);


Имя вершины2 - метка перехода при совпадении «содержимого магазина» команды и содержимого магазина с заданным номером. Конечно, для хранения меток можно выбрать специальный магазин, предназначенный только для меток, чтобы избежать коллизий символов и меток при возникновении грамматических ошибок, или воспользоваться имеющимся магазином. Команда сравнения может быть расширена введением атрибутов запоминания меток возврата.
Вместо заключения. Этим завершается построение системы команд МГР. Состав системы команд насчитывает всего 8 команд без учета расширения, не вносящего ничего нового в процессы грамматического разбора текстов. Мощность МГР больше мощности системы языков с порождающими грамматиками Хомского. Для установления мощности МГР осуществим сравнение МГР и МТ. Тип языка можно определять типом используемой МГР.
Система команд МГР любого типа отражает синтаксический вариант ГЯ. Для программирования семантического ГЯ в формат команд необходимо добавить еще одно поле, в котором надо помещать имя подпрограммы формирования выходного текста. Для ГЯсем принят следующий формат команд:
[имя вершины 1 :] ЕСЛИ символ, ТО имя вершины 2 (число дуг),

имя вершины 3 (номер магазина), имя семантики;



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

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

(1) Знаковое моделирование предусматривает сопоставление терминальных алфавитов МГР и МТ. Они идентичны полностью. Обе машины перерабатывают слова в одном и том же терминальном алфавите. Правда, МТ может содержать в терминальном алфавите еще три символа: начало слова, конец слова и символ останова. Их моделирование не усложняют проблему сопоставления, поэтому будем ими пренебрегать для простоты.

(2) Языковое моделирование предусматривает сопоставление системы команд обеих машин. Это главный раздел моделирования, он будет рассмотрен далее.

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

(4) Информатическое моделирование предусматривает сопоставление знаний, получаемых при переработке исходного слова в результат. Обе машины эквивалентны в смысле разрешения главной проблемы, они получают одинаковые результаты. Далее.

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

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

(7) Структурное моделирование предусматривает сопоставление физического состава обеих машин. Бесконечную в оба конца ленту МТ будем моделировать двумя магазинами (фактически можно моделировать одним магазином). Логическое устройство МТ моделируется алгоритмами МГР. Движение ленты МТ моделируется выборкой из магазина, например, при движении ленты влево, и посылкой в другой магазин. Эти разделы полностью гарантируют правильность доказательства теоремы. Доказательство теоремы проведено совместно со студентом МФТИ Лукашевым В.В.


Таким образом процесс доказательства сводится при указанных условиях к программированию команд МТ подпрограммами МГР. В качестве следствия теоремы можно сказать о том, что множества языков, обрабатываемых на МТ и МГР равномощны. Различие машин имеется только в количествах выполняемых операций над одним и тем же алгоритмом. Здесь сказывается потеря производительности МГР по сравнению с МТ как при всяком моделировании.
Прежде всего примем некоторую модель МТ. Заметим, что теоретически имеются самые разнообразные модели МТ. Имеется также фундаментальное утверждение о функциональной эквивалентности всех модификаций МТ. В связи с этим будет использован простейший (классический) вариант МТ, что упростит понимание основной теоремы об эквивалентности МГР и МТ. Заметим также еще раз, что установление эквивалентности МГР и МТ дает возможность переноса всех свойств МТ на МГР. Эта возможность является прагматической целью изучения эквивалентности. Так как относительно свойств МТ накоплено много теорем, то перенос сущности утверждений относительно МТ на МГР снимает трудности поиска доказательств аналогичных утверждений для МГР.
МТ имеет бесконечную в оба конца ленту с ячейками для хранения терминальных символов алфавита Т = {А1,А2,...,Аn}, читающую или пишущую головку, логическое устройство (ЛУ) программного управления и двигатель D ленты, перемещающий ленту за один такт выполнения команды влево (L) на одну ячейку, вправо (R) на одну ячейку или не перемещающий ленту (N). ЛУ может находиться в одном из состояний Q = {q0,q1,q2,...,qm}. D - представляется символами из множества {L,R,N}. Для МТ имеются специальные символы # - заполняющие левый конец ленты, $ - заполняющие правый конец ленты и «!» - обозначающий в программе остановку МТ. Введение этих символов условно. Между символами # и $ помещается слово S (s1,s2,s3,..,sn) из терминальных символов Т для обработки по программе. Результат обработки сохраняется на ленте. Если результатом является пустое слово, то проблема принадлежности слова языку разрешается положительно, в противном случае в исследуемом слове имеется языковая ошибка. Далее. Символы # и $ не обрабатываются, а символ (!) моделируется командой МГР останова.
Команда управления МТ реализует один элемент отображения следующего вида: Т * Q --> D * T * Q. За один такт работы МТ выполняется преобразование вида: (Аi, qj) --> (d, Аk, ql), где d равно L, R, N (или !). Как было сказано, будем рассматривать несколько упрощенный вариант системы команд МТ, которая состоит из трех сортов команд (обычно программа МТ задается таблицей из m строчек и n столбцов):
1. (Аi, qj) --> (N, Аk, ql),

2. (Аi, qj) --> (L, ql),

3. (Аi, qj) --> (R, ql).
МТ предназначена для производства вычислений или для реализации вычислительных функций, в то время как МГР реализует распознавание истинности соотношения S in Я. Будем рассматривать программы работы МТ, которые реализуют функции:

= Ø, если S in Я

МТ(S)



=/= Ø, если not(S in Я)
Будем считать, что ячейка ленты МТ, которую обозревает читающая головка, моделируется верхушкой первого магазина МГР. Также будем считать, что читающая головка установлена на начало слова S. Подпрограммы-модели команд МТ соответствуют любой из трех команд, поэтому начальная установка головки несущественна.
Переходим к построению подпрограмм моделирования каждой команды МТ. Начало каждой подпрограммы включает последовательность команд МГР для распознавания символа, который помещен под читающей головкой. Затем подпрограмма реализует действия, предусмотренные командой МТ. Трем командам МТ соответствуют три подпрограммы МГР. Начало подпрограмм состоит из последовательности команд МГР типа 4:
qik : СРАВНЕНИЕ qkl, Aj (1);
гле qik, qkl - некоторые состояния МТ из алфавита состояний Q, (1) - номер магазина, моделирующего левую часть бесконечной ленты, i, k, l = 1, 2,.., m. Всего таких команд в последовательности m*n. Для каждой из трех команд запишем подпрограммы МГР.
Команда первого типа. После определения искомого символа Aj выполняется замена символа Aj на символ Ak и переход в состояние ql (передача управления на идентичное имя вершины) с числом команд К:
qkl : НА qk (К), Ак (1);
На этом моделирование команды МТ первого типа завершается. Число таких команд МГР равно числу состояний ЛУ.
Команда второго типа. Пусть определение искомого символа реализовано. Тогда моделирующая подпрограмма для этой команды МТ чуть сложнее, так как она связана с моделированием перемещения ленты МТ влево. Для этого надо произвести распознавание символа во втором магазине (в левой части бесконечной ленты) с выборкой символа и записью выбранного символа в верхушку первого магазина. Но прежде необходимо выбранный при начальном распознавании символ поместить в магазин номер 1 (вернуть в прежнее состояние содержимое ленты). Команда МГР из последовательности имеет вид:
qkl : НА qр (К), Аj (1);
После выполнения одной из команд последовательности необходимо распознать символ верхушки второго магазина. Это делается аналогично поиску при начальном распознавании символа:
qр : СРАВНЕНИЕ qх, Aх (2);
Теперь надо записать символ Aх в верхушку первого магазина. Для этого используются команды следующего вида:
qх : НА ql (К), Ах (1);
Такими группами команд моделируется перемещение ленты влево и второй команды МТ.
Команда третьего типа. Пусть определение искомого символа реализовано. Тогда моделирующая подпрограмма для этой команды МТ будет простой, поскольку моделирование перемещения ленты вправо реализуется одной командой МГР. Достаточно восстановить верхушку второго магазина символом, который распознан при начальном распознавании. Представляющую последовательность команда МГР имеет вид:
qkl : НА ql (К), Аj (2);
Программа МТ переведена в ПГР покомандно с помощью подпрограмм моделирования каждой команды МТ. Таким образом, каждая программа МТ может быть переведена в программу МГР, что доказывает ЯМГР >= ЯМТ и всю теорему эквивалентности МГР и МТ. Следовательно, если любая программа МТ может быть выполнена на МГР, то свойства МГР аналогичны свойствам МТ.

Каталог: 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
обратиться к администрации

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