深圳大学编译原理实验报告蔡树彬实验一资料.docx
- 文档编号:13391905
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:28
- 大小:145.55KB
深圳大学编译原理实验报告蔡树彬实验一资料.docx
《深圳大学编译原理实验报告蔡树彬实验一资料.docx》由会员分享,可在线阅读,更多相关《深圳大学编译原理实验报告蔡树彬实验一资料.docx(28页珍藏版)》请在冰点文库上搜索。
深圳大学编译原理实验报告蔡树彬实验一资料
深圳大学实验报告
课程名称:
编译原理
实验项目名称:
文法分析方法及其应用
学院:
计算机与软件学院
专业:
软件工程
指导教师:
蔡树彬
报告人:
学号班级:
实验时间:
2015年9月16日至10月28日
实验报告提交时间:
2015年11月10日
教务处制
实验目的与要求:
目的:
针对分词、停用词过滤等文法分析应用问题,设计并实现相应的解决方案,再通过设计文法相关类族,以及实现文法化简等方法,既加深对抽象的文法、推导、语言等形式语言理论基础概念的理解与掌握,也加强对面向对象程序编写能力和计算思维的培养。
要求:
第一部分:
分词
输入:
输入是一个文本文件,里面的内容是符合某个语言语法、词法要求的源代码(语法可参考课本P104,包括语句表、for循环和赋值语句等),例如“position:
=initial+rate*60;”;
输出:
设计并实现对输入文件的处理(禁用正则表达式),以获得如下输出,输出是一个文本文件,对前面例子,里面内容是:
(标识符,position)
(赋值运算符,:
=)
(标识符,initial)
(加法运算符,+)
(标识符,rate)
(乘法运算符,*)
(整数,60)
(分隔符,;)
第二部分:
停用词过滤,分为“产生随机停用词”、“产生随机待过滤文本”和“过滤停用词”3个小实验。
产生随机停用词:
生成一个文件长度和单词平均长度可控的文本文件,要求字符集为26个字母,每行生产一个单词,每个单词的长度随机,全部单词的平均长度可控制,通常为4、5(非严格要求),总共输出的文件长度可控制。
产生随机待过滤文本:
生成一个文件大小和单词平均长度可控的文本文件,要求
字符集为26个字母+“”(空格)+“\r\n”(回车换行);从文件开始一直到结束,持续输出,不额外换行(除非遇到生成的\r\n),总共输出的文件大小可控制。
过滤停用词:
写一个程序,快速扫描待过滤文本,然后将待过滤文本中出现的所有停用词,替换为“**”,要求禁用正则表达式,不要误杀(例如,若停用词包括“abc”,那么“abcd”等不应该被误杀。
第三部分:
文法化简
设计文法类,实现对文法G[S]=(Vt,Vn,P,S)的文件读写,文法的文件表示形式以及内存表示形式可自定义。
本质上,文法就是3个集合+1个符号,重点(难点)是产生式集合如何处理。
文法的文本形式可根据自己需要自由定义。
在前述的基础上,实现文法化简的无用符号及无用产生式消除算法(即课本算法2.1、2.2)。
方法、步骤:
要完成本实验,依据实验要求进行分解,需要完成的实验步骤是:
1.如何读写文件?
读写文法文件内容,需要用到文件IO,查阅、复习文件IO操作。
写文件的方法包含在头文件include
:
out)对文件进行写。
读文件的方法包含在头文件include
2.如何分词?
第一部分实验要求进行分词,源代码中的单词可以分成3类,一类是约定的保留字,一类是普通标识符,最后一类是数字
2.1如何识别保留字?
2.2如何识别标识符?
2.3如何识别数字?
特别的,如果你有多种方法来识别这3类单词,那这些方法有何优缺点?
分析并作出你的选择。
首先将保留字和和标识符一一列举出来,创建保留字表和标识符表,然后对待识别文件进行分类(分成保留字、标识符、运算符、分隔符),然后逐一比对,最终不属于以上分类的就是数字。
识别保留字时,可以选择创建保留字及其名称的表,直接与保留字逐个比较,然而看起来没有将单词分成三类的感觉,而创建表来比较的话看起来要简洁很多,因此不用前者。
识别整数时也可以根据ASCLL码的值区间去判断,但是这种方法不太直观。
3.如何产生符合要求的随机停用词和待处理文本
第二部分实验要求先产生随机的停用词和待处理文本,主要是如何产生符合要求的这些词或文本?
3.1如何产生随机停用词?
3.2如何控制随机停用词的平均长度(而不是固定长度)?
3.3如何产生待处理文本中的“段落”?
3.4如何控制待处理文本的长度?
1.调用srand(time(0)),使得每次产生的随机数不同,定义一个string类型的字符串word,‘a’+rand()%26即可产生a-z的字母,然后将每次产生的字母添加进word中,即可产生随机停用词。
2.定义一个int变量length,用rand()函数随机确定length的取值范围,然后在循环中以length为判断条件即可生成所需平均长度的停用词。
3.建立的符号集中添加入”\r\n”即可产生段落。
4.定义一个int类型的变量len,用rand()函数随机确定len的取值范围,然后在产生停用词的循环外嵌套一个循环,以len为判断条件即可控制产生停用词的个数,即处理文本的长度。
4.如何过滤停用词
第二部分实验最后要求把待处理文本中出现的停用词替换为“**”,那你如何准确、快速判断出文本中的停用词?
通过定义两个指针变量,分别储存生成的停用词表和待处理文件,然后利用strcmp()函数对两者进行比较。
若在遇到空格回车换行之前全部一致,则用“*”代替待处理文件中的单词,最终输出处理后的单词。
尤其注意对最后一个单词的截断处理。
5.如何设计文法类?
文法类里面,有3个集合,1个特别的非终结符——开始符号。
集合应如何表示?
Set
也可直接采用数组等形式来表示,那种方法更好?
分析并做出你的设计。
类成员中,非终结符集合和终结符集合使用数组格式储存,这是一种常用的数据格式,它可以直接用下标的方式获取其中的数据,开始符号使用char类型,产生式集合同样使用了数组格式。
对于产生式集合,可以考虑使用了vector
选用数组,主要是因为其较为简单。
6.如何实现无用文法的化简算法?
算法2.1、2.2课本已经给出了说明,那你如何将算法说明变成代码?
有什么主要内容?
由于课本中提供了算法2.1、2.2的处理过程,因此在编程过程中基本的步骤是和课本上一样的,但是具体的实现过程却比课本上要复杂的多,比如求Vn,Vt和P时,课本上是直接将其置为空,然后向其添加内容,但代码实现的过程中,我们需要用到Vn,Vt和P来进行判断和筛选,所以只能通过新建临时的集合的方式,经过课本上的方法处理之后再临时的集合赋值给Vn、Vt和P。
在课本描述为重复进行的步骤中,我们需要用到循环,并且循环里面需要有判断语句甚至是嵌套另一个循环。
实验过程及内容:
实验过程及内容,处理代码设计说明、代码及其注释外,特别关注编程过程。
要求,至少有一张照片,照片上出现你(正面)+正在写的代码(电脑要有外观)
实验1_1代码:
#include
#include
#include
usingnamespacestd;
#defineN100
charstr[N];
stringKeyWord[N]={"int","if","else","for","while","return","main"};//仅列出常见关键字
stringsymbol1[N]={"+","-","*","/","%"};
stringsymbol2[N]={"!
","&","|","&&","||"};
stringsymbol3[N]={"<",">","==","<=",">="};
intGetClassify(charc);//分类函数
voidLexicalAnalyzer(strings,intk);//词法分析器
voidGetIdentifier(strings,intk);//标识符函数
voidGetOperator(strings,intk);//运算符函数
voidGetSeparator();//分隔符函数
intmain()
{
ifstreamfin("string.txt");
fin>>noskipws;//读取空白字符
intpos=0;
inti;
while(!
fin.eof())
{
fin>>str[pos];
pos++;
}
cout<<"测试语句:
"< stringString=""; intkey,curKey; key=GetClassify(str[0]); curKey=GetClassify(str[0]); for(i=0;i { curKey=GetClassify(str[i]); if(curKey==key&&curKey! =2)//同类继续添加 String+=str[i]; else//发现不同类对前面的字符串进行判断 { LexicalAnalyzer(String,key); String=""; if(curKey! =0) String+=str[i]; } key=curKey; } return0; } //分成四类 intGetClassify(charc) { if(c==''||c=='\n')//空格或换行 return0; if((c>='A'&&c<='Z')||(c>='a'&&c<='z')||(c>='0'&&c<='9')||c=='_'||c=='.')//标识符或整数或关键字 return1; elseif(c=='('||c==')'||c=='{'||c=='}'||c==';')//分隔符 return2; else return3;//运算符 } //词法分析器 voidLexicalAnalyzer(strings,intk) { if(s! ="") { if(k==1)//标识符或整数或关键字 GetIdentifier(s,k); elseif(k==2)//分隔符 GetSeparator(); elseif(k==3)//运算符 GetOperator(s,k); cout< } } //标识符函数 voidGetIdentifier(strings,intk) { inti; boolflag1=false; for(i=0;i { if(s[i]=='.') { flag1=false; break; } if(s[i]>'9'||s[i]<'0') { flag1=true; break; } } if(flag1==true) { boolflag2=true; for(i=0;i<7;i++) if(s==KeyWord[i]) { cout<<"(关键字,"; flag2=false; } if(flag2) cout<<"(标识符,"; } else{ boolflag3=true; for(i=0;i if(s[i]=='.') { flag3=false; cout<<"(浮点数,"; break; } if(flag3) cout<<"(整数,"; } } //运算符函数 voidGetOperator(strings,intk) { inti; for(i=0;i<5;i++) if(s==symbol1[i]) { switch(i) { case0: cout<<"(加法运算符,"; break; case1: cout<<"(减法运算符,"; break; case2: cout<<"(乘法运算符,"; break; case3: cout<<"(除法运算符,"; break; case4: cout<<"(求余运算符,"; break; } } for(i=0;i<5;i++) if(s==symbol2[i]) cout<<"(条件运算符,"; for(i=0;i<5;i++) if(s==symbol3[i]) cout<<"(关系运算符,"; if(s==": =") cout<<"(赋值运算符,"; elseif(s=="--"||s=="++") cout<<"(操作运算符,"; elseif(s=="<<"||s==">>") cout<<"(移位运算符,"; } //分隔符函数 voidGetSeparator() { cout<<"(分隔符,"; } 实验1_2_1代码: #include #include #include #include #include usingnamespacestd; //随机产生长度为size的单词 stringGetStopWords(intsize); intmain() { stringstr; inti,rows,aver; cout<<"请输入行数和单词平均长度: "< srand((unsigned)time(NULL));//利用种子函数产生伪随机数 ofstreamcout("test.txt",ios: : out);//将产生单词输出到test.txt cin>>rows>>aver; for(i=1;i<=rows;i++) { intlength; if(i%2) { if(i==rows) length=aver; else length=rand()%(2*aver-1)+1; } else length=2*aver-length; str=GetStopWords(length); cout< } return0; } //随机产生长度为size的单词 stringGetStopWords(intsize) { intflag; stringstr=""; for(inti=0;i { charch; ch=char(rand()%26+97); flag=rand()%2;//大小写随机产生 if(flag) ch-=32;//将字符ch转换成大写 str+=ch; } returnstr; } 实验1_2_2代码: #include #include #include #include #include usingnamespacestd; //随机产生长度为size的单词 stringGetFiles(intsize); intmain() { intcount,k,length; intnum=1; stringstr; cout<<"请输入文件大小和单词平均长度: "< srand((unsigned)time(0));//利用种子函数产生伪随机数 ofstreamcout("test.txt",ios: : out);//将产生单词输出到test.txt cin>>count>>k; while(count>0) { if(num%2) length=rand()%(2*k-1)+1; else length=2*k-length; if(length>count)//判断是否发生截断 length=count; str=GetRandomString(length); cout< count-=length; boolflag=false; if(count>1) { if(rand()%2)//随机产生回车换行 { cout< count-=2; flag=true; } } if(! flag) { if(count>0)//产生空格 { cout<<""; count--; } } num++; } return0; } //随机产生长度为size的字符串 stringGetFiles(intsize) { intflag; stringstr=""; for(inti=0;i { charch; ch=char(rand()%26+97); flag=rand()%2;//大小写随机产生 if(flag) ch-=32;//将字符ch转换成大写 str+=ch; } returnstr; } 实验1_2_3代码: #include #include #include #include #include #include usingnamespacestd; voidGetStopWords();//获得停用词表 voidGetFiles();//获得待处理文件 voidSettleFiles();//替换文件函数 char**v,**f;//v是停用词,f是待处理文件 intn,length;//n是禁用词个数,length是禁用词的平均长度 intsize,len;//size为待处理文件大小,len为单词平均长度 intnum,*key;//num是单词个数,key用来记录实际长度 intmain() { GetStopWords(); GetFiles(); SettleFiles(); return0; } //替换文件函数 voidSettleFiles() { inti,j,k; ofstreamcout("result.txt",ios: : out); for(i=0;i { for(j=0;j { if(! strcmp(f[i],v[j])) for(k=0;k f[i][k]='*'; } } for(i=0;i { for(j=0;j<=key[i];j++) cout< } } 实验1_3_1代码: //定义文法类 classGrammar { private: charVn[MAX];//非终结符号集 intVn_num;//非终结符号数目 charVt[MAX];//终结符号集 intVt_num;//终结符号数目 stringp[MAX];//产生式集合 intP_num;//产生式数目 charstart;//起始符号 public: voidInitial();//初始化及输入文法类 voidDisplay();//输出化简后的文法 voidRemoveProduction();//无用产生式消除 voidRemoveSingle();//单产生式消除 }; 实验1_3_2代码: #include #include #include #include usingnamespacestd; constintMAX=100; //定义文法类 classGrammar { private: charVn[MAX];//非终结符号集 intVn_num;//非终结符号数目 charVt[MAX];//终结符号集 intVt_num;//终结符号数目 stringp[MAX];//产生式集合 intP_num;//产生式数目 charstart;//起始符号 public: voidInitial();//初始化及输入文法类 voidDisplay();//输出化简后的文法 voidRemoveProduction();//无用产生式消除 voidRemoveSingle();//单产生式消除 }; voidGrammar: : Initial() { inti=0,j=0,k=0,num; for(i=0;i {//初始化赋值 Vn[i]='0'; Vt[i]='0'; p[i]='0'; } i=0; cout<<"输入非终结符个数以及非终结符: "; cin>>num; while(num--) cin>>Vn[++i]; Vn_num=i; cout<<"输入终结符个数以及终结符: "; cin>>num; while(num--) cin>>Vt[++j]; Vt_num=j; cout<<"输入产生式个数以及产生式: "; cin>>num; while(num--) cin>>p[++k]; P_num=k; cout<<"输入起始符号: "; cin>>start; } voidGrammar: : RemoveProduction() { charVn1[MAX]; stringp1[MAX]; int
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 深圳大学 编译 原理 实验 报告 蔡树彬 资料