语法分析——自底向上分析技术

1、5.1 引言引言5.2 算符优先分析技术算符优先分析技术5.3 LR(k)分析技术分析技术本章小结本章小结5.1 引言引言 5.1.1 自底向上分析技术及识别算法自底向上分析技术及识别算法 5.1.2 讨论的前提讨论的前提 5.1.3 基本实现方法基本实现方法5.1 引言引言5.1.1 自底向上分析技术及识别算法自底向上分析技术及识别算法 基本思想基本思想是是: 从输入符号串出发，在每一分析步对相从输入符号串出发，在每一分析步对相应句型中的某个简单短语进行归约。如果最终能归约到识应句型中的某个简单短语进行归约。如果最终能归约到识别符号，则该输入符号串是相应文法的句子，否则就不是。别符号，则该输

2、入符号串是相应文法的句子，否则就不是。 当句型分析过程中每个分析步都对最左的简单短语进当句型分析过程中每个分析步都对最左的简单短语进行直接归约时，自底向上分析技术的两个基本问题可以更行直接归约时，自底向上分析技术的两个基本问题可以更确切地叙述为：确切地叙述为：如何找出句柄如何找出句柄及及把此句柄直接归约为哪个把此句柄直接归约为哪个非终结符号非终结符号。5.1 引言引言5.1.1 自底向上分析技术及识别算法自底向上分析技术及识别算法5.1.2 讨论的前提讨论的前提 识别过程是从左到右、自底向上地进行的，一般识别过程是从左到右、自底向上地进行的，一般都将采用规范归约；除了特别指明的以外，每一步都将

3、采用规范归约；除了特别指明的以外，每一步总是对句柄总是对句柄最左的简单短语进行直接归约最左的简单短语进行直接归约。5.1.3 基本实现方法基本实现方法 采用自底向上分析技术时，通常以移入采用自底向上分析技术时，通常以移入- -归约归约法为基础。一般地，动作共有法为基础。一般地，动作共有4 4类，即移入、归约、类，即移入、归约、接受与报错。接受与报错。v移入：移入：读入下一个输入符号并把它下推进栈；读入下一个输入符号并把它下推进栈；v归约：归约：当栈顶的当栈顶的( (部分部分) )符号串形成一个句柄时，对符号串形成一个句柄时，对此句柄进行直接归约；此句柄进行直接归约；v接受：接受：当识别程序发现

4、栈中除了栈底标志符号当识别程序发现栈中除了栈底标志符号# #外外仅有识别符号，而输入也已到达右端仅有识别符号，而输入也已到达右端# #，则接受；，则接受；v报错：报错：当识别程序察觉一个错误，因此输入符号串当识别程序察觉一个错误，因此输入符号串不是句子而无法继续识别工作时，调用一个出错处不是句子而无法继续识别工作时，调用一个出错处理子程序进行处理或停止。理子程序进行处理或停止。 步骤 栈 输入 动作 规则 （1） （2） （3） （4） （5） （6） （7） （8） （9）（10）（11） # #i #E #E* #E*i #E*E #E #E+ #E+i #E+E #E i*i+i# *i

5、+i#*i+i# i+i#+i#+i#+i# i# 移入 归约 移入 移入 归约 归约 移入 移入 归约 归约 接受 E=i E=i E=E*E E=i E=E+E例例5.1 5.1 设有文法设有文法GEGE：E=E+E|EE=E+E|E* *E|(E)|iE|(E)|i自底向上分析技术的步骤自底向上分析技术的步骤: : 1) 1) 找出句柄找出句柄u;u; 2) 2) 找出规则找出规则U=uU=u； 3) 把把u u直接归约成直接归约成U U。 分析技术不同分析技术不同, ,寻找句柄的方法也不同。寻找句柄的方法也不同。5.25.2 算符优先分析技术算符优先分析技术 一、一、算符优先分析技术的

6、引进算符优先分析技术的引进 二、二、算符文法算符文法 三、三、算符优先关系与算符优先文法算符优先关系与算符优先文法 四、四、算符优先文法句型的识别算符优先文法句型的识别 五、实际应用中的五、实际应用中的算符优先分析技术算符优先分析技术 一、算符优先分析技术的引进一、算符优先分析技术的引进 对算术表达式，运算符完全决定了运算对算术表达式，运算符完全决定了运算次序，运算次序，运算对象完全不起作用。对象完全不起作用。 因此，将文法中的因此，将文法中的终结符号终结符号看作看作运算符运算符； 非终结符号非终结符号看作看作运算对象运算对象。 算符优先分析技术：只在终结符号之间算符优先分析技术：只在终结符号

7、之间引进优先关系，并利用优先关系找出句柄引进优先关系，并利用优先关系找出句柄（最左质短语）。（最左质短语）。5.25.2算符优先分析技术算符优先分析技术一、算符优先分析技术的引进一、算符优先分析技术的引进二、算符文法二、算符文法 定义定义5.1 如果文法如果文法G中没有形如中没有形如 U =VW 的规则，其中的规则，其中U、V、WVN，则该文法，则该文法G称为算称为算符文法，缩写为符文法，缩写为OG。5.25.2算符优先分析技术算符优先分析技术 一、一、算符优先分析技术的引进算符优先分析技术的引进 二、二、算符文法算符文法 三、三、算符优先关系与算符优先文法算符优先关系与算符优先文法v算符优先

8、关系算符优先关系v算符优先文法算符优先文法5.2 简单优先分析技术5.2.1算符优先分析技术的引进5.2.2算符文法v算符优先关系算符优先关系v算符优先文法算符优先文法定义定义5.25.2 设文法设文法G G是一个算符文法，是一个算符文法，T Tj j与与T Ti i是两个任意的终结符号，而是两个任意的终结符号，而U,V,WVU,V,WVN N，定义算符优先关系如下：，定义算符优先关系如下：T Tj j=T=Ti i 当且仅当文法当且仅当文法G G中存在形如中存在形如U=U=T Tj jT Ti i或或U=U=T Tj jVTVTi i的规则；的规则；T Tj jT Ti i 当且仅当文法当且

9、仅当文法G G中存在形如中存在形如U=U=T Tj jV V的规则，其中的规则，其中V=TV=Ti i或或V=WTV=WTi i；T Tj jT Ti i 当且仅当文法当且仅当文法G G中存在形如中存在形如U=U=VTVTi i的规则，其中的规则，其中V=V=T Tj j或或V=V=T Tj jW W。例例 设有文法设有文法GZ: Z=E E=T|E+T T=F|TGZ: Z=E E=T|E+T T=F|T* *F F=(E)|iF F=(E)|i+ i + i + * * ( ) ( )i i + + * * ( =( ) 5.25.2算符优先分析技术算符优先分析技术 一、一、算符优先分析技

10、术的引进算符优先分析技术的引进 二、二、算符文法算符文法 三、三、算符优先关系与算符优先文法算符优先关系与算符优先文法v算符优先关系算符优先关系v算符优先文法算符优先文法定义定义5.55.5 设有算符文法设有算符文法G G，如果在它的任意两，如果在它的任意两个终结符号之间，算符优先关系个终结符号之间，算符优先关系 =、与、与至多只有一种关系成立，则称该文法至多只有一种关系成立，则称该文法G G为算符为算符优先文法，缩写为优先文法，缩写为OPGOPG。例例1 1 文法文法GZ: Z=E E=T|E+T GZ: Z=E E=T|E+T T=F|T T=F|T* *F F=(E)|iF F=(E)|

11、i例例2 2 文法文法GEGE： E=E+E|EE=E+E|E* *E|(E)|iE|(E)|i5.2 简单优先分析技术5.2.1算符优先分析技术的引进5.2.2算符文法四、四、算符优先文法句型的识别算符优先文法句型的识别v质短语质短语v算符优先识别算法算符优先识别算法定义定义5.65.6 设有算符文法设有算符文法GZGZ，( (句型的句型的) )质短语定义为这样一个短语：质短语定义为这样一个短语：它至少包含一个终结符号，且除它自身外不再包含其他质短语。它至少包含一个终结符号，且除它自身外不再包含其他质短语。例例1 1 文法文法GZ: Z=E E=T|E+T T=F|TGZ: Z=E E=T|

12、E+T T=F|T* *F F=(E)|iF F=(E)|i （考虑句型（考虑句型T+TT+T* *F+i)F+i)定理定理5.35.3 一个算符优先文法句型一个算符优先文法句型NN1 1TT1 1NN2 2 NNn nTTn nNNn+1 的最左质的最左质短语是满足条件：短语是满足条件：T Tj j1 1 T T Ti+1i+1的最左子符号串的最左子符号串 j jTTj jNNj+1j+1 NNi iTTi iNNi+1i+1 ，其中的，其中的N Nk k(k=1,2,(k=1,2,，n+1)n+1)可能有也可能无可能有也可能无。四、四、算符优先文法句型的识别算符优先文法句型的识别v质短语质

13、短语v算符优先识别算法算符优先识别算法例例 文法文法GZ:GZ: Z=E E=T|E+T Z=E E=T|E+T T=F|T T=F|T* *F F=(E)|iF F=(E)|i 设有输入符号串设有输入符号串i+(i+i)i+(i+i)* *i i， 试识别它是否是文法的句子。试识别它是否是文法的句子。五、实际应用中的五、实际应用中的算符优先分析技术算符优先分析技术 算符优先分析技术由于它的简单直观、所需存储容量小、算符优先分析技术由于它的简单直观、所需存储容量小、且速度快而被广泛应用于识别各类表达式，把且速度快而被广泛应用于识别各类表达式，把while、do与与if之类界限符也看作运算符之类

14、界限符也看作运算符 (称作广义运算符称作广义运算符)，给它们优先，给它们优先数，则算符优先分析技术可扩充到整个语言的处理。对于数，则算符优先分析技术可扩充到整个语言的处理。对于C等实际的程序设计语言，只需对文法稍加修改便可应用算符等实际的程序设计语言，只需对文法稍加修改便可应用算符优先分析技术。算符优先分析技术是一种行之有效、广为应优先分析技术。算符优先分析技术是一种行之有效、广为应用的分析技术。用的分析技术。五、实际应用中的五、实际应用中的算符优先分析技术算符优先分析技术 通常实际的编译程序应用算符优先分析通常实际的编译程序应用算符优先分析技术实现表达式的编译时，使用的栈往往不技术实现表达式

15、的编译时，使用的栈往往不是一个，而是两个，即运算分量栈与运算符是一个，而是两个，即运算分量栈与运算符栈，分别用来存放还不能生成目标栈，分别用来存放还不能生成目标(归约归约)的运的运算分量算分量(标识符或常量之类终结符号标识符或常量之类终结符号)与运算符与运算符(其他终结符号其他终结符号)。算法框图如下：。算法框图如下：5.2算符优先分析技术5.35.3 LR(K)分析技术分析技术 5.3.1 LR(K)分析技术的逻辑结构和分析过程分析技术的逻辑结构和分析过程 5.3.2 LR(0)分析技术分析技术 5.3.3 SLR(1)分析技术分析技术 5.3.4 LR(1)分析技术分析技术5.3.1 LR

16、(K)分析技术的逻辑结分析技术的逻辑结构和分析过程构和分析过程一、活前缀与可归前缀一、活前缀与可归前缀二、二、 LR(K)分析技术的逻辑结构分析技术的逻辑结构三、三、LR(K)分析技术的分析过程分析技术的分析过程5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程一、活前缀与可归前缀一、活前缀与可归前缀 1、定义定义 对于文法对于文法GS,若若S= , VtVt* *, ,则称则称为为规范前缀规范前缀, ,又称又称活前缀活前缀。 若若是含句柄的是含句柄的活前缀，并且每个句柄是活前缀，并且每个句柄是的后缀，则的后缀，则为可归规范前缀，或为可归规范前缀，或可归前缀可归前缀

17、。 例例: (0)S:=S (4)B:=C: (0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a (3)A:=ab (7)D:=a*rr5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程一、活前缀与可归前缀一、活前缀与可归前缀 1、定义定义 2 2、可归前缀的求法、可归前缀的求法 如某文法有可归前缀如某文法有可归前缀xAy ,AVn,xAy ,AVn, 若有规则：若有规则：A:=u,A:=u,则则xux

18、u也是文法的可归前缀。也是文法的可归前缀。 例例: :设有文法设有文法GS: (1) S:=aAcGS: (1) S:=aAc (2) A:=Abb (2) A:=Abb (3) A:=b (3) A:=br5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程二、二、 LR(K)分析技术的逻辑结构分析技术的逻辑结构 1、逻辑结构、逻辑结构 LR(K)分析器包括：总控程序和分析表分析器包括：总控程序和分析表 总控程序：根据不同的分析表决定下一步的总控程序：根据不同的分析表决定下一步的处理动作。对不同的文法，总控程序都一样，只处理动作。对不同的文法，总控程序都一样，只是分

19、析表不同。是分析表不同。 分析表：是分析表：是LR(K)分析技术的核心，是根据分析技术的核心，是根据具体文法按某种规则构造出来的。具体文法按某种规则构造出来的。图8-3LR(K)分析方法的逻辑结构5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程二、二、 LR(K)分析技术的逻辑结构分析技术的逻辑结构 1、逻辑结构、逻辑结构 2、分析表的组成、分析表的组成 (1)分析动作表：分析动作表：ACTIONS,y指明当状态指明当状态S与与向前看符号串向前看符号串y相匹配时所应采取的动作。包括：相匹配时所应采取的动作。包括：移进、归约、接受、出错移进、归约、接受、出错 (2)

20、状态转换表状态转换表 ：GOTOS,U指明当状态指明当状态S与与非终结符号非终结符号U相匹配时所转换到的下一状态。相匹配时所转换到的下一状态。 (表8-3）LR(K)分析表5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程三、三、LR(K)分析技术的分析过程分析技术的分析过程 分析步骤分析步骤: (1)将初始状态将初始状态S0与与#压进分析栈压进分析栈. (2)根据栈顶状态和当前输入符号查动作表进行以下工作根据栈顶状态和当前输入符号查动作表进行以下工作: a.移进移进:当前输入符号进符号栈当前输入符号进符号栈,新的状态进状态栈新的状态进状态栈,继续扫描继续扫描. b

21、.归约归约:按某规则归约按某规则归约,若规则的右部长度若规则的右部长度n,则符号栈顶和状态栈顶则符号栈顶和状态栈顶n个元素同时退栈个元素同时退栈. 把归约后的左部符号进符号栈把归约后的左部符号进符号栈,查状态转换表查状态转换表,新的新的状态进状态栈状态进状态栈. c.接受接受: 分析成功分析成功,结束结束. d.出错出错: 报告出错信息报告出错信息. (3)重复重复(2),直到接受或出错为止直到接受或出错为止. 5.3.1 LR(K)分析技术的逻辑结构和分分析技术的逻辑结构和分析过程析过程三、三、LR(K)分析技术的分析过程分析技术的分析过程 分析步骤分析步骤: (1)将初始状态将初始状态S0

22、与与#压进分析栈压进分析栈. (2)根据栈顶状态和当前输入符号查动作表进行以下工作根据栈顶状态和当前输入符号查动作表进行以下工作: a.移进移进:当前输入符号进符号栈当前输入符号进符号栈,新的状态进状态栈新的状态进状态栈,继续扫描继续扫描. b.归约归约:按某规则归约按某规则归约,若规则的右部长度若规则的右部长度n,则符号栈顶和状态栈顶则符号栈顶和状态栈顶n个元素同时退栈个元素同时退栈. 把归约后的左部符号进符号栈把归约后的左部符号进符号栈,查状态转换表查状态转换表,新的新的状态进状态栈状态进状态栈. c.接受接受: 分析成功分析成功,结束结束. d.出错出错: 报告出错信息报告出错信息. (

23、3)重复重复(2),直到接受或出错为止直到接受或出错为止. 例例:设有文法设有文法GL: (1)L:=E,L (2)L:=E (3)E:=a (4)E:=b 分析输入串分析输入串#a,b,a#5.3.2 LR(0)分析技术分析技术 一、基本概念一、基本概念 二、项集规范族和特征有穷状态机二、项集规范族和特征有穷状态机 三、三、 LR(0)分析表的构造分析表的构造 四、应用举例四、应用举例5.3.2 LR(0)分析技术分析技术一、基本概念一、基本概念(1) LR(0)(1) LR(0)项项 定义定义5.145.14 如果如果=uv=uv是文法是文法G G的一个规则，的一个规则，其中其中u u或或

24、v v可为空串，则可为空串，则Uu.vUu.v称为称为G G的一个的一个LR(0)LR(0)项，简称项。项，简称项。 完备项：完备项：圆点在整个右部之后的圆点在整个右部之后的LR(0)LR(0)项称为完备项。项称为完备项。 接受项接受项：如果一个完备项呈如果一个完备项呈Zu.形，形，Z是识别符号。是识别符号。 归约项归约项：其余所有的完备项称归约项：其余所有的完备项称归约项 。 不完备项：不完备项：不是完备项的项不是完备项的项 。 移入项移入项 ：圆点之后是终结符号的不完备项。：圆点之后是终结符号的不完备项。 待约项待约项：圆点之后是非终结符号的不完备项：圆点之后是非终结符号的不完备项 。 5

25、.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念 (1) LR(0)项项 (2) 初始项初始项 定义定义5.15 文法文法GZ的的LR(0)项项Z.u称为称为G的初始的初始LR(0)项，简称初始项。项，简称初始项。 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念 (1) LR(0)项项 (2) 初始项初始项 定义定义5.20 文法文法GZ的的LR(0)项项Z.u称为称为G的初始的初始LR(0)项，简称初始项。项，简称初始项。 (3) 后继项后继项 定义定义5.16 设设u.Av是文法是文法G的一个的一个LR(0)项，其中项，其中AVNVT，则，则LR(0)项项uA.

26、v称为称为它的后继项。它的后继项。 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念 (4) 项集项集 定义定义5.17 由由LR(0)项组成的集合称项组成的集合称LR(0)项集，项集，简称项集。简称项集。 后继项集后继项集: 如果识别程序所处状态所对应的如果识别程序所处状态所对应的项集中有一个项，其中圆点后面是符号项集中有一个项，其中圆点后面是符号X，则识别，则识别程序在该符号程序在该符号X下将进入所处状态的下将进入所处状态的X_后继状态。后继状态。相应的项集称相应的项集称X_后继项集。后继项集。 每个项集每个项集Si的后继项集的后继项集S通常是基本项集的闭通常是基本项集的闭包

27、集合，基本项集可直接由项集包集合，基本项集可直接由项集Si生成，生成， 即即uA.v|u.AvSi 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念 (5)项集的闭包项集的闭包 定义定义5.18 设设Si是文法是文法G的一个项集，项集的一个项集，项集Si 的闭包的闭包CLOSURE(Si )是按下列步骤构造而得的项是按下列步骤构造而得的项集。集。 步骤步骤1 Si中每个项在中每个项在CLOSURE(Si)中；中； 步骤步骤2 如果如果u.VvCLOSURE(Si )，且，且V =w是一个规则，则把是一个规则，则把V.w添入添入CLOSURE(Si )中；中； 步骤步骤3 重复步骤

28、重复步骤2，直到，直到CLOSURE(Si )不再扩不再扩大。这时所得的便是项集大。这时所得的便是项集Si的闭包的闭包CLOSURE(Si)。 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念二、项集规范族和特征有穷状态机二、项集规范族和特征有穷状态机 一个文法一个文法GZ的的LR(0)项集规范族的构造步骤：项集规范族的构造步骤： 步骤步骤1 初始项集初始项集S0=CLOSURE(Z.Z)是是G 的的LR(0)项集，这里项集，这里Z是包含有规则是包含有规则 Z =Z的增广文法之识别符号；的增广文法之识别符号； 步骤步骤2 如果如果Si是是G的项集，则的项集，则Si的一切后继项集的

29、一切后继项集 均是均是G的项集；的项集； 步骤步骤3 重复步骤重复步骤2，直到再无新的项集可以添入。，直到再无新的项集可以添入。 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念二、项集规范族和特征有穷状态机二、项集规范族和特征有穷状态机 一个文法一个文法GZ的的LR(0)项集规范族项集规范族的构造步骤：的构造步骤： 步骤步骤1 初始项集初始项集S0=CLOSURE(Z.Z)是是G的的LR(0)项集，这里项集，这里Z是是包含有规则包含有规则Z =Z的增广文法之识别符号；的增广文法之识别符号； 步骤步骤2 如果如果Si是是G的项集，则的项集，则Si的一切后继项集均是的一切后继项集均

30、是G的项集；的项集； 步骤步骤3 重复步骤重复步骤2，直到再无新的项集可以添入。，直到再无新的项集可以添入。 特别说明特别说明: 某一项集中某一项集中,不同的项不同的项,其后继符号相同时其后继符号相同时,后继项集相同。后继项集相同。 不同的不同的项集中项集中,若干个与前面对应相同的项若干个与前面对应相同的项,其后继项集与其后继项集与前面的相同。前面的相同。例：设有文法例：设有文法GS：(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念二、项集规范族和特征有穷状态机二、项集规范族和特

31、征有穷状态机 一个文法一个文法GZ的的LR(0)项集规范族项集规范族的构造步骤：的构造步骤： 步骤步骤1 初始项集初始项集S0=CLOSURE(Z.Z)是是G的的LR(0)项集，这里项集，这里Z是是包含有规则包含有规则Z =Z的增广文法之识别符号；的增广文法之识别符号； 步骤步骤2 如果如果Si是是G的项集，则的项集，则Si的一切后继项集均是的一切后继项集均是G的项集；的项集； 步骤步骤3 重复步骤重复步骤2，直到再无新的项集可以添入。，直到再无新的项集可以添入。 特别说明特别说明: 某一项集中某一项集中,不不 同的项同的项,其后继符号相同时其后继符号相同时,后继项集相同。后继项集相同。 不同

32、的不同的项集中项集中,若干个与前面对应相同的项若干个与前面对应相同的项,其后继项集与其后继项集与前面的相同。前面的相同。例：增广文法例：增广文法GS：(0)S=S(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d图8-55.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念二、项集规范族和特征有穷状态机二、项集规范族和特征有穷状态机 文法的文法的LR(0)项集规范族可以被抽象成一个有穷状态机项集规范族可以被抽象成一个有穷状态机(FSM)，其步骤如下，其步骤如下:步骤步骤1 把各个项集定义为该把各个项集定义为该FSM的内部状态，并用项集

33、的编的内部状态，并用项集的编号来命名各个状态，因此，每一个项集在号来命名各个状态，因此，每一个项集在FSM中有一个对中有一个对应状态；应状态；步骤步骤2 让该让该FSM状态之间的转换对应于后继关系。状态之间的转换对应于后继关系。步骤步骤3 与初始项集对应的状态作为该与初始项集对应的状态作为该FSM的初始状态，与的初始状态，与#归归约约_后继项集对应的状态作为该后继项集对应的状态作为该FSM的终止状态。的终止状态。这种有穷状态机这种有穷状态机FSM称为文法的称为文法的特征有穷状态机特征有穷状态机 (CFSM)。 5.3.2 LR(0)分析技术分析技术一、一、基本概念基本概念二、项集规范族和特征有

34、穷状态机二、项集规范族和特征有穷状态机 如果项集中包含的全是完备项，则称相应状态如果项集中包含的全是完备项，则称相应状态为为归约状态归约状态 ；如果项集中包含的全是不完备项，；如果项集中包含的全是不完备项，则称相应的状态为则称相应的状态为读状态读状态；如果项集中既有完备项，；如果项集中既有完备项，又有不完备项，则称相应的状态为又有不完备项，则称相应的状态为不适定状态不适定状态。 定义定义5.19 一个上下文无关文法一个上下文无关文法G是是LR(0)文文法法，当且仅当该文法，当且仅当该文法G的的CFSM中无不适定状态。中无不适定状态。5.3.2 LR(0)分析技术分析技术 三、三、 LR(0)分

35、析表的构造分析表的构造 (i)如果移入项如果移入项u.avSi,且且GO(Si,a)=Sj，其中，其中aVt，则置，则置ACTIONSi,a=把状态把状态j及符号及符号a移入移入(下推下推)进栈进栈，简记作，简记作Sj。 (ii)如果归约项如果归约项u.Si，且，且 =u是增广文法是增广文法G的第的第j个规个规则，则对任何输入符号则，则对任何输入符号a,aVt，置，置ACTIONSi,a=按第按第j个规个规则则 =u进行直接归约进行直接归约，简记作，简记作rj。 (iii)如果项如果项ZZ.Si，置，置ACTIONSi,#为为接受接受，简记作，简记作acc。 (iv)如果如果GO(Si,)=S

36、j,Vn，则置，则置GOTOSi,U=j。 (v)凡不能由上述凡不能由上述4个规则确定的分析表元素全置为报错标志个规则确定的分析表元素全置为报错标志(空空白白)。 表8-5例：增广文法例：增广文法GS：(0)S=S(1)S:=A (4)A:=c (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d5.3.2 LR(0)分析技术分析技术四、四、 应用举例应用举例例：设有文法例：设有文法GS: (1)S:=A (4)A:=c (0) S:=S (2)S:=B (5)B:=aBb (3)A:=aAb (6)B:=d 构造项集规范族和构造项集规范族和 LR(0)分析表，并对输入串分析

37、表，并对输入串 #aacbb#进行分析。进行分析。 5.3.3 SLR(1)分析技术分析技术 一、问题的提出一、问题的提出 二、简单向前看二、简单向前看1集合集合 三、三、 SLR(1)文法文法 四、四、 SLR(1)分析表的构造分析表的构造 五、应用举例五、应用举例5.3.3 SLR(1)分析技术分析技术一、问题的提出一、问题的提出 例：设有文法例：设有文法GS：(0)S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i 5.3.3 SLR(1)分析技术分析技术 一、问题的提出一、问题的提出 例：设有文法例：设有文法GS：(0)

38、S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i S2：E T. 归约项归约项 T T.T.* *F F 移入项移入项 S9: E E+T. E+T. 归约项归约项 TT.TT.* *F F 移入项移入项 S2 和和S9均为不适定状态均为不适定状态,文法文法GS不是不是LR(0)文法。文法。5.3.3 SLR(1)分析技术分析技术二、简单向前看二、简单向前看1集合集合 定义定义5.20 一个简单向前看一个简单向前看1集合是某些文法符号组成的集合是某些文法符号组成的集合，它和集合，它和CFSM中一个不适定状态的各个转换相联系。不

39、中一个不适定状态的各个转换相联系。不适定状态的转换有两类适定状态的转换有两类: 一类是文法符号一类是文法符号X下的转换下的转换(称称X_转换转换)，简单向前看，简单向前看1集合便是集合便是X， 另一类是另一类是# =u转换转换，简单向前看，简单向前看1集合是集合是FT1()： FT1()=FOLLOW() 例：文法例：文法GS的的CFSM的状态的状态S2是不适定状态，对于它是不适定状态，对于它的简单向前看的简单向前看1集合，存在两类转换：集合，存在两类转换： *_转换转换 简单向前看简单向前看1集合是集合是* #E =T转换转换 简单向前看简单向前看1集合是集合是 FT1(E) FT1(E)=

40、FOLLOW(E)=+,)，#5.3.3 SLR(1)分析技术分析技术 三、三、 SLR(1)文法文法 定义定义5.21 一个上下文无关文法一个上下文无关文法G是是SLR(1)文文法，当且仅当与其法，当且仅当与其CFSM每个不适定状态的各个每个不适定状态的各个T_转换与转换与# =u转换相联系的简单向前看转换相联系的简单向前看1集合集合互不相交。互不相交。 5.3.3 SLR(1)分析技术分析技术 四、四、 SLR(1)分析表的构造分析表的构造 分析表中的分析表中的ACTION部分与部分与GOTO部分可按下述规则构造如下部分可按下述规则构造如下:(i)如果移入项如果移入项u.avSi,且且GO

41、(Si,a)=Sj，其中，其中aVt，则置，则置ACTIONSi,a=把状态把状态j及符号及符号a移入移入(下推下推)进栈进栈，简记作，简记作Sj。(ii)如果归约项如果归约项u.Si，且，且 =u是增广文法是增广文法G的第的第j个规则，个规则，则对任何输入符号则对任何输入符号a,aFT1()，置，置ACTIONSi,a=按第按第j个规则个规则 =u进行直接归约进行直接归约，简记作，简记作rj。(iii)如果项如果项ZZ.Si，置，置ACTIONSi,#为为接受接受，简记作，简记作acc。(iv)如果如果GO(Si,)=Sj,VN，则置，则置GOTOSi,=j。(v)凡不能由上述凡不能由上述4

42、个规则确定的分析表元素全置为报错标志个规则确定的分析表元素全置为报错标志(空白空白)。 5.3.3 SLR(1)分析技术分析技术五、应用举例五、应用举例 例：设有文法例：设有文法GS：(0)S:=E (1)E:=E+T (4)T:=F (2)E:=T (5)F:=(E) (3)T:=T*F (6)F:=i 对输入串对输入串i+i*i#进行分析。进行分析。 *5.3.4 LR(1)分析技术分析技术 一、问题的提出一、问题的提出例例: : 设有文法设有文法S:S:(0)S:=S (4)B:=C(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db(1)S:=CbBA (5)B:=D

43、b (2)A:=Aab (6)C:=a(2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a(3)A:=ab (7)D:=a 其项集规范族如下图所示其项集规范族如下图所示: :5.3.4 LR(1)分析技术分析技术 一、问题的提出一、问题的提出 考察状态考察状态 S8 : C a,D a S10: SCbBA,A A.ab 对对S10，FT1(S)=# 与与 a 不相交不相交, 对对S8, FT1(C)=Follow(C)=a,b , FT1(D)= Follow(D)=b 有交集有交集, 因此该文法不能使用因此该文法不能使用SLR(1)分析技术分析技术.例例:设有文法设有文法S

44、:(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a5.3.4 LR(1)分析技术分析技术 二、二、 几个基本概念几个基本概念 1、LR(1)项项 定义：在定义：在LR(0)项中放一个向前搜索符号项中放一个向前搜索符号a, 成为形式成为形式: A .,a, 其中其中a Follow(A),Follow(A),称为称为LR(1)项。项。 2 2、有效项、有效项 定义定义: :设有文法设有文法GS,LR(1)GS,LR(1)项项A A . ,a 对活前缀对活前缀= =有效有效, ,是指存在规范推导：是指存在规

45、范推导：S=S=Ay=Ay=y, y VtVt* *, ,且满足下列条件且满足下列条件: :当当y=y=, a=# , a=# 当当y y, a=First(y), a=First(y) 考虑规范句型考虑规范句型:Cbabab:Cbabab和和CbaababCbaabab*rr例例:设有文法设有文法S:(0)S:=S (4)B:=C (1)S:=CbBA (5)B:=Db (2)A:=Aab (6)C:=a (3)A:=ab (7)D:=a5.3.4 LR(1)分析技术分析技术 二、二、 几个基本概念几个基本概念 3 3、LR(1)LR(1)项集的闭包项集的闭包 定义定义 设设Si是文法是文法G的一个的一个LR(1)项集，项集项集，项集Si的闭包的闭包CLOSURE(Si )是按下列步骤构造而得的项集。是按下列步骤构造而得的项集。 步骤步骤1 Si 中每个项在中每个项在CLOSURE(Si )中；中； 步骤步骤2 如果如果u.Vv,aCLOSURE(Si )，且，且V =w是一个规则，则把是一个规则，则把V.w,b,添入添入CLOSURE(Si )中中,这里这里b=First(va)； 步骤步骤3 重复步骤重复步骤2，直到，直到CLOSURE(Si )不再扩大。这不再扩大。这时所