ll1grammar.java

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

import java.io.*;

//产生式的类
class GeneFormula {
	int length; // 产生式的长度
	String leftLetter; // 产生式左端字符
	String rightLetters; // 产生式右端字符串

	static String grammarLetters = new String("EeTtFi+*()#"); // 所有文法符号
	static String terminate = new String("i+*()#"); // 终结符号
	static String non_terminate = new String("EeTtF"); // 非终结符
	static int i = 1; // 产生式序号

	// 构造函数
	GeneFormula() {
	}

	// 构造函数
	GeneFormula(int length, String leftLetter, String rightLetters) {
		this.length = length;
		this.leftLetter = leftLetter;
		this.rightLetters = rightLetters;
	}

	// 不同格式的产生式显示函数
	// 产生式显示函数
	public void displayGeneFormula() {
		System.out.print(leftLetter + "->" + rightLetters + "\t");
	}

	// 产生式显示函数
	public void LLDisplayGeneFormula() {
//		System.out.print(leftLetter + "->" + rightLetters);
		System.out.print("->" + rightLetters);
	}

	// 产生式显示函数
	public void preDisplayGeneFormula() {
		System.out.print("\t\t" + "  产生式 " + i + ":\t" + leftLetter + "->"
				+ rightLetters);
		i++;
	}

	// 返回产生式的长度，返回类型为int
	public int getLength() {
		return length;
	}

	// 返回产生式的左端字符，返回类型为char
	public char getLeftLetter() {
		return leftLetter.charAt(0);
	}

	// //返回产生式的右端字符，返回类型为string
	public String getrightLetters() {
		return rightLetters;
	}
}

public class LL1Grammar {
	static String first[] = new String[10]; // 定义first集合
	static String follow[] = new String[5]; // 定义follow集合

	static char[] stack = new char[30]; // 定义文法符号栈，类型为字符数组
	static String surplus; // 用于保存要分析的句子

	static int surplusFlag = 0; // 当前输入符号的位置
	static int stackTop = 0; // 文法符号栈的位置
	static int s = 1; // 分析步骤的序号
	static char currentStackTop; // 当前栈顶的符号
	static int flag = 0; // 标志是否为终结符
	static int success = 0; // 分析成功标志
	static char currentChar; // 当前输入符号
	static GeneFormula tempFormula = null; // 产生式临时变量

	// 构造产生式的数组
	static GeneFormula formula[] = { new GeneFormula(3, "E", "Te"),
			new GeneFormula(4, "e", "+Te"), new GeneFormula(1, "e", "^"),
			new GeneFormula(3, "T", "Ft"), new GeneFormula(4, "t", "*Ft"),
			new GeneFormula(1, "t", "^"), new GeneFormula(4, "F", "(E)"),
			new GeneFormula(2, "F", "i") };

	// 定义LL(1)分析表，类型为产生式的类型
	static GeneFormula analTable[][] = new GeneFormula[5][6];

	// FIRST集合的构造函数
	public static void GeneFirstSet() {
		first[0] = ""; // 赋初值
		first[1] = "";
		first[2] = "";
		first[3] = "";
		first[4] = "";
		first[5] = "";
		first[6] = "";
		first[7] = "";
		first[8] = "";
		first[9] = "";

		for (int i = 0; i < GeneFormula.grammarLetters.length() - 1; i++) {
			// 针对每一个文法符号tempchar进行分析
			char tempChar = GeneFormula.grammarLetters.charAt(i);
			if (GeneFormula.non_terminate.indexOf(tempChar) == -1) {
				// 如果tempchar为终结符号，直接赋值
				first[GeneFormula.grammarLetters.indexOf(tempChar)] = (new StringBuffer())
						.append(tempChar).toString();
				continue;
			} else {
				for (int j = 0; j < formula.length; j++) {
					// 对每一个产生式进行扫描，A->a.........的形式 ->右边为终结符
					if (GeneFormula.terminate.indexOf(formula[j]
							.getrightLetters().charAt(0)) != -1
							|| formula[j].getrightLetters().charAt(0) == '^') {
						if (formula[j].getLeftLetter() == tempChar) {
							first[GeneFormula.grammarLetters.indexOf(tempChar)] = ((new StringBuffer(
									first[GeneFormula.grammarLetters
											.indexOf(tempChar)]))
									.append(formula[j].getrightLetters()
											.charAt(0))).toString();
						}
					}
				}
			}
		}

		// 判断形式为X->ABCD...的形式
		for (int r = 0; r < 2; r++) {
			for (int m = 0; m < formula.length; m++) {
				if (GeneFormula.non_terminate.indexOf(formula[m]
						.getrightLetters().charAt(0)) != -1) {
					first[GeneFormula.grammarLetters.indexOf(formula[m]
							.getLeftLetter())] = linkString(
							first[GeneFormula.grammarLetters.indexOf(formula[m]
									.getLeftLetter())],
							first[GeneFormula.grammarLetters.indexOf(formula[m]
									.getrightLetters().charAt(0))]);
				}
			}
		}
	}

	// FOLLOW集合的构造函数
	public static void GeneFollowSet() {
		follow[0] = "#"; // 赋初值
		follow[1] = "";
		follow[2] = "";
		follow[3] = "";
		follow[4] = "";

		for (int heihei = 0; heihei < 10; heihei++) {
			// 外层循环两次，确保每个集合都不会再增长
			for (int i = 0; i < formula.length; i++) {
				// 对产生式依次判断分析
				String rightLetters = formula[i].getrightLetters();
				int rightLength = formula[i].getLength() - 1;
				if (rightLength == 1) {
					// A->B的情况
					if (GeneFormula.non_terminate.indexOf(rightLetters
							.charAt(0)) != -1) {
						follow[GeneFormula.non_terminate.indexOf(rightLetters
								.charAt(0))] = linkString(
								follow[GeneFormula.non_terminate
										.indexOf(rightLetters.charAt(0))],
								follow[GeneFormula.non_terminate
										.indexOf(formula[i].getLeftLetter())]);
					}
					continue;
				}

				// A->BCDEF的情况，暂时不考虑空符的情况
				for (int j = 0; j < rightLength; j++) {
					if (j < rightLength - 1
							&& GeneFormula.non_terminate.indexOf(rightLetters
									.charAt(j)) != -1) {
						StringBuffer str1 = new StringBuffer(
								follow[GeneFormula.non_terminate
										.indexOf(rightLetters.charAt(j))]);
						StringBuffer str2 = new StringBuffer(
								first[GeneFormula.grammarLetters
										.indexOf(rightLetters.charAt(j + 1))]);
						for (int o = 0; o < str2.length(); o++) {
							char ch = str2.charAt(o);
							if (str1.toString().indexOf(ch) == -1 && ch != '^') {
								str1.append(ch);
							}
						}
						follow[GeneFormula.non_terminate.indexOf(rightLetters
								.charAt(j))] = str1.toString();
					}
					if (j == rightLength
							&& GeneFormula.non_terminate.indexOf(rightLetters
									.charAt(j)) != -1) {
						follow[GeneFormula.non_terminate.indexOf(rightLetters
								.charAt(j))] = linkString(
								follow[GeneFormula.non_terminate
										.indexOf(rightLetters.charAt(j))],
								follow[GeneFormula.non_terminate
										.indexOf(formula[i].getLeftLetter())]);
					}
				}
			}

			// 判断空的情况
			for (int t = 0; t < formula.length; t++) {
				String rightLetters = formula[t].getrightLetters();
				int rightLength = formula[t].getLength() - 1;
				// char left = formula[t].getLeftLetter();
				int backPosition = rightLength - 1;

				for (int m = 0; m < rightLength; m++) {

					while (first[GeneFormula.grammarLetters
							.indexOf(rightLetters.charAt(backPosition))]
							.indexOf('^') != -1
							&& GeneFormula.non_terminate.indexOf(rightLetters
									.charAt(backPosition)) != -1) {
						backPosition--;
					}

					for (int g = backPosition; g < rightLength; g++) {
						if (GeneFormula.non_terminate.indexOf(rightLetters
								.charAt(g)) != -1) {
							follow[GeneFormula.non_terminate
									.indexOf(rightLetters.charAt(g))] = linkString(
									follow[GeneFormula.non_terminate
											.indexOf(rightLetters.charAt(g))],
									follow[GeneFormula.non_terminate
											.indexOf(formula[t].getLeftLetter())]);
						}
					}
				}
				continue;
			}
		}
	}

	// 利用FIRST和FOLLOW集合来构造LL(1)分析表
	public static void GeneLLTable() {
		// 按产生式的顺序逐一填表
		for (int i = 0; i < formula.length; i++) {
			char left = formula[i].getLeftLetter();
			String right = formula[i].getrightLetters();

			// 如果产生式右端有'^'
			if (right.charAt(0) == '^') {
				int m = GeneFormula.non_terminate.indexOf(left);
				int n;
				int j = follow[m].length();
				for (int t = 0; t < j; t++) {
					n = GeneFormula.terminate.indexOf(follow[m].charAt(t));
					analTable[m][n] = formula[i];
				}
				continue;
			}

			// 没有空符的情况