wenfaconvert.java

问题描述 设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。(算法参见教材) 【基本要求】 动态模拟算法的基本功能是： （1） 输入一个文法G； （2） 输

package sun.chenzhipeng.main;

import java.awt.TextArea;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

/**
 * @author 陈志鹏
 * @place 华东交通大学——创新大楼402
 */
class WenFaConvert {

	private List<String> wenFaList = new LinkedList();// 存放产生式  //  @jve:decl-index=0:
	private List<String> VtList = new LinkedList();// 存放终结符集合  //  @jve:decl-index=0:
	private List<String> VnList = new LinkedList();// 存放非终结符集合

	public WenFaConvert(List list) {
		// 用一个存有文法的数组来初始化该对象；
		setWenFaList(list);
		setVnList();
		setVtList();
	}

	public List getVtList() {
		return VtList;
	}

	public void setVtList() {

		for(String o:wenFaList){
			String right = getRight(o);
			int length = right.length();
			String str = right.substring(0, 1);//文法右部的第一个符号
			if(VnList.contains(str)){//第一个为非终结符，由正规文法的定义，可知 ，其后一定不再含有终结符
				continue;
				//查看下一个文法
			}
			else{
				if(!VtList.contains(str)){
					VtList.add(str);
				}
				if(length == 1){
					continue;
				}else{
					if(str.equals("(")){
						if(!VtList.contains(")")){
							VtList.add(")");
				}
					}
					else if(str.equals("{")){
						if(!VtList.contains("}")){
							VtList.add("}");
						}
					}
					else if(str.equals("[")){
						if(!VtList.contains("]")){
							VtList.add("]");
						}
					}
					else
						continue;
				}
				
			}
		}

	}
	
	

	public List getVnList() {
		return VnList;
	}

	public void setVnList() {
		for (int i = 0; i < this.wenFaList.size(); i++) {
			String chanshengshi = ((String) wenFaList.get(i));
			String Vn = chanshengshi.substring(0, chanshengshi.indexOf("-"));
			if (!VnList.contains(Vn)) {
				VnList.add(Vn);// 将产生式加入到终结符集合里去
			}
		}
	}

	public List getWenFaList() {
		return wenFaList;
	}

	public void setWenFaList(List list) {

		for (int i = 0; i < list.size(); i++) {
			String str = ((String) list.get(i)).replace('|', '⊙');
			// System.out.println("取出的产生式是:"+str);
			if (str.indexOf("⊙") != -1) {// 如果含有|符号，说明该产生式可以分解成多个子产生式
				String ss[] = str.split("⊙");
				this.wenFaList.add(ss[0]);
				String preStr = ss[0].substring(0, 1 + ss[0].indexOf(">"));
				// 用于查找产生式的左部及"->"符号
				for (int j = 1; j < ss.length; j++) {
					this.wenFaList.add(preStr + ss[j]);
				}
			} else {
				this.wenFaList.add(str);
			}
		}
	}

	/**
	 * 
	 * 计算终结符的FIRST()集合
	 * 
	 * @param textArea
	 *            TODO
	 * @param bl
	 *            TODO
	 */
	public List First(String Vn, TextArea textArea, boolean bl) {// Vn参数为一个产生式形式如：
		// S->aA,参数isInput
		// 表示该终结符是不是起始字符
		/*
		 * E->TE’ E’->+TE’ E’->ε T->FT’ T’->*FT’ T’->ε F->(E) F->i
		 * 
		 * A->BC (1)B !->ε First(A)=First(B) (2)B ->ε C !=>ε
		 * First(A)={First(B)-ε}UFirst(C) (3)B->ε C ->ε
		 * First(A)={First(B)-ε}U{First(C)-ε}U{ε}
		 */
		if (bl) {
			textArea.append("------分析非终结符" + Vn + "的First集\n");
		}
		List list = new LinkedList();// 存储指定非终结符的First集合
		Vector v = this.getCssFromVn(Vn);// 获取
		// System.out.println("该非终结符有"+v.size()+"个产生式。");
		String css = null, right;// right为产生式的右部字符串

		//
		// if (isInput) {
		// list.add("ε");// 如果是文法的输入字符，则该非终结符首先必然包含ε
		// }

		for (int k = 0; k < v.size(); k++) {
			css = (String) v.get(k);
			right = this.getRight(css);// 获取到产生式的右部，以利于分析First集
			if (bl) {
				textArea.append("--分析产生式" + css + "\n");
			}
			if (this.getVnList().contains(right.substring(0, 1))
					|| (right.length() >= 2 && this.getVnList().contains(
							right.substring(0, 2)))) {
				// 判断第一个是不是非终结符
				// 因为输入的文法是左线性文法
				// 如果第一个是非终结符的话，后面的符号都是非终结符，则依次取出个非终结符

				if (right.length() >= 2
						&& this.getVnList().contains(right.substring(0, 2))
						&& !this.getWenFaList().contains(
								right.substring(0, 2) + "->ε")) {
					// 如果文法的右部第一个非终结符符B不存在B'->ε
					// 则A->BC,First(A)=First(B)
					if (bl) {
						textArea.append("不存在" + right.substring(0, 2)
								+ "->ε ,所以非终结符" + Vn + "的First集为"
								+ right.substring(0, 2) + "的First集\n");
					}

					list = this.unionList(list, First(right.substring(0, 2),
							textArea, bl));
					continue;// 求得该产生式的结果，继续求该非终结符的下一个产生式的结果
				} else if (this.getVnList().contains(right.substring(0, 1))
						&& !this.getWenFaList().contains(
								right.substring(0, 1) + "->ε")) {
					// 如果文法的右部第一个非终结符符B不存在B->ε
					if (bl) {
						textArea.append("不存在" + right.substring(0, 1)
								+ "->ε ,所以非终结符" + Vn + "的First集为"
								+ right.substring(0, 1) + "的First集\n");
					}

					list = this.unionList(list, First(right.substring(0, 1),
							textArea, bl));// 则A->BC,First(A)=First(B)
					continue;// 求得该产生式的结果，继续求该非终结符的下一个产生式的结果
				} else {
					int i = 0, j = i + 1;
					while ((j + 1) <= right.length()
							&& this.getVnList().contains(
									right.substring(i, j + 1))// 这里两条件排序很有讲究
							|| this.getVnList().contains(right.substring(i, j))) {// 有左到右判断文法左部的字符是不是非终结符

						if ((j + 1) <= right.length()
								&& this.getVnList().contains(
										right.substring(i, j + 1))) {// 表明非终结符是X'的形式
							if (this.wenFaList.contains(right.substring(i,
									j + 1)
									+ "->ε")) {

								if (bl) {
									textArea.append("存在"
											+ right.substring(k, j + 1)
											+ "->ε ,所以非终结符" + Vn + "的First集包含"
											+ right.substring(i, j + 1)
											+ "的First集，并去掉ε\n");
								}

								list = unionList(list, First(right.substring(i,
										j + 1), textArea, bl));
								list.remove("ε");
							} else {
								if (bl) {
									textArea.append("不存在"
											+ right.substring(i, j + 1)
											+ "->ε ,所以非终结符" + Vn + "的First集包含"
											+ right.substring(i, j + 1)
											+ "的First集\n");
								}
								list = unionList(list, First(right.substring(i,
										j + 1), textArea, bl));
							}
							i += 2;
							j += 2;
						} else if (this.getVnList().contains(
								right.substring(i, j))) {// 表明非终结符是X'的形式
							if (this.wenFaList.contains(right.substring(i, j)
									+ "->ε")) {
								if (bl) {
									textArea.append("存在"
											+ right.substring(i, j)
											+ "->ε ,所以非终结符" + Vn + "的First集包含"
											+ right.substring(i, j)
											+ "的First集，并去掉ε\n");
								}
								list = unionList(list, First(right.substring(i,
										j), textArea, bl));
								list.remove("ε");
							} else {
								if (bl) {
									textArea.append("不存在"
											+ right.substring(i, j)
											+ "->ε ,所以非终结符" + Vn + "的First集包含"
											+ right.substring(i, j)
											+ "的First集\n");
								}
								list = unionList(list, First(right.substring(i,
										j), textArea, bl));
							}
							i += 1;
							j += 1;
						}
						if (i == right.length()
								&& this.getWenFaList().contains(
										Character.toString(right.charAt(right
												.length() - 1))
												+ "->ε")) {
							list.add("ε");
						}
						if ((right.length() >= 2) && j > right.length()) {
							break;
						}
					}
				}
			} else {// 第一个终结符，如：A->aB，则需要分析，抽取出终结符，存储到list中去
				char c = right.charAt(0);
				String s = Character.toString(c);
				if (bl) {
					textArea.append("将" + s + "加入" + Vn + "的First集\n");
				}
				list.add(s);// 将该终结符加如到First集合中
			}
		}
//		for (int i = 0; i < list.size(); i++) {
//			String s = (String) list.get(i);
//			if (!VtList.contains(s)) {
//				VtList.add(s);
//			}
//		}
		if (bl) {
			textArea
					.append("最后求得" + Vn + "的First集合为: " + "First(" + Vn + ")={");

			for (int i = 0; i < list.size(); i++) {
				if (i != list.size() - 1) {
					textArea.append((String) list.get(i) + ",");
				} else
					textArea.append((String) list.get(i));
			}
			textArea.append("}\n");
		}
		return list;
	}

	public String getLeft(String chanshengshi) {
		return chanshengshi.substring(0, chanshengshi.indexOf("-"));
	}

	public String getRight(String chanshengshi) {
		return chanshengshi.substring(chanshengshi.indexOf(">") + 1);// 得到文法的右部
	}

	public Vector getCssFromVn(String vn) {
		// System.out.println("非终结符是:"+vn);
		Vector v = new Vector();
		for (int i = 0; i < this.wenFaList.size(); i++) {
			String css = (String) wenFaList.get(i);
			// System.out.println("比较第"+(i+1)+"个产生式:"+css);
			if (this.getLeft(css).equals(vn)) { // 选取终结符Vn的相应产生式； Vn->xY
				v.add(css);
				// System.out.println(" 执行了添加工作");
			}
		}
		return v;
	}

	public List unionList(List a, List b) {
		for (int i = 0; i < b.size(); i++) {
			if (!a.contains(b.get(i))) {
				a.add(b.get(i));
			}
		}
		return a;
	}

	public List Follow(String Vn, boolean bl, TextArea textArea) {
		List list = new LinkedList();
		for (int i = 0; i < wenFaList.size(); i++) {
			String css = (String) wenFaList.get(i);
			List list2 = VtOfRight(Vn, css, bl, textArea);
			if (list2 != null) {
				list = unionList(list, list2);
			}

		}
		return list;
	}

	public List VtOfRight(String Vn, String css, boolean bl, TextArea textArea) {
		// System.out.println(css);
		String right = getRight(css);
		// System.out.println(right);
		String left = getLeft(css);
		List<String> list = new LinkedList();
		int index;
		int rightLength = right.length();
		if ((index = right.indexOf(Vn)) != -1/* &&Character.toString(right.charAt(index+1))!="'" */) {// 如果产生式的右部包含待求的非终结符
			// 则开始求其Follow集
			// System.out.println(Vn.length()==1);
			// System.out.println(Character.toString(right.charAt(index+1)).equals("'"));
			if (Vn.length() == 1
					&& (index == rightLength - 2 && Character.toString(
							right.charAt(index + 1)).equals("'"))) {
				// System.out.println("上当了,闪，运行下一个产生式");
				return list;
			}
			// System.out.println("---------开始求" + Vn + "的Follow集");
			if (bl) {
				textArea.append("---------开始求 " + Vn + " 的Follow集\n");
			}
			 System.out.println("--分析产生式" + css);
			if (bl) {
				textArea.append("--分析产生式 " + css + " \n");
			}
			// System.out.println("index "+index);
			// System.out.println("right.length() "+right.length());
			if (index == rightLength - 1
					|| (Character.toString(right.charAt(index + 1)) == "'"
							&& Vn.length() == 2 && index == rightLength - 2)) {
				// 如果该非终结符是最后一字符
				// 则将#加入到Follow集中
				if (bl) {
					textArea.append("该非终结符是最后一字符,将 # 加入 " + Vn + " 的Follow集\n");
				}
				if (!list.contains("#")) {
					// System.out.println("添加#");
					list.add("#");
				}
				// 再考虑另一种情况
				String rePlaceCss = null;
				// System.out.println("然后再替换求解");
				if (bl) {
					textArea
							.append("因为该终结符出现在产生式的末尾，则若有其他产生式右部含有该产生式左部输入符号B(B为非终结符)，"
									+ "则用前一个产生式的右部替换B,然后继续求解\n");
				}
				for (int i = 0; i < wenFaList.size(); i++) {
					rePlaceCss = (String) wenFaList.get(i);

					// System.out.println();
					String newRight = getRight(rePlaceCss);
					if (newRight.indexOf(left) == -1) {
						continue;
					}
					if (bl) {
						textArea.append("发现产生式 " + rePlaceCss + " 的右部含有 "
								+ left + " ,然后用 " + right + " 将其替换，并继续求解！\n");
					}
					newRight = newRight.replaceAll(left, right);
					// System.out.println("VtOfRight(" + Vn + ", " + newRight
					// + ")");
					VtOfRight(Vn, rePlaceCss, bl, textArea);
				}
				// 然后用该产生式的右部
			} else {

				String nextV = Character.toString(right.charAt(index + 1));// 非终结符的后一个字符
				if (VtList.contains(nextV)
						/*&& Character.toString(right.charAt(index + 2)) != "'"*/) {
					// 该非终结符的后一个字符为终结符
					// 则将该终结符加如其Follow集中
					// System.out.println("该非终结符的后一个字符为终结符,加入终结符" + nextV
					// + "到Follow(" + Vn + ")中");
					if (bl) {
						textArea.append("非终结符 " + Vn + " 的后一个字符是终结符 " + nextV
								+ " ,将终结符加入到 " + Vn + " 的Follow集中\n");
					}
					if (!list.contains(nextV)) {
						list.add(nextV);
					}
				} else {// 如果该非终结符的后一个字符为非终结符
					if (bl) {
						textArea.append("非终结符 " + Vn + " 的后一个字符为非终结符,加入非终结符"
								+ nextV + "的First集合到Follow(" + Vn + ")中");
					}
					List listtemp = First(nextV, null, false);
					if (listtemp.contains("ε")) {
						listtemp.remove("ε");
						if (!list.contains("#")) {
							list.add("#");
						}
					}
					list = unionList(list, listtemp);
				}
			}
		}
		return list;
	}
}