followset.java

java写的词法和语法分析器

package cminus;

/**
 * Class name：FollowSet.
 * 继承了FirstSet类。
 * 功能：
 * 		得到文法的follow集合，并且判断文法是否是LL(1)文法。
 * @author Administrator
 */
import java.util.*;
import java.io.*;

public class FollowSet extends FirstSet {
	// 存储follow集的Vector对象
	public Vector vectorFollowSet = new Vector();

	public Vector vectorFollowSetApart = new Vector();

	// 暂存follow集的链表数组
	public LinkedList listFollowSet[]; // 按照非终结字符种类存放

	public LinkedList listFollowSetApart[];// 按照各个非终结字符的候选来存放

	/**
	 * 构造函数
	 * 
	 * @param fileName
	 */
	public FollowSet(String fileName) {
		super(fileName);

	}

	/**
	 * 打印follow set到标准输出流
	 * 
	 */
	public void printFollowSet() {
		// print first set
		System.out.println("\nThe follow set of the grammar:");
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			LinkedList list = (LinkedList) this.vectorFollowSet.get(i);
			for (int j = 0; j < list.size(); j++) {
				if(j==0){
					System.out.print(list.get(j)+":\t");
				}
				else{
					System.out.print(list.get(j) + " ");
				}
			}
			System.out.println();
		}
	}

	/**
	 * 得到文法的Follow集合
	 * 
	 */
	public void getFollowSet() {
		// 初始化暂存follow集的链表数组
		listFollowSet = new LinkedList[this.numOfNonTerminals];
		listFollowSetApart = new LinkedList[this.vectorGrammar.size()];

		// 初始化各个listFollowSetApart数组，按照候选存储各个非终结符号的Follow set
		try {
			for (int i = 0; i < vectorGrammar.size(); i++)
				listFollowSetApart[i] = new LinkedList();
			for (int i = 0; i < vectorGrammar.size(); i++) {
				// 每个链表都存储了一个非终结符号作为标识
				listFollowSetApart[i].add(listGrammar[i].get(0));
			}
		} catch (Exception e) {
			System.out.println("初始化follow集数组错误：	" + e.getMessage());
		}
		// 求Follow集
		// 初始化
		listFollowSetApart[0].add("$".trim());
		boolean isChanged[] = new boolean[vectorGrammar.size()];
		boolean changed = true;
		while (changed) {
			for (int tt = 0; tt < isChanged.length; tt++) {
				isChanged[tt] = false;
			}
			for (int i = 0; i < this.vectorGrammar.size(); i++) {
				//如果token个数为2
				if (listGrammar[i].size() == 2) {
					//如果第二个token不是终结符号，则将第一个的follow集给第二个token的follow集。
					String str1 = (String) listGrammar[i].get(0);
					String str = (String) listGrammar[i].get(1);
					if (!tokenPro.isTerminal(str)) {
						for (int k = 0; k < this.vectorGrammar.size(); k++) {// find str's follow set
							if (((String) listFollowSetApart[k].get(0)) .equals(str)) {
								for (int a = 0; a < this.vectorGrammar.size(); a++) {// find str1's follow set
									String tmp1 = (String) listFollowSetApart[a] .get(0);
									if (str1.equals(tmp1)) {
										for (int s = 1; s < listFollowSetApart[a] .size(); s++) {
											String tmp = (String) listFollowSetApart[a] .get(s);
												if (!listFollowSetApart[k] .contains(tmp)) {
													listFollowSetApart[k] .add(tmp.trim());
													isChanged[i] = true;
												}
										}
										// break;// can not be break here
									}
								}
								break;// should be break here
							}
						}
					}
				}
				//如果token的个数大于二
				else {
					for (int j = 1; j < listGrammar[i].size() - 1; j++) {
						int tempflag = j;//临时标记变量，用来指示临时链表从何处(哪个token)开始构建
						// 一次获取两个token
						String str1 = (String) listGrammar[i].get(j);
						String str2 = (String) listGrammar[i].get(j + 1);//此次得到str2为了判断结尾时使用
						if (!tokenPro.isTerminal(str1)) {
							//将str2 str3...的first集中不是empty的元素给str1的follow集
							//通过将上面的first集合求出装载在一个临时的链表里，然后复制这个链表来实现。
							LinkedList tmpList = new LinkedList();//存储first集的临时链表
							String first = (String) listGrammar[i].get(0);//获取第一个token

							//构建这个临时链表，将str2 str3...的first集装入临时链表
							boolean isBreak = false;
							for (int bb = tempflag + 1; bb < this.listGrammar[i].size(); bb++) {
								String bbString = (String) this.listGrammar[i].get(bb);//得到str2
								if (tokenPro.isTerminal(bbString)) {
									if (!tmpList.contains(bbString)) {
										tmpList.add(bbString);
									}
									isBreak = true;
									break;
								} 
								else {
									//找到str2的first集
									for (int s = 0; s < this.numOfNonTerminals; s++) {
										String tmp2 = (String) listFirstSet[s].get(0);
										if (bbString.equals(tmp2)) {// find it
											// copy bbString's first to tmpList
											for (int hh = 1; hh < listFirstSet[s].size(); hh++) {
												if(!listFirstSet[s].contains("EMPTY")){
													isBreak = true;
												}
												String hhString = (String) listFirstSet[s].get(hh);
												if (!tmpList.contains(hhString)&&
														(!hhString.equalsIgnoreCase("EMPTY"))) {
													tmpList.add(hhString);
												}
											}
											break;
										}
									}
									if(isBreak){
										break;
									}
								}
							}
							if(isBreak == false){
								tmpList.add("EMPTY");
							}
							// 将临时链表中的除了EMPTY的元素拷贝到str1的follow集中
							for (int k = 0; k < vectorGrammar.size(); k++) {
								String tmp3 = (String) listFollowSetApart[k].get(0);
								if (str1.equals(tmp3)) {
									for (int fff = 0; fff < tmpList.size(); fff++) {
										String tmpStr = ((String)tmpList.get(fff)).trim();
										if(!tmpStr.equalsIgnoreCase("EMPTY")){
											if (!listFollowSetApart[k].contains(tmpStr)) {
												listFollowSetApart[k].add(tmpStr);
												isChanged[i] = true;
											}
										}
									}
									break;
								}
							}
							
							boolean tempboolean = false;//标记临时链表中是否有empty的变量。
							if(tmpList.contains("EMPTY")){
								tempboolean = true;
							}
							tmpList.clear();

							//如果临时链表中有EMPTY，则将第一个token的follow集拷贝给str1的follow集
							if (tempboolean == true) {
								for (int k = 0; k < vectorGrammar.size(); k++) {// find str1's follow set
									String tmp3 = (String) listFollowSetApart[k] .get(0);
									if (str1.equals(tmp3)) {// find it.
										for (int f = 0; f < vectorGrammar .size(); f++) {// find first's follow set
											String tmp4 = (String) listFollowSetApart[f] .get(0);
											if (first.equals(tmp4)) {//find it
												for (int g = 1; g < listFollowSetApart[f] .size(); g++) {
													String tmp5 = (String) listFollowSetApart[f] .get(g);
													if (!listFollowSetApart[k].contains(tmp5)) {
															listFollowSetApart[k].add(tmp5.trim());
															isChanged[i] = true;
													}
												}
											}
										}
										break;
									}
								}
							}
						}
						//如果一个token是这行的最后一个token，则将第一个token的follow集拷贝到这个token的follow集中。
						if (j == listGrammar[i].size() - 2) {
							// At this time ,str2 is the last token
							if (!tokenPro.isTerminal(str2)) {
								for (int a = 0; a < this.vectorGrammar.size(); a++) {// Find str2's follow set
									String temp = (String) listFollowSetApart[a] .get(0);
									if (str2.equals(temp)) {//find it
										String heihei = (String) listGrammar[i] .get(0);
										// Find the first token's follow set
										for (int b = 0; b < this.vectorGrammar .size(); b++) {
											String temp2 = (String) listFollowSetApart[b] .get(0);
											if (heihei.equals(temp2)) {//find it,then start copying.
												for (int mama = 1; mama < listFollowSetApart[b] .size(); mama++) {
													String temp3 = (String) listFollowSetApart[b] .get(mama); 
													if (!listFollowSetApart[a] .contains(temp3)) {
														listFollowSetApart[a] .add(temp3 .trim());
														isChanged[i] = true;
													} 
												}
											}
										}
										break;
									}
								}
							} 
						}
					}// end of for
				}// end of else
			}// end of for
			// Judge whether should run the "while" loop.
			for (int aaaa = 0; aaaa < this.vectorGrammar.size(); aaaa++) {
				if (isChanged[aaaa]) {
					changed = true;
					break;
				} else {
					changed = false;
				}
			}
		}// end of the while loop.
	}

	public void constructFollowSet() {
		// 将按候选存储的follow集合合并成按照非终结字符存储的follow集合
		String tmp = (String) listFirstSetApart[0].get(0);
		// 初始化listFollowSet数组，在每个链表中装入一个值：非终结符号
		for (int i = 0; i < this.listNonTerminals.size(); i++) {
			listFollowSet[i] = new LinkedList();
			listFollowSet[i].add(this.listNonTerminals.get(i));
		}
		// 整合listFollowSet数组
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			String str = (String) listFollowSet[i].get(0);
			for (int j = 0; j < vectorGrammar.size(); j++) {
				String str1 = (String) listFollowSetApart[j].get(0);
				// 如果两者输入同一个非终结符号,直接将另一个的数据复制过来，
				if (str.equals(str1)) {
					for (int k = 1; k < listFollowSetApart[j].size(); k++) {
						if (!listFollowSet[i].contains(listFollowSetApart[j]
								.get(k)))
							listFollowSet[i].add(listFollowSetApart[j].get(k));
					}
				}
			}
		}
		// 合并完毕

		// 存储两种follow集合到Vector对象中
		for (int i = 0; i < vectorGrammar.size(); i++) {
			this.vectorFollowSetApart.add(listFollowSetApart[i]);
		}
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			this.vectorFollowSet.add(listFollowSet[i]);
		}
	}

	/**
	 * When we get the follow set ,we can judge the whether the grammar is LL(1)
	 * for the second step: if First(A) contains EMPTY, then if the intersection
	 * of First(A) and Follow(A) is empty, the grammar is LL(1).
	 * 
	 * NOTE: The first step of judgement has been done in class FirstSet. And to
	 * be more security, I take the third step to do the judge in contructing
	 * the parsing table.
	 */
	public void isLL1() {
		for (int i = 0; i < this.vectorFirstSet.size(); i++) {
			for (int j = 0; j < this.listFirstSet[i].size(); j++) {
				if (this.listFirstSet[i].contains("EMPTY")) {
					String nonTerminal = (String) this.listFollowSet[i].get(0);
					for (int k = 1; k < this.listFollowSet[i].size(); k++) {
						String tmp = (String) this.listFollowSet[i].get(k);
						if (this.listFirstSet[i].contains(tmp)) {
							// 对selection-stmt-1进行特殊排除，selection-stmt-1的二义性无法消除
							if (!nonTerminal.equals("selection-stmt-1")) {
								System.err
										.println("The grammar is not LL(1)--first和follow交集不为空.\nProgram will exit...");
								int line = this.listNonTerminals
										.indexOf(nonTerminal) + 1;
								System.err.println("Line no--" + line + ":\t"
										+ nonTerminal);
								try{
									System.in.read();
									System.exit(0);
								}catch(IOException e){
									e.printStackTrace();
								}
							}
						}
					}
				}
			}
		}
	}

	/**
	 * Main function ,for testing use.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		FollowSet followset = new FollowSet("test");
		followset.getFollowSet();
		followset.printFollowSet();
	}

}