句型的分析算法分类 分析算法可分为: 自上而下分析法: 从文法的开始符号出发,反复使用文法的 产生式,寻找与输入符号串匹配的推导。 自下而上分析法: 从输入符号串开始,逐步进行归约,直至 归约到文法的开始符号
句型的分析算法分类 分析算法可分为： 自上而下分析法： 从文法的开始符号出发，反复使用文法的 产生式，寻找与输入符号串匹配的推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至 归约到文法的开始符号
句型分析的有关问题 1)在自上而下的分析方法中如何选择使用哪个产 生式进行推导? 假定要被代换的最左非终结符号是B,且有n条 规则:B→A1|A2|An,那么如何确定用哪个右 部去替代B? 2)在自下而上的分析方法中如何识别可归约的串? 在分析程序工作的每一步,都是从当前串中选择 个子串,将它归约到某个非终结符号,该子串 称为“可归约串
句型分析的有关问题 1）在自上而下的分析方法中如何选择使用哪个产 生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条 规则：B→A1|A2|…|An，那么如何确定用哪个右 部去替代B？ 2）在自下而上的分析方法中如何识别可归约的串？ 在分析程序工作的每一步，都是从当前串中选择 一个子串，将它归约到某个非终结符号，该子串 称为“可归约串
自下而上的分析方法 OPG LR分析器及其自动构造 自上而下 LL(1)分析器及其自动构造
自下而上的分析方法 OPG LR分析器及其自动构造 自上而下 LL(1)分析器及其自动构造
预测分析程序 Predictive parser无 回测的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L从左到右扫描输入串 第二个L生成的是最左推导 1向前看一个输入符号( lookahead) 预测分析程序的实现技术 1递归下降子程序 2表驱动分析程序
预测分析程序Predictive parser无 回溯的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序
表驱动予测分析程序模型 Input # 总控程序 stack 预测分析表
表驱动予测分析程序模型 Input # 总控程序 预测分析表 stack