Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа), страница 3

Результатом проверки будет список возможных выводов, а точнеесписок остатков от входной строки, первые части которых порадились22конструкциейграмматики.Затемпроверяетсяналичиеребер.Еслиисходящего ребра нет, то этот же список – результат работы функции. Еслиребро есть, то для каждой строки из списка возможных делается переход кследующей вершине.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) {...return "Разбор - завершен удачно";} else {return "Ошибка разбора - не удалось произвестивывод";}После запуска этой процедуры для начального нетерминала иначальной входной строки будет получен список остатков входной строки,которые не прошли проверку.

Из этого списка выбираются результаты, укоторых строка остатка пуста. Если таких строк нет, то входная строка недопускается грамматикой.Если такая строка одна, то входная строкадопускается грамматикой. Если результатов большеодного, то этосвидетельствует о неоднозначном выводе.Таким образом, если запускать эту процедурудля списка синструкциями языка (определениями направленных отношений)lst.Select(p => Parser.Parser.Parse(p)).ToList();получится список с результатами проверки поражения каждой строкиисходного списка заданной грамматикой.Если же до проверки описать реакцию на определенный нетерминал,Parser.Parser.AssigEvent(new PairAssign("$Константа", p => Saver.Add(p)),23new PairAssign("$Конструктор", p => Saver.Add(p)),new PairAssign("$Сеть", p => Saver.Add(p)),new PairAssign("$Конец", p => Saver.Action()),new PairAssign("$АрностьКонстр", p => Saver.Add(p)),new PairAssign("$Арность", p => Saver.Add(p)),new PairAssign("$Имя", p => Saver.Add(p)),new PairAssign("$Рекурсия", p => Saver.Add(p)),new PairAssign("$КонецВСкобках", p => Saver.Add(p)),new PairAssign("$НачалоВСкобках", p => Saver.Add(p)),new PairAssign("$Операция", p => Saver.Add(p)),new PairAssign("$ПрологПредставление", p => Saver.Add(p)),new PairAssign("$ПрологВходы", p => Saver.Add(p)),new PairAssign("$ПрологВыходы", p => Saver.Add(p)),new PairAssign("$ПрологОграничения", p => Saver.Add(p)),new PairAssign("$ПрологОграничение", p => Saver.Add(p)),new PairAssign("$ПрологФункция", p => Saver.Add(p)),new PairAssign("$ЛеваяЧасть", p => Saver.Add(p)),new PairAssign("$ПраваяЧасть", p => Saver.Add(p)),new PairAssign("$Переменная", p => Saver.Add(p)),new PairAssign("$КонецПрологФункции", p => Saver.Add(p)));То по этим данным можно будет проводить уже лексический анализвходного файла.Описание класса Saver есть в приложении.243.2.

Описание объектов программы.Посмотрим на диаграмму классов (рис 3.1).Рис 3.1 Диаграмма классов проектаСредиобъектовязыкаестьфункции,которыеделятсянаКонструкторы, Константы, и пользовательские функции. Также есть деревья– параллельная и последовательная композиции.Весь метод вычисление схем направленных отношений основан награфическом представлении направленных отношений, соответственно укаждого объекта программы есть это представление.

Информация о немсодержится в классе Base.Любая функция имеет имя, будь токонструктор(имя конструктора), константа (определенная одним из имен ---,-->, >-- и т.д.) или же пользовательская функция.Конструктор и константа очень похожи по своей сути, это видно по ихкоду, который находится в приложении. Пользовательская функциясодержит список своих определений. Каждое определение принимает одно из2х значений – либо дерево, определяющее алгебраическое представлениесхемы направленного отношения, либо графическое представление.Дерево же содержит список своих операндов, опять же, каждый изкоторых может быть либо деревом, либо указателем на функцию. Всефункции хранятся в глобальном массиве функций.25Дерево последовательной и параллельной композиций отличаютсялишь агрегатной функцией свертки своих операндов, которая нужна длясоставления графического представления.По своей сути все деревья являются промежуточными объектами впроцессе создания графическогополностьюопределенныепредставления.

К концу разбора всефункциинебудутиметьграфическогопредставления, так как оно оказывается ненужным в силу отсутствия впрограмме графического редактора d-отношений.Представление в виде дерева нужно для обеспечения более свободногометода написания кода – можно использовать ранее неопределенныеотношения, а затем их доопределить.3.3.Процесссозданияпользовательскойфункцииизалгебраического представленияСогласно заданным правилам реакции на нетерминалы в списке лексембудет последовательность из операций и операндов, и еще некотораявспомогательнаяинформация(которая,вообщеговоря,избыточная).Последовательно проходя по списку лексем, формируется дерево.

Причём,если в процессе формирования дерева встречается необъявленная функция,под нее тут же резервируется место в памяти. Как только дерево оказываетсяполностью построенным, начинается процесс его свертки – созданияграфическогопредставления.Каждоеподдеревозаменяетсясвоимграфическим представлением. Если в дереве есть неопределенные функции(функции, у которых не определена арность), то содержащее их поддеревопропускается. Это даёт возможность при последующем определениинедостающей функции быстро пересчитать арность зависимой от неефункции. В процессе пересчёта арности повторяется попытка построенияграфческого представления.263.4.ПроцесссозданияграфиескогопредставленияизалгебраическогоПроцесссостоитизпоследовательногопримененияоперацийсоставления графического представления для каждого поддерева заданногодерева. По умолчанию каждая функция и конструктор имеют представлениеИмяФункции = { 1, 2, … ,: E1, E2, … EF}Внутренне представление графической формы описывается в классеPrologViewpublic class PrologView {public List<Def> relations = new List<Def>();int[] input = null;int[] output = null;string str;…}Input, output – списки номеров переменных – входов и выходовфункции, которые, в процессе вывода, преобразовываются в именапеременных.Relations – список зависимостей.public class Def {public Function name;public List<int> input;// = new List<int>();public List<int> output;// = new List<int>();...}Каждая зависимость определяет имя функции, или конструктора, откоторой зависит, а также номера переменных, являющихся входами ивыходами(input, output соответственно).Процесссоставленияграфическогопредставлениядлядеревапараллельной композиции:public static PrologView operator +(PrologView op1, PrologViewop2) {if (op1 == null)return null;if (op2 == null)27return 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 = Invers(op2, inv);if (op2 == null)return null;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();return PrologView.Create(input, output, defs);}Сначала строится список занятых переменных для первого операнда.Затем строится список замен для второго операнда, чтобы имена переменныхне пересекались.

Результатом операции будет графическое представление,входы, выходы и зависимости которого будут объединением списковсоответственно входов, выходов и зависимостей первого операнда и второго.Построение графического представления для дерева последовательнойкомпозиции аналогично с той лишь разницей, что входы результата будутвходами первого операнда, а выходы - выходами второго операнда. Такжедобавится шаг изменения первого операнда согласно входам второгооперанда.Этот процесс хорошо виден на примере.Test = (---# [ # [) * (]#]#---)Рис 3.2 Схематическое представление функции Test28После первого прохода построится список замен, затем он упрощается.G→G→E→GE→H→EH→9→H9→I→9I→и эти замены применяются операндамРис 3.3 Результат замены и построение графического представленияРезультатом будет графическое представление HJ4 = { , }ПроцесспреобразованиясписказаменописываетсявклассеInversion3.5.

Создание графического представления и его проверкаВся идея принципа сетевой резолюции реализована именно впроцедуре создания графического представления. После построения списказависимостей происходит процесс его оптимизации. Он основан на свойствахфункциональности и обратной функциональности конструкторов – проверяявсе зависимости с одинаковыми именами, строится список замен, а затем этизамены применяются к представлению. Вторым шагом используетсясвойство ортогональности конструкторов. Оно реализовано в виде проверкипредставления. Если представление не прошло проверку, то оно удаляется изсписка определений функции.29По запросу пользователя может проходить процесс подстановки,реализующий процесс вычислений схем направленнх отношений.Процесс β-редукции очень похож на операцию последовательнойкомпозиции. Это достигается за счёт использования сетевой резолюции вграфическом представления.Процесс вычисления основан на последовательной подстановкекаждого из определений каждой функции в зависимую от них.Пример вычисления(рис 3.4): Требуется сложить два числа.Рис 3.4 пример вычисления НО4.