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