广药编译原理实验

1、实验一：消去C、C+程序中的注释实验类型：验证一、实验目的掌握C语言文件的基本操作，消除源C语言程序中的注释，为以后的编译提供方便。二、实验内容注释对于高级语言程序设计可以提高程序的可阅读性，但是对于编译系统而言，注释是没有实际意义的，所以编译系统在预编译阶段首先就要去掉注释。在VC中有两种注释，即单行注释，由/引入到行未，由/*.*/所包围的注释。要求去掉VC中这两种注释而不改变程序的其它部分。三、实验原理或算法算法原理：逐字符读入源程序，并判断相邻2个字符是否为/或/*或*/，如果不是，则直接将读入的字符写入新文件中；如果是，则跳过注释部分。四、程序清单在VC6.0下程序清单：/削除单行注

2、释与多行注释即/与/*.*/#includestdio.h#includestdlib.hmain()FILE*fp1,*fp2;char ch1,ch2,ch3,ch4,flag=0; if(fp1=fopen(D:Hxjb.c,r)=NULL)/ input.cpp为任意带注释的C程序 printf(file cannot be openedn);exit(1);if(fp2=fopen(D:Hxjb1.c,w)=NULL)printf(file cannot be writedn);exit(1);/fgetc是用来从文件中读取内容的ch1=fgetc(fp1);ch2=fgetc(fp

3、1);/feof为输入输出函数,检查文件是否结束,如结束,则返回非零值,否则返回0。while(!feof(fp1)/文件未结束时feof(fp1)=0;反之为1 if(ch1=/)if(ch2=*|ch2=/)if(ch2=*)ch3=fgetc(fp1);ch4=fgetc(fp1);while(!(ch3=*& ch4=/)&!feof(fp1)ch3=ch4;ch4=fgetc(fp1);ch2=fgetc(fp1);if(ch2=/)while(ch2=fgetc(fp1)!=10);elsefputc(ch1,fp2);/ fputc函数的功能是把一个字符写入指定的文件中elsef

4、putc(ch1,fp2);ch1=ch2;ch2=fgetc(fp1);fputc(ch1,fp2);fclose(fp1);fclose(fp2);return 1;五、实验结果分析比对源文件和产生的新文件，对照验证程序所产生的结果。答：程序byyl1.c运行结果截图如下：测试程序b.c如下：生成程序b1.c如下：显然，通过文件b.c和b1.c的截图对比，可见b1.c中少了b.c中的单行注释/与多行注释/*.*/，而其他部分不变。故程序的作用是读入源程序中的字符，削除其中的单行注释与多行注释，产生一个新文件。六、思考题（1）将输入输出文件改成可由键盘输入的文件名。答：改写程序byyl12.

5、c如下：#includestdio.h#includestdlib.hmain()FILE*fp1,*fp2;char ch1,ch2,ch3,ch4,flag=0; char fname20;printf(请输入文件名：n);scanf(%s,fname);/输入文件名if(fp1=fopen(fname,r)=NULL)/打开输入的文件名的文件printf(file cannot be openedn);exit(1);if(fp2=fopen(D:Hxjb1.c,w)=NULL)/新建文件b1printf(file cannot be writedn);exit(1);/fgetc是用来

6、从文件中读取内容的ch1=fgetc(fp1);ch2=fgetc(fp1);/feof输入输出函数,检查文件是否结束,如结束,则返回非零值,否则返回0 while(!feof(fp1)/文件未结束时feof(fp1)=0;反之为1 if(ch1=/)if(ch2=*|ch2=/)if(ch2=*)ch3=fgetc(fp1);ch4=fgetc(fp1);while(!(ch3=*& ch4=/)&!feof(fp1)ch3=ch4;ch4=fgetc(fp1);ch2=fgetc(fp1);if(ch2=/)while(ch2=fgetc(fp1)!=10);elsefputc(ch1,f

7、p2);/ fputc函数的功能是把一个字符写入指定的文件中elsefputc(ch1,fp2);ch1=ch2;ch2=fgetc(fp1);fputc(ch1,fp2);fclose(fp1);fclose(fp2);return 1;程序运行结果如下：输入要打开的文件名：源文件b.c：生成文件b1.c：（2）如果在字符串中出现连续的/或/*或*/则不应做处理，请修改上面的程序。答：程序byyl13.cpp如下：#include stdio.h#include stringchar fsm8128;void initfsm() const int line_len=sizeof(char)

8、*128;memset(fsm0,0,line_len); memset(fsm1,0,line_len);memset(fsm2,2,line_len); memset(fsm3,3,line_len); memset(fsm4,3,line_len); memset(fsm5,5,line_len); memset(fsm6,5,line_len); memset(fsm7,0,line_len); fsm0/=1; fsm0=5; fsm1/=2; fsm1*=3; fsm1=5; fsm2n=7; fsm3*=4; fsm4/=7; fsm4*=4; fsm5=0; fsm5=6; f

9、sm7/=1; fsm7=5;int main() int state=0; char c; std:string s; FILE *fin=fopen(D:Hxja.c,r); FILE *fout=fopen(D:Hxja1.c,w); initfsm(); while(fscanf(fin,%c,&c)!=EOF) state=fsmstatec; s+=c; switch(state) case 0: fprintf(fout,%s,s.c_str(); s=; break; case 7: s=; if(c=n) fputc(c,fout); break; fclose(fin);

10、fclose(fout); return 0; 源文件a.c如下：生成文件a1.c如下：两张截图对比可见程序对在输出的符号串中出现连续的/或/*或*/不做处理，而删除了注释内容。实验二：词法分析实验类型：综合一、实验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。二、实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

11、三、实验原理或算法1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、单词的BNF表示- -| - - |- +- - - =3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a=”或“ab”,当前字符为“”，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符“”或“b”，这时可知应将“”解释为大于或大于等于运算符。但此时，超前读了一个字符“

12、b”，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、编程思路这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。5、单词种别码要求：识别保留字：if、int、for、while、do、return、break、continue；单

13、词种别码为1。 分隔符包括：,、;、(、)； 单词种别码为2。运算符包括：+、-、*、/、=、；单词种别码为3。关系运算符：、=、=、!= ；单词种别码为4。标识符；单词种别码为5。常数为无符号整形数；单词种别码为6。四、程序清单#include #include #include #include #define NULL 0FILE *fp;char cbuffer;char *key8=if,else,for,while,int,return,break,continue;char *border6=,;,(,);char *arithmetic5=+,-,*,/,=;char *rel

14、ation6=,=,!=;char *consts20;char *label20;int constnum=0,labelnum=0;int search(char searchchar,int wordtype)int i=0;switch (wordtype)case 1:for (i=0;i=7;i+)if (strcmp(keyi,searchchar)=0) return(i+1);return 0;case 2:for (i=0;i=5;i+)if (strcmp(borderi,searchchar)=0) return(i+1);return(0);case 3:for (i

15、=0;i=4;i+)if (strcmp(arithmetici,searchchar)=0) return(i+1); return(0);case 4:for (i=0;i=5;i+)if(strcmp(relationi,searchchar)=0) return(i+1); return(0);case 5:for (i=0;iconstnum;i+)if(strcmp(constsi,searchchar)=0) return(i+1); constsi=(char *)malloc(sizeof(searchchar);strcpy(constsi,searchchar);cons

16、tnum+;return(i+1);case 6:for (i=0;ilabelnum;i+)if (strcmp(labeli,searchchar)=0) return(i+1); labeli=(char *)malloc(sizeof(searchchar);strcpy(labeli,searchchar);labelnum+;return(i+1);char alphaprocess(char buffer)/字母开头串的处理（可能是保留字或标识符）int atype;int i=-1;char alphatp20;while (isalpha(buffer)|(isdigit(b

17、uffer) alphatp+i=buffer;buffer=fgetc(fp);alphatpi+1=0;/printf(%s,search=%d,alphatp,search(alphatp,1); if (atype=search(alphatp,1)printf(%s,1,%d)n,alphatp,atype); elseatype=search(alphatp,6);printf(%s,6,%d)n,alphatp,atype); return(buffer);char digitprocess(char buffer) /常量串的处理int i=-1;char digittp20;

18、int dtype;while (isdigit(buffer)digittp+i=buffer;buffer=fgetc(fp);digittpi+1=0;dtype=search(digittp,5);printf(%s,5,%d)n,digittp,dtype);return(buffer);char otherprocess(char buffer) /进行其它符号的处理 int i=-1;char othertp20;int otype,otypetp;othertp0=buffer;othertp1=0;if (otype=search(othertp,3)printf(%s,3,

19、%d)n,othertp,otype);buffer=fgetc(fp);goto out;if (otype=search(othertp,4)buffer=fgetc(fp);othertp1=buffer;othertp2=0;if (otypetp=search(othertp,4) printf(%s,4,%d)n,othertp,otypetp); goto out;elseothertp1=0;printf(%s,4,%d)n,othertp,otype); goto out;if (buffer=:)buffer=fgetc(fp);if (buffer=)printf(:=

20、(2,2)n);buffer=fgetc(fp);goto out;elseif (otype=search(othertp,2)printf(%s,2,%d)n,othertp,otype); buffer=fgetc(fp);goto out;if (buffer!=n)&(buffer!= )printf(%c error,not a wordn,buffer);buffer=fgetc(fp);out: return(buffer);void main()int i;for (i=0;iE+T|T T-T*F|F F-(E)| 所生成的句子进行LL（1）分析，构造其分析程序。三、实验原

21、理或算法1、改造文法：消除左递归、提取左因子 将文法改造为： ETE E+TE| TFT T*FT|F (E)|i2、 求出firstt和follow FIRST()的 构造：设(VNVT)*，=X1X2Xn，FIRST()：（1）若=，则FIRST()=；（2）若，则FIRST() FIRST(X)； （3）若X1X2Xi1* , 则：FIRST(Xi) FIRST(); （4）若X1X2Xn * , 则 FIRST()对于X(VNVT），FIRST(X) 的构造: （1）若X VT，则FIRST(X)=X；（2）若X VN，且有产生式Xa，a VT ，则：aFIRST(X)，如果X ，那么

22、FIRST(X)；（3）若有产生式XY,Y VN ,则：FIRST(Y) FIRST(X)；（4）如果有产生式XY1Y2YK，其中Y1，Y2，Yi1 VN 且Y1Y2Yi1* , 则FIRST(Yi) FIRST(X)；（5）若Y1Y2YK * ，则 FIRST(X)。FOLLOW(U) 的 构造：（1）# FOLLOW(S)（2）如果有产生式AxUy，那么FIRST(y) FOLLOW(U)。（3）如果有产生式AxU 或则 AxUy 且y*，那么FOLLOW(A) FOLLOW(U) 3、LL（1）文法的判定：对于文法G 的每一个非终结符U 的产生式：U1|2|n 。如果文法G 是一个LL(

23、1) 文法，则有SELECT(Ui)SELECT(Uj)= (ij，i，j=1，2，n)。4、SELECT 集的构造：SELECT(U)= FIRST(), 当 不空 FIRST()FOLLOW(U), 当 为空对于上面的方法可以得到：first（E）= (,ifirst（ E）=+, first（T）=*, follow(E)=follow(E)= ),# follow(T)=follow(T)=+, ),# follow(F)=*,+,),# （3） 构造预测分析表 5、LL（1）分析表构造算法：对于每个产生式U，执行下一步骤：1、对于每个终结符号：aFIRST()，MU，a=U.2、如果

24、eFIRST( )，对于每个终结符号：bFOLLOW(U)，MU，b=U。3、将其它未定义的分析元素置为ERROR。预测分析表i+*()#ETETEE+TETFTFTT*FTFi(E)6、自下而上分析技术：从输入符号串出发，试图把它规约为识别符号。自下而上分析技术是一种“移进归约”法。从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进归约”方法。四、程序清单/文法：E-E+T|T T-T*F|F F-(E)|i/

25、根据预测分析表MA，a对输入串进行自上而下的语法分析程序 /已知预测分析表MA，a和输入串/判别输入串是否为文法的句子，并生成预测分析步骤#include #include #include #includeusing namespace std;char Vn=E,e,T,t,F; /定义文法的非终结符，由小写字母e表示E char Vt=i,+,*,(,),#; /定义文法的终结符 int LENVt=sizeof(Vt);void showstack(stack st) /从栈底开始显示栈中的内容 int i,j;char ch100; j=st.size();for(i=0;i=0;i

26、-) coutchi; st.push(chi); int find(char c,char array,int n)/查找函数，返回布尔值 int i;int flag=0;for(i=0;in;i+) if(c=arrayi)flag=1; return flag; int location(char c,char array) /定位函数,指出字符所在位置，即将字母转换为数组下标值 int i;for(i=0;c!=arrayi;i+); return i; void error() cout 出错!endl; void analyse(char Vn,char Vt,string M5

27、6,string str) int i,j,p,q,h,flag=1; char a,X;stack st; /定义堆栈st.push(#); st.push(Vn0); /#与识别符号入栈j=0; /j指向输入串的指针 h=1; a=strj;cout步骤 分析栈 剩余输入串 所用产生式endl; while(flag=1) couth ; /显示步骤 h+;showstack(st); /显示分析栈中内容 cout ;for(i=j;istr.size();i+) coutstri; /显示剩余字符串X=st.top(); /取栈顶符号放入X if(find(X,Vt,LENVt)=1)

28、/X是终结符if(X=a) /分析栈的栈顶元素和剩余输入串的第一个元素相比较 if (X!=#) cout X匹配endl;st.pop(); a=str+j; /读入输入串的下一字符 else cout 接受!endlendl; flag=0; else error();break; else p=location(X,Vn); /实现下标的转换（非终结符转换为行下标） q=location(a,Vt); /实现下标的转换（终结符转换为列下标）string S1(NULL),S2(null); if(Mpq=S1 | Mpq=S2) /查找二维数组中的产生式 error();break; /

29、对应项为空，则出错 else string str0=Mpq; cout Xstr0=0;i-)st.push(str0i);/产生式右端逆序进栈 main()string M56=Te ,NULL,NULL,Te, NULL,NULL,NULL,+Te ,NULL,NULL,$, $,Ft,NULL,NULL,Ft, NULL,NULL,NULL,$, *Ft, NULL,$, $,i,NULL,NULL,(E), NULL,NULL; /预测分析表j string str;int errflag,i;coutE+T|T T-T*F|F F-(E)|iendl;cout请输入分析串（以#结束

30、）：str;for(i=0;istr.size();i+)if(!find(stri,Vt,LENVt) cout输入串中包含有非终结符stri(输入错误)!endl; errflag=1;while(errflag=1); /判断输入串的合法性analyse(Vn, Vt, M,str);return 0;5、 实验结果分析输入i+i*(i+i)#,请给出结果截图与分析答：程序byyl3.cpp运行结果如下：输入i+i*(i+i)#，结果如下：由上图中的分析栈和剩余输入串可见栈的变化，把“#”和文法开始符压入进栈，产生式右部为反序进栈。 思考:如何改写程序，实现first集和follow集的

31、自动生成算法、预测分析表的构造算法？答：程序byyl32.cpp实现first集和follow集如下：#include #include #include #include#includeusing namespace std;char Vn=E,e,T,t,F; /定义文法的非终结符，由小写字母e表示E char Vt=i,+,*,(,),#; /定义文法的终结符 int LENVt=sizeof(Vt);struct define /产生式 char left;string right; ; int N,K1=0,K2=0; char B; struct define *p=new def

32、ine10; bool find(char b) /查找是否有产生空的产生式 int i;for(i=0;iN;i+) if(b=pi.left & pi.right0=) return true; return false; bool findfo(char b) /查找是否有产生空的产生式 int i; for(i=0;iN;i+) if(b=pi.left & pi.right0=) return true; return false; string first(char b) /求解Frist集 int i,index; queue pos; string s,rights; for(i=0;iN;i+) if(b=pi.left) pos.push(i); while(!pos.empty() if(!(ppos.front