编译原理实验报告-3

编译原理实验报告专业：计算机科学与技术班级：1201学号：0909120225姓名：吴晓阳指导教师：张修如日期：2014.12.12实验一：词法分析实验目的和要求设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解。实验描述：通过对PL/0词法分析程序（GETSYM）的分析，并在此基础上按照附录A中给出的PL/0语言的语法描述，编写一个PL/0语言的词法分析程序。此程序应具有如下功能：输入为字符串（待进行词法分析的源程序），输出为单词串，即由（单词、类别）所组成的二元组序列。有一定检查错误的能力，例如发现2A这类不能作为单词的字符串。主要变量名说明：char*key[8]={"if","else","for","while","do","return","break","continue"};确定关键字char*border[6]={",",";","{","}","(",")"};确定界符char*arithmetic[4]={"+","-","*","/"};确定算术运算符char*relation[6]={"<","<=","=",">",">=","<>"};确定关系运算符程序清单：#include<stdio.h>#include<ctype.h>#include<stdlib.h>#include<string.h>#defineNULL0#include<iostream>usingnamespacestd;FILE*fp;charcbuffer;char*key[8]={"if","else","for","while","do","return","break","continue"};char*border[6]={",",";","{","}","(",")"};char*arithmetic[4]={"+","-","*","/"};char*relation[6]={"<","<=","=",">",">=","<>"};char*consts[20];char*label[20];intconstnum=0,labelnum=0;intsearch(charsearchchar[],intwordtype){ inti=0; switch(wordtype){ case1:{ for(i=0;i<=7;i++){ if(strcmp(key[i],searchchar)==0) return(i+1); } return0; } case2:{ for(i=0;i<=5;i++) { if(strcmp(border[i],searchchar)==0) return(i+1); } return(0); } case3:{ for(i=0;i<=3;i++) { if(strcmp(arithmetic[i],searchchar)==0){ return(i+1); } } return(0); } case4:{ for(i=0;i<=5;i++) { if(strcmp(relation[i],searchchar)==0) { return(i+1); } } return(0); } case5:{ for(i=0;i<=constnum;i++) { if(i!=constnum) { if(strcmp(consts[i],searchchar)==0) return(i+1); } } consts[i-1]=(char*)malloc(sizeof(searchchar)); strcpy(consts[i-1],searchchar); constnum++; return(i); } case6：{ for(i=0;i<=labelnum;i++) { if(i!=labelnum) { if(strcmp(label[i],searchchar)==0) return(i+1); } } label[i-1]=(char*)malloc(sizeof(searchchar)); strcpy(label[i-1],searchchar); labelnum++; return(i); } default: return0; }}charalphaprocess(charbuffer){ intatype;inti=-1;charalphatp[20];while((isalpha(buffer))||(isdigit(buffer))) { alphatp[++i]=buffer; buffer=fgetc(fp); }alphatp[i+1]='\0';if(atype=search(alphatp,1)) { printf("%8s(1,%d)\n",alphatp,atype-1); }else { atype=search(alphatp,6); printf("%8s(6,%d)\n",alphatp,atype-1); }return(buffer);chardigitprocess(charbuffer){ inti=-1;chardigittp[20];intdtype;while((isdigit(buffer))) { digittp[++i]=buffer; buffer=fgetc(fp); }digittp[i+1]='\0';dtype=search(digittp,5);printf("%8s(5,%d)\n",digittp,dtype-1);return(buffer);}charotherprocess(charbuffer){ inti=-1;charothertp[20];intotype,otypetp;othertp[0]=buffer;othertp[1]='\0';if(otype=search(othertp,3)) { printf("%8s(3,%d)\n",othertp,otype-1); buffer=fgetc(fp); gotoout; } if(otype=search(othertp,4)) { buffer=fgetc(fp); othertp[1]=buffer; othertp[2]='\0'; if(otypetp=search(othertp,4)){ buffer=fgetc(fp); } else{ othertp[1]='\0'; } printf("%8s(4,%d)\n",othertp,otype-1); gotoout; } if(buffer==':'){ buffer=fgetc(fp); if(buffer=='=') printf("%8s(2,2)\n",":="); buffer=fgetc(fp); gotoout; } else{ if(otype=search(othertp,2)) { printf("%8s(2,%d)\n",othertp,otype-1); buffer=fgetc(fp); gotoout; } } if((buffer!='\n')&&(buffer!='')&&(buffer!='\t')) { printf("%8cerror,notaword\n",buffer);} buffer=fgetc(fp);out:return(buffer);}voidmain(){ inti; for(i=0;i<=20;i++) { label[i]=NULL; consts[i]=NULL; } if((fp=fopen("example.c","r"))==NULL) printf("error!\n"); else { cbuffer=fgetc(fp); while(cbuffer!=EOF) { if(isalpha(cbuffer)) cbuffer=alphaprocess(cbuffer); elseif(isdigit(cbuffer)) cbuffer=digitprocess(cbuffer); else cbuffer=otherprocess(cbuffer); } printf("over!\n"); system("pause"); }}实验中用到的测试的example.c的文件内容#include<stdio.h>voidmian(){inta=10,b=5;if(a<b){ printf("aissmallerthanb");}elseif(a>b){ printf("aisbiggerthanb");}else{do{ a=b+a;b=a*b; break; }while(a==b) } return0;}程序运行结果：分析：程序中，用到了较多的数组和动态数组分配，和较多的循环判断，在动态内存分配时出现了较多的错误，而在关键字和单词的判定中，也出现了不可预知的错误和警告，通过设置断点和插入特殊变量标记法，发现问题并予以解决实验二、三语法分析实验目的和要求：设计、编制、调试一个典型的语法分析程序，实现对语法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。要求：（1）程序具有通用性。即所编制的LL（1）语法分析程序能够适用于不同文法以及各种输入单词串（为简单起见，可将单词串视为字符串），并能判断文法是否为LL（1）文法。（2）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词是否为该文法的句子，并要求输出分析过程实验描述：根据图4.1所示LL（1）分析法总控流程图，编写一个语法分析程序，该语法分析程序实现LL（1）算法的分析过程。读者可根据自己的能力情况，选择以下其中一项作为分析算法的输入：（1）直接输入根据已知文法构造的分析表M。（2）输入已知文法的集合FIRST（x）和FOLLOW（U），由程序自动生成该文法的分析表M。（3）输入已知文法，由程序自动生成该文法的分析表M。/*LL(1)分析法源程序*//*其相应文法为:E—>TGT—>FSG—>+FG|^S—>*FS|^F—>(E)|^*/charA[20];/*分析栈*/charB[20];/*剩余串*/charv1[20]={'i','+','*','(',')','#'};/*终结符*/charv2[20]={'E','G','T','S','F'};/*非终结符*/intj=0,b=0,top=0,l;/*L为输入串长度*/typedefstructtype/*产生式类型定义*/{ charorigin;/*大写字符*/ chararray[5];/*产生式右边字符*/ intlength;/*字符个数*/}type;typee,t,g,g1,s,s1,f,f1;/*结构体变量*/typeC[10][10];/*预测分析表*/程序清单：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>charA[20];/*分析栈*/charB[20];/*剩余串*/charv1[20]={'i','+','*','(',')','#'};/*终结符*/charv2[20]={'E','G','T','S','F'};/*非终结符*/intj=0,b=0,top=0,l;/*L为输入串长度*/typedefstructtype/*产生式类型定义*/{ charorigin;/*大写字符*/ chararray[5];/*产生式右边字符*/ intlength;/*字符个数*/}type;typee,t,g,g1,s,s1,f,f1;/*结构体变量*/typeC[10][10];/*预测分析表*/voidprint()/*输出分析栈*/{ inta;/*指针*/ for(a=0;a<=top+1;a++) printf("%c",A[a]); printf("\t\t");}/*print*/voidprint1()/*输出剩余串*/{ intj; for(j=0;j<b;j++)/*输出对齐符*/ printf(""); for(j=b;j<=l;j++) printf("%c",B[j]); printf("\t\t\t");}/*print1*/voidmain(){ intm,n,k=0,flag=0,finish=0; charch,x; typecha;/*用来接受C[m][n]*/ /*把文法产生式赋值结构体*/ e.origin='E'; strcpy(e.array,"TG"); e.length=2; t.origin='T'; strcpy(t.array,"FS"); t.length=2; g.origin='G'; strcpy(g.array,"+TG"); g.length=3; g1.origin='G'; g1.array[0]='^'; g1.length=1;s.origin='S'; strcpy(s.array,"*FS"); s.length=3; s1.origin='S'; s1.array[0]='^'; s1.length=1; f.origin='F'; strcpy(f.array,"(E)"); f.length=3; f1.origin='F'; f1.array[0]='i'; f1.length=1; for(m=0;m<=4;m++)/*初始化分析表*/ for(n=0;n<=5;n++) C[m][n].origin='N';/*全部赋为空*//*填充分析表*/C[0][0]=e;C[0][3]=e;C[1][1]=g;C[1][4]=g1;C[1][5]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;C[4][0]=f1;C[4][3]=f;printf("提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,\n");printf("请输入要分析的字符串:");do/*读入分析串*/{ scanf("%c",&ch); if((ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')) { printf("输入串中有非法字符\n"); exit(1); } B[j]=ch; j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#';A[++top]='E';/*'#','E'进栈*/printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n");do{ x=A[top--];/*x为当前栈顶字符*/printf("%d",k++);printf("\t\t");for(j=0;j<=5;j++)/*判断是否为终结符*/ if(x==v1[j]) { flag=1; break; } if(flag==1)/*如果是终结符*/ { if(x=='#') { finish=1;/*结束标记*/ print(); print1(); printf("acc!\n");/*接受*/ //getchar(); getchar(); exit(1); }/*if*/ if(x==ch) {print(); print1(); printf("%c匹配\n",ch); ch=B[++b];/*下一个输入字符*/ flag=0;/*恢复标记*/ }/*if*/ else/*出错处理*/ {print(); print1(); printf("%c出错\n",ch);/*输出出错终结符*/ exit(1); }/*else*/ }/*if*/ else/*非终结符处理*/ {for(j=0;j<=4;j++) if(x==v2[j]) { m=j;/*行号*/ break; } for(j=0;j<=5;j++) if(ch==v1[j]) { n=j;/*列号*/ break; } cha=C[m][n]; if(cha.origin!='N')/*判断是否为空*/ { print(); print1(); printf("%c->",cha.origin);/*输出产生式*/ for(j=0;j<cha.length;j++) printf("%c",cha.array[j]); printf("\n"); for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/ A[++top]=cha.array[j]; if(A[top]=='^')/*为空则不进栈*/ top--; }/*if*/ else/*出错处理*/ {print(); print1(); printf("%c出错\n",x);/*输出出错非终结符*/ exit(1); }/*else*/ }/*else*/}while(finish==0);}/*main*/实验5运行结果当输入i+i*i#后分析：此程序设计的只是处理特定的字符，而当输入其他字符时，程序会崩溃，经借鉴实验指导书的代码及个人理解，采取中间插入“监视”变量的方法，确定错误点。实验三中间代码生成一．实验目的和内容：掌握中间代码的四种形式逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。三元式：形式序号：（op,arg1,arg2）四元式：形式（op,arg1,arg2,result）二、实验设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。程序代码：//这是一个由中缀式生成后缀式的程序#include<iostream.h>#include<string.h>#include<math.h>#include<ctype.h>#definemaxbuffer64voidmain(){chardisplay_out(charout_ch[maxbuffer],charch[32]);//intcaculate_array(charout_ch[32]);staticinti=0;staticintj=0;charch[maxbuffer],s[maxbuffer],out[maxbuffer];cout<<"请输入中缀表达式:";cin>>ch;for(i=0;i<maxbuffer;i++){out[i]=ch[i];}cout<<"请确认您输入的表达式：";while(out[j]!='#'){cout<<out[j];j++;}cout<<'#'<<endl;display_out(s,out);//caculate_array;}chardisplay_out