L语言编译器技术课程设计报告书Word格式.docx
《L语言编译器技术课程设计报告书Word格式.docx》由会员分享,可在线阅读,更多相关《L语言编译器技术课程设计报告书Word格式.docx(51页珍藏版)》请在冰点文库上搜索。
算法设计,程序实现
第一周周二至第二周周四
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
or
11
(
21
:
=
31
begin
program
12
)
22
32
bool
real
13
+
23
<
33
do
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;
//类型
//名字
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.实验结果
目标代码生成
实践目标代码的生成方法。
四元式序列文件
编写一个目标代码生成程序,将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)>
JMP
无条件转移
3.数据结构
四元式序列文件和符号表文件,其结构与语法/语义分析程序的输出一致。
一个汇编代码文件,并无特殊数据结构。
4.程序参考结构:
将中间代码程序(四元式序列)翻译成汇编程序可按以下步骤进行:
(1)划分基本块
(2)对每个基本块生成基本块的目标代码
划分基本块
生成目
标代码
为了划分和记录基本块,对四元式结构作以下修改:
typedefstructGenStruct
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;
其它策略;
注:
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);
\n"
);
+"
MOVAX,%1s\n"
ADDAx,%1s\n"
fourCom[i].arg2);
MOV%1s,Ax\n"
printf("
-"
{printf("
SUBAx,%1s\n"
*"
MOVAL,%1s\n"
MUL%1s\n"
/"
DIV%1s\n"
MOV%1s,AL\n"
if(strcmp(fourCom[i].arg2,"
goto"
)==0&
&
strcmp(fourCom[i].arg1,"
if"
CMP%1s\n"
fourCom[i].opera);
JNC%1s\n"
fourCom[i].result,"
}if(strcmp(fourCom[i].arg2,"
)!
=0)
JMP%1s\n"
通过语义生成的四元式得到一系列的fourCom[i]结构体组,用该结构体里的opera与算
符及界符比较以及arg1和arg2与goto比较得出相应的汇编指令代码,由于涉及到四元式的生成,该程序将语义分析的大部分放了进来导致程序较为冗长,但是生成目标代码的主要部分比较简单。
同时由于课本上的寄存器分配部分较为艰深,为了简便处理只用了一个寄存器。
8.实验结果
实验总结
本次实验我负责词法分析和目标代码生成部分,总体感觉此次课程设计较难,而且由于开始时对实验难度认识不足以及考试复习的原因导致前面两三天的时间没能充分利用,导致目标代码生成部分没能得出完善的结果。
词法分析是我做的较为满意的地方,不仅可以方便的判别小数,还可以对一些错误进行正确的处理,完全满足了实验的要求,但是这个程序花了也我大部分的时间。
由于实验难度大,且需要注意的地方多,比如小数的判断,比如区别小数点后加一个字母这种类型,真的是让我一边写一遍调试一边修改,改了无数次后才终于得到一个还算完美的结果。
虽
然难,但是很大程度上锻炼了我分析处理问题的能力,不停地调试修改过程中也让程序变得更加简洁明了了。
目标代码生成因为要用到语义分析的结果,所以我将大部分的语义代码加了进来,导致代码较为冗长。
由于时间不够,且用多个寄存器还涉及到活跃变量等复杂问题,为了简单处理,只用到了一个寄存器。
除了这个问题,其他都较好,如对if和while的跳转语句,如有条件跳转和无条件跳转。
实验让我切实的感受到了理论知识与具体实现之间的差距。
那些平时上课时觉得很容易懂的知识,要通过自己在计算机上进行实现并不像想象中的那么容易。
我们能理解的知识用计算机语言表述成计算机能理解的语言,这不仅需要很扎实的编程基础,更要彻彻底底的搞懂所学的理论知识,并达到将所学知识融会贯通的程度。
这样才能自由的应付实现时出现的细节问题。
两周的实验让我学到了很多,比如对文件流的应用,c语言和c++的区别,也对编译原理中语法词法中间代码目标代码以及L语言有了更深的认识。
附录一:
词法分析程序代码#include<
math.h>
#include<
stdlib.h>
fstream>
iostream>
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"
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;
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'
Z'
)))
m=0;
x=0;
while(((ch>
vt.name[m++]=ch;
st.name[x++]=ch;
vt.name[m]='
\0'
;
st.name[x]='
ch=prog[--p];
vt.syn=18;
for(n=0;
17;
n++){
if(strcmp(vt.name,rwtab[n])==0)
{ st.name[n]='
st.type=-2;
vt.syn=n+1;
break;
st.type=18;
{x=0;
c=p;
k=0;
sumint=0;
do
{sum1[k]=ch;
ch=prog[++c];
//ch取后一个数字
k++;
shuzi();
//这个函数用来分析浮点数的整数部分是否已经输入到数组里f=vt.syn;
}while(f==20);
if(ch=='
.'
{ ch=prog[++c];
if(ch>
{st.name[x++]='
}c--;
st.type=20;
k;
sumint=sumint*10+sum1[n]-'
} //计算整数部分i=0;
fenshu[i]=ch;
i++;
//这个函数用来分析浮点数的小数部分是否已经输入到数组里
}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.1;
} //计算浮点数的小数部分fudian=sumint+sumf;
//浮点数计算vt.syn=20;
p=--c;
else{
ch=prog[p];
//若是整数,ch等于原来的值sum=0;
st.type=-1;
while(ch>
sum=sum*10+ch-'
ch=prog[++p];
//st.name[x++]=ch;
st.type=19;
//st.name[--x]=NULL;
ch=prog[--p];
vt.syn=19;
elseswitch(ch)
case'
'
vt.name[m++]=ch;
vt.syn=33;
elseif(ch=='
vt.syn=35;
vt.syn=34;
p--;
break;
vt.syn=37;
vt.syn=36;
vt.syn=32;
+'
st.type=-1;
vt.syn=23;
case'
-'
st.type=-1;
vt.syn=24;
*'
vt.syn=25;
/'
vt.syn=26;
vt.syn=27;
'
vt.syn=27