1 自上而下分析

自上而下分析宗旨是为输入串寻找最左推导，也就是说在分析树上不断地试探、回溯，得到一个能够接收给定串的分析树。

这个分析方法导致的问题主要是回溯带来的代价不可预测，因为实际上每一步是贪心的，即使这一步成功了，很多步之后可能导致无路可走，被迫回到最开始的起点，对分析的复杂度造成挑战。

问题：能否避免回溯？

LL(1) 文法的意思是：【从左向右的扫描输入串】【产生最左推导】【每次查看下一个符号就可以做决策】

如果要避免回溯，应当做到的场景就是：面对一个非终结符，如果指派了某个选择，那么这个选择绝不是虚假的。也就是说，如果选这个选择不能完成匹配，当时选其他的选择肯定也不能完成匹配。

要避免回溯，前提条件就是要对文法消除左递归，已经介绍过。

分析一个递归下降的分析实例：

void A() {
    选择一个 A 产生式，A→X_1 X_2 …… X_k;
    for (i = 1 to k) {
        if (X_i是非终结符) X_i(); // 递归调用，名字由来
        else if (X_i == 输入符号a) 读入下一个输入符号;
        else error;
    }
}

现在要解决的是第一行，怎么选择确定的 A 产生式，A→X_1 X_2 …… X_k 使得分析确定地进行下去。

本文阅读量