Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа), страница 6
Описание файла
PDF-файл из архива "Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа)", который расположен в категории "". Всё это находится в предмете "дипломы и вкр" из 8 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "выпускные работы и поступление в магистратуру" в общих файлах.
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
Класс для графического представленияpublic class PrologView {public List<Def> relations = new List<Def>();int[] input = null;int[] output = null;string str;List<Word> words = new List<Word>(); //Списоквсевозможных буквList<FuncGraphPoint> functions = newList<FuncGraphPoint>(); //Список всевозможных функцийPrologView() {}public PrologView(IEnumerable<int> input,IEnumerable<int> output) {this.input = input.ToArray();this.output = output.ToArray();62str = "{";if (this.input.Length > 0)str += input.Select(p =>p.ToChar().ToString()).Aggregate((x, y) => x + ", " + y);if (this.output.Length > 0) {str += ":";str += output.Select(p =>p.ToChar().ToString()).Aggregate((x, y) => x + ", " + y);}str += "}";}PrologView(PrologView p1) {this.input = p1.input.ToArray();this.output = p1.output.ToArray();foreach( Def f in p1.relations) {this.relations.Add(new Def(f));}}void AddFunction(List<int> paraminput, List<int>paramout, Def def) {;// param) {//, string param = null) {FuncGraphPoint New = new FuncGraphPoint() {def = def };functions.Add(New);for (int j = 0; j < paraminput.Count; j++) {Word w = words.FirstOrDefault(p =>p.name == paraminput[j]);if (w == null) {w = new Word() { name =paraminput[j] };words.Add(w);}w.input.Add(New);New.child.Add(w);}for (int j = 0; j < paramout.Count; j++) {Word w = words.FirstOrDefault(p =>p.name == paramout[j]);63if (w == null) {w = new Word() { name = paramout[j]};words.Add(w);}w.output.Add(New);New.parent.Add(w);}}void AgregateFunction() {foreach (Word word in words) {if (word.output.Count == 1) {if (word.input.Count == 1) {if (word.input[0] !=word.output[0]) {if(word.output[0].parent.Count == 1) {int ind =word.input[0].child.IndexOf(word);word.output[0].parent.Clear();word.input[0].child[ind]= word.output[0];functions.Remove(word.output[0]);}}} else if (word.input.Count == 0) {word.name = 0;}} else if (word.output.Count == 2) {if (word.input.Count == 0) {if (word.output[0].parent.Count== 1) {int ind =word.output[1].parent.IndexOf(word);word.output[1].parent[ind] =word.output[0];word.output[0].parent.Clear();64functions.Remove(word.output[0]);} else if(word.output[1].parent.Count == 1) {int ind =word.output[0].parent.IndexOf(word);word.output[0].parent[ind] =word.output[1];word.output[1].parent.Clear();functions.Remove(word.output[1]);}}} else if (word.output.Count +word.input.Count <= 1) {word.name = 0;}}functions =functions.Where<FuncGraphPoint>(p => {if(p.def == null)return true;if(p.def.name is Constructor) {if (p.parent.Count == 0)return true;if (p.parent.All(q => q is Word)) {List<Word> tmp =p.parent.Cast<Word>().ToList();if (tmp.All(q => q.name == 0)) {return false;} else {return true;}} else {return true;}} else {return true;65}}).ToList();}void CreateString() {List<Graph> input = functions[0].child;List<Graph> output = functions[1].child;functions = functions.Skip(2).ToList();str = "{";if (input.Count > 0)str += input.Select(p =>p.ToString()).Aggregate((x, y) => x + ", " + y);if (output.Count > 0) {str += ":";str += output.Select(p =>p.ToString()).Aggregate((x, y) => x + ", " + y);}if (functions.Count > 0) {str += "?";str += functions.Select(p =>p.ToString()).Aggregate((x, y) => x + ", " + y);}str += "}";}void CheckOneConstructor() {relations = relations.Distinct().ToList();if(relations.Count == 0)return;IEnumerable<IGrouping<string, Def>> lst =relations.Where(p => p.name is Constructor).GroupBy<Def,string>(p => p.name.Name);Inversion inv = new Inversion();foreach (IGrouping<string, Def> ind1 in lst){//Внутри одного конструктораList<Def> ind = ind1.ToList();for (int i = 0; i < ind.Count(); i++) {66for (int j = i + 1; j < ind.Count();j++) {if(RelationFunction.Equals(ind[i].input, ind[j].input))for (int k = 0; k <ind[i].output.Count; k++)inv.Add(newPair(ind[j].output[k], ind[i].output[k]));if(RelationFunction.Equals(ind[i].output, ind[j].output))for (int k = 0; k <ind[i].input.Count; k++)inv.Add(newPair(ind[j].input[k], ind[i].input[k]));}}}if (inv.Return().Count != 0)Inverse(inv.Return());}bool CheckManyConstructors() {relations = relations.Distinct().ToList();if (relations.Count == 0)return true;IEnumerable<IGrouping<string, Def>> lst =relations.Where(p => p.name is Constructor).GroupBy<Def,string>(p => p.name.Name);if (lst.Count() <= 1)return true;foreach (IGrouping<string, Def> group inlst) {List<Def> temp = lst.Where(j => j.Key !=group.Key).Select(q => q as IEnumerable<Def>).Aggregate((x,y) => x.Concat(y)).ToList();foreach( Def def in group)for (int k = 0; k < temp.Count; k++)if(RelationFunction.Equals(def.output, temp[k].output))return false;}67return true;}bool Check() {CheckOneConstructor();return CheckManyConstructors();}public Pair Arity {get {return new Pair(input.Length,output.Length);}}public override string ToString() {return str;}public string GetTypeFunction() {return "Prolog Function";}static List<int> CreateListOfWord(PrologViewop1) {IEnumerable<int> lockedWord;if (op1.relations.Count > 0)lockedWord = op1.relations.Select(p =>p.input.Union(p.output)).Aggregate((x, y) => x.Union(y));elselockedWord = new List<int>();lockedWord =lockedWord.Union(op1.input).Union(op1.output);lockedWord = lockedWord.Distinct();return lockedWord.ToList();}void Inverse(List<Pair> inv) {68Func<int, int> lol = i => {Pair inve = inv.FirstOrDefault(p =>p.input == i);return inve == null ? i : inve.output;};relations = relations.Select<Def, Def>(d =>{Def New = new Def();New.name = d.name;New.input =d.input.Select(lol).ToList();New.output =d.output.Select(lol).ToList();return New;}).ToList();input = input.Select(lol).ToArray();output = output.Select(lol).ToArray();}public static PrologView operator +(PrologViewop1, PrologView op2) {if (op1 == null)return null;if (op2 == null)return null;List<int> lockedWord =CreateListOfWord(op1);List<Pair> inv = new List<Pair>();foreach (int i in CreateListOfWord(op2))inv.Add(new Pair(i,lockedWord.GetFree()));op2.Inverse(inv);IEnumerable<int> input =op1.input.Concat(op2.input);IEnumerable<int> output =op1.output.Concat(op2.output);List<Def> defs =op1.relations.Concat(op2.relations).ToList();69return PrologView.Create(input, output,defs);}public static PrologView operator * (PrologViewop1, PrologView op2) {if (op1 == null)return null;if (op2 == null)return null;if (op1.Arity.output != op2.Arity.input)throw new Exception("Арности несовпадают " + op1 + "*" + op2 );List<int> lockedWord =CreateListOfWord(op1);List<Pair> invop2 = new List<Pair>();foreach (int i in CreateListOfWord(op2))invop2.Add(new Pair(i,lockedWord.GetFree()));//Составлен список заменif (invop2.Count > 0)op2.Inverse(invop2);//На этом этапе переменные у op2 и op1 непересекаются.Inversion inv = new Inversion();//Далее надо делать заменыfor (int i = 0; i < op1.output.Length; i++)if (inv.Return().Exists(p => p.input ==op2.input[i]))inv.Add(new Pair(op1.output[i],op2.input[i]));elseinv.Add(new Pair(op2.input[i],op1.output[i]));inv.Check();if(inv.Return().Count > 0) {op2.Inverse(inv.Return());op1.Inverse(inv.Return());}IEnumerable<int> input = op1.input;70IEnumerable<int> output = op2.output;List<Def> defs =op1.relations.Concat(op2.relations).ToList();return PrologView.Create(input, output,defs);}public static PrologView Create(IEnumerable<int>input, IEnumerable<int> output, List<Def> defs){PrologView result = new PrologView();result.input = input.ToArray();result.output = output.ToArray();result.relations = defs;if (!result.Check())return null;result.AddFunction(result.input.ToList(),new List<int>(), null);//"$input");result.AddFunction(result.output.ToList(),new List<int>(), null);// "$output");foreach (Def def in result.relations) {result.AddFunction(def.input,def.output, def);}result.AgregateFunction();result.CreateString();return result;}public static PrologView Inject(PrologView p1,int ind, PrologView inj) {if (p1 == null)return null;if (inj == null)return null;if (ind < 0)return null;if (ind >= p1.relations.Count)return null;Def relat = p1.relations[ind];if (relat.Arity != inj.Arity)71return null;LOGClass.Add("PrologView", "Подстановка в "+ p1 + " функции " + inj);PrologView op1 = new PrologView(p1);PrologView op2 = new PrologView(inj);op1.relations.Remove(relat);List<int> lockedWord = CreateListOfWord(op1);List<Pair> invop2 = new List<Pair>();foreach (int i in CreateListOfWord(op2))invop2.Add(new Pair(i,lockedWord.GetFree()));//Составлен список заменif(invop2.Count > 0)op2.Inverse(invop2);//На этом этапе переменные у op2 и op1 непересекаются.Inversion inv = new Inversion();//Далее надо делать заменыfor (int i = 0; i < relat.input.Count; i++)if (inv.Return().Exists(p => p.input ==op2.input[i]))inv.Add(new Pair(relat.input[i],op2.input[i]));elseinv.Add(new Pair(op2.input[i],relat.input[i]));for(int i = 0; i < relat.output.Count; i++)if(inv.Return().Exists(p => p.input ==op2.output[i]))inv.Add(new Pair(relat.output[i],op2.output[i]));elseinv.Add(new Pair(op2.output[i],relat.output[i]));inv.Check();if(inv.Return().Count > 0) {op2.Inverse(inv.Return());op1.Inverse(inv.Return());}72IEnumerable<int> input = op1.input;IEnumerable<int> output = op1.output;List<Def> defs =op1.relations.Concat(op2.relations).ToList();return PrologView.Create(input, output,defs);}6.
Создание списка зависимостей из списка лексемclass PrologWiewCreator {class WordNumer {class Pair {public string s;public Word w;}List<Pair> words = new List<Pair>();/// <summary>/// Функция возвращает первый свободныйномер/// </summary>/// <returns></returns>int GetNum() {List<int> temp = words.Select(p =>p.w.name).ToList();int i = 1;while (temp.Exists(p => p == i))i++;return i;}public Word New() {Pair result = new Pair() { w = newWord() { name = GetNum() } };words.Add(result);return result.w;}public Word Add(string s) {73Pair result = words.FirstOrDefault(p =>p.s == s);if (result == null) {result = new Pair() { s = s, w = newWord() { name = GetNum() } };words.Add(result);}return result.w;}public Word Get(Func<string, bool>predicate) {Pair p = words.FirstOrDefault(q =>predicate(q.s));if (p == null)return null;elsereturn p.w;}}WordNumer words = new WordNumer();List<FuncGraph> relations = newList<FuncGraph>();List<Graph> npt = new List<Graph>();List<Graph> otpt = new List<Graph>();void Check(List<Graph> npt) {for (int i = 0; i < npt.Count; i++) {if (npt[i] is FuncGraph) {relations.Add(npt[i] as FuncGraph);Word w = words.New();(npt[i] as FuncGraph).parent.Add(w);npt[i] = w;}}}74List<Graph> CreateInput(List<string[]> token) {List<Graph> result = new List<Graph>();List<string[]> forin = new List<string[]>();int num = 0;foreach (string[] lst in token) {if (lst[0] == "$ПрологФункция") {if (num > 0) {forin.Add(lst);}num++;} else if (lst[0] =="$КонецПрологФункции") {num--;if (num == 0) {FuncGraph New = new FuncGraph(){ name = forin[0][1] };New.child =CreateInput(forin.Skip(1).ToList());result.Add(New);forin.Clear();} else {forin.Add(lst);}} else {if (num > 0) {forin.Add(lst);} else {if (lst[0] == "$Переменная") {Word word = words.Get(p => p== lst[1]);if (word == null)word =words.Add(lst[1]);//word.input.Add(result);result.Add(word);}}75}}return result;}/// <summary>///Составление предиката(без возврзначения) по списку лексем/// </summary>/// <param name="token">Список лексем</param>/// <returns>Граф функция</returns>FuncGraph CreateOneRelation(List<string[]>token) {int i = 0;List<string[]> left = null;List<string[]> right = null;if (token[i][0] == "$ЛеваяЧасть") {left = CreateList(token, ref i);}if (token[i][0] == "$ПраваяЧасть") {right = CreateList(token, ref i);}if (right == null)throw new Exception("Ошибка парсингаправой части");if (right.Count < 2)throw new Exception("Ошибка парсингаправой части");FuncGraph R = null;if (right[0][0] == "$ПрологФункция") {if (right[1][0] == "$Имя") {string Name = right[1][1];right = right.Skip(2).ToList();R = new FuncGraph() { name = Name };(R as FuncGraph).child =CreateInput(right);} else {76throw new Exception("Ожидаетсяимя");}} else {throw new Exception("Ожидается праваячасть оперделения");}if (R == null)throw new Exception("Ошибкараспозначания праой части опредеолния");if (left != null) {if (left.Count == 0)throw new Exception("Ошибка парсингалевой части");R.parent = CreateInput(left);}return R;}void CreateStructure(List<string[]> token) {int i = 0;if (token[i][0] == "$ПрологВходы") {List<string[]> listInput =CreateList(token, ref i);npt = CreateInput(listInput);}if (token[i][0] == "$ПрологВыходы") {List<string[]> listOutput =CreateList(token, ref i);otpt = CreateInput(listOutput);}if (token[i][0] == "$ПрологОграничения") {if (i >= token.Count) return;// result;List<string[]> temp = newList<string[]>();for(i+=1; i < token.Count; i++) {if (token[i][0] =="$ПрологОграничение") {if (temp.Count > 0)77relations.Add(CreateOneRelation(temp));temp.Clear();} else {temp.Add(token[i]);}}if (temp.Count > 0) {relations.Add(CreateOneRelation(temp));}}}public PrologView CreatePrologView(UserFunctionname, List<string[]> token) {CreateStructure(token);//На этот момент уже потеряли именапеременныхCheck(npt);Check(otpt);for (int i = 0; i < relations.Count; i++) {FuncGraph relat = relations[i];Check(relat.child);Check(relat.parent);}//На этот момент уже нет вложенийList<Def> defs = relations.Select<FuncGraph,Def>(p => {Def New = new Def();New.input =p.child.Cast<Word>().Select(q => q.name).ToList();New.output =p.parent.Cast<Word>().Select(q => q.name).ToList();int ind = Function.Functions.FindIndex(q=> q.Name == p.name);Pair Arity = new Pair(p.child.Count,p.parent.Count);Function f;78if (ind == -1) {//Если такой функции нет, то её надосоздать.f = new UserFunction(p.name);} else {f = ind.GetFunction();}//Если такая функция есть, то надопопытаться проверить арность.if (f.AssignArity(newPair(New.input.Count, New.output.Count))) {New.name = f;} else {return new Def();}return New;}).ToList();if (defs.Exists(p => p == default(Def)))return null;PrologView result = PrologView.Create(npt.Cast<Word>().Select(p => p.name),otpt.Cast<Word>().Select(p => p.name),defs);return result;}static List<string[]> CreateList(List<string[]>token, ref int i) {List<string[]> result = newList<string[]>();for (i++; i < token.Count; i++)switch (token[i][0]) {case "$ПрологФункция":case "$Параметр":case "$Переменная":case "$Имя":case "$Рекурсия":79case "$КонецПрологФункции":result.Add(token[i]);break;default:goto LabelInputOk;}LabelInputOk:return result;}}7.