编译原理：LL(1)语法分析器的实现（内含代码详细注释）

自顶向下语法分析器的设计与实现一、说明这是一个简单的自顶向下语法分析程序——LL(1) 语法分析程序。自顶向下分析也称面向目标的分析方法，也就是从文法的开始符出发，试图推导出与输入单词串相匹配的句子。预测分析法（LL(1)方法）的基本思想是：从文法开始符S 出发，从左到右扫描源程序，每次通过向前查看 1 个字符，选择合适的产生式，生成句子的最左推导。二、程序功能及运行截图功能...

文章共8,704字 · 阅读需要大约30分钟

一键AI生成摘要，助你高效阅读

问答

!angway

43962人浏览 · 2020-04-26 20:43:42

!angway · 2020-04-26 20:43:42 发布

自顶向下语法分析器的设计与实现

一、说明

这是一个简单的自顶向下语法分析程序——LL(1) 语法分析程序。自顶向下分析也称面向目标的分析方法，也就是从文法的开始符出发，试图推导出与输入单词串相匹配的句子。

预测分析法（LL(1)方法）的基本思想是：从文法开始符S 出发，从左到右扫描源程序，每次通过向前查看 1 个字符，选择合适的产生式，生成句子的最左推导。

该程序代码具有一定的通用性，可通过以下几个样例来看。

作者的另一个《编译原理》实验代码：PL/0语言词法分析程序地址：词法分析器的编程实现(含源码)

二、程序功能及运行截图

功能：

从文件读入文法自动区分终结符号VT 和非终结符号VN
消除直接左递归、~~间接左递归和提取左公因子（未实现）~~
自动生成FIRST和FOLLOW集合
自动判断是否是LL(1)文法
自动构建预测分析表
输入要分析的单词串自动输出分析过程

（可根据自己需求借鉴相关模块函数的实现）

环境：

Java语言编写，在eclipse或者其他Java编译器上编译执行

运行截图：

样例0：

文法（含直接左递归）：

E→T|E+T|E-T 
T→F|T*F|T/F 
F→(E)|i

输出：

输入单词串分析：i+i*i

样例①：

文法：

E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|i

输出：

样例②：

文法：

S→AaS|BbS|d
A→a
B→ε|c

输入单词串分析：aabd

输出：

分析单词串：aaaa

输出：

样例③（含直接左递归）：

文法：

S→a|^|(T)
T→T,S|S

输出：

样例④

E→TE'
E'→+E|ε
T→FT'
T'→T|ε
F→PF'
F'→*F'|ε
P→(E)|^|a|b

输出：

样例⑤

文法：

X→ABCd
A→a|ε
B→b|ε
C→c|ε

输出：

样例⑥：

非LL(1)文法：

S→AaS|a
A→a

输出：

三、算法逻辑和程序流程图

定义的主要变量或存储结构有：

	private static String START; // 开始符号
	private static HashSet<String> VN, VT; // 非终结符号集、终结符号集
	private static HashMap<String, ArrayList<ArrayList<String>>> MAP;// key:产生式左边 value:产生式右边(含多条)
	private static HashMap<String, String> oneLeftFirst;// "|" 分开的单条产生式对应的FIRST集合,用于构建预测分析表
	private static HashMap<String, HashSet<String>> FIRST, FOLLOW; // FIRST、FOLLOW集合
	private static String[][] FORM; // 存放预测分析表的数组，用于输出
	private static HashMap<String, String> preMap;// 存放预测分析表的map，用于快速查找

非终结符号VN、终结符号VT存于Set，集合元素不重复。
文法的每条产生式分割存于map中，键值对的数据结构，便于查找。其中产生式的左边为key，右边如果有多条就存于动态数组中，每个字符识别后同样存于动态数组中，所以value为ArrayList<ArrayList<String>>>，便于之后可能对单个字符的分析。
FIRST集合和FOLLOW集合同样以键值对Map的形式存放，其中FIRST中除了非终结符号VN的所有的FIRST集合外，oneLeftFirst在FIRST生成的同时，其也在同步构建，只不过表示方式不太一样，仅是为了便于构建预测分析表（第一行为Vt，第一列为Vn）的将Vn和与之对应的Vt（FIRST）组合起来为key，其value为当条产生式(“|”分割开的)，该产生式的FIRST里有的Vt，如此以来，加速了预测分析表的构建。
String[][] FROM仅是为了方便输出，行与列之间的对应关系依然存于Map中，在对具体的单词串分析的时候，不可能每次都遍历一个二维数组，效率太低，而HashMap查询效率高。

大体流程图：

UML图：

（1）消除直接左递归

（2）求FIRST集合

对每一文法符号X∈(VnUVt)*

①若X∈Vt ，则FIRST(X)={X}。

②若X∈Vn ，且有产生式X→a，a∈Vt，则a∈FIRST(X)。

③若X∈Vn ，X→ε，则ε∈FIRST(X)

④若X∈Vn，Y1，Y2，...，Yi ∈VN，

且有产生式X→Y1,...,Yn。

若对于1≤i≤k≤n，都有Yi∈ε, 则FIRST(Yk+1)-{ε}∈FIRST(X)

（3）求FOLLOW集合

①对文法开始符号 S ，将“ # ” ( 结束标记）置于 FOLLOW(S) 中。即 FOLLOW(S)= { # } 。 ( ∵有句型 #S#)

②若有A→aBb，则把FIRST(β)-{ε}加至FOLLOW(B)

③若有A→aB或A→aBb，而b∈ε即ε∈FIRST(b))；则把FOLLOW(A)加至FOLLOW(B)中。

（4）判断是否是LL(1)文法

①文法不包含左递归 ;

②对于文法中的每一个非终结符 A的各个产生式的侯选首字符集两两不相交。

③即：对于产生式A→a| b

若b ≠ ε, 则 FIRST( a ) ∩ FIRST( b )= Ф

若 b ＝ε , 则 FIRST(A) ∩FOLLOW(A)=Ф

如果文法 G 满足以上条件，则称该文法 G 为 LL(1) 文法

（5）构建预测分析表

①若a∈FIRST(α)，则把A→α放入M[A,a]中

②若ε∈FIRST(α)，则对每个终结符b∈ FOLLOW(A),将A→ε放入M[A,b]中

③对空项置出错标记（或用空表示出错）

（6）字符串分析过程

①置栈的初态为#S（#:输入串的开始标记，S:文法开始符号），读入符号放a中；

②弹出栈顶符号放入x中；

③若x∈VT :

若 a=x ：则把下一个输入符号读到 a 中，转②

若 a≠x ：出错。

④若x=‘#’且a=‘#’：则分析结束，否则出错。

⑤若x∈VN：则查预测分析表M[A,a]:

若 M[ A,a ] 为空，则出错；

若 M[ A,a ] 有一个产生式 x→x 1 … x n ，则将产生式右部符号串以反序进栈。

四、源代码

请结合流程图看代码，定义的方法无顺序关系，调用顺序流程请看main方法

package exp;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;

/**
 * 
 * @Description:[自动去直接左递归、自动生成FIRST、FOLLOW集合、自动构建预测分析表、输入单词串给出推导过程]
 * @author kailang
 * @date 2020-4-25
 * 
 */
public class Parser {
	public static final String PATH = "./grammar2";// 文法
	private static String START; // 开始符号
	private static HashSet<String> VN, VT; // 非终结符号集、终结符号集
	private static HashMap<String, ArrayList<ArrayList<String>>> MAP;// key:产生式左边 value:产生式右边(含多条)
	private static HashMap<String, String> oneLeftFirst;// "|" 分开的单条产生式对应的FIRST集合,用于构建预测分析表
	private static HashMap<String, HashSet<String>> FIRST, FOLLOW; // FIRST、FOLLOW集合
	private static String[][] FORM; // 存放预测分析表的数组，用于输出
	private static HashMap<String, String> preMap;// 存放预测分析表的map，用于快速查找

	public static void main(String[] args) {
		init(); // 初始化变量
		identifyVnVt(readFile(new File(PATH)));// 符号分类,并以key-value形式存于MAP中
		reformMap();// 消除左递归和提取左公因子
		findFirst(); // 求FIRST集合
		findFollow(); // 求FOLLOW集合
		// 断点测试
//		VN.toString();
//		VT.toString();
//		MAP.toString();
//		FOLLOW.toString();
//		FIRST.toString();
//		oneLeftFirst.toString();
		if (isLL1()) {
			preForm(); // 构建预测分析表
			// printAutoPre("aacbd"); // 示例推导
			System.out.println("请输入要分析的单词串:");
			Scanner in = new Scanner(System.in);
			printAutoPre(in.nextLine());
			in.close();
		}
	}

	// 变量初始化
	private static void init() {
		VN = new HashSet<>();
		VT = new HashSet<>();
		MAP = new HashMap<>();
		FIRST = new HashMap<>();
		FOLLOW = new HashMap<>();
		oneLeftFirst = new HashMap<>();
		preMap = new HashMap<>();
	}

	// 判断是否是LL(1)文法
	private static boolean isLL1() {
		System.out.println("\n正在判断是否是LL(1)文法....");
		boolean flag = true;// 标记是否是LL(1)文法
		Iterator<String> it = VN.iterator();
		while (it.hasNext()) {
			String key = it.next();
			ArrayList<ArrayList<String>> list = MAP.get(key);// 单条产生式
			if (list.size() > 1) // 如果单条产生式的左边包含两个式子以上，则进行判断
				for (int i = 0; i < list.size(); i++) {
					String aLeft = String.join("", list.get(i).toArray(new String[list.get(i).size()]));
					for (int j = i + 1; j < list.size(); j++) {
						String bLeft = String.join("", list.get(j).toArray(new String[list.get(j).size()]));
						if (aLeft.equals("ε") || bLeft.equals("ε")) { // (1)若b＝ε,则要FIRST(A)∩FOLLOW(A)=φ
							HashSet<String> retainSet = new HashSet<>();
							// retainSet=FIRST.get(key);//需要要深拷贝，否则修改retainSet时FIRST同样会被修改
							retainSet.addAll(FIRST.get(key));
							if (FOLLOW.get(key) != null)
								retainSet.retainAll(FOLLOW.get(key));
							if (!retainSet.isEmpty()) {
								flag = false;// 不是LL(1)文法，输出FIRST(a)FOLLOW(a)的交集
								System.out.println("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ") = {"
										+ String.join("、", retainSet.toArray(new String[retainSet.size()])) + "}");
								break;
							} else {
								System.out.println("\tFIRST(" + key + ") ∩ FOLLOW(" + key + ") = φ");
							}
						} else { // (2)b!＝ε若,则要FIRST(a)∩FIRST(b)= Ф
							HashSet<String> retainSet = new HashSet<>();
							retainSet.addAll(FIRST.get(key + "→" + aLeft));
							retainSet.retainAll(FIRST.get(key + "→" + bLeft));
							if (!retainSet.isEmpty()) {
								flag = false;// 不是LL(1)文法，输出FIRST(a)FIRST(b)的交集
								System.out.println("\tFIRST(" + aLeft + ") ∩ FIRST(" + bLeft + ") = {"
										+ String.join("、", retainSet.toArray(new String[retainSet.size()])) + "}");
								break;
							} else {
								System.out.println("\tFIRST(" + aLeft + ") ∩ FIRST(" + bLeft + ") = φ");
							}
						}
					}
				}
		}
		if (flag)
			System.out.println("\t是LL(1)文法,继续分析!");
		else
			System.out.println("\t不是LL(1)文法,退出分析!");
		return flag;
	}
	
	
	// 构建预测分析表FORM
	private static void preForm() {
		HashSet<String> set = new HashSet<>();
		set.addAll(VT);
		set.remove("ε");
		FORM = new String[VN.size() + 1][set.size() + 2];
		Iterator<String> itVn = VN.iterator();
		Iterator<String> itVt = set.iterator();

		// (1)初始化FORM,并根据oneLeftFirst(VN$VT,产生式)填表
		for (int i = 0; i < FORM.length; i++)
			for (int j = 0; j < FORM[0].length; j++) {
				if (i == 0 && j > 0) {// 第一行为Vt
					if (itVt.hasNext()) {
						FORM[i][j] = itVt.next();
					}
					if (j == FORM[0].length - 1)// 最后一列加入#
						FORM[i][j] = "#";
				}
				if (j == 0 && i > 0) {// 第一列为Vn
					if (itVn.hasNext())
						FORM[i][j] = itVn.next();
				}
				if (i > 0 && j > 0) {// 其他情况先根据oneLeftFirst填表
					String oneLeftKey = FORM[i][0] + "$" + FORM[0][j];// 作为key查找其First集合
					FORM[i][j] = oneLeftFirst.get(oneLeftKey);
				}
			}
		// (2)如果有推出了ε，则根据FOLLOW填表
		for (int i = 1; i < FORM.length; i++) {
			String oneLeftKey = FORM[i][0] + "$ε";
			if (oneLeftFirst.containsKey(oneLeftKey)) {
				HashSet<String> followCell = FOLLOW.get(FORM[i][0]);
				Iterator<String> it = followCell.iterator();
				while (it.hasNext()) {
					String vt = it.next();
					for (int j = 1; j < FORM.length; j++)
						for (int k = 1; k < FORM[0].length; k++) {
							if (FORM[j][0].equals(FORM[i][0]) && FORM[0][k].equals(vt))
								FORM[j][k] = oneLeftFirst.get(oneLeftKey);
						}
				}
			}
		}

		// 打印预测表,并存于Map的数据结构中用于快速查找
		System.out.println("\n该文法的预测分析表为：");
		for (int i = 0; i < FORM.length; i++) {
			for (int j = 0; j < FORM[0].length; j++) {
				if (FORM[i][j] == null)
					System.out.print(" " + "\t");
				else {
					System.out.print(FORM[i][j] + "\t");
					if (i > 0 && j > 0) {
						String[] tmp = FORM[i][j].split("→");
						preMap.put(FORM[i][0] + "" + FORM[0][j], tmp[1]);
					}
				}
			}
			System.out.println();
		}
		System.out.println();
	}


	// 输入的单词串分析推导过程
	public static void printAutoPre(String str) {
		System.out.println(str + "的分析过程:");
		Queue<String> queue = new LinkedList<>();// 句子拆分存于队列
		for (int i = 0; i < str.length(); i++) {
			String t = str.charAt(i) + "";
			if (i + 1 < str.length() && (str.charAt(i + 1) == '\'' || str.charAt(i + 1) == '’')) {
				t += str.charAt(i + 1);
				i++;
			}
			queue.offer(t);
		}
		queue.offer("#");// "#"结束
		// 分析栈
		Stack<String> stack = new Stack<>();
		stack.push("#");// "#"开始
		stack.push(START);// 初态为开始符号
		boolean isSuccess = false;
		int step = 1;
		while (!stack.isEmpty()) {
			String left = stack.peek();
			String right = queue.peek();
			// System.out.println(left+" "+right);
			// (1)分析成功
			if (left.equals(right) && right.equals("#")) {
				isSuccess = true;
				System.out.println((step++) + "\t#\t#\t" + "分析成功");
				break;
			}
			// (2)匹配栈顶和当前符号，均为终结符号，消去
			if (left.equals(right)) {
				String stackStr = String.join("", stack.toArray(new String[stack.size()]));
				String queueStr = String.join("", queue.toArray(new String[queue.size()]));
				System.out.println((step++) + "\t" + stackStr + "\t" + queueStr + "\t匹配成功" + left);
				stack.pop();
				queue.poll();
				continue;
			}
			// (3)从预测表中查询
			if (preMap.containsKey(left + right)) {
				String stackStr = String.join("", stack.toArray(new String[stack.size()]));
				String queueStr = String.join("", queue.toArray(new String[queue.size()]));
				System.out.println((step++) + "\t" + stackStr + "\t" + queueStr + "\t用" + left + "→"
						+ preMap.get(left + right) + "," + right + "逆序进栈");
				stack.pop();
				String tmp = preMap.get(left + right);
				for (int i = tmp.length() - 1; i >= 0; i--) {// 逆序进栈
					String t = "";
					if (tmp.charAt(i) == '\'' || tmp.charAt(i) == '’') {
						t = tmp.charAt(i-1)+""+tmp.charAt(i);
						i--;
					}else {
						t=tmp.charAt(i)+"";
					}
					if (!t.equals("ε"))
						stack.push(t);
				}
				continue;
			}
			break;// (4)其他情况失败并退出
		}
		if (!isSuccess)
			System.out.println((step++) + "\t#\t#\t" + "分析失败");
	}


	// 符号分类
	private static void identifyVnVt(ArrayList<String> list) {
		START = list.get(0).charAt(0) + "";// 存放开始符号

		for (int i = 0; i < list.size(); i++) {
			String oneline = list.get(i);
			String[] vnvt = oneline.split("→");// 用定义符号分割
			String left = vnvt[0].trim(); // 文法的左边
			VN.add(left);

			// 文法右边
			ArrayList<ArrayList<String>> mapValue = new ArrayList<>();
			ArrayList<String> right = new ArrayList<>();

			for (int j = 0; j < vnvt[1].length(); j++) { // 用 “|”分割右边
				if (vnvt[1].charAt(j) == '|') {
					VT.addAll(right);
					mapValue.add(right);
					// right.clear();// 清空之后，依然是同一个地址，需要重新new对象
					right = null;
					right = new ArrayList<>();
					continue;
				}
				// 如果产生式某字符的左边含有中文或英文的单引号，则视为同一个字符
				if (j + 1 < vnvt[1].length() && (vnvt[1].charAt(j + 1) == '\'' || vnvt[1].charAt(j + 1) == '’')) {
					right.add(vnvt[1].charAt(j) + "" + vnvt[1].charAt(j + 1));
					j++;
				} else {
					right.add(vnvt[1].charAt(j) + "");
				}
			}
			VT.addAll(right);
			mapValue.add(right);

			MAP.put(left, mapValue);
		}
		VT.removeAll(VN); // 从终结字符集中移除非终结符
		// 打印Vn、Vt
		System.out.println("\nVn集合:\t{" + String.join("、", VN.toArray(new String[VN.size()])) + "}");
		System.out.println("Vt集合:\t{" + String.join("、", VT.toArray(new String[VT.size()])) + "}");

	}

	// 求每个非终结符号的FIRST集合 和 分解单个产生式的FIRST集合
	private static void findFirst() {
		System.out.println("\nFIRST集合:");
		Iterator<String> it = VN.iterator();
		while (it.hasNext()) {
			HashSet<String> firstCell = new HashSet<>();// 存放单个非终结符号的FIRST
			String key = it.next();
			ArrayList<ArrayList<String>> list = MAP.get(key);
			// System.out.println(key+":");
			// 遍历单个产生式的左边
			for (int i = 0; i < list.size(); i++) {
				ArrayList<String> listCell = list.get(i);// listCell为“|”分割出来
				HashSet<String> firstCellOne = new HashSet<>();// 产生式左边用“ | ”分割的单个式子的First(弃用)
				String oneLeft = String.join("", listCell.toArray(new String[listCell.size()]));
				// System.out.println("oneLeft: "+oneLeft);
				if (VT.contains(listCell.get(0))) {
					firstCell.add(listCell.get(0));
					firstCellOne.add(listCell.get(0));
					oneLeftFirst.put(key + "$" + listCell.get(0), key + "→" + oneLeft);
				} else {
					boolean[] isVn = new boolean[listCell.size()];// 标记是否有定义为空,如果有则检查下一个字符
					isVn[0] = true;// 第一个为非终结符号
					int p = 0;
					while (isVn[p]) {
						// System.out.println(p+" "+listCell.size());
						if (VT.contains(listCell.get(p))) {
							firstCell.add(listCell.get(p));
							firstCellOne.add(listCell.get(p));
							oneLeftFirst.put(key + "$" + listCell.get(p), key + "→" + oneLeft);
							break;
						}
						String vnGo = listCell.get(p);//
						Stack<String> stack = new Stack<>();
						stack.push(vnGo);
						while (!stack.isEmpty()) {
							ArrayList<ArrayList<String>> listGo = MAP.get(stack.pop());
							for (int k = 0; k < listGo.size(); k++) {
								ArrayList<String> listGoCell = listGo.get(k);
								if (VT.contains(listGoCell.get(0))) { // 如果第一个字符是终结符号
									if (listGoCell.get(0).equals("ε")) {
										if (!key.equals(START)) { // 开始符号不能推出空
											firstCell.add(listGoCell.get(0));
											firstCellOne.add(listGoCell.get(0));
											oneLeftFirst.put(key + "$" + listGoCell.get(0), key + "→" + oneLeft);
										}
										if (p + 1 < isVn.length) {// 如果为空，可以查询下一个字符
											isVn[p + 1] = true;
										}
									} else { // 非空的终结符号加入对应的FIRST集合
										firstCell.add(listGoCell.get(0));
										firstCellOne.add(listGoCell.get(0));
										oneLeftFirst.put(key + "$" + listGoCell.get(0), key + "→" + oneLeft);
									}
								} else {// 不是终结符号，入栈
									stack.push(listGoCell.get(0));
								}
							}
						}
						p++;
						if (p > isVn.length - 1)
							break;
					}
				}
				FIRST.put(key + "→" + oneLeft, firstCellOne);
			}
			FIRST.put(key, firstCell);
			// 输出key的FIRST集合
			System.out.println(
					"\tFIRST(" + key + ")={" + String.join("、", firstCell.toArray(new String[firstCell.size()])) + "}");
		}
	}

	// 求每个非终结符号的FLLOW集合
	private static void findFollow() {
		System.out.println("\nFOLLOW集合:");
		Iterator<String> it = VN.iterator();
		HashMap<String, HashSet<String>> keyFollow = new HashMap<>();

		ArrayList<HashMap<String, String>> vn_VnList = new ArrayList<>();// 用于存放/A->...B 或者 A->...Bε的组合

		HashSet<String> vn_VnListLeft = new HashSet<>();// 存放vn_VnList的左边和右边
		HashSet<String> vn_VnListRight = new HashSet<>();
		// 开始符号加入#
		keyFollow.put(START, new HashSet<String>() {
			private static final long serialVersionUID = 1L;
			{
				add(new String("#"));
			}
		});

		while (it.hasNext()) {
			String key = it.next();
			ArrayList<ArrayList<String>> list = MAP.get(key);
			ArrayList<String> listCell;

			// 先把每个VN作为keyFollow的key，之后在查找添加其FOLLOW元素
			if (!keyFollow.containsKey(key)) {
				keyFollow.put(key, new HashSet<>());
			}
			keyFollow.toString();

			for (int i = 0; i < list.size(); i++) {
				listCell = list.get(i);

				// (1)直接找非总结符号后面跟着终结符号
				for (int j = 1; j < listCell.size(); j++) {
					HashSet<String> set = new HashSet<>();
					if (VT.contains(listCell.get(j))) {
						// System.out.println(listCell.get(j - 1) + ":" + listCell.get(j));
						set.add(listCell.get(j));
						if (keyFollow.containsKey(listCell.get(j - 1)))
							set.addAll(keyFollow.get(listCell.get(j - 1)));
						keyFollow.put(listCell.get(j - 1), set);
					}
				}
				// (2)找...VnVn...组合
				for (int j = 0; j < listCell.size() - 1; j++) {
					HashSet<String> set = new HashSet<>();
					if (VN.contains(listCell.get(j)) && VN.contains(listCell.get(j + 1))) {
						set.addAll(FIRST.get(listCell.get(j + 1)));
						set.remove("ε");

						if (keyFollow.containsKey(listCell.get(j)))
							set.addAll(keyFollow.get(listCell.get(j)));
						keyFollow.put(listCell.get(j), set);
					}
				}

				// (3)A->...B 或者 A->...Bε(可以有n个ε)的组合存起来
				for (int j = 0; j < listCell.size(); j++) {
					HashMap<String, String> vn_Vn;
					if (VN.contains(listCell.get(j)) && !listCell.get(j).equals(key)) {// 是VN且A不等于B
						boolean isAllNull = false;// 标记VN后是否为空
						if (j + 1 < listCell.size())// 即A->...Bε(可以有n个ε)
							for (int k = j + 1; k < listCell.size(); k++) {
								if ((FIRST.containsKey(listCell.get(k)) ? FIRST.get(listCell.get(k)).contains("ε")
										: false)) {// 如果其后面的都是VN且其FIRST中包含ε
									isAllNull = true;
								} else {
									isAllNull = false;
									break;
								}
							}
						// 如果是最后一个为VN,即A->...B
						if (j == listCell.size() - 1) {
							isAllNull = true;
						}
						if (isAllNull) {
							vn_VnListLeft.add(key);
							vn_VnListRight.add(listCell.get(j));

							// 往vn_VnList中添加，分存在和不存在两种情况
							boolean isHaveAdd = false;
							for (int x = 0; x < vn_VnList.size(); x++) {
								HashMap<String, String> vn_VnListCell = vn_VnList.get(x);
								if (!vn_VnListCell.containsKey(key)) {
									vn_VnListCell.put(key, listCell.get(j));
									vn_VnList.set(x, vn_VnListCell);
									isHaveAdd = true;
									break;
								} else {
									// 去重
									if (vn_VnListCell.get(key).equals(listCell.get(j))) {
										isHaveAdd = true;
										break;
									}
									continue;
								}
							}
							if (!isHaveAdd) {// 如果没有添加，表示是新的组合
								vn_Vn = new HashMap<>();
								vn_Vn.put(key, listCell.get(j));
								vn_VnList.add(vn_Vn);
							}
						}
					}
				}
			}
		}

		keyFollow.toString();

		// (4)vn_VnListLeft减去vn_VnListRight,剩下的就是入口产生式，
		vn_VnListLeft.removeAll(vn_VnListRight);
		Queue<String> keyQueue = new LinkedList<>();// 用栈或者队列都行
		Iterator<String> itVnVn = vn_VnListLeft.iterator();
		while (itVnVn.hasNext()) {
			keyQueue.add(itVnVn.next());
		}
		while (!keyQueue.isEmpty()) {
			String keyLeft = keyQueue.poll();
			for (int t = 0; t < vn_VnList.size(); t++) {
				HashMap<String, String> vn_VnListCell = vn_VnList.get(t);
				if (vn_VnListCell.containsKey(keyLeft)) {
					HashSet<String> set = new HashSet<>();
					// 原来的FOLLOW加上左边的FOLLOW
					if (keyFollow.containsKey(keyLeft))
						set.addAll(keyFollow.get(keyLeft));
					if (keyFollow.containsKey(vn_VnListCell.get(keyLeft)))
						set.addAll(keyFollow.get(vn_VnListCell.get(keyLeft)));
					keyFollow.put(vn_VnListCell.get(keyLeft), set);
					keyQueue.add(vn_VnListCell.get(keyLeft));

					// 移除已处理的组合
					vn_VnListCell.remove(keyLeft);
					vn_VnList.set(t, vn_VnListCell);
				}
			}
		}

		// 此时keyFollow为完整的FOLLOW集
		FOLLOW = keyFollow;
		// 打印FOLLOW集合
		Iterator<String> itF = keyFollow.keySet().iterator();
		while (itF.hasNext()) {
			String key = itF.next();
			HashSet<String> f = keyFollow.get(key);
			System.out.println("\tFOLLOW(" + key + ")={" + String.join("、", f.toArray(new String[f.size()])) + "}");
		}
	}

	// 消除直接左递归
	private static void reformMap() {
		boolean isReForm = false;// MAP是否被修改
		Set<String> keys = new HashSet<>();
		keys.addAll(MAP.keySet());
		Iterator<String> it = keys.iterator();
		ArrayList<String> nullSign = new ArrayList<>();
		nullSign.add("ε");
		while (it.hasNext()) {
			String left = it.next();
			boolean flag = false;// 是否有左递归
			ArrayList<ArrayList<String>> rightList = MAP.get(left);
			ArrayList<String> oldRightCell = new ArrayList<>(); // 旧产生的右边
			ArrayList<ArrayList<String>> newLeftNew = new ArrayList<>();// 存放新的左边和新的右边

			// 消除直接左递归
			for (int i = 0; i < rightList.size(); i++) {
				ArrayList<String> newRightCell = new ArrayList<>(); // 新产生式的右边
				if (rightList.get(i).get(0).equals(left)) {
					for (int j = 1; j < rightList.get(i).size(); j++) {
						newRightCell.add(rightList.get(i).get(j));
					}
					flag = true;
					newRightCell.add(left + "\'");
					newLeftNew.add(newRightCell);
				} else {
					for (int j = 0; j < rightList.get(i).size(); j++) {
						oldRightCell.add(rightList.get(i).get(j));
					}
					oldRightCell.add(left + "\'");
				}
			}
			if (flag) {// 如果有左递归，则更新MAP
				isReForm = true;
				newLeftNew.add(nullSign);
				MAP.put(left + "\'", newLeftNew);
				VN.add(left + "\'"); // 加入新的VN
				VT.add("ε"); // 加入ε到VT
				ArrayList<ArrayList<String>> newLeftOld = new ArrayList<>();// 存放原先，但是产生新的右边
				newLeftOld.add(oldRightCell);
				MAP.put(left, newLeftOld);
			}
			// 间接左递归
			// 提取左公因子
			// 待续...

		}
		// 如果文法被修改，则输出修改后的文法
		if (isReForm) {
			System.out.println("消除文法的左递归:");
			Set<String> kSet = new HashSet<>(MAP.keySet());
			Iterator<String> itk = kSet.iterator();
			while (itk.hasNext()) {
				String k = itk.next();
				ArrayList<ArrayList<String>> leftList = MAP.get(k);
				System.out.print("\t" + k + "→");
				for (int i = 0; i < leftList.size(); i++) {
					System.out.print(String.join("", leftList.get(i).toArray(new String[leftList.get(i).size()])));
					if (i + 1 < leftList.size())
						System.out.print("|");
				}
				System.out.println();
			}
		}
	}

	// 从文件读文法
	public static ArrayList<String> readFile(File file) {
		System.out.println("从文件读入的文法为:");
		ArrayList<String> result = new ArrayList<>();
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String s = null;
			while ((s = br.readLine()) != null) {
				System.out.println("\t" + s);
				result.add(s.trim());
			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return result;
	}
}

tips：产生式的定义符号请以“→”，如果有两个符号组成的字符只允许含英文或中文的单引号，空符号请用这个“ ε ”，分割符号请用“ | ”，请不要添加多余的空格！

如果出现文件读入乱码，请用记事本改成这样的编码格式，（如果保存为txt，代码里的文件名记得加上.txt）

五、总结

虽然代码有点长，但逻辑上还是比较直白的。

由于构建的预测表不尽完善，仅是按FIRST、FOLLOW填表，无出错处理，所以在对输入的单词输出分析过程的时候，有可能陷入死循环，但是如果单词串是由该文法推导出来的话，一般来说，应该大概也许可能没什么问题！

希望能给你帮助！不理解的地方可以私信我！能否及时回复随缘。

Github仓库地址

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/