Теория формальных языков и компиляторов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

Новосибирский государственный технический университет

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

Курсовая работа

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

Новосибирск

2017



Оглавление

1. Цель работы

2. Задание на работу

3. Описание заданного варианта языка

4. Тестовая программа

5. Создание лексики заданного учебного языка

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

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

8. Интерпретатор учебного языка

Заключение

Приложение А



1. Цель работы

проектирование транслятор язык программирование

Практическое применение теоретических основ проектирования трансляторов с языков программирования; освоение средств автоматизации построения трансляторов; разработка элементов транслятора для учебного языка.

2. Задание на работу

1. Описать лексику, синтаксис и семантику заданного варианта языка. Написать несколько простых тестовых программ, содержащих все заданные элементы и управляющие конструкции языка. Вручную выполнить интерпретацию программы. Эти программы использовать впоследствии для проверки элементов разрабатываемого транслятора.

2. Разработать систему регулярных выражений, определяющую лексику заданного варианта языка. Используя пакет Вебтранслаб, построить автоматную реализацию лексического акцептора на выбранном инструментальном языке. Добиться работоспособности акцептора.

3. Разработать совокупность действий, т.е. расширение системы регулярных выражений, реализующую:

- поиск в таблицах идентификаторов / констант и пополнение таблиц;

- доформирование лексем, и построить лексический анализатор. Убедиться в правильности его работы.

4. Разработать формальную грамматику класса LL(1), определяющую синтаксис заданного языка. Используя пакет Вебтранслаб, построить какую-либо автоматную реализацию нисходящего синтаксического акцептора, добиться его работоспособности.

Или:

5. Разработать формальную грамматику класса не выше, чем LALR(1). Используя пакет Вебтранслаб, построить автоматную реализацию восходящего синтаксического акцептора, добиться его работоспособности.

6. Разработать расширение построенного синтаксического акцептора для преобразования входной последовательности лексем в постфиксную форму записи или в абстрактное синтаксическое дерево.

7. Разработать семантический анализатор и преобразователь ПФЗ в псевдокод. Формат псевдокода определяется последней цифрой варианта задания.

8. Разработать интерпретатор псевдокода.

3. Описание заданного варианта языка

Лексика, синтаксис и семантика учебного языка основаны на языках типа Java и C#. Любые конструкции, не оговоренные явно в задании, были определены самостоятельно.

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

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

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

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

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

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

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

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

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

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. Правила грамматики с использованием расширения синтаксического анализатора

Левая часть

Правая часть

Примечание

P

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());

]*

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

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

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

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

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

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

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

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

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);

}

8. Интерпретатор учебного языка

В ходе работы был разработан интерпретатор учебного языка. Код языка транслируется. В итоге трансляции будет получен псевдокод из пентад, этот псевдокод подается на обработку интерпретатора, который в зависимости от кода операции будет выполнять различные действия с аргументами. Результат каждой операции может иметь три исхода: быть записанным в стек, быть записанным в первый аргумент, быть записанным во второй аргумент. Каждое действие записывается в журнал. В результате выполнения выводятся полученные значения для каждой переменной.

Пример:



Заключение

В ходе выполнения курсовой работы, были получены навыки практического применение теоретических основ проектирования трансляторов и интерпритаторов с языками программирования. Были освоены средства автоматизации построения трансляторов, а также разработаны элементы транслятора для учебного языка. Помимо этого, были получены знания о принципах работы трансляторов, были получены навыки разработки отдельных частей транслятора - лексического анализатора, синтаксического анализатора семантического анализатора, интерпретатора, принципы формирования и использования ими информационных таблиц.

Была разработана система лексических правил учебного языка, представленных набором регулярных выражений.

Была разработана формальная грамматика класса 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<tmpRule.argumentNumber) this.returnString+=" "+this.commandStack.pop();

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<n;++i) if (this.ruleSet[i].name!=name) continue; else return this.ruleSet[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;

}

};

Размещено на Allbest.ru

...