词法分析

开发平台：
Java

Parsing.java：源码内容
							import java.io.*;
import java.util.*;
import javax.swing.tree.DefaultMutableTreeNode;
public class Parsing {
	Hashtable rules;
	List edges;
	double sProb;
	
	public Parsing() {
		rules = new Hashtable();
		edges = new ArrayList();
	}
	public String BottomUp(String fileName) throws IOException {
		String result = new String();
		String r = new String();
		try {
			this.ReadRules("f:/上下文无关rule.txt");
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		//String fileName = new String("f:/yuliao.txt");
		BufferedReader in = new BufferedReader(new FileReader(fileName));
		String s;
		while ((s = in.readLine()) != null) {
			// System.out.println(s);
			long start = System.currentTimeMillis(); // 获取最初时间
			r = this.ProbParseOne(s);
			long end = System.currentTimeMillis(); // 获取运行结束时间
			System.out.println("程序运行时间1： " + (end - start) + "ms");
			
			this.edges = new ArrayList();
			System.out.println(r);
			result += r;
		}
		in.close();
		// String msg;
		return result;
	}
	public void ReadRules(String fileName) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(fileName));
		String s;
		while ((s = in.readLine()) != null) {
			Key key = new Key(s);
			Value value = new Value(s);
			this.putHashNode(key, value);
		}
		in.close();
	}
	void putHashNode(Key key, Value value) {
		ArrayList valueList;
		valueList = (ArrayList) rules.get(key);
		if (valueList == null) {
			valueList = new ArrayList();
			valueList.add(value);
			rules.put(key, valueList);
		} else {
			valueList.add(value);
		}
	}
	public String ProbParseOne(String s) {
		int i, j, wn = 0; // wn是语句S中词的个数
		int pId; // 该局部分析的序号
		String w;
		ProbEdge e = new ProbEdge();
		// ProbRules r = new ProbRules();
		Vector theRs = new Vector();
		Value v;
		while (s.length() > 0) { // 输入句不为空时
			wn++;
			i = s.indexOf(" ");
			if (i < 0) {
				w = s;
				s = new String();
			} else {
				w = s.substring(0, i);
				s = s.substring(i + 1);
				s.trim();
			}
			// 添加该局部分析
			pId = edges.size();
			e = new ProbEdge(w, wn, pId);
			edges.add(e);
			// 运用提升规则
			theRs = new Vector();
			theRs.add(e.GetRoot());
			ArrayList valueList = this.getProbRules(theRs);
			if (valueList != null) {
				// r = (ProbRules) rules.get(rId);
				// edges.add(new ProbEdge(e, pId, this.rules, rId, this.edges));
				for (int k = 0; k < valueList.size(); k++) {
					v = (Value) valueList.get(k);
					pId = edges.size();
					edges.add(new ProbEdge(e, v, pId));
				}
			}
		}
		for (j = 1; j <= wn; j++)
			// 运用提升规则、捆绑规则添加局部分析
			for (i = 1; i + j <= wn; i++) {
				// System.out.println(i + " " + j);
				InsertEdges(i, i + j, wn);
			}
		String t = this.getProbTrees(wn); // 构造带概率的分析串
		//tRoot = this.getProbTrees2(wn);
		return t; // 输出分析结果
	}
	public List find(int first, int last, List edgeList, int wn) {
		ProbEdge e, e0, e1;
		int pId;
		Vector theRs;
		ArrayList valueList;
		Value value;
		for (int i = 0; i < edges.size(); i++) {
			e0 = (ProbEdge) edges.get(i);
			if (e0.first != first)
				continue;
			if (e0.first == first && e0.last == last) {
				// 匹配处理，无需添加到链表
				edgeList.add(e0);
				theRs = new Vector();
				for (int j = 0; j < edgeList.size(); j++) {
					e1 = (ProbEdge) edgeList.get(j);
					theRs.add(e1.GetRoot());
				}
				valueList = this.getProbRules(theRs);
				// 匹配不成功
				if (valueList == null) {
					edgeList.remove(edgeList.size() - 1);
					continue;
				}
				for (int k = 0; k < valueList.size(); k++) {
					value = (Value) valueList.get(k);
					pId = edges.size();
					e = new ProbEdge(edgeList, value, pId);
					// 若没有完全分析完已归约出S则不加入局部分析表中
					if (!(e.GetRoot().equals("S") && (e.first != 1 || e.last != wn))) {
						// 需要剪枝则代替原有局部分析，在isPruning(e)中实现
						// 不需要剪枝则加入当前局部分析
						if (!isPruning(e))
							edges.add(e);
					}
				}
				// 匹配列表最后一项删除
				edgeList.remove(edgeList.size() - 1);
				continue;
			}
			if (e0.first == first && e0.last < last) {
				// 添加该E
				edgeList.add(e0);
				edgeList = find(e0.last + 1, last, edgeList, wn);
			}
		}
		if (edgeList.size() > 0)
			edgeList.remove(edgeList.size() - 1);
		return edgeList; // 返回
	}
	boolean isPruning(ProbEdge e) {
		ProbEdge e2;
		for (int k = edges.size() - 1; k >= 0; k--) {
			e2 = (ProbEdge) edges.get(k);
			if (e2.first != e.first || e2.last != e.last)// 起点和终点不同即可结束查找（因为跟e的起点、终点相同的局部分析必然连续排列）
				break;
			if (e2.GetRoot().equals(e.GetRoot())) {
				if (e.insideProb > e2.insideProb) {
					e2.root = e.root;
					e2.insideProb = e.insideProb;
					e2.child = e.child;
					return true;
				}
				if (e.insideProb < e2.insideProb)
					return true;
			}// if
		}// for
		return false;
	}
	public void InsertEdges(int first, int last, int wn) {
		List edgeList = new ArrayList();
		edgeList = find(first, last, edgeList, wn);
	}
	
	public String getProbTrees(int wid) // 获取分析结果
	{
		String s = new String();
		String temp;
		ProbEdge e;
		// double sInsideProb = 0.0;
		for (int i = 0; i < edges.size(); i++) {
			e = (ProbEdge) edges.get(i);
			if (e.first == 1 && e.last == wid && e.GetRoot().equals("S"))
				s += "n" + new Double(e.insideProb).toString() + ": "
						+ this.getOneTree(e) + "nn"; // 添加该局部分析结果
		}
		int n = edges.size();
		temp = new String("局部分析" + n + "个");
		if (s == null)
			s = temp + "句子不合法";
		else
			s = temp + s;
		return s;
	}
	public String getOneTree(ProbEdge e) // 获取一棵分析树
	{
		String s = e.root;
		int index;
		if (e.child.isEmpty()) {
			return s;
		}
		s += " ( ";
		int i = 0;
		// 添加第一棵子树
		index = ((Integer) e.child.get(i)).intValue();
		s += this.getOneTree((ProbEdge) edges.get(index));
		i++;
		// 添加除首尾两棵子树外的中间段子树
		for (; i < e.child.size(); i++) {
			index = ((Integer) e.child.get(i)).intValue();
			s += " + " + this.getOneTree((ProbEdge) edges.get(index));
		}
		s += " )";
		return s;
	}
	public ArrayList getProbRules(Vector theRs) {
		Key key;
		ArrayList valueList;
		
		key = new Key(theRs);
		//System.out.println(key.toString());
		valueList = (ArrayList) rules.get(key);
		//System.out.println(valueList.toString());
		
		return valueList;
	}
	public static void main(String[] args) {
		Parsing p = new Parsing();
		try {
			p.BottomUp("ddd");
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

						