DOWHILE循环语句的翻译程序设计简单优先法输出三地址表示.docx
《DOWHILE循环语句的翻译程序设计简单优先法输出三地址表示.docx》由会员分享，可在线阅读，更多相关《DOWHILE循环语句的翻译程序设计简单优先法输出三地址表示.docx（24页珍藏版）》请在冰点文库上搜索。
DOWHILE循环语句的翻译程序设计简单优先法输出三地址表示
附件1：
学号：
0120910340525
课程设计
题目
DO-WHILE（简单优先法、输出三地址表示）
学院
计算机科学与技术
专业
计算机科学与技术
班级
0905
姓名
明正超
指导教师
杨克俭
2012
年
1
月
3
日
课程设计任务书
学生姓名：
明正超专业班级：
计算机0905班
指导教师：
杨克俭工作单位：
计算机科学与技术学院
题目:
DO-WHILE循环语句的翻译程序设计（简单优先法、输出三地址表示）
初始条件：
理论：
学完编译课程，掌握一种计算机高级语言的使用。
实践：
计算机实验室提供计算机及软件环境。
如果自己有计算机可以在其上进行设计。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
（1）写出符合给定的语法分析方法的文法及属性文法。
（2）完成题目要求的中间代码三地址表示的描述。
（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。
（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。
（5）设计报告格式按附件要求书写。
课程设计报告书正文的内容应包括：
1系统描述（问题域描述）；
2文法及属性文法的描述；
3语法分析方法描述及语法分析表设计；
4按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；
5编译系统的概要设计；
6详细的算法描述（流程图或伪代码）；
7软件的测试方法和测试结果；
8研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；
9参考文献（按公开发表的规范书写）。
时间安排：
设计安排一周：
周1、周2：
完成系统分析及设计。
周3、周4：
完成程序调试及测试。
周5：
撰写课程设计报告。
设计验收安排：
设计周的星期五第1节课开始到实验室进行上机验收。
设计报告书收取时间：
设计周的次周星期一上午10点。
指导教师签名：
2011年11月23日
系主任（或责任教师）签名：
2011年11月23日
（一）系统描述
根据所学编译原理有关词法分析，语法分析，语义分析有关规则,对DO_WHILE循环语句的翻译程序进行设计，使用高级语言或者伪代码形式，进行编写，其中要求使用简单优先法法并在程序的最终结果中显示出表达式的三地址形式。
（二）文法及属性文法的描述
2.1文法描述
G（s）:
S->doBwhileE,
B->c:
=a+1,
E->a>b
2.2属性文法描述
G（s）:
S->doBwhileE,{S.begin:
=newlabel;
B.next:
=S.begin;
E.true:
=newlabel;
E.false:
=S.next;
S.code:
=gen（S.begin’:
’）‖B.code‖E.code‖
gen（E.true’:
’）‖gen（‘goto’S.begin）}
B->c:
=a+1{B.code:
=’c:
=a+1’}
E->a>b{E.code=gen（‘if’’a>b’’goto’E.true）‖
Gen（‘goto’E.false）}
E->true{E.code:
=gen（‘goto’E.true）}
E->false{E.code:
=gen（‘goto’E.false）}
3语法分析方法及中间代码形式的描述
3.1语法分析方法描述
3.1.1简单优先法的定义
一个文法G，若它不含ε产生式，也不含任何右部相同的不同产生式，并且它的任何符号对（X,Y），或者没有关系，或者存在下述三种关系：
=、<、>之一，则称该文法是一个简单优先文法。
A）X=Y当且仅当G中含有形如P→…XY…的产生式
B）XC）X>Y当且仅当Y为G的终结符，G中含有形如P→…QR…的产生式，其中Q，R为非终结符，且Q→…X，Y∈First（R）
D）对任何X，若文法开始符号S→X…，则##。
3.1.2简单优先法的基本思想
根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。
PDA读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于该单词，继续读入；若栈顶符号优先级高于或等于读入符号，则找句柄进行归约，找不到句柄就继续读入。
直到最后栈内只剩下开始符号，输入串读到“＃”为止。
此时识别正确。
可分点描述如下:
1、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄;
2、规定句柄内各相邻符号之间具有相同的优先级;
3、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄;
4、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系.
3.1.3简单优先矩阵
用于表示文法符号之间的简单优先关系的矩阵。
3.1.4简单优先法的优缺点
优点：
技术简单
缺点：
适用范围小，分析表尺寸太大。
3.2中间代码形式描述
四元式是一种比较普遍采用的中间代码形式。
四元式的四个组成成分是：
算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。
运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。
有时，为了更直观，也把四元式的形式写成简单赋值形式，即三地址。
例如:
输入字符串a:
=b*c+b*d则输出三地址：
（1）t:
=b*c
（2）m:
=b*d
（3）n:
=t+m
（4）a:
=n
4详细算法描述
字符栈
#include
usingnamespacestd;
#defineSTACKSIZE100
classSeqStack
{
private:
inttop;
char*data;
intmaxSize;
public:
SeqStack（）;
~SeqStack（）{delete[]data;}
voidInitStack（）;
voidPush（char）;
voidPop（char）;
voidPrintStack（）;
charTopValue（）;
charNextTop（）;
boolEmpty（）;
};
SeqStack:
:
SeqStack（）
{
data=newchar[STACKSIZE];
}
voidSeqStack:
:
InitStack（）//初始化符号栈
{
top=-1;
}
boolSeqStack:
:
Empty（）//判断操作符栈是否为空
{
if（top>=0）
returnfalse;
else
returntrue;
}
voidSeqStack:
:
Push（charc）//压栈
{
if（top{
top++;
data[top]=c;
}
}
voidSeqStack:
:
Pop（charc）//出栈
{
if（!
Empty（））
{
c=data[top];
top--;
}
}
charSeqStack:
:
TopValue（）//取栈顶元素值
{
if（!
Empty（））
{
charc=data[top];
returnc;
}
elsereturnNULL;
}
charSeqStack:
:
NextTop（）//取次栈顶元素
{
if（top>0）
{
charc=data[top-1];
returnc;
}
elsereturnNULL;
}
voidSeqStack:
:
PrintStack（）//打印栈的元素
{
for（inti=0;i<=top;i++）
cout<cout<}
主要程序
#include"Stack.h"
#include
#include
#include
usingnamespacestd;
#definenorw13//关键字的个数
#definenmax14//数字的最大位数
#defineal10//符号的最大长度
#defineN-10
#definegetchdoif（getch（）==-1）return-1
#definegetsymdoif（getsym（）==-1）return-1
ifstream*fin;
SeqStackSym,Opt,Opr;
char*p,ch;
charstr[20];
charinputstr[100];//保存从文件读入的所有字符
charbuf[5][20];
intcount1=0,count2=0;
intip=0,row,line;
enumsymbolsym;//当前的符号
intnum;//当前number
chara[al+1];//临时符号
charid[al+1];//当前ident
charword[norw][al];//保留字
enumsymbolwsym[norw];//关键字的符号值
enumsymbolssym[256];//单字符的符号值
enumsymbol{
nul,ident,number,plus,minus,times,
slash,oddsym,eql,neq,lss,leq,
gtr,geq,lparen,rparen,lbrace,rbrace,
comma,semicolon,period,becomes,beginsym,endsym,
ifsym,elsesym,whilesym,writesym,readsym,dosym,
callsym,constsym,varsym,procsym
};
voidThreeAddr（）;
voidinit（）
{
//设置单字符符号
for（inti=0;i<=255;i++）
{
ssym[i]=nul;
}
ssym['+']=plus;
ssym['-']=minus;
ssym['*']=times;
ssym['/']=slash;
ssym['（']=lparen;
ssym['）']=rparen;
ssym['{']=lbrace;
ssym['}']=rbrace;
ssym['=']=eql;
ssym[',']=comma;
ssym['.']=period;
ssym['#']=neq;
ssym[';']=semicolon;
//设置保留字名字，
strcpy（&（word[0][0]）,"begin"）;
strcpy（&（word[1][0]）,"call"）;
strcpy（&（word[2][0]）,"const"）;
strcpy（&（word[3][0]）,"do"）;
strcpy（&（word[4][0]）,"end"）;
strcpy（&（word[5][0]）,"if"）;
strcpy（&（word[6][0]）,"odd"）;
strcpy（&（word[7][0]）,"procedure"）;
strcpy（&（word[8][0]）,"read"）;
strcpy（&（word[9][0]）,"then"）;
strcpy（&（word[10][0]）,"var"）;
strcpy（&（word[11][0]）,"while"）;
strcpy（&（word[12][0]）,"write"）;
//设置保留字符号
wsym[0]=beginsym;
wsym[1]=callsym;
wsym[2]=constsym;
wsym[3]=dosym;
wsym[4]=endsym;
wsym[5]=ifsym;
wsym[6]=oddsym;
wsym[7]=procsym;
wsym[8]=readsym;
wsym[9]=elsesym;
wsym[10]=varsym;
wsym[11]=whilesym;
wsym[12]=writesym;
}
charrule[12][20]={
"S->do{B}while（E）\0",
"B->d=C;\0",
"C->A+A\0",
"C->A-A\0",
"C->A*A\0",
"C->A/A\0",
"C->A\0",
"E->A>A\0",
"E->A"E->A==A\0",
"E->A\0",
"A->d\0",};//文法
intgetch（）
{
if（fin->get（ch））
{
if（ch!
=''&&ch!
=9&&ch!
=10）
{
inputstr[ip]=ch;
ip++;
}
cout<return0;
}
elsereturn-1;
}
//词法分析
intgetsym（）
{
inti,j,k;
while（ch==''||ch==10||ch==9）
{
getchdo;
sym=nul;
}
if（ch>='a'&&ch<='z'）
{
k=0;
do{
if（k{
a[k]=ch;
k++;
}
getchdo;
}while（ch>='a'&&ch<='z'||ch>='0'&&ch<='9'）;
a[k]=0;
strcpy（id,a）;
i=0;
j=norw-1;
do{//搜索当前符号是否为保留字
k=（i+j）/2;
if（strcmp（id,word[k]）<=0）
{
j=k-1;
}
if（strcmp（id,word[k]）>=0）
{
i=k+1;
}
}while（i<=j）;
if（i-1>j）
{
sym=wsym[k];
}
else
{
sym=ident;//搜索失败，则是名字或数字
}
}
else{
if（ch>='0'&&ch<='9'）//检测是否为数字
{
k=0;
num=0;
sym=number;
do{
num=num*10+ch-'0';
k++;
getchdo;
}while（ch>='0'&&ch<='9'）;
k--;
if（k>nmax）
{
cout<<"error:
toolargenumber!
"<}
}
else
{
if（ch=='='）//检测赋值符号
{
sym=becomes;
getchdo;
}
else
{
if（ch=='<'）//检测小于或小于等于符号
{
getchdo;
if（ch=='='）
{
sym=leq;
getchdo;
}
else
{
sym=lss;
}
}
else{
if（ch=='>'）//检测大于或大于等于符号
{
getchdo;
if（ch=='='）
{
sym=geq;
getchdo;
}
else
{
sym=gtr;
}
}
else
{
sym=ssym[ch];
if（sym!
=period）
{
getchdo;
}
}
}
}
}
}
return0;
}
//优先关系模块
//定义优先关系
intPreTable[23][23]=
{/**Sdo{B}whileEa=+1;>（bc）#**/
/*S*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,1},
/*d*/{N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*o*/{N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*{*/{N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,-1,N,N},
/*B*/{N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*}*/{N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*w*/{N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*h*/{N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*i*/{N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*l*/{N,N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N,N,N},
/*e*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N,N},
/*E*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N},
/*a*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,0,N,N,N,N,N},
/*=*/{N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N,N},
/*+*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N},
/*1*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N},
/*;*/{N,N,N,N,N,1,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N},
/*>*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N},
/*（*/{N,N,N,N,N,N,N,N,N,N,N,0,-1,N,N,N,N,N,N,N,N,N,N},
/*b*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,1,N},
/*c*/{N,N,N,N,N,N,N,N,N,N,N,N,N,0,N,N,N,N,N,N,N,N,N},
/*）*/{N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,1},
/*#*/{-1,-1,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,0}};
intCompare（charm,charn）//定义矩阵
{
switch（m）
{
case'S':
row=0;break;
case'd':
row=1;break;
case'o':
row=2;break;
case'{':
row=3;break;
case'B':
row=4;break;
case'}':
row=5;break;
case'w':
row=6;break;
case'h':
row=7;break;
case'i':
row=8;break;
case'l':
row=9;break;
case'e':
row=10;break;
case'E':
row=11;break;
case'a':
row=12;break;
case'=':
row=13;break;
case'+':
row=14;break;
case'1':
row=15;break;
case';':
row=16;break;
case'>':
row=17;break;
case'（':
row=18;break;
case'b':
row=19;break;
case'c':
row=20;break;
case'）':
row=21;break;
case'#':
row=22;break;
default:
return-100;break
升级会员 