词法分析实验报告.doc

编译原理课程实验报告题目 词法分析 专业 华侨大学09软件工程 班级 1班 学号 姓名 日期 2012-4-5 源码下载地址：http:/www.gxp.cc/file-1179505.html一. 实验题目词法分析二. 实验环境（操作系统，开发语言）操作系统：Windows 7开发语言：JAVA语言开发工具：MyEclipse8.5调试环境：JDK-1.7.0三. 实验内容（实验要求）1. 根据用户输入的正规式，使用Thompson算法构建NFA2. 利用子集法，从NFA构造DFA3. 最小化DFA4. 根据用户输入的字符串，模拟字符串的识别过程四. 实验过程及主要的数据结构(一) 程序流程图开始用户输入正规式正规式有效？处理正规式（加.，为字符添加优先级）构造NFA构造DFA最小化DFA用户输入字符串显示识别结果提示错误信息结束(二) 数据结构l 正规式处理过程正规式存储结构ArrayList（ArrayList是实现了基于动态数组的数据结构）正规式元素结构：ExpressionItem；类图如下例：正规式（a|b）*ab经过处理后的结构如下：true.2falsea-1true.2true*3true)4falseb-1true|1falsea-1true(0falseb-1l NFA结构正规式“a|b”的邻接表结构5510243ab#正规式“a|b”的邻接表结构字符集charList状态表statesId=0edgeList4终态集endStates5初态startStatevalue=anext=1abId=1edgeListId=2edgeListId=3edgeListId=4edgeListId=5edgeListnulllvalue=bnext=3value=#next=5value=#next=0value=#next=5value=#next=2EdgeNFA结构代码实现public class NFA private ArrayListcharList;/输入字符集private ArrayList states;/状态集private NFAStateNode startState;/开始状态private ArrayList endStates;/结束状态集/*内部类:存放一个正规式的开始与结束状态*/class StatePairprivate NFAStateNode startState;private NFAStateNode endState;StatePair(NFAStateNode start,NFAStateNode end)this.startState=start;this.endState=end;NFA状态节点结构代码实现public class NFAStateNode static int stateNum=0;private int id;private ArrayListEdge edgeList;public NFAStateNode()edgeList=new ArrayListEdge();id=stateNum+;NFA或DFA图的边Edge结构代码实现 public class Edge private T next; private char value; public Edge(T next,char value) this.next=next; this.value=value; l DFA数据结构DFA结构代码实现public class DFA private ArrayListcharList;/输入字符集private DFAStateNode startState;/开始状态private ArrayList endStates;/终态集 private ArrayList Dstates;/所有状态集private NFA nfa;/被转化的NFADFA状态节点代码实现public class DFAStateNode static int stateNum=0;private int id;private ArrayListEdge edgeList;private HashSet nfaStateSet;(三) 核心代码l 构造NFA/用于存放输入正规式中的操作符Stack operatorStack = new Stack();/用于存放输入字母及运算结果Stack resultStack=new Stack();/* * 构造NFA * param list 为经处理的正规式链表 * */private void createNFA(ArrayList list)int index=0;while(indexoperatorStack.peek().opPriority&item.value!=)operatorStack.push(item);index+;continue;if(item.opPriority=operatorStack.peek().opPriority)&item.value!=()calculate(operatorStack.peek().value);index+;operatorStack.push(item);continue;if(item.value=()operatorStack.push(item);index+;continue;if(item.value=)calculate(item.value);index+;continue;while(!operatorStack.isEmpty()calculate(operatorStack.peek().value);startState=resultStack.peek().startState;endStates.add(resultStack.peek().endState);l 构造DFA/* *利用子集法将NFA转换成DFA */public void NFAtoDFA() /DFA的开始状态为NFA开始状态的空闭包startState =new DFAStateNode(nfa.getStartState().getNullClosure();Dstates.add(startState);if(isEndState(startState)endStates.add(startState);/创建DFA状态队列Queue queue =new LinkedList();queue.add(startState);while(!queue.isEmpty()DFAStateNode state = queue.poll();for(int i=0;icharList.size();i+)HashSet resultSet = state.getSet(charList.get(i);if(resultSet.size()=0)continue;/如果不接受字符，则继续测试下一个字符DFAStateNode findRuselt=getNextState(resultSet);if(findRuselt=null)DFAStateNode newState=new DFAStateNode(resultSet);Dstates.add(newState);if(isEndState(newState)endStates.add(newState);state.addEdge(newState,charList.get(i);queue.add(newState);elsestate.addEdge(findRuselt,charList.get(i); l 最小化DFA最小化DFA采用子集法，但算法和书上的不一样我的算法类似最小生成树中的避圈法，而书上则类似于破圈法。我认为“避圈法”更适合理解，下面是DFA的最小化过程：public void minimize()boolean changed=true;while(changed)changed=false;ArrayListArrayList moveTable=new ArrayListArrayList();for(DFAStateNode state : Dstates)ArrayList moveList=new ArrayList();for(char eachChar : charList)DFAStateNode next=state.move(eachChar);if(next=null)moveList.add(-1);elsemoveList.add(next.getId();moveTable.add(moveList);for(int i=0;imoveTable.size();i+)ArrayList equalStateList=new ArrayList();DFAStateNode curState=Dstates.get(i);equalStateList.add(curState);for(int j=i+1;j1) changed=true; changeDFA(equalStateList); break;/for j/for i/while五. 测试结果(一) 功能测试测试用例ID1目的(1) 输入的正规式包含所有操作符，测试程序对操作符的识别能力(2) 测试程序对非终态的最小化情况输入正规式：(a|b)*abb 待识别字符串：abb aaabb bbabb abab预期输出(1) 可识别 可识别 可识别 不可识别(2) 不可识别的非终态可合并，最小化后DFA只有4个状态 测试用例ID2目的(1) 测试对空串的识别情况(2) 测试对不可识别终态的最小化情况输入正规式：a*待识别字符串：空串预期输出可识别 最小化后只有一个状态(二) 健壮性测试测试用例ID3目的测试程序的健