214语法分析、自上而下分析 本章主要介绍语法分析的处理 要进行语法分析,必须对语言的语法结 构进行描述。 ●采用正规式和有限自动机可以描述和识别语 言的单词符号; 用上下文无关文法来描述语法规则
2.4 语法分析—自上而下分析 本章主要介绍语法分析的处理 要进行语法分析，必须对语言的语法结 构进行描述。 ⚫ 采用正规式和有限自动机可以描述和识别语 言的单词符号； ⚫ 用上下文无关文法来描述语法规则
2.4.1语法分析器的功能 语法分析的任务是分析一个文法的句子 结构 语法分析器的功能:按照文法的产生式 (语言的语法规则),识别输入符号串是 否为一个句子(合式程序)
2.4.1 语法分析器的功能 语法分析的任务是分析一个文法的句子 结构。 语法分析器的功能：按照文法的产生式 (语言的语法规则)，识别输入符号串是 否为一个句子(合式程序)
单词符号 语法分 源程序词法分 语法分析树编译程序 析器 取下一单词 析器 后续部分 符号表
源程序 单词符号 取下一单词 ... 语法分 词法分 析树 析器 语法分 析器 符号表 编译程序 后续部分
定义:假定G是一个文法,S是它的开始符号 如果s=则a称是一个句型。仅含终结 符号的句型是一个句子。文法G所产生的句子的 全体是一个语言,将它记为L(G)。 L(G)={c1S→c,c∈I}
* S ( ) { | , } * VT L G = S + ❑定义：假定G是一个文法，S 是它的开始符号。 如果 ，则称是一个句型。仅含终结 符号的句型是一个句子。文法G所产生的句子的 全体是一个语言，将它记为 L(G)
●语法分析的方法: 自下而土分析法( Bottom-up) 基本思想:从输入串开始,逐步进行“归约”, 直到文法的开始符号。即从树末端开始,构造语 法树。所谓归约,是指根据文法的产生式规则, 把产生式的右部替换成左部符号。 ●算符优先分析法:按照算符的优先关系和结合性质 进行语法分析。适合分析表达式。 LR分析法:一种更一般的自下而上分析法
语法分析的方法： ⚫ 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约” ， 直到文法的开始符号。即从树末端开始，构造语 法树。所谓归约，是指根据文法的产生式规则， 把产生式的右部替换成左部符号。 ⚫ 算符优先分析法：按照算符的优先关系和结合性质 进行语法分析。适合分析表达式。 ⚫ LR分析法：一种更一般的自下而上分析法
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 + 含有左递归的文法将使自上而下的分析陷入无限 循环