自顶向下语法分析

自顶向下分析

从文法开始符号开始推导，每步获得文法的一个句型，直到产生期望的句子。

一般的自顶向下分析存在两类非确定性：

• 每步推导中选择哪个非终结符展开
• 展开某个非终结符时选择哪个产生式

第一种非确定性可以通过选规定最左或最右推导解决。为了消除第二类非确定性，一般采取向前查看确定数量的单词来确定选择哪个产生式。比如，对于

$$\begin{array}{rl}S& \to AB\\ A& \to aA|\delta \\ B& \to b|bB\end{array}$$

显然只需向前查看至多两个单词就可以确定选用哪个产生式。

但有些文法无论向前查看多少个单词都无法确定选择哪个产生式，如

$$\begin{array}{r}S\to Sa|b\end{array}$$

LL(1) 分析

LL(1) 的含义：

• 第一个 L：从左向右扫描单词
• 第二个 L：最左推导
• 1：向前查看一个单词

LL(1) 分析的前提是文法是 LL(1) 的。

First 集合

First 集合

对 $\alpha \in (V_T\cup V_N{)}^{\ast }$，$First(\alpha )=\{a|\alpha {\Rightarrow }^{\ast }a\beta ,a\in V_T,\beta \in (V_T\cup V_N{)}^{\ast }或\alpha {\Rightarrow }^{\ast }ϵ,a=ϵ\}$ 直观上讲，如果一个句型 $\alpha$ 可以推导出 $a$ 开头的句型，则 $a\in First(\alpha )$

• 一般只考虑 $V_N\cup V_T\cup \{ϵ\}\cup \{v|A\to u\in P,v为u后缀\}$

First 集合的计算：

1. 对 $x\in V_T\cup \{ϵ\},First(x)=\{x\}$
2. 重复以下步骤直到所有 First 集合不变
   1. 对于 $y_1{y}_2\dots y_k\in \{v|A\to u\in P,v为u后缀\}$，若 $First(y_1),\dots ,First(y_k)$ 均包含 $ϵ$，则 $First(y_1\dots y_k)=First(y_1)\cup \cdots \cup First(y_k)$，否则设 $y_i$ 为第一个不包含 $ϵ$ 的集合，$First(y_1\dots y_k)=First(y_1)\cup \cdots \cup First(y_i)-\{ϵ\}$
   2. 若有 $A\to y_1{y}_2\dots y_k\in P$，则 $First(A)=First(A)\cup First(y_1\dots y_k)$

Follow 集合

Follow 集合

对 $A\in V_N$,，$Follow(A)=\{a|S\#{\Rightarrow }^{\ast }\alpha A\beta \#且a\in First(\beta \#),\alpha ,\beta \in (V_N\cup V_T{)}^{\ast }\}$ 直观上讲，若 $G$ 中包含一个 $\dots Xa\dots$ 形式的句型，则 $a\in Follow(X)$，若存在一个以 $X$ 结尾的句型，则 $\#\in Follow(X)$

Follow 集合的计算：

1. $Follow(S)=\{\#\}$
2. 重复以下步骤直到所有 Follow 集合不变：
   1. 对于 $A\to \alpha B\beta \in P,\alpha ,\beta \in (V_N\cup V_T{)}^{\ast }$，$Follow(B)=Follow(B)\cup (First(\beta )-\{ϵ\})$
   2. 若 $ϵ\in First(\beta )$，$Follow(B)=Follow(B)\cup Follow(A)$

• $ϵ$ 总是不出现在 Follow 集合中
• 手动计算 First 集合（Follow 集合）时，可以重复扫描每一个非终结符来实现，对于每个非终结符，找它出现在左侧（右侧）的产生式并更新，直到没有更新为止

LL(1) 文法

预测集合

对任何 $A\to \alpha \in P$，定义预测集合 $PS(A\to \alpha )$：

• 若 $ϵ\notin First(\alpha )$，则 $PS(A\to \alpha )=First(\alpha )$
• 若 $ϵ\in First(\alpha )$，则 $PS(A\to \alpha )=(First(\alpha )-\{ϵ\})\cup Follow(A)$

直观上讲，预测集合中的单词代表如果选用这条产生式可能得到的第一个单词

LL(1) 文法

定义文法 $G$ 是 LL(1) 的当且仅当对于任意 $A\to \alpha ,A\to \beta \in P$，有 $PS(A\to \alpha )\cap PS(A\to \beta )=\varnothing$ 直观上讲，表示仅向前查看一个单词就可以确定选用哪条产生式

LL(1) 分析的实现

递归下降

每个非终结符对应一个子程序，对于一个产生式右部，如果遇到终结符则判断当前单词是否匹配，若不匹配则报错，如果遇到非终结符则继续调用它的子程序。一般结构如下：

void ParseA() {
	switch (lookahead) {
		case PS(A_to_u1):
			...
			break;
		case PS(A_to_u2):
			...
			break;
		...
		default:
			printf("Syntax error!\n")
			exit(0);
	}
}

这种方法比较直观，缺点也显而易见，效率较低。

表驱动

预先构建一个预测分析表：

• 每行对应一个非终结符
• 每列对应一个终结符或结束符号#
• 每项对应一个产生式集合，若 $P(A\to \alpha )$ 中包含 $a\in V_T\cup \{ϵ\}$，则将 $A\to \alpha$ 加入 $[A,a]$ 预测分析表的每个表项只含一个产生式当且仅当 $G$ 为 LL(1) 文法。

表驱动的 LL(1) 分析过程如下：

1. 初始时将 $\#,S$ 依次入栈
2. 重复以下步骤：
   1. 若栈顶为终结符，判断当前读入字符是否匹配，若不匹配则报错，否则弹出
   2. 若栈顶为非终结符，根据预测分析表选择栈顶符号和当前读入字符对应的产生式，若不存在该表项则报错，否则弹出该非终结符，将产生式右部从右向左入栈

文法变换

消除左递归

消除直接左递归：

对于

$$\begin{array}{r}P\to P{\alpha }_1|P{\alpha }_2|\dots |P{\alpha }_k|{\beta }_1|\dots |{\beta }_m\end{array}$$

可将其替换为

$$\begin{array}{rl}P& \to {\beta }_{1}Q|{\beta }_{2}Q|\dots |{\beta }_{m}Q\\ Q& \to {\alpha }_{1}Q|{\alpha }_{2}Q|\dots |{\alpha }_{k}Q|ϵ\end{array}$$

• 不要漏了 $Q\to ϵ$

对于存在间接左递归的情况，先将所有非终结符排列为 $A_1,A_2,\dots ,A_n$，然后遍历：

1. 对于 $A_i\to A_{j}r$，用 $A_i\to {\alpha }_{1}r|\dots |{\alpha }_{k}r$ 替代，其中 $A_j\to {\alpha }_1|\dots |{\alpha }_k$ 是其全部产生式，$j=1,\dots ,i-1$。
2. 消除 $A_i$ 的直接左递归

消除左公因子

对于

$$P\to \alpha {\beta }_1|\alpha {\beta }_2|\dots |\alpha {\beta }_k|{\gamma }_1|\dots |{\gamma }_m$$

可将其替换为

$$\begin{array}{rl}P& \to \alpha Q|{\gamma }_1|\dots |{\gamma }_m\\ Q& \to {\beta }_1|\dots |{\beta }_k\end{array}$$

• 不含左递归和左公因子的文法不一定是 LL(1) 文法

LL(1) 分析中的错误处理

同步符号

跳过输入串中的一些符号直到遇到同步符号为止。

同步符号的选择：

• 把 Follow(A) 中的所有符号作为 A 的同步符号
• 把 First(A) 中的所有符号作为 A 的同步符号

LL(K) 文法

• 给定 $k>0$，一个 CFG 是否为 $LL(k)$ 文法是可判定的
• 对于一个 CFG，是否存在 $k>0$，使得该文法是 $LL(k)$ 文法是不可判定的
• 对于一个 CFG，是否存在一个阈值等价的 $LL(k)$ 文法是不可判定的
• 两个 $LL(k)$ 的语言是否相等是可判定的
• $LL(k)$ 文法是无二义的
• $LL(k)$ 文法中不存在左递归的非终结符
• 给定 $k>0$，不含 $ϵ$ 产生式的 $LL(k)$ 文法的语言类真包含于不含 $ϵ$ 产生式的 $LL(k+1)$ 文法的语言类