实验1：词法分析程序

《实验1：词法分析程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验1词法分析程序一、实验目的与要求1.复习正规文法、正规式、有限自动机之间的相互转换的原理及技术；2.学会使用VisualC++等高级语言编程实现上述转换，并能合理显示结果；3.以C++的一个真子集为案例，具体分析词法分析程序的设计步骤、基本架构及代码编制，并通过一定实例验证其可行性，以加深对词法分析原理的理解；4.通过本次实验，使学生理解模块化程序设计的思想，从而从全局角度领会一个完整软件的设计精髓，为后续试验的顺利完成奠定坚实的基础。二、实验仪器及设备1.微型电子计算机80台2.配置Windows2000

2、及以上版本操作系统3.安装VisualC++6.0/VisualC#2000/Delphi6.0等以上版本的开发环境三、实验内容及步骤（一）正规文法与有限自动机的相互转换1．正规文法Þ有限自动机已知某正规文法G[S]如下：S→aAS→bBS→εA→aBA→bAB→aSB→bAB→ε请编程实现：（1）将G[S]转换为NFA；（2）将上述得到的NFA确定化为DFA；（3）再将DFA最简化为MFA。2．有限自动机Þ正规文法已知某有限自动机NFAM=（Q,∑,f,q0,Z）如下：状态集：Q={1,2,3,4,5,6,7

3、,8,9}字母表：∑={a,b}转移函数：f(1,a)=5f(1,ε)=2f(1,a)=4f(5,ε)=6f(2,b)=3f(4,ε)=7f(6,ε)=2f(6,b)=9f(3,ε)=8f(8,a)=9f(7,b)=941初态：q0=1终态集：Z={6,7,9}请编程实现：（1）首先将此NFA确定化为DFA；（2）再将得到的DFA最简化为MFA；（3）最后，将MFA转化为正规文法（左线性或右线性均可）。（二）编程实现MiniC++的词法分析这里的MiniC++为C++语言的一个真子集，其语法结构与C++类似。基

4、本组成如下：（1）关键字有18个，分别为：void、int、char、bool、float、double、if、else、switch、case、default、break、continue、do、while、for、return以及struct等。（2）标识符：定义为“以字母或下划线开头，由字母、数字或下划线组成的符号串。”（3）常量：包括数字（暂时仅考虑无符号整数）、字符串、字符常量等。（4）分隔符：()[]{}.,:;~?#等。（5）运算符：=、==、>、>=、<、<=、!、!=、&&、&=、

5、

6、、

7、=、

8、+、++、-、=、->、/、/=、%、%=等。要求同学们完成下述工作：1．基于上述描述，根据你的理解，尝试写出该MiniC++的文法G[S]；2．再根据你所写的文法G[S]，绘制出MiniC++的NFA状态图，并进而推导出最简化的MFA；3．根据你推导出的MFA，编写MiniC++的词法分析程序，并用下面的源代码测试你所设计的程序。//测试函数调用，求N!intf(inta){if(a==1)a=1;elsea=a*f(a-1);returna;}voidmain(){inti,a;cout<<"pleasei

9、nputn=:"<>i;a=f(i);cout<<"n!="<

10、结果，尤其是程序显示结果；3．不需要附上源代码。四、思考题五、实验小结阐述实验中碰到的问题、解决的方法或技术、得到的结论、体会感触等。六、参考代码（一）CGrammar类1．头文件Grammar.h#pragmawarning(disable:4786)//屏蔽“由于string和vector等STL模版产生很长的标识符而引起的警告信息”#include#include#include#include#include//使用

11、vector容器#includeusingnamespacestd;structCreateFormula//产生式{stringLeftPart;//左部stringRightPart;//右部};classCGrammar{public:CGrammar();~CGrammar();//外部操作函数：voidSetGrammar(char*Filename);//