Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Министерство образования и науки РФ
ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
(ОмГТУ)
Кафедра «ИВТ»
Пояснительная записка
К КУРСОВОМУ ПРОЕКТУ
Разработка компилятора
|
Руководитель проекта |
|
|
Флоренсов А.Н. |
|
|
Разработал студент гр. ИВТ-415 Кривчун Н.С. |
|
Омск 2009
ЗАДАНИЕ №27.
Используя компилятор компиляторов BISON или ZUBR, разработать компилятор с языка программирования, который описательно задается следующими определениями:
1. язык обеспечивает вычисления только в целых числах, директивы определения типа отсутствуют;
2. арифметические выражения могут состоять только из одного или двух операндов, разделенных операцией сложения, вычитания, умножения или деления, причем сами операнды задаются числовой константой или идентификатором;
3. язык содержит операторы цикла, задаваемые ключевым словом while, и условные операторы if, причем возможно использование этого оператора как с частью else, так и без нее;
4. условия задаются в виде
операнд операция_сравнения операнд
где операндом может служить идентификатор или целочисленная константа;
5. для выдачи результатов служит оператор
print имя_переменной
а для ввода оператор
input имя_переменной
6. язык может использовать процедуры, вызываемые в виде отдельного оператора, а описание которых начинается с ключевого слова procedure, а последний операнд вызова всегда возвращает значение (как будто бы эта процедура описана в терминах Паскаля в виде
procedure имя(arg1,arg2,…,argn: INTEGER; VAR argm: INTEGER) ) ;
7. остальные синтаксические элементы языка выбираются разработчиком самостоятельно (скобки, средства указания конца оператора, блока операторов, символ присваивания, обозначения операций сравнения и т.п.);
8. промежуточным языком разрабатываемого компилятора должен быть ассемблер nasm, компилятор с которого, в свою очередь, следует вызывать внутри разрабатываемого компилятора, следом за которым вызывать соответствующий компоновщик;
9. Имена программных объектов должны формироваться по общеупотребительному правилу: первым символом должна быть произвольная латинская буква, последующими символами могут быть цифры или латинские буквы.
Основным результатом работы компилятора должен быть либо исполняемый файл, либо файл объектного кода - в зависимости от опции вызова этого компилятора; в качестве дополнительных файлов, выдаваемых компилятором при указании опций запроса для них, должны формироваться ассемблерный файл промежуточного представления и файл таблицы символических имен.
Представляемые результаты разработки должны включать пояснительную записку и исходный файл для компилятора компиляторов, детально прокомментированный, с текстами подключаемых файлов, созданных разработчиком. Рекомендуется проводить разработку постепенно, реализуя до получения результирующего файла сначала первые пункты его задания, затем добавляя к ним группу следующих и т.д.
Введение
Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые "универсальные языки" (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ. Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM/PC на рынке десятки. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel-80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, 68040. В рамках традиционных последовательных машин возникает большое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков. Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM/RS-6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.
1 Краткое описание Bison
Bison - это генератор лексических анализаторов общего назначения, который преобразует описание контекстно-свободной LALR(1) грамматики в программу на языке C для разбора этой грамматики. Если вы овладеете Bison, вы сможете использовать его для разработки анализаторов языков достаточно широкого класса: от используемых в простых настольных калькуляторах до сложных языков программирования.
Bison обратно совместим с Yacc: все правильные грамматики Yacc должны без изменений работать с Bison. Любой человек, хорошо знающий Yacc, не должен иметь больших проблем при использовании Bison.
Bison написан, в основном, Робертом Корбеттом (Robert Corbett). Ричард Столлмен (Richard Stallman) сделал его совместимым с Yacc. Вильфред Хансен (Wilfred Hansen) из Carnegie Mellon Univerisity добавил поддержку многосимвольных литералов и другие возможности.
2 Описание компилятора
Условно можно выделить две основные функции компилятора – лексический анализатор и синтаксический анализатор. Bison, на основе представленного лексического анализатора, строит синтаксический анализатор на языке С++. Лексический анализатор разрабатывается самостоятельно или с помощью специальных программных средств.
Синтаксис языка похож на синтаксис С++. Язык чувствителен к регистру. Переменные могут быть объявлены в любом месте программы. Все операторы должны заканчиваться точкой с запятой. В качестве операторных скобок используются фигурные скобки. Операции сравнения задаются комбинациями символов eq, ne, ge, le – соответственно равно, неравно, больше либо равно и меньше либо равно.
Управляющие конструкции имеют следующий синтаксис:
Цикл с предусловием while ( условие ) { опреаторы ; };
Условный оператор if ( условие ) { операторы ; } else { операторы ; };
Сокращенный вид управляющих конструкций:
while ( условие ) { ; };
if ( условие ) { ; } else { ; };
Вложенность ограничена возможностями платформы.
Описание основных функций.
InitTable – инициализация таблицы символов.
yylex – лексический анализатор. Читает и распознает лексемы из входного потока данных, пока не встретит символ конца файла.
yyparse – синтаксический анализатор. Выполняет синтаксический анализ входного текста на соответствие правилам грамматики.
GetSym – в зависимости от преданного параметра возвращает указатель на него или нуль.
PutSym – передается имя и тип заносимого объекта. Объект включается в начало списка и передается указатель на него.
Компиляция исходного текста выполняется за один проход. При распознавании правил грамматики в выходной файл записывается соответствующий текст на ассемблере nasm.
Исходный текст с примером приведены в приложении.
Руководство пользователя.
Формат командной строки mc_tab.exe исходный_файл файл_результата
Расширения файлов могут быть любые.
При наличии ошибок будет выдано соответствующие сообщение и номер строки с ошибкой. После чего компиляция продолжится. Результатом компиляции будут являться два файла: файл с сегментом кода и файл с сегментом данных, который включается основной файл специальной директивой.
Приложение
Исходный файл Bison
mc.y
%{
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<errno.h>
#include<math.h>
#include<process.h>
#define YYDEBUG 1
#define stderr herr
int linenum=1;
static int FL=0,count0=0,count_if=0,num_if=0;
static char c;
static FILE *hfile,*hout,*herr,*hdat;
typedef struct sym_table{
char *name;
short type;
union{
int val;
double (*ptr)();
}u;
struct sym_table *next;
}sym_table;
sym_table *PutSym(),*GetSym();
static sym_table *symlist=0;
void execerror(char *s,char *t)
{
if(t) printf("%s %s\n",s,t);
else printf("%s\n",s);
printf("line %d\n",linenum);
}
yyerror()
{
printf("Error: Syntax error: %d\n",linenum);
return 0;
}
sym_table *GetSym(char *s)
{
sym_table *sp;
for(sp=symlist;sp!=(sym_table*)0;sp=sp->next)
if(strcmp(sp->name,s)==0)
return sp;
return 0;
}
char *Allocate(unsigned n)
{
char *p;
p=(char*)malloc(n);
if(p==0) execerror("Error: Out of memory!",(char*)0);
return p;
}
sym_table *PutSym(char *s,int t,double d)
{
sym_table *sp;
sp=(sym_table*)Allocate(sizeof(sym_table));
sp->name=Allocate(strlen(s)+1);
strcpy(sp->name,s);
sp->type=t;
sp->u.val=d;
sp->next=symlist;
symlist=sp;
return sp;
}
static struct{
char *name;
double cval;
} consts[]={
"PI",3.14,
"E",2.17,
0,0
};
static struct{
char *name;
double (*func)();
}builtins[]={
"cos",cos,
"sin",sin,
0,0
};
%}
%union{
int val;
sym_table *sym;
}
%token <val> NUM
%token <sym> UNDEF PRINT INT INPUT ELSE EQ NE GE LE IF ID WHILE EXIT BLTIN
%right '='
%left '*' '/' '%'
%left '+' '-'
%left UNARMIN
%%
wert:
| wert ';'
| wert stmt '\n'
| wert asg '\n'
| wert '\n'
| wert error '\n' {yyerrok;FL=1;}
;
prisv: // присвоение
ID '=' ID {if($1->type==UNDEF||$3->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"push dword[%s]\npop dword[%s]\n",$3->name,$1->name);}}
| ID '=' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"mov dword[%s],%d\n",$1->name,$3);}}
// сложение
| ID '=' ID '+' ID {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else if($5->type==UNDEF) execerror("Error: Undefined variable: ",$5->name);
else{fprintf(hout,"mov eax,dword[%s]\nadd eax,dword[%s]\nmov dword[%s],eax\n",$3->name,$5->name,$1->name);}
}
| ID '=' ID '+' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else{fprintf(hout,"mov eax,dword[%s]\nadd eax,%d\nmov dword[%s],eax\n",$3->name,$5,$1->name);}
}
| ID '=' NUM '+' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"mov dword[%s],%d\n",$1->name,$3+$5);}
}
// вычитание
| ID '=' ID '-' ID {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else if($5->type==UNDEF) execerror("Error: Undefined variable: ",$5->name);
else{fprintf(hout,"mov eax,dword[%s]\nsub eax,dword[%s]\nmov dword[%s],eax\n",$3->name,$5->name,$1->name);}
}
| ID '=' ID '-' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else{fprintf(hout,"mov eax,dword[%s]\nsub eax,%d\nmov dword[%s],eax\n",$3->name,$5,$1->name);}
}
| ID '=' NUM '-' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"mov dword[%s],%d\n",$1->name,$3-$5);}
}
// умножение
| ID '=' ID '*' ID {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else if($5->type==UNDEF) execerror("Error: Undefined variable: ",$5->name);
else{fprintf(hout,"mov eax,dword[%s]\nmul dword[%s]\nmov dword[%s],eax\n",$3->name,$5->name,$1->name);}
}
| ID '=' ID '*' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else{fprintf(hout,"mov eax,%d\nmul dword[%s]\nmov dword[%s],eax\n",$5,$3->name,$1->name);}
}
| ID '=' NUM '*' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"mov dword[%s],%d\n",$1->name,$3*$5);}
}
// деление
| ID '=' ID '/' ID {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else if($5->type==UNDEF) execerror("Error: Undefined variable: ",$5->name);
else{fprintf(hout,"mov eax,dword[%s]\nxor edx,edx\ndiv dword[%s]\nmov dword[%s],eax\n",$3->name,$5->name,$1->name);}
}
| ID '=' ID '/' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else if($3->type==UNDEF) execerror("Error: Undefined variable: ",$3->name);
else{fprintf(hout,"mov eax,dword[%s]\nmov ebx,%d\nxor edx,edx\ndiv ebx\nmov dword[%s],eax\n",$3->name,$5,$1->name);}
}
| ID '=' NUM '/' NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"mov dword[%s],%d\n",$1->name,$3/$5);}
}
;
stmt: PRINT ID ';' {if($2->type==UNDEF) {FL=1;execerror("Error: Undefined variable: ",$2->name);}
else{fprintf(hout,"xor eax,eax\nxor ecx,ecx\n",$2->name);
fprintf(hout,"mov eax,dword[%s]\nlea edi,[bufstr]\n",$2->name);
fprintf(hout,"push eax\npush edi\ncall IntToStr\n");
fprintf(hout,"mov dword[len],ebx\nlea eax,[bufstr]\n");
fprintf(hout,"mov esi,dword[len]\ncall WriteStr\n");
fprintf(hout,"lea eax,[newstr]\nmov esi,2\ncall WriteStr\n");}
}
| INPUT ID ';' {if($2->type==UNDEF) {FL=1;execerror("Error: Undefined variable: ",$2->name);}
else {fprintf(hout,"lea eax,[bufstr]\nmov esi,80\ncall ReadStr\n");
fprintf(hout,"xor eax,eax\nxor esi,esi\nlea eax,[bufstr]\n");
fprintf(hout,"push eax\ncall StrToInt\n");}
fprintf(hout,"mov dword[%s],eax\n",$2->name);
}
| prisv';'
| asg ';'
| IF {count0++;count_if++;num_if++;}'(' cond ')'
'{' stmt '}' {fprintf(hout,"jmp near end_if%d\nelse_if%d:\n",count0,count0);}
ELSE '{' stmt '}' {fprintf(hout,"end_if%d:\n",count0);count0--;count_if--;if(!count_if){count0+=num_if;num_if=0;}} ';'
| WHILE {count0++;count_if++;num_if++;}'(' cond ')'
'{' stmt '}' {fprintf(hout,"jmp near label%d\nelse_if%d:\n",count0,count0);count0--;count_if--;if(!count_if){count0+=num_if;num_if=0;}} ';'
| stmt prisv ';' {}
| stmt asg ';' {}
| stmt PRINT ID ';' {if($3->type==UNDEF) {FL=1;execerror("Error: Undefined variable: ",$2->name);}
else{fprintf(hout,"xor eax,eax\nxor ecx,ecx\n",$3->name);
fprintf(hout,"mov eax,dword[%s]\nlea edi,[bufstr]\n",$3->name);
fprintf(hout,"push eax\npush edi\ncall IntToStr\n");
fprintf(hout,"mov dword[len],ebx\nlea eax,[bufstr]\n");
fprintf(hout,"mov esi,dword[len]\ncall WriteStr\n");
fprintf(hout,"lea eax,[newstr]\nmov esi,2\ncall WriteStr\n");}
}
| stmt INPUT ID ';' {if($3->type==UNDEF) {FL=1;execerror("Error: Undefined variable: ",$3->name);}
else {fprintf(hout,"lea eax,[bufstr]\nmov esi,80\ncall ReadStr\n");
fprintf(hout,"xor eax,eax\nxor esi,esi\nlea eax,[bufstr]\n");
fprintf(hout,"push eax\ncall StrToInt\n");}
fprintf(hout,"mov dword[%s],eax\n",$3->name);
}
| stmt IF {count0++;count_if++;num_if++;}'(' cond ')'
'{' stmt '}' {fprintf(hout,"jmp near end_if%d\nelse_if%d:\n",count0,count0);}
ELSE '{' stmt '}' {fprintf(hout,"end_if%d:\n",count0);count0--;count_if--;if(!count_if){count0+=num_if;num_if=0;}}';'
| stmt WHILE {count0++;count_if++;num_if++;}'(' cond ')'
'{' stmt '}' {fprintf(hout,"jmp near label%d\nelse_if%d:\n",count0,count0);count0--;count_if--;if(!count_if){count0+=num_if;num_if=0;}} ';'
| ';' {}
;
asg: INT ID {fprintf(hdat,"%s dd 0\n",$2->name);$2->u.val=0;$2->type=ID;}
| asg ',' ID {fprintf(hdat,"%s dd 0\n",$3->name);$3->u.val=0; $3->type=ID;}
;
cond: ID EQ NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"label%d:\nmov eax,dword[%s]\ncmp eax,%d\njne near else_if%d\n",count0,$1->name,$3,count0);}
}
|ID NE NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"label%d:\nmov eax,dword[%s]\ncmp eax,%d\nje near else_if%d\n",count0,$1->name,$3,count0);}
}
|ID GE NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"label%d:\nmov eax,dword[%s]\ncmp eax,%d\njl near else_if%d\n",count0,$1->name,$3,count0);}
}
|ID LE NUM {if($1->type==UNDEF) execerror("Error: Undefined variable: ",$1->name);
else{fprintf(hout,"label%d:\nmov eax,dword[%s]\ncmp eax,%d\njg near else_if%d\n",count0,$1->name,$3,count0);}
}
;
%%
static struct
{
char *name;
int key;
} keywords[]={
"print",PRINT,
"input",INPUT,
"exit",EXIT,
"int",INT,
"eq",EQ,
"ne",NE,
"ge",GE,
"le",LE,
"if",IF,
"else",ELSE,
"while",WHILE,
0,0
};
void InitTable()
{
int i;
sym_table *s;
for(i=0;consts[i].name;i++)
PutSym(consts[i].name,ID,consts[i].cval);
for(i=0;builtins[i].name;i++)
{
s=PutSym(builtins[i].name,BLTIN,0.0);
s->u.ptr=builtins[i].func;
}
for(i=0;keywords[i].name;i++)
PutSym(keywords[i].name,keywords[i].key,0.0);
}
yylex()
{
while((c=fgetc(hfile))==' '||c=='\t');
if(isalpha(c))
{
sym_table *s;
char sbuf[80], *p=sbuf;
do{*p++=c;}while((c=fgetc(hfile))!=EOF&&isalnum(c));
ungetc(c,hfile);
*p='\0';
if((s=GetSym(sbuf))==0)
s=PutSym(sbuf,UNDEF,0.0);
yylval.sym=s;
return s->type==UNDEF ? ID : s->type;
}
if(c=='.'||isdigit(c))
{
ungetc(c,hfile);
fscanf(hfile,"%d",&yylval.val);
return NUM;
}
if(c=='\n') linenum++;
return c;
}
void main(int k,char *arg[])
{
hfile=fopen(arg[1],"r");
if (!hfile){printf("error source file");return;}
hout=fopen(arg[2],"w");
if (!hout){printf("error destination file");return;}
herr=fopen("log.txt","w");
if (!hout){printf("error destination file");return;}
hdat=fopen("data.asm","w");
if (!hout){printf("error data file");return;}
fprintf(hout,"EXTERN StrToInt,IntToStr,WriteStr,ReadStr,ExitProg\n");
fprintf(hout,"SEGMENT .text use32 class=code\n");
fprintf(hout,"..start:\n");
fprintf(hdat,"SEGMENT .data use32\n");
fprintf(hdat,"len dd 0\n");
fprintf(hdat,"bufstr times 80 db 0\n");
fprintf(hdat,"newstr db 0xA,0xD\n");
InitTable();
yyparse();
fprintf(hout,"call ExitProg\n");
fputc('%',hout);
fprintf(hout,"include \"data.asm\"\n");
fclose(hfile);
fclose(hout);
fclose(herr);
}
Исходный файл примера
int v1,v2,v3,v4,v5,v6,v7;
v1=26;
v3=5;
input v4;
if (v4 eq 5) { v2=v4;
print v2;
}
else { v2=v4*10;
print v2;
};
v7=0;
while (v7 le 5)
{
v7=v7+1;
v4=v4+2;
print v4;
}
v6=v1-v3;
print v6;
v6=v1*v3;
print v6;
v6=v1/v3;
print v6;
Результирующий файл на ассемблере
EXTERN StrToInt,IntToStr,WriteStr,ReadStr,ExitProg
SEGMENT .text use32 class=code
..start:
mov dword[v1],26
mov dword[v3],5
mov dword[mas+20],9
mov dword[mas+30],5
mov eax,dword[mas+20]
xor edx,edx
div dword[mas+30]
mov dword[mas+1],edx
push dword[mas+1]
pop dword[v2]
xor eax,eax
xor ecx,ecx
mov eax,dword[v2]
lea edi,[bufstr]
push eax
push edi
call IntToStr
mov dword[len],ebx
lea eax,[bufstr]
mov esi,dword[len]
call WriteStr
lea eax,[newstr]
mov esi,2
call WriteStr
call ExitProg
%include "data.asm"
Файл, указанный в директиве %include "data.asm"
SEGMENT .data use32
len dd 0
bufstr times 80 db 0
newstr db 0xA,0xD
v1 dd 0
v2 dd 0
v3 dd 0
v4 dd 0
v5 dd 0