编译原理课后答案——第十一章小型编译程序ppt课件.ppt

第十一章 小型编译程序,11.1 高级语言到四元式的编译程序PAS11.2 四元式到汇编语言程序的编译程序COMPILER,11.1 高级语言到四元式的编译程序PAS,/*/* pas.c */* 高级语言到四元式 */*/,#includetdio.h#include string.h#defineACC-2/*/#define sy_if0#define sy_then1#define sy_else2,#define sy_while3#define sy_begin4#define sy_do5#define sy_end6#define a7#define semicolon8#define e9,#define jinghao10#define S11#define L12#define tempsy 15#define EA18 /*E and*/#define EO19 /*E or*/,#define plus34#define times36#define becomes38#define op_and39#define op_or40#define op_not41#define rop42#define lparent4#define rparent49#define ident 56#define intconst 57,/*/charch=0 ; /*当前字符*/int count=0;staticcharspelling10= ; /*存放识别的字*/staticcharline81= ; /*一行字符缓冲区*/char*pline ; /*字符缓冲区指针*/,staticcharntab110010;structntabint tc;int fc;ntab2200;int label=0;/*存放临时变量的表的定义 */,structrwordscharsp10;intsy;/*存放文件的结构*/struct rwords reswords10= if,sy_if,do,sy_do,else,sy_else,while,sy_while,then,sy_then,begin,sy_begin,end,sy_end,and,op_and,or,op_or,not,op_not;struct aaint sy1;int pos;buf1000;/*词法分析结果缓冲区*/,n;/*当前字符*/n1;/*当前表达式中的字符*/E;/*非终结符*/sstack100;/*符号栈*/ibuf100,stack1000;struct aa oth;,struct fourexpchar op10;struct aa arg1;struct aa arg2;intresult;fexp200;/*四元式的结构*/int ssp=0;/*指向sstack100*/,structaa*pbuf=buf;/*指向词法分析缓冲区*/int nlength=0;int lnum=0;/*源程序长度*/int tt1=0;FILE *cfile;FILE *mfile;,/*/int newt=0;/*临时变量*/int nxq=100;/*nxq指向下一个形成的四元式的地址*/int lr;int lr1;int sp=0;,/* 状态栈定义*/int stack1100;int sp1=0;/*状态栈1的定义*/int num=0;struct llint nxq1;int tc1;int fc1;labelmark10;,int labeltemp10;int pointmark=-1,pointtemp=-1;int sign=0;/*sign1，表达式为赋值语句；sign2，表达式为布尔表达式。*/*/static intaction1913=/*0*/2,-1,-1,3,4,-1,-1,5,-1,-1,-1,1,-1,/*1*/-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,ACC,-1,-1,/*2*/-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,/*3*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,-1,-1,/*4*/ 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,8,/*5*/ -1,-1,104,-1,-1,-1,104,-1,104,-1,104,-1,-1,/*6*/ -1,10,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*7*/ -1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,-1,-1,/*8*/ -1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1,-1,-1,/*9*/ -1,-1,-1,-1,-1,-1,105,-1,13,-1,-1,-1,-1,/*10*/ 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,14,-1,/*11*/ 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,15,-1,/*12*/ -1,-1,103,-1,-1,-1,103,-1,103,-1,103,-1,-1,/*13*/ 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,9,16,/*14*/ -1,-1,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*15*/ -1,-1,102,-1,-1,-1,102,-1,102,-1,102,-1,-1,/*16*/ -1,-1,-1,-1,-1,-1,106,-1,-1,-1,-1,-1,-1,/*17*/ 2,-1,-1,3,4,-1,-1,5,-1,-1,-1,18,-1,/*18*/ -1,-1,101,-1,-1,-1,101,-1,101,-1,101,-1,-1;,static int action1107=/*0*/ 3,-1,-1,2,-1,-1,1,/*1*/ -1,4,5,-1,-1,ACC,-1,/*2*/ 3,-1,-1,2,-1,-1,6,/*3*/ 104,104,104,104,104,104,-1,/*4*/ 3,-1,-1,2,-1,-1,7,/*5*/ 3,-1,-1,2,-1,-1,8,/*6*/ -1,4,5,-1,9,-1,-1,/*7*/ 101,101,5,101,101,101,-1,/*8*/ 102,102,102,102,102,102,-1,/*9*/ 103,103,103,103,103,103,-1;,static int action21611=/*0*/ 1,-1,4,-1,5,-1,-1,-1,13,7,8,/*1*/ -1,2,-1,101,-1,101,101,101,-1,-1,-1,/*2*/ 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/*3*/ -1,-1,-1,102,-1,102,102,102,-1,-1,-1,/*4*/ 1,-1,4,-1,5,-1,-1,-1,11,7,8,/*5*/1,-1,4,-1,5,-1,-1,-1,6,7,8,/*6*/-1,-1,-1,104,-1,9,10,104,-1,-1,-1,/*7*/1,-1,4,-1,5,-1,-1,-1,14,7,8,/*8*/1,-1,4,-1,5,-1,-1,-1,15,7,8,/*9*/105,-1,105,-1,105,-1,-1,105,-1,-1,-1,/*10*/107,-1,107,-1,107,-1,-1,107,-1,-1,-1,/*11*/-1,-1,-1,12,-1,9,10,-1,-1,-1,-1,/*12*/-1,103,-1,103,-1,103,103,103,-1,-1,-1,/*13*/-1,-1,-1,-1,-1,9,10,ACC,-1,-1,-1,/*14*/-1,-1,-1,106,-1,9,10,106,-1,-1,-1,/*15*/-1,-1,-1,108,-1,9,10,108,-1,-1,-1;/*从文件读一行到缓冲区*/,readline( )char ch1;pline=line;ch1=getc(cfile);while (ch1!= n)*pline=ch1;pline+;ch1=getc(cfile);,*pline=0;pline=line;/*从缓冲区读一个字符*/readch( )if (ch=0) readline( );lnum+;,ch=*pline;pline+;/*标志符和关键字的识别*/find(char spel )int ss1=0;int ii=0;while(ss1=0)&(iinlength),if (!strcmp(spel,ntab1ii) ss1=1;ii+;if (ss1=1) return ii-1;else return -1;,identifier( )int iii=0,j,k;int ss=0;k=0;dospellingk=ch;k+;readch( ); while(ch=a),pline-;spellingk= 0;while(ss=0),/*关键字匹配*/if(ss=1)bufcount.sy1=reswordsiii-1.sy;elsebufcount.sy1=ident;j=find(spelling);if (j=-1),bufcount.pos=tt1;strcpy(ntab1tt1,spelling);tt1+;nlength+;else bufcount.pos=j;count+;for(k=0;k10;k+) spellingk= ;,/*数字的识别*/number( )int ivalue=0;int digit;dodigit=ch-0;ivalue=ivalue*10+digit;readch( );while(ch=0),bufcount.sy1=intconst;bufcount.pos=ivalue;count+;pline-;/*扫描主函数*/scan( ),int i;while(ch!= )switch (ch)case :break;case a:case b:case c:,case d:case e:case f:case g:case h:case i:case j:case k:case l:case m:case n:case o:,case p:case q:case r:case s:case t:case u:case v:case w:case x:case y:case z:,identifier( );break;case 0:case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:number( );,break;case :readch( );if(ch=)bufcount.pos=0;else,if(ch=) bufcount.pos=4;elsebufcount.pos=1;pline-;bufcount.sy1=rop;count+;break;,case :readch( );if(ch=)bufcount.pos=2;elsebufcount.pos=3;pline-;,bufcount.sy1=rop;count+;break;case (:bufcount.sy1=lparent;count+;break;case ) :bufcount.sy1=rparent;count+;break;,case #:bufcount.sy1=jinghao;count+;break;case +:bufcount.sy1=plus;count+;break;,case *:bufcount.sy1=times;count+;break;case : :readch( );if (ch=)bufcount.sy1=becomes;count+;break;,case =:bufcount.sy1=rop;bufcount.pos=5;count+;break;case ; :bufcount.sy1=semicolon;count+;break;,readch( );bufcount.sy1=-1;/*/,readnu( )if (pbuf-sy1=0)n.sy1=pbuf-sy1;n.pos=pbuf-pos;pbuf+;,/*中间变量的生成*/newtemp( )newt+;return newt;/*生成四元式*/,gen(char op1 ,struct aa arg11,struct aa arg22,int result1)strcpy(fexpnxq.op,op1);fexpnxq.arg1.sy1=arg11.sy1;fexpnxq.arg1.pos=arg11.pos;fexpnxq.arg2.sy1=arg22.sy1;fexpnxq.arg2.pos=arg22.pos;fexpnxq.result=result1;nxq+;return nxq-1;,/*布尔表达式的匹配*/merg(int p1,int p2)int p;if(p2=0) return p1;elsep=p2;while(fexpp.result!=0) p=fexpp.result;fexpp.result=p1;return p2;,backpatch(int p,int t)int tempq;int q;q=p;while(q!=0)tempq=fexpq.result;fexpq.result=t;q=tempq;,/*/change1(int chan)switch (chan)case ident:case intconst:return 0;case plus:return 1;case times:return 2;,case lparent:return 3;case rparent:return 4;case jinghao:return 5;case tempsy:return 6;,change2(int chan)switch (chan)case ident:case intconst:return 0;case rop:return 1;case lparent:return 2;,case rparent:return 3;case op_not:return 4;case op_and:return 5;case op_or:return 6;case jinghao:return 7;,case tempsy:return 8;case EA:return 9;case EO:return 10;,/*赋值语句的分析*/lrparse1(int num)lr1=action1stack1sp1change1(n1.sy1);if (lr1=-1)printf(n算术表达式或赋值语句出错！n);getch( );exit(0);,if (lr1=0)sp1+;stack1sp1=lr1;if (n1.sy1!=tempsy)ssp+;num+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;,n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse1(num);if(lr1=100),gen(+,sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E-E+E*/,case 102:E.pos=newtemp( );gen(*,sstackssp-2,sstackssp,E.pos+100);ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E-E*E*/,case 103:E.pos=sstackssp-1.pos;ssp=ssp-2;sstackssp.sy1=tempsy;sstackssp.pos=E.pos;sp1=sp1-3;break;/*E-(E)*/,case 104:E.pos=sstackssp.pos;sp1-;break;/*E-i*/n1.sy1=tempsy; /*规约后为非终结符*/n1.pos=E.pos;lrparse1(num);,if (lr1=ACC),/*布尔表达式的分析*/lrparse2(int num)int templabel;lr1=action2stack1sp1change2(n1.sy1);if (lr1=-1) if (sign=2) printf(nwhile语句出错!n);if (sign=3) printf(nif语句出错!n);getch( );exit(0);,if (lr1=0)sp1+;stack1sp1=lr1;ssp+;sstackssp.sy1=n1.sy1;sstackssp.pos=n1.pos;if (n1.sy1!=tempsy),if(lr1=100),gen(jnz,sstackssp,oth,0);gen(j,oth,oth,0);sp1-;ssp-;label+;n1.sy1=tempsy;break;/*E-i*/,case 102:ntab2label.tc=nxq;ntab2label.fc=nxq+1;switch (sstackssp-1.pos)case 0:gen(j=,sstackssp-2,sstackssp,0);break;case 1:gen(j,sstackssp-2,sstackssp,0);break;,case 2:gen(j=,sstackssp-2,sstackssp,0);break;case 3:gen(j,sstackssp-2,sstackssp,0);break;case 4:gen(j,sstackssp-2,sstackssp,0);break;case 5:gen(j=,sstackssp-2,sstackssp,0);break;,gen(j,oth,oth,0);ssp=ssp-3;sp1=sp1-3;label+;n1.sy1=tempsy;break;/*E-i rop i*/,case 103:label=label-1;ssp=ssp-3;sp1=sp1-3;label+;n1.sy1=tempsy;break;/*E-(E)*/,case 104:label=label-1;templabel=ntab2label.tc;ntab2label.tc=ntab2label.fc;ntab2label.fc=templabel;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;/*E-not E*/,case 105:backpatch(ntab2label-1.tc,nxq);label=label-1;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=EA;break;/*EA-E(1)and*/,case 106:label=label-2;ntab2label.tc=ntab2label+1.tc;ntab2label.fc=merg(ntab2label.fc,ntab2label+1.fc);ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;/*E-EA E(2)*/,case 107:backpatch(ntab2label-1.fc,nxq);label=label-1;ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=EO;break;,case 108:label=label-2;ntab2label.fc=ntab2label+1.fc;ntab2label.tc=merg(ntab2label.tc,ntab2label+1.tc);ssp=ssp-2;sp1=sp1-2;label+;n1.sy1=tempsy;break;,lrparse2(num);if (lr1=ACC) return 1;/*测试字符是否为表达式中的值(不包括; )*/test(int value)switch (value)case intconst:case ident:case plus:case times:,case becomes:case lparent:case rparent:case rop:case op_and:case op_or:case op_not:return 1;default:return 0; ,/*/lrparse( )int i1=0;int num=0;/*指向表达式缓冲区*/if (test(n.sy1)if(stacksp.sy1=sy_while) sign=2;else if (stacksp.sy1=sy_if) sign=3;else sign=1;,doibufi1.sy1=n.sy1;ibufi1.pos=n.pos;readnu( );i1+;while(test(n.sy1);,/*把表达式放入缓冲区*/ibufi1.sy1=jinghao;pbuf-;/*指针后退1，需要吗？*/sstack0.sy1=jinghao;ssp=0;/*符号栈底的初始化*/if (sign=1),sp1=0;stack1sp1=0;/*状态栈1的栈底初始化*/num=2;/*指向:=*/n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse1(num);/*处理赋值语句*/n.sy1=a;/*当前文法符号置为a(赋值语句)*/,if (sign=2)|(sign=3)pointmark+;labelmarkpointmark.nxq1=nxq;sp1=0;stack1sp1=0;num=0;n1.sy1=ibufnum.sy1;n1.pos=ibufnum.pos;lrparse2(num);,labelmarkpointmark.tc1=ntab2label-1.tc;labelmarkpointmark.fc1=ntab2label-1.fc;/*处理布尔语句*/*在处理完E，要回填真值链*/backpatch(labelmarkpointmark.tc1,nxq);n.sy1=e;/*当前文法符号置为e(赋值语句)*/,lr=actionstacksp.posn.sy1;printf(stack%d=%dttn=%dttlr=%dn,sp,stacksp.pos,n.sy1,lr);if (lr=0)sp+;stacksp.pos=lr;stacksp.sy1=n.sy1;readnu( );lrparse( );,if (lr=100)switch (lr)case 100:break;/*S-S*/case 101:printf(S-if e then S then S else S 归约n);sp=sp-6;n.sy1=S;,/*归约完if后，填then后面的无条件转移语句*/fexplabeltemppointtemp.result=nxq;pointtemp-;if(stacksp.sy1=sy_then)gen(j,oth,oth,0);backpatch(labelmarkpointmark.fc1,nxq);pointtemp+;labeltemppointtemp=nxq-1;,pointmark-;if(stacksp.sy1=sy_do)gen(j,oth,oth,labelmarkpointmark.nxq1);backpatch(labelmarkpointmark.fc1,nxq);break;,/*S-if e then S then S else S*/case 102:printf(S-while e do S 归约n);sp=sp-4;n.sy1=S;pointmark-;if(stacksp.sy1=sy_do)gen(j,oth,oth,labelmarkpointmark.nxq1);backpatch(labelmarkpointmark.fc1,nxq);,if(stacksp.sy1=sy_then)gen(j,oth,oth,0);fexplabelmarkpointmark.fc1.result=nxq;pointtemp+;labeltemppointtemp=nxq-1;break;,/*S-while e do S*/case 103:printf(S-begin L end 归约n);sp=sp-3;n.sy1=S;if(stacksp.sy1=sy_then)gen(j,oth,oth,0);backpatch(labelmarkpointmark.fc1,nxq);pointtemp+;labeltemppointtemp=nxq-1;,if(stacksp.sy1=sy_do)gen(j,oth,oth,labelmarkpointmark.nxq1);backpatch(labelmarkpointmark.fc1,nxq);getch( );break;,/*S-begin L end*/case 104:printf(S-a 归约n);sp=sp-1;n.sy1=S;if(stacksp.sy1=sy_then)gen(j,oth,oth,0);backpatch(labelmarkpointmark.fc1,nxq);pointtemp+;labeltemppointtemp=nxq-1;,if(stacksp.sy1=sy_do)gen(j,oth,oth,labelmarkpointmark.nxq1);backpatch(labelmarkpointmark.fc1,nxq);break;/*S-a*/,case 105:printf(归约n);sp=sp-1;n.sy1=L;break;/*L-S*/,case 106:printf(L-S;L 归约n);sp=sp-3;n.sy1=L;break;/*L-S;L*/,getch( );pbuf-;lrparse( );if (lr=ACC) return ACC;/*disp1*/,disp1( )int temp1=0;printf(n*词法分析结果*n);for(temp1=0;temp1count;temp1+),printf(%dt%dn,buftemp1.sy1,buftemp1.pos);if (temp1=20)printf(Press any key to continue.n);getch( );getch ( );,/*/disp2()int temp1=100;printf(n*四元式分析结果*n);,for(temp1=100;temp1100) fprintf(mfile, n);fprintf(mfile, %dt,temp1);fprintf(mfile, (%st, ,fexptemp1.op);if (fexptemp1.arg1.sy1=ident)fprintf(mfile, %st, ,ntab1fexptemp1.arg1.pos);,else if (fexptemp1.arg1.sy1=tempsy)fprintf(mfile, T%dt, ,fexptemp1.arg1.pos);elseif(fexptemp1.arg1.sy1=intconst)fprintf(mfile, %dt, ,fexptemp1.arg1.pos);else fprintf(mfile, t, );,if (fexptemp1.arg2.sy1=ident)fprintf(mfile, %st, ,ntab1fexptemp1.arg2.pos);elseif (fexptemp1.arg2.sy1=tempsy)fprintf(mfile, T%dt, ,fexptemp1.arg2.pos);else,if(fexptemp1.arg2.sy1=intconst)fprintf(mfile, %dt, ,fexptemp1.arg2.pos);else fprintf(mfile, t, );,if (fexptemp1.op0!= j)if(fexptemp1.result=100)fprintf(mfile, T%dt) ,fexptemp1.result-100);else fprintf(mfile, %st) ,ntab1fexptemp1.result);,else fprintf(mfile, %dt) ,fexptemp1.result);if (temp1=20)printf(nPress any key to continue.n);getch( );,getch( );disp3( )int tttt;printf(nn程序总共%d行，产生了%d个二元式！n,lnum,count);getch( );printf(n*变量表*n);for(tttt=0;tttttt1;tttt+) printf(%dt%sn,tttt,ntab1tttt);getch();,/*主程序*/main()cfile=fopen(pas.dat, r); mfile=fopen(pas.med, w);/*打开c语言源文件*/readch( );/*从源文件读一个字符*/scan( );,/*词法分析*/disp1( );disp3( );stacksp.pos=0;stacksp.sy1=-1;/*初始化状态栈栈底*/stack1sp1=0;/*初始化状态栈栈底*/,oth.sy1=-1;printf(n*状态栈变化过程及规约顺序*n);readnu( );/*从二元式读一个字符*/lrparse( );getch( );/*四元式的分析*/disp2( );printf(n程序结束。谢谢使用！n);printf(COPYRIGHT BY Z.Y.P 2001.6.7);getch( );,11.2 四元式到汇编语言程序的编译程序COMPILER,1. COMPILER的组成 编译程序COMPILER由1个工程文件，5个 *.h 文件，6个 *.C 文件组成。 (1) 1个工程文件为 compiler.prj,(2) 5个 *.h 文件为 globals.h read.h symtab.h block.h cgen.h,(3) 6个*.C 文件为 main.c read.c symtab.c block.c code.c cgen.c,2. 工程文件/*/* compiler.prj */* 四元式到汇编工程文件 */*/,D:tc源程序main.cD:tc源程序read.cD:tc源程序symtab.cD:tc源程序block.cD:tc源程序code.cD:tc源程序cgen.c,3. *.h文件/*/* 文件: globals.h */*/,#ifndef _GLOBALS_H_#define _GLOBALS_H_#include #include #include #include #ifndef FALSE#define FALSE 0#endif,#ifndef TRUE#define TRUE 1#endif/*四元式的结构类型*/typedef struct MLanguage unsigned int line; char op4; char opv110; char opv210; char result10; struct MLanguage * next; *ml;,/*符号表每个元素的结构*/typedef struct VariableRec char name10; int regstats; int regnum; struct variableRec * next; * vr;,extern FILE* source; /* 中间代码的源文件 */extern FILE* code; /* 汇编语言的目标文件 */#endif/*/* 文件: read.h */* 读取中间语言源文件的接口。 */*/,#ifndef _READ_H_#define _READ_H_/*过程read_mlanguage读取源文件以指定格式输入到内存。*/void read_mlanguage( );#endif/*/* 文件：symtab.h */* 访问符号表的接口。 */*/,#ifndef _SYMTAB_H_#define _SYMTAB_H_/*过程st_insert把程序变量插入符号表。*/void st_insert( char name ,vr Table );/*过程insert根据变量是变量还是临时变量，然后执行st_insert过程 把不同的变量插入相应的符号表。*/void insert( char name );,/*建立符号表的函数，变量和临时变量保存在不同的符号表中。*/void buildsymtab( );/*在符号表中查找变量，返回所需变量在符号表中的地址。*/vr st_lookup(char name ,vr Table );/*判断是变量还是临时变量，然后在不同的符号表中查找*/vr lookup( char name );,/*建立数据段的主程序,临时变量不存入数据段。*/void create_dataseg( );#endif/*/* 文件: block.h */* 建立基本块的接口。 */*/,#ifndef _BLOCK_H_#define _BLOCK_H_/*过程create_basicblock为中间语言建立基本块，并按行号从小到大的顺序排列。*/void create_basicblock( );#endif/*/* 文件: cgen.h */* 执行中间语言的分析，调用相应的子程序 */* 来完成汇编代码的产生的接口。 */*/,#ifndef _CGEN_H_#define _CGEN_H_ /*过程codegen产生汇编目标语言的初始化程序段，*/*并调用相应的函数产生程序的数据段和代码段，*/*字符串变量codefile为目标文件的文件名，*/*用于在编译过程中作为注释在屏幕上打印出文件名。*/void codegen( char * codefile );#endif,4. *.c文件/*/* 文件: main.c */* 中间语言编译的主程序。 */*/#include globals.h#include read.h#include symtab.h#include block.h#include cgen.h,/* allocate global variables */FILE * source;FILE * code;int Error = FALSE;main( ) char filename20,* codefilename,ch ; /* 中间代码源文件名 */ printf(是否从键盘输入四元式(y/n)?: ); ch = getch(); if( ch != y ), printf(n请输入源文件的文件名：); scanf(%s,filename); if( strchr (filename, . ) = NULL ) strcat(filename, .med); source = fop