calculateset.java

词法和语法分析器

package cminusCompiler;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * @author tanfei E-mail:[e-mail]
 * @version Create Time：2007-12-7 下午09:28:45 description:
 */
public class CalculateSet {

	private LinkedList<Nonterminal> nonterminal;

	private HashMap<Integer, String> terminal;

	public CalculateSet(LinkedList<Nonterminal> n, HashMap<Integer, String> t) {
		nonterminal = n;
		terminal = t;
	}

	public void calculateFirstSet() {
		Nonterminal nont, nont1;
		int k;
		boolean conti;
		LinkedList elementList, tempList;
		String element;
		k = 0;
		while (isEveryoneChange()) {
			setAllToFalse();
			k++;
			for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
				nont = (Nonterminal) i.next();
				for (ListIterator j = nont.getFollowElement().listIterator(); j
						.hasNext();) {
					elementList = (LinkedList) j.next();
					conti = true;
					for (ListIterator m = elementList.listIterator(); m
							.hasNext()
							&& conti;) {
						element = (String) m.next();
						if ((terminal.containsValue(element))
								&& (!nont.getFirstSet().contains(element))) {
							nont.getFirstSet().add(element);
							nont.setIsChanged(true);
							conti = false;
						} else if (terminal.containsValue(element)) {
							conti = false;
						} else if (element.equals("empty")){
							conti = true;
							}else {

							nont1 = getInstance(element);
							if (nont1.getFirstSet().size() == 0)
								conti = false;
							else {
								tempList = nont1.getFirstSet();
								for (ListIterator p = tempList.listIterator(); p
										.hasNext();) {
									String sFirst = (String) p.next();
									if (!nont.getFirstSet().contains(sFirst)) {
										if(!sFirst.equals("empty")){
										nont.getFirstSet().add(sFirst);
										nont.setIsChanged(true);}
									}
								}
								if (tempList.contains("empty")) {
									conti = true;
								} else {
									conti = false;
								}
							}
						}
					}
					if (conti) {
						if(!nont.getFirstSet().contains("empty")){
						   nont.getFirstSet().add("empty");
						}
					}
				}
			}
		}
	}

	public void CalculateFollowSet() {
		Nonterminal nont, nont1, nont2;
		LinkedList tempList, elementList, tempList1;
		String element, element1;
		boolean conti;
		int n = 0;
		nont = nonterminal.getFirst();
		nont.getFollowSet().add("$");
		setAllToTrue();
		while (isEveryoneChange()) {
			setAllToFalse();
			for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
				nont = (Nonterminal) i.next();
				tempList = nont.getFollowElement();
				for (ListIterator j = tempList.listIterator(); j.hasNext();) {
					elementList = (LinkedList) j.next();
					for (ListIterator k = elementList.listIterator(); k
							.hasNext();) {
						element = (String) k.next();
						if ((!terminal.containsValue(element))&&(!element.equals("empty"))) {
							nont1 = getInstance(element);
							if (k.hasNext()) {
								conti = true;
								n = 0;
								while (k.hasNext() && conti) {
									element1 = (String) k.next();
									n++;
									if (terminal.containsValue(element1)) {
										if(!nont1.getFollowSet().contains(element1)){
										nont1.getFollowSet().add(element1);
										nont1.setIsChanged(true);}
										conti = false;
									} else {
										nont2 = getInstance(element1);
										addFIToFL(nont1, nont2);
										tempList1 = nont2.getFirstSet();
										if (!tempList1.contains("empty")) {
											conti = false;
										}
										else if(!k.hasNext()){
											if(!nont.getName().equals(nont1.getName())){
											addFLToFL(nont, nont1);
											}
										}
									}
								}
								while(!(n == 0)){
									k.previous();
									n--;
								}
							} else {
								addFLToFL(nont, nont1);
							}
						}
					}
				}
			}
		}

	}

	private boolean isEveryoneChange() {
		Nonterminal nont;
		for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
			nont = (Nonterminal) i.next();
			if (nont.getIsChanged())
				return true;
		}
		return false;
	}

	private void setAllToFalse() {
		Nonterminal nont;
		for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
			nont = (Nonterminal) i.next();
			nont.setIsChanged(false);
		}
	}

	private void setAllToTrue() {
		Nonterminal nont;
		for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
			nont = (Nonterminal) i.next();
			nont.setIsChanged(true);
		}
	}

	private Nonterminal getInstance(String name) {
		Nonterminal nont = new Nonterminal(name);
		for (ListIterator i = nonterminal.listIterator(); i.hasNext();) {
			nont = (Nonterminal) i.next();
			if (nont.getName().equals(name))
				return nont;
		}
		return nont;
	}
	
	private void addFLToFL(Nonterminal n1, Nonterminal n2){
		String element;
		for(ListIterator i = n1.getFollowSet().listIterator(); i.hasNext();){
			element = (String)i.next();
			if(!n2.getFollowSet().contains(element)){
				n2.getFollowSet().add(element);
				n2.setIsChanged(true);
			}
		}
	}
	
	private void addFIToFL(Nonterminal n1, Nonterminal n2){
		String element;
		for(ListIterator i = n2.getFirstSet().listIterator(); i.hasNext();){
			element = (String) i.next();
			if (!element.equals("empty")) {
				if (!n1.getFollowSet().contains(element)) {
					n1.getFollowSet().add(element);
					n1.setIsChanged(true);
				}
			}
		}
	}

}