G(E):E->iE+E E-EI E*EE/E(E) i*i+i E*i+i E*E+i E+i E+E E E E 米 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 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
语法分析的方法： 口自下而上分析法(Bottom-up) 口自上而下分析法(Top-down) ■基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找”匹配”的推导。 ■递归下降分析法：对每一语法变量（非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息反 馈和联合作用实现对输入串的识别。 ■预测分析程序 优点：直观、简单和宜于手工实现。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down) ◼基本思想：它从文法的开始符号出发，反复 使用各种产生式，寻找"匹配"的推导。 ◼递归下降分析法：对每一语法变量(非终结 符)构造一个相应的子程序，每个子程序识 别一定的语法单位，通过子程序间的信息反 馈和联合作用实现对输入串的识别。 ◼预测分析程序 优点：直观、简单和宜于手工实现
4.2自上而下分析面临的问题 自上而下就是从文法的开始符号出发，向 下推导，推出句子。 口带“回溯”的 口不带回溯的递归子程序（递归下降）分析方法。 ■ 自上而下分析的主旨：对任何输入串，试 图用一切可能的办法，从文法开始符号（根 结点)出发，自上而下地为输入串建立一棵 语法树。或者说，为输入串寻找一个最 左推导。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 4.2 自上而下分析面临的问题 ◼ 自上而下就是从文法的开始符号出发，向 下推导，推出句子。 带“回溯”的 不带回溯的递归子程序(递归下降)分析方法。 ◼ 自上而下分析的主旨：对任何输入串，试 图用一切可能的办法，从文法开始符号(根 结点)出发，自上而下地为输入串建立一棵 语法树。或者说，为输入串寻找一个最 左推导
例3.4.1假定有文法G(S): (1)S→xAy (2)A一→** 分析输入串x*y(记为a)。 ↑ 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 例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→Pa ◆含有左递归的文法将使自上而下的分 析陷入无限循环。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 当某个非终结符有多个产生式候选时，可 能带来如下问题: 1. 分析过程中，当一个非终结符用某一个候选 匹配成功时，这种匹配可能是暂时的。出错时， 不得不“回溯” 。 2. 文法左递归问题。一个文法是含有左递归的， 如果存在非终结符P PP + 含有左递归的文法将使自上而下的分 析陷入无限循环