firstvt.java

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

package you.test;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class FirstVT extends BaseVT {

	private Map<String, Set<String>> firstVT = new TreeMap<String, Set<String>>();

	// 默认构造函数,为firstVT赋初值
	public FirstVT() {

		super();
		Iterator<String> it = nonTerminal.iterator();
		while (it.hasNext()) {
			firstVT.put(it.next(), null);
		}

	}

	/**
	 * 
	 */
	@SuppressWarnings("unused")
	public void init() {

		// 非终结符，文法左部
		String key = null;
		// 文法右部
		String value = null;
		// 产生式首字母
		String begin = null;
		// 下一个字符
		String next = null;
		// 第三个字符
		String third = null;
		String t = null;

		// 将A->a....或A->Ba...的产生式
		System.out.println("找到所有的A->a....或A->Ba...的产生式");
		Iterator<String> it = sentence.keySet().iterator();
		while (it.hasNext()) {
			key = (String) it.next();
			// System.out.print(key + "---");
			Iterator<String> itValue = sentence.get(key).iterator();
			while (itValue.hasNext()) {
				// System.out.print(it1.next() + "|");
				value = itValue.next();

				// 首字符
				begin = "" + value.charAt(0);
				// 重新置为null
				next = null;
				third = null;
				if (value.length() > 1) {
					next = "" + value.charAt(1);
				}
				if (value.length() > 2) {
					third = "" + value.charAt(2);
					t = begin + next;
				}
				// 如果为终结符，A->a....
				if (terminal.contains(begin)) {
				//	System.out.println("找到一个A->a....");
					System.out.print(key+"->"+value);
					//System.out.println("------将("+key+","+begin+")入栈");
					insert(key, begin, firstVT);
				}
				// A->T'a...
				else if (third != null && nonTerminal.contains(t)
						&& terminal.contains(third)) {
					System.out.print(key+"->"+value);
					//System.out.println("------将("+key+","+third+")入栈");
					insert(key, third, firstVT);
				} else if (next != null && nonTerminal.contains(begin)
						&& terminal.contains(next)) {
					System.out.print(key+"->"+value);					
					insert(key, next, firstVT);
				}
			}
		}
	}

	/**
	 * 栈操作
	 */
	@SuppressWarnings("unused")
	public void processStack() {
		// 栈顶元素
		String top = null;
		// 非终结符
		String vN = null;
		// 终结符
		String vT = null;
		// 非终结符，文法左部
		String key = null;
		// 文法右部
		String value = null;
		// 产生式首字母
		@SuppressWarnings("unused")
		String begin = null;
		//
		int t = 0;
		while (stack.empty() == false) {
			top = stack.pop();
			System.out.println("弹出栈顶元素:"+top);
			// 解析出VN,VT
			t = top.indexOf(",");
			vN = top.substring(1, t);
			vT = "" + top.charAt(t + 1);
			System.out.println("查找所有A->"+vN+"....的产生式");
			Iterator<String> it = sentence.keySet().iterator();
			while (it.hasNext()) {
				key = (String) it.next();
				Iterator<String> itValue = sentence.get(key).iterator();
				while (itValue.hasNext()) {
					// System.out.print(it1.next() + "|");
					value = itValue.next();
					// 若找到A->B....的产生式
					if (value.indexOf(vN) == 0) {
						System.out.print(key+"->"+value);
						insert(key, vT, firstVT);
					}
				}
			}
		}
		System.out.println("栈空，算法结束\r\n");
	}

	/**
	 * 重写toString方法
	 */
	@Override
	public String toString() {
		StringBuffer result = new StringBuffer();
		String key = null;
		Set<String> valueSet = null;
		@SuppressWarnings("unused")
		String value = null;
		Iterator<String> itF = firstVT.keySet().iterator();
		while (itF.hasNext()) {
			key = itF.next();
			valueSet = firstVT.get(key);
			result.append("FIRSTVT(" + key + ")={");
			if (valueSet != null) {
				Iterator<String> itValue = valueSet.iterator();				
				while (itValue.hasNext()) {
					result.append(itValue.next() + ",");
				}
				//删除最后一个，号
				result.deleteCharAt(result.length() - 1);
			}else{
				result.append("空集");
			}
			result.append("}\r\n");
		}
		return result.toString();
	}

}