更新于 2024-05-08 00:40:59

1.确定的自顶向下分析方法#

1.0 求字符$a$是否可以推导出空#

对于非空终结符$a\in V_T \wedge a \ne \varepsilon$​，不能推导出空。

接着扫描产生式$p: A \to \beta$：

1. 如果产生式右部$\beta$中有终结符，直接删除该产生式，如果此操作导致有一个非终结符$A$的所有产生式都被删除，则认为$A$不能推导出空。
2. 如果该产生式是一个空产生式即$\beta = \varepsilon$，则直接认为$A$能够推导出空，并且删除所有左部为$A$的产生式。

TIP

剩下来的产生式的右部都是由非终结符组成的非空产生式。

循环松弛:

• 接着扫描每一个产生式的右部的每一个非终结符$B$:
  1. 如果该非终结符已经被认为不能推导出空，则直接删除对应的产生式$A\to \alpha B\beta$。如果此操作导致有一个非终结符$A$的所有产生式都被删除，则认为$A$​不能推导出空。
  2. 如果该非终结符已经被认为能够推导出空，则直接删除对应产生式中该非终结符$B$。如果该操作导致对应产生式$A\to B$的右部全被删除完，则认为非终结符能够推导出空串。
  3. 如果该非终结符还没有被认定，就continue。
• 如果已经没有非终结符再继续能被认定，则退出松弛循环。

就能得到每一个符号$a\in (V_T \cup V_N)$是否可以推导出空。

TIP

对于一个串$\beta = A_1A_2A_3\cdots A_n,$ $A_i \in (V_T \cup V_N)$，能推导出空，$\beta\mathop{\Rightarrow}\limits^* \varepsilon$ ，当且仅当$A_i \mathop{\Rightarrow}\limits^* \varepsilon, \forall i(1\le i \le n)$ 。

1.1 $FIRST(\alpha)$ : 对串运算​#

$定义1.1.1$ 定义一个串$\alpha$的$First$运算:

$$\begin{align} FIRST(\alpha) &= \\ &\ \ \ \ \{b|\alpha\xRightarrow{*}b\beta, b\in V_T \wedge \beta \in (V_T \cup V_N)^*\} \\ & \cup (\{\varepsilon \}\ if \ \alpha \xRightarrow{*} \varepsilon \ otherwise \ \varnothing) \end{align}$$

当一个上下文无关文法没有空产生式$A \to \varepsilon$时，如果相同左部的产生式的右部的开头要么是不同的非终结符要么是不同的终结符。能保证每一个串$\alpha$使用不同产生式得到的串$\beta$的$FIRST(\beta)$不相交。

则只需要对着当前字符串的第一个待匹配字符，确定当前字符串对应不同产生式的$FIRST$​集合，就能确定使用哪一个产生式继续推导。这就是确定的自顶向下分析的第一种情况。

CAUTION

求$FIRST$集合注意最后一步的$\varepsilon$.

在有空产生式且产生式的右部第一个字符有非终结符的情况时，$FIRST$集合依旧可以被定义。实际情况中使用算法来求解字符串的$FIRST$集合。

1.1.1 循环松弛算法求每一个符号的$FIRST$[与课本上不太一致]#

前置步骤(可以减少之后循环产生式的数量 )

1. 对于终结符$a \in V_T$，$FIRST(a) = \{a\}$。
2. 对于非终结符$A \in V_N$，如果有产生式$A \to a\beta,a\in V_T, \beta \in (V_T \cup V_N)^*$，则$a \in FIRST(A)$​​。
3. 对于产生式$A\to \epsilon$，则直接丢掉。

接着把上述两种产生式[开头是终结符/空产生式]都可以丢掉，只剩下右部以非终结符开头的产生式，循环扫描所有剩下的产生式：

1. 对于非终结符$A\in V_N$，如果有产生式$A \to A_1A_2A_3\cdots A_n,$ $A_i \in (V_T \cup V_N)$，找到第一个不能推导出空的符号$A_i$，即第一个$i$使得$A_i \mathop{\nRightarrow}\limits^* \epsilon$，则$FIRST(A) \supseteq FIRST(A_i) \cup (\mathop{\cup}\limits_{j=1}^{i-1} (FIRST(A_j) - \{\epsilon\}))$
2. 查看每一个非终结符的$FIRST(A)$​有无变化，如果每一个都没有变化，则退出循环。
3. 最后一步，为所有能够导出空的非终结符符号的$FIRST$集合都添加上$\varepsilon$元素！

void ContextFreeGrammar::getFIRST_loop()
{
	vector<int> used(P.size(), 0);
	for (int i = 0; i < P.size(); i++)
	{
		int idx = P[i].first; string beta = P[i].second;
		if (beta.length() == 0) {
			used[i] = 1; continue;
		}
		if (ys_T.find(beta[0]) != ys_T.end())
		{
			FIRST[idx][ys_T[beta[0]]] = 1;
			used[i] = 1;
		}
	}
	bool flag = 1;
	while (flag)
	{
		flag = 0;
		for (int i = 0; i < P.size(); i++)
		{
			if (used[i])	continue;
			int idx = P[i].first; string beta = P[i].second;
			for (int j = 0; j < beta.size(); j++)
			{
				if (ifToEpsilon(beta[j]))
				{
					int idx2 = ys_N[beta[j]];
					vector<int> tmp = FIRST[idx];
					FIRST[idx] = merge(FIRST[idx], FIRST[idx2]);
					flag = isUpdated(FIRST[idx], tmp);
				}
				else
				{
					if (isTerminaled(beta[j]))
					{
						if (FIRST[idx][ys_T[beta[j]]] == 0)
						{
							flag = 1;
							FIRST[idx][ys_T[beta[j]]] = 1;
						}
					}
					else {
						int idx2 = ys_N[beta[j]];
						vector<int> tmp = FIRST[idx];
						FIRST[idx] = merge(FIRST[idx], FIRST[idx2]);
						flag = isUpdated(FIRST[idx], tmp);
					}
					break;
				}
			}
		}
	}
	for (int i = 0; i < toEpsilon.size(); i++)
	{
		if (toEpsilon[i] == 1)
		{
			FIRST[i][ys_T['\0']] = 1;
		}
	}
}

1.1.2 建图求每一个符号的$FIRST$集合#

设该上下文无关文法(Context Free Grammar)有$n$个非终结符($|V_N| = n$)，有$m$个终结符($|V_T| = m$)，建立一张$n+m$个节点的新图，每一个节点代表一个字符:

遍历每一条产生式$p$​给图加边:

1. 如果该产生式为$A \to A_1A_2A_3\cdots A_n$，$A_i \in (V_T \cup V_N)$，找到其中第一个$i$使得$A_i \mathop{\nRightarrow}\limits^* \varepsilon$，对每一个$1\le j\le i$，连接一条从字符$A$连向$A_j$​的有向边。
2. 对于空产生式$A\to \varepsilon$，跳过

在这张有向图$G$上，每一个字符的可达集合$S$就是该字符的$FIRST(A) - \{\varepsilon\}$集合。

最后，为能够推导出$\varepsilon$的非终结符的$FIRST$集合加入$\varepsilon$​

void ContextFreeGrammar::getFIRST_graph()
{
	int n = VN.size(),m = VT.size();
	vector<vector<int>> g(n+m);
	for (int i = 0; i < P.size(); i++)
	{
		int idx = P[i].first; string beta = P[i].second;
		if (beta.length() == 0)	continue;
		for (int j = 0; j < beta.size(); j++)
		{
			if (ys_T.find(beta[j]) != ys_T.end())
			{
				g[idx].push_back(ys_T[beta[j]] + n);
			}
			else
			{
				g[idx].push_back(ys_N[beta[j]]);
			}
			if (!ifToEpsilon(beta[j]))	break;
		}
	}

	for (int i = 0; i < n; i++)
	{
		vector<int> ans = bfs({ i }, g);
		for (int j = 0; j < ans.size(); j++)
		{
			int idx = ans[j];
			if (idx >= n)	FIRST[i][idx - n] = 1;
		}
		if(toEpsilon[i])	FIRST[i][ys_T['\0']] = 1;
	}
}

TIP

通过以上步骤可以得到每一个字符$a\in (V_T \cup V_N)$的$FIRST(a)$。

对于串$\beta \in (V_T \cup V_N)^*$，写为符号的拼接$\beta = A_1A_2A_3\cdots A_n,$ $A_i \in (V_T \cup V_N)$，找到第一个不能推导出空的符号$A_i$，即第一个$i$使得$A_i \mathop{\nRightarrow}\limits^* \varepsilon$，则$FIRST(\beta) = FIRST(A_i) \cup (\mathop{\cup}\limits_{j=1}^{i-1} (FIRST(A_j) - \{\epsilon\}))$​

1.2 $FOLLOW(A)$ : 对一个非终结符运算#

当一个上下文无关文法有空产生式$A \to \varepsilon$时，当当前推导有$A$时可以选择使用该产生式，把匹配字符的任务交给当前推导的下一个字符。

定义$1.2.1$ 定义对一个**非终结符$A$**的$FOLLOW$运算:

$$\begin{align} FOLLOW(A) &= \\ &\ \ \ \ \{b|S\xRightarrow{*}\alpha A \beta, b\in FIRST(\beta)\} \\ & \cup (\{\# \}\ if \ \beta \xRightarrow{*} \varepsilon \ otherwise \ \varnothing) \end{align}$$

$FOLLOW(A)$运算的结果是所有可能存在于A后的合法终结符$b$的集合，当且仅当有一个合法句型形如$\alpha A$(即存在$S\xRightarrow{*}\alpha A$时)，$\# \in FOLLOW(A)$，$\#$​​​​为句子结束符。

CAUTION

$\#$在FOLLOW中很重要。

FOLLOW集合中没有$\varepsilon$。

1.2.1 使用循环松弛法求非终结符$A$的$FOLLOW$集#

第一步，把$\#$加入到起始符号的$FOLLOW$集合中去。

接着循环松弛：

1. 遍历每一个产生式$p$:
   • 对于产生式$A \to A_1A_2A_3\cdots A_n$,$A_i \in (V_T \cup V_N)$。对于$1\le i \le n$:
     • 如果$A_i \in V_N$，则把$(FIRST(A_{i+1}A_{i+2}\cdots A_N) - \{\varepsilon\})$加入到$FOLLOW(A_i)$中。如果$A_{i+1}A_{i+2}\cdots A_n \xRightarrow{*} \varepsilon$，需要把$FOLLOW(A)加入到FOLLOW(A_i)$中！
2. 如果每一个非终结符$A$的$FOLLOW$集合都不再变化，则结束循环。

void ContextFreeGrammar::getFOLLOW_loop()
{
	FOLLOW[ys_N[S]][VT.size()] = 1;	// '#'
	bool flag = 1;
	while (flag)
	{
		flag = 0;
		for (int i = 0; i < P.size(); i++)
		{
			int idx = P[i].first; string beta = P[i].second;
			for (int j = 0; j < beta.length(); j++)
			{
				if (isNonTerminaled(beta[j]))
				{
					int idx2 = ys_N[beta[j]];
					// vector<int> tmp1 = FOLLOW[idx];
					vector<int> tmp2 = FOLLOW[idx2];
					vector<char> cs = getFIRST(beta.substr(j + 1));
					for (char c : cs)
					{
						if (c == '\0')	continue;			// epsilon不在FOLLOW中
						FOLLOW[idx2][ys_T[c]] = 1;
					}
					if (ifToEpsilon(beta.substr(j + 1)))
					{
						FOLLOW[idx2] = merge(FOLLOW[idx2], FOLLOW[idx]);
					}
					flag = flag || isUpdated(tmp2, FOLLOW[idx2]);
				}
			}
		}
	}
}

1.2.2 使用建图法求非终结符$A$的$FOLLOW$​集#

该算法把求SELECT的大部分事情也都做了。

设该上下文无关文法(Context Free Grammar)有$n$个非终结符($|V_N| = n$)，有$m$个终结符($|V_T| = m$)，建立一张$n+n+m+1$点的新图，分别代表非终结符$A \in V_T$的$FOLLOW$集合、非终结符$A\in V_T$的$FIRST(A) - \{\varepsilon\}$集合，简称$F'$集合，终结符$a \in V_N$，以及$\#$

首先，从初始符号$S$的$FOLLOW(S)$节点连一条边向$\#$节点。

遍历每一个产生式$p$:

1. 遇到空产生式，跳过
2. 对于产生式$A \to A_1A_2A_3\cdots A_n$,$A_i \in (V_T \cup V_N)$。对于$1\le i \le n$:
   • 对每一个$1\le i \le n$，如果$A_i \in V_N$，找到第一个$j > i$，使得$A_j \mathop{\nRightarrow}\limits^* \varepsilon$，接着从$A_i$连向所有的$F’(A_k)$,$i < k < j$。如果$A_j \in V_T$,就从$A_i$连一条边向$A_j$,否则从$A_i$连接一条边向$F'(A_j)$。如果子串$A_{i+1}A_{i+2}\cdots A_n \xRightarrow{*} \varepsilon$，注意空子串也可以导出空串。，就从$FOLLOW(A_i)$连接一条边向$FOLLOW(A)$。 [FOLLOW的事情]
   • 找到第一个$i$使得$A_i \mathop{\nRightarrow}\limits^* \varepsilon$，则从$F'(A)$连向每一个$F'(A_j),j<i$，如果$A_i \in V_T$,则从$F'(A)$连向$A_i$,否则从$F'(A)$连向$F'(A_i)$(FIRST的事情)

则每一个FOLLOW节点的可达$V_T \cup \{\#\}$集合就是该$FOLLOW$​集合。

void ContextFreeGrammar::getFOLLOW_graph1()
{
	int n = VN.size(), m = VT.size();
	vector<vector<int>> g(n + n + m + 1);
	g[ys_N[S]].push_back(2 * n + m);
	for (auto p : P)
	{
		int idx = p.first; string beta = p.second;
		if (beta.length() == 0)	continue;
		for (int i = 0; i < beta.length(); i++)			//FOLLOW 的连边
		{
			if (isNonTerminaled(beta[i]))
			{
				int idx2 = ys_N[beta[i]];
				bool flag = 1;
				for (int j = i + 1; j < beta.length(); j++)
				{
					if (beta[j] == '\0')	continue;
					if (isTerminaled(beta[j])) {
						g[idx2].push_back(ys_T[beta[j]] + 2 * n);
					}
					else if (isNonTerminaled(beta[j]))
					{
						g[idx2].push_back(ys_N[beta[j]] + n);
					}
					if (!ifToEpsilon(beta[j])) {
						flag = 0;
						break;
					}
				}
				if (flag)
				{
					g[idx2].push_back(idx);
				}
			}
		}
		for (int i = 0; i < beta.length(); i++)
		{
			if (isNonTerminaled(beta[i]))
			{
				g[idx + n].push_back(ys_N[beta[i]] + n);
			}
			else if (isTerminaled(beta[i]))
			{
				g[idx + n].push_back(ys_T[beta[i]] + 2 * n);
			}
			if (!ifToEpsilon(beta[i])) {
				break;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		vector<int> ans = bfs({ i }, g);
		for (int v : ans)
		{
			if (v >= 2 * n)
			{
				FOLLOW[i][v - 2 * n] = 1;
			}
		}
	}
}

1.3 $SELECT(A \to \beta)$: 对一个产生式的运算#

如果$\beta$可以推导出$\varepsilon$，那么$SELECT(A \to \beta) = (FIRST(\beta) - \{\varepsilon\}) \cup (FOLLOW(A))$

如过$\beta$推导不出$\varepsilon$，那么$SELECT(A \to \beta) = FIRST(\beta)$。

由此规则遍历所有的产生式就可以得到每一条产生式的$SELECT$集合。

void ContextFreeGrammar::getSELECT_loop()
{
	int m = VT.size();

	for (int i = 0; i < P.size(); i++)
	{
		int idx = P[i].first; string beta = P[i].second;
		vector<char> first = getFIRST(beta);
		for (char c : first)
		{
			if(c != '\0')
				SELECT[i][ys_T[c]] = 1;
		}
		if (ifToEpsilon(beta))
		{
			vector<char> follow = getFOLLOW(VN[idx]);
			for (char c : follow)
			{
				if (c == '#')
					SELECT[i][m] = 1;
				else SELECT[i][ys_T[c]] = 1;
			}

		}

	}
}

1.4 $LL(1)$​文法的判别#

判定一个文法是$LL(1)$文法的充要条件是，相同左部的任意两个产生式的$SELECT$集合没有交集。

按照左部扫描一次产生式集合，两两比较$SELECT$集合是否有交集。

1.5 LL(1)文法的实现#