编译原理课设-(词法分析、自下而上语法分析程序、生成中间代码)

1、精选优质文档-倾情为你奉上 课程设计任务书课题名称编译原理课程设计完成时间 指导教师 职称 学生姓名 班级 总体设计要求总体设计要求： 课程设计内容共给定1个题目，每个学生按照课程设计要求，在规定的两周时间内独立完成。题目： 编译程序构造涉及内容：词法分析、语法分析、语义分析生成中间代码工作内容及时间进度安排第一周、周：设计动员，布置课程设计任务，查阅资料，制定方案，进行程序方案设计。第一周、周2-周5：编写和调试程序第二周、周1-周3：编写和调试程序第二周、周4：整理，撰写设计报告。第二周、周5：验收，提交设计报告，评定成绩。毕业设计成果1、课程设计报告书一份2、源程序清单一份3、成果使用说

2、明书一份内容摘要 第1章 绪论1.1、课程设计目的 1.2、课程设计意义 1.3、课程设计要求 1.4、课程设计内容1.4.1、题目编译程序构造1.4.2、内容涉及词法分析、自下而上语法分析程序的实现：SLR（1）分析器的实现以及生成中间代码。1.4.3、具体要求根据LR分析算法构造SLR（1）分析程序，并完成语法分析动作（当需要一个单词时，调用词法分析程序获取），同时完成语义分析生成四元式输出。要求程序具有通用性，改变文法时只需改变程序的数据初值，无需改变程序主体；要求完成一条说明语句、一条算数表达式和赋值语句的翻译，生成中间代码。变量说明语句的文法及相应的语义子程序：.att表示数据类型属

3、性，fill函数表示将单词id及其类别属性填写符号表。（0）SD； acc（1）Dint id fill（id，int）；D.att=int; （2）Dfloat id fill(id,float); D.att=float; （3）DD（1），id fill(id,D(1).att);D.att=D(1).att; 算数表达式和赋值语句的文法及相应的语义子程序。（1）Aid=E； p=lookup(); emit（E.PALCE, , p）; （2）EE(1)+T E.PALCE=newtemp(); emit(+，E(1).PALCE，T.PALCE，E.PALCE)（3）E

4、T E.PALCE=T.PALCE;（4）TT(1)*F T.PALCE=newtemp(); emit(+，T(1).PALCE，F.PALCE，T.PALCE)（5）TF T.PALCE=F.PALCE;（6）F(E) F.PALCE=E.PALCE;（7）Fid P=LOOKUP(); F.PALCE=P;（8）Fnum P=LOOKUP(num.value)F.PALCE=P;构造其用于SLR(1)分析的识别活前缀的DFA以及action表和goto表。然后编程实现。（关于词法分析部分只需识别出与此文法相关的单词即可（+，*，(，)，id，=）。1.4.4、程序设计提示（

5、1）分析栈设计时可以用一个栈完成，也可以设计三个栈：一个符号栈，一个状态栈，一个语义栈，则归约时，则需要在符号栈中退掉n个符号，在状态栈中退掉n个符号（n为产生式符号个数），语义栈中退掉n个符号对应的语义；（2）终结符表和非终结符表的组织和预测分析程序中相同（将符号对应到一个数字，表示在分析表中对应的下标）。（3）action表中的错误处理：简化的错误处理：当查找action表出现空白时，则当前单词无法移进和规约，可简单的认为当前单词为多余的单词，则抛弃当前单词，读下一单词继续分析。1.4.5、测试数据源文件中数据：int area，r； r=1；area=r*r+r；程序要求输出二元式序列、

6、符号表、语法分析过程、四元式序列。1.4.6、程序扩展要求 第2章 程序总体设计 第3章 程序详细设计与实现3.1、词法分析首先定义结构体typedef struct /状态栈 int datamax;int top;seqstack1;typedef struct /符号栈 string datamax; int top;seqstack2;struct reserveedword/保留字表结构 string word;char value;reserveedword1maxsize;struct identifer/标识符表结构 char identiname15; char identi

7、type15; int address;identifer1maxsize;struct constant/常量表结构string constantname; string value; int constantaddress;constant1maxsize;词法分析主要函数结构： void Initscanner() /该函数用于用C语言当中常见的关键字初始化保留表 void Isalpha(char s) /用于判断读入的字符是不是字母 void Isnumber(char s) /用于判断读入的字符是不是数字 void Isother(char s) /判断除数字与字母之外的其他字符

8、void Lexscan() /用于循环从程序中读入字符并判断应调用那个判断函数字符 void Output(int i,int j,char ss15) /输出二元式 本模块程序的伪代码如下：打开文件infile.open("input.txt",ios:in); if(!infile) cerr<<"读取的文件打开失败!"<<endl; exit(1); 初始化保留字表 Initscanner();循环读入从文件当中 Scanner()while(ch!='#') 在该函数中判断应该调用的判断函数 Lexsca

9、n() infile.get(ch); if(ch>='A')&&(ch<='Z')|(ch>='a')&&(ch<='z') Isalpha(ch) Output； else if(ch>='0')&&(ch<='9') Isnumber(ch) Output； else Isother(ch) Output； 关闭文件infile.close(); 词法分析器中从源文件读出一个单词，判断其类型是关键字、标识符还是

10、普通符号，根据其类型为结构体各项赋值，并将其传给语法分析函数。3.2、语法分析由于说明语句与算术表达式和赋值语句所使用的是不同的文法，所以两者的ACTION表和GOTO表也不一样，本次课设采用二维数组存放ACTION表和GOTO表信息，其中移进用大于0的数表示，归约用小于0的数表示，成功用100表示(acc),其他处用0表示，查表时遇到相应的数进行相应的操作。其中，归约部分需要根据其产生式的信息进行，所以程序中有如下定义：string v18="int","float","",",","id",

11、"#","D","S" /存放说明文法当中的字符string v213="#","id","=","num","","+","*","(",")","F","A","E","T"/存放算本文法当中的字符根据状态转换图(DFA)构造SLR(1)分析表：其中说明文法和算术文法分别构造

12、，同时在每个表当中既有action表 又有goto表int analysis_table1108=3,4,0,0,0,0,2,1, 0,0,0,0,0,100,0,0,0,0,5,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,9,0,0,0,0,0,-2,-2,0,0,0,0,0,0,-3,-3,0,0,0,0,0,0,-4,-4,0,0,0,0;int analysis_table21713=0,2,0,0,0,0,0,0,0,0,1,0,0, 100,0,0,0,0,0,0,0,0,0,0,0,0, 0

13、,0,3,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,4,5, 0,0,0,0,10,11,0,0,0,0,0,0,0, 0,0,0,0,-3,-3,12,0,-3,0,0,0,0, 0,0,0,0,-5,-5,-5,0,-5,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,13,5, 0,0,0,0,-8,-8,-8,0,-8,0,0,0,0, 0,0,0,0,-7,-7,-7,0,-7,0,0,0,0, -1,0,0,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,0,14, 0,9,0,8,0,

14、0,0,7,0,15,0,0,0, 0,0,0,0,0,11,0,0,16,0,0,0,0, 0,0,0,0,-2,-2,12,0,-2,0,0,0,0, 0,0,0,0,-4,-4,-4,0,-4,0,0,0,0, 0,0,0,0,-6,-6,-6,0,-6,0,0,0,0;语法分析当中各个函数说明及伪代码：void action1(int i,string s) /通过词法分析传过来的值判断移进动作三个栈(状态栈,符号栈,语义栈)应该读入哪些值。void action2(int i,string s) /同action1只是表示算术文法int address(string m,int i,

15、string x) /获得在分析表中的列下标void goto1(int i,string s) /通过判断栈中的元素，来判断用那个产生式来进行规约void goto2(int i,string s) /同goto1void slr1() /对说明文法进行语法分析void slr1() /对算术文法进行语法分析 伪代码如下： 先判断是说明文法还是算术文法 If(说明文法) Slr1()push_seq1(s1,0); push_seq2(s2,"#");push_seq2(s3,"_");while(1) j=address(v1,8,get1); to

16、p_seq1(s1,top); j=analysis_table1topj; if(j<0) if(j=-1) 用S->D;归约 else if(j=-2)用D->int id归约 else if(j=-3)用D->float id归约" else if(j=-4)用D->D,id归约" else if(j>0) action1(top,get1); else Slr2() push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); while(1)

17、 j=address(v2,13,get1); j=analysis_table2topj; if(j>0) action2(top,get1); else if(j<0) if(j=-1)用A->id=E;归约" else if(j=-2)用E->E+T归约" else if(j=-3)用E->T归约" else if(j=-4) 用T->T*F归约"); else if(j=-5)用T->F归约" else if(j=-6)用F->(E)归约" else if(j=-7)用F->

18、;id归约" else if(j=-8)用F->num归约" 3.3、语义分析一个程序经过词法分析，语法分析之后，表明该院程序在书写上是正确的，但是未对程序的内部逻辑语义进行分析，接下来是进行语义分析。语义分析当中各个函数说明： void print(string s) /打印四元式str1,string str2,string str3,string str4) /产生四元式string newtemp() /产生一个新的临时变量 3.4、程序实现结果图图3-4 语义分析结果图图3-5二元式图3-6符号表图3-7四元式 专心-专注-专业附录#include<i

19、ostream>#include<fstream>using namespace std;#define maxsize 50#define max 30ifstream infile;char ch;int m,n,kk=0,addr=0,t=1;string get1;string inmaxsize;string insmaxsize;string s4;int count=0;string v18="int","float","",",","id","#&qu

20、ot;,"D","S"string v213="#","id","=","num","","+","*","(",")","F","A","E","T"string E="",E1="",T="",T1="",F=&qu

21、ot;"int analysis_table1108=3,4,0,0,0,0,2,1, 0,0,0,0,0,100,0,0,0,0,5,6,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,9,0,0,0,0,0,-2,-2,0,0,0,0,0,0,-3,-3,0,0,0,0,0,0,-4,-4,0,0,0,0;int analysis_table21713=0,2,0,0,0,0,0,0,0,0,1,0,0, 100,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,3,0,0,0,0,0,0,

22、0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,4,5, 0,0,0,0,10,11,0,0,0,0,0,0,0, 0,0,0,0,-3,-3,12,0,-3,0,0,0,0, 0,0,0,0,-5,-5,-5,0,-5,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,13,5, 0,0,0,0,-8,-8,-8,0,-8,0,0,0,0, 0,0,0,0,-7,-7,-7,0,-7,0,0,0,0, -1,0,0,0,0,0,0,0,0,0,0,0,0, 0,9,0,8,0,0,0,7,0,6,0,0,14, 0,9,0,8,0,0,0,7,0,15,0,0,0,

23、 0,0,0,0,0,11,0,0,16,0,0,0,0, 0,0,0,0,-2,-2,12,0,-2,0,0,0,0, 0,0,0,0,-4,-4,-4,0,-4,0,0,0,0, 0,0,0,0,-6,-6,-6,0,-6,0,0,0,0;typedef struct /状态栈 int datamax;int top;seqstack1;typedef struct /符号栈 string datamax;int top;seqstack2;struct reserveedword/保留字表结构string word;char value;reserveedword1maxsize;str

24、uct identifer/标识符表结构char identiname15;char identitype15;int address;identifer1maxsize;struct constant/常量表结构string constantname;string value;int constantaddress;constant1maxsize;void Initscanner();void Lexscan();void Isalpha(char);void Isnumber(char);void Isother(char);void Output(int ,int ,char *);v

25、oid Scanner();void change(char c,string str) int len=str.length();for(int num=0;num<len;num+)cnum=strnum;clen='0'seqstack1 *init_seqstack1()seqstack1 *s;s=new seqstack1;if(!s)cout<<"空间不足！"<<endl;return NULL;else s->top=-1;return s; int empty_seq1(seqstack1 *s)if(s

26、->top=-1) return 1;else return 0;int push_seq1(seqstack1 *s,int x) if(s->top=max-1)return 0;else s->top+;s->datas->top=x;return 1;int pop_seq1(seqstack1 *s,int *x)if(empty_seq1(s)return 0;else *x=s->datas->top;s->top-;return 1;void top_seq1(seqstack1 *s,int &e)if(empty_se

27、q1(s)cout<<"占空!"else e=s->datas->top;seqstack2 *init_seqstack2()seqstack2 *s;s=new seqstack2;if(!s)cout<<"空间不足！"<<endl;return NULL;else s->top=-1;return s; int empty_seq2(seqstack2 *s)if(s->top=-1) return 1;else return 0;int push_seq2(seqstack2 *s,st

28、ring x) if(s->top=max-1)return 0;else s->top+;s->datas->top=x;return 1;int pop_seq2(seqstack2 *s,string *x)if(empty_seq2(s)return 0;else *x=s->datas->top;s->top-;return 1;void out_seq1(seqstack1 *s)for(int i=0;i<=s->top;i+)printf("%d",s->datai);void out_seq2(s

29、eqstack2 *s) char ch15;for(int i=0;i<=s->top;i+)change(ch,s->datai);printf("%s",ch);seqstack1 *s1=init_seqstack1();seqstack2 *s2=init_seqstack2();seqstack2 *s3=init_seqstack2();void pop(int n)int m;string s;for(int i=0;i<n;i+)pop_seq1(s1,&m);pop_seq2(s2,&s); pop_seq2(s3

30、,&s);int screamp(char a15,string b)int i=0,j=0; while(ai!='0'&&bi!='0')if(ai=bi)i+; j+; elsereturn 0;if(ai=bi)return 1;elsereturn 0;int screamp1(string a,string b)int i=0,j=0; while(ai!='0'&&bi!='0')if(ai=bi)i+; j+; elsereturn 0;if(ai=bi)return 1;e

31、lsereturn 0;void clear(seqstack1 *s1,seqstack2 *s2,seqstack2 *s3)int m;string s;while(!empty_seq1(s1)pop_seq1(s1,&m); pop_seq2(s2,&s); pop_seq2(s3,&s);void char_Table() char str115,str215; cout<<"n生成的标识符表为：" cout<<"ntnamettypetvaluetaddress" for(int i=0;i&

32、lt;m;i+) printf("n%dt%st%s",i,identifer1i.identiname,identifer1i.identitype); cout<<"n生成的常数表为：" cout<<"ntvaluettypetnametaddress" for(int j=0;j<n;j+) change(str1,constant1j.constantname); change(str2,constant1j.value); printf("n%dt%st%s",j,str1,

33、str2); int judge(string m,int i,string x) for(int j=0;j<i;j+) if(screamp1(x,mj) return 1; return 0;int address(string m,int i,string x) for(int j=0;j<i;j+) if(screamp1(x,mj) return j;void print(string s)cout<<"n产生的四元式为"<<endl;char chmax; for(int i=0;i<count;i+)change(c

34、h,si);printf("%s",ch);cout<<endl;cout<<endl;void emit(string str1,string str2,string str3,string str4) scount+="("scount+=str1;scount+=","scount+=str2;scount+=","scount+=str3;scount+=","scount+=str4;scount+=")"count+;string newt

35、emp()char s2;s0='T's1=t;s2='0't+;return s;void action1(int i,string s)int pos,j;j=address(v1,8,s);pos=analysis_table1ij;char str15;change(str,s);out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt");if(pos=100)cout<<"分析

36、成功！"<<endl; cout<<"*"<<endl;else printf("action%d,%s=S%d状态%d入栈n",i,str,pos,pos);push_seq1(s1,pos); push_seq2(s2,s); push_seq2(s3,"_"); get1=inaddr;addr+;void goto1(int i,string s) int pos,j; if(judge(v1,8,s) j=address(v1,8,s);pos=analysis_table1ij

37、;char str15;change(str,s); printf("goto%d,%s=%dn",i,str,pos);push_seq1(s1,pos);push_seq2(s2,s);void slr1() clear(s1,s2,s3); char str115; push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); get1=inaddr; addr+; int top,j; while(1) j=address(v1,8,get1); top_seq1(s1,top)

38、; if(top=100) addr-; return; j=analysis_table1topj; if(j<0) if(j=-1) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用S->D;归约"); pop(2); top_seq1(s1,top); goto1(top,"S"); push_seq2(s3,"_"); else if(j=-2) out_seq1(s1);

39、printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->int id归约"); change(str1,"int"); for(int k=0;k<15;k+) identifer1kk.identitypek=str1k; kk+; pop(2); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); else if(j=-3) out

40、_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->float id归约"); change(str1,"float"); for(int k=0;k<15;k+) identifer1kk.identitypek=str1k; kk+; pop(2); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); els

41、e if(j=-4) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用D->D,id归约"); for(int k=0;k<15;k+) identifer1kk.identitypek=identifer1kk-1.identitypek; kk+; pop(3); top_seq1(s1,top); goto1(top,"D"); push_seq2(s3,"_"); else

42、 if(j>0) action1(top,get1); void action2(int i,string s)int pos,j; if(judge(v2,13,s) j=address(v2,13,s);pos=analysis_table2ij;char str15;change(str,s);out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt");if(pos=100)cout<<"分析成功！&quo

43、t;<<endl;cout<<"*"<<endl;else printf("action%d,%s=S%d状态%d入栈n",i,str,pos,pos);push_seq1(s1,pos); push_seq2(s2,s); push_seq2(s3,"_"); get1=inaddr;addr+;void goto2(int i,string s) int pos,j; if(judge(v2,13,s) j=address(v2,13,s);pos=analysis_table2ij;char

44、str15;change(str,s); printf("goto%d,%s=%dn",i,str,pos);push_seq1(s1,pos);push_seq2(s2,s); void slr2() t='1' clear(s1,s2,s3); push_seq1(s1,0); push_seq2(s2,"#"); push_seq2(s3,"_"); get1=inaddr; addr+; string p10;int num=0; pnum=insaddr-1;num+; int top,j; char str

45、115; while(1) j=address(v2,13,get1); top_seq1(s1,top); if(top=100) addr-; return; j=analysis_table2topj; if(j>0) action2(top,get1); else if(j<0) if(j=-1) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用A->id=E;归约"); pop(4); top_seq1(

46、s1,top); goto2(top,"A"); for(int i=0;i<m;i+) if(screamp(identifer1i.identiname,p0)&&(identifer1i.identitype!=NULL) change(str1,identifer1i.identiname); emit("=",E,"_",str1); push_seq2(s3,str1); else if(j=-2) out_seq1(s1);printf("tt");out_seq2(s2);pr

47、intf("tt");out_seq2(s3);printf("tt用E->E+T归约"); pop(3); top_seq1(s1,top); goto2(top,"E"); E1=E; E=newtemp(); emit("+",E1,T,E); push_seq2(s3,E); else if(j=-3) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt

48、用E->T归约"); pop(1); top_seq1(s1,top); goto2(top,"E"); E=T; push_seq2(s3,T); else if(j=-4) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用T->T*F归约"); pop(3); top_seq1(s1,top); goto2(top,"T"); T1=T; T=newtemp(); e

49、mit("*",T1,F,T); push_seq2(s3,T); else if(j=-5) out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用T->F归约"); pop(1); top_seq1(s1,top); goto2(top,"T"); T=F; push_seq2(s3,F); else if(j=-6) out_seq1(s1);printf("tt")

50、;out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用F->(E)归约"); pop(3); top_seq1(s1,top); goto2(top,"F"); F=E; push_seq2(s3,E); else if(j=-7) pnum=insaddr-2;num+; out_seq1(s1);printf("tt");out_seq2(s2);printf("tt");out_seq2(s3);printf("tt用F->id归约"); pop(1); top_seq1(s1,top); goto2(top,"F"); for(int i=0;i<m;i+) if(screamp(identifer1i.identiname,pnum-1)&&(identifer1i.identitype!=NULL) change(str1,identifer1i.identi