自底向上分析－金锄头文库

资源描述

《自底向上分析》由会员分享，可在线阅读，更多相关《自底向上分析（105页珍藏版）》请在金锄头文库上搜索。

1、6 6 自底向上分析自底向上分析6.1 自底向上分析2 2 2 2 若采用自左向右的描述和分析输入串若采用自左向右的描述和分析输入串若采用自左向右的描述和分析输入串若采用自左向右的描述和分析输入串, ,那么自那么自那么自那么自底向上的基本算法是：底向上的基本算法是：底向上的基本算法是：底向上的基本算法是：从输入符号串开始，通过重复查找当前句型的从输入符号串开始，通过重复查找当前句型的从输入符号串开始，通过重复查找当前句型的从输入符号串开始，通过重复查找当前句型的句柄句柄句柄句柄( (最左简单短语最左简单短语最左简单短语最左简单短语) )，并利用有关规则进行规约，并利用有关规则进行规约，并利

2、用有关规则进行规约，并利用有关规则进行规约，若能规约为文法的识别符号，则表示分析成功，输若能规约为文法的识别符号，则表示分析成功，输若能规约为文法的识别符号，则表示分析成功，输若能规约为文法的识别符号，则表示分析成功，输入符号串是文法的合法句子，否则有语法错误。入符号串是文法的合法句子，否则有语法错误。入符号串是文法的合法句子，否则有语法错误。入符号串是文法的合法句子，否则有语法错误。基本算法思想基本算法思想:3 3 3 3分析过程是重复一下步骤：分析过程是重复一下步骤：1 1、找出当前句型的句柄、找出当前句型的句柄、找出当前句型的句柄、找出当前句型的句柄 x x （或句柄的变形）（或句柄的

3、变形）（或句柄的变形）（或句柄的变形）2 2、找出以、找出以、找出以、找出以 x x 为右部的规则为右部的规则为右部的规则为右部的规则 X X:= := x x 3 3、把、把、把、把 x x 规约为规约为规约为规约为X X，产生语法树的一枝产生语法树的一枝产生语法树的一枝产生语法树的一枝关键关键关键关键：找出当前句型的句柄：找出当前句型的句柄：找出当前句型的句柄：找出当前句型的句柄 x x ( (或其变形），这不是很容易或其变形），这不是很容易或其变形），这不是很容易或其变形），这不是很容易。6.1 移进规约分析（Shift-reduce parsing)4 4#S.R.P #符号符号栈栈输

4、输入串入串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。5 5 5 5 分析过程：把输入符号串按描述顺序一一地移进符分析过程：把输入符号串按描述顺序一一地移进符分析过程：把输入符号串按描述顺序一一地移进符分析过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄号形成当前句型的句柄时，就根据规则进行规约，将句柄号形

5、成当前句型的句柄时，就根据规则进行规约，将句柄号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规从符号栈中弹出，并将相应的非终结符号压入栈内（即规从符号栈中弹出，并将相应的非终结符号压入栈内（即规从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句则的左部符号），然后再检查栈内符号串是否形成新的句则的左部符号），然后再检查栈内符号串是否形成新的句则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到柄，若有就再进行规约，否则移进符号。分析一直进行到柄，

6、若有就再进行规约，否则移进符号。分析一直进行到柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号读到输入串的右界符为止。最后，若栈中仅含有左界符号读到输入串的右界符为止。最后，若栈中仅含有左界符号读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。和识别符号，则表示分析成功，否则失败。和识别符号，则表示分析成功，否则失败。和识别符号，则表示分析成功，否则失败。# #S.R.PS.R.P# #符号符号符号符号栈栈栈栈输输输输入串入串入串入串6 6 6 6例：例：例：例：GS:GS: SaAcBe SaAcBe

7、Ab Ab AAb AAb Bd Bd输入串为输入串为输入串为输入串为abbcdeabbcde，检查是否是该文法的合法句子。，检查是否是该文法的合法句子。，检查是否是该文法的合法句子。，检查是否是该文法的合法句子。若采用自底向上分析，即能否一步步规约若采用自底向上分析，即能否一步步规约若采用自底向上分析，即能否一步步规约若采用自底向上分析，即能否一步步规约当前句型的句柄当前句型的句柄当前句型的句柄当前句型的句柄，最终最终最终最终规约到规约到规约到规约到识别符号识别符号识别符号识别符号S S。先设立一个符号栈，我们统一符号。先设立一个符号栈，我们统一符号。先设立一个符号栈，我们统一符号。先设立

8、一个符号栈，我们统一符号“#”“#”作为待分析的符号串的左右分界符。作为待分析的符号串的左右分界符。作为待分析的符号串的左右分界符。作为待分析的符号串的左右分界符。作为初始状态，先将符号串的分界符推进符号栈，作为栈底作为初始状态，先将符号串的分界符推进符号栈，作为栈底作为初始状态，先将符号串的分界符推进符号栈，作为栈底作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。符号。符号。符号。分析过程如下表分析过程如下表分析过程如下表分析过程如下表: :7 7 7 7步骤步骤步骤步骤符号栈符号栈符号栈符号栈输入符号串输入符号串输入符号串输入符号串动作动作动作动作1 12 23 34 45 5

9、6 67 78 89 9101011111212# #a#a#a#ab b#a#aAbAb#a#aA A#aAc#aAc#aAc#aAcd d#aAc#aAcB B# #aAcBeaAcBe# #S S#S#S#a#aA Aabbcde#abbcde#bbcde#bbcde#bcde#bcde#bcde#bcde#cde#cde#cde#cde#de#de#e#e#e#e# # # #准备准备准备准备. .初始化初始化初始化初始化移进移进移进移进移进移进移进移进规约规约规约规约( (AbAb) )移进移进移进移进规约规约规约规约( (AAbAAb) )移进移进移进移进移进移进移进移进规约规约规

10、约规约( (BdBd) )移进移进移进移进规约规约规约规约( (SaAcBeSaAcBe) )成功成功成功成功例：例：例：例：GS: SaAcBe Ab GS: SaAcBe Ab AAb Bd AAb Bd8 8 8 8 这一方法简单明了这一方法简单明了这一方法简单明了这一方法简单明了, ,不断地进行移进规约不断地进行移进规约不断地进行移进规约不断地进行移进规约, ,关键是确定当前句型的关键是确定当前句型的关键是确定当前句型的关键是确定当前句型的句柄句柄句柄句柄. .说明说明说明说明:(1):(1)例子的分析过程是一步步地规约当前句型的句柄例子的分析过程是一步步地规约当前句型的句柄例子的分析

11、过程是一步步地规约当前句型的句柄例子的分析过程是一步步地规约当前句型的句柄该句子的唯一语法树为该句子的唯一语法树为该句子的唯一语法树为该句子的唯一语法树为: :a aA Ac cB Be eA Ab bb bd dS S注意两点：注意两点：注意两点：注意两点：（a a）栈内符号串）栈内符号串）栈内符号串）栈内符号串+ + 未处理输入符号串未处理输入符号串未处理输入符号串未处理输入符号串 = = 当前句型当前句型当前句型当前句型（b b）句柄都在栈顶）句柄都在栈顶）句柄都在栈顶）句柄都在栈顶实际上，以上分析过程并未真正解决句柄的识别问题实际上，以上分析过程并未真正解决句柄的识别问题实际上，以上分

12、析过程并未真正解决句柄的识别问题实际上，以上分析过程并未真正解决句柄的识别问题9 9 9 9(2)(2)未真正解决句柄的识别未真正解决句柄的识别未真正解决句柄的识别未真正解决句柄的识别. . 上述分析过程的怎样上述分析过程的怎样上述分析过程的怎样上述分析过程的怎样识别句柄识别句柄识别句柄识别句柄的，主要看栈顶符号串的，主要看栈顶符号串的，主要看栈顶符号串的，主要看栈顶符号串是否形成规则的右部。是否形成规则的右部。是否形成规则的右部。是否形成规则的右部。这种做法形式上是正确的，但在实际上不一定正确。这种做法形式上是正确的，但在实际上不一定正确。这种做法形式上是正确的，但在实际上不一定正确。这

13、种做法形式上是正确的，但在实际上不一定正确。举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。举例的分析过程可以说是一种巧合。因为不能认为因为不能认为因为不能认为因为不能认为: : 对句型对句型对句型对句型 xuY xuY 而言而言而言而言若有若有若有若有A Auu，即，即，即，即A Au u 就断定就断定就断定就断定u u是简单短语，是简单短语，是简单短语，是简单短语， u u 就是句柄，就是句柄，就是句柄，就是句柄，而是要同时满足而是要同时满足而是要同时满足而是要同时满足 S S xAY xAY* *6.2 简单优先分析例例例例: : G

14、S GS SbAb SbAb A(B | a A(B | a B Aa) B Aa) (1) (1) 先确定符号之间的优先关系先确定符号之间的优先关系先确定符号之间的优先关系先确定符号之间的优先关系优先关系的定义优先关系的定义优先关系的定义优先关系的定义: : 设设设设 X, Y X, Y 为可能相邻的符号为可能相邻的符号为可能相邻的符号为可能相邻的符号定义定义定义定义: X = Y X: X = Y X的优先级等于的优先级等于的优先级等于的优先级等于Y Y X Y X X Y X X Y X的优先级大于的优先级大于的优先级大于的优先级大于Y Y. . . . .1) X=Y if1) X=

15、Y if文法中有形如文法中有形如文法中有形如文法中有形如 AXY AXY 2) XY if 2) XY if 3) XY if 文法中有形如文法中有形如文法中有形如文法中有形如 ABD ABD的规则的规则的规则的规则, , 其中其中其中其中 B B X X或或或或D DY Y 。 + + . . . . . .+ +* *+例例例例: : GS GS SbAb b=A, A=b ,b(,bb,ab,Bb SbAb b=A, A=b ,b(,bb,ab,Bb A(B | a (=B, (A, (,(a A(B | a (=B, (A, (,(a,aa,)a B Aa) A=a,a=),Ba,aa

16、,)a SbAbb=A,A=b,b(,bb,ab,BbSbAbb=A,A=b,b(,bb,ab,BbA(B|a(=B,(A,(,(aA(B|a(=B,(A,(,(a,aa,)aBAa)A=a,a=),Ba,aa,)aSbA(Ba)#Sb=A=(=a=)#=6.3 算符优先分析(Operator-Precedence Parsing)131313131) 1) 这是一种这是一种这是一种这是一种经典经典经典经典的自底向上分析法，简单直观，并被广泛使的自底向上分析法，简单直观，并被广泛使的自底向上分析法，简单直观，并被广泛使的自底向上分析法，简单直观，并被广泛使用。用。用。用。运算法则运算法则运算

17、法则运算法则: :1. 1.乘除乘除乘除乘除的优先大于的优先大于的优先大于的优先大于加减加减加减加减 2. 2.同优先级的运算符同优先级的运算符同优先级的运算符同优先级的运算符左左左左大于大于大于大于右右右右 3. 3.括号括号括号括号内内内内的优先级大于括号的优先级大于括号的优先级大于括号的优先级大于括号外外外外于是：于是：于是：于是： 4+8-6/2*3 4+8-6/2*3 运算过程和结果唯一。运算过程和结果唯一。运算过程和结果唯一。运算过程和结果唯一。2) 2) 称为算符优先分析是因为这种方法是称为算符优先分析是因为这种方法是称为算符优先分析是因为这种方法是称为算符优先分析是因为这种方

18、法是仿效仿效仿效仿效算术式的四则运算算术式的四则运算算术式的四则运算算术式的四则运算而建立起来的，作算术式的四则运算时，为了保证而建立起来的，作算术式的四则运算时，为了保证而建立起来的，作算术式的四则运算时，为了保证而建立起来的，作算术式的四则运算时，为了保证计算结果计算结果计算结果计算结果和过程的和过程的和过程的和过程的唯一性唯一性唯一性唯一性，规定了一个统一的，规定了一个统一的，规定了一个统一的，规定了一个统一的四则运算法则四则运算法则四则运算法则四则运算法则，规定运，规定运，规定运，规定运算符之间的算符之间的算符之间的算符之间的优先关系优先关系优先关系优先关系。 6.3.1直观算符

19、优先文法直观算符优先文法14141414例例例例: GE : GE EE+E | E*E | (E) | i EE+E | E*E | (E) | i V Vt t=+, *, (, ), i =+, *, (, ), i 这是一个二义文法，要用算符优先法分析有该文法所确定的这是一个二义文法，要用算符优先法分析有该文法所确定的这是一个二义文法，要用算符优先法分析有该文法所确定的这是一个二义文法，要用算符优先法分析有该文法所确定的语言句子。语言句子。语言句子。语言句子。如：如：如：如：i+i*ii+i*i(1) (1) 先确定终结符之间的优先关系先确定终结符之间的优先关系先确定终结符之间的优

20、先关系先确定终结符之间的优先关系优先关系的定义优先关系的定义优先关系的定义优先关系的定义: : 设设设设 a, b a, b 为可能相邻的终结符为可能相邻的终结符为可能相邻的终结符为可能相邻的终结符定义定义定义定义: a = b a: a = b a的优先级等于的优先级等于的优先级等于的优先级等于b b a b a a b a a b a的优先级大于的优先级大于的优先级大于的优先级大于b b. . . . .151515152)2)例中文法终结符之间的优先关系可以用一个矩阵例中文法终结符之间的优先关系可以用一个矩阵例中文法终结符之间的优先关系可以用一个矩阵例中文法终结符之间的优先关系可以用一

21、个矩阵MM来表示来表示来表示来表示 ) ) = = i i * * + + # # ) ) ( ( i i * * + +b(b(右栈外右栈外右栈外右栈外) )a(a(右栈内右栈内右栈内右栈内) ). . . . . . . . . . . . . . . . . . . . . . . 3)3)矩阵元素空白处表示这两个终结符不能相邻矩阵元素空白处表示这两个终结符不能相邻矩阵元素空白处表示这两个终结符不能相邻矩阵元素空白处表示这两个终结符不能相邻, ,故没有优先关系故没有优先关系故没有优先关系故没有优先关系16161616步骤步骤步骤步骤符号栈符号栈符号栈符号栈输入串输入串输入串输入串优先关系

22、优先关系优先关系优先关系动作动作动作动作1 12 23 34 45 56 67 78 89 910101111# #i#i#E#E#E+#E+#E+i#E+i#E+E#E+E#E+E*#E+E*#E+E*i#E+E*i#E+E*E#E+E*E#E+E#E+E#E#E# # # # #i#i#*i#*i#*i#*i#i*i#i*i#+i*i#+i*i#+i*i#+i*i#i+i*i#i+i*i#i#+i+#+#+i+*i*+*+*i*#i#*#*#+#+#移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进移进规约规约规约规约规约规约规约规约规约规约规约规约规约规约规约

23、规约规约规约规约规约接受接受接受接受 ) ) = = i i * * + + # # ) ) ( ( i i * * + +b ba a. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EE+E | E*E | (E) | iEE+E | E*E | (E) | i算法算法算法算法: : 当栈顶项当栈顶项当栈顶项当栈顶项( (或次栈顶或次栈顶或次栈顶或次栈顶项项项项) )终结符终结符终结符终结符的优先级的优先级的优先级的优先级

24、大于栈外的大于栈外的大于栈外的大于栈外的终结符终结符终结符终结符的的的的优先级则进行规约，优先级则进行规约，优先级则进行规约，优先级则进行规约，否则移进否则移进否则移进否则移进. .(2) (2) 分析过程分析过程分析过程分析过程 i+i*i i+i*i6.3.2 算符优先文法的定义17171717 (1)算符优先文法(OPG) (2)构造优先关系矩阵 (3)算符优先分析算法的设计18181818（1）算符优先文法（）算符优先文法（OPG）算符文法（算符文法（算符文法（算符文法（OGOG）的定义）的定义）的定义）的定义优先关系的定义优先关系的定义优先关系的定义优先关系的定义若文法中无形如若文法

25、中无形如若文法中无形如若文法中无形如ABCABC的规则，这里的规则，这里的规则，这里的规则，这里B,CB,CV VN N 则称则称则称则称GG为为为为OGOG文法，也就是文法，也就是文法，也就是文法，也就是算符文法算符文法算符文法算符文法。若若若若GG是一是一是一是一OGOG文法，文法，文法，文法，a,ba,bV VT T, A,B,C, A,B,CV VN N分别有以下三种情况分别有以下三种情况分别有以下三种情况分别有以下三种情况: :GG中不含中不含中不含中不含的产生式的产生式的产生式的产生式191919191) a=b if1) a=b if文法中有形如文法中有形如文法中有形如文法中有

26、形如 Aab Aab或或或或AaBb AaBb 的规则。的规则。的规则。的规则。 2) ab if 2) ab if 3) ab if 文法中有形如文法中有形如文法中有形如文法中有形如 ABb ABb的规则的规则的规则的规则, , 其中其中其中其中 B B a a或或或或B B aC aC 。 + + + . . . . . .+ + +算符优先文法（算符优先文法（OPG）的定义）的定义设有一设有一OG文法，如果在任意两个终结符之间，文法，如果在任意两个终结符之间，至多只有至多只有上述关系中的一种，则称该文法为上述关系中的一种，则称该文法为算符优先文法算符优先文法(OPG)21212121对于

27、对于OG算法的几点说明算法的几点说明:1) 1) 运算是以中缀形式出现的运算是以中缀形式出现的运算是以中缀形式出现的运算是以中缀形式出现的3) 3) 算法语言中的表达式以及大部分语言成分算法语言中的表达式以及大部分语言成分算法语言中的表达式以及大部分语言成分算法语言中的表达式以及大部分语言成分的文法均是的文法均是的文法均是的文法均是OGOG文法文法文法文法2) 2) 可以证明，若文法为可以证明，若文法为可以证明，若文法为可以证明，若文法为OGOG文法，则不会出现文法，则不会出现文法，则不会出现文法，则不会出现两个非终结符相邻的句型。两个非终结符相邻的句型。两个非终结符相邻的句型。两个非终结符相

28、邻的句型。2222（2）构造优先关系矩阵）构造优先关系矩阵FIRSTVT( B )=b|BFIRSTVT( B )=b|Bbb或或或或B BCb,bCb,bV Vt t, B, BV Vn n + + +LASTVT( B )=a|BLASTVT( B )=a|Baa或或或或B BaC,aaC,aV Vt t, B, BV Vn n + + + 求求求求 “ “ = = ” ” 检查每一条规则，若有检查每一条规则，若有检查每一条规则，若有检查每一条规则，若有A:=A:=abab或或或或 A:=A:=a aB Bb b, , 则则则则 a=ba=b. . . 求求求求“ “ ” ”复杂一些，需定

29、义两个集合复杂一些，需定义两个集合复杂一些，需定义两个集合复杂一些，需定义两个集合. . .23232323求求“ ”:. .若文法有规则若文法有规则若文法有规则若文法有规则 A.aB. A.aB. ，对任何，对任何，对任何，对任何b, bb, bFIRSTVT(B) FIRSTVT(B) 则有：则有：则有：则有：a ba ba b. .例例例例: : 文法文法文法文法GE GE E:=E+T|T E:=E+T|T T:=T*F|F T:=T*F|F F:=(E)|i F:=(E)|i 1 1、求每个非终结符号的、求每个非终结符号的、求每个非终结符号的、求每个非终结符号的FIRSTVTFIRS

30、TVT及及及及LASTVTLASTVT FIRSTVT LASTVTE+,*,(,i+.*,),i T*,(,i*,),iF(,i),i2、求、求=关系：关系：(=)3、求、求关系：关系：+FIRSTVT(T),*FITSTVT(F),(关系：关系：LASTVT(E)+,LASTVT(T)*,LASTVT(E) ) ) = = i i * * + + # # ) ) ( ( i i * * + +b(b(右栈外右栈外右栈外右栈外) )a(a(右栈内右栈内右栈内右栈内) ). . . . . . . . . . . . . . . . . . . . . . . 构造优先关系表：构造优先关系表：

31、26262626构造构造FIRSTBT(A)的算法的算法1)1)若有规则若有规则若有规则若有规则AbAb或或或或ABb(ABb(存在存在存在存在A Abb或或或或A ABb) Bb) 则则则则b bFIRSTVT(A)FIRSTVT(A)+ + +2)2)若有规则若有规则若有规则若有规则ABAB且且且且b bFIRSTVT(B), FIRSTVT(B), 则则则则b bFIRSTVT(A) FIRSTVT(A) 说明说明说明说明: :因为因为因为因为B Bbb或或或或B BCb,Cb,所以有所以有所以有所以有A ABBbb或或或或 A AB B CbCb+ + + + +27272727设一个

32、栈设一个栈设一个栈设一个栈S S和一个二维布尔数组和一个二维布尔数组和一个二维布尔数组和一个二维布尔数组F F FA,b=TRAE iff b FA,b=TRAE iff bFIRSTVT(A) FIRSTVT(A) PROCEDBRE INSERT(A,b) PROCEDBRE INSERT(A,b) IF NOT FA,b THEN IF NOT FA,b THEN BEGIN BEGIN FA,b:=TRAE FA,b:=TRAE 把把把把(A,b)(A,b)推进推进推进推进S S栈栈栈栈 /* b /* bFIRSTVT(A) */ FIRSTVT(A) */ END END BEGI

33、N main BEGIN main FOR FOR 每个非终结符号每个非终结符号每个非终结符号每个非终结符号A A和终结符和终结符和终结符和终结符b DO b DO FA,b:=FALSE /* FA,b:=FALSE /*赋值符赋值符赋值符赋值符*/ */ FOR FOR 每个形如每个形如每个形如每个形如A:=bA:=b或或或或A:=Bb A:=Bb 的规则的规则的规则的规则 DO DO INSERT(A,b) INSERT(A,b) 具体方法如下具体方法如下具体方法如下具体方法如下: :28282828WHILE SWHILE S栈非空栈非空栈非空栈非空 DO DO BEIGN BEIGN

34、把把把把S S栈的顶项弹出栈的顶项弹出栈的顶项弹出栈的顶项弹出, ,记为记为记为记为 (B,b)/* b (B,b)/* bFIRSTVT(A)*/ FIRSTVT(A)*/ FOR FOR 每条形如每条形如每条形如每条形如A:=BA:=B的规则的规则的规则的规则 DO DO INSTER(A,b); /* b INSTER(A,b); /* bFIRSTVT(A)*/ FIRSTVT(A)*/ END OF WHILE END OF WHILE ENDEND上述算法的工作结果是得到一个二维的布尔数组上述算法的工作结果是得到一个二维的布尔数组上述算法的工作结果是得到一个二维的布尔数组上述算法

35、的工作结果是得到一个二维的布尔数组F,F,从从从从F F 可以得到任何非终结符号可以得到任何非终结符号可以得到任何非终结符号可以得到任何非终结符号A A的的的的FIRSTVT FIRSTVT FIRSTVT(A)=b|FA,b=TRAE FIRSTVT(A)=b|FA,b=TRAE 29292929构造构造LASTBT(A)的算法的算法1. 1.若有规则若有规则若有规则若有规则A:=aA:=a或或或或A:=aB,A:=aB,则则则则a aLASTVT(A)LASTVT(A)2. 2.若有规则若有规则若有规则若有规则A:=B,A:=B,且且且且a aLASTVT(B)LASTVT(B)则则则则a

36、 aLASTVT(A)LASTVT(A)设一个栈设一个栈设一个栈设一个栈ST,ST,和一个布尔数组和一个布尔数组和一个布尔数组和一个布尔数组B B PROCEDARE INSERT(A,a) PROCEDARE INSERT(A,a) IF NOT BA,a THEN IF NOT BA,a THEN BEGIN BEGIN BA,a:=TRAE; BA,a:=TRAE;把把把把(A,a)(A,a)推进推进推进推进STST栈栈栈栈; ; END; END;30303030BEGIN BEGIN FOR FOR 每个非终结符号每个非终结符号每个非终结符号每个非终结符号A A和终结符号和终结符号和

37、终结符号和终结符号a DO a DO BA,a:=FALSE; BA,a:=FALSE; FOR FOR 每个形如每个形如每个形如每个形如A:=aA:=a或或或或A:=aBA:=aB的规则的规则的规则的规则 DO DO INSERT (A,a); INSERT (A,a); WHILE ST WHILE ST栈非空栈非空栈非空栈非空 DO DO BEGIN BEGIN 把把把把STST栈的栈顶弹出栈的栈顶弹出栈的栈顶弹出栈的栈顶弹出, ,记为记为记为记为(B,a); (B,a); FOR FOR 每条形如每条形如每条形如每条形如A:=BA:=B的规则的规则的规则的规则 DO DO INSERT

38、(A,a); INSERT(A,a); END OF WHILE; END OF WHILE; END;END;31313131构造优先关系矩阵的算法构造优先关系矩阵的算法构造优先关系矩阵的算法构造优先关系矩阵的算法FOR FOR 每条规则每条规则每条规则每条规则A:=xA:=x1 1x x2 2xxn n DO DO FOR i:=1 TO n-1 DO FOR i:=1 TO n-1 DO BEGIN BEGIN IF x IF xi i和和和和x xi+1i+1均为终结符均为终结符均为终结符均为终结符,THEN ,THEN 置置置置 x xi i=x=xi+1i+1 IF in-2 IF

39、 in-2，且，且，且，且x xi i和和和和x xi+2i+2都为终结符号但都为终结符号但都为终结符号但都为终结符号但 x xi+1i+1为非终结符号为非终结符号为非终结符号为非终结符号 THEN THEN 置置置置 x xi i=x=xi+2 i+2 IF x IF xi i为终结符号为终结符号为终结符号为终结符号x xi+1i+1为非终结符号为非终结符号为非终结符号为非终结符号 THEN THEN FOR FIRSTVT(x FOR FIRSTVT(xi+1i+1) )中的每个中的每个中的每个中的每个b DO b DO 置置置置x xi ibxaxi+1 i+1 END END . .

40、. . .32323232（3）算符优先分析算法的实现）算符优先分析算法的实现. 先定义优先级，在分析过程中通过比较相邻先定义优先级，在分析过程中通过比较相邻先定义优先级，在分析过程中通过比较相邻先定义优先级，在分析过程中通过比较相邻运算符之间的优先级来确定句型的运算符之间的优先级来确定句型的运算符之间的优先级来确定句型的运算符之间的优先级来确定句型的“ “句柄句柄句柄句柄” ”并进行并进行并进行并进行归约归约归约归约. . 定义定义定义定义素短语：文法素短语：文法素短语：文法素短语：文法GG的句型的素短语是一个短的句型的素短语是一个短的句型的素短语是一个短的句型的素短语是一个短语，它至少包

41、含有一个终结符号，并且除它自身语，它至少包含有一个终结符号，并且除它自身语，它至少包含有一个终结符号，并且除它自身语，它至少包含有一个终结符号，并且除它自身以外不再包含其他素短语以外不再包含其他素短语以外不再包含其他素短语以外不再包含其他素短语. .最左素短语最左素短语最左素短语最左素短语？33333333文法的语法树文法的语法树文法的语法树文法的语法树: : E E T T E E + + T T + + T T T T F F * * F F i i E E短语短语短语短语:T+T*F+i, T+T*F :T+T*F+i, T+T*F T( T(最左最左最左最左), T*F, i ), T

42、*F, i 其中其中其中其中T T不包含终结符不包含终结符不包含终结符不包含终结符,T,T是句型是句型是句型是句型而而而而T+T*F+iT+T*F+i和和和和T+T*FT+T*F包含其他包含其他包含其他包含其他素短语素短语素短语素短语. .只有只有只有只有T*FT*F和和和和i i为素短语为素短语为素短语为素短语, ,其中其中其中其中T*FT*F为最左素短语为最左素短语为最左素短语为最左素短语, ,而而而而该句型句柄为该句型句柄为该句型句柄为该句型句柄为T.T.例例例例: : 文法文法文法文法GE GE E:=E+T|T E:=E+T|T T:=T*F|F T:=T*F|F F:=(E)|

43、i F:=(E)|i 求句型求句型求句型求句型T+T*F+i T+T*F+i 的素短语的素短语的素短语的素短语34343434于是算符优先分析法：如何确定当前句型的最左素短语？于是算符优先分析法：如何确定当前句型的最左素短语？于是算符优先分析法：如何确定当前句型的最左素短语？于是算符优先分析法：如何确定当前句型的最左素短语？设有设有设有设有OPGOPG文法句型为文法句型为文法句型为文法句型为: : #N #N1 1a a1 1N N2 2a a2 2NNn na an nN Nn+1n+1# # 其中其中其中其中N Ni i为非终结符为非终结符为非终结符为非终结符( (可以为空可以为空可以为

44、空可以为空), a), ai i为终结符为终结符为终结符为终结符定理定理定理定理：一个：一个：一个：一个OPGOPG句型的最左素短语是满足下列条件的句型的最左素短语是满足下列条件的句型的最左素短语是满足下列条件的句型的最左素短语是满足下列条件的最左子串：最左子串：最左子串：最左子串：a aj-1j-1N Nj ja aj jNNi ia ai iN Ni+1i+1a ai+1i+1其中其中其中其中 a aj-1j-1a a ai+1i+1. . . . . . . . . . 35353535 根据该定理根据该定理根据该定理根据该定理, ,要找句型的最左素短语就是要找满足要找句型的最左素短语

45、就是要找满足要找句型的最左素短语就是要找满足要找句型的最左素短语就是要找满足上述条件的最左子串上述条件的最左子串上述条件的最左子串上述条件的最左子串. . 注意注意注意注意: :出现在出现在出现在出现在a aj j左端和左端和左端和左端和a a i i右端的非终结符号一定右端的非终结符号一定右端的非终结符号一定右端的非终结符号一定属于这个素短语属于这个素短语属于这个素短语属于这个素短语, ,因为我们的运算是中缀形式给出的因为我们的运算是中缀形式给出的因为我们的运算是中缀形式给出的因为我们的运算是中缀形式给出的(OPG(OPG文法的特点文法的特点文法的特点文法的特点)NaNaNaN )NaNa

46、NaN NaWaNNaWaN例例: 文法文法GE E:=E+T|T T:=T*F|F F:=(E)|i分析文法的句型分析文法的句型T+T*F+i36363636可以看出可以看出可以看出可以看出: : 1. 1. 每次每次每次每次规约规约规约规约最左子串最左子串最左子串最左子串, ,确实是当前句型的确实是当前句型的确实是当前句型的确实是当前句型的最左素短语最左素短语最左素短语最左素短语( (语法树）语法树）语法树）语法树） 2. 2. 规约的不都是真句柄（仅规约的不都是真句柄（仅规约的不都是真句柄（仅规约的不都是真句柄（仅i i规约为规约为规约为规约为F F是句柄，但它是句柄，但它是句柄，但它是

47、句柄，但它是最左短语是最左短语是最左短语是最左短语) ) 3. 3. 没有完全按规则进行规约没有完全按规则进行规约没有完全按规则进行规约没有完全按规则进行规约, ,因为因为因为因为素短语不一定是简素短语不一定是简素短语不一定是简素短语不一定是简单短语单短语单短语单短语步骤步骤步骤步骤句型句型句型句型关系关系关系关系最左子串最左子串最左子串最左子串规约符号规约符号规约符号规约符号1 12 23 34 4#T+T*F+i#T+T*F+i#T+T+i#T+T+i#E+i#E+i#E+F#E+F#+#+#+#+#+#+#T*FT*FT+TT+Ti iE+FE+FT TE EE EF F. . . .

48、 . . . . . . . . . . . . . . . . .37373737算符优先分析法的实现：算符优先分析法的实现：详见讲义，基本部分是找句型的最左子串（最左素短语）详见讲义，基本部分是找句型的最左子串（最左素短语）详见讲义，基本部分是找句型的最左子串（最左素短语）详见讲义，基本部分是找句型的最左子串（最左素短语）并进行规约。并进行规约。并进行规约。并进行规约。# #分析程序分析程序分析程序分析程序优先关系矩阵优先关系矩阵优先关系矩阵优先关系矩阵# #符号符号符号符号栈栈栈栈输输输输入串入串入串入串当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的

49、优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终结符的优先级时，移进。表明找到了素短语的尾，再往前找其头，并进行规约。进。表明找到了素短语的尾，再往前找其头，并进行规约。进。表明找到了素短语的尾，再往前找其头，并进行规约。进。表明找到了素短语的尾，再往前找其头，并进行规约。优先函数为了节约存储空间和便于执行比较运算为了节约存储空间和便于执行比较运算?，用两，用两个优

50、先函数个优先函数f和和g，它们是从终结符号映射到整数，它们是从终结符号映射到整数的函数。对于终结符号的函数。对于终结符号a和和b选择选择f和和g,使之满足：使之满足：1.当当a=b时时,f(a)=g(b);2.当当ab时时,f(a)g(b);3.当当ab时时,f(a)g(b)。于是于是a和和b之间的优先关系可以由比较之间的优先关系可以由比较f(a)与与g(b)的大小来决定。的大小来决定。算法算法:从优先关系构造优先函数从优先关系构造优先函数方法：方法：1.a VT #,建立两个符号建立两个符号fa和和ga;2.若若a=b,从从fa至至gb画一条弧；也从画一条弧；也从gb至至fa画画一条弧一条

51、弧3.a，b VT，若若ab，则从，则从fa至至gb画一条弧；画一条弧；若若ab，则从，则从gb至至fa画一条弧画一条弧;4.若图中无环，则存在优先函数，若图中无环，则存在优先函数，f(a)和和g(b)等于从等于从fa和和gb出发所能到达的结点出发所能到达的结点个数（包括该结点自身）。个数（包括该结点自身）。id+* #f664 2g753 241414141注意特点注意特点: (a) (a) 优先函数值不唯一优先函数值不唯一优先函数值不唯一优先函数值不唯一 (b) (b) 优点：优点：优点：优点：节省内存空间节省内存空间节省内存空间节省内存空间若文法有若文法有若文法有若文法有n n个终结

52、符，则关系矩阵为个终结符，则关系矩阵为个终结符，则关系矩阵为个终结符，则关系矩阵为n n2 2 而优先函数为而优先函数为而优先函数为而优先函数为2n 2n 易于比较：算法上容易实现易于比较：算法上容易实现易于比较：算法上容易实现易于比较：算法上容易实现, ,数与数比数与数比数与数比数与数比, ,不必不必不必不必查矩阵查矩阵查矩阵查矩阵. . (c) (c) 缺点：可能掩盖错误缺点：可能掩盖错误缺点：可能掩盖错误缺点：可能掩盖错误. . 算符优先分析小结算符优先分析小结优点优点1.简单、效率高简单、效率高2.能够处理部分二义性文法能够处理部分二义性文法缺点缺点1.文法书写限制大文法书写限制大2

53、.占用内存空间大占用内存空间大3.不规范、存在查不到的语法错误不规范、存在查不到的语法错误7.1.1 LR分析法的概述43434343(1)LR分析法的优缺点(2)LR分析器有三部分: 状态栈、分析表、控制程序(3)分析表的种类(4)补充说明(1) LR分析法的优缺点: 1) 适合文法类足够大,适用于所有上下文无关文法 2) 分析效率高 3) 报错及时 4) 可以自动生成 5) 手工实现工作量大45454545状态栈：放置分析状态栈：放置分析状态栈：放置分析状态栈：放置分析器状态和文法符号器状态和文法符号器状态和文法符号器状态和文法符号. .分析表：由两个矩阵组成，其功能是指示分析器的动作，

54、分析表：由两个矩阵组成，其功能是指示分析器的动作，分析表：由两个矩阵组成，其功能是指示分析器的动作，分析表：由两个矩阵组成，其功能是指示分析器的动作，是是是是移进移进移进移进还是还是还是还是规约规约规约规约，根据不同的文法类要采用不同，根据不同的文法类要采用不同，根据不同的文法类要采用不同，根据不同的文法类要采用不同的构造方法的构造方法的构造方法的构造方法. . 控制程序：执行分析表所规定的动作，对栈进行操作。控制程序：执行分析表所规定的动作，对栈进行操作。控制程序：执行分析表所规定的动作，对栈进行操作。控制程序：执行分析表所规定的动作，对栈进行操作。(2)LR分析器有三部分分析器有三部分

55、: 状态栈、分析表、控制程序状态栈、分析表、控制程序# #控制程序控制程序控制程序控制程序分析表分析表分析表分析表# #状状状状态栈态栈态栈态栈输输输输入串入串入串入串46464646(3)分析表的种类分析表的种类a) SLRa) SLR分析表分析表分析表分析表( (简单简单简单简单LRLR分析表分析表分析表分析表) ) b) LRb) LR分析表分析表分析表分析表( (规范规范规范规范LRLR分析表分析表分析表分析表) )构造简单构造简单构造简单构造简单, ,最易实现最易实现最易实现最易实现, ,大多数上下文无关文法都大多数上下文无关文法都大多数上下文无关文法都大多数上下文无关文法都可以

56、构造出可以构造出可以构造出可以构造出SLRSLR分析表分析表分析表分析表, ,所以具有所以具有所以具有所以具有较高的实用较高的实用较高的实用较高的实用价值。价值。价值。价值。使用使用使用使用SLRSLR分析表进行语法分析的分析器分析表进行语法分析的分析器分析表进行语法分析的分析器分析表进行语法分析的分析器叫叫叫叫SLRSLR分析器分析器分析器分析器适用文法类最大适用文法类最大适用文法类最大适用文法类最大,n,n个所有上下文无关文法都能个所有上下文无关文法都能个所有上下文无关文法都能个所有上下文无关文法都能构造出构造出构造出构造出LRLR分析表分析表分析表分析表, ,但其分析表体积太大但其

57、分析表体积太大但其分析表体积太大但其分析表体积太大. .暂时实暂时实暂时实暂时实用价值不大用价值不大用价值不大用价值不大. .47474747c) LALRc) LALR分析表分析表分析表分析表( (超前超前超前超前LRLR分析表分析表分析表分析表) ) 这种表适用的文法类及其实现上这种表适用的文法类及其实现上这种表适用的文法类及其实现上这种表适用的文法类及其实现上难易在上面难易在上面难易在上面难易在上面两种之间两种之间两种之间两种之间, ,在实用上很吸引人在实用上很吸引人在实用上很吸引人在实用上很吸引人. . 使用使用使用使用LALRLALR分析表进行语法分析的分析器叫分析表进行语法分析

58、的分析器叫分析表进行语法分析的分析器叫分析表进行语法分析的分析器叫LALRLALR分析器。分析器。分析器。分析器。例：例：例：例：ANIX-YACC ANIX-YACC 文法规则文件文法规则文件文法规则文件文法规则文件 YACCYACC源文件源文件源文件源文件 YACC YACC 某语言的某语言的某语言的某语言的 LALRLALR分析器分析器分析器分析器48481. 1.三种分析表对应三类文法三种分析表对应三类文法三种分析表对应三类文法三种分析表对应三类文法(4)几点说明几点说明2. 2.一个一个一个一个SLRSLR文法必定是文法必定是文法必定是文法必定是LALRLALR文法和文法和文法和文

59、法和LRLR文法文法文法文法3. 3.仅讨论仅讨论仅讨论仅讨论SLRSLR分析表的构造方法分析表的构造方法分析表的构造方法分析表的构造方法7.1.2 LR分析（1）逻辑结构（2） LR分析过程5050（1）逻辑结构）逻辑结构分分分分析析析析动动动动作作作作表表表表状状状状态态态态转转转转移移移移表表表表控控制制程程序序输入串：输入串：输入串：输入串：#a#a1 1 a a2 2 . a. ai i . . a an n # #S#S0 0x x1 1S S1 1x x2 2. . x xmmS SmmLRLR分析器分析器分析器分析器状态栈状态栈状态栈状态栈51515151 状态栈状态栈状态栈状

60、态栈: :S S0 0,S,S1 1,S,Smm 状态状态状态状态 S S0 0-初始状态初始状态初始状态初始状态 S Smm-栈顶状态栈顶状态栈顶状态栈顶状态栈顶状态概括了从分析开始到该状态的栈顶状态概括了从分析开始到该状态的栈顶状态概括了从分析开始到该状态的栈顶状态概括了从分析开始到该状态的全部分析历史和展望资料全部分析历史和展望资料全部分析历史和展望资料全部分析历史和展望资料. . 符号串符号串符号串符号串: : X X1 1X X2. 2. X Xmm 为从开始状态为从开始状态为从开始状态为从开始状态(S(S0 0) )到当前状态到当前状态到当前状态到当前状态(S(Smm) )所识

61、别的所识别的所识别的所识别的规范句型的活前缀规范句型的活前缀规范句型的活前缀规范句型的活前缀. .#S#S0 0x x1 1S S1 1x x2 2. . x xmmS SmmS S0 0S S1 1. . S Smm# x# x1 1x x2 2. . x xmm52525252规范句型：规范句型：规范句型：规范句型：通过规范规约得到的句型通过规范规约得到的句型通过规范规约得到的句型通过规范规约得到的句型. .规范句型前缀：规范句型前缀：规范句型前缀：规范句型前缀：将输入串的剩余部分与将输入串的剩余部分与将输入串的剩余部分与将输入串的剩余部分与其其其其连结起来就连结起来就连结起来就连结起来就

62、构成了规范句型构成了规范句型构成了规范句型构成了规范句型. . 如：如：如：如： x x1 1x x2 2. . x xmma ai i . . a an n为规范句型为规范句型为规范句型为规范句型 x x1 1x x2 2. . x xmm 为规范句型前缀为规范句型前缀为规范句型前缀为规范句型前缀 a ai i . . a an n为输入串的剩余部分为输入串的剩余部分为输入串的剩余部分为输入串的剩余部分活前缀：活前缀：活前缀：活前缀：若分析过程能够保证若分析过程能够保证若分析过程能够保证若分析过程能够保证栈中符号栈中符号栈中符号栈中符号均是均是均是均是规范句型规范句型规范句型规范句型的前缀的

63、前缀的前缀的前缀，则表示输入串已分析过的部分没有，则表示输入串已分析过的部分没有，则表示输入串已分析过的部分没有，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀语法错误，所以称为规范句型的活前缀语法错误，所以称为规范句型的活前缀语法错误，所以称为规范句型的活前缀. .规范句型的活前缀规范句型的活前缀规范句型的活前缀规范句型的活前缀: :对于句型对于句型对于句型对于句型tt，表示句柄表示句柄表示句柄表示句柄, ,如果如果如果如果=u=u1 1u u2 2uur r那么符号串那么符号串那么符号串那么符号串u u1 1u u2 2uui i(1ir)(1ir)即是句型即是句型即是

64、句型即是句型tt的活前缀的活前缀的活前缀的活前缀例：有文法例：有文法例：有文法例：有文法 ET | E+T | E-T ET | E+T | E-T Ti | (E) Ti | (E) 拓广文法拓广文法拓广文法拓广文法GG：SE# SE# ET | E+T | E-T ET | E+T | E-T Ti | (E) Ti | (E) 已知句型已知句型已知句型已知句型E-(i) #E-(i) #，求，求，求，求活前缀活前缀活前缀活前缀? ?E, E-, E-(, E-(i E, E-, E-(, E-(i 是句型是句型是句型是句型E-(i+i)# E-(i+i)# 的活前缀。的活前缀。的活前缀。

65、的活前缀。53S SE E# #E ET T- -( () )E ET Ti i54545454 分析表分析表分析表分析表是一个矩阵：是一个矩阵：是一个矩阵：是一个矩阵：行行行行-分析器的状态分析器的状态分析器的状态分析器的状态列列列列-文法符号文法符号文法符号文法符号状态状态状态状态符号符号符号符号E ET TF FS S0 0S S1 1S S2 2: :S Sn nGOTOGOTO表表表表a. a. 状态转移表状态转移表状态转移表状态转移表 (GOTO (GOTO表表表表) ) 55555555GOTOSGOTOSi-1i-1, x, xi i=S=Si i S Si-1 i-1

66、-当前状态当前状态当前状态当前状态( (栈顶状态栈顶状态栈顶状态栈顶状态) ) x xi i - - 新的栈顶符号新的栈顶符号新的栈顶符号新的栈顶符号 S Si -i - 新的栈顶状态新的栈顶状态新的栈顶状态新的栈顶状态( (状态转移状态转移状态转移状态转移) ) S Si i需要满足条件是需要满足条件是需要满足条件是需要满足条件是: : 若若若若X X1 1X X2 2. X. Xi-1i-1是由是由是由是由S S0 0到到到到S Si-1i-1所识别的规范句型的活前所识别的规范句型的活前所识别的规范句型的活前所识别的规范句型的活前缀缀缀缀, ,则则则则X X1 1X X2 2. X. Xi

67、 i是由是由是由是由S S0 0到到到到S Si i所识别的规范句型的活前缀所识别的规范句型的活前缀所识别的规范句型的活前缀所识别的规范句型的活前缀 #S#S0 0x x1 1S S1 1x x2 2. . x xi-1i-1S Si-1 i-1 x xi iS Si i状态状态状态状态符号符号符号符号E ET TF FS S0 0S S1 1S S2 2: :S Sn nGOTOGOTO表表表表56565656通过对有穷自动机的了解通过对有穷自动机的了解通过对有穷自动机的了解通过对有穷自动机的了解, ,我们可以看出我们可以看出我们可以看出我们可以看出: : 状态转移函数状态转移函数状态转移函

68、数状态转移函数GOTOGOTO是定义了一个以文法符是定义了一个以文法符是定义了一个以文法符是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法号集为字母表的有穷自动机，该自动机识别文法号集为字母表的有穷自动机，该自动机识别文法号集为字母表的有穷自动机，该自动机识别文法所有所有所有所有规范句型的活前缀规范句型的活前缀规范句型的活前缀规范句型的活前缀。M=(S, B, GOTO, SM=(S, B, GOTO, S0 0, Z), Z)S S0 0S S1 1S Si-1i-1S S2 2S Si iX X1 1X X2 2X Xi-1i-1X Xi i57575757b. b. 分析动

69、作表分析动作表分析动作表分析动作表(ACTION(ACTION表表表表) ) Sn n状态状态状态状态s s输入符号输入符号输入符号输入符号a ai+*()#S0 0S1 1S2 2:ACTION表表ACTIONSi i,a=动作分析动作分析 aBt t58585858分析动作：分析动作：分析动作：分析动作：1)1)移进移进移进移进(shift) (shift) ACTIONS ACTIONSi i,a= ,a= S Sj j 动作：将动作：将动作：将动作：将a a推进栈，并设置新的栈顶状态推进栈，并设置新的栈顶状态推进栈，并设置新的栈顶状态推进栈，并设置新的栈顶状态S Sj j S Sj j

70、=GOTOS=GOTOSi i,a,a，将指针指向下一个输入符号，将指针指向下一个输入符号，将指针指向下一个输入符号，将指针指向下一个输入符号2)2)规约规约规约规约(reduce) (reduce) ACTIONS ACTIONSi i,a=r,a=rd d d d：文法规则编号：文法规则编号：文法规则编号：文法规则编号 (d) A (d) A 动作：将符号串动作：将符号串动作：将符号串动作：将符号串(假定长度为假定长度为假定长度为假定长度为n)n)连同状态从栈内弹出把连同状态从栈内弹出把连同状态从栈内弹出把连同状态从栈内弹出把A A推推推推进栈，并设置新的栈顶状态进栈，并设置新的栈顶状态进

71、栈，并设置新的栈顶状态进栈，并设置新的栈顶状态S Sj j , S, Sj j=GOTOS=GOTOSi-ni-n,A,A3)3)接受接受接受接受(accept) (accept) ACTIONS ACTIONSi i,#=accept,#=accept4)4)出错出错出错出错(error) (error) ACTIONS ACTIONSi i,a=error,a=error59595959 控制程序控制程序控制程序控制程序:(Driver Routine) :(Driver Routine) 1) 1) 根据根据根据根据栈顶状态栈顶状态栈顶状态栈顶状态和和和和现行输入符号现行输入符号现行输入

72、符号现行输入符号，查分析动作，查分析动作，查分析动作，查分析动作表表表表(ACTION(ACTION表表表表) )，执行有分析表所规定的操作；，执行有分析表所规定的操作；，执行有分析表所规定的操作；，执行有分析表所规定的操作； 2) 2) 并根据并根据并根据并根据GOTOGOTO表设置新的栈顶状态表设置新的栈顶状态表设置新的栈顶状态表设置新的栈顶状态( (即实现状即实现状即实现状即实现状态转移态转移态转移态转移) )60606060例：文法例：文法例：文法例：文法GE GE (1)E:=E+T (1)E:=E+T (2)E:=T (2)E:=T (3)T :=T*F (3)T :=T*F (4

73、)T:=F (4)T:=F (5)F:=(E) (5)F:=(E) (6)F:=i(6)F:=i（2） LR分析过程分析过程该文法是该文法是该文法是该文法是SLRSLR文法文法文法文法, ,故可以构造出故可以构造出故可以构造出故可以构造出SLRSLR分析表分析表分析表分析表(ACTION(ACTION表表表表和和和和GOTOGOTO表表表表) )ACTION表 GOTO表文法GE ：(1)E:=E+T (2)E:=T (3)T :=T*F (4)T:=F (5)F:=(E) (6)F:=i文法符号状态i+*()#ETF0(S0)S5S41231(S1)S6ACCEPT2(S2)R2S7R2R2

74、3(S3)R4R4R4R4 4(S4)S5S48235(S5)R6R6R6R66(S6)S5S4937(S7)S5S4108(S8)S6S119(S9)R1S7R1R110(S10)R3R3R3R311(S11)R5R5R5R56262626211(S11(S1111) )10(S10(S1010) ) 7 79(S9(S9 9) ) 11 11 6 68(S8(S8 8) ) 4 4 5 5 10 107(S7(S7 7) ) 4 4 5 5 3 3 9 96(S6(S6 6) )5(S5(S5 5) ) 4 4 5 5 3 3 2 2 8 8 4(S4(S4 4) )3(S3(S3 3)

75、) 7 72(S2(S2 2) ) 6 61(S1(S1 1) ) 4 4 5 5 3 3 2 2 1 10(S0(S0 0) ) ) ) ( ( * * + + i i F F T T E EGOTOGOTO表表表表 ACTIONACTION表表表表文法符号文法符号文法符号文法符号状态状态状态状态状态状态状态状态若移入：若移入：若移入：若移入：i i为状态为状态为状态为状态若规约：若规约：若规约：若规约：i i为产生式编号为产生式编号为产生式编号为产生式编号文法文法文法文法GE GE ：(1)E:=E+T (2)E:=T (3)T :=T*F (1)E:=E+T (2)E:=T (3)T :

76、=T*F (4)T:=F (5)F:=(E) (6)F:=i (4)T:=F (5)F:=(E) (6)F:=iB Bn nB Bt t63636363ACTION ACTION 表表表表GOTO GOTO 表表表表输入符号输入符号输入符号输入符号状态状态状态状态文法文法文法文法GE GE (1)E:=E+T (1)E:=E+T (2)E:=T (2)E:=T (3)T :=T*F (3)T :=T*F (4)T:=F (4)T:=F (5)F:=(E) (5)F:=(E) (6)F:=i(6)F:=iS Si i：移入，：移入，：移入，：移入，i i为状态为状态为状态为状态R Ri i：规约

77、，：规约，：规约，：规约，i i为产生式编号为产生式编号为产生式编号为产生式编号64646464分析过程分析过程： i*i+i步骤步骤步骤步骤状态栈状态栈状态栈状态栈符号符号符号符号输入串输入串输入串输入串动作动作动作动作 1 10 0i*i+i#i*i+i#初始化初始化初始化初始化 2 20i50i5i i*i+i#*i+i#S S 3 30F30F3F F*i+i#*i+i#R6R6 4 40T20T2T T*i+i#*i+i#R4R4 5 50T2*70T2*7T*T* i+i# i+i#S S 6 60T2*7i50T2*7i5T*iT*i +i# +i#S S 7 70T2*7F1

78、00T2*7F10 T*FT*F +i# +i#R6R6GOTOGOTO表表表表 ACTIONACTION表表表表11(S11(S1111) )10(S10(S1010) ) 7 79(S9(S9 9) ) 11 11 6 68(S8(S8 8) ) 4 4 5 5 10 107(S7(S7 7) ) 4 4 5 5 3 3 9 96(S6(S6 6) )5(S5(S5 5) ) 4 4 5 5 3 3 2 2 8 8 4(S4(S4 4) )3(S3(S3 3) ) 7 72(S2(S2 2) ) 6 61(S1(S1 1) ) 4 4 5 5 3 3 2 2 1 10(S0(S0 0) )

79、 ) ) ( ( * * + + i i F F T T E E文法符号文法符号文法符号文法符号状态状态状态状态 11 110E1+6i50E1+6i5#E+i#E+i # #S S 12 120E1+6F30E1+6F3#E+F#E+F # #R6R6 13 130E1+6T90E1+6T9#E+T#E+T # #R4R4 14 140E10E1#E#E # #R1R1 15 15 #E #E Accept Accept 9 90E10E1#E#E +i# +i#R2R2 10 100E1+60E1+6#E+#E+ i# i#S S 8 80T20T2#T#T +i# +i#R3R3GOTO

80、GOTO表表表表 ACTIONACTION表表表表11(S11(S1111) )10(S10(S1010) ) 7 79(S9(S9 9) ) 11 11 6 68(S8(S8 8) ) 4 4 5 5 10 107(S7(S7 7) ) 4 4 5 5 3 3 9 96(S6(S6 6) )5(S5(S5 5) ) 4 4 5 5 3 3 2 2 8 8 4(S4(S4 4) )3(S3(S3 3) ) 7 72(S2(S2 2) ) 6 61(S1(S1 1) ) 4 4 5 5 3 3 2 2 1 10(S0(S0 0) ) ) ) ( ( * * + + i i F F T T E E

81、文法符号文法符号文法符号文法符号状态状态状态状态66666666由分析过程可以看到由分析过程可以看到由分析过程可以看到由分析过程可以看到: :(1) (1) 每次规约总是每次规约总是每次规约总是每次规约总是规约规约规约规约当前句型的当前句型的当前句型的当前句型的句柄句柄句柄句柄，是规范规约，可以看到语，是规范规约，可以看到语，是规范规约，可以看到语，是规范规约，可以看到语法树法树法树法树( (算符优先是规约最左素短语算符优先是规约最左素短语算符优先是规约最左素短语算符优先是规约最左素短语) )E EE ET T+ +T TT T * *F FF Fi ii iF Fi i8 87 75 56

82、64 43 32 21 1(2) (2) 分析的每一步栈内符号串均是分析的每一步栈内符号串均是分析的每一步栈内符号串均是分析的每一步栈内符号串均是规范句型的活前缀规范句型的活前缀规范句型的活前缀规范句型的活前缀，与输入串的，与输入串的，与输入串的，与输入串的剩余部分构成规范句型剩余部分构成规范句型剩余部分构成规范句型剩余部分构成规范句型. .7.1.3 构造SLR分析表67676767构造构造构造构造LRLR分析器的关键时构造其分析表分析器的关键时构造其分析表分析器的关键时构造其分析表分析器的关键时构造其分析表构造LR分析表的方法是:（1）根据文法构造识别规范句型活前缀的有穷自动机DFA（2）

83、由DFA构造SLR分析表68681. 构造构造DFA(1) DFA是一个五元式是一个五元式M=(S, B, GOTO, SM=(S, B, GOTO, S0 0, Z), Z)S S：有穷状态集：有穷状态集：有穷状态集：有穷状态集在此具体情况下，在此具体情况下，在此具体情况下，在此具体情况下，S=LR(0)S=LR(0)项目集规范族项目集规范族项目集规范族项目集规范族LR(0)LR(0)。项目集规范族项目集规范族项目集规范族项目集规范族：其元素是由项目所构成的集合：其元素是由项目所构成的集合：其元素是由项目所构成的集合：其元素是由项目所构成的集合. .B B：文法字汇表：文法字汇表：文法字汇

84、表：文法字汇表S S0 0：初始状态：初始状态：初始状态：初始状态GOTO:GOTO:状态转移函数状态转移函数状态转移函数状态转移函数 GOTOSGOTOSi i,X=S,X=Sj j S Si i ,S,Sj jS SS Si i ,S,Sj j为项目集合为项目集合为项目集合为项目集合 X XB Bn nB Bt t表示当前状态表示当前状态表示当前状态表示当前状态S Si i面临文法符号为面临文法符号为面临文法符号为面临文法符号为X X时，应将状态转移到时，应将状态转移到时，应将状态转移到时，应将状态转移到 S Sj jZ Z：终态集合：终态集合：终态集合：终态集合 Z=S-S Z=S-S0

85、 0 即除即除即除即除S S0 0以外，其余全部是终态以外，其余全部是终态以外，其余全部是终态以外，其余全部是终态696969691）确定确定S集合，即集合，即LR（0）项目集规项目集规范族范族，同时确定，同时确定S02）确定确定状态转移函数状态转移函数GOTO构造构造DFA方法：方法：70707070（2）构造）构造LR（0）的方法）的方法LR(0)LR(0)是是是是DFADFA的状态集，其中每个状态又都是的状态集，其中每个状态又都是的状态集，其中每个状态又都是的状态集，其中每个状态又都是项目项目的集合的集合的集合的集合项目项目:文法文法文法文法GG的每个产生式的每个产生式的每个产生式的

86、每个产生式( (规则规则规则规则) )的右部添加一个圆点就构的右部添加一个圆点就构的右部添加一个圆点就构的右部添加一个圆点就构成一个项目。成一个项目。成一个项目。成一个项目。例例例例: :产生式产生式产生式产生式:AXYZ :AXYZ 项项项项目目目目: A.XYZ : A.XYZ AX.YZ AX.YZ AXY.Z AXY.Z AXYZ. AXYZ. 产生式产生式产生式产生式:A:A 项项项项目目目目: A. : A. 项目的直观意义项目的直观意义项目的直观意义项目的直观意义: :指明在分过程中指明在分过程中指明在分过程中指明在分过程中的某一时刻已经的某一时刻已经的某一时刻已经的某一时刻

87、已经规约的部分和等规约的部分和等规约的部分和等规约的部分和等待规约部分。待规约部分。待规约部分。待规约部分。71717171. . 将文法扩充将文法扩充将文法扩充将文法扩充构造构造构造构造LR(0)LR(0)文法的方法文法的方法文法的方法文法的方法( (三步三步三步三步) )目的：使构造出来的分析表只有一个接受状态目的：使构造出来的分析表只有一个接受状态目的：使构造出来的分析表只有一个接受状态目的：使构造出来的分析表只有一个接受状态, ,这是这是这是这是为了实现的方便。为了实现的方便。为了实现的方便。为了实现的方便。方法：修改文法，使识别符号的规则只有一条方法：修改文法，使识别符号的规则只有

88、一条方法：修改文法，使识别符号的规则只有一条方法：修改文法，使识别符号的规则只有一条GE GE EEEE 拓广拓广拓广拓广GE GE EE EE EEEE L(G(E)=L(GE)L(G(E)=L(GE)72727272. . 根据文法列出所有的项目根据文法列出所有的项目根据文法列出所有的项目根据文法列出所有的项目. . 将有关项目组合成集合，即将有关项目组合成集合，即将有关项目组合成集合，即将有关项目组合成集合，即DFADFA中的状态；中的状态；中的状态；中的状态；所有状态再组合成一个集合，即所有状态再组合成一个集合，即所有状态再组合成一个集合，即所有状态再组合成一个集合，即LRLR（0

90、 EE (4) TF (1)(1) EE+T (5) F(E) EE+T (5) F(E) (2)(2) ET (6) Fi ET (6) Fi (3)(3) TT*F TT*F2 2列出文法的所有项目列出文法的所有项目列出文法的所有项目列出文法的所有项目(1)(1)E.E E.E (2)(2)EE. EE. (3) E.E+T (3) E.E+T (4) EE.+T (4) EE.+T (5) EE+.T (5) EE+.T (6) EE+T. (6) EE+T. (7) E.T (7) E.T (8) ET. (8) ET. (9) T.T*F (9) T.T*F (10) TT.*F (

91、10) TT.*F (11)TT*.F (11)TT*.F (12)TT*F. (12)TT*F. (13)T.F (13)T.F (14)TF. (14)TF. (15)F.(E) (15)F.(E) (16)F(.E) (16)F(.E) (17)F(E.) (17)F(E.) (18)F(E). (18)F(E). (19)F.i (19)F.i (20) Fi.(20) Fi.747474743 3 将有关项目组成项目集将有关项目组成项目集将有关项目组成项目集将有关项目组成项目集, ,所有项目集构成的集合即为所有项目集构成的集合即为所有项目集构成的集合即为所有项目集构成的集合即为LR(

92、0)LR(0)为实现这一步，先定义：为实现这一步，先定义：为实现这一步，先定义：为实现这一步，先定义：项目集闭包项目集闭包项目集闭包项目集闭包closure closure 状态转移函数状态转移函数状态转移函数状态转移函数GOTOGOTO例例例例:GE :GE 令令令令I=E.E I=E.E closure(I)=E.E, E.E+T, E.T, T.T*F, T.F, closure(I)=E.E, E.E+T, E.T, T.T*F, T.F, F.(E), F.i F.(E), F.i 75757575A.A.项目集闭包项目集闭包项目集闭包项目集闭包closureclosure的定义和

93、计算的定义和计算的定义和计算的定义和计算: : 令令令令I I是文法是文法是文法是文法GG的任一项目集合，定义的任一项目集合，定义的任一项目集合，定义的任一项目集合，定义closure(I)closure(I)为项目集合为项目集合为项目集合为项目集合I I的闭包，可用一个过程来定义并计算的闭包，可用一个过程来定义并计算的闭包，可用一个过程来定义并计算的闭包，可用一个过程来定义并计算closure(I)closure(I)。 Procedure closure(I); Procedure closure(I); begin begin 将属于将属于将属于将属于I I的项目加入的项目加入的项目加入

94、的项目加入closure(I); closure(I); repeat repeat for closure(I) for closure(I)中的每个项目中的每个项目中的每个项目中的每个项目A.B(BA.B(BB Bn n) do ) do 将将将将B.r(rB.r(rB* )B* )加入加入加入加入closure(I) closure(I) until closure(I) until closure(I)不再增大不再增大不再增大不再增大 endend例例例例:GE :GE 令令令令I=E.E I=E.E closure(I)=E.E, E.E+T, E.T, T.T*F, T.F, cl

95、osure(I)=E.E, E.E+T, E.T, T.T*F, T.F, F.(E), F.i F.(E), F.i 76767676B B 状态转移函数状态转移函数状态转移函数状态转移函数GOTOGOTO的定义的定义的定义的定义: :GOTO(I,X)=closure(J) GOTO(I,X)=closure(J) I I：项目集合：项目集合：项目集合：项目集合 X X：文法符号，：文法符号，：文法符号，：文法符号，X XB B J J：项目集合：项目集合：项目集合：项目集合 J=J=任何形如任何形如任何形如任何形如AX.AX.的项目的项目的项目的项目| A.X| A.XI I closu

96、re(J):closure(J):项目集项目集项目集项目集J J的闭包仍是项目集合的闭包仍是项目集合的闭包仍是项目集合的闭包仍是项目集合所以所以所以所以,GOTO(I,X)=closure(J),GOTO(I,X)=closure(J)的直观意义是的直观意义是的直观意义是的直观意义是: : 它规定了识别文法规范句型活前缀的它规定了识别文法规范句型活前缀的它规定了识别文法规范句型活前缀的它规定了识别文法规范句型活前缀的DFADFA从从从从状态状态状态状态I( I(项目集项目集项目集项目集) )出发出发出发出发, ,经过经过经过经过X X弧所应该到达的状态弧所应该到达的状态弧所应该到达的状态弧所应

97、该到达的状态( (项目集合项目集合项目集合项目集合) ) 77777777例例. I=EE. , EE.+T 求求GOTO(I , + )=? GOTO(I , +)=closure(J) J=EE+.T GOTO(I , +)=EE+.T , T.T*F , T.F , F.(E) , F.i 78787878LR(0)LR(0)项目集规范族的构造算法项目集规范族的构造算法项目集规范族的构造算法项目集规范族的构造算法: :GLR(0) GLR(0) Procedure ITEMSETS(G); Procedure ITEMSETS(G); begin begin LR(0):=closure

98、(E.E); LR(0):=closure(E.E); repeat repeat for LR(0) for LR(0)中的每个项目集中的每个项目集中的每个项目集中的每个项目集I I和和和和GG的每个符号的每个符号的每个符号的每个符号X do X do if GOTO(I , X) if GOTO(I , X)非空非空非空非空, ,且不属于且不属于且不属于且不属于LR(0) LR(0) then then 把把把把GOTO(I , X)GOTO(I , X)放入放入放入放入LR(0)LR(0)中中中中 until LR(0) until LR(0)不再增大不再增大不再增大不再增大 enden

99、d79797979例例例例. .求求求求GEGE的的的的LR(0) LR(0) B=E, T, F, I, +, *, (, ) B=E, T, F, I, +, *, (, ) GEGE共有共有共有共有2020个项目个项目个项目个项目 LR(0)=ILR(0)=I0 0,I ,I1 1,I ,I2 2,I,I1111 有有有有1212个项目组成个项目组成个项目组成个项目组成: : I I0 0: : E.E E.E E.E+T E.E+T E.T E.T T.T*F T.T*F T.F T.F F.(E) F.(E) F.i F.i I I1 1: : EE. EE. EE.+TEE.+TC

100、losure(B.B)=IClosure(B.B)=I0 0GOTO(IGOTO(I0 0,E)=closure(EE. ,E)=closure(EE. EE.+T) EE.+T) =I =I1 1(0) EE (4) TF (0) EE (4) TF (1)(1) EE+T (5) F(E) EE+T (5) F(E) (2)(2) ET (6) Fi ET (6) Fi (3)(3) TT*F TT*F80808080I I2 2: :ET. GOTO(IET. GOTO(I0 0,T)=closure(ET. TT.*F)= I,T)=closure(ET. TT.*F)= I2 2 T

101、T.*F TT.*F I I3 3: :TFTF. . GOTO(I GOTO(I0 0,F)=closure(TF.)= I,F)=closure(TF.)= I3 3I I4 4: :F(.E) GOTO(IF(.E) GOTO(I0 0,()=closure(F(.E)= I,()=closure(F(.E)= I4 4 E E. .E+T E+T E E . .T T T.T*F T.T*F T.F T.F F.(E) F.(E) F.i F.i I I5 5: :FiFi. . GOTO(I GOTO(I0 0,i)=closure(Fi.)= I,i)=closure(Fi.)=

102、I5 5 GOTO(I GOTO(I0 0,*)= ,*)= GOTO(I GOTO(I0 0,+)= ,+)= GOTO(I GOTO(I0 0,)=,)=I I0 0: E.E : E.E E.E+T E.E+T E.T E.T T.T*F T.T*F T.F T.F F.(E) F.(E) F.i F.i 81818181I I6 6: :EE+.T GOTO(IEE+.T GOTO(I1 1,+)=closure(EE+.T)= I,+)=closure(EE+.T)= I6 6T.T*F GOTO(IT.T*F GOTO(I1 1, ,其他符号其他符号其他符号其他符号) )为空为空为

103、空为空 T.F T.F F.(E) F.(E) F.i F.i I I7 7: :TT*.F TT*.F GOTO(IGOTO(I2 2,*)=closure(TT*.F)= I,*)=closure(TT*.F)= I7 7F.(E) F.(E) GOTO(IGOTO(I2 2, ,其他符号其他符号其他符号其他符号) )为空为空为空为空 F.i F.i GOTO(IGOTO(I3 3, ,其他符号其他符号其他符号其他符号) )为空为空为空为空 I I1 1: EE. : EE. EE.+T EE.+TI I2 2: ET. : ET. TT.*F TT.*F82828282I I8 8: :

104、F(E.) F(E.) GOTO(IGOTO(I4 4,F)=closure(F(E.),EE.+T)= I,F)=closure(F(E.),EE.+T)= I8 8 EE.+T EE.+T GOTO(IGOTO(I4 4,T)= I,T)= I2 2 LR(0) LR(0) GOTO(IGOTO(I4 4,F)= I,F)= I3 3 LR(0) LR(0) GOTO(IGOTO(I4 4,()= I,()= I4 4 LR(0) LR(0) GOTO(IGOTO(I4 4,i)= I,i)= I5 5 LR(0) LR(0) GOTO(IGOTO(I4 4,+)= ,+)= GOTO(I

105、GOTO(I4 4,*)= ,*)= GOTO(IGOTO(I4 4,)= GOTO(I,)= GOTO(I5 5, ,其他符号其他符号其他符号其他符号)= )= I I9 9: :EE+T. EE+T. GOTO(IGOTO(I6 6,T)=closure(EE+T.,TT.*F)= I,T)=closure(EE+T.,TT.*F)= I9 9 ET.*F ET.*F GOTO(IGOTO(I6 6,F)= I,F)= I3 3 GOTO(IGOTO(I6 6,()= I,()= I4 4GOTO(IGOTO(I6 6,i)= I,i)= I5 5I I4 4: :F(.E) EF(.E)

106、 E. .E+T E+T E E . .T T.T*F T T.T*F T.FT.F F.(E) F.(E) F.iF.i83838383I I1010:TT*F. :TT*F. GOTO(IGOTO(I7 7,T)=closure(TT*F .)= I,T)=closure(TT*F .)= I10 10 GOTO(IGOTO(I7 7,()= I,()= I4 4 GOTO(IGOTO(I7 7,i)= I,i)= I5 5I I1111:F(E). :F(E). GOTO(IGOTO(I8 8,)=closure(F(E) .)= I,)=closure(F(E) .)= I11 11

107、GOTO(IGOTO(I7 7,()= I,()= I4 4 GOTO(IGOTO(I7 7,i)= I,i)= I5 5求完所有求完所有求完所有求完所有I Ii i的后继的后继的后继的后继GOTO(IGOTO(I8 8,+)= I,+)= I6 6GOTO(IGOTO(I9 9,*)= I,*)= I7 7 GOTO(IGOTO(I1010, ,所有符号所有符号所有符号所有符号)=, GOTO(I)=, GOTO(I1111, ,所有符号所有符号所有符号所有符号)= )= 84848484（3）构造）构造DFA M=(S, B, GOTO, SM=(S, B, GOTO, S0 0, Z)

108、, Z) S =IS =I0 0, I, I1 1, I, I2 2, , I, , I1111=LR(0) =LR(0) B =+, *, i, (, ), E, T, F B =+, *, i, (, ), E, T, F GOTO(IGOTO(Imm , X)= I , X)= Imm S S0 0=I=I0 0Z=S-IZ=S-I0 0=I=I1 1, I, I2 2, , I, , I1111 MM的图解表示如下的图解表示如下的图解表示如下的图解表示如下: :85858585I I0 0I I5 5I I2 2I I4 4I I3 3I I1 1I I1111I I8 8I I6 6

109、I I1010I I7 7I I9 9starstart tE E+ + +i iF F( (T TT TF F( (i iF F( (i iE E( (* * *) )+ +i iF F86868686关于自动机的说明关于自动机的说明关于自动机的说明关于自动机的说明: :1 1除除除除I0I0以外以外以外以外, ,其余状态都是活前缀的识别状态其余状态都是活前缀的识别状态其余状态都是活前缀的识别状态其余状态都是活前缀的识别状态, ,从从从从I I0 0到每一状态到每一状态到每一状态到每一状态的每条路径都识别和接受一个规范句型的活前缀的每条路径都识别和接受一个规范句型的活前缀的每条路径都识别和接

110、受一个规范句型的活前缀的每条路径都识别和接受一个规范句型的活前缀如对文法句子如对文法句子如对文法句子如对文法句子i+i*i i+i*i 进行规范规约，进行规范规约，进行规范规约，进行规范规约，所得到的所得到的所得到的所得到的规范句型规范句型规范句型规范句型的的的的活前缀活前缀活前缀活前缀都可都可都可都可以由该自动机识别以由该自动机识别以由该自动机识别以由该自动机识别, ,如如如如: : I I0 0II3 3 F(+i*i) F(+i*i) I I0 0II2 2 T(+i*i) T(+i*i) I I0 0II1 1 识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀识别规范句

111、型的活前缀E(+i*i) E(+i*i) I I0 0II6 6 识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀E+(i*i) E+(i*i) I I0 0II7 7 识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀E+T*(i) E+T*(i) I I0 0II9 9 识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀E+T(*i) E+T(*i) I I0 0II1010 识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀识别规范句型的活前缀E+T*FE+T*FE EE ET T+ +

112、T TT T * *F FF Fi ii i8 85 5F Fi i7 74 43 32 21 1(0) EE (3) TT*F (6) Fi (0) EE (3) TT*F (6) Fi (1)(1) EE+T (4) TF EE+T (4) TF(2)(2) ET (5) F(E) ET (5) F(E)6 6878787872 2要求状态中每个项目对该状态能识别的活前缀都要求状态中每个项目对该状态能识别的活前缀都要求状态中每个项目对该状态能识别的活前缀都要求状态中每个项目对该状态能识别的活前缀都有效有效有效有效. . 有效项目定义有效项目定义有效项目定义有效项目定义: :若项目若项目若

113、项目若项目A A 1 1 1 1 .2 2，对活前缀，对活前缀，对活前缀，对活前缀1 1 1 1 有效，则其条件是存在规范推导有效，则其条件是存在规范推导有效，则其条件是存在规范推导有效，则其条件是存在规范推导 E EAw Aw 1 1 1 1 2 2 w w 注意：注意：注意：注意：项目中圆点前的符号串成为活前缀的后缀项目中圆点前的符号串成为活前缀的后缀项目中圆点前的符号串成为活前缀的后缀项目中圆点前的符号串成为活前缀的后缀 * * *888888883 3有效项目能预测分析的下一步动作：有效项目能预测分析的下一步动作：有效项目能预测分析的下一步动作：有效项目能预测分析的下一步动作： EE+

114、T. EE+T. 表示已将输入串规约为表示已将输入串规约为表示已将输入串规约为表示已将输入串规约为E+T,E+T,下一步应下一步应下一步应下一步应该将该将该将该将E+TE+T规约为规约为规约为规约为E E E E (E)(E)(E+T) (E+T) TT.*F TT.*F 表示已将输入串规约为表示已将输入串规约为表示已将输入串规约为表示已将输入串规约为T,T,下一步动作下一步动作下一步动作下一步动作是移进输入符号是移进输入符号是移进输入符号是移进输入符号* *注意：注意：注意：注意：经移进或规约后经移进或规约后经移进或规约后经移进或规约后, ,在栈内仍是规范句型的活前缀在栈内仍是规范句型的

115、活前缀在栈内仍是规范句型的活前缀在栈内仍是规范句型的活前缀898989894 4 DFADFA中的状态中的状态中的状态中的状态, ,既代表了分析历史又提供了展望信息既代表了分析历史又提供了展望信息既代表了分析历史又提供了展望信息既代表了分析历史又提供了展望信息每条规范句型的活前缀都代表了一个确定的每条规范句型的活前缀都代表了一个确定的每条规范句型的活前缀都代表了一个确定的每条规范句型的活前缀都代表了一个确定的的规范规约过程的规范规约过程的规范规约过程的规范规约过程, ,故有状态可以代表分析历史故有状态可以代表分析历史故有状态可以代表分析历史故有状态可以代表分析历史. . 由于状态中的项目都

116、是有效项目由于状态中的项目都是有效项目由于状态中的项目都是有效项目由于状态中的项目都是有效项目, ,所以提供了所以提供了所以提供了所以提供了下一步可能采取的动作下一步可能采取的动作下一步可能采取的动作下一步可能采取的动作. .历史历史历史历史+ +展望展望展望展望+ +实现实现实现实现句柄句柄句柄句柄90909090（2 2）由）由）由）由DFADFA构造构造构造构造SLRSLR分析表分析表分析表分析表* GOTO* GOTO表在求表在求表在求表在求LRLR（0 0）时已求出）时已求出）时已求出）时已求出11(S11(S1111) )10(S10(S1010) ) 7 79(S9(S9 9

117、) ) 11 11 6 68(S8(S8 8) ) 4 4 5 5 10 107(S7(S7 7) ) 4 4 5 5 3 3 9 96(S6(S6 6) )5(S5(S5 5) ) 4 4 5 5 3 3 2 2 8 8 4(S4(S4 4) )3(S3(S3 3) ) 7 72(S2(S2 2) ) 6 61(S1(S1 1) ) 4 4 5 5 3 3 2 2 1 10(S0(S0 0) ) ) ) ( ( * * + + i i F F T T E EGOTOGOTO表表表表文法符号文法符号文法符号文法符号状态状态状态状态91919191设设设设k k为状态编号为状态编号为状态编号为状

118、态编号,E,E为原文法识别符号，为原文法识别符号，为原文法识别符号，为原文法识别符号， EE为扩充文法识别符号为扩充文法识别符号为扩充文法识别符号为扩充文法识别符号* * 求求求求ACTIONACTION表表表表1 1、求出文法每个非终结符的、求出文法每个非终结符的、求出文法每个非终结符的、求出文法每个非终结符的FOLLOWFOLLOW集合集合集合集合2 2、若项目、若项目、若项目、若项目ApAp.aq aq k,k,且且且且a a Bt,Bt,则置则置则置则置 ACTIONk,a=S ( ACTIONk,a=S (移进）移进）移进）移进）929292923 3、若项目、若项目、若项目、若项目

119、ApAp.k, k, 那么对输入符号那么对输入符号那么对输入符号那么对输入符号a, a,若若若若 a aFOLLOW(A),FOLLOW(A),则置则置则置则置ACTIONk,a=ACTIONk,a=r rj j 其中其中其中其中ApAp为文法为文法为文法为文法GG的第的第的第的第j j个产生式。个产生式。个产生式。个产生式。4 4、若项目、若项目、若项目、若项目EEEE.k, k, 则置则置则置则置 ACTION k , ACTION k , # # = =ACCEPTACCEPT5 5、ACTIONACTION表中不能用步骤表中不能用步骤表中不能用步骤表中不能用步骤2424填入信息的填入信

120、息的填入信息的填入信息的空白格，均置空白格，均置空白格，均置空白格，均置ERRORERROR93939393在状态中可有三种类型的项目在状态中可有三种类型的项目在状态中可有三种类型的项目在状态中可有三种类型的项目, ,其中只有两种有移其中只有两种有移其中只有两种有移其中只有两种有移进或规约动作进或规约动作进或规约动作进或规约动作: :A .aA .a a aB Bt t 移进项目移进项目移进项目移进项目分析动作分析动作分析动作分析动作: :移进移进移进移进 A . A . 规约项目规约项目规约项目规约项目分析动作分析动作分析动作分析动作: :规约规约规约规约 A .BA .B B BB

121、 Bn n 待约项目待约项目待约项目待约项目无动作无动作无动作无动作根据上述算法根据上述算法根据上述算法根据上述算法, ,可以构造出文法可以构造出文法可以构造出文法可以构造出文法GEGE的的的的ACTIONACTION94949494对文法对文法对文法对文法GEGEk=2(Ik=2(I2 2) ) 有效项目有效项目有效项目有效项目 ET. ET. TT.*F TT.*F FOLLOW(E)=#, +, )FOLLOW(E)=#, +, )k=1(Ik=1(I1 1) ) EE. EE. EE.+T EE.+T FOLLOW(E)=#FOLLOW(E)=#k=0(Ik=0(I0 0) ) E.

122、E E.E E.E+T E.E+T E.T E.T T.T*F T.T*F T.F T.F F.(E) F.(E) F.i F.i 根据算法造出的根据算法造出的根据算法造出的根据算法造出的ACTIONACTION表为表为表为表为: :959595954 4状态状态状态状态s s输入符号输入符号输入符号输入符号a ai i* *( () )# #0 0 1 12 23 3 ACTIONACTION表表表表5 56 67 78 89 910101111S S5 5S S6 6S S7 7r r2 2r r2 2r r2 2accpetaccpetS S4 4+ +96969696两点说明两点说明两

123、点说明两点说明: :1. 1. 由由由由DFADFA构造出的构造出的构造出的构造出的SLRSLR分析表分析表分析表分析表, ,在造表示在造表示在造表示在造表示, ,我们我们我们我们只需向前看一个符号就能确定分析的动作是移只需向前看一个符号就能确定分析的动作是移只需向前看一个符号就能确定分析的动作是移只需向前看一个符号就能确定分析的动作是移进还是规约进还是规约进还是规约进还是规约. .所以所以所以所以SLR(1)SLR(1)分析表简称分析表简称分析表简称分析表简称SLRSLR分析表分析表分析表分析表使用使用使用使用SLRSLR分析表的分析器叫分析表的分析器叫分析表的分析器叫分析表的分析器叫

124、SLRSLR分析器分析器分析器分析器. . 2. 2. 对文法对文法对文法对文法G,G,若使用上述算法若使用上述算法若使用上述算法若使用上述算法, ,所造出的分析表所造出的分析表所造出的分析表所造出的分析表具有多重定义入口具有多重定义入口具有多重定义入口具有多重定义入口, ,分析动作就不唯一分析动作就不唯一分析动作就不唯一分析动作就不唯一, ,则文法则文法则文法则文法 GG就不是就不是就不是就不是SLRSLR的需要用别的方法来构造分析表的需要用别的方法来构造分析表的需要用别的方法来构造分析表的需要用别的方法来构造分析表. . 第五章语法分析小结97979797语法分析方法语法分析方法语法分

125、析方法语法分析方法: :自顶向上分析法自顶向上分析法自顶向上分析法自顶向上分析法 Z Z S S+ +自顶向上分析法自顶向上分析法自顶向上分析法自顶向上分析法 S SZ Z+ +S SLZLZ( (一一一一) ) 自顶向下分析自顶向下分析自顶向下分析自顶向下分析1 1 概述自顶向下分析的一般过程概述自顶向下分析的一般过程概述自顶向下分析的一般过程概述自顶向下分析的一般过程存在问题存在问题存在问题存在问题左递归问题左递归问题左递归问题左递归问题回溯问题回溯问题回溯问题回溯问题消除左递归的方法消除左递归的方法消除左递归的方法消除左递归的方法无回溯的条件无回溯的条件无回溯的条件无回溯的条件改写文法改

126、写文法改写文法改写文法超前扫描超前扫描超前扫描超前扫描989898982两种常用方法两种常用方法:(1)(1)递归子程序法递归子程序法递归子程序法递归子程序法a)a)改写文法改写文法改写文法改写文法, ,消除作递归消除作递归消除作递归消除作递归, ,回溯回溯回溯回溯b)b)写递归子程序写递归子程序写递归子程序写递归子程序(2)LL(1)(2)LL(1)分析法分析法分析法分析法LL(1)LL(1)分析器的逻辑结构及工作过程分析器的逻辑结构及工作过程分析器的逻辑结构及工作过程分析器的逻辑结构及工作过程LL(1)LL(1)分析表的构造方法分析表的构造方法分析表的构造方法分析表的构造方法LL(1)LL

127、(1)文法的定义以及充分必要条件文法的定义以及充分必要条件文法的定义以及充分必要条件文法的定义以及充分必要条件1. 1.构造构造构造构造FirstFirst集合的算法集合的算法集合的算法集合的算法 2. 2.构造构造构造构造FollowFollow集合的算法集合的算法集合的算法集合的算法 3. 3.构造分析表的算法构造分析表的算法构造分析表的算法构造分析表的算法99999999( (二二二二) ) 自底向上分析自底向上分析自底向上分析自底向上分析规约过程规约过程规约过程规约过程: :(1)(1)一般过程一般过程一般过程一般过程: : 移进移进移进移进规约过程规约过程规约过程规约过程(2)(2)

128、算法算法算法算法: :问题问题问题问题: :如何寻找句柄如何寻找句柄如何寻找句柄如何寻找句柄i) i)算符优先分析法算符优先分析法算符优先分析法算符优先分析法: :1. 1.分析器的构造分析器的构造分析器的构造分析器的构造, ,分析过程分析过程分析过程分析过程. . 根据算符优先关系矩阵来决定根据算符优先关系矩阵来决定根据算符优先关系矩阵来决定根据算符优先关系矩阵来决定是移进还是规约是移进还是规约是移进还是规约是移进还是规约. .1001001001002. 2.算符优先法的进一步讨论算符优先法的进一步讨论算符优先法的进一步讨论算符优先法的进一步讨论1. 1.适用的文法类适用的文法类适用的文

129、法类适用的文法类-引出的引出的引出的引出的算符优先法算符优先法算符优先法算符优先法的定义的定义的定义的定义 2. 2.优先关系矩阵地构造优先关系矩阵地构造优先关系矩阵地构造优先关系矩阵地构造 3. 3.什么是什么是什么是什么是“ “句柄句柄句柄句柄” ”, ,如何找如何找如何找如何找有句柄引出的有句柄引出的有句柄引出的有句柄引出的最左素短语最左素短语最左素短语最左素短语的概念的概念的概念的概念. . 最左素短语的定理最左素短语的定理最左素短语的定理最左素短语的定理, ,如何找如何找如何找如何找. .ii)LRii)LR分析法分析法分析法分析法1. 1.概述概述概述概述-概念、术语概念、术语概

130、念、术语概念、术语 ( (活前缀、项目活前缀、项目活前缀、项目活前缀、项目) ) 1011011011012.LR2.LR分析分析分析分析1)1)逻辑结构逻辑结构逻辑结构逻辑结构2)2)分析过程分析过程分析过程分析过程状态栈状态栈状态栈状态栈分析表分析表分析表分析表控制程序控制程序控制程序控制程序GOTOGOTO表表表表分析动作表分析动作表分析动作表分析动作表3. 3.如何构造如何构造如何构造如何构造SLRSLR分析表分析表分析表分析表1)1)构造构造构造构造DFADFA2)2)由由由由DFADFA构造分析表构造分析表构造分析表构造分析表102102102102除了递归子程序法，其他几种方法逻

131、辑结构很象：除了递归子程序法，其他几种方法逻辑结构很象：除了递归子程序法，其他几种方法逻辑结构很象：除了递归子程序法，其他几种方法逻辑结构很象：输入串输入串输入串输入串符号栈符号栈符号栈符号栈( (状态栈状态栈状态栈状态栈) ) 控制程序控制程序控制程序控制程序分析表分析表分析表分析表(1)(1)对于对于对于对于LL(1)LL(1)分析法分析法分析法分析法符号栈符号栈符号栈符号栈 i i( (自顶向下，保证最左推导自顶向下，保证最左推导自顶向下，保证最左推导自顶向下，保证最左推导) )LL(1)LL(1)分析表分析表分析表分析表 i iA AA:=A:=i ierrorerror终结符终结符终

132、结符终结符非非非非终终终终结结结结符符符符首字符首字符首字符首字符103103103103(2)(2)对于算法优先分析对于算法优先分析对于算法优先分析对于算法优先分析: :符号栈符号栈符号栈符号栈栈栈栈栈内内内内终终终终结结结结符符符符= error= error栈外终结符栈外终结符栈外终结符栈外终结符(3)LR(3)LR分析分析分析分析: :符号栈符号栈符号栈符号栈S S0 0,S,S1 1SSmm#X#X0 0,X,X1 1XXmm分析表分析表分析表分析表状态转移状态转移状态转移状态转移GOTOGOTO表表表表分析动作表分析动作表分析动作表分析动作表104104104104GOTOGOTO

133、表表表表下一下一下一下一状态状态状态状态状状状状态态态态符号符号符号符号根据栈顶状态和栈根据栈顶状态和栈根据栈顶状态和栈根据栈顶状态和栈顶符号推导出下一顶符号推导出下一顶符号推导出下一顶符号推导出下一状态状态状态状态分析动作表分析动作表分析动作表分析动作表移进移进移进移进S S 规约规约规约规约(r(rj j) )状状状状态态态态终结符号终结符号终结符号终结符号根据栈顶状态和输入根据栈顶状态和输入根据栈顶状态和输入根据栈顶状态和输入符号推导出下一动作符号推导出下一动作符号推导出下一动作符号推导出下一动作105105105105将将将将GOTOGOTO表和分析动作表压缩后得表和分析动作表压缩后得表和分析动作表压缩后得表和分析动作表压缩后得: :状状状状态态态态终结符号终结符号终结符号终结符号非终结符号非终结符号非终结符号非终结符号GOTOGOTO表表表表S Si i r rj ji( i(下一状态数下一状态数下一状态数下一状态数) )

展开阅读全文

自底向上分析

最新文档