ll1grammar.java

用java语言编写的LL(1)文法分析程序

			char firstRightLetters = right.charAt(0);
			int m = GeneFormula.non_terminate.indexOf(left);
			int n;
			int j = first[GeneFormula.grammarLetters.indexOf(firstRightLetters)]
					.length();
			for (int t = 0; t < j; t++) {
				n = GeneFormula.terminate
						.indexOf((first[GeneFormula.grammarLetters
								.indexOf(firstRightLetters)].charAt(t)));
				analTable[m][n] = formula[i];
			}
		}
	}

	// 打印剩余符号串
	public static void printSurplus() {
		System.out.print(surplus.substring(surplusFlag, surplus.length()));
		System.out.println();
	}

	// 打印文法符号栈
	public static void printStack() {
		int a = 0;
		for (; a <= stackTop + 1; a++) {
			System.out.print(stack[a]);
		}
		System.out.print("\t\t");
	}

	// 产生式右端符号反序入栈
	public static void insertStack(GeneFormula formula) {
		String str = formula.getrightLetters();
		int temp;
		for (temp = str.length() - 1; temp >= 0; temp--) {
			stack[++stackTop] = (str.charAt(temp));
		}
	}

	// 字符串变形的函数
	public static String transformString(String str) {
		StringBuffer aimString = new StringBuffer();
		int i = 0;

		aimString.append(str.charAt(i++));
		for (; i < str.length(); i++) {
			aimString.append(',');
			aimString.append(str.charAt(i));
		}

		return aimString.toString();
	}

	// 字符串连接函数
	public static String linkString(String s1, String s2) {
		StringBuffer str1 = new StringBuffer(s1);
		StringBuffer str2 = new StringBuffer(s2);
		for (int o = str2.length() - 1; o > -1; o--) {
			char ch = str2.charAt(o);
			if (str1.toString().indexOf(ch) == -1) {
				str1.append(ch);
			}
		}
		return str1.toString();
	}

	// 显示FIRST集合的函数
	public static void displayFirstSet() {
		System.out.println();
		System.out.println("各个文法符号的FIRST集合显示如下..................");
		for (int i = 0; i <= 9; i++) {
			if (i <= 4) {
				System.out.println("\t\t" + "FIRST("
						+ GeneFormula.non_terminate.charAt(i) + ")=" + "{"
						+ transformString(first[i]) + "}");
			} else {
				System.out.println("\t\t" + "FIRST("
						+ GeneFormula.terminate.charAt(i - 5) + ")=" + "{"
						+ transformString(first[i]) + "}");
			}
		}
	}

	// 显示FOLLOW集合的函数
	public static void displayFollowSet() {
		System.out.println();
		System.out.println("各个文法符号的FOLLOW集合显示如下..................");
		for (int i = 0; i <= 4; i++) {
			System.out.println("\t\t" + "FOLLOW("
					+ GeneFormula.non_terminate.charAt(i) + ")=" + "{"
					+ transformString(follow[i]) + "}");
		}
	}

	// 显示LL(1)分析表的函数
	public static void displayAnalTable() {
		System.out.println();
		System.out.println("LL(1)分析表为..............................");
		System.out.println();
		System.out.println("\t " + 'i' + "\t " + '+' + "\t " + '*' + "\t " + '('
				+ "\t " + ')' + "\t " + '#');
		for (int i = 0; i <= 4; i++) {
			System.out.print(GeneFormula.non_terminate.charAt(i));
			System.out.print("\t");
			for (int j = 0; j <= 5; j++) {
				if (analTable[i][j] == null) {
					System.out.print("    ");
					System.out.print("\t");
				} else {
					analTable[i][j].LLDisplayGeneFormula();
					System.out.print("\t");
				}
			}
			System.out.println();
		}
	}

	// 主函数入口
	public static void main(String args[]) {
		// ************************************************
		// 显示非终结符号
		// 显示终结符号
		// 显示所有的产生式
		System.out.println();
		System.out.println("文法 G[E] 定义为:");
		System.out.println("\t\t" + "非终结符:" + "\t"
				+ transformString(GeneFormula.non_terminate));
		System.out.println("\t\t" + "终结符  :" + "\t"
				+ transformString(GeneFormula.terminate));
		System.out.println();
//		formula[0].preDisplayGeneFormula();
//		System.out.println();
//		formula[1].preDisplayGeneFormula();
//		System.out.println();
//		formula[2].preDisplayGeneFormula();
//		System.out.println();
//		formula[3].preDisplayGeneFormula();
//		System.out.println();
//		formula[4].preDisplayGeneFormula();
//		System.out.println();
//		formula[5].preDisplayGeneFormula();
//		System.out.println();
//		formula[6].preDisplayGeneFormula();
//		System.out.println();
//		formula[7].preDisplayGeneFormula();
//		System.out.println();
		
		for(int k = 0; k < formula.length; k++){
			formula[k].preDisplayGeneFormula();
			System.out.println();
		}
		
		// *****************************************************************************
		GeneFirstSet(); // 调用FIRST集合构造函数
		GeneFollowSet(); // 调用FOLLOW集合的构造函数
//		GeneFollowSet();
		GeneLLTable(); // 调用LL(1)分析表的构造函数
		displayFirstSet(); // 调用FIRST集合的显示函数
		displayFollowSet(); // 调用FOLLOW集合的显示函数
		displayAnalTable(); // 调用LL(1)分析表的显示函数
		// *****************************************************************************
		
		// ************************************************

		// 从键盘接受要分析的句子，并显示要输入句子的句型要求，必须以'#'为结束标志
		try {
			BufferedReader buf_reader = new BufferedReader(
					new InputStreamReader(System.in));
			System.out
					.println("提示:请输入以'i','+','*','(',')'构成的并以'#'结束的字符");
			System.out.println("请输入要分析的语句：.............." + "\r\n");
			System.out.print("\t\t：");

			StringBuffer str = new StringBuffer();
			char ch;
			do {
				ch = (char) buf_reader.read();
				if ((ch != 'i') && (ch != '+') && (ch != '*') && (ch != '(')
						&& (ch != ')') && (ch != '#')) {
					System.out.println("\t\t\r\n输入串中有非法字符\n");
					System.exit(1);
				}
				str.append(ch);
			} while (ch != '#');
			surplus = str.toString();
			System.out.println();
			System.out.println("你输入的语句为:" + "\t" + surplus + "      "
					+ "分析过程如下......");
			System.out.println();
		} catch (IOException e) {
		}

		System.out.println();
		stackTop = 0;
		currentChar = surplus.charAt(surplusFlag++); // 当前输入符号
		stack[stackTop] = '#';
		stack[++stackTop] = 'E'; // 先将'#' 'E'入栈
		System.out.println("序号\t文法符号栈\t所用产生式\t当前输入符号\t剩余输入字符串\t");

		do {
			currentStackTop = stack[stackTop--];
			System.out.print(s++ + "\t");

			if (GeneFormula.terminate.indexOf(currentStackTop) != -1) {
				// 如果当前栈顶为终结符号
				flag = 1;
			}

			if (flag == 1) {
				if (currentStackTop == '#') {
					// 如果当前栈顶和当前输入符号均为'#'，则分析成功
					success = 1;
					System.out.print("success!" + "\r\n");
					System.exit(1);
				}// if

				if (currentStackTop == currentChar) {
					// 如果当前栈顶和当前输入符号相同，则出栈，并载入下一个输入符号
					printStack();
					System.out.print("匹配 " + currentChar);
					System.out.print("\t\t");
					System.out.print(currentChar + "\t\t");
					printSurplus();
					currentChar = surplus.charAt(surplusFlag++);
					flag = 0;
				}// if

				else {
					// 出错
					printStack();
					System.out.print("出错" + currentChar);
					System.out.println();
					System.exit(1);
				}
			} else {
				// 如果是非终结符号
				tempFormula = analTable[GeneFormula.non_terminate
						.indexOf(currentStackTop)][GeneFormula.terminate
						.indexOf(currentChar)];
				if (tempFormula != null) {
					printStack();
					tempFormula.displayGeneFormula();
					System.out.print("\t");
					System.out.print(currentChar + "\t\t");
					printSurplus();
					insertStack(tempFormula); // 产生式反序入栈
					if (stack[stackTop] == '^')
						stackTop--;
				} else {
					printStack();
					System.out.print("出错" + currentStackTop);
					System.out.println();
					System.exit(1);
				}
			}
		} while (success == 0);
	}// main
}