firstset.java

C语言的词法、语法分析器 输出语法分析树

		} catch (Exception e) {
			System.out.println("public void addToList()" + e.getMessage());
			e.printStackTrace();
		}
	}

	/**
	 * 
	 * Note:This function must be called after function : addToList
	 * 
	 */
	public void validateGrammar() {
		for (int i = 0; i < this.vectorGrammarTogether.size(); i++) {
			LinkedList list = (LinkedList) this.vectorGrammarTogether.get(i);
			for (int j = 0; j < list.size(); j++) {
				String str = ((String) list.get(j)).trim();
				if (!this.tokenPro.isTerminal(str)) {
					if (!this.listNonTerminals.contains(str)) {
						System.err
								.println("Syntax error happened in grammar file, line no.:"
										+ (i + 1));
						System.err
								.println("\t"
										+ " -->\""
										+ str
										+ "\" :Token is neither non-terminal nor terminal.");
						System.err.println("System will exit...");
						try{
							System.in.read();
							System.exit(0);
						}catch(IOException e){
							e.printStackTrace();
						}
					}
				}
			}
		}

	}

	/**
	 * 辅助函数：获得一句话中某个符号的个数
	 * 
	 * @param source
	 *            话语
	 * @param symbol
	 *            符号
	 * @return int型的指定符号个数
	 */
	public static int getSymbolNum(String source, char symbol) {
		int num = 0;
		for (int i = 0; i < source.length(); i++) {
			if (source.charAt(i) == symbol) {
				num++;
			}
		}
		return num;
	}

	/**
	 * 得到文法的first集
	 * 
	 */
	public void getFirstSet() {
		// 装有每条文法的链表数组
		this.listGrammar = new LinkedList[vectorGrammar.size()];
		// 按照候选装每个非终结符号的First集链表数组
		this.listFirstSetApart = new LinkedList[vectorGrammar.size()];
		// 按照非终结符号装每个符号的First集的链表数组
		this.listFirstSet = new LinkedList[this.numOfNonTerminals];
		// 初始化lists数组
		try {
			for (int i = 0; i < vectorGrammar.size(); i++) {
				listGrammar[i] = (LinkedList) vectorGrammar.get(i);
			}
		} catch (Exception e) {
			System.out.println("初始化文法数组错误：" + e.getMessage());
		}
		// 初始化各个firsts数组
		try {
			for (int i = 0; i < vectorGrammar.size(); i++)
				listFirstSetApart[i] = new LinkedList();
			for (int i = 0; i < vectorGrammar.size(); i++) {
				listFirstSetApart[i].add(listGrammar[i].get(0));
			}
		} catch (Exception e) {
			System.out.println("初始化first集数组错误：	" + e.getMessage());
		}
		// 求First集
		int first = 0;
		boolean changed = true;

		boolean isChanged[] = new boolean[vectorGrammar.size()];
		String symbol = "";// 产生式中第一个字符
		while (changed) {
			for (int assign = 0; assign < isChanged.length; assign++) {
				isChanged[assign] = false;
			}
			for (int i = 0; i < vectorGrammar.size(); i++) {
				int k = 1;
				boolean isContinue = true;
				while (isContinue && k <= listGrammar[i].size() - 1) {
					String symbol2 = "";
					boolean isToJudgeContainsEmpty = true;// 是否需要判断first(Xk)包含空字
					// 如果得到的每行的第一个值是非终结符号，这点肯定满足
					if (!tokenPro.isTerminal(symbol = (String) listGrammar[i]
							.get(0))) {
						symbol2 = (String) listGrammar[i].get(k);// 产生式中第二个字符
						// 如果下一个符号是终结字符，直接加到当前链表的first集合中
						if (tokenPro.isTerminal(symbol2)) {
							isToJudgeContainsEmpty = false;
							if (!listFirstSetApart[i].contains(symbol2)) {
								listFirstSetApart[i].add(symbol2.trim());
								isChanged[i] = true;// 改变了
							}
						} else {
							// 如果第二个不是终结字符，那么就找到此符号的first集，
							// 将其中的除empty外的所有符号加入到当前非终结符号的first集合中
							for (int a = 0; a < vectorGrammar.size(); a++) {// 找到以该非终结字符为首的链表
								String symbol3 = (String) listGrammar[a].get(0);
								if (symbol3.equals(symbol2)) {// 二者相等，说明找到了
									for (int b = 1; b < listFirstSetApart[a]
											.size(); b++) {// 找到之后将其first集中的所有东西给当前链表
										String tmp = (String) listFirstSetApart[a]
												.get(b);
										if (!tmp.equalsIgnoreCase("EMPTY")) {
											if (!listFirstSetApart[i]
													.contains(tmp)) {
												listFirstSetApart[i].add(tmp
														.trim());
												isChanged[i] = true;
											}
										}
									}
									// break; 此处不能break
								}
							}
						}
					}
					// 判断symbol2的first集中是否有空
					if (isToJudgeContainsEmpty) {
						for (int p = 0; p < vectorGrammar.size(); p++) {// 找到以该非终结字符为首的链表
							String symbol3 = (String) listGrammar[p].get(0);
							if (symbol3.equals(symbol2)) {// 二者相等，说明找到了
								if (!this.listFirstSetApart[p]
										.contains("EMPTY")) {
									isContinue = false;
								} else {
									isContinue = true;
									break;
								}
								// break; 此处不能break
							}
						}
					} else {
						isContinue = false;
					}
					k++;
				}// end of while
				if (isContinue) {
					if (!listFirstSetApart[i].contains("EMPTY")) {
						listFirstSetApart[i].add("EMPTY".trim());
						isChanged[i] = true;
					}
				}
			}
			for (int i = 0; i < vectorGrammar.size(); i++) {
				if (isChanged[i]) {
					changed = true;
					break;
				} else
					changed = false;
			}
		}
	}

	/**
	 * 将First集合装入Vector对象
	 * 
	 */
	public void constructFirstSet() {
		// 将按候选存储的first集合合并成按照非终结字符存储的first集合
		String tmp = (String) listFirstSetApart[0].get(0);
		// 初始化firstSet数组，在每个链表中装入一个值：非终结符号
		for (int i = 0; i < this.listNonTerminals.size(); i++) {
			listFirstSet[i] = new LinkedList();
			listFirstSet[i].add(this.listNonTerminals.get(i));
		}
		// 整合firstSet数组
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			String str = (String) listFirstSet[i].get(0);
			for (int j = 0; j < vectorGrammar.size(); j++) {
				String str1 = (String) listFirstSetApart[j].get(0);
				// 如果两者输入同一个非终结符号,直接将另一个的数据复制过来，
				// 如果中间出现重叠，那么文法不是LL(1)的，程序报错退出。
				if (str.equals(str1)) {
					for (int k = 1; k < listFirstSetApart[j].size(); k++) {
						if (!listFirstSet[i].contains(listFirstSetApart[j]
								.get(k)))
							listFirstSet[i].add(listFirstSetApart[j].get(k));
						else {
							System.err
									.println("The grammar is not LL(1)--候选first交集不为空\nProgram will exit...");
							int line = this.listNonTerminals.indexOf(str) + 1;
							System.err
									.println("Line no--" + line + ":\t" + str);
							try{
								System.in.read();
								System.exit(0);
							}catch(IOException e){
								e.printStackTrace();
							}
						}
					}
				}
			}
		}
		// 合并完毕

		// 存储两种first集合到Vector对象中
		for (int i = 0; i < vectorGrammar.size(); i++) {
			this.vectorFirstSetApart.add(listFirstSetApart[i]);
		}
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			this.vectorFirstSet.add(listFirstSet[i]);
		}
	}

	/**
	 * 主函数，测试时候使用。
	 * 
	 * @param args
	 *            没有使用
	 * @throws IOException
	 */
	public static void main(String args[]) throws IOException {
		try {
			FirstSet first = new FirstSet("c-minus-2");
			first.addToList(); // 将文法文件装入数据结构
			first.validateGrammar();
			first.getFirstSet(); // 得到初期存储在多个链表中的first集合
			first.constructFirstSet(); // 将多个链表存储的first集合装入vector中。
			first.printFirstSet();
		} catch (Exception e) {
			System.out.println("main " + e.getMessage());
		}
	}
}