4 预测分析
预测分析是指，能够根据当前的输入符号，为相应的非终结符确定采用哪一个选择。（LL1文法支持这个要求）
接下来我们把 FIRST 和 FOLLOW 的信息集成到一个预测分析表 M[A, a] 中，A 是一个非终结符，a 是一个终结符或者 $。
构造预测分析表
构造分析预测表的思路，对于每个形如 A→\alpha 的产生式，考虑两方面：
- 对于 FIRST(\alpha) 中的所有非空终结符 a，都要使 A→\alpha 加入 M[A,a]；
- 如果 FIRST(\alpha) 中包含 \varepsilon，如果当前的输入符号（包含 \$）在 FOLLOW(A) 中，用 \alpha 展开 A 仍是合理的选择。在这种情况下，对于 FOLLOW(A) 中的每个终结符 b（包含 \$），都要使 A→\alpha 加入 M[A,b]。
对于文法 G 的所有产生式执行上述两条后，剩下的 M 条目都是空白（出错）。
一个文法的预测分析表没有多重定义条目 \Leftrightarrow 该文法是 LL(1) 的
文法 G 是左递归或者二义的 \Rightarrow M 至少含一个多重定义的条目
如何解决分析表中有多重定义的情况？
求助于文法变换：消除左递归和提取左因子，以期得到 LL(1) 文法。（不一定能够做到）
这说明使用预测分析的主要困难就是给源语言写出一个好的文法。
递归下降的预测分析
已在第一小节论述
非递归的预测分析
- 显式地维护一个栈，将递归转为非递归。
- 关键问题：扩展一个非终结符时怎么为其选择合适的产生式（选择）。
- 解决策略：查分析表。
非递归预测分析算法
条件：
- 一个栈：栈底为 \$，栈顶为开始符号 S
- 一个预测分析表 M：接受两个参数 A,a，前者表示栈顶符号，后者表示当前输入符号
工作过程：
设当前栈顶符号为 X，当前输入符号为 a。
- 如果 X 是终结符，且 X=a=\$，说明分析成功，停机。
- 如果 X 是终结符，且 X=a\neq\$，说明 X 成功匹配 a，弹出 X，并查看下一个输入符号。
- 如果 X 是终结符，但 X\neq a，说明出错。
- 如果 X 是非终结符，访问分析表 M，若 M[X,a] 是 X 的产生式，例如 X\rightarrow UVW，则弹出 X，将 UVW 倒序入栈（保证 U 在栈顶）。
- 如果 X 是非终结符，访问分析表 M，若 M[X,a] 是空白，说明出错。
算法执行示例位于书 P59，个人感觉挺好理解，就不贴了。
错误恢复
编译器的错误处理
词法错误，如标识符、关键字或算符的拼写错
语法错误，如算术表达式的括号不配对
语义错误，如算符作用于不相容的运算对象
逻辑错误，如无穷的递归调用；把 == 写成了 =
分析器对错误处理的基本目标
清楚而准确地报告错误的出现，并尽量少出现伪错误
迅速地从每个错误中恢复过来，以便诊断后面的错误
它不应该使正确程序的处理速度降低太多
非递归预测分析的错误场合
- 如果 X 是终结符，但 X\neq a
- 如果 X 是非终结符，访问分析表 M，但 M[X,a] 是空白
预测分析的错误恢复
采用紧急方式的错误恢复：发现错误时，抛弃输入记号直到其属于某个指定的同步记号集合为止。
同步词法单元通常是界限符号，比如 ; 和 \}，具体如何为一种文法的非终结符 A 选择同步记号集合有下面一些启发式方法：
- FOLLOW(A) 的所有终结符，比如 \textbf{if }expr\textbf{ then } stmt，非终结符 expr 的同步记号包含 \textbf{then} 和 ; 等。
- 高层构造的首终结符，比如 a=expr;\textbf{ if }...，可以把 \textbf{if} 这样的句首终结符作为 expr 的同步记号，以免发生遗漏分号的错误时把后面的 if 语句一大段全部丢弃的情况。
- FIRST(A) 的所有终结符，比如 a=expr;,\textbf{if }...，语句的开始符号（这里是 if）作为 stmt 语句的同步符号，以免多出一个逗号时把 if 语句忽略了。
- 如果出错时栈顶是存在有产生空串选择的非终结符，则可以使用其推出空串的产生式选择。
- 如果终结符在栈顶而不能匹配，弹出此终结符。
