编译原理-第五章.ppt_一课资料网ekdoc.com

资源描述

1、编译原理第五章语法分析(自下而上分析,王金伟计算机与信息工程学院天津师范大学,TJNU-COCIE-WJW,2,2021/3/23,第五章语法分析(自下而上分析,从输入符号串开始，逐步进行“归约”，直到归约到文法的开始符号。即从语法树的末端开始，逐步向上“归约”，直到根节点。 1.算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 2.LR分析法：规范归约,TJNU-COCIE-WJW,3,2021/3/23,第五章语法分析(自下而上分析,5.1 自下而上语法分析基本问题 5.2 算符优先分析法 5.3 LR分析法 5.4 LR(0)项目集族和LR(0)分析表

2、的构造 5.5 SLR分析表的构造 5.6 规范LR分析表的构造,TJNU-COCIE-WJW,4,2021/3/23,5.1 自下而上语法分析基本问题,1.基本思想用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 2.归约是指根据文法的产生式规则，把产生式的右部替换成左部符号,一、移进归约,TJNU-COCIE-WJW,5,2021/3/23,例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d 试对abbcde进行“移进归约”分析,TJNU-COC

3、IE-WJW,6,2021/3/23,例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d 试对abbcde进行“移进归约”分析,问题： 1.何时进行归约？ 2.“可归约串”的定义方法？ (5步，为什么用(3)不用(2,TJNU-COCIE-WJW,7,2021/3/23,b,d,b,a,c,e,自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串,TJNU-COCIE-WJW,8,2021/3/23,1.短语定义:令G是一个文法，S是文法的开始符号，假定是文法G的一个句型其中,(VNVT)*，AVN ，如果有则称是句型相对于非终结

4、符A的短语。注意：因为句型是由开始符号推出来的，而短语是由非终结符号推出来的。所以，短语是句型的一部份或全部符号串,且,二、规范归约,TJNU-COCIE-WJW,9,2021/3/23,2.直接短语特别是，如果有A,则称是句型相对于规则A 的直接短语。 3.句柄一个句型的最左直接短语称为该句型的句柄,TJNU-COCIE-WJW,10,2021/3/23,例：考虑文法 G ： E T | E+T T F | T*F F (E) | i 求证i1*i2+i3是G的一个句型，并找出该句型的全部短语、直接短语和句柄解：证明i1*i2+i3是G的一个句型 E E+T T+T T*F+T F*

5、F+T i1*F+T i1*i2+T i1*i2+F i1*i2+i3,TJNU-COCIE-WJW,11,2021/3/23,找i1*i2+i3的所有短语 (1)假设i1*i2+i3是一个短语因为E E 且 E i1*i2+i3 所以i1*i2+i3是句型i1*i2+i3关于E的一个短语 (2)假设i1*i2是一个短语因为E T+i3 且 T i1*i2 所以i1*i2是句型i1*i2+i3关于T的一个短语 (3)假设i1是一个短语因为E F*i2+i3 且 F i1 所以i1是句型i1*i2+i3关于F的一个短语,且,E T | E+T T F | T*F F (E) | i,TJN

6、U-COCIE-WJW,12,2021/3/23,找i1*i2+i3的所有短语 (4)假设i2是一个短语因为E i1*F+i3 且 F i2 所以i2是句型i1*i2+i3关于F的一个短语 (5)假设i3是一个短语因为E i1*i2+F且 F i3 所以i3是句型i1*i2+i3关于F的一个短语 (6)假设i2+i3是一个短语因为E i1*E不成立，且 E i2+i3成立所以i2+i3不是句型i1*i2+i3的一个短语,且,E T | E+T T F | T*F F (E) | i,TJNU-COCIE-WJW,13,2021/3/23,注意：缺一不可所以短语有：i1*i2+i3

7、， i1*i2， i1，i2，i3 找直接短语：根据定义，如果有A,则称是句型相对于规则A 的直接短语因为有：F i 所以i1、i2、i3是直接短语找句柄：根据定义，一个句型的最左直接短语称为该句型的句柄。 i1是句型i1*i2+i3的句柄,和,TJNU-COCIE-WJW,14,2021/3/23,4.规范归约定义：假定是文法G的一个句子，我们称序列 n， n-1，，0 是的一个规范归约，如果此序列满足： (1) n= (2) 0为文法的开始符号，即0=S (3) 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的,TJNU-COCIE-WJW,15,

8、2021/3/23,例：设文法G(S)： (1) S aAcBe (2) A b (3) A Ab (4) B d 求句子abbcde的规范归约 abbcde aAbcde aAcde aAcBe S,TJNU-COCIE-WJW,16,2021/3/23,注意: (1)把上例倒过来写，则得到： S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。 (2)由于规范句型由最右推导推出的句型，故该句型的句柄右边只含有终结符号,17,2021/3/23,6.修剪语法树使用修剪语法

9、树的方法来加深对自下而上语法分析的理解。 (1)子树：是由该树的某个结点(子树的根)连同它的所有子孙组成。 (2)简单子树：只有单层分支的子树(只有父子两代没有第三代,TJNU-COCIE-WJW,18,2021/3/23,6.修剪语法树 (3) 对语法树有如下结论每个句型都有一棵语法树与之对应每棵语法树的叶结点自左至右排列就组成一个句型每棵子树的叶结点自左至右排列就组成一个短语每棵简单子树的叶结点自左至右排列就组成一个直接短语每棵最左简单子树的叶结点自左至右排列就组成一个句柄,TJNU-COCIE-WJW,19,2021/3/23,例：短语 i1，i2，i3 i1*i2 i1*i

10、2+i3 直接短语 i1，i2，i3 句柄 i1,TJNU-COCIE-WJW,20,2021/3/23,修剪最左简单子树,TJNU-COCIE-WJW,21,2021/3/23,栈是语法分析的一种基本数据结构。 1.#的使用 (1)在分析开始时，将#预先进栈，作为栈底符号 (2)将#作为输入串的结束符即分析开始时的格局为,三、用符号栈进行自下而上的语法分析,TJNU-COCIE-WJW,22,2021/3/23,2.分析过程自左向右对输入串不断向栈中进行移进归约，直到形成如下格局表示分析成功，否则意味着输入串有错,TJNU-COCIE-WJW,23,2021/3/23,例子：考虑文法

11、G： E T | E+T T F | T*F F (E) | i 输入串为i1*i2+i3 ，分析步骤为,TJNU-COCIE-WJW,24,2021/3/23,步骤符号栈输入串动作 0 #i1*i2+i3#预备 1 #i1 *i2+i3#进 2 #F *i2+i3#归，用Fi 3 #T *i2+i3#归，用TF 4 #T* i2+i3#进 5 #T*i2 +i3#进 6 #T*F +i3#归，用Fi 7 #T +i3#归，用TT*F,TJNU-COCIE-WJW,25,2021/3/23,步骤符号栈输入串动作 8#E+i3#归，用ET 9#E+ i3#进 10#E+i3 #进 11#E+

12、F #归，用Fi 12#E+T #归，用TF 13#E #归，用EE+T 14#E #接受,TJNU-COCIE-WJW,26,2021/3/23,5.2 算符优先分析法,1.引例试分析下面算数表达式的计算结果 (先乘除后加减，同级从左到右) 9+8-6/2*3(+ - 同级，服从左结合) = 17-6/2*3(- 低于 /) = 17-3*3(- 低于 *) = 17-9(唯一一个-) = 8,一、问题的提出,TJNU-COCIE-WJW,27,2021/3/23,2.算符优先分析法思路：定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约,TJNU-COCIE-WJW,28

13、,2021/3/23,3.定义两个终结符a与b的优先关系 a =.b 表示a的优先性等于b a .b 表示a的优先性大于b a . a =.b 不一定对应着 b =. a a .b 不一定对应着 b . a,TJNU-COCIE-WJW,29,2021/3/23,1.算符优先文法 (1)算符文法一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR 则我们称该文法为算符文法，也称OG文法 (Operater Grammar) 。约定： a、b代表任意终结符； P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字,二、算

14、符优先文法及优先表构造,TJNU-COCIE-WJW,30,2021/3/23,1. a =. b 当且仅当文法G中含有形如Pab或PaQb的产生式,2. a . b 当且仅当G中含有形如PaR的产生式，而R b或R Qb,3. a.b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ,2)定义终结符之间的优先关系假定G是一个不含产生式的算符文法。对于任何一对终结符a、b，我们说,TJNU-COCIE-WJW,31,2021/3/23,3)如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： a=.b a.b a.b 则称G是一个算符优先文法(OPG文法,TJNU

17、Q 所以 * . * 由(3) FP FFP F a R Q b 所以 .,1.a =. b 当且仅当文法G中含有形如Pab或PaQb的产生式； 2. a .b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ,TJNU-COCIE-WJW,36,2021/3/23,1)EE+T | T (2)TT*F | F (3)FP F | P (4)P(E) | i 由(4) P( E ) a R 且EE+TT+TT*F+TF*F+TPF*F+T(E)F*F+T Qb Qb Qb b iF*F+T b 所以( . + , * , , ( , i,1.a =. b 当且仅当文法G中含有形如Pab

18、或PaQb的产生式； 2. a .b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ,TJNU-COCIE-WJW,37,2021/3/23,1)EE+T | T (2)TT*F | F (3)FP F | P (4)P(E) | i 由(4) P( E ) Rb 且EE+TE+T*FE+T*PF E+T*PP E+T*P(E) aQ aQ aQ a E+T*Pi a 所以 + , * , , ) , i . ) 以下略在该文法中任意两个终结符号之间在.中只有一种关系成立，所以，G是一个OPG文法,1.a =. b 当且仅当文法G中含有形如Pab或PaQb的产生式； 2. a .b

19、当且仅当G中含有形如PRb的产生式，而 R a或R aQ,TJNU-COCIE-WJW,38,2021/3/23,2.构造算符优先关系表 (1)通过检查产生式的每一个候选式可以找出满足a=.b （即Pab或PaQb的产生式） (2)为了满足.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P,TJNU-COCIE-WJW,39,2021/3/23,3)构造集合FIRSTVT(P)的算法按其定义，可用下面两条规则来构造集合FIRSTVT(P)：若有产生式Pa或PQa，则aFIRSTVT(P)；若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P,T

20、JNU-COCIE-WJW,40,2021/3/23,4)同理构造构造集合LASTVT(P)的算法按其定义，可用下面两条规则来构造集合LASTVT(P)：若有产生式P a或P aQ ，则a LASTVT(P)；若a LASTVT(Q)，且有产生式P Q ，则a LASTVT(P,TJNU-COCIE-WJW,41,2021/3/23,5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系.的所有终结符对。 (1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b,TJNU-COCIE-WJW,42,2021/3/23,例1:考虑下面的文

22、IRSTVT和LASTVT集合解: (1)构造LASTVT集合 LASTVT(P)= LASTVT(F)= LASTVT(T)= LASTVT(E)=, i, i, i, i,若有产生式P a或P aQ ，则a LASTVT(P)；若a LASTVT(P)，且有产生式P Q ，则a LASTVT(P,TJNU-COCIE-WJW,44,2021/3/23,例2:G: EE+T | T TT*F | F F(E) | i 求出该文法每个终结符号的优先关系，并构造优先分析表 (1)EE+T，且*, (, i FIRSTVT(T) aP 所以+ .,FIRSTVT(E)=+, *, (, i F

23、IRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i,1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b,TJNU-COCIE-WJW,45,2021/3/23,例2:G: EE+T | T TT*F | F F(E) | I (3)TT*F，且 (, i FIRSTVT(F) aP 所以* .,FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRSTVT(F)= (, i LASTVT(E

24、)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i,1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b,TJNU-COCIE-WJW,46,2021/3/23,例:G: EE+T | T TT*F | F F(E) | i (5)F(E) ，且+,*, (, i FIRSTVT(E) aP 所以( . ) (7)F(E) ，所以( =.,0)通过检查产生式的每一个候选式可以找出满足a=.b （即Pab或PaQb的产生式,FIRSTVT(E)=+, *, (, i FIRSTVT(T)= *, (, i FIRS

25、TVT(F)= (, i LASTVT(E)=+, *, ), i LASTVT(T)= *, ), i LASTVT(F)= ), i,1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b,TJNU-COCIE-WJW,47,2021/3/23,构造分析表如下：其中，E=ERROR,TJNU-COCIE-WJW,48,2021/3/23,注意：对于#号，相当于在文法开始符号S前加一个额外的开始符号，比如为Z 然后，把 Z #S# 添加到原文法中，再进行分析,TJNU-COCIE-WJW,49,2021/3/23,例3:G: EE+T | T TT*F

26、| F F(E) | I (1)因为Z#E# 所以# =. # (2)因为FIRSTVT(E)=+, *, , (, i Z #E# aP 所以# . ,Z #E# EE+T | T TT*F | F F(E) | i,1)假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有a . b,TJNU-COCIE-WJW,50,2021/3/23, . +, *, , (, i, *, , ), i . ,TJNU-COCIE-WJW,51,2021/3/23,1.问题的提出自下而上分析移进-归约法：句柄为可归纳串算符优先分析法：最左素短语为可归纳串 2.素短语指一个句

27、型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语 3.最左素短语处在句型最左端那个素短语成为最左素短语,三、算符优先分析算法的设计,TJNU-COCIE-WJW,52,2021/3/23,例:考虑下面的文法G： EE+T | T TT*F | F F(E) | i 求句型E+T*F+i的素短语和最左素短语解: 构造一个推导 EE+TE+T+TE+T+TE+T*F+FE+T*F+i 素短语： T*F，i 最左素短语： T*F,短语： E+T*F+i E+T*F T*F i,TJNU-COCIE-WJW,53,2021/3/23,4.算符优先分析算法和设计 (1)句型的

28、一般表示形式： #N1a1N2a2NnanNn+1# 其中，每个ai都是终结符，Ni是可有可无的非终结符 (2)定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1， aj-1 . ai+1 注意：出现在左端或右端的非终结符一定属于这个素短语,TJNU-COCIE-WJW,54,2021/3/23,例:EE+T | T TT*F | F F(E) | i 句型关系最左素短语归约符号 # #i#.+i F #F+ #F+i#. *i F #F+F* #F+F*i#. #i F #F+F*F#. #F*F T #F+T# #.# F+T E #E,

29、对句子 i + i * i 进行分析,TJNU-COCIE-WJW,55,2021/3/23,注意：算符优先分析一般不等于规范归约例:文法G：EE+T | T TT*F | F FP F | P P(E) | i 解:#.+.# #P+i# #.# #P+P# #.# #E# 右边是规范归约,对句型 “#i+i#” 进行分析,TJNU-COCIE-WJW,56,2021/3/23,1.优先函数的定义把每个终结符与两个自然数f()与g()相对应，使得若1 . 2，则f(1) g(2) f称为入栈优先函数，g称为比较优先函数。 (1)优点:便于比较，节省空间； (2)缺点:原来不存在优先关系

30、的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断,四、优先函数,TJNU-COCIE-WJW,57,2021/3/23,例如：文法G(E) (1) EE+T | T (2) TT*F | F (3) FP F | P (4) P(E) | i 的优先函数如下表注意： (1)对应一个优先关系表的优先函数f和g并不唯一，只要存在一对，就存在无穷多对,TJNU-COCIE-WJW,58,2021/3/23,注意： (2) 许多优先关系表不存在优先函数如：不存在对应的优先函数f和g 假定存在f和g，则有 f(a)=g(a)，f(a)g(b)， f(b)=g(a)，f(b)=g

31、(b) 导致如下矛盾: f(a) g(b) = f(b) = g(a) = f(a,TJNU-COCIE-WJW,59,2021/3/23,2.优先函数的构造方法如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数: (1)对于每个终结符a，令其对应两个符号fa和ga，画一张以所有符号fa和ga为结点的方向图。如果a.=.b，则从fa画一条弧至gb如果a.=.b，则从gb画一条弧至fa 。 (2)对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)赋给ga的数作为g(a)。 (3)检查所构造出来的函数f和g是否与原来的关系矛盾。若没有

32、矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数,TJNU-COCIE-WJW,60,2021/3/23,gi,fi,f,g,g,f,f,g,例:取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) F (E) | i 的终结符+，*，i，,7,4,6,6,2,1,5,1,TJNU-COCIE-WJW,61,2021/3/23,3.构造方法证明现在必须证明：若a=.b，则f(a)g(b)；若a.b，则f(a) g(b)。第一个关系可从函数的构造直接获得。因为，若a=.b，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同

33、的。至于a.b的情形，只须证明其一。如果a.b，则有从fa到gb的弧。也就是gb能到达的任何结fa也能到达。因此，f(a) g(b)。所需证明的是，在这种情况下，f(a)=g(b)不应成立,TJNU-COCIE-WJW,62,2021/3/23,我们将指出，如果f(a)=g(b)，则根本不存在优先函数。假若f(a)=g(b)，那么必有如下的回路,因此有 a.b, a1.=.b1, , am.=.bm, a g(b) f(a1) g(b1) f(am) g(bm) f(a) 从而导致f(a) f(a)，产生矛盾。因此，不存在优先函数f和g,TJNU-COCIE-WJW,63,2021/3/2

34、3,5.3 LR分析法,L指从左到右扫描输入 R指构造最右推导的逆 k指的是在决定分析动作时向前看的符号个数,一、LR(k)分析法,TJNU-COCIE-WJW,64,2021/3/23,1.分析能力强大 LR分析器能够构造识别所有上下文无关文法写的程序设计语言的结构 LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现 LR方法能分析的文法类是预测分析法能分析的文法类的真超集 LR分析器能及时察觉语法错误,TJNU-COCIE-WJW,65,2021/3/23,2.LR分析器的组成总控程序一张分析表,TJNU-COCIE-WJW,66,2021/3/

35、23,3. LR分析表的种类 LR(0)分析表功能较弱，但是它是建立LR分析的基础 SLR(简单LR)分析表功能一般，但容易实现，使用价值比较高规范LR分析表功能强，应用范围比较广，但实现代价高 LALR(向前LR)分析表功能介于SLR与规范LR之间,TJNU-COCIE-WJW,67,2021/3/23,4.LR分析法的基本思想使用的最右推导的逆过程，就是规范归约在规范归约中，记住已移进和归约出的整个符号串 (记住历史) 根据产生式，推测未来可能碰到的输入符号 (展望未来) 根据当前正在要进栈的输入符号 (面对现实) 最终是为了寻找句柄(可归约串,TJNU-COCIE-WJW,

36、68,2021/3/23,LR分析程序,二、 LR分析器的结构,TJNU-COCIE-WJW,69,2021/3/23,1.LR分析器栈的结构 (1)把历史和展望材料抽象成某些状态。分析栈用来存放这些状态。栈顶的状态都代表了整个历史和已经推测出的展望。 (2)为了有助于明确规约手续，将已规约出的文法符号串也同时放到栈里,TJNU-COCIE-WJW,70,2021/3/23,2.LR分析表的结构动作表： ACTIONs，a：当状态s面临输入符号a时，应采取什么动作状态转换表： GOTOs，X：状态s面对文法符号X时，下一状态是什么,TJNU-COCIE-WJW,71,2021/3/

37、23,1)动作表 ACTIONs，a：当状态s面临输入符号a时，应采取什么动作每一项ACTIONs，a所规定的四种动作: . 移进 . 归约 . 接受 . 报错,TJNU-COCIE-WJW,72,2021/3/23,移进把(s，a)的下一状态s=GOTOs,a 和输入符号a推进栈，下一输入符号变成现行输入符号,状态,符号,分析栈,a,s,TJNU-COCIE-WJW,73,2021/3/23,归约指用某产生式A进行归约. 假若的长度为r，归约动作是A，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s=GOTOsm-r, A和文法符号A推进栈,状态,符

38、号,分析栈,A,s,TJNU-COCIE-WJW,74,2021/3/23,接受宣布分析成功，停止分析器工作。 . 报错发现源程序含有错误，调用出错处理程序,TJNU-COCIE-WJW,75,2021/3/23,可以看成是一个三元式的变化过程 (状态序列，已规约串，输入串) 分析开始时: 状态序列已归约串输入串 (s0， #， a1a2 an #) 以后每步的结果可以表示为: (s0 s1 sm ，# X1 Xm ，aiai+1 an #) 分析器下一步的动作由ACTIONsm ，ai所规定的,三、 LR分析器的工作过程,TJNU-COCIE-WJW,76,2021/3/23,s0

39、s1 sm ，# X1 Xm ，aiai+1 an #) .若ACTION(sm , ai)为移进，且s=GOTOsm , ai ，则三元式格局变为: (s0 s1 sms ，# X1 Xm ai ， ai+1 an #) .若ACTION(sm , ai)为按A归约，三元式变为: (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #) 此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm .若ACTION(sm , ai)为接受，则三元式不再变化，变化过程终止，宣布分析成功. .若ACTION(sm , ai)为报错，则三元式变化过程终止，报告

40、错误,TJNU-COCIE-WJW,77,2021/3/23,文法G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi 分析i*i+i,四、LR分析器示例,TJNU-COCIE-WJW,78,2021/3/23,其LR分析表为（书P101,TJNU-COCIE-WJW,79,2021/3/23,假定输入串为i*i+i， LR分析器的工作过程: 步骤状态符号输入串 (1)0#i*i+i# (2)05#i*i+i# (3)03#F*i+i# (4)02#T*i+i# (5)027#T*i+i# (6)0275#T*i+i# (7)02710#T*

41、F+i# (8)02#T+i,TJNU-COCIE-WJW,80,2021/3/23,步骤状态符号输入串 (9)01#E+i# (10)016#E+i# (11)0165#E+i# (12)0163#E+F# (13)0169#E+T# (14)01#E# (15) 接受,TJNU-COCIE-WJW,81,2021/3/23,1)定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法注意：不是所有上下文无关文法都是LR文法，但多数程序设计语言都可用LR文法描述 (2)定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，

42、则这个文法就称为LR(k)文法注意：对于多数程序设计语言，k=0或1，足够了,五、LR文法,TJNU-COCIE-WJW,82,2021/3/23,3)非LR结构 LR文法不是二义的，二义文法肯定不会是LR的。 S iCtS | iCtSeS 栈输入 iCtS e# iCtS是否为句柄？是规约还是继续移进,TJNU-COCIE-WJW,83,2021/3/23,5.4 LR(0)项目集族和LR(0)分析表的构造,1.字的前缀是指字的任意首部. 如:字abc的前缀有，a，ab，abc 2.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u

43、2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串,一、规范句型活前缀的概念,TJNU-COCIE-WJW,84,2021/3/23,注意： 1.在LR分析工作过程中的任何时候，栈里的文法符号X1 X2 Xm应该构成活前缀，把输入串的剩余部分配上之后，即应成为规范句型(如果整个输入串确实是一个句子)。因此，只要输入串的已扫描部分保持可归约为一个活前缀，则意味着扫描过的部分没有错。 2.LR分析器的工作实质上就是一个逐步产生或识别所给文法规范句型活前缀的过程。 3.对于一个文法G, 可以构造一个DFA,它能识别G的所有活前缀.然后我们可以将该DFA转变成LR分析表,TJNU-COC

44、IE-WJW,85,2021/3/23,1.LR(0)项目的提出 (1)活前缀与句柄的关系 A.活前缀中已含有句柄的全部(句柄在最右边) B.活前缀中只含句柄的一部分符号 C.活前缀中全然不含句柄的任何符号分析一下：从A看出A的右部已出现在栈顶，用产生式A进行归约. 从B看出A12，已经看到1，期待看到2 从C看出A，产生式的右部一点都没看到,二、构造识别文法G的所有活前缀的NFA,TJNU-COCIE-WJW,86,2021/3/23,2)LR(0)项目概念文法G的每个产生式的右部添加一个圆点称为 G的LR(0)项目例如:AXYZ有四个项目： A.XYZ AX.YZ AXY.Z AX

45、YZ,TJNU-COCIE-WJW,87,2021/3/23,2.构造识别文法所有活前缀的NFA方法例如：文法G(S) SE EaA|bB AcA|d BcB|d 构造识别该文法所有活前缀的NFA,TJNU-COCIE-WJW,88,2021/3/23,1)求出该文法的LR(0)项目 SE EaA|bB AcA|d BcB|d 1.SE2.SE 3.EaA 4.EaA5.EaA 6.AcA7.AcA8.AcA 9.Ad 10.Ad 11.EbB12.EbB13.EbB 14.BcB15.BcB 16.BcB 17.Bd18.Bd,TJNU-COCIE-WJW,89,2021/3/23,2)构

46、造识别文法的NFA为 M = (S, , f, S0, Z) 其中 S=s|s是文法G的18个LR(0)项目 =S,E, A, B, a, b, c, d S0= SE Z:规定每个状态都是识别活前缀的终态(18个,TJNU-COCIE-WJW,90,2021/3/23,f: 若状态i为XX1 Xi-1Xi Xn ，状态j为XX1 Xi-1Xi Xi+1 Xn ，则从状态i画一条标志为Xi的有向边到状态j；若状态i为X .A ，A为非终结符，则从状态i画一条边到所有状态j：A.。例如：状态i：SE 状态j：EaA,i,j,Xi,i,j,TJNU-COCIE-WJW,91,2021/

47、3/23,6,7,8,9,10,4,5,3,1,2,11,12,13,14,15,16,18,17,a,A,E,b,B,B,c,A,c,d,识别活前缀的NFA,SE 2. SE EaA EaA 5. EaA AcA AcA 8. AcA Ad 10. Ad EbB EbB 13. EbB BcB BcB 16. BcB Bd 18. Bd,d,TJNU-COCIE-WJW,92,2021/3/23,用子集法，把项目集变为状态,三、把识别文法所有活前缀的NFA确定化,TJNU-COCIE-WJW,93,2021/3/23,识别活前缀的DFA,TJNU-COCIE-WJW,94,2021/3/23

48、,1.LR(0)项目集规范族的定义构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族,TJNU-COCIE-WJW,95,2021/3/23,2.几个专门术语 (1)凡是圆点在最右端的项目，如A . 称为“归约项目” (2)对于文法的开始符号S把S . 称为接受项目“ (3)把形如A .a (aVT) 称为移进项目” (4)把形如A .B (BVN) 称为待约项目” 例如：状态611都是规约项目，状态1都是接受项目，其他状态均含移进和待约项目,TJNU-COCIE-WJW,96,2021/3/23,用_CLOSURE(闭包)的办法来构造一个文法G的LR(0)

49、项目集规范族。 1.构造G的拓广文法G 设S为文法G的开始符号，构造一个文法G，它包含整个文法G，并且引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，这个S是G的开始符号。G是G的拓广文法。 (有一个仅含项目SS. 的状态，这就是唯一的“接受”状态,四、LR(0)项目集规范族的构造,TJNU-COCIE-WJW,97,2021/3/23,2.定义和构造状态项目集I的闭包CLOSURE(I)的方法 (1) I的任何项目都属于CLOSURE(I)； (2) 若AB属于CLOSURE(I)，那么，对任何关于B的产生式B的项目B也属于CLOSURE(I)； (3) 重复执行上述两步骤直至C

50、LOSURE(I) 不再增大为止例如：设I=SE 则CLOSURE(I)=SE ，EaA， EbB,TJNU-COCIE-WJW,98,2021/3/23,3.状态转换函数GO(I，X)的定义函数值GO(I，X)定义为： GO(I，X)CLOSURE(J) 其中 I是一个项目集， X是一个文法符号， J任何形如AX的项目| A X属于I,TJNU-COCIE-WJW,99,2021/3/23,例如：项目集I0=SE, EaA, EbB GO(I0, E)= closure(J)=closure(SE) = SE = I1 GO(I0, a)= closure(J)=closure(EaA

展开阅读全文