DOWHILE循环语句的翻译程序设计（简单优先法、输出三地址表示）.docx

武汉理工大学编译原理课程设计说明书附件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-do B while E,B-c:=a+1,E-ab2.2属性文法描述G(s): S-do B while E, 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(gotoS.begin) B-c:=a+1 B.code:= c:=a+1 E-ab E.code=gen(ifabgoto 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，若它不含e产生式，也不含任何右部相同的不同产生式，并且它的任何符号对(X,Y)，或者没有关系，或者存在下述三种关系：=、之一，则称该文法是一个简单优先文法。 A)X=Y当且仅当G中含有形如PXY的产生式 B)XY当且仅当Y为G的终结符，G中含有形如PQR的产生式，其中Q，R为非终结符，且Q X，YFirst(R)D)对任何X，若文法开始符号SX，则#。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:=n4详细算法描述字符栈#includeusing namespace std;#define STACKSIZE 100class SeqStackprivate:int top;char *data;int maxSize;public: SeqStack();SeqStack()delete data;void InitStack();void Push(char);void Pop(char);void PrintStack();char TopValue();char NextTop();bool Empty();SeqStack:SeqStack()data=new charSTACKSIZE;void SeqStack:InitStack()/初始化符号栈 top = -1;bool SeqStack:Empty() /判断操作符栈是否为空 if(top=0) return false; else return true; void SeqStack:Push(char c)/压栈 if (top 0)char c=datatop-1;return c;else return NULL;void SeqStack:PrintStack()/打印栈的元素 for(int i=0;i=top;i+)coutdatai; coutendl;主要程序#includeStack.h#include#include#include using namespace std;#define norw 13 /关键字的个数#define nmax 14 /数字的最大位数#define al 10 /符号的最大长度#define N -10 #define getchdo if(getch()=-1)return -1#define getsymdo if(getsym()=-1)return -1ifstream *fin;SeqStack Sym,Opt,Opr;char *p,ch;char str20; char inputstr100; /保存从文件读入的所有字符char buf520;int count1=0,count2=0;int ip=0,row,line;enum symbol sym; /当前的符号int num; /当前numberchar aal+1; /临时符号char idal+1; /当前identchar wordnorwal; /保留字enum symbol wsymnorw; /关键字的符号值enum symbol ssym256; /单字符的符号值 enum symbol 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; void ThreeAddr();void init()/设置单字符符号for(int i=0;idoBwhile(E)0,B-d=C;0,C-A+A0, C-A-A0,C-A*A0,C-A/A0,C-A0, E-AA0, E-AA=A0,E-A0,A-d0,; /文法int getch()if(fin-get(ch)if(ch!= & ch!=9 & ch!=10)inputstrip=ch; ip+; cout=a&ch=z)k=0;doif(k=a&ch=0&ch=9);ak=0;strcpy(id,a);i=0;j=norw-1;do /搜索当前符号是否为保留字k=(i+j)/2;if(strcmp(id,wordk)=0)i=k+1;while(ij)sym=wsymk;elsesym=ident; /搜索失败，则是名字或数字elseif(ch=0&ch=0&chnmax)couterror:too large number!endl;else if(ch=) /检测赋值符号sym=becomes;getchdo;elseif(ch=) /检测大于或大于等于符号getchdo;if(ch=)sym=geq;getchdo;elsesym=gtr;elsesym=ssymch;if(sym!=period)getchdo;return 0;/优先关系模块/定义优先关系int PreTable2323 =/* S d o B w h i l e E a = + 1 ; ( b c ) # */* 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 ;int Compare(char m,char n)/定义矩阵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;switch (n)case S: line=0;break;case d: line=1;break;case o: line=2;break; case : line=3;break;case B: line=4;break;case : line=5;break;case w: line=6;break;case h: line=7;break;case i: line=8;break;case l: line=9;break;case e: line=10;break;case E: line=11;break;case a: line=12;break;case =: line=13;break;case +: line=14;break; case 1: line=15;break;case ;: line=16;break; case : line=17;break;case (: line=18;break;case b: line=19;break;case c: line=20;break;case ): line=21;break;case #: line=22;break;default: return -100;break; return PreTablerowline;void Error()/规约不成功 cout归约失败,语法有错误!endl;void Succeed()/规约成功 cout归约成功,语法正确.endl;char Reduce(char c) /将终极符或非终极符规约为非终极符 if (c = d) return S; else if (c = c ) return B; else if (c = a) return E; else return NULL;void Parse()/简单优先语法分析 char c; /保存栈顶元素 char t1; /规约时判断是否规约的栈顶元素char t2; /规约时判断是否规约的次栈顶元素cout归约过程如下:endl;Sym.Push(#); while (*p!=0) c=Sym.TopValue(); if (c=S)/如果栈顶为S或#,规约成功 Succeed(); cout语法分析完成!nendl; cout三地址码如下所示:endl; ThreeAddr(); coutendl; return; else switch (Compare(c, *p) /如果优先符是小于或等于则压栈,否则进栈 case -1: case 0: Sym.Push(*p);/压栈 Sym.PrintStack(); p+; break; case 1: do t1 = Sym.TopValue();bufcount10=0;bufcount1count2=t1;count2+; t2 = Sym.NextTop(); Sym.Pop(c);/栈顶出栈 while(Compare(t2, t1) != -1); count1+; t1 = Reduce(t1); Sym.Push(t1); Sym.PrintStack(); break; default: Error(); cout语法分析完成!n; coutendl; return; void ThreeAddr() /产生并输出三地址码int m=0,nextstat=100;char op1,op2,opt,c;for(int i=0;i=0;j-)if(bufij=a&bufij=A&bufij=0&bufij=9)Opr.Push(bufij); else if(bufij=+|bufij=-|bufij=*|bufij=/|bufij=|bufij=) Opt.Push(bufij);while(!Opr.Empty() & !Opt.Empty() op1=Opr.TopValue();Opr.Pop(c); op2=Opr.TopValue();Opr.Pop(c); opt=Opt.TopValue();if(Opt.TopValue()=) coutnextstat+ op2 opt op1m-1)coutnextstat+ tm-1= op2optop1endl;coutnextstat+ if tm-1 goto 100endl; else coutnextstat+ tm = op2optop1endl;Opt.Pop(c); if(!Opr.Empty() Opr.Push(t);m+;coutnextstat+endl;int main() fin = new ifstream(simple.txt); if(!fin) cout文件打开失败!endl; init();Sym.InitStack();Opt.InitStack();Opr.InitStack();coutn DO-WHILE循环语句的翻译程序(简单优先法、