G(E):E>il E+EIE-EI E*E IE/E I(E) Ei+i 三“E十i E+i E+E E E k E
G(E)： E → i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E E E E
●自上而下分析法(Top-down) 基本思想:它从文法的开始符号出发,反 复使用各种产生式,寻找匹配"的推导 递归下降分析法:对每一语法变量(非终结符) 构造一个相应的子程序,每个子程序识别一定的 语法单位,通过子程序间的信息反馈和联合作用 实现对输入串的识别 预测分析程序 优点:直观、简单和宜于手工实现
⚫ 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反 复使用各种产生式，寻找"匹配"的推导。 ⚫ 递归下降分析法：对每一语法变量(非终结符) 构造一个相应的子程序，每个子程序识别一定的 语法单位，通过子程序间的信息反馈和联合作用 实现对输入串的识别。 ⚫ 预测分析程序 优点：直观、简单和宜于手工实现
242自上而下分析面临的问 自上而下就是从文法的开始符号出发,向下 推导,推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法 ●自上而下分析的主旨:对任何输入串,试图 用一切可能的办法,从文法开始符号(根结 点)出发,自上而下地为输入串建立一棵语 法树。或者说,为输入串寻找一个最左推导
2.4.2 自上而下分析面临的问 题 自上而下就是从文法的开始符号出发，向下 推导，推出句子。 ⚫ 带“回溯”的 ⚫ 不带回溯的递归子程序(递归下降)分析方法。 自上而下分析的主旨：对任何输入串，试图 用一切可能的办法，从文法开始符号(根结 点)出发，自上而下地为输入串建立一棵语 法树。或者说，为输入串寻找一个最左推导
●例341假定有文法G(S) (1)s→xAy (2)A→** 分析输入串xy(记为)
例3.4.1 假定有文法G(S): (1) S→xAy (2) A→**|* 分析输入串x*y(记为)。 x*y S IP x*y S x A y x*y S IP x A y x*y S IP x A y * * x*y S IP x A y * * x*y S IP x A y * x*y S IP x A y *
●当某个非终结符有多个产生式候选时,可 能带来如下问题 1.回溯问题 分析过程中,当一个非终结符用某一个候选匹配成 功时,这种匹配可能是暂时的。出错时,不得不“回 溯 2.文法左递归问题 一个文法是含有左递归的,如果存在非终结符P P→PC ◆含有左递归的文法将使自上而下的分析陷入无限 循环
当某个非终结符有多个产生式候选时，可 能带来如下问题: 1. 回溯问题 分析过程中，当一个非终结符用某一个候选匹配成 功时，这种匹配可能是暂时的。出错时，不得不“回 溯” 。 2. 文法左递归问题。 一个文法是含有左递归的，如果存在非终结符P PP + 含有左递归的文法将使自上而下的分析陷入无限 循环