编译原理 词法分析 语法分析 Java版

编译原理 词法分析 语法分析Java版【NFA DFA DFA最小化】【添加注释版】

package lexicalanalyzer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class DFA {
	
	private ArrayList states=new ArrayList（）; 
	private NFA nfa;
	private DFAState startState;
	private ArrayList endStates=new ArrayList（）;
	
	public static DFA newInstance（NFA nfa）{
		return new DFA（nfa）;
	}
	
	public DFA（NFA nfa）{
		this.nfa=nfa;
		createDFA（nfa）;		
	}
		
	public void minimize（）{
		ArrayList> workspace=
			new ArrayList>（）;
		for（DFAState state : getStates（））{
			ArrayList moveTable=new ArrayList（）;
			for（char eachChar : getAlphabet（））{				
				if（state.move（eachChar）==null）{
					moveTable.add（-1）;
				}
				else{
					moveTable.add（state.move（eachChar）.getID（））;		
				}	
			}			
			workspace.add（moveTable）;		
		}
		//partition.
		ArrayList> partition=
			new ArrayList>（）;
		partition.add（this.endStates）;
		boolean[] visited=new boolean[workspace.size（）];
		for（int i=0;i			if（visited[i]==true）{
				continue;
			}
			ArrayList temp=new ArrayList（）;
			temp.add（states.get（i））;
			for（int j=i+1;j				if（workspace.get（i）.equals（workspace.get（j）））{
					visited[j]=true;
					if （!endStates.contains（states.get（j））） {
						temp.add（states.get（j））;
					}
				}
			}
			partition.add（temp）;	
		}
		selectRepresent（partition）;	
	}
	
	public ArrayList getStates（）{		
		return states;
	}
	
	public DFAState getStartState（）{
		return this.startState;
	}
	
	public ArrayList getEndStates（）{
		return endStates;
	}
	
	public ArrayList getAlphabet（）{
		return nfa.getAlphabet（）;
	}

	private void createDFA（NFA nfa）{
		Stack untagedStates=new Stack（）;
		DFAState start=new DFAState（）;
		start.addAll（nullClosure（nfa.getStartState（）））;
		states.add（start）;
		setStartState（start）;
		untagedStates.push（start）;
		while（!untagedStates.empty（））{
			DFAState current=untagedStates.pop（）;
			for（char eachChar : nfa.getAlphabet（））{
				ArrayList temp=nullClosure（smove（currenteachChar））;
				boolean needNew=true;
				for（DFAState existed : states）{
					if（existed.contains（temp））{
						current.connect（existedeachChar）;
						needNew=false;
						break;
					}
				}
				if（needNew && temp.size（）!=0）
				{
					DFAState newborn=new DFAState（）;
					newborn.addAll（temp）;
					untagedStates.push（newborn）;
					states.add（newborn）;
					current.connect（newborn eachChar）;		
				}				
			}
		}
		fillEndStates（）;
	}

	private ArrayList smove（DFAState schar a）{
		ArrayList result=new ArrayList（）;
		for（NFAState eachState : s.getContent（））{
			result.addAll（eachState.move（a））;
		}
		return result;		
	}

	private ArrayList nullCl

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\
     文件         422  2010-06-21 15:49  FundamentalsOfCompiling\.classpath
     文件         607  2010-06-21 14:24  FundamentalsOfCompiling\.project
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.settings\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\
     文件         331  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\entries
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.settings\.svn\prop-base\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.settings\.svn\props\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\text-base\
     文件         629  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\text-base\org.eclipse.jdt.core.prefs.svn-base
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\tmp\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.settings\.svn\tmp\prop-base\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.settings\.svn\tmp\props\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.settings\.svn\tmp\text-base\
     文件         629  2010-06-01 19:25  FundamentalsOfCompiling\.settings\org.eclipse.jdt.core.prefs
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.svn\
     文件         668  2010-10-17 16:18  FundamentalsOfCompiling\.svn\entries
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.svn\prop-base\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.svn\props\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.svn\text-base\
     文件         422  2010-10-17 16:18  FundamentalsOfCompiling\.svn\text-base\.classpath.svn-base
     文件         607  2010-10-17 16:18  FundamentalsOfCompiling\.svn\text-base\.project.svn-base
     文件        1295  2010-10-17 16:18  FundamentalsOfCompiling\.svn\text-base\build.xml.svn-base
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.svn\tmp\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.svn\tmp\prop-base\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\.svn\tmp\props\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\.svn\tmp\text-base\
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\bin\
     目录           0  2010-10-17 16:18  FundamentalsOfCompiling\bin\.svn\
     文件         166  2010-10-17 16:18  FundamentalsOfCompiling\bin\.svn\entries
     目录           0  2010-10-17 16:17  FundamentalsOfCompiling\bin\.svn\prop-base\
............此处省略247个文件信息