basevt.java

设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟。

package you.test;

import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

public class BaseVT {

	public Stack<String> stack = new Stack<String>();

	// 存储终结符,自动排序
	public static Set<String> terminal = new TreeSet<String>();

	// 存储非终结符，自动排序
	public static Set<String> nonTerminal = new TreeSet<String>();

	// 存储产生式,key--string非终结符，value--set所有的产生式
	public static Map<String, Set<String>> sentence = new TreeMap<String, Set<String>>();
    
	public BaseVT(){
		
	}
	

	
	
	/**
	 * 
	 * @param gs
	 *            单行文法 
	 *   根据传入的文法，分离出终结符和非终结符
	 */
	public static void parseTerminal(String gs) {
		// 对单行进行解析，分离出终结符和非终结符
		for (int i = 0; i < gs.length(); i++) {
			// 逐个字符扫描
			char ch = gs.charAt(i);
			if (ch >= 'A' && ch <= 'Z') {

				StringBuffer s = new StringBuffer();
				s.append(ch);
				// 若非终结符含有（’）字符
				if (i < gs.length() - 1 && gs.charAt(i + 1) == '’')
					s.append('’');
				nonTerminal.add("" + s.toString());
			} else {

				// 跳过->(即下标为1、2的字符)符和|
				if (ch == '|' || ch == '’' || ch == '-' || ch == '>')
					continue;
				// 漏掉'’'情况
				terminal.add("" + ch);
			}
		}
	}

	/**
	 * 
	 * @param gs
	 *            单行文法 
	 * 根据传入的文法，解析出所有的产生式，并存储在TreeMap中
	 */
	public static void parseSentence(String gs) {
		Set<String> right = null;
		// 按->分割字符串
		String[] slr = gs.split("->");
		// 用|对产生式右部进行分割
		String[] rs = slr[1].split("\\|");
		// 如果已经存在该非终结符
		if (sentence.containsKey(slr[0])) {
			// 先取出，
			right = sentence.get(slr[0]);
		} else {
			right = new TreeSet<String>();
		}

		// 再重新加入新的产生式
		for (String s : rs) {
			right.add(s);
		}
		sentence.put(slr[0], right);
	}
	
	/**
	 * 
	 * @param indexVN
	 *            非终结符的下标
	 * @param indexVT
	 *            终结符的下标 入栈操作
	 * @param vt 
	 *            firstVT或lasetVT        
	 *            
	 * 
	 */
	public void insert(String vN, String vT,Map<String, Set<String>> vt) {
	
		Set<String> setVT = null;
		setVT = vt.get(vN);
		if(setVT==null){
			setVT = new TreeSet<String>();
		}
		//如果不含有终结符，则加入
		if (setVT.contains(vT) == false) {
			setVT.add(vT);
			vt.put(vN, setVT);
			System.out.println("------将("+vN+","+vT+")入栈");
			stack.push("(" + vN + "," + vT + ")");
		}else{
			System.out.println("------("+vN+","+vT+")已经在栈中");
		}
	}

}