编译原理实验报告

编译方法实验报告实验1：扫描器的设计一、实验目的熟悉并实现一个扫描器（词法分析程序）。二、实验要求(1)设计扫描器的有限自动机（识别器）；(2)设计翻译、生成Token的算法（翻译器）；(3)编写代码并上机调试运行通过。·输入——源程序文件或源程序字符串；·输出——相应的Token序列；关键字表和界符表；符号表和常数表；三、实验步骤流程：初始化；打开用户源程序文件；while（文件未结束）{读入一行到w[i]，i=0;do//处理一行，每次处理一个单词{滤空格，直到第一个非空的w[i]；i--；s=1;//处理一个单词开始while（s!=0）//拼单词并生成相应Token{act(s);//执行qsif（s=11&&s=14）//一个单词处理结束break;i++;//getchar()s=find(s,w[i]);}if（s==0）词法错误；}while（w[i]!=换行符）；}关闭用户源程序文件；生成Token文件；输出关键字表；输出Token序列；输出符号表；输出常数表；有限自动机的状态转换图：eddd+|--1/+/-+①d②.③d④e⑤⑥d⑦d--1/+/-l/d-1/+/--1l⑧--1b⑨b⑩--1--1-其中：d为数字，l为字母，b为界符，-1代表其它符号（如在状态8处遇到了非字母或数字的其它符号，会变换到状态12）。关键字表和界符表：Program;Begin:End(Var)While,Do:=Repeat+Until-For*To/IfThen=Else===四、主要数据结构①状态转换矩阵：intaut[10][7]={2,0,0,0,8,9,15,2,3,5,11,0,0,11,4,0,0,0,0,0,0,4,0,5,11,0,0,11,7,0,0,6,0,0,0,7,0,0,0,0,0,0,7,0,0,11,0,0,11,12111314158,0,0,0,8,0,12,0,0,0,0,0,10,14,0,0,0,0,0,0,13};②关键字表：charkeywords[30][12]={“program”,”begin”,”end”,”var”,”while”,”do”,”repeat”,”until”,”for”,”to”,”if”,”then”,”else”,“;”,”:”,”(“,”)”,”,”,”:=”,”+”,”-“,”*”,”/”,””,”=”,”==”,“”,“=”};③符号表：charID[50][12];//表中存有源程序中的标识符④常数表：floatC[20];⑤其它变量：structtoken{intcode;intvalue};//Token结构structtokentok[100];//Token数组ints;//当前状态intn,p,m,e,t;//尾数值，指数值，小数位数，指数符号，类型floatnum;//常数值charw[50];//源程序缓冲区inti;//源程序指针,当前字符为w[i]charstrTOKEN[12];//当前已经识别出的单词五、实验核心代码intmain(intargc,char*argv[]){FILE*fp;ints;//当前状态*有限自动机中的状态fp=fopen(exa.txt,r);while(!feof(fp)){fgets(w,50,fp);i=0;//*处理一行do{printf(%c,w[i]);//测试显示每个token的首字母//*处理一个tokenwhile(w[i]=='')//滤空格i++;if(w[i]='a'&&w[i]='z')//判定单词类别*是字母（关键字或标识符）{ptr=col2;num_map=2;}elseif(w[i]='0'&&w[i]='9')//*是数字（常量的开头）{ptr=col1;num_map=4;}elseif(strchr(col3[0].str,w[i])==NULL)//*其他字符算为非法字符{printf(非法字符%c\n,w[i]);i++;continue;}else//界符{ptr=col3;num_map=1;}i--;//*向后退一个字符s=1;//开始处理一个单词while(s!=0){act(s);if(s=11&&s=14)//*判断是否是终止状态*是终止状态，则形成一个tokenbreak;i++;//getchar()*读取下一个字符s=find(s,w[i]);//状态转换}if(s==0){strTOKEN[i_str]='\0';printf(词法错误：%s\n,strTOKEN);}}while(w[i]!=10);}printf(关键字表：);//输出结果for(i=0;i30;i++)printf(%s,keywords[i]);printf(\n);printf(Token序列：);for(i=0;inum_token;i++)printf((%d,%d),tok[i].code,tok[i].value);printf(\n);printf(符号表：);for(i=0;inum_ID;i++)printf(%s,ID[i]);printf(\n);printf(常数表：);for(i=0;inum_C;i++)printf(%d,C[i]);printf(\n);fclose(fp);printf(HelloWorld!\n);return0;}//*状态转换后，达到新的状态之后，记录的变化voidact(ints){intcode;switch(s){case1:n=0;m=0;p=0;t=0;e=1;num=0;i_str=0;strTOKEN[i_str]='\0';//其它变量初始化break;case2:n=10*n+w[i]-48;break;case3:t=1;break;case4:n=10*n+w[i]-48;m++;break;case5:t=1;break;case6:if(w[i]=='-')e=-1;break;case7:p=10*p+w[i]-48;break;case8:strTOKEN[i_str++]=w[i];//将ch中的符号拼接到strTOKEN的尾部；break;case9:strTOKEN[i_str++]=w[i];//将ch中的符号拼接到strTOKEN的尾部；break;case10:strTOKEN[i_str++]=w[i];//将ch中的符号拼接到strTOKEN的尾部；break;case11:num=n*pow(10,e*p-m);//计算常数值tok[i_token].code=2;tok[i_token++].value=InsertConst(num);//生成常数Tokennum_token++;break;case12:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);//查关键字表if(code){tok[i_token].code=code;tok[i_token++].value=0;}//生成关键字Tokenelse{tok[i_token].code=1;tok[i_token++].value=InsertID(strTOKEN);}//生成标识符Tokennum_token++;break;case13:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);//查界符表if(code){tok[i_token].code=code;tok[i_token++].value=0;}//生成界符Tokenelse{strTOKEN[strlen(strTOKEN)-1]='\0';//单界符i--;code=Reserve(strTOKEN);//查界符表tok[i_token].code=code;tok[i_token++].value=0;//生成界符Token}num_token++;break;case14:strTOKEN[i_str]='\0';code=Reserve(strTOKEN);//查界符表tok[i_token].code=code;tok[i_token++].value=0;//生成界符Tokennum_token++;break;}}//*状态转换intfind(ints,charch){inti,col=7;structmap*p;p=ptr;for(i=0;inum_map;i++)if(strchr((p+i)-str,ch)){col=(p+i)-col;break;}returnaut[s][col];}//*向常量表中插入常量intInsertConst(doublenum){inti;for(i=0;inum_C;i++)if(num==C[i])returni;C[i]=(int)num;num_C++;returni;}intReserve(char*str){inti;for(i=0;inum_key;i++)if(!strcmp(keywords[i],str))return(i+3);return0;}//*向符号表中插入新的符号intInsertID(char*str){inti;for(i=0;inum_ID;i++)if(!strcmp(ID[i],str))//*符号已经存在，则返回地址returni;strcpy(ID[i],str);num_ID++;returni;}六、实验结果实验思考题：1.扫描器的任务是什么？答：词法分析程序又称扫描器，任务有：(1)识别单词——从用户的源程序中把单词分离出来;(2)翻译单词——把单词转换成机内表示，便于后续处理。2.扫描器、识别器、翻译器三者之间的关系是怎样的？答：扫描器、识别器、翻译器三者之间的关系是：扫描器的实现要通过识别器和翻译器1.为什么说有限自动机是词法分析的基础？答：因为词法分析的包括：识别---识别单词的有限自动机。和翻译---根据有限自动机所识别出的对象，完成从单词串到单词的TOKEN串的翻译。我们可以看出，不论是识别还是分析，都是应用有限自动机，所以可以说有限自动机是词法分析的基础。实验2：中间代码生成器的设计一、实验目的熟悉算术表达式的语法分析与中间代码生成原理。二、实验要求(1)设计语法制导翻译生成表达式的四元式的算法；(2)编写代码并上机调试运行通过。·输入——算术表达式·输出——语法分析结果相应的四元式序列(3)本实验已给出递归子程序法的四元式属性翻译文法的设计，鼓励学生在此基础上进行创新，即设计LL(1)分析法或LR(0)分析法的属性翻译文法，并根据这些属性翻译文法，使用扩展的语法分析器实现语法制导翻译。三、设计概要(1)算术表达式文法G(E)：EEω0T|TTTω1F|FFi|(E)(2)文法变换G’(E)ET{ω0T}TF{ω1F}Fi|(E)(3)属性翻译文法：ET{ω0“push(SYN,w)”T“QUAT”}TF{ω1“push(SYN,w)”F“QUAT”}Fi“push(SEM,entry(w))”|(E)其中：·push(SYN,w)—当前单词w入算符栈SYN;·push(SEM,entry(w))—当前w在符号表中的入口值压入语义栈SEM;·QUAT—生成四元式函数i．T=newtemp;ii．QT[j]=(SYN[k],SEM[s-1],SEM[s],T);j++;iii．pop(SYN,_);pop(SEM,_);pop(SEM,_);push(SEM,T);(4)递归下降子程序：·数据结构：SYN—算符栈；SEM—语义栈；E:入口T:入口TFnω0?nω1?yy出口push(SYN,w)出口push(SYN,w)read(w)QUATread(w)QUATTFF:入口主程序：ZE(?ni?nerrread(w)read(w)push(S