编译原理 第四章语法分析 自上而下分析
编译原理 第四章 语法分析—— 自上而下分析
编泽原理 语法分折析-自上而下分析 4.1语法分析器的功能 墨语法分析是编译过程的核心部分。它的任务是在词法分 析识别出单词符号串的基础上，分析并判定程序的语法 结构是否符合语法规则。 中间 中间 源程序 编译前端 代码优化 代码生成器 目标程序 代码 代码 符号表 彩2页
编译原理 第2页 语法分析-自上而下分析 4.1语法分析器的功能 语法分析是编译过程的核心部分。它的任务是在词法分 析识别出单词符号串的基础上，分析并判定程序的语法 结构是否符合语法规则。 源程序 编译前端 中间 代码 代码优化 中间 代码 代码生成器 目标程序 符 号 表
编泽原理 语法分析-自上而下分析 语法分析器的工作本质上就是按文法的产生式，识 别输入符号串是否为一个句子。并建立一棵与输入 串相匹配的语法分析树。 墨按照语法分析树的建立方法，可以把语法分析办法 分成两类：一类是自上而下分析法，另一类是自下 而上分析法 第3页
编译原理 第3页 语法分析-自上而下分析 语法分析器的工作本质上就是按文法的产生式，识 别输入符号串是否为一个句子。并建立一棵与输入 串相匹配的语法分析树。 按照语法分析树的建立方法，可以把语法分析办法 分成两类：一类是自上而下分析法，另一类是自下 而上分析法
编泽原理 语法分折-自上而下分析 4.2自上而下分析面临的问题 自上而下分析就是从文法的开始符号出发，向下推 导，推出句子。 自上而下分析的主旨是，对任何输入串，试图用一 切可能的办法，从文法开始符号（根结）出发，自 上而下地为输入串建立一棵语法树。或者说，为输 入串寻找一个最左推导。 这种分析过程本质上是一种试探过程，是反复使用 不同产生式谋求匹配输入串的过程。 第4负
编译原理 第4页 语法分析-自上而下分析 4.2自上而下分析面临的问题 自上而下分析就是从文法的开始符号出发，向下推 导，推出句子。 自上而下分析的主旨是，对任何输入串，试图用一 切可能的办法，从文法开始符号（根结）出发，自 上而下地为输入串建立一棵语法树。或者说，为输 入串寻找一个最左推导。 这种分析过程本质上是一种试探过程，是反复使用 不同产生式谋求匹配输入串的过程
编泽原理 语法分析-自上而下分析 雪例4.1假定有文法 (1)S→XAy (2)A→** (4.1) 以及输入串xy(记为a)。 为了自上而下构造α的语法树，我们首先按文法的开始符号产生根结$， 并让指示器P指向输入串的第一个符号x。然后，用$的规则（此处 关于$的规则仅有一条)把这棵树发展为 第5页
编译原理 第5页 语法分析-自上而下分析 例4.1假定有文法 （1）S→xAy (2）A→**|* （4 ．1） 以及输入串x*y(记为α）。 为了自上而下构造α的语法树，我们首先按文法的开始符号产生根结s， 并让指示器IP指向输入串的第一个符号x。然后，用S的规则（此处 关于S的规则仅有一条）把这棵树发展为 S X A Y
编泽原理 语法分折-自上而下分析 非终结符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）分析法 自上而下分析方法不允许文法含有任何左递归。 为构造不带回溯的自上而下分析算法，首先要消除 文法的左递归性，并找出克服回溯的充分必要条件。 消除左递归和克服回溯