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

Компиляторы РГР. Компиляторы_РГР. Курсовая работа по дисциплине Теория формальных языков и компиляторов


Скачать 183.25 Kb.
НазваниеКурсовая работа по дисциплине Теория формальных языков и компиляторов
АнкорКомпиляторы РГР
Дата30.11.2022
Размер183.25 Kb.
Формат файлаdocx
Имя файлаКомпиляторы_РГР.docx
ТипКурсовая
#821124

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра Вычислительной техники
Курсовая работа

по дисциплине «Теория формальных языков и компиляторов»


Студент:




Преподаватель:

Группа:




.

Вариант:

34111232





Новосибирск

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#. Любые конструкции, не оговоренные явно в задании, были определены самостоятельно.

Ключевые слова (в задании выделены жирным шрифтом, например: longwhencase, …) должны быть нечувствительны к регистру. Обозначения:

[...]             – необязательная часть

…              – часть, повторяющаяся произвольное количество раз

< >             – описание конструкции:

<Б>|<Ц>|<пБ>|<пЦ>|<пБЦ> – одна буква | одна цифра | непустая последовательность букв | непустая последовательность цифр | возможно пустая последовательность букв и/или цифр

<И> – Имя переменной / объекта; <К> – Константа;

<В> – произвольное Выражение; <ЛВ> – Логическое Выражение;

<ОБ> – Оператор или Блок; <О> – одиночный оператор; <ОП> – оператор присваивания; <Код> – код операции; <Оп> – имя операнда; <Рез> – имя результата

Расшифровка цифр варианта задания:

II.1      Идентификаторы и константы

Вариант:

3

Идентификаторы

<Б>_<пБЦ>

Константы

целые 10-чные целые 4-ричные

вещественные

символьные

 II.2      Объявления примитивных типов (целое, вещественное, символьное):

Вариант:

3




[un]signed

number

sign

II.3      Объявления объектов

Вариант:

2

Класс

Entity

II.4      Оператор присваивания:

Вариант:

4




let <И> <В> ;

 II.5      Условный оператор:

Вариант:

1




when <ЛВ> then<ОБ> [else <ОБ>]

 

II.6      Оператор цикла:

Вариант:

2




while(<ЛВ>loop <ОБ>

II.7      Оператор переключателя

Вариант:

2




with <В> {? <К>:<ОБ> [off]}

II.8      Вид псевдокода

Вариант:

1




пентады

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 Создание лексики заданного учебного языка


Исходя из варианта на курсовую работу, были написаны следующие правила лексики:

 Имя автомата 

 Имя группы слов 

 Регулярное выражение 

 Действие 

 Примечание 

 main 

 ar_md 

 [/*] 

  

 

 main 

 ar_pm 

 [-+] 

  

 

 main 

 assign 

 [=] 

  

 

 main 

 braces 

 [{}] 

  

 

 main 

 closer 

 [;] 

  

 

 main 

 comment 

 [/][/][а-яА-Яa-zA-Z0-9 .-+*/{}<>()[\]='";]* 

 ignoreLastWord=true; 

 

 main 

 compare 

 [<>]|([<][=])|([>][=])|([=][=])|([!][=]) 

  

 

 main 

 divider 

 [,] 

  

 

 main 

 id 

 [a-zA-Z][_][a-zA-Z]+ 

  

 

 main 

 keyword 

 [a-zA-Z]+ 

  

 

 main 

 number 

 [0-9]+[.]([0-9]+) 

  

 

 main 

 quadre 

 ([0][x])[0-3]+[q] 

  

 

 main 

 rnd_braces 

 [()] 

  

 

 main 

 sign 

 ["][]*["] 

  

 

 main 

 space 

 [ \r\t\n] 

 ignoreLastWord=true; 

 

 main 

 unsigned 

 [0-9]+ 

  

 

 main 

 switch_tr 

 [?]|[:] 

  

 

 

 

 

 

 


6 Создание грамматики заданного учебного языка


Правильная программа на заданном языке представляет собой класс, содержащий условные блоки, в которых выполняются арифметические операции с переменными. Объявление класса начинается с ключевого слова entity, за которым следует имя класса (идентификатор). Далее между словами «{« и «}» описывается тело класса.

Объявление одного набора переменных (полей) начинается с его типа, за которым следует идентификатор переменной. Так же при объявлении переменной можно задать ей значение.

Исходя из варианта на курсовую работу, была разработана формальная грамматика, принадлежащая к классу LL(1), на основании которой был построен нисходящий синтаксический анализатор (шаблон lexAsGraphSyntAsRD). Текст грамматики приведен в таблице 2.

Таблица 2. Правила грамматики с использованием расширения синтаксического анализатора

Левая часть 

 Правая часть 

 Примечание 

 

 class 

 [ 

 showc 

 ]? 

 

 class 

 entity 

 tracer.put(0,this.currentLexem[1]); tracer.put(0,"entity"); 

 id 

 

 [ 

 block 

 ]* 

 

 tracer.put(0, "entityend" ); 

 

 showc 

 show 

 var translator = new LangTrans(tracer.history); var t = document.createTextNode(translator.stackCompute()); document.body.appendChild(t); translator.copyPCode(); console.log("t:\n",t); 

 

 block 

 sent 

 

 block 

 

 [ 

 sent 

 ]* 

 

 

 sent 

 tmpStack.in(this.currentLexem[1]); 

 var_type 

 var_def 

 tracer.put(0,tmpStack.typeCheck()); 

 [ 

 divider 

 var_def 

 tracer.put(0,tmpStack.typeCheck()); 

 ]* 

 closer 

 tmpStack.out(); 

 

 sent 

 assignment 

 

 sent 

 whenthen 

 Else 

 tracer.put(0,tmpStack.out()+"End:"); 

 

 sent 

 while 

 

 sent 

 switch 

 

 var_type 

 unsigned 

 

 var_type 

 sign 

 

 var_type 

 number 

 

 var_def 

 tracer.put(0,this.currentLexem[1]); 

 id 

 [ 

 

 expression 

 tmpStack.in("exp"); 

 ]? 

 

 assignment 

 let 

 tracer.put(0,this.currentLexem[1]); 

 id 

 

 expression 

 closer 

 tracer.put(0,"assign"); 

 

 whenthen 

 when 

 logical 

 tmpStack.in("ifLbl"+ifCnt); tracer.put(0,tmpStack.get()); tracer.put(0,"JmpF"); ++ifCnt; 

 then 

 block 

 tracer.put(0,tmpStack.get()+"End"); tracer.put(0,"Jmp"); tracer.put(0,tmpStack.get()+":"); 

 

 Else 

 else 

 block 

 

 Else 

 else 

 

 while 

 tmpStack.in("whileLbl"+doCnt); tracer.put(0,tmpStack.get()+":"); ++doCnt; 

 while 

 logical 

 tracer.put(0,tmpStack.get()+"End");tracer.put(0,"JmpF"); 

 loop 

 block 

 tracer.put(0,tmpStack.get()); tracer.put(0,"Jmp"); tracer.put(0,tmpStack.get()+"End"+":"); 

 

 switch 

 tmpStack.in("switchLbl"+switchCnt); ++switchCnt; 

 with 

 expression 

 tracer.put(0, "with" ); caseCnt=0; 

 

 [ 

 switch_block 

 ]+ 

 

 tracer.put(0,tmpStack.get()+"Case"+caseCnt+":"); tracer.put(0,tmpStack.out()+":"); tracer.put(0,"withend"); 

 

 expression 

 exp_pm 

 

 logical 

 

 expression 

 tmpStack.in(this.currentLexem[1]); 

 compare 

 expression 

 

 tracer.put(0,tmpStack.out()); 

 

 switch_block 

 tracer.put(0,tmpStack.get()+"Case"+caseCnt+":"); ++caseCnt; 

 

 val 

 

 tracer.put(0,"?"); tracer.put(0,tmpStack.get()+"Case"+caseCnt); tracer.put(0,"JmpF"); 

 [ 

 block 

 ]* 

 off 

 closer 

 tracer.put(0,tmpStack.get()); tracer.put(0,"Jmp"); 

 

 exp_pm 

 exp_md 

 [ 

 tmpStack.in(this.currentLexem[1]); 

 ar_pm 

 exp_md 

 tracer.put(0,tmpStack.out()); 

 ]* 

 

 val 

 tracer.put(0,this.currentLexem[1]); 

 id 

 

 val 

 tracer.put(0,this.currentLexem[1]); 

 number 

 

 val 

 tracer.put(0,this.currentLexem[1]); 

 quadre 

 

 val 

 tracer.put(0,this.currentLexem[1]); 

 sign 

 

 val 

 tracer.put(0,this.currentLexem[1]); 

 unsigned 

 

 val 

 

 expression 

 

 

 exp_md 

 val 

 [ 

 tmpStack.in(this.currentLexem[1]); 

 ar_md 

 val 

 tracer.put(0,tmpStack.out()); 

 ]* 

 

 

 

 

 

6.1 Расширение синтаксического анализатора


Расширение синтаксического анализатора подразделяется на четыре основные составляющие:

  1. Формирование постфиксной записи

  2. Преобразование постфиксной записи в набор пентад

  3. Интерпретация

Для формирования постфиксной записи (далее ПФЗ) разработано расширение. Вызовы функций производятся при синтаксическом разборе. Класс, формирующий ПФЗ, добавляет операнды и операции в стек, а затем извлекает в необходимом порядке. Основной подход при формировании ПФЗ заключается в том, что при чтении той или иной синтаксической конструкции, нужно определить, какие действия должны выполняться при ее обработке, выявляется выполняемая операция, определяются ее операнды и записываются в постфиксной форме (сначала идут операнды, затем операция).

Псевдокод формируется посредством последовательного чтения лексем из ПФЗ. Для каждой операции строится соответствующее правило формирования пентады. Полный код расширения приведен в Приложении А.

Правила построения пентад:

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;

}

};


написать администратору сайта