自上而下的语法分析

自上而下 指从文法的开始符号开始，逐步向下构建出整棵语法树。这样的分析过程会遇到以下问题：

文法左递归：导致分析过程无限循环
回溯问题：在进入错误分支后，需要恢复进入分支前的现场，导致程序设计复杂

构造不会陷入死循环的、不需要回溯的语法分析算法

1. 消除左递归

文法可以消除左递归的条件

不含以为右部的产生式
不含回路，即不存在

1.1 直接左递归

该产生式表示 以一个beta开头，以若干个alpha结尾的串 。即。

需要设计出不含左递归的文法：左递归变右递归。

容易知道，这两种文法是等价的。

CAUTION 左递归的实质是语法树不断增长而输入串的匹配没有任何推进，左递归改为右递归后，虽然语法树还可能一直增长，但是输入串的匹配指针在一直前进。

推广更复杂产生式的直接左递归消除

含有左递归的文法

如此改为右递归：

1.2 间接左递归

若从开始推导，会出现，出现循环，为间接左递归。

为了消除这种依赖关系，进行如下操作：

这样出现了直接左递归，可用之前提到的方法进行消除，即：

由于文法的轮换对称性，对其他非终结符进行操作得到的文法是等价的。

1.3 消除左递归的通用算法

sort(G) # 把文法G的所有非终结符按照一种顺序排列 P_1, P_2, ..., P_N
for i in range(1, N + 1): # 把P_i的规则修改为 P_i -> a...|P_{i+1}...|P_{i+2}...|...
                          # 即只能包含P_i之后的非终结符

    for j in range(1, i):
        把形如 P_i -> P_j\gamma 的产生式中的P_j替换为它的定义式（消除P_j）
    消除关于P_i的直接左递归
simplify(G) # 化简文法G，删除无法到达的文法

由于在外层循环执行到时，均已经只包含之前的非终结符，所以该算法可以正确执行，消除的左递归。

2. 消除回溯

为了消除回溯，必须保证选派的候选项可以成功匹配输入串，这就要求我们合理构造集合和集合。

2.1 First集合

假设当前需要匹配的输入串的 token 为，那么文法的规则中只能有至多一个以开头，或者可以推导出以开头的串，由此定义候选项的集合：

特别地，若可以推导出，则。

在满足文法的规则中只能有至多一个以开头这一条件的情况下，若，则一定会选派去完成对的匹配。

但是并非所有的文法都满足上述条件，即，有时可以通过提取左公共因子的方式使其满足这一条件。

2.2 Follow集合

上述的集合没有考虑使用进行匹配的情况。

若可以被匹配，则一定可以紧跟在当前正在匹配的非终结符的后面出现，即存在一条规则，满足。由此定义非终结符的集合：

特别地，若可推导出，则。

2.3 LL(1)文法

文法不含左递归
文法中的每个非终结符的产生式的所有候选项的集合两两不相交
对于文法中的每个非终结符，若它的某个候选项的集合中存在，则所有候选项的集合不能和该非终结符的集合相交

上述第三条规则保证了不会出现可以同时匹配某个非空候选项和的情况。

LL(1)文法分析过程

若，则指派完成匹配
若不属于任何一个候选项的集合，则：

若某个候选项的集合中有，且，则用匹配。

否则，的出现为语法错误。

2.4 First集合的构造

对于每个，连续使用下面的规则，直到每个候选项的集合均不再发生变化：

若，则
若，且有产生式，则将加入中。特别地，若也是一条产生式，则也将加入中。
若是一条产生式，且，则将中所有非元素加入中。
若 $X\rightarrow Y1Y_2…Y{i-1}Yi…Y_k $是一个产生式，$ Y_1, Y_2, …, Y{i-1}\in VN $，且$ Y_1 $到$ Y{i-1} $的$ First $集合中均含有$ \epsilon $，则将$ First(Y_i) $中的非$ \epsilon $元素加入$ First(X) $。特别地，若$ Y_1 $到$ Y_k $的$ First $集合中均含有$ \epsilon $，则将$ \epsilon $加入$ First(X)$ 。

虽然一个产生式的前几个非终结符可能含有，但是这些的后面还可能会有别的串，所以在第步中，只有所有非终结符均含有时，才将加入。

构造任意符号串的First集合

对文法的任何符号串构造的算法如下：

置
若对于任意，均有，则置 \ 。特别地，若到的集合均含有，则置。

2.5 Follow 集合的构造

假设空串用 # 表示，对于文法的每个非终结符构造集合的办法是，连续使用下面的规则，直到所有非终结符的集合都不再发生变化：

对于文法的开始符号，将 # 加入
若是一个产生式，则将 \ 中的元素加入。
若是一个产生式，则将中的元素加入中。
若是一个产生式，且，则将中的元素加入中。

3 递归下降分析器

按照上述方法进行分析即可，程序实现较为简单。