广药编译原理实验

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

2、释与多行注释即/与/*.*/#include"stdio.h"#include"stdlib.h"main()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)

3、printf("file cannot be writedn");exit(1);/fgetc是用来从文件中读取内容的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='*&

4、#39;&& ch4='/')&&!feof(fp1)ch3=ch4;ch4=fgetc(fp1);ch2=fgetc(fp1);if(ch2='/')while(ch2=fgetc(fp1)!=10);elsefputc(ch1,fp2);/ fputc函数的功能是把一个字符写入指定的文件中elsefputc(ch1,fp2);ch1=ch2;ch2=fgetc(fp1);fputc(ch1,fp2);fclose(fp1);fclose(fp2);return 1;五、实验结果分析比对源文件和产生的新文件，对照验证程序所产生的

5、结果。答：程序byyl1.c运行结果截图如下：测试程序b.c如下：生成程序b1.c如下：显然，通过文件b.c和b1.c的截图对比，可见b1.c中少了b.c中的单行注释/与多行注释/*.*/，而其他部分不变。故程序的作用是读入源程序中的字符，削除其中的单行注释与多行注释，产生一个新文件。六、思考题（1）将输入输出文件改成可由键盘输入的文件名。答：改写程序byyl12.c如下：#include"stdio.h"#include"stdlib.h"main()FILE*fp1,*fp2;char ch1,ch2,ch3,ch4,flag=0; char fna

6、me20;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是用来从文件中读取内容

7、的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(

8、fp1);ch2=fgetc(fp1);if(ch2='/')while(ch2=fgetc(fp1)!=10);elsefputc(ch1,fp2);/ 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 &

9、quot;stdio.h"#include "string"char fsm8128;void initfsm() const int line_len=sizeof(char)*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,lin

10、e_len); fsm0'/'=1; fsm0'"'=5; fsm1'/'=2; fsm1'*'=3; fsm1'"'=5; fsm2'n'=7; fsm3'*'=4; fsm4'/'=7; fsm4'*'=4; fsm5'"'=0; fsm5''=6; fsm7'/'=1; fsm7'"'=5;int main() int state=0; cha

11、r 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=

12、"" if(c='n') fputc(c,fout); break; fclose(fin); fclose(fout); return 0; 源文件a.c如下：生成文件a1.c如下：两张截图对比可见程序对在输出的符号串中出现连续的/或/*或*/不做处理，而删除了注释内容。实验二：词法分析实验类型：综合一、实验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。二、实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数

13、、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。三、实验原理或算法1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、单词的BNF表示<标识符>-> <字母><字母数字串><字母数字串>-><字母><字母数字串>|<数字><字母数字串>|<下划线>&l

14、t;字母数字串>| <无符号整数>-> <数字><数字串><数字串>-> <数字><数字串> |<加法运算符>-> +<减法运算符>-> -<大于关系运算符>-> ><大于等于关系运算符>-> >=3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>=”或“a>b”,当前字符为“>”，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符

15、是什么才能下结论。于是分析器读入下一个字符“”或“b”，这时可知应将“>”解释为大于或大于等于运算符。但此时，超前读了一个字符“b”，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4、编程思路这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常

16、数和所有标识符。5、单词种别码要求：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。 分隔符包括：,、;、(、)； 单词种别码为2。运算符包括：+、-、*、/、=、；单词种别码为3。关系运算符：>、<、=、>=、<=、!= ；单词种别码为4。标识符；单词种别码为5。常数为无符号整形数；单词种别码为6。四、程序清单#include <stdio.h>#include <ctype.h>#include <stdlib.h>#include <string.h>#

17、define NULL 0FILE *fp;char cbuffer;char *key8="if","else","for","while","int","return","break","continue"char *border6=",","","","","(",")"char *arithmetic5=&qu

18、ot;+","-","*","/","="char *relation6="<","<=","=",">",">=","!="char *consts20;char *label20;int constnum=0,labelnum=0;int search(char searchchar,int wordtype)int i=0;switch (wordtype)

19、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=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,sea

20、rchchar)=0) return(i+1); return(0);case 5:for (i=0;i<constnum;i+)if(strcmp(constsi,searchchar)=0) return(i+1); constsi=(char *)malloc(sizeof(searchchar);strcpy(constsi,searchchar);constnum+;return(i+1);case 6:for (i=0;i<labelnum;i+)if (strcmp(labeli,searchchar)=0) return(i+1); labeli=(char *)m

21、alloc(sizeof(searchchar);strcpy(labeli,searchchar);labelnum+;return(i+1);char alphaprocess(char buffer)/字母开头串的处理（可能是保留字或标识符）int atype;int i=-1;char alphatp20;while (isalpha(buffer)|(isdigit(buffer) alphatp+i=buffer;buffer=fgetc(fp);alphatpi+1='0'/printf("%s,search=%d",alphatp,searc

22、h(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;int dtype;while (isdigit(buffer)digittp+i=buffer;buffer=fgetc(

23、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,%d)n",othertp,otype

24、);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=':')buf

25、fer=fgetc(fp);if (buffer='=')printf(":= (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);b

26、uffer=fgetc(fp);out: return(buffer);void main()int i;for (i=0;i<=20;i+)labeli=NULL;constsi=NULL;if (fp=fopen("D:Hxjc.c","r")=NULL) printf("Open File Error!");elseprintf("输出格式为：(单词，类别，位置)n"); cbuffer = fgetc(fp);while (cbuffer!=EOF)if (isalpha(cbuffer)cbuffe

27、r=alphaprocess(cbuffer); elseif (isdigit(cbuffer)cbuffer=digitprocess(cbuffer); else cbuffer=otherprocess(cbuffer); printf("Anysis Endn");getchar();五、实验结果分析如源程序为C语言。输入如下一段：main() int a,b;a = 10;b = a + 20;程序运行结果为？答：程序byyl2.c运行实验结果如下：思考题：对于一个真正的系统应该怎么完善该程序？答：这个程序只是可以通过一定的方法将语素（即英语单词和数字符号）从输

28、入字符串中分割出来，而语素只是一类字符构成的字符串（字符序列）。要构建单词，需要第二阶段的评估器（Evaluator）。评估器根据语素中的字符序列生成一个“值”，这个“值”和语素的类型便构成了可以送入语法分析器的单词。在上面，我们并没有很好的显示这些“值”，所以要完善的就是这部分。一些诸如括号的语素并没有“值”，评估器函数便可以什么都不返回。整数、标识符、字符串的评估器则要复杂的多。评估器有时会抑制语素，被抑制的语素（例如空白语素和注释语素）随后不会被送入语法分析器。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行，比如，对标识符来说，还需要记载它的类别、层次还有其它属

29、性。实验三.词法分析程序LL（1）实验类型：设计 一、实验目的根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。二、实验内容对文法：E->E+T|T T->T*F|F F->(E)| 所生成的句子进行LL（1）分析，构造其分析程序。三、实验原理或算法1、改造文法：消除左递归、提取左因子 将文法改造为： E>TE E>+TE| T>FT T>*FT|F> (E)|i2、 求出firstt和follow FIRST()的 构造：设(VNVT)*，=X1X2Xn，FIRST

30、()：（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 ，那么FIRST(X)；（3）若有产生式XY,Y VN ,则：FIRST(Y) FIRST(X)；（4）如果有产生式XY1Y2YK，其中Y1，Y2，Yi1 VN 且Y1Y2Yi1* , 则FIRST(Yi) FIRST(X)；

31、（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(1) 文法，则有SELECT(Ui)SELECT(Uj)= (ij，i，j=1，2，n)。4、SELECT 集的构造：SELECT(U)= FIRST(), 当 不空 FIRST()FOLLOW(U), 当 为空对于上面

32、的方法可以得到：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、如果eFIRST( )，对于每个终结符号：bFOLLOW(U)，MU，b=U。3、将其它未定义的分析元素置为ERROR。预测分析表i+*()#ETETEE+TETFTFTT*FTFi(E)6、自下而上分析技术：从输入符号串出

33、发，试图把它规约为识别符号。自下而上分析技术是一种“移进归约”法。从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进归约”方法。四、程序清单/文法：E->E+T|T T->T*F|F F->(E)|i/根据预测分析表MA，a对输入串进行自上而下的语法分析程序 /已知预测分析表MA，a和输入串/判别输入串是否为文法的句子，并生成预测分析步骤#include<iostream> #inc

34、lude<stdio.h> #include<string> #include<stack>using namespace std;char Vn='E','e','T','t','F' /定义文法的非终结符，由小写字母e表示E char Vt='i','+','*','(',')','#' /定义文法的终结符 int LENVt=sizeof(Vt);void showstack(s

35、tack <char> st) /从栈底开始显示栈中的内容 int i,j;char ch100; j=st.size();for(i=0;i<j;i+) chi=st.top(); st.pop(); for(i=j-1;i>=0;i-) cout<<chi; st.push(chi); int find(char c,char array,int n)/查找函数，返回布尔值 int i;int flag=0;for(i=0;i<n;i+) if(c=arrayi)flag=1; return flag; int location(char c,ch

36、ar array) /定位函数,指出字符所在位置，即将字母转换为数组下标值 int i;for(i=0;c!=arrayi;i+); return i; void error() cout<<" 出错!"<<endl; void analyse(char Vn,char Vt,string M56,string str) int i,j,p,q,h,flag=1; char a,X;stack <char> st; /定义堆栈st.push('#'); st.push(Vn0); /#与识别符号入栈j=0; /j指向输入串

37、的指针 h=1; a=strj;cout<<"步骤 "<<"分析栈 "<<"剩余输入串 "<<" 所用产生式"<<endl; while(flag=1) cout<<h<<" " /显示步骤 h+;showstack(st); /显示分析栈中内容 cout<<" "for(i=j;i<str.size();i+) cout<<stri; /显示剩余字符串X=st.

38、top(); /取栈顶符号放入X if(find(X,Vt,LENVt)=1) /X是终结符if(X=a) /分析栈的栈顶元素和剩余输入串的第一个元素相比较 if (X!='#') cout<<" "<<X<<"匹配"<<endl;st.pop(); a=str+j; /读入输入串的下一字符 else cout<<" "<<"接受!"<<endl<<endl; flag=0; else error();b

39、reak; else p=location(X,Vn); /实现下标的转换（非终结符转换为行下标） q=location(a,Vt); /实现下标的转换（终结符转换为列下标）string S1("NULL"),S2("null"); if(Mpq=S1 | Mpq=S2) /查找二维数组中的产生式 error();break; /对应项为空，则出错 else string str0=Mpq; cout<<" "<<X<<"->"<<str0<<end

40、l; /显示对应的产生式 st.pop(); if(str0!="$") /$代表“空”字符for(i=str0.size()-1;i>=0;i-)st.push(str0i);/产生式右端逆序进栈 main()string M56="Te" ,"NULL","NULL","Te", "NULL","NULL","NULL","+Te" ,"NULL","NULL",&q

41、uot;$", "$","Ft","NULL","NULL","Ft", "NULL","NULL","NULL","$", "*Ft", "NULL","$", "$","i","NULL","NULL","(E)", "NULL&quo

42、t;,"NULL" /预测分析表j string str;int errflag,i;cout<<"文法：E->E+T|T T->T*F|F F->(E)|i"<<endl;cout<<"请输入分析串（以#结束）："<<endl;do errflag=0;cin>>str;for(i=0;i<str.size();i+)if(!find(stri,Vt,LENVt) cout<<"输入串中包含有非终结符"<<

43、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集的自动生成算法、预测分析表的构造算法？答：程序byyl32.cpp实现first集

44、和follow集如下：#include<iostream> #include<stdio.h> #include<string> #include<stack>#include<queue>using namespace std;char Vn='E','e','T','t','F' /定义文法的非终结符，由小写字母e表示E char Vt='i','+','*','(',')'

45、;,'#' /定义文法的终结符 int LENVt=sizeof(Vt);struct define /产生式 char left;string right; ; int N,K1=0,K2=0; char B; struct define *p=new define10; bool find(char b) /查找是否有产生空的产生式 int i;for(i=0;i<N;i+) if(b=pi.left && pi.right0='') return true; return false; bool findfo(char b) /查找是

46、否有产生空的产生式 int i; for(i=0;i<N;i+) if(b=pi.left && pi.right0='') return true; return false; string first(char b) /求解Frist集 int i,index; queue<int> pos; string s,rights; for(i=0;i<N;i+) if(b=pi.left) pos.push(i); while(!pos.empty() if(!(ppos.front().right0<='Z' && ppos.front().right0>='A') if(int)s.find(ppos.front().right0)=-1) s.append(1,ppos.front().right0); els