Liping Zou bio photo

Liping Zou

An Android Developer

Email Twitter Instagram Github

Overview

在上一次词法分析的基础之上,我完成了我的C语言的语法分析器。这次选择的是用Java来实现,采用了自顶向下的分析方法,其思想是根据输入token串的最左推导,试图根据现在的输入字符来判断用哪个产生式来进行推导。

使用LL(1)分析法的问题就是对文法的要求较高,要求消除回溯了左递归,以致于后来在写文法的时候遇到各种麻烦,做了各种消除(本来想偷个懒,不通过程序直接手动解决这个问题的,结果还是耗费了不少体力)。

预测分析法的关键在于预测分析表的构造。这就要求求出每个变量的FIRST集和FOLLOW集,并且根据这来求出每个产生式的SELECT集。所以只要在顺利的理解了求解非终结符的FIRST集和FOLLOW集的算法之后,语法分析的实现其实已经胜利在望了。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	/**
	 * 初始化First集
	 * 
	 * @param expList
	 * @param mFirst
	 */
	public static List<String> initFirst(List<Grammar> expList,
			List<String> mFirst) {
		List<String> right = null;
		for (int i = 0; i < expList.size(); i++) { // 初始化FIRST集
			right = expList.get(i).getRightPart();
			if (right.size() > 0) {
				if (terminalSymbolMap.containsKey(right.get(0))) { // 若右部表达式的第一位为终结符则加入nts的FIRST集
					mFirst.add(right.get(0));
				}
			}
		}
		return mFirst;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
	 * 求非终结符的FIRST集
	 * 
	 * @param nts
	 *            非终结符
	 * @return FIRST集
	 */
	public static List<String> FIRST(NonTerminalSymbol nts) {
		List<Grammar> expList = getMyExp(nts.getValue());
		List<String> mFirst = new ArrayList<String>();
		List<String> right = null;

		mFirst = initFirst(expList, mFirst);// 初始化工作

		for (int i = 0; i < expList.size(); i++) {
			right = expList.get(i).getRightPart();
			if (right.size() > 0) {
				if (nonTerminalSymbolMap.containsKey(right.get(0))) {// 若右部表达式的第一位为非终结符则递归
					combineList(mFirst,
							FIRST(new NonTerminalSymbol(right.get(0))));

					int j = 0;
					while (j < right.size() - 1 && isEmptyExp(right.get(j))) { // 若X→Y1…Yn∈P,且Y1...Yi-1⇒*ε,
						combineList(mFirst,
								FIRST(new NonTerminalSymbol(right.get(j + 1))));
						j++;
					}
				}
			}
		}
		if (mFirst.contains("$"))
			mFirst.remove("$");
		combineList(nts.getFirst(), mFirst);
		return mFirst;
	}

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
	/**
	 * 求一个文法串的FIRST集
	 * 
	 * @param right
	 *            文法产生式的右部
	 * @return FIRST集
	 */
	public static List<String> getNTSStringFirst(List<String> right) {
		List<String> mFirst = new ArrayList<String>();

		if (right.size() > 0) { // 初始化,FIRST(α)= FIRST(X1);
			String curString = right.get(0);
			if (terminalSymbolMap.get(curString) != null)
				combineList(mFirst, terminalSymbolMap.get(right.get(0))
						.getFirst());
			else {
				combineList(mFirst, FIRST(new NonTerminalSymbol(curString)));
			}
		}

		if (right.size() > 0) {
			if (nonTerminalSymbolMap.get(right.get(0)) != null) { // 第一个符号为非终结符
				if (right.size() == 1) { // 直接将这个非终结符的first集加入right的first集
					combineList(mFirst, nonTerminalSymbolMap.get(right.get(0))
							.getFirst());
				} else if (right.size() > 1) {
					int j = 0;
					while (j < right.size() - 1 && isEmptyExp(right.get(j))) { // 若Xk→ε,FIRST(α)=FIRST(α)∪FIRST(Xk+1)
						String tString = right.get(j + 1);
						if (nonTerminalSymbolMap.get(tString) != null) {
							combineList(mFirst, FIRST(new NonTerminalSymbol(
									tString)));
						} else {
							combineList(mFirst, terminalSymbolMap.get(tString)
									.getFirst());
						}
						j++;
					}
				}
			}
		}
		return mFirst;
	}

	/**
	 * 求非终结符的FOLLOW集
	 * 
	 * @param nts
	 *            非终结符
	 * @return FOLLOW集
	 */
	public static void FOLLOW() {
		for (int i = 0; i < grammarList.size(); i++) {
			String left = grammarList.get(i).getLeftPart();
			List<String> right = grammarList.get(i).getRightPart();

			for (int j = 0; j < right.size(); j++) {
				String cur = right.get(j);

				if (terminalSymbolMap.containsKey(cur)) // 若是终结符则忽略
					continue;

				if (j < right.size() - 1) {
					List<String> nList = new ArrayList<String>();
					for (int m = j + 1; m < right.size(); m++)
						nList.add(right.get(m));
					List<String> mfirst = getNTSStringFirst(nList);
					for (String str : mfirst) {
						if (!nonTerminalSymbolMap.get(cur).getFollowList()
								.contains(str)) {
							combineList(nonTerminalSymbolMap.get(cur)
									.getFollowList(), mfirst);
							whetherChanged = true;
							break;
						}
					}

					boolean isNull = true; // 判断A→αBβ,且β⇒*ε,其中β能否为空
					for (int k = 0; k < nList.size(); k++) {
						if (!isEmptyExp(nList.get(k))) {
							isNull = false;
							break;
						}
					}
					if (isNull == true) {
						for (String str : nonTerminalSymbolMap.get(left)
								.getFollowList()) {
							if (!nonTerminalSymbolMap.get(cur).getFollowList()
									.contains(str)) {
								combineList(nonTerminalSymbolMap.get(cur)
										.getFollowList(), nonTerminalSymbolMap
										.get(left).getFollowList());
								whetherChanged = true;
								break;
							}
						}
					}
				} else if (j == right.size() - 1) { // 若该非终结符位于右部表达式最后一个字符
					List<String> mfollow = nonTerminalSymbolMap.get(left)
							.getFollowList();
					for (String str : mfollow) {
						if (!nonTerminalSymbolMap.get(cur).getFollowList()
								.contains(str)) {
							combineList(nonTerminalSymbolMap.get(cur)
									.getFollowList(), mfollow);
							whetherChanged = true;
							break;
						}
					}
				}
			}
		}
	}

上面的两张图很详细的表述了如何求解FIRST集和FOLLOW集的算法,我正是根据这两个算法将其实现的。在实现的过程中,我引入了一个缺陷,我的FIRST求解用到了递归求解,而这样可以正常运行的条件必须是使用的文法不存在左递归,不然就会产生StackOverFlow的错误。因此在对FOLLOW集求解的时候,为了避免文法存在右递归,不能再使用同求FIRST集类似的递归来求解了。我采用了每执行一遍求FOLLOW集的方法,将所有的非终结符的FOLLOW集都求解出来,如果其中有一个非终结符的FOLLOW集发生了改变,则再执行一遍该方法。根据FIRST集和FOLLOW集就可以很快捷的求出SELECT集,并构造出预测分析表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
	/**
	 * 求一个文法表达式的SELECT集
	 * 
	 * @param g
	 *            一个文法表达式
	 * @return SELECT集
	 */
	public static List<String> SELECT(Grammar g) {
		List<String> mselect = new ArrayList<String>();
		if (g.getRightPart().size() > 0) {
			if (g.getRightPart().get(0).equals("$")) { // 含有空表达式
				mselect = nonTerminalSymbolMap.get(g.getLeftPart())
						.getFollowList();
				return mselect;
			} else {
				mselect = getNTSStringFirst(g.getRightPart());
				boolean isNull = true;
				for (int i = 0; i < g.getRightPart().size(); i++) { // 如果右部可以推出空
					if (!isEmptyExp(g.getRightPart().get(i))) {
						isNull = false;
						break;
					}
				}
				if (isNull) {
					combineList(mselect,
							nonTerminalSymbolMap.get(g.getLeftPart())
									.getFollowList());
				}
				return mselect;
			}
		}
		return null;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
	 * 构造预测分析表
	 */
	public static void getAnalysisTable() {
		List<String> synString = new ArrayList<String>();
		synString.add(SYN);

		for (int i = 0; i < grammarList.size(); i++) {
			Grammar grammar = grammarList.get(i);
			if (analysisTable.get(grammar.getLeftPart()) != null) { // 如果多个文法表达式的左部相同,则将其合并
				for (String sel : grammar.getSelect()) {
					analysisTable.get(grammar.getLeftPart()).put(sel,
							grammar.getRightPart());
				}
			} else {
				HashMap<String, List<String>> inMap = new HashMap<String, List<String>>();
				for (String sel : grammar.getSelect())
					inMap.put(sel, grammar.getRightPart());
				analysisTable.put(grammar.getLeftPart(), inMap);
			}
			NonTerminalSymbol nts = nonTerminalSymbolMap.get(grammar
					.getLeftPart());
			List<String> msynList = nts.getSynList();
			for (int j = 0; j < msynList.size(); j++) {
				analysisTable.get(grammar.getLeftPart()).put(msynList.get(j), // 将同步记号集加入分析表中
						synString);
			}
		}
	}

下面简要的说一下我的数据结构。我对终结符、非终结符、文法产生式和单词封装到了实体类中。将符号的值与其FIRST集、FOLLOW集或SELECT集进行了关联。

image

程序中所有的终结符和非终结符分别保存在一个一维的哈希表中,其值作为HashMap的key,而其值所对应的对象作为HashMap的的value;所有经过程序处理的仅包含一个产生式右部的产生式保存在一个LIST中,LIST中装载着文法所对应的Grammar对象;预测分析表保存在一个二维的哈希表中,这个HashMap的key是某一个非终结符,value是其对应的一个一维HashMap,这个一维HashMap的key是终结符,value是某非终结符遇到某终结符时所对应的操作(一个产生式的右部或是同步记号)。

错误处理主要是依赖于同步记号集合,所以在语法分析中错误处理的关键就在于同步记号记号的构造。我的非终结符A的同步记号集合是将A的FIRST集、FOLLOW集、其高层结构的FIRST集组合而成的。在语法分析的时候,如果输入缓冲区中是终结符a,栈顶为非终结符,在预测分析表中对应的表项为空,则忽略终结符a;在预测分析表中对应的表项是synch(定义这样一个字符串来表示同步记号),则将当前栈顶的非终结符弹出,继续分析;如果栈顶的终结符和输入符合a不匹配,则将栈顶终结符弹出。

分析过程部分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
	/**
	 * LL(1)语法分析控制程序,输出分析树
	 * 
	 * @param sentence
	 *            分析的句子
	 */
	public static void myParser(List<String> sentence) {
		Stack<String> stack = new Stack<String>();
		int index = 0;
		String curCharacter = null;
		stack.push("#");
		stack.push("program");

		while (!stack.peek().equals("#")) {
			if (index < sentence.size()) // 注意下标,否则越界
				curCharacter = sentence.get(index);
			if (terminalSymbolMap.containsKey(stack.peek())
					|| stack.peek().equals("#")) {
				if (stack.peek().equals(curCharacter)) {
					if (!stack.peek().equals("#")) {
						stack.pop();
						index++;
					}
				} else {
					System.err.println("当前栈顶符号" + stack.pop() + "与"
							+ curCharacter + "不匹配");
				}
			} else {
				List<String> exp = analysisTable.get(stack.peek()).get(
						curCharacter);
				if (exp != null) {
					if (exp.get(0).equals(SYN)) {
						System.err.println("遇到SYNCH,从栈顶弹出非终结符" + stack.pop());
					} else {
						System.out.println(stack.peek() + "->"
								+ ListToString(exp));
						stack.pop();

						for (int j = exp.size() - 1; j > -1; j--) {
							if (!exp.get(j).equals("$")
									&& !exp.get(j).equals(SYN))
								stack.push(exp.get(j));
						}
					}
				} else {
					if (index < sentence.size()-1){
						System.err.println("忽略" + curCharacter);
						index++;
					}else {
						System.err.println("语法错误,缺少 '}' !");
						break;
					}
				}
			}
		}
	}