词法分析报告实验报告材料34309.doc

《词法分析报告实验报告材料34309.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《编译原理》课程实验报告题目词法分析专业华侨大学09软件工程班级1班学号日期2012-4-5源码下载地址：.gxp.cc/file-1179505.html一.实验题目词法分析二.实验环境（操作系统，开发语言）操作系统：Windows7开发语言：JAVA语言开发工具：MyEclipse8.5调试环境：JDK-1.7.0一.实验容（实验要求）1.根据用户输入的正规式，使用Thompson算法构建NFA2.利用子集法，从NFA构造DFA3.最小化DFA4.根据用户输入的字符串，模拟字符串的识别过程二.实验过程及主要的数据结构(一)程序

2、流程图开始用户输入正规式正规式有效？处理正规式（加’.’，为字符添加优先级）构造NFA构造DFA最小化DFA用户输入字符串显示识别结果提示错误信息结束(二)数据结构l正规式处理过程正规式存储结构ArrayList（ArrayList是实现了基于动态数组的数据结构）正规式元素结构：ExpressionItem；类图如下例：正规式（a

3、b）*ab经过处理后的结构如下：true.2falsea-1true.2true*3true)4falseb-1true

4、1falsea-1true(0falseb-1lNFA结构正规式“a

5、b”的邻接

6、表结构5510243ab####正规式“a

7、b”的邻接表结构字符集charList状态表statesId=0edgeList4终态集endStates5初态startStatevalue=anext=1abId=1edgeListId=2edgeListId=3edgeListId=4edgeListId=5edgeListnulllvalue=bnext=3value=#next=5value=#next=0value=#next=5value=#next=2EdgeNFA结构代码实现publicclassNFA{private

8、ArrayListcharList;//输入字符集privateArrayListstates;//状态集privateNFAStateNodestartState;//开始状态privateArrayListendStates;//结束状态集/**部类:存放一个正规式的开始与结束状态*/classStatePair{privateNFAStateNodestartState;privateNFAStateNodeendState;StatePair(N

9、FAStateNodestart,NFAStateNodeend){this.startState=start;this.endState=end;}}}NFA状态节点结构代码实现publicclassNFAStateNode{staticintstateNum=0;privateintid;privateArrayList>edgeList;publicNFAStateNode(){edgeList=newArrayList>();id=stateNum

10、++;}}NFA或DFA图的边Edge结构代码实现publicclassEdge{privateTnext;privatecharvalue;publicEdge(Tnext,charvalue){this.next=next;this.value=value;}}lDFA数据结构DFA结构代码实现publicclassDFA{privateArrayListcharList;//输入字符集privateDFAStateNodestartState;//开始状态privateArrayList

11、tateNode>endStates;//终态集privateArrayListDstates;//所有状态集privateNFAnfa;//被转化的NFA}DFA状态节点代码实现publicclassDFAStateNode{staticintstateNum=0;privateintid;privateArrayList>edgeList;privateHashSetnfaStateSet;}(一)核心代码l构造NFA//用于存放输入正规式中的操作符Stack<

12、ExpressionItem>operatorStack=newStack();//用于存放输入字母及运算结果StackresultStack=newStack();/**