Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа), страница 4
Описание файла
PDF-файл из архива "Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа)", который расположен в категории "". Всё это находится в предмете "дипломы и вкр" из 8 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "выпускные работы и поступление в магистратуру" в общих файлах.
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Описание программы4.1. Графический интерфейсПрограмма начинает свою работу сразу же после запуска.Графический интерфейс пользователя изображён на рисунке 4.1.30Рис 4.1. Окно программыВ левой части окна расположен список со всеми доступнымифункциями. Функции взяты из исходного файла, который расположен поумолчанию в папке с программой. Далее расположен список всевозможныхопределений выбранной функции. В правой части находится некотораяинформация о функции или определении – имя функции, имя класса, вкотором хранится информация о функции, арность функции, и её граическоепредставление.В нижней части расположено окно с информацией о процессе разбора ипроцессе построения деревьев или графических представлений.Чтобы перейти к процессу вычислений схем направленных отношенийтребуется выбрать функцию для подстановки и её реализации (Рис 4.2).31Рис 4.2 Выбор подставляемой функцииПосле очередногоэтапа совершения подстановкиопределений функции будут добавляться её новые определения.в списке32Рис 4.3 Результат процесса вычисления4.2.
ВыводВ работе реализована базовая система функционально-логическогопрограммирования (СФЛП). Созданы средства распознавания и анализаисходного кода программ на разновидности языка FLOGOL; разработанасистема структур внутренних представлений направленных отношений,выраженных в алгебраической и графической формах и их зависимостях.Реализована процедура вычислений направленных отношений на основепринципа сетевой резолюции.Программа разработана в среде Visual studio 2010 на языке C# сиспользованием платформы .NET Framework.4.3. ПерспективыОдним из недостатков работы с алгебраическим представлениемявляется высокая сложность алгоритма редукции дерева.. Поэтому одной из33основных проблем является решение задачи оптимизации алгоритмов βредукции НО в форме алгебраического представления.В рассматриваемой программе не реализовано получение информацииоб еще не объявленной функции из контекста.Помимо оптимизации кода планируется добавить типизацию –отступить от парадигмы абсолютно функционального языка.В данной реализации типизация достигается за счёт добавленияпредиката,проверяющегопорождениесвоегопараметразаданнымиконструкторами.
Эта задача ложится на пользователя и сильно увеличиваетпроцесс редукции.Перспективной задачей также является увеличение конструкций языкав данной реализации.345. Использованная литература1. Фальк В.Н. FLOGOL: Язык и система функционально-логическогопрограммирования. М:–МЭИ. -2009.2. FLIDE Система функционально-логическогопрограммирования наязыке S-FLOGOL //Приложение к диссертация Бебчик Ал.М. БебчикАн.М. М:–МЭИ. -2004.3. Дж. Бишоп, Н. Хорспул. C# в кратком изложенииМ:-Бином.Лаборатория знаний.
-20054. Фальк В.Н. Теория направленных отношений и ее приложения // Дисс.докт. техн. наук. М: – МЭИ. -2001.5. ФалькВ.Н.Языкисхемотношений//Формальныемоделипараллельных вычислений. Новосибирск, 1988.6. Бебчик Ал.М., Бебчик Ан.М., Фальк В.Н. Система функциональнологического программирования S-FLOGOL // Девятая Национальнаяконференция по искусственному интеллекту с международнымучастием КИИ-2004 (28 сентября – 2 октября 2004 г., Тверь)7. БебчикАл.М.,БебчикАн.М.,ФалькВ.Н.Инструментальныесредства разработки и отладки программ системы функциональнологического программирования S-FLOGOL // Девятая Национальнаяконференция по искусственномуинтеллектусмеждународнымучастием КИИ-2004 (28 сентября – 2 октября 2004 г., Тверь)35Приложение1.
Описание грамматикиНетерминальные символы начинаются со знака $. Затем следует егоназвание с большой буквы.В левой части от знака «=» находится определяемый нетерминал. Вправой части -список определяющих нетерминальных и терминальныхсимволов, разделённый знаком “_”$Имя=$ЗагБуква_$Строка$Строка=$ЗагБуква_$Строка$Строка=$Цифра_$Строка$Строка=$Буква_$Строка$Строка=$Пусто$Буквы=$Буква$Буквы=$Буква_$Буквы$Число=$Цифра$Число=$Цифра_$Число$Пробел=$Пробелы=$Пробел_$Пробелы$Арность=(_$Число_:_$Число_)$Рекурсия=@$Графич=$Конструктор_$Конец$Графич=$ПрологПредставление_$Конец$Графич=$Сеть_$Конец$Конец=;//ОПИСАНИЕ ФУНКЦИИ, ЗАДАННОЙ СЕТЬЮ$Сеть=$Имя_=_$ГрафичОперанд$Сеть=$Арность_$Имя_=_$ГрафичОперанд$ГрафичОперанд1=$Имя36$ГрафичОперанд1=$Константа$ГрафичОперанд1=$Рекурсия$ГрафичОперанд1=(_$НачалоВСкобках_$ГрафичОперанд_$КонецВСкобках_)$НачалоВСкобках=$Пусто$КонецВСкобках=$Пусто$ГрафичОперанд=$ГрафичОперанд1$ГрафичОперанд=$ГрафичОперанд1_$Операция_$ГрафичОперанд$Константа=-->$Константа=--<$Константа=<-$Константа=>-$Константа=--$Константа=-/$Константа=]$Константа=[$Операция=*$Операция=#//ОПИСАНИЕ КОНСТРУКТОРА$Конструктор=$АрностьКонстр_$Имя$АрностьКонстр=(_+_$Число_+_:_+_$Число_)//ОПИСАНИЕ ФУНКЦИИ, ЗАДАННОЙ ГРАФИЧЕСКИМПРЕДСТАВЛЕНИЕМ$ПрологПредставление=$Имя_=_{_$ПрологВходы_$ПрологВыходы_$ПрологОграничения_}$ПрологПредставление=$Арность_$Имя_=_{_$ПрологВходы_$ПрологВыходы_$ПрологОграничения_}$ПрологВходы=$СписокПараметров$СписокПараметров=$Параметр$СписокПараметров=$Параметр_,_$СписокПараметров$Параметр=$Переменная$Параметр=$ПрологФункция37$Переменная=$Буквы$КонецПрологФункции=$Пусто$ПрологФункция=$Имя_$КонецПрологФункции$ПрологФункция=$Имя_(_$СписокПараметров_)_$КонецПрологФункции$ПрологВыходы=$Пусто$ПрологВыходы=:_$СписокПараметров$ПрологОграничения=$Пусто$ПрологОграничения=?_$ПрологСписокОграничений$ПрологОграничения=?$ПрологСписокОграничений=$ПрологОграничение$ПрологСписокОграничений=$ПрологОграничение_,_$ПрологСписокОграничений$ПрологОграничение=$ПраваяЧасть$ПрологОграничение=$ЛеваяЧасть_=_$ПраваяЧасть$ПраваяЧасть=$ПрологФункция$ПраваяЧасть=$Переменная$ЛеваяЧасть=$ПрологФункция$ЛеваяЧасть=$Переменная$ЛеваяЧасть=[_$СписокПараметров_]2.
Класс для составления функций по списку лексемМетод Аction будет выполняться после завершения разборакаждой строки входного файла.Определив состав списка лексем по некоторым ключевыммоментам,объекта.запускаетсясоответствующаяпроцедурасоздания38static class Saver {static List<string[]> lst = new List<string[]>();public static void Add(string[] s) {lst.Add(s);}public static void Action(){if (lst[0][0] == "$Сеть") {if (lst[1][0] == "$Имя") {List<string[]> tmp = lst.Skip(2).ToList();UserFunction.CreateFunction(lst[1][1], tmp);} else if (lst[1][0] == "$Арность") {List<string[]> tmp = lst.Skip(3).ToList();UserFunction.CreateFunction(lst[2][1], tmp, lst[1][1]);} else {LOGClass.Add("Saver", "Не распознан способ заданияфункции ");}} else if (lst[0][0] == "$Конструктор") {Constructor.Create(lst[1][1], lst[2][1]);} else if (lst[0][0] == "$ПрологПредставление") {if (lst[1][0] == "$Имя") {List<string[]> tmp = lst.Skip(2).ToList();UserFunction.CreateProlog(lst[1][1], tmp);} else if (lst[1][0] == "$Арность") {List<string[]> tmp = lst.Skip(3).ToList();UserFunction.CreateProlog(lst[2][1], tmp, lst[1][1]);} else {LOGClass.Add("Saver", "Не распознан способ задания функции");}}lst.Clear();}}393.
Лексический разбор на основе грамматикиnamespace Parser {public delegate void OnAction(params string[] param);public delegate void OnLog(string classname, string s);public struct PairAssign {internal string Name;internal OnAction Action;public PairAssign(string Name, OnAction Action) {this.Name = Name;this.Action = Action;}}public static class Parser {#region Классыstruct Pair {public OnAction Action;public string[] param;public Pair(OnAction Action, params string[] param) {this.Action =Action;this.param = param;}}class Result {internal string s;internal List<Pair> lst;internal Result(string s, List<Pair> lst) {this.s = s;this.lst = lst;}}40class NTerm { //Нетерминалinternal string Name;internal List<TVertex> def = new List<TVertex>();internal static NTerm Start = null;internal OnAction action = null;static NTerm() {CreateWord();}static void CreateWord() {NTerm res = new NTerm();res.Name = "$Буква";Add(res);for(int i = 97; i <= 122; i++) {TVertex v = new TVertex();TVertex vi = new TVertex();v.edges = new TWEdge((char)i + "", vi);res.def.Add(v);}res = new NTerm();res.Name = "$ЗагБуква";Add(res);for(int i = 65; i < 91; i++) {TVertex v = new TVertex();TVertex vi = new TVertex();v.edges = new TWEdge((char)i + "", vi);res.def.Add(v);}res = new NTerm();res.Name = "$Цифра";Add(res);for(int i = 48; i <= 57; i++) {TVertex v = new TVertex();41TVertex vi = new TVertex();v.edges = new TWEdge((char)i + "", vi);res.def.Add(v);}res = new NTerm();res.Name = "$Пусто";Add(res);res.def.Add(new TVertex());}public override string ToString() {return Name;}}class TEdge { //эпсилон дугаinternal TVertex next; //Указатель на сл вершинуinternal TEdge(TVertex vertex) {next = vertex;}}class TWEdge:TEdge { //Взвешенная дугаpublic string c;public TWEdge(string c, TVertex vertex): base(vertex) {this.c = c;}public override string ToString() {return c + "";}}42class TVertex { //вершина графаinternal TEdge edges = null; //Исходящие дугиinternal NTerm nterm = null; //Указатель на определяющийнетерминалpublic override string ToString() {if(edges == null)return "final";elsereturn "->" + edges;}}#endregionstatic List<Result> Rec(TVertex v, string str) {List<Result> bk = new List<Result>();if(v.nterm != null) {foreach(TVertex def in v.nterm.def)bk = bk.Concat(Rec(def, str)).ToList();if(bk.Count == 0) {return new List<Result>();} elseif(v.nterm.action != null) {for(int i = 0; i < bk.Count; i++) {Pair pair = new Pair(v.nterm.action , v.nterm.Name,str.Substring(0, str.Length - bk[i].s.Length));bk[i].lst.Insert(0,pair);}}} else {bk.Add(new Result(str, new List<Pair>()));}//В bk список всевозможных вариантов//Для каждого вариантаList<Result> result = new List<Result>();if(v.edges == null) {return bk;} else {TWEdge w = v.edges as TWEdge;if(w == null) {43foreach (Result res in bk){List<Result> restmp = Rec(v.edges.next, res.s);foreach (Result rr in restmp)rr.lst = res.lst.Concat(rr.lst).ToList();result = result.Concat(restmp).ToList();}} else {foreach(Result res in bk) {if(res.s.Length >= w.c.Length)if(res.s.Substring(0, w.c.Length) == w.c) {List<Result> restmp = Rec(v.edges.next,res.s.Substring(w.c.Length));foreach (Result rr in restmp)rr.lst = res.lst.Concat(rr.lst).ToList();result = result.Concat(restmp).ToList();}}}return result;}}static NTerm CreateTerm(string name) {NTerm res = new NTerm();res.Name = name;Add(res);return res;}static TVertex CreateForString(TVertex start, string s) {TVertex v = start;TVertex vi = new TVertex();v.edges = new TWEdge(s, vi);v = vi;return v;}static OnLog Log = null;44#region Пабликиpublic static void Create(List<string> lst, string Start, OnLog param =null) {AssignLog(param);Write("Создание автомата по списку правил");for(int i = 0; i < lst.Count; i++) {if (lst[i].Length >= 2) {if (lst[i].Substring(0, 2) == @"//")continue;}string[] arr = lst[i].Split('=');string temp = lst[i].Substring(arr[0].Length+1);NTerm res = Get( p => p.Name == arr[0]);if (res == null)res = CreateTerm(arr[0]);TVertex v = new TVertex();res.def.Add(v);arr = temp.Split('_');for(int j = 0; j < arr.Length; j++) {if(arr[j][0] == '$') {if(v.nterm != null) {TVertex v1 = new TVertex();v1.nterm = Get(p => p.Name == arr[j]);if(v1.nterm == null)v1.nterm = CreateTerm(arr[j]);v.edges = new TEdge(v1);v = v1;} else {v.nterm = Get(p => p.Name == arr[j]);if(v.nterm == null)v.nterm = CreateTerm(arr[j]);}} else {v = CreateForString(v, arr[j]);}}}if (Check())NTerm.Start = Get(p => p.Name == Start);}45public static void AssigEvent(params PairAssign[] input) {foreach(PairAssign p in input) {NTerm nt = Get(q => q.Name == p.Name);if(nt == null)Write(p.Name + " Action not assigned");else {nt.action = p.Action;Write(p.Name + " Action assigned");}}}public static string Parse(string s) {if(NTerm.Start == null)return "Ошибка разбора - не найдено начальное состояниеавтомата";if (s.Length == 0)return "Ошибка разбора - строка пуста";if (s.Length >= 2)if (s.Substring(0, 2) == @"//")return "Разбор - стркоа закомментирована";List<Result> bk = new List<Result>();foreach(TVertex def in NTerm.Start.def)bk = bk.Concat(Rec(def, s)).ToList();bk = bk.Where(p => p.s == "").ToList();if(bk.Count > 1) {return "Ошибка разбора - неоднозначный вывод " + s;} else if(bk.Count == 1) {if(NTerm.Start.action != null) {Pair pair = new Pair(NTerm.Start.action, NTerm.Start.Name,s.Substring(0, s.Length - bk[0].s.Length));bk[0].lst.Insert(0,pair);}for(int i = 0; i < bk[0].lst.Count; i++)bk[0].lst[i].Action(bk[0].lst[i].param);46return "Разбор - завершен удачно";} else {return "Ошибка разбора - не удалось произвести вывод";}}static void AssignLog(OnLog param) {param("Parser", "Установка события");Log = param;}#endregion#region Работа со списком нетерминаловstatic readonly List<NTerm> nterms = new List<NTerm>(); //Списоквсех возможных нетерминаловstatic NTerm Get(int i) {return nterms[i];}static NTerm Get(Func<NTerm,bool> predicate) {return nterms.FirstOrDefault(p => predicate(p));}static bool Check() {bool result = true;foreach(NTerm nt in nterms) {if(nt.def.Count == 0) {Write("No defined " + nt.Name);result = false;}}return result;}static void Add(NTerm n) {Write("Creating " + n.Name);nterms.Add(n);}#endregion47static void Write(string s) {if (Log != null) {Log("Parser", s);}}}}4.