Компиляторы РГР. Компиляторы_РГР. Курсовая работа по дисциплине Теория формальных языков и компиляторов
Скачать 183.25 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра Вычислительной техники Курсовая работа по дисциплине «Теория формальных языков и компиляторов»
Новосибирск 20 Оглавление1 Цель работы 3 2 Задание на работу 3 3 Описание заданного варианта языка 3 4 Тестовая программа 5 5 Создание лексики заданного учебного языка 6 6 Создание грамматики заданного учебного языка 6 6.1 Расширение синтаксического анализатора 10 7 Интерпретатор учебного языка 11 Заключение 12 Приложения 13 1 Цель работыПрактическое применение теоретических основ проектирования трансляторов с языков программирования; освоение средств автоматизации построения трансляторов; разработка элементов транслятора для учебного языка. 2 Задание на работу1. Описать лексику, синтаксис и семантику заданного варианта языка. Написать несколько простых тестовых программ, содержащих все заданные элементы и управляющие конструкции языка. Вручную выполнить интерпретацию программы. Эти программы использовать впоследствии для проверки элементов разрабатываемого транслятора. 2. Разработать систему регулярных выражений, определяющую лексику заданного варианта языка. Используя пакет Вебтранслаб, построить автоматную реализацию лексического акцептора на выбранном инструментальном языке. Добиться работоспособности акцептора. 3. Разработать совокупность действий, т.е. расширение системы регулярных выражений, реализующую: - поиск в таблицах идентификаторов / констант и пополнение таблиц; - доформирование лексем, и построить лексический анализатор. Убедиться в правильности его работы. 4. Разработать формальную грамматику класса LL(1), определяющую синтаксис заданного языка. Используя пакет Вебтранслаб, построить какую-либо автоматную реализацию нисходящего синтаксического акцептора, добиться его работоспособности. Или: 5. Разработать формальную грамматику класса не выше, чем LALR(1). Используя пакет Вебтранслаб, построить автоматную реализацию восходящего синтаксического акцептора, добиться его работоспособности. 6. Разработать расширение построенного синтаксического акцептора для преобразования входной последовательности лексем в постфиксную форму записи или в абстрактное синтаксическое дерево. 7. Разработать семантический анализатор и преобразователь ПФЗ в псевдокод. Формат псевдокода определяется последней цифрой варианта задания. 8. Разработать интерпретатор псевдокода. 3 Описание заданного варианта языкаЛексика, синтаксис и семантика учебного языка основаны на языках типа Java и C#. Любые конструкции, не оговоренные явно в задании, были определены самостоятельно. Ключевые слова (в задании выделены жирным шрифтом, например: long, when, case, …) должны быть нечувствительны к регистру. Обозначения: [...] – необязательная часть … – часть, повторяющаяся произвольное количество раз < > – описание конструкции: <Б>|<Ц>|<пБ>|<пЦ>|<пБЦ> – одна буква | одна цифра | непустая последовательность букв | непустая последовательность цифр | возможно пустая последовательность букв и/или цифр <И> – Имя переменной / объекта; <К> – Константа; <В> – произвольное Выражение; <ЛВ> – Логическое Выражение; <ОБ> – Оператор или Блок; <О> – одиночный оператор; <ОП> – оператор присваивания; <Код> – код операции; <Оп> – имя операнда; <Рез> – имя результата Расшифровка цифр варианта задания: II.1 Идентификаторы и константы
II.2 Объявления примитивных типов (целое, вещественное, символьное):
II.3 Объявления объектов
II.4 Оператор присваивания:
II.5 Условный оператор:
II.6 Оператор цикла:
II.7 Оператор переключателя
II.8 Вид псевдокода
4 Тестовая программаentity a_a { unsigned b_a; let b_a = 2*(1+2); when(b_a==6) then { let b_a=3; } else { let b_a=2; } when(b_a>3) then { let b_a=4; } else let b_a=5; } } 5 Создание лексики заданного учебного языкаИсходя из варианта на курсовую работу, были написаны следующие правила лексики:
6 Создание грамматики заданного учебного языкаПравильная программа на заданном языке представляет собой класс, содержащий условные блоки, в которых выполняются арифметические операции с переменными. Объявление класса начинается с ключевого слова entity, за которым следует имя класса (идентификатор). Далее между словами «{« и «}» описывается тело класса. Объявление одного набора переменных (полей) начинается с его типа, за которым следует идентификатор переменной. Так же при объявлении переменной можно задать ей значение. Исходя из варианта на курсовую работу, была разработана формальная грамматика, принадлежащая к классу LL(1), на основании которой был построен нисходящий синтаксический анализатор (шаблон lexAsGraphSyntAsRD). Текст грамматики приведен в таблице 2. Таблица 2. Правила грамматики с использованием расширения синтаксического анализатора
6.1 Расширение синтаксического анализатораРасширение синтаксического анализатора подразделяется на четыре основные составляющие: Формирование постфиксной записи Преобразование постфиксной записи в набор пентад Интерпретация Для формирования постфиксной записи (далее ПФЗ) разработано расширение. Вызовы функций производятся при синтаксическом разборе. Класс, формирующий ПФЗ, добавляет операнды и операции в стек, а затем извлекает в необходимом порядке. Основной подход при формировании ПФЗ заключается в том, что при чтении той или иной синтаксической конструкции, нужно определить, какие действия должны выполняться при ее обработке, выявляется выполняемая операция, определяются ее операнды и записываются в постфиксной форме (сначала идут операнды, затем операция). Псевдокод формируется посредством последовательного чтения лексем из ПФЗ. Для каждой операции строится соответствующее правило формирования пентады. Полный код расширения приведен в Приложении А. Правила построения пентад: rulesInit: function() { //Наборы правил (команда, первый аргумент, второй аргумент, //режим записи результата) //где 1- первый аргумент, 2 – второй, -1 – null this.ruleStack = new RulesSet(); //Открытие блока объекта (ent,entityName,null,null) this.ruleStack.addRule("entity","ent",1,-1); //Закртыие блока объекта (entitye,null,null,null) this.ruleStack.addRule("entityend","ente",0,-1); //Объявление целочисленной переменной (unsig,varName,null,null) this.ruleStack.addRule("unsigned","uns",1,-1); //Объявление целочисленной переменной, которой будет присвоено значение //(unsig0,value,varName,second) this.ruleStack.addRule("unsigned0","uns0",2,2); //Объявление переменной с плавающей точкой (num,varName,null,null) this.ruleStack.addRule("number","num",1,-1); //Объявление переменной с плавающей точкой, которой будет присвоено значение //(num0,value,varName,second) this.ruleStack.addRule("number0","num0",2,2); //Объявление строки (sig,varName,null,null) this.ruleStack.addRule("sign","sign",1,-1); //Объявление строки, которой будет присвоено значение //(sig0,value,varName,second) this.ruleStack.addRule("sign0","sign0",2,2); //Присвоение значение переменной (asg,value,varName,first) this.ruleStack.addRule("assign","asgn",2,2); //Сравнение "равно" (equ,value1,value2,push) this.ruleStack.addRule("==","equ",2,0); //Сравнение "больше" (mor,value1,value2,push) this.ruleStack.addRule(">","mor",2,0); //Сравнение "меньше" (les,value1,value2,push) this.ruleStack.addRule("<","les",2,0); //Сравнение "больше либо равно" (morq,value1,value2,push) this.ruleStack.addRule(">=","morq",2,0); //Сравнение "меньше либо равно" (lesq,value1,value2,push) this.ruleStack.addRule("<=","lesq",2,0); //Переход по метке (jmp,label,null,null) this.ruleStack.addRule("Jmp","jmp",1,-1); //Переход по метке, если значение = 0 (jmpf,label,value,null) this.ruleStack.addRule("JmpF","jmpf",1,-1); //Если value != нужному значению - возвращается 0 (?,value,null,push) this.ruleStack.addRule("?","case",1,0); //Операция сложения (plus,value1,value2,push) this.ruleStack.addRule("+","plus",2,0); //Операция вычитания (mns,value1,value2,push) this.ruleStack.addRule("-","mns",2,0); //Операция умножения (mltp,value1,value2,push) this.ruleStack.addRule("*","mltp",2,0); //Операция деления (div,value1,value2,push) this.ruleStack.addRule("/","div",2,0); //Начало переключателя (with,value1,null,push) this.ruleStack.addRule("with","with",1,0); //Закрытие блока переключателя (withe,null,null,null) this.ruleStack.addRule("withend","withe",0,-1); } 7 Интерпретатор учебного языкаВ ходе работы был разработан интерпретатор учебного языка. Код языка транслируется. В итоге трансляции будет получен псевдокод из пентад, этот псевдокод подается на обработку интерпретатора, который в зависимости от кода операции будет выполнять различные действия с аргументами. Результат каждой операции может иметь три исхода: быть записанным в стек, быть записанным в первый аргумент, быть записанным во второй аргумент. Каждое действие записывается в журнал. В результате выполнения выводятся полученные значения для каждой переменной. П ример: ЗаключениеВ ходе выполнения курсовой работы, были получены навыки практического применение теоретических основ проектирования трансляторов и интерпритаторов с языками программирования. Были освоены средства автоматизации построения трансляторов, а также разработаны элементы транслятора для учебного языка. Помимо этого, были получены знания о принципах работы трансляторов, были получены навыки разработки отдельных частей транслятора – лексического анализатора, синтаксического анализатора семантического анализатора, интерпретатора, принципы формирования и использования ими информационных таблиц. Была разработана система лексических правил учебного языка, представленных набором регулярных выражений. Была разработана формальная грамматика класса LL(1), описывающая синтаксис учебного языка. На базе данной грамматики был построен нисходящий синтаксический анализатор, представленный конечным автоматом с одним состоянием и стековой памятью. Синтаксический анализатор был доделан до формирователя ПФЗ транслируемой программы, который в последующем формирует из ПФЗ в набор пентад. Был разработан интерпретатор учебного языка, интерпретирующий псевдокод пентад, полученный при обработке кода транслятором. ПриложенияПриложение А var stack = []; var tmpVal = []; var doCnt=0, ifCnt=0, caseCnt=0, switchCnt=0; function TmpInfo() { this.tmpVal = []; }; TmpInfo.prototype = { in: function(a){ this.tmpVal.push(a); }, out: function(){ return this.tmpVal.pop(); }, get: function(){ return this.tmpVal[this.tmpVal.length-1]; }, typeCheck: function(){ var check = this.get(); if (check == "exp") {this.out(); return this.get()+"0";} else return this.get(); } }; function TraceInfo(){ this.history = []; }; TraceInfo.prototype = { put: function(a,b){ this.history.push(b); }, getAll: function(){ var r = ""; for(var i = 0; i < this.history.length; i++) r += " " + this.history[i]; return r; }, clear: function(){ this.history = []; } }; var tracer = new TraceInfo(); var tmpStack = new TmpInfo(); function LangTrans(stack) { this.reset(); this.stackSet(stack); this.rulesInit(); }; LangTrans.prototype = { getWord: function(){ return this.startStack.shift(); }, isLabel: function (word) { return (word.substr(word.length - 1)==":")? true : false; }, getCleanLabel: function (word) { return word.substr(0,word.length-1); }, operateWord: function (word){ if (!this.isLabel(word)) { var tmpRule = this.ruleStack.findRule(word); if (tmpRule!=null) { if (this.label!="") this.returnString+=this.label+" "; else this.returnString+="null "; this.returnString+=tmpRule.finalName; for (var i=0;i<2;++i) { if (i else this.returnString+=" null"; } switch (tmpRule.varMode) { case 0: this.commandStack.push("^get"); this.returnString+=" push\n"; break; case 1: this.returnString+=" first\n"; break; case 2: this.returnString+=" second\n"; break; case -1: this.returnString+=" null\n" } ++this.lineCount; this.label=""; } else this.commandStack.push(word); } else this.label=this.getCleanLabel(word); }, stackCompute: function() { while (this.startStack.length>0) this.operateWord(this.getWord()); return this.returnString; }, reset: function() { this.startStack = []; this.commandStack = []; this.returnString=""; this.lineCount = 1; this.label = ""; }, stackSet: function(stack) { this.startStack = stack; }, rulesInit: function() { //Наборы правил (команда, первый аргумент, второй аргумент, //режим записи результата) this.ruleStack = new RulesSet(); //Открытие блока объекта (ent,entityName,null,null) this.ruleStack.addRule("entity","ent",1,-1); //Закртыие блока объекта (entitye,null,null,null) this.ruleStack.addRule("entityend","ente",0,-1); //Объявление целочисленной переменной (unsig,varName,null,null) this.ruleStack.addRule("unsigned","uns",1,-1); //Объявление целочисленной переменной, которой будет присвоено значение //(unsig0,value,varName,second) this.ruleStack.addRule("unsigned0","uns0",2,2); //Объявление переменной с плавающей точкой (num,varName,null,null) this.ruleStack.addRule("number","num",1,-1); //Объявление переменной с плавающей точкой, которой будет присвоено значение //(num0,value,varName,second) this.ruleStack.addRule("number0","num0",2,2); //Объявление строки (sig,varName,null,null) this.ruleStack.addRule("sign","sign",1,-1); //Объявление строки, которой будет присвоено значение //(sig0,value,varName,second) this.ruleStack.addRule("sign0","sign0",2,2); //Присвоение значение переменной (asg,value,varName,first) this.ruleStack.addRule("assign","asgn",2,2); //Сравнение "равно" (equ,value1,value2,push) this.ruleStack.addRule("==","equ",2,0); //Сравнение "больше" (mor,value1,value2,push) this.ruleStack.addRule(">","mor",2,0); //Сравнение "меньше" (les,value1,value2,push) this.ruleStack.addRule("<","les",2,0); //Сравнение "больше либо равно" (morq,value1,value2,push) this.ruleStack.addRule(">=","morq",2,0); //Сравнение "меньше либо равно" (lesq,value1,value2,push) this.ruleStack.addRule("<=","lesq",2,0); //Переход по метке (jmp,label,null,null) this.ruleStack.addRule("Jmp","jmp",1,-1); //Переход по метке, если значение = 0 (jmpf,label,value,null) this.ruleStack.addRule("JmpF","jmpf",1,-1); //Если value != нужному значению - возвращается 0 (?,value,null,push) this.ruleStack.addRule("?","case",1,0); //Операция сложения (plus,value1,value2,push) this.ruleStack.addRule("+","plus",2,0); //Операция вычитания (mns,value1,value2,push) this.ruleStack.addRule("-","mns",2,0); //Операция умножения (mltp,value1,value2,push) this.ruleStack.addRule("*","mltp",2,0); //Операция деления (div,value1,value2,push) this.ruleStack.addRule("/","div",2,0); //Начало переключателя (with,value1,null,push) this.ruleStack.addRule("with","with",1,0); //Закрытие блока переключателя (wth,null,null,null) this.ruleStack.addRule("withend","withe",0,-1); }, copyPCode: function() { var textArea = document.createElement("textarea"); textArea.style.position = 'fixed'; textArea.style.top = 0; textArea.style.left = 0; textArea.style.width = '2em'; textArea.style.height = '2em'; textArea.style.padding = 0; textArea.style.border = 'none'; textArea.style.outline = 'none'; textArea.style.boxShadow = 'none'; textArea.style.background = 'transparent'; textArea.value = this.returnString; document.body.appendChild(textArea); textArea.select(); try { var successful = document.execCommand('copy'); var msg = successful ? 'successful' : 'unsuccessful'; console.log('Copying text command was ' + msg); } catch (err) { console.log('Oops, unable to copy'); } document.body.removeChild(textArea); } }; function RulesSet() { this.ruleSet = []; }; RulesSet.prototype = { findRule: function(name) { var n = this.ruleSet.length; for (var i=0;i return null; }, addRule: function(name,finalName,argumentNumber,varMode) { this.ruleSet.push(new Rule(name,finalName,argumentNumber,varMode)) } }; function Rule(name,finalName,argumentNumber,varMode) { this.name=name; this.finalName=finalName; this.argumentNumber=argumentNumber; this.varMode=varMode; }; Rule.prototype = { set: function(name,finalName,argumentNumber,varMode) { this.name=name; this.finalName=finalName; this.argumentNumber=argumentNumber; this.varMode=varMode; } }; |