confirmnfa.java

本程序是编译原理的经典试验

	 * @param statusT
	 * @param input
	 * @return
	 */
	public String move(String statusT, int input, String[][] metrix) {
		String afterMove = "";
		for(int i = 0; i < statusT.length(); i++) {
			if(!metrix[statusT.charAt(i) - '0'][input].equals("#") && !metrix[statusT.charAt(i) - '0'][input].equals("@")) {
				afterMove += metrix[statusT.charAt(i) - '0'][input];
			}
		}
		afterMove = removeEcho(afterMove);
		return afterMove;
	}
	/**
	 * 求moveStatus的闭包集，最终存储在closureStatus
	 * e - closure(move(T, a))
	 * @param moveStatus
	 * @param closureStatus
	 * @param eIndex
	 * @return
	 */
	public String closure(String moveStatus, String closureStatus, int eIndex) {
		for(int i = 0; i < moveStatus.length(); i++) {								/* moveStatus表示move(T, a)，已经由move函数求得 */
			String str = matrix_NFA[moveStatus.charAt(i) - '0'][eIndex];	/* 在e输入下的跳转状态 */
			if(str.charAt(0) == '#') {
				continue;
			}
			for(int j = 0; j < str.length(); j++) {
				if(closureStatus.contains(String.valueOf(str.charAt(j)))) {
					continue;
				} else {
					closureStatus += str.charAt(j);
				}
				closureStatus = closure(String.valueOf(str.charAt(j)), closureStatus, eIndex);	/* 递归求在e输入下的一连串状态 */
			}
		}
		return closureStatus;
	}
	/**
	 * NFA的确定化函数
	 */
	public void confirm() {
		String moveStatus;							/* 存放子集成员在a输入下的状态转换集 */
		String closureStatus;							/* 存放在moveStatus的闭包集 */
		ArrayList strOnly;								/* 存放子集中的元素，与c_Group不同的是strOnly只存放状态集，以便判断 */
		int stTag = 0;									/* 与ClosureStatus类中的ST变量对应 */

		moveStatus = closureStatus = "0";	/* 初始值为初始状态 */		
		closureStatus = sort(closure(moveStatus, closureStatus, len_SYMS));	/* 求初始状态的闭包集，并排序 */

		c_Group = new ArrayList();
		strOnly = new ArrayList();
		ClosureStatus cs = new ClosureStatus();											/* 状态子集中的第一个元素，课本算法上的T0集，为标记*/
		cs.setSTATUS(closureStatus);
		cs.setST("" + stTag);
		stTag++;
		c_Group.add(cs);																				/* 把T0添加到C子集中 */			
		strOnly.add(closureStatus);
		counter++;									
		
		/**
		 * 
		 * index_CGroup：从C子集开头挨个检测状态集是否被标记的下标
		 * counter：C子集中的状态个数
		 * C子集中存在未标记的状态集且index_CGroup < counter则继续执行
		 */
		while(index_CGroup < counter && !((ClosureStatus)c_Group.get(index_CGroup)).isTARGET()) {
			cs = (ClosureStatus)c_Group.get(index_CGroup);
			String tempStr = cs.getSTATUS();
			cs.setTARGET(true);
			for(int i = 1; i < len_SYMS; i++) {
				moveStatus = move(tempStr, i, matrix_NFA);								/* 代表move(T, a)*/
				closureStatus = moveStatus;														/* 待求闭包的状态集也包含在闭包集中 */
				closureStatus = closure(moveStatus, closureStatus, len_SYMS);	/* 求闭包 */
				closureStatus = removeEcho(closureStatus);								/* 删除在状态集中重复的状态 */
				closureStatus = sort(closureStatus);											/* 排序 */
				ClosureStatus newCS = new ClosureStatus();
				newCS.setSTATUS(closureStatus);
				if(!strOnly.contains(closureStatus)) {											/* 如果新求得的闭包集不包含在C子集中，则添加到C子集中 */
					newCS.setST("" +stTag );
					stTag++;
					c_Group.add(newCS);
					strOnly.add(closureStatus);
					counter++;
				}
			}
			index_CGroup++;
		}
		strToChar();
	}
	public void getInitData() {
		String nextLine;									/* 存放从文件中读取的一行字符串 */
		String tempStr;									/* 存放所读取字符串去空格之后的字符串 */		
		StringTokenizer tokenStr;					/* 序列化字符串 */
		int tempRow, tempCol;						/* 初始化matrix_NFA矩阵时的临时下标 */
		int statusIndex;									/* 在矩阵每行最前面标记状态 */

		try {
			BufferedReader br = new BufferedReader(new FileReader("./files/Test.txt"));

			tempStr = "";
			nextLine = br.readLine();					/* 读取第一行，作为输入符号集 */
			tokenStr=new StringTokenizer(nextLine);
			while(tokenStr.hasMoreTokens()) {
				tempStr += tokenStr.nextToken();
			}
			len_SYMS = tempStr.length();			/* 输入符号个数 */
			input_SYM = new char[len_SYMS];	/* 分配输入符号数组长度 */
			input_SYM = tempStr.toCharArray();	/* 用读取到的输入符号初始化input_SYM内的元素 */

			tempStr = "";
			nextLine = br.readLine();					/* 读取第二行，NFA的终态集 */
			tokenStr=new StringTokenizer(nextLine);
			while(tokenStr.hasMoreTokens()) {
				tempStr += tokenStr.nextToken();
			}
			len_ENDSTNFA = tempStr.length();					/* NFA的终态个数 */
			endStatus_NFA = new char[len_ENDSTNFA];		/* 初始化NFA终态集的长度 */
			endStatus_NFA = tempStr.toCharArray();			/* 用所读取到的终态初始化endStatus_NFA的元素 */

			nextLine = br.readLine();									/* 读取地三行，状态转换矩阵的行数 */
			row_NFA = Integer.parseInt(nextLine);	
			col_NFA = len_SYMS;	
			matrix_NFA = new String[row_NFA][col_NFA + 1];	/* 分配NFA状态转换矩阵空间大小 */

			tempStr = "";
			nextLine = br.readLine();									/* 读取矩阵 */
			tokenStr=new StringTokenizer(nextLine);
			tempRow = 0;	tempCol = 0;
			statusIndex = 0;
			while(nextLine != null && !nextLine.equals("")) {
				matrix_NFA[tempRow][tempCol++] = "" + statusIndex++;
				while(tokenStr.hasMoreTokens()) {
					matrix_NFA[tempRow][tempCol++] = tokenStr.nextToken();
				}

				nextLine = br.readLine();
				if(nextLine != null && !nextLine.equals("")) {
					tokenStr=new StringTokenizer(nextLine);
				}
				tempRow++;	tempCol = 0;
			}
		} catch(FileNotFoundException e) {
			System.out.println("FileNotFoundException!!!");
		} catch(IOException e) {
			System.out.println("IOException");
		}
	}
	public void display(int n) {
		switch(n) {
		case 1:
			for(int i = 0; i < row_NFA; i++) {
				for(int j = 0; j < col_NFA + 1; j++) {
					System.out.print(matrix_NFA[i][j] + "\t");
				}
				System.out.println();
			}
			break;
		case 2:
			for(int i = 0; i < row_DFA; i++) {
				for(int j = 0; j < col_DFA + 1; j++) {
					System.out.print(matrix_DFA[i][j] + "\t");
				}
				System.out.println();
			}
			break;
		}
	}
	public void check() {
		String inputStr = "";
		int next = 0;
		String status = "0";

		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			while(true) {
				System.out.print("请输入待检测的句子(01串) ： ");
				inputStr = br.readLine();
				for(int i = 0; i < inputStr.length(); i++) {
					if(inputStr.charAt(i) == input_SYM[0]) {
						next = 1;
					} else {
						next = 2;
					}
					status = matrix_DFA[status.charAt(0) - '0'][next];
					if(i == inputStr.length() - 1) {
						if(status.equals(end_Status)) {
							System.out.println("所输入句子被识别!!!");
						} else {
							System.out.println("所输入句子不能被识别!!!");
						}
					}
					if(status.equals("@")) {
						System.out.println("所输入句子不能被识别!!!");
					}
				}
			}
		} catch(Exception e) {}
	}
	public static void main(String args[]) {
		ConfirmNFA confirm = new ConfirmNFA();

		confirm.getInitData();
		confirm.confirm();
		confirm.display(2);
		confirm.miniDFA();
		confirm.display(2);
		confirm.check();

	}
}

/*
 * 该类的对象作为根据NFA构造的子集族C的元素
 */
class ClosureStatus {
	private String STATUS;							/* 存放求完闭包之后的状态集，其中每一个字符表示一个状态 */
	private boolean TARGET;						/* 标记(课本P59算法中提到的标记，true为被标记状态，初始值为未标记 )*/
	private String ST;									/* 存放用字符代替状态集之后的状态标记 */

	public ClosureStatus() {STATUS = "";	TARGET = false;}
	public String getSTATUS() {return STATUS;}
	public void setSTATUS(String status) {STATUS = status;}
	public boolean isTARGET() {return TARGET;}
	public void setTARGET(boolean target) {TARGET = target;}
	public String getST() {return ST;}
	public void setST(String st) {ST = st;}
}