编译原理课件Chapt5-2.ppt

1、编译原理,第五章 语法分析自下而上分析,LR分析法,1965年 由Knuth提出 什么是LR(k)分析: L：从左到右扫描 R：最右推导的逆过程（最左归约） k：是指为了作出分析决定而向前看的输入符号的个数 是一种规范归约过程,适用范围广，适用于多数无二义性的上下文无关文法 分析效率高，报错及时 可以自动生成,手工实现工作量大,LR分析法的优缺点,优点,缺点,自下而上分析的中心思想是“移进归约”，关键问题就是“寻找规范句型的句柄”。 当一貌似句柄的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？,文法GS：(1) S aPcQe(2) P b(3) P Pb(4) Q d,a,b,b,c

2、,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aP bcde# 移进,6） #aP cde# 移进,7） #aPc de# 移进,9） #aPcQ e# 移进,11） #S # 接受,LR分析法,LR分析法的基本思想：根据“历史资料”、“现实输入符号”以及对未来的“展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的句柄。,5.3.1 LR分析器,规范归约的关键问题是寻找句柄. “历史”：已移入符号栈的内容 “展望”：根据产生式推测未来可能遇到的输入符号 “现实”：当前的输入符号,LR分析方法：把历史及展望综合抽象成状

3、态；由栈顶的状态和现行的输入符号唯一确定每一步工作,LR分析 程 序,LR分析器的核心是一张分析表： ACTIONs，a：当状态s面临输入符号a时，应采取什么动作. GOTOs，X：状态s面对文法符号X时，下一状态是什么,LR分析表,ACTION 表（分析动作表）,GOTO表（状态转换表）,每一项ACTIONs，a所规定的四种动作: 1. 移进 把(s，a)的下一状态s和输入符号a推进栈，下一输入符号变成现行输入符号. 2. 归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s=GOTOsm-r, A和

4、文法符号A推进栈. 3. 接受 宣布分析成功，停止分析器工作. 4. 报错,分析开始时: 状态 已归约串 输入串 (s0， #， a1a2 an #) 以后每步的结果可以表示为: (s0 s1 sm ，# X1 Xm ，aiai+1 an #),(s0 s1 sm ，# X1 Xm ，aiai+1 an #) 分析器根据ACTION(sm , ai)确定下一步动作 1. 若ACTION(sm , ai)为移进，且s=GOTO(sm, ai),，则三元式格局变为: (s0 s1 sms ，# X1 Xm ai，ai+1 an #) 2. 若ACTION(sm , ai)为按A归约，三元式变为:

5、(s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #) 此处, s=GOTO(sm-r, A), r为的长度, = Xm-r+1 Xm 3. 若ACTION(sm , ai)为接受，则三元式不再变化，变化过程终止，宣布分析成功. 4. 若ACTION(sm , ai)为报错，则三元式变化过程终止，报告错误.,(s0 s1 sm-r sm-r+1 sm ，# X1 Xm-r Xm-r+1 Xm ，aiai+1 an #) (s0 s1 sm-r ，# X1 Xm-r，aiai+1 an #) (s0 s1 sm-rs ，# X1 Xm-rA ，aiai+1 an #),LR

6、分析表实例,设已给文法GL: 1. LE,L 2. LE 3. Ea 4. Eb，产生的语言为：单个a,b或用逗号隔开的多个a,b符号串 文法的LR分析表如下(s表示移进操作,r表示归约),ACTION表,GOTO表,分析表的合并,可看出,GOTO表中所有关于终结符的状态转换都与ACTION表中的移进操作对应，因此可将相应的列合并，得到下面的分析表（关于VN符的状态转换仍然保留）：,实际的分析表往往是稀疏的，可采用更紧凑的格式存储。,分析表的种类,SLR(1)分析表(简单LR分析表),LR(0)分析表,对文法的限制较大，无实用价值，是构造其它LR分析表的基础,构造简单，最易实现，大多数上下文无

7、关文法都可以构造出SLR分析表，所以具有较高的实用价值。,LR(1)分析表(规范LR分析表),适用文法类最大,几乎所有上下文无关文法都能构造出LR(1)分析表,但其分析表体积太大，实用价值不大。,分析表的种类,LALR分析表(超前LR分析表),这种表适用的文法类及其实现上难易在LR(1)和SLR(1)两种之间,比较实用。使用LALR分析表进行语法分析的分析器叫LALR分析器,分析表的种类,LR分析器的工作过程,控制程序 1、根据栈顶状态和现行输入符号,查分析动作表(ACTION表),执行分析表所规定的操作 2、根据GOTO表设置新的栈顶状态(即实现状态转移),LR分析器的工作过程,1. 分析开

8、始时,首先将初始状态S0及#压入栈; 2. 设在分析的某一步,分析栈和余留输入串所处格局如下:,S0S1S2Sm #X1X2Xm aiai+1ai+2an#,LR分析器的工作过程,用Sm,ai查ACTION表,并根据指示完成相应的动作,分析动作有移进,归约,报错,接受四种: (1)移进Sk：表明句柄尚未在栈顶形成,正期待继续移进输入符号ai以形成句柄,并且移入后状态转移到Sk ，故将ai和Sk压入栈，格局如下:,S0S1S2SmSk #X1X2Xmai ai+1ai+2an#,LR分析器的工作过程,归约rj：其中rj表示按P的第j产生式AXm-k+1Xm-k+2Xm进行归约;这表明栈顶部的符号

9、串Xm-k+1Xm-k+2Xm是当前句型的句柄。 将栈顶符号串Xm-k+1Xm-k+2Xm(k个符号)从栈顶退出,再将A压入栈,此时的格局为：,S0S1S2Sm-k # X1X2Xm-k A aiai+1ai+2an#,LR分析器的工作过程,再以（Sm-k,A）查GOTO表,得Sk,将Sk压入栈,得到格局如下:,S0S1S2Sm-rSk # X1X2Xm-rA aiai+1ai+2an#,LR分析器的工作过程,(3)若ACTION(Sm,ai)=“acc”,则表明当前输入串已被成功地分析完毕,结束; (4)若ACTION(Sm,ai)=“ERROR”,则表明当前输入串有语法错误,转入出错处理程

10、序;,LR分析器的工作过程,3. 重复步骤2的工作,直到分析的某步的格局如下: S0SZ # Z # 其中,Z为文法 的开始符号, SZ是使ACTION(SZ,#)=“acc”的唯一状态。,LR分析算法描述,将S0移进状态栈，# 移进符号栈; /S为状态栈栈顶状态； a=getsym( ) /读入第一个符号给a while(ACTIONS,a!=acc ) if ACTIONS,a=Si PUSH i,a(分别进栈); a=getsym( ) ; /读入下一个符号给a,LR分析算法描述,else if ACTIONS,a=Rj /第j条产生式为A 将状态栈和符号栈分别弹出| 项; push(A

11、); /A进符号栈 将GOTOS,A 移进状态栈; /S为当前栈顶状态 else error( ); ,LR分析器示例：,文法G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,其LR分析表为:,假定输入串为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#,i,*,假定输入串为i*i+i， LR分析器的工作过程: 步骤状态符号输入串 (5)027#T*i+i# (6)0275#T*i+i# (7)0271

12、0#T*F+i# (8)02#T+i# (9)01#E+i# (10)016#E+i#,+,i,步骤状态符号输入串 (10)016#E+i# (11)0165#E+i# (12)0163#E+F# (13)0169#E+T# (14)01#E# (15) 接受,+,i,i,定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。 定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法. 非LR结构 LR文法不是二义的，二义文法肯定不会是LR的。 S iCtS | iCtSeS 栈 输入 iCtS

13、 e#,LR(k)分析法通过活前缀来帮助确定句柄,规范句型：通过规范推导（规约）得到的句型,字的前缀：该字的任意首部 如字abc的前缀有,a,b,ab,abc,LR(0)分析法,活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 即，对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串) 对于一个文法G, 可以构造一个DFA,它能识别G的所有活前缀.,例: 文法GE EE+T|T TT*F|F F(E)|i,LR(0)项目集族和LR(0)分析表的构造,假定是文法G的一个句子，我们称序列 n， n-1， ，0 是的一个规范归约，如果此序

14、列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,规范归约过程中 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型 分析栈中内容+剩余输入符号=“规范句型” 栈内容规范句型活前缀,均为活前缀,活前缀与句柄的关系,活前缀已含有句柄的全部符号,活前缀只含有句柄的部分符号,活前缀不含有句柄的任何符号,A,为刻划产生式右部符号已有多大一部分被识别，用项目来指示位置 项目:产生式的右部添加一个圆点,A12,A,栈内永远不会出现句柄之后的符号！,栈内的如果出现句柄，句柄一定在栈的顶部,指导思想目标驱动,踢足球 “

15、如果你不知道怎样踢球，就往球门方向踢 ” 施拉普纳 LR分析 “如果你不知道怎样分析，就保证栈中总是活前缀”,一个语言都有哪些活前缀? 那些字符串是活前缀? 能不能构造一个DFA来识别活前缀?,文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目 如:AXYZ有四个项目： A.XYZ AX.YZ AXY.Z AXYZ. A . 称为归约项目 归约项目 S . 称为接受项目 A .a (aVT) 称为移进项目 A .B (BVN) 称为待约项目.,项目分为四类,移进项目：Aa,待约项目：AB,文法G(S) SE EaA|bB AcA|d BcB|d 该文法的项目有： 1. SE2. SE3

16、. EaA 4. EaA5. EaA6. AcA 7. AcA8. AcA9. Ad 10. Ad11. EbB12. EbB 13. EbB14. BcB15. BcB 16. BcB17. Bd18. Bd,构造识别文法所有活前缀的NFA方法： 1. 若状态i为XX1 Xi-1.Xi Xn ， 状态j为XX1 Xi-1Xi .Xi+1 Xn ， 则从状态i画一条标志为Xi的有向边到状态j； 2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。 把识别文法所有活前缀的NFA确定化。,识别活前缀的NFA,识别活前缀的DFA,构成识别一个文法活前缀的DFA的项目集(状态

17、)的全体称为文法的LR(0)项目集规范族。 这个规范族提供了建立一类LR（0）和SLR分析器的基础。,LR(0)项目集规范族的构造,假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，而这个S是G的开始符号。那么，我们称G是G的拓广文法。 这样，便会有一个仅含项目SS.的状态，这就是唯一的“接受”态。,假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下： 1. I的任何项目都属于CLOSURE(I)； 2. 若AB属于CLOSURE(I)，那么，对任何关于B的产生式B，项目B也属于CLOSUR

18、E(I)； 3. 重复执行上述两步骤直至CLOSURE(I) 不再增大为止。,P50：NFA确定化 设I是的状态集的一个子集，定义I的-闭包-closure(I)为: i) 若sI，则s-closure(I)； ii) 若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I) -closure(I)=Is|从某个sI出发经过任意条弧能到达s,2. 若状态i为X .A ，A为非终结符， 则从状态i画一条边到所有状态A.。,【例】 （0）SS （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,例：I= SS closure(I)=？, SS , S

19、aS , Sb ,练习：I= SaS closure(I)=？, SaS , SaS , Sb ,识别活前缀的DFA,为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为： GO(I，X)CLOSURE(J) 其中 J任何形如AX的项目| A X属于I。 直观上说，若I是对某个活前缀 有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。,P50：设a是中的一个字符，定义 Ia= -closure(J) 其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,文法G(S) SE EaA|bB AcA|d BcB|

20、d I0=SE, EaA, EbB GO(I0, E)= closure(J)=closure(SE) = SE = I1 GO(I0, a)= closure(J)=closure(EaA) = EaA, AcA, Ad )=I2 GO(I0, b)= closure(J)=closure (E b.B) =E b.B, B.cB, B.d= I3,【例】 （0）SS （1）SS （2）SaS （3）SaS （4）SaS （5）Sb （6）Sb,求GO (I , b )=?,GO(I,b)=closure(Sb)= Sb,求GO (I , a )=?,GO(I,a)=closure(SaS)

21、= SaS , SaS , Sb ,例：I= SS , SaS , Sb ,识别活前缀的DFA,直接构造DFA的思想 从SS开始，得到DFA的初态项目集 然后通过状态转换函数GO求其所有的后继项目集,识别活前缀的DFA,构造文法G的拓广文法G的LR(0)项目集规范族算法： PROCEDURE ITEMSETS(G)； BEGIN C:=CLOSURE(SS)； REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中; UNTIL C不再增大 END 转换函数GO把项目集连接成一个DFA转换图.,【例】GS： SS

22、SaS|b,I0= SS , SaS , Sb I1 = GO(I0,S)=closure(SS)= SS I2 = GO(I0,a)=closure(SaS)= SaS , SaS , Sb I3 = GO(I0,b)=closure(Sb)= Sb I4 = GO(I2,S)=closure( SaS)= SaS,识别活前缀的DFA,DFA的每一个状态由若干个LR(0)项目所组成的集合 (称为项目集)来表示。,0: SE EaA EbB,4: AcA AcA Ad,5: BcB BcB Bd,3: EbB BcB Bd,1: SE,2: EaA AcA Ad,11: Bd,8: AcA,1

23、0: Ad,9: BcB,6: EaA,7: EbB,LR(0)项目小结,同一产生式(设右部有n个符号)对应了若干(n+1)个LR(0)项目,每个项目反映了栈顶所处的不同状态. 若AP,则对应了唯一的LR(0)项目A； 所有的LR(0)项目是构造识别活前缀的自动机的基础。,有穷自动机的输入字符：终结符和非终结符 状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。 终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约。,识别活前缀的DFA,有效项目,我们说项目A 1.2对活前缀

24、1是有效的，其条件是存在规范推导,在任何时候，分析栈中的活前缀X1X2 Xm的有效项目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 Xm后到达的那个项目集(状态)。,结论: 若项目A .B对活前缀=是有效的且B 是一个产生式，则项目B .对=也是有效的。,所以，B .对=也是有效的。,文法G(S) SE EaA|bB AcA|d BcB|d 考虑： 项目：B c.BB . cB B . d 活前缀：bc S E bB bcB S E bB bcB bccB S E bB bcB bcd,项目A 1.2对活前缀1是有效的，其条件是存在规范推导,LR(0)

25、分析表的构造,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况： 1) 既含移进项目又含归约项目， 2) 含有多个归约项目 则称G是一个LR(0)文法。,构造LR(0)分析表的算法,令每个项目集Ik的下标k作为分析器的状态，包含项目SS的集合Ik的下标k为分析器的初态。,分析表的ACTION和GOTO子表构造方法： 1. 若项目Aa属于Ik且GO(Ik, a)Ij，a为终结符，则置ACTIONk,a 为“sj”。 2. 若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为 “rj”(假定产生式A是文法G的第j个产生式)。 3. 若项目SS

26、属于Ik，则置ACTIONk,#为 “acc”。 4. 若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。 5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。,文法G(S) SE EaA|bB AcA|d BcB|d,识别活前缀的DFA,LR(0)分析表为,例: 按上表对acccd进行分析 步骤状态符号输入串 10#acccd# 202#acccd# 3024#acccd# 40244#acccd# 502444#acccd# 60244410#acccd# 7024448#acccA# 802448#accA# 90248#acA# 10026#aA# 1101

27、#E#,LR(0)小结,对于一个文法构造了它的LR(0)分析表就可以在LR分析器的总控程序控制下对输入串进行分析，即根据输入串当前符号a和分析栈栈顶状态i查找分析表应采取的动作，对状态栈和符号栈进行相应的操作即移进、归约、接受或报错。具体为： 1）若ACTIONi,a=Sj, aVT,则把a移进符号栈，j移进状态栈。,LR(0)小结,2）若ACTIONi,a=Rj，a VT或$，则用第j个产生式归约。并将两个栈的指针减去K(其中K为第j 个产生式右部的串长度），并把产生式的左部符号A压入符号栈，同时用符号对（ Si-k,A)去查GOTO表（其中Si-k为状态栈当前栈顶元素，若GOTOSi-k,A=j,则j压入状态栈，使得两个栈内的元素一样多。 3）若ACTIONi,a=Acc,（此时a应为“$”号），则表明分析成功，结束分析。 4）若ACTIONi,a=空白，转出错处理。,GS： S aAcBe A b A Ab B d