lastvt.java

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

package you.test;

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

public class LastVT extends BaseVT {

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

	// 默认构造函数，为lastVT赋初值
	public LastVT() {

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

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

		// 非终结符，文法左部
		String key = null;
		// 文法右部
		String value = null;
		// 产生式尾字母
		String end1 = null;
		// 倒二个字符
		String end2 = null;
		// 倒三个字符
		String end3 = null;
		String t = null;

		// 将A->....a或A->....aB的产生式
		System.out.println("找到所有的A->....a或A->....aB的产生式");
		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();

				// 尾字符
				end1 = "" + value.charAt(value.length() - 1);
				// 重新置为null
				end2 = null;
				end3 = null;
				if (value.length() > 1) {
					end2 = "" + value.charAt(value.length() - 2);
				}
				if (value.length() > 2) {
					end3 = "" + value.charAt(value.length() - 3);
					t = end1 + end2;
				}
				// 如果为终结符，A->....a
				if (terminal.contains(end1)) {
					System.out.print(key+"->"+value);	
					insert(key, end1, lastVT);
				}
				// A->...aT'
				else if (end3 != null && nonTerminal.contains(t)
						&& terminal.contains(end3)) {
					System.out.print(key+"->"+value);	
					insert(key, end3, lastVT);
				} // A->...aB
				else if (end2 != null && nonTerminal.contains(end1)
						&& terminal.contains(end2)) {
					System.out.print(key+"->"+value);	
					insert(key, end2, lastVT);
				}
			}
		}
	}

	/**
	 * 栈操作
	 */
	@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
			System.out.println("弹出栈顶元素:"+top);
			t = top.indexOf(",");
			vN = top.substring(1, t);
			vT = "" + top.charAt(t + 1);
			// 查找所有A->.....B的产生式
			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()) {
					value = itValue.next();
					// 若找到A->....B的产生式
					if (value.lastIndexOf(vN) == 0) {
						System.out.print(key+"->"+value);
						insert(key, vT, lastVT);
					}
				}
			}			
		}
		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 = lastVT.keySet().iterator();
		while (itF.hasNext()) {
			key = itF.next();
			valueSet = lastVT.get(key);
			result.append("LASTVT(" + 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();
	}
}