L语言编译器技术课程设计报告书.docx
《L语言编译器技术课程设计报告书.docx》由会员分享,可在线阅读,更多相关《L语言编译器技术课程设计报告书.docx(51页珍藏版)》请在冰点文库上搜索。
![L语言编译器技术课程设计报告书.docx](https://file1.bingdoc.com/fileroot1/2023-4/28/6c61e9eb-9710-492a-b6be-cb48e6955f1b/6c61e9eb-9710-492a-b6be-cb48e6955f1b1.gif)
课程设计报告
(2012–2013年度第1学期)
名 称:
编译技术课程设计 题 目:
L语言编译器的设计与实现院 系:
计算机系 班 级:
学 号:
学生姓名:
指导教师:
设计周数:
2 周
成 绩:
日期:
2012年12月27日
《编译技术》课程设计
任 务 书
一、目的与要求
1.任务:
实现一个简单的编译程序,能够对指定程序设计语言进行编译。
2.目的:
加深对课堂讲授知识的理解,熟练掌握编译程序设计原理及常用的技术,建立编译程序的整体概念,使得学生初步具有研究、设计、编制和调试编译程序的能力。
3.要求:
熟悉有关定义、概念和实现算法,设计出程序流程框图和数据结构,编写出完整的源程序,进行静态检查,设计出输入数据、显示输出数据;基本功能完善,方便易用,操作无误;通过课程设计学会编译程序设计与实现的常用技术,具备初步分析、设计和开发编译程序的能力,具备分析与检查软件错误、解决和处理实验结果的能力。
4.学生要求人数:
2人,1人负责扫描器和目标代码生成器的设计和实现,另1人负责语法分析器和语法制导翻译程序的设计和实现。
二、主要内容
下面是课程设计主要内容的简介,详细内容请见《编译技术课程设计指导书》。
1.扫描器设计
该扫描器是一个子程序,其输入是源程序字符串,每调用一次输出一个单词符号。
为了避免超前搜索,提高运行效率,简化扫描器的设计,假设程序设计语言中,基本字不能用作一般标识符,如果基本字、标识符和常数之间没有确定的运算符或界符作间隔,则用空白作间隔。
2.语法分析器设计
以算法优先分析方法为例,设计一个算符优先语法分析程序。
算符优先分析属于自下
而上的分析方法,该语法分析程序的输入是终结符号串(即单词符号串,以一个“#”结尾)
,如果输入串是句子则输出“YES”,否则输出“NO”和错误信息。
当然,也可采用预测分析等方法设计语法分析器,具体方法自定。
3.语法制导翻译程序设计
采用语法制导翻译方法,实现算术表达式、赋值语句和基本控制语句等的翻译。
本语法制导翻译程序的输入是终结符号串(即单词符号串,以一个“#”结尾),如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列。
4.目标代码生成器设计
50
将程序设计语言的中间代码程序翻译为目标代码程序,其输入是四元式序列,输出是一个汇编代码文件。
三、进度计划
序号
设计内容
完成时间
备注
1
任务布置,资料查询,方案制定
第一周周一
2
算法设计,程序实现
第一周周二至第二周周四
3
撰写报告,软件验收
第二周周五
4
四、设计成果要求
1.完成规定的课程设计任务,所设计软件功能符合要求;
2.完成课程设计报告,要求格式规范,内容具体而翔实,应体现自身所做的工作,注重对设计思路的归纳和对问题解决过程的总结。
五、考核方式
1.平时成绩+验收答辩+实验报告;
2.五级分制。
日
学生姓名:
指导教师:
2011 年 12月 12
词法分析
1目 的
通过设计调试词法分析程序,实现从源程序中分出各种单词的方法;加深对课堂教学的理解;提高词法分析方法的实践能力;掌握词法分析器作为子程序以及一遍的处理过程。
源程序
词法分析程序
符号表文件
token文件
2任 务
(1)能对任何L语言源程序进行分析;
(2)采用问答方式输入源程序文件名,然后进行词法分析;
(3)分割单词并转换成机内表示形式,形成token文件(单词序列)、符号表文件;
(4)删除空格等无用符号;
(5)错误处理
l给出的错误信息包括:
总的出错个数,每个错误所在行号,错误编号及说明;
l只处理以下两种错误,其它可不必考虑
1.非法字符:
删除,即,不写入token文件
2.错误单词
a)包括三种形式:
i.数字开头的数字、字母串,如:
3a56
ii.实数中出现两个小数点,如:
3.14.15
iii.实数的小数部分出现字母,如:
5.26B78
b)处理方式:
截去后面出错部分,使其成为一个正确单词(即:
常数)。
如:
3a56转换为3,3.14.15转换为3.14,5.26B78转换为5.26
3数据结构
3.1输入
L源程序,为文本文件。
3.2输出
一个单词序列文件(即:
token文件)和一个符号表文件,并输出错误信息。
(1)token文件结构
typedefstructtoken
{
intlabel; //单词序号
charname[30]; //单词本身intcode; //单词的机内码
intaddr; //地址,单词为保留字时为-1,为标识符或常数时为大于0的数值,即在符号表中的入口地址。
}token;
单词的机内码表示:
单词
编码
单词
编码
单词
编码
单词
编码
and
1
or
11
(
21
:
=
31
begin
2
program
12
)
22
=
32
bool
3
real
13
+
23
<=
33
do
4
then
14
-
24
<
34
else
5
true
15
*
25
<>
35
end
6
var
16
/
26
>
36
false
7
while
17
.
27
>=
37
if
8
标识符
18
,
28
integer
9
整数
19
:
29
not
10
实数
20
;
30
(2)符号表文件结构
符号表用来存放L语言源程序中出现的标识符和常数,文件结构如下:
typedefstructsymble
{
}symble;
intnumber; //序号inttype; //类型
charname[30]; //名字
4词法分析程序流程图
(1)token表生成的主要流程如下:
vt.syn为19时往symp.txt中存入整数,为20symp.txt中存入实数(小数),为-1时显示错误,其他值时symp.txt中存入字符串,包括关键字与标识符
(2)symple表的生成:
由于他是与token表同时生成的,基本流程大致相同,因此用文字叙述与上面流程的差异
A.以字母开头时,为关键字时st.type等于-2,为标识符时为18
B.以数字开头时,小数时st.type为20,整数时为19
C.为#时,st.type为0
D.其他情况均为-1
当st.type为18时往symple.txt中存入标识符,为19时往symple.txt中存入整数,为20时往symple.txt中存入实数(小数)
5.实验算法思想(包含主程序的示意图)
输入字符串
(1)主程序的示意图如下图所示:
调用scanner函数进行分析
判断是什么类型
分类型写入token文件中(symp.txt)
是标志符,整数,实数则分析类型后写入symple文件中
是否结束
否
是
结束
返回
6.实验结果
目标代码生成
1目 的
实践目标代码的生成方法。
2任 务
符号表文件
四元式序列文件
编写一个目标代码生成程序,将L语言的中间代码程序翻译为目标代码程序(汇编语言程序),如下图:
目标代码生成程序
目标代码程序
目标机说明:
l以8086微处理机为目标机,生成8086汇编指令
l8086是16位微处理器,数据总线为16位,地址总线为20位,可寻址1MB的空间
l8086有8个16位通用寄存器和一个标志寄存器。
这8个寄存器AX-DI都可以用作累加器。
其中,BX和BP(基地址指针)寄存器通常用于指定数据区的基址,称为基址寄存器,SI和DI大多用来表示相对基址的偏移量,称为变址寄存器
l8086的地址空间是分段的,每段64KB
l简单起见,本实验不涉及段间寻址,数据与代码都放在一个段内
l实验中选用以下寻址功能,圆括号表示取其内容:
n寄存器寻址:
MOVAX,BX;
功能:
AX←(BX)
n直接寻址:
MOVAX,DATA;
功能:
AX←(DATA)
l常用指令:
n传送指令:
r表示寄存器,m表示内存单元MOVr,r/mr←(r/m),r/m表示r或mMOVr/m,rr/m←(r)
MOV r/m,imm r/m←imm,imm是立即数
n运算指令:
包括ADD,SUB,MUL,DIV,CMP等。
下面以ADD为例说明其用法:
ADD r,r/m r←(r)+(r/m)
ADD r/m,r/imm r/m←(r/m)+(r)或imm
nCMP只影响标志位,不影响操作数的大小
n转移指令:
Z是标志位,S是符号位,O是溢出位
指令码
意义
条件
JZ,JE
结果为0或相等则转
Z=1,(A)=(B)
JNZ,JNE
结果不为0或不相等则
转
Z=0,(A)≠(B)
JNL,JGE
大于等于转
(S∨O)=0,(A)≥(B)
JL,JNGE
小于转
(S∨O)=1,(A)<(B)
JG,JNLE
大于转
(S∨O∨Z)=0,(A)>(B)
JMP
无条件转移
3.数据结构
3.1输入
四元式序列文件和符号表文件,其结构与语法/语义分析程序的输出一致。
3.2输出
一个汇编代码文件,并无特殊数据结构。
4.程序参考结构:
将中间代码程序(四元式序列)翻译成汇编程序可按以下步骤进行:
(1)划分基本块
(2)对每个基本块生成基本块的目标代码
划分基本块
符号表文件
四元式序列文件
目标代码程序
生成目
标代码
为了划分和记录基本块,对四元式结构作以下修改:
typedefstructGenStruct
{
intlabel;charop[4];intcode;intaddr1;intaddr2;intresult;
intout_port; //记录该四元式是否为一个基本块的入口,是则为1,否则为0。
}GenStruct;
5.寄存器分配策略
主要采用四个通用寄存器:
ax,bx,cx,dx,其中,ax,cx的作用固定,ax用作累加器,
cx用作循环计数器,在四元式翻译时直接应用不再分配。
所以分配策略只用于bx与dx,具体算法如下:
if(bx未被使用或已分配给了变量a){
bx分配给变量a;
}
else{
if(dx未被使用或已分配给了变量a){
dx分配给变量a;
}
else{
其它策略;
}
}
注:
a为变量在符号表的入口地址。
Target
6.代码生成器的模块结构及说明
汇编指令
SortDGA
Produce
InitTarget
实现时,整个程序的四元式表和目标代码文件说明为全局数据。
调用划分基本块模块之后,返回新的四元式序列(带入口标记)。
先根据基本块的入口,再查找下一入口,两个入口之间就是该基本块。
7.程序思想流程
if(strcmp(fourCom[i].opera,"=")==0)
{printf("MOV AX,%1s\n",fourCom[i].arg1);printf("MOV%5s,Ax\n",fourCom[i].result);printf("\n");}
if(strcmp(fourCom[i].opera,"+")==0)
{printf("MOVAX,%1s\n",fourCom[i].arg1);printf("ADDAx,%1s\n",fourCom[i].arg2);printf("MOV%1s,Ax\n",fourCom[i].result);
printf("\n");}
if(strcmp(fourCom[i].opera,"-")==0)
{printf("MOVAX,%1s\n",fourCom[i].arg1);printf("SUBAx,%1s\n",fourCom[i].arg2);printf("MOV%1s,Ax\n",fourCom[i].result);printf("\n");}
if(strcmp(fourCom[i].opera,"*")==0)
{printf("MOVAL,%1s\n",fourCom[i].arg1);printf("MUL%1s\n",fourCom[i].arg2);printf("MOV%1s,Ax\n",fourCom[i].result);printf("\n");}
if(strcmp(fourCom[i].opera,"/")==0)
{printf("MOVAX,%1s\n",fourCom[i].arg1);printf("DIV%1s\n",fourCom[i].arg2);printf("MOV%1s,AL\n",fourCom[i].result);printf("\n");}
if(strcmp(fourCom[i].arg2,"goto")==0&&strcmp(fourCom[i].arg1,"if")==0)
{printf("CMP%1s\n",fourCom[i].opera);printf("JNC%1s\n",fourCom[i].result,"\n");
printf("\n");}if(strcmp(fourCom[i].arg2,"goto")==0&&strcmp(fourCom[i].arg1,"if")!
=0)
{printf("JMP%1s\n",fourCom[i].result,"\n");printf("\n");}
通过语义生成的四元式得到一系列的fourCom[i]结构体组,用该结构体里的opera与算
符及界符比较以及arg1和arg2与goto比较得出相应的汇编指令代码,由于涉及到四元式的生成,该程序将语义分析的大部分放了进来导致程序较为冗长,但是生成目标代码的主要部分比较简单。
同时由于课本上的寄存器分配部分较为艰深,为了简便处理只用了一个寄存器。
8.实验结果
实验总结
本次实验我负责词法分析和目标代码生成部分,总体感觉此次课程设计较难,而且由于开始时对实验难度认识不足以及考试复习的原因导致前面两三天的时间没能充分利用,导致目标代码生成部分没能得出完善的结果。
词法分析是我做的较为满意的地方,不仅可以方便的判别小数,还可以对一些错误进行正确的处理,完全满足了实验的要求,但是这个程序花了也我大部分的时间。
由于实验难度大,且需要注意的地方多,比如小数的判断,比如区别小数点后加一个字母这种类型,真的是让我一边写一遍调试一边修改,改了无数次后才终于得到一个还算完美的结果。
虽
然难,但是很大程度上锻炼了我分析处理问题的能力,不停地调试修改过程中也让程序变得更加简洁明了了。
目标代码生成因为要用到语义分析的结果,所以我将大部分的语义代码加了进来,导致代码较为冗长。
由于时间不够,且用多个寄存器还涉及到活跃变量等复杂问题,为了简单处理,只用到了一个寄存器。
除了这个问题,其他都较好,如对if和while的跳转语句,如有条件跳转和无条件跳转。
实验让我切实的感受到了理论知识与具体实现之间的差距。
那些平时上课时觉得很容易懂的知识,要通过自己在计算机上进行实现并不像想象中的那么容易。
我们能理解的知识用计算机语言表述成计算机能理解的语言,这不仅需要很扎实的编程基础,更要彻彻底底的搞懂所学的理论知识,并达到将所学知识融会贯通的程度。
这样才能自由的应付实现时出现的细节问题。
两周的实验让我学到了很多,比如对文件流的应用,c语言和c++的区别,也对编译原理中语法词法中间代码目标代码以及L语言有了更深的认识。
附录一:
词法分析程序代码#include#include#include#include
usingnamespacestd;typedefstructtoken
{charname[30];intsyn;
}token;
typedefstructsymple
{charname[30];int type;
}sym;tokenvt;symst;
charprog[80];charch;
intp,m,x,n,sum;
char
*rwtab[17]={"and","begin","bool","do","else","end","false","if","integer","not"
"or","program","real","then","ture","var","while"};inti=0,k,c,sumint,f;
charfenshu[80],sum1[80];doublesumf=0,fudian;
intshuzi(){
if(ch>='0'&&ch<='9')vt.syn=20;
else
vt.syn=-2;returnvt.syn;}
voidscaner()
{
for(n=0;n<8;n++)
{vt.name[n]=NULL;st.name[n]=NULL;}//if(1+2!
=3)ch=prog[++p];
while(ch==''||ch=='\n')
ch=prog[++p];//跳过空格if(((ch>='a')&&(ch<='z'))||((ch>='A')&&(ch<='Z')))
{
m=0;x=0;
while(((ch>='a')&&(ch<='z'))||((ch>='A')&&(ch<='Z'))||((ch>='0')&&(ch<='9')))
{
vt.name[m++]=ch;st.name[x++]=ch;
ch=prog[++p];
}
vt.name[m]='\0';
st.name[x]='\0';
ch=prog[--p];vt.syn=18;for(n=0;n<17;n++){
if(strcmp(vt.name,rwtab[n])==0)
{ st.name[n]='';st.type=-2;vt.syn=n+1;break;
}
else
st.type=18;
}
}
else
if(ch>='0'&&ch<='9')
{x=0;
c=p;
k=0;
sumint=0;do
{sum1[k]=ch;st.name[x++]=ch;
ch=prog[++c];//ch取后一个数字
k++;
shuzi();//这个函数用来分析浮点数的整数部分是否已经输入到数组里f=vt.syn;
}while(f==20);if(ch=='.')
{ ch=prog[++c];if(ch>='0'&&ch<='9')
{st.name[x++]='.';}c--;
st.type=20;for(n=0;n{
sumint=sumint*10+sum1[n]-'0';
} //计算整数部分i=0;
do
{
ch=prog[++c];st.name[x++]=ch;fenshu[i]=ch;i++;
shuzi();//这个函数用来分析浮点数的小数部分是否已经输入到数组里
}while(vt.syn==20);sumf=0;
st.name[--x]=NULL;x++;
for(k=i-2;k>=0;k--)
{
sumf=sumf*0.1+(fenshu[k]-'0')*0.1;
} //计算浮点数的小数部分fudian=sumint+sumf; //浮点数计算vt.syn=20;
p=--c;
}
else{
ch=prog[p];//若是整数,ch等于原来的值sum=0;
st.type=-1;
while(ch>='0'&&ch<='9')
{
sum=sum*10+ch-'0';ch=prog[++p];
//st.name[x++]=ch;st.type=19;
}
//st.name[--x]=NULL;ch=prog[--p];vt.syn=19;
}
}
elseswitch(ch)
{
case'<':
m=0;
st.type=-1;vt.name[m++]=ch;ch=prog[++p];if(ch=='=')
{
vt.syn=33;vt.name[m++]=ch;
elseif(ch=='>')
{
vt.syn=35;vt.name[m++]=ch;
}
else
{
vt.syn=34;p--;
}
break;
case'>':
m=0;st.type=-1;vt.name[m++]=ch;ch=prog[++p];if(ch=='=')
{
vt.syn=37;vt.name[m++]=ch;
}
else
{
vt.syn=36;p--;
}
break;
case'=':
m=0;st.type=-1;vt.syn=32;
vt.name[m++]=ch;break;
case'+':
m=0;st.type=-1;vt.syn=23;vt.name[m++]=ch;break;
case'-':
m=0; st.type=-1;vt.syn=24;vt.name[m++]=ch;break;
case'*':
m=0;st.type=-1;vt.syn=25;vt.name[m++]=ch;break;
case'/':
m=0;st.type=-1;vt.syn=26;vt.name[m++]=ch;break;
case'.':
m=0;st.type=-1;vt.syn=27;vt.name[m++]=ch;break;
case',':
m=0;st.type=-1;vt.name[m++]=ch;vt.syn=27