编泽原理 语法分折-自上而下分析 非终结符A有两个候选，试着用它的第一个候选去匹配 输入串，于是把语法树发展为 子树A的最左子结和IP所指的符号*相符，然后我们再 把IP调为指向下一符号并让A的第二个子结进入工作。 但A的第二子结*和当前所指的符号y不一致。因此，A 告失败。这意味着A的第一个候选此刻不适用于构造a 的语法树。这时应该回头（回溯），看A是否还有别 的候选。 第6页
编译原理 第6页 语法分析-自上而下分析 非终结符A有两个候选，试着用它的第一个候选去匹配 输入串，于是把语法树发展为 子树A的最左子结和IP所指的符号*相符，然后我们再 把IP调为指向下一符号并让A的第二个子结进入工作。 但A的第二子结*和当前所指的符号y不一致。因此，A 告失败。这意味着A的第一个候选此刻不适用于构造α 的语法树。这时应该回头（回溯），看A是否还有别 的候选。 S X A Y * *
编泽原理 语法分析-自上而下分析 为了这种回溯，我们一方面应把A的第一候选所发 展的子树注销掉，另一方面应把P恢复为进入A时 的原值，也就是让它重新指向第二个输入符号，。 现在我们试探A的第二个候选，即考虑如下的语法 树： 第7觉
编译原理 第7页 语法分析-自上而下分析 为了这种回溯，我们一方面应把A的第一候选所发 展的子树注销掉，另一方面应把IP恢复为进入A时 的原值，也就是让它重新指向第二个输入符号，。 现在我们试探A的第二个候选，即考虑如下的语法 树： X A Y S *
编泽原理 语法分折-自上而下分析 由于子树A只有一个子结，而且它和P所指的符号 相一致，于是，A完成了匹配任务。在A获得匹配 后，指示器P应指向下一个未被触及符号y。 在s的第二子结A完成匹配后，接着就轮到第三个 子结y进行工作。 由于这个子结和最后一个输入符号相符，于是，我 们完成了为a构造语法树的任务，证明了α是一个 句子。 第8列
编译原理 第8页 语法分析-自上而下分析 由于子树A只有一个子结，而且它和IP所指的符号 相一致，于是，A完成了匹配任务。在A获得匹配 后，指示器IP应指向下一个未被触及符号y。 在s的第二子结A完成匹配后，接着就轮到第三个 子结y进行工作。 由于这个子结和最后一个输入符号相符，于是，我 们完成了为α构造语法树的任务，证明了α是一个 句子
编译原理 语法分析-自上而下分析 自上而下分析法存在的困难 文法的左递归性问题P本Po 墨回溯 虚假匹配 难于知道输入串中出错的确切位置 墨效率很低，代价极高 第9页
编译原理 第9页 语法分析-自上而下分析 自上而下分析法存在的困难 文法的左递归性问题 P P α 回溯 虚假匹配 难于知道输入串中出错的确切位置 效率很低，代价极高
编泽原理 语法分折-自上而下分析 4.3LL(1)分析法 自上而下分析方法不允许文法含有任何左递归。 为构造不带回溯的自上而下分析算法，首先要消除 文法的左递归性，并找出克服回溯的充分必要条件。 消除左递归和克服回溯 第0
编译原理 第10页 语法分析-自上而下分析 4.3 LL（1）分析法 自上而下分析方法不允许文法含有任何左递归。 为构造不带回溯的自上而下分析算法，首先要消除 文法的左递归性，并找出克服回溯的充分必要条件。 消除左递归和克服回溯