编译原理（4）：语法分析上——自顶向下分析

声明：本系列文章，是根据中国大学MOOC网哈工大的编译原理这门课学习而成的学习笔记。

一、自顶向下分析概述

最左推导(Left-most Derivation)

最右推导(Right-most Derivation)

编译原理（4）：语法分析上——自顶向下分析

自顶向下分析(Top-Down Parsing)

从分析树的顶部（根节点）向底部（叶节点）方向构造分析树可以看成是从文法开始符号S推导出词串w的过程
每一步推导中，都需要做两个选择
- 替换当前句型中的哪个非终结符
- 用该非终结符的哪个候选式进行替换

自顶向下的语法分析采用最左推导方式

总是选择每个句型的最左非终结符进行替换
根据输入流中的下一个终结符，选择最左非终结符的一个候选式

自顶向下语法分析的通用形式

递归下降分析 (Recursive-Descent Parsing)

由一组过程组成，每个过程对应一个非终结符
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析

预测分析 (Predictive Parsing)

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。
可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类
预测分析不需要回溯，是一种确定的自顶向下分析方法

二、文法转换

递归下降分析器存在的问题

编译原理（4）：语法分析上——自顶向下分析

解决办法

消除直接左递归

消除直接左递归的一般形式
消除间接左递归
消除左递归算法
提取左公因子

提取左公因子算法

三、LL（1）文法

S_文法（简单的确定性文法，Korenjak & Hopcroft，1966）

每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同
S_文法不含ε产生式

预测分析法的工作过程：从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

非终结符的后继符号集

编译原理（4）：语法分析上——自顶向下分析

产生式的可选集

编译原理（4）：语法分析上——自顶向下分析

串首终结符集

编译原理（4）：语法分析上——自顶向下分析

LL(1)文法

编译原理（4）：语法分析上——自顶向下分析

四、FIRST集和FOLLOW集的计算

计算文法符号X的FIRST(X )

编译原理（4）：语法分析上——自顶向下分析

由定义可知，FIRST(T)={ +,ε }, FIRST(T’)={ *, ε }, FIRST(F)={ (, ε }

FIRST(E) 取决于 FIRST(T)，而FIRST(T)取决于FIRST(F)

所以FIRST(E)=FIRST(F)=FIRST(F)

编译原理（4）：语法分析上——自顶向下分析

计算非终结符A的FOLLOW(A)

编译原理（4）：语法分析上——自顶向下分析

E是文法的开始符号，属于最右符号，将$加入其FOLLOW(E)中

根据①，跟着E后的符号可以直接跟在E’后面，故将FOLLOW(E)加入到FOLLOW(E’)中。同时根据②，E’可替换成 ε ，故直接跟在E后面的符号也有可能直接跟在T后面，所以将FOLLOW(E)加入到FOLLOW(T)中。

再根据①，E’紧跟在T后面，故将FIRST(E’)中的所有终结符，即+加入FOLLOW(T)中;

根据②推出的结果和①类似，没有更新

根据③，T’紧跟在F后面，故将FIRST(T’)中的所有终结符，即*加入到FOLLOW(T)中;同时T’可推到出ε，跟在T后的终结符可能也会直接跟再F后面，故将FOLLOW(T)加入到FOLLOW(F)中。

再根据③，跟在T后面的终结符可以直接跟在T’后面，故将FOLLOW(T)加入到FOLLOW(T’)中。

根据④推出的结果和③类似，没有更新

根据⑤，E后面直接跟有终结符号）。故直接将）加入到FOLLOW(E)中，同时根据上面的推理，发现FOLLOW集彼此之间存在相互依赖的关系，故每当一个FOLLOW集更新时，应再重新计算一遍，直到所有的FOLLOW集不再更新