编译原理：自上而下语法分析

自上而下分析遇到的问题

1. 左递归
2. 回溯

消除左递归

直接左递归

$$P \rightarrow P\alpha|\beta$$

$\beta$ 不以 $P$ 开头，推导后可得

P &\Rightarrow& P\alpha|\beta \\ &\Rightarrow& P\alpha\alpha\\ &\Rightarrow& P\alpha\alpha...\alpha\\ &\Rightarrow& \beta\alpha\alpha...\alpha

也就是会进入不断地递归，但是这个文法结束的时候一定是开头为 $\beta$ 的时候

void ParseP() {
	ParseP(); //开头仍为 P ，需要继续分析，陷入死循环
   	...
}

左递归转右递归

既然能够确定 $P$ 结束的时候一定是以 $\beta$ 开头，不如直接将文法转化为：

$$P \rightarrow \beta P'\\ P' \rightarrow \alpha P' | \varepsilon$$

于是递归就转换到了产生式右边的结尾。

在进行语法分析时，产生式将不断地将源程序读入与终结符 $\alpha$ 进行匹配，故在面对有限长度的程序输入时不会陷入死循环

void ParseP() {
	if (curToken == 'b') {
        nextToken(); // 匹配到了一个 b，所以可以读入下一个单词
        ParseP2();
    }
    ...
}
void ParseP2() {
    if (curToken == 'a') {
        nextToken();// 匹配到了一个 a，所以可以读入下一个单词
        ParseP2();
    }
    ...
}

左递归文法：

$$P \rightarrow P\alpha_1|P\alpha_2|...|P\alpha_m|\beta_1|\beta_2|...|\beta_n$$

转化为右递归：

P &\rightarrow& \beta_1P' | \beta_2P'|...|\beta_nP'\\ P' &\rightarrow& \alpha_1P' | \alpha_2P'|...|\alpha_mP'|\varepsilon

例题：

&& E \rightarrow E+T|T \\ 转化后：&& \\ &&E \rightarrow TE' \\ &&E' \rightarrow +TE'

间接左递归

直接看产生式没有左递归，但是在推导过程中产生了左递归

文法消除左递归的条件：

1. 不含以 $\varepsilon$ 为右部的产生式
2. 不含回路，，即不含 $P \xRightarrow{+} P$

消除思路：

1. 将文法 G 的所有非终结符按照任一种顺序排列 $P_i$
2. 把 $P_i$ 的规则改造成 $P_i \rightarrow a..|P_{i+1}...|P_{i+2}$… ，即产生式右部若以非终结符开头，一定要是按照第 1 步的顺序 $P_i$ 往后的非终结符，如果不是，则用其定义进行替换
3. 化简，删除无用的产生式

由于排序不同，得到的产生式可能不一样，但是是等价的

消除回溯

$$A \rightarrow B | C \\ B\rightarrow abd \\ C \rightarrow abcd$$

A 可能的两个候选都是非终结符开头，若选择用 B 去匹配，若源程序为 “abcd”，则匹配到 ‘c’ 的时候发现不符合 B 的文法规则，于是需要回溯到 ‘a’，再使用 C 进行匹配。

解决思路

$$A\rightarrow \alpha_1|\alpha_2|\alpha_3|...|\alpha_n$$

终结首符集 (FIRST 集合)：将来若干步推导后在开头出现的终结符集合

$$FIRST(\alpha_i) = \{\alpha_i|\alpha_i\xRightarrow{*} a..., a\in V_T\}$$

可能包含空字

FIRST($\alpha$) 也就是选择非终结符候选 $\alpha$ 后，经过若干步推导、可能存在于首部的非终结符的集合

要根据 FIRST($\alpha$) 确定选择哪个候选，前提条件是任意两个候选的 FIRST 集合都不相交。

提取公共左因子

引进非终结符和新的产生式

A \rightarrow \var\beta_1 | \var\beta_2|\var\beta_3...

可改写为

A \rightarrow \var A' \\ A' \rightarrow \beta_1|\beta_2|...|\beta_n

候选含有空字

$$A\rightarrow \alpha_1|\alpha_2|\alpha_3|...|\alpha_n|\varepsilon$$

若此时遇到了要匹配的字符 a，是否应该使用 A 的空字去匹配，应该取决于 A 之后是否有其他符号可以匹配 a，所以需要有 FOLLOW 集合（S 为开始符号）

$$FOLLOW(A) = \{a|S\xRightarrow{*}...Aa...,a\in V_T\}$$

就是在某个句型里，可能跟在 A 后面的终结符

若存在 $S\xRightarrow{*}...A$ 则规定 # $\in$ FOLLOW(A)‘

LL(1) 文法

含义

L: 从左到右

L: 最左推导

1: 根据当前单词分析

规则

1. 不含左递归

2. 所有产生式的所有候选的 FIRST 集合不相交

3. 对每个非终结符 A 如果候选的 FIRST 集合包含空字，则

   $$FIRST(\alpha_i)\cap FOLLOW(A) = \phi$$

   也就是当需要使用 $\varepsilon$ 的时候，一定是不得已而为之（候选 FIRST 集合内没有当前这个输入字符），且之后有其它推导可以匹配当前的这个字符，如果之后也没有，则报错。

分析

$$A\rightarrow \alpha_1|\alpha_2|\alpha_3|...|\alpha_n$$

1. 若 $a \in FIRST(\alpha_i)$，则指派 $\alpha_i$ 执行任务

2. 若 $a \notin FIRST(\alpha_i)$：

   1. $\varepsilon \in FIRST(\alpha_i)$ 且 $a \in FOLLOW(A)$，则让 A 与 $\varepsilon$ 匹配
   2. 否则出错

SELECT 集合

$$SELECT(A \rightarrow \alpha)=\left\{ \begin{array}{rcl} (FIRST(\alpha)-\{\varepsilon\})\cup FOLLOW(\alpha) & & {\alpha \xRightarrow {*} \varepsilon}\\ FIRST(\alpha) & & {\alpha \stackrel{*}{\nRightarrow} \varepsilon}\\ \end{array} \right.$$

代表的是当遇到某个字符 a 的时候，如果 $a \in SELECT(A\rightarrow \alpha)$ ，则应该使用 A 的候选 $\alpha$ 来匹配 a

FIRST 与 FOLLOW 的构造

$$FIRST(\alpha_i) = \{\alpha_i|\alpha_i\xRightarrow{*} a..., a\in V_T\}$$

对每一个 $X\in V_T\cup V_N$:

1. 若 X 本身就是终结符，则 FIRST(X) = {X}
2. 若 $X\rightarrow a...$，则 a 加入 FIRST(X) 中，若推出空字也加入
3. 若 $X\rightarrow Y...$ 是一个产生式，则 FIRST(Y) 的所有非空字（因为 Y 后可能还有其他符号）元素加入 FIRST(X)
4. 若 X 可以推出很长的符号串，且前 j 个符号都是非终结符，且都能推出 $\varepsilon$ ，则需要将第 j + 1个符号的 FIRST 集合加入 FIRST(X)
5. 如果 X 可以推出的符号串中的所有符号都可以推出 $\varepsilon$，则 $\varepsilon$ 应该加入 FIRST(X)

$$FOLLOW(A) = \{a|S\xRightarrow{*}...Aa...,a\in V_T\}$$

对每个非终结符 A

1. 对于文法的开始符号，将 # 加入 FOLLOW(S)
2. 若 $A \rightarrow \alpha B \beta$ 是一个产生式，则把 $FIRST(\beta) - \{\varepsilon\}$ 加入 FOLLOW(B)（$\beta$ 的第一个字符就是 B 的后继字符）
3. 若 $A \rightarrow \alpha B$ 是一个产生式，或 $A \rightarrow \alpha B \beta$ 是一个产生式而 $\beta \xRightarrow{*} \varepsilon$，则把 FOLLOW(A) 加入 FOLLOW(B) 中（B 在 A 产生式的最右边，所以跟在 A 后面的元素也可能跟在 B 后面）

总结：

1. 看有没有产生式是 一个非终结符跟在另一个非终结符后面的，有的话，就要考虑将后面的 FIRST 加入前面 FOLLOW
2. 看有没有位于产生式末尾的非终结符，或者位于产生式末尾的非终结符可能推出 $\varepsilon$ ，有的话，则考虑将左部的 FOLLOW 加入末尾的 FOLLOW

预测分析

• 总控程序
• 分析表：$M[A, a]$ 矩阵，$A\in V_n, a\in V_T \cup \{ \# \}$
• 分析栈：
  • 初始状态：#E
  • 读入新的符号 a，查表 M[E, a]，并将查询结果压入分析栈

构造预测分析表

1. 构造 FIRST 集合和 FOLLOW 集合
2. 构造分析表

$$A \rightarrow \alpha$$

应该放到分析表中的 A 行，放到 $FIRST(\alpha)$ 中所有元素的列中

$$A \rightarrow \varepsilon$$

应该放到分析表中的 A 行，放到 $FOLLOW(\alpha)$ 中所有元素的列中

所有没有定义的格子上放上出错标志

若文法满足 LL(1)，其上不会有多重定义入口（也就是表格内的一个单元格有两个值）

• 若含左递归 / 二义性则有多重定义入口