词法分析实验报告.doc

《编译原理》课程
实验报告

题目 词法分析
专业 华侨大学09软件工程
班级 1班
学号
姓名
日期 2012-4-5

源码下载地址：http://www.gxp.cc/file-1179505.html

一. 实验题目
词法分析
二. 实验环境（操作系统，开发语言）
操作系统：Windows 7
开发语言：JAVA语言
开发工具：MyEclipse8.5
调试环境：JDK-1.7.0
三. 实验内容（实验要求）
1. 根据用户输入的正规式，使用Thompson算法构建NFA
2. 利用子集法，从NFA构造DFA
3. 最小化DFA
4. 根据用户输入的字符串，模拟字符串的识别过程
四. 实验过程及主要的数据结构
(一) 程序流程图
开始
用户输入正规式
正规式有效？
处理正规式（加’.’，
为字符添加优先级）

构造NFA
构造DFA
最小化DFA
用户输入字符串
显示识别结果
提示错误信息
结束

(二) 数据结构
l 正规式处理过程
正规式存储结构ArrayList（ArrayList是实现了基于动态数组的数据结构）
正规式元素结构：ExpressionItem；类图如下

例：正规式（a|b）*ab经过处理后的结构如下：
true
.
2
false
a
-1
true
.
2
true
*
3

true
)
4
false
b
-1
true
|
1
false
a
-1
true
(
0
false
b
-1

l NFA结构
正规式“a|b”的邻接表结构
55
1
0
2
4
3
a
b
#
#
#
#

正规式“a|b”的邻接表结构
字符集charList
状态表
states
Id=0
edgeList
4
终态集endStates
5

初态startState
value=a
next=1
a
b
Id=1
edgeList
Id=2
edgeList
Id=3
edgeList
Id=4
edgeList
Id=5
edgeList
nulll
value=b
next=3
value=#
next=5
value=#
next=0
value=#
next=5
value=#
next=2
Edge

NFA结构代码实现
public class NFA {
private ArrayList<Character>charList;//输入字符集
private ArrayList<NFAStateNode> states;//状态集
private NFAStateNode startState;//开始状态
private ArrayList<NFAStateNode> endStates;//结束状态集
/**内部类:存放一个正规式的开始与结束状态*/
class StatePair{
private 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 ArrayList<Edge<NFAStateNode>> edgeList;
public NFAStateNode(){
edgeList=new ArrayList<Edge<NFAStateNode>>();
id=stateNum++;
}
}
NFA或DFA图的边Edge结构代码实现
public class Edge<T> {
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 ArrayList<Character>charList;//输入字符集
private DFAStateNode startState;//开始状态
private ArrayList<DFAStateNode> endStates;//终态集
private ArrayList<DFAStateNode> Dstates;//所有状态集
private NFA nfa;//被转化的NFA
}

DFA状态节点代码实现
public class DFAStateNode {
static int stateNum=0;
private int id;
private ArrayList<Edge<DFAStateNode>> edgeList;
private HashSet nfaStateSet;
}

(三) 核心代码

l 构造NFA
//用于存放输入正规式中的操作符
Stack<ExpressionItem> operatorStack = new Stack<ExpressionItem>();
//用于存放输入字母及运算结果
Stack<StatePair> resultStack=new Stack<StatePair>();
/**
* 构造NFA
* @param list 为经处理的正规式链表
*
*/
private void createNFA(ArrayList<ExpressionItem> list){
int index=0;
while(index<list.size()){
ExpressionItem item=list.get(index);
if(!item.isOperator){
addToCharList(item.value);
resultStack.push(singleCharCreate(item.value));
index++;
}
else{
if(operatorStack.isEmpty()) {
operatorStack.push(item);
index++;
}
else{
if(item.opPriority>operatorStack.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<DFAStateNode> queue =new LinkedList<DFAStateNode>();
queue.add(startState);
while(!queue.isEmpty()){
DFAStateNode state = queue.poll();
for(int i=0;i<charList.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);
}else{
state.addEdge(findRuselt,charList.get(i));
}
}
}
}
l 最小化DFA
最小化DFA采用子集法，但算法和书上的不一样
我的算法类似最小生成树中的避圈法，而书上则类似于破圈法。我认为“避圈法”更适合理解，下面是DFA的最小化过程：

public void minimize(){
boolean changed=true;
while(changed){
changed=false;
ArrayList<ArrayList<Integer>> moveTable=new ArrayList<ArrayList<Integer>>();
for(DFAStateNode state : Dstates){
ArrayList<Integer> moveList=new ArrayList<Integer>();
for(char eachChar : charList){
DFAStateNode next=state.move(eachChar);
if(next==null){
moveList.add(-1);
}
else{
moveList.add(next.getId());
}
}
moveTable.add(moveList);
}
for(int i=0;i<moveTable.size();i++){
ArrayList<DFAStateNode> equalStateList=new ArrayList<DFAStateNode>();
DFAStateNode curState=Dstates.get(i);
equalStateList.add(curState);
for(int j=i+1;j<moveTable.size();j++){
DFAStateNode nextState=Dstates.get(j);
if(moveTable.get(i).equals(moveTable.get(j))){
if (endStates.contains(curState)
&&endStates.contains(nextState)
||!endStates.contains(curState)
&&!endStates.contains(nextState)) {
equalStateList.add(nextState);
}
}
}
if(equalStateList.size()>1){
changed=true;
changeDFA(equalStateList);
break;
}//for j
}//for i
}//while
}
五. 测试结果
(一) 功能测试
测试用例ID
1
目的
(1) 输入的正规式包含所有操作符，测试程序对操作符的识别能力
(2) 测试程序对非终态的最小化情况
输入
正规式：(a|b)*abb 待识别字符串：abb aaabb bbabb abab
预期输出
(1) 可识别 可识别 可识别 不可识别
(2) 不可识别的非终态可合并，最小化后DFA只有4个状态

测试用例ID
2
目的
(1) 测试对空串的识别情况
(2) 测试对不可识别终态的最小化情况
输入
正规式：a*待识别字符串：空串
预期输出
可识别 最小化后只有一个状态

(二) 健壮性测试
测试用例ID
3
目的
测试程序的健壮性，对各种非法输入的识别
输入
正规式：“|ab” “ab||a” “ab()”“ $” “(a|b” “ab|b)”
预期输出
输出提示信息

六. 实验总结
此次实验，个人感觉相对较难。不仅要对书上的概念、算法理解通透，更要掌握数据结构的相关知识。在实验过程中，我把书上的算法看了好几遍，同时，还重新看了数据结构书中关于表达式求值、图的邻接矩阵表示法等章节。通过此次实验不仅对词法分析有了进一步的掌握，也让我巩固了一些常用算法及数据结构知识。