编译原理与技术 自底向上分析.ppt

《编译原理与技术 自底向上分析.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术 自底向上分析.ppt（102页珍藏版）》请在三一办公上搜索。

1、2023/4/26,编译原理与技术讲义,1,编译原理与技术,自底向上分析,2023/4/26,编译原理与技术讲义,2,自底向上分析,移进归约分析分析树的构建 从叶子结点开始，逐步构造各内部结点直至根结点出现。分析技术的关键句柄的识别句柄（handle）是什么？简单讲，句柄是一个产生式的右部；自底向上分析（移进归约分析）过程，其实就是发现句柄并将句柄（产生式右部）替换成相应左部非终结符的过程。该替换称为最左归约，它对应着某最右推导逆过程的一步。,2023/4/26,编译原理与技术讲义,3,自底向上分析,分析技术的关键句柄的识别句柄（handle）是什么？一般地，如果有以下最右推导序列，则产生式A

2、及其在右句型中的位置称为右句型的句柄。,2023/4/26,编译原理与技术讲义,4,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的分析过程。,输入串 a b b c d e$,a A b c d e$,a A d e$,a A B e$,S$,最左归约,最右推导,2023/4/26,编译原理与技术讲义,5,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,2023/4/26,编译原理与技术讲义,6,自底向上分析,e.g.1

3、7 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,2023/4/26,编译原理与技术讲义,7,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,A,2023/4/26,编译原理与技术讲义,8,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,A,2023/4/26,编译原理与技术讲

4、义,9,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,A,A,2023/4/26,编译原理与技术讲义,10,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e$,A,A,B,2023/4/26,编译原理与技术讲义,11,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c

5、 d e$,A,A,B,S,2023/4/26,编译原理与技术讲义,12,移进归约分析,e.g.17 用栈来实现串abbcde$的分析（1）,2023/4/26,编译原理与技术讲义,13,移进归约分析,e.g.17 用栈来实现串abbcde$的分析（2）,分析成功！,2023/4/26,编译原理与技术讲义,14,移进归约分析,四种分析动作（action）移进（shift）将当前输入符号移入栈顶top（why？）归约（reduce）当“句柄”出现在栈顶（从栈中某处到栈顶top），则将“句柄”从栈顶弹弹出，并将相应产生式左部非终结符置入栈顶top。（when？）接受（accept）分析成功！报错（

6、error）出现语法错误，调错误恢复例程,2023/4/26,编译原理与技术讲义,15,移进归约分析,分析动作冲突 移进-归约冲突（shift-reduce conflict）当“句柄”处于栈顶时，分析动作指示既可以将下一输入符号移入栈顶top，又可以实施归约操作。如何动作呢？归约-归约冲突（reduce-reduce conflict）位于栈顶的“句柄”，同时匹配两个（以上）产生式的右部。选谁呢？,怎么可能呢？,2023/4/26,编译原理与技术讲义,16,移进归约分析冲突,二义文法G不适合移进归约分析 e.g.18 移进-归约冲突文法G7：S if E then S|if E then S

7、 else S S a,$.if E then S,“句柄”？,else.,分析栈,输入串：,当前输入符号,2023/4/26,编译原理与技术讲义,17,$.if E then S else,栈顶,.,分析栈,输入串：,$S,else.,分析栈,输入串：,归约动作,移进动作,文法G7:S if E then S|if E then S else S|a,期待新的“长句柄”,2023/4/26,编译原理与技术讲义,18,e.g.19 二义性文法G8如下：EE+E|E*E|(E)|id 输入串id+id+id$的最右推导：1）EE+EE+idE+E+idE+id+idid+id+id2）EE+EE

8、+E+EE+E+idE+id+idid+id+id带下划线的符号串是相应句型的句柄。,移进归约分析冲突,2023/4/26,编译原理与技术讲义,19,e.g.19输入串id+id+id$的栈分析过程,分析1）输入串分析2）$id+id+id$id+id+id$id$E+id+id$E$E+id+id$E+$E+id+id$E+id$E+E+id$E+E$E+id$id$E+E+,归约,移进,2023/4/26,编译原理与技术讲义,20,e.g.19输入串id+id+id$的栈分析过程,分析1）输入串分析2）$E+E+id$+id$E+E$E+id$id$E+E+$E+id$E+E+id$E+i

9、d$E+E+E$E+E$E+E$E$E,2023/4/26,编译原理与技术讲义,21,移进归约分析冲突,归约-归约冲突e.g.20 文法G91）Statid(para_list)|expr:=expr2）para_listpara_list,para|para3）paraid4）exprid(expr_list)5）exprid6）expr_listexpr_list,expr|expr,2023/4/26,编译原理与技术讲义,22,e.g.20分析输入串id(id,id)$,分析栈输入串$id(id,id)$1)$id(expr,id)$2)$id(para,id)$,paraid，目标：过

10、程调用语句,exprid 目标：数组引用,2023/4/26,编译原理与技术讲义,23,LR分析器,高效易实现的自底向上的分析方法文法限制少，适用于大多数CFG（包括含左递归、左因子的文法）LR（k）分析器L 从左自右读（read from Left to right）R 构造最右推导的逆（for constructing a Rightmost derivation in reverse）k 向前看符号的个数（the number of input symbols of lookhead）,2023/4/26,编译原理与技术讲义,24,LR分析器,输入串,LR控制程序,LR分析表,状态 符号

11、 栈,输出,Top,Bottom,动作表Action,转移表GOTO,2023/4/26,编译原理与技术讲义,25,格局：状态符号栈 输入串 分析表动作表（Action）：S（$）shift,reduce,accept,error转移表（GOTO）：S VN S,LR分析器,2023/4/26,编译原理与技术讲义,26,分析算法初始，状态S0位于栈底（栈顶）；根据当前栈顶状态S和当前输入符号a，查action表，由actionS,a决定分析动作：si输入符a移入栈顶top（push a）；状态i移入栈顶top（push i）。rj 按第j个产生式（A）进行归约，首先将从栈顶top往栈中的|个状

12、态和|个符号（计2|个）弹出分析栈；设此时栈顶状态为T，再将符号A和状态S=GOTOT,A 依次移入分析栈（S在栈顶top）acc 输入串被接受，分析成功！error 输入串有错，调错误恢复程序,2023/4/26,编译原理与技术讲义,27,e.g.21 表达式文法G2的LR分析表,文法G2：（1）EE+T（2）ET（3）TT*F（4）TF（5）F（E）（6）F id,2023/4/26,编译原理与技术讲义,28,e.g.21 表达式文法G2的LR分析表,2023/4/26,编译原理与技术讲义,29,e.g.21 表达式文法G2的LR分析表（续）,2023/4/26,编译原理与技术讲义,30,

13、e.g.21 id*(id+id)$的移进-归约分析过程,2023/4/26,编译原理与技术讲义,31,e.g.21 id*(id+id)$的移进-归约分析过程,2023/4/26,编译原理与技术讲义,32,e.g.21 id*(id+id)$的移进-归约分析过程,2023/4/26,编译原理与技术讲义,33,活前缀（viable prefix）是规范（右）句型的前缀，它不包含句柄后的任何符号（即活前缀的长度不会超过句柄的最右端）。若AP，有如下规范推导，则，的前缀为右句型的活前缀。,识别活前缀的DFA,2023/4/26,编译原理与技术讲义,34,活前缀与句柄移进-归约分析过程中，分析栈内的

14、符号串构成活前缀（这表明已扫描过的输入串没有语法错误；事实上，也只有形成活前缀的符号才会被移入分析栈；分析的实质就是判断剩余输入串能否继续形成活前缀）活前缀不包含或部分包含句柄 此时期待着“匹配”句柄的输入串并将之移入栈顶；,bottom,2023/4/26,编译原理与技术讲义,35,活前缀与句柄 活前缀已完全包含句柄 此时句柄位于栈顶，需要进行归约。,bottom,句柄,A,bottom,2023/4/26,编译原理与技术讲义,36,识别活前缀的DFA,LR（0）项目产生式右部加“”；“”的左部表示已“看见”（分析识别过）的部分；而右部则是期望“看到”的部分。如：产生式AP，其LR（0）项目

15、有：A 期望看到产生的串（移进项目）A 已分析期望看到产生的串（移进项目）A、都分析完了（归约项目）特别的，空产生式A 的LR（0）项目只有一个：A（归约项目）,2023/4/26,编译原理与技术讲义,37,识别活前缀的NFA,拓展文法引入新产生式SS，S为新的开始符号NFA的状态：各个产生式的LR（0）项目；初态：SS 终态（唯一）：SSNFA的状态转换,i:AX,j:AX,X,h:AB,k:B,XVTVN,BVN,2023/4/26,编译原理与技术讲义,38,采用子集构造法转换上述的NFA到DFA闭包 closure（I）/I：NFA的状态子集即LR(0)项目集合1）I closure（I

16、）2）若项目ABI，BP，则项目 B closure（I）3）重复2）直至closure（I）不再增大 转移 goto（I，X）/XVTVNJ=goto（I，X）=closure（AX|AX I）,2023/4/26,编译原理与技术讲义,39,DFA识别的活前缀从DFA初态I0到任一状态Ij的路径上所“读过”的符号串。状态Ij可以指示下一步的“动作”。该DFA识别所有的活前缀；且只能识别活前缀。LR(0)项目规范族C=DFA的状态LR(0)有效项目项目A，如果有则项目A 对活前缀有效。对同一活前缀有效的（多个）LR（0）项目均在同一个项目集合（状态）中；而且同一LR（0）项目可以对多个活前缀有

17、效（即该项目可以出现在不同的项目集合中）。,2023/4/26,编译原理与技术讲义,40,LR(0)有效项目如果项目AB对活前缀有效，即有最右推导如果BP 则有以下最右推导，显然，项目B对活前缀也有效。项目AB和B应在同一个状态(项目集合)这就是closure（）函数,2023/4/26,编译原理与技术讲义,41,LR(0)有效项目如果项目AXI对活前缀有效，则项目AXJ=goto(I,X)显然对活前缀X有效。,2023/4/26,编译原理与技术讲义,42,e.g.22 识别文法G2活前缀的DFA,拓展文法G2（0）EE（1）EE+T（2）ET（3）TT*F（4）TF（5）F（E）（6）F i

18、d,DFA的初态I0=closure(EE)E EE E+TE TT T*FT FF（E）F id,2023/4/26,编译原理与技术讲义,43,I1:EE E E+T,I2:ET TT*F,I3:T F,I4:F(E)EE+T ET TT*F TF F(E)Fid,I5:F id,I0:E E E E+T E T T T*F T F F(E)F id,I7:TT*F F(E)Fid,I6:EE+T TT*F TF F(E)Fid,I8:F(E)EE+T,I11:F(E),I9:EE+T TT*F,I10:TT*F,E,T,id,F,(,+,*,(,E,T,F,id,T,F,(,id,F,(,

19、id,),+,*,2023/4/26,编译原理与技术讲义,44,e.g.23 对活前缀E+T*有效的LR(0)项目,E+T*的识别路径：I0E I1+I6T I9*I7项目集合（状态）I7中的项目对E+T*有效：TT*F F(E)Fid,EE+T E+T*F,EE+T E+T*F E+T*(E),EE+T E+T*F E+T*id,=E+=T*=F,=E+T*=(E)或 id,2023/4/26,编译原理与技术讲义,45,LR(0)分析仅取决于当前（栈顶）状态，由状态本身所包含的信息决定下一步动作。如，,LR(0)分析方法,I7:TT*F/转移 F(E)/移进下一输入符号 Fid/移进下一输入

20、符号 至于移入栈顶的符号不是(或 id，则报错,I10:TT*F/归约（不论下一输入符号是谁）,2023/4/26,编译原理与技术讲义,46,LR(0)分析方法,LR(0)分析表的构造 若AaI，且goto(I,a)=J，则actionI,a=sJ 若A I，则actionI,a=r A,aVT或$若SS I，则actionI,$=acc 若goto(I,B)=K，则GOTOI,B=K 其它为空白/error文法G是LR(0)的，如果它的LR(0)分析表项没有多重定义即动作冲突；或者它的LR(0)项目规范族中的任一状态不能同时含有移进和归约的LR(0)项目。e.g.23中表达式文法G2不是LR

21、(0)文法。如状态I1、I2、I9中有移进-归约冲突。（分析表略）,2023/4/26,编译原理与技术讲义,47,SLR（1）分析,LR(0)分析能力很弱！解决LR(0)分析冲突通过向前看一个符号（当前输入符）来解决移进-归约冲突 若状态I中同时含有移进和归约的LR(0)项目，如，Aa B 则 约定仅在当前输入符号Follow(B)时进行归约因为完成B的分析后，读到的输入符号应该是B的后继符号。而当前输入符号是a时则进行移进。如果a Follow(B)，冲突仍然存在！,2023/4/26,编译原理与技术讲义,48,SLR（1）分析,解决LR(0)分析冲突通过向前看一个符号（当前输入符）来解决归

22、约-归约冲突 若状态I中同时含有两个（或两个以上）归约LR(0)项目，如，A B 则 约定仅在当前输入符号Follow(A)时进行按A归约；仅当前输入符号Follow(B)时进行按B归约；如果Follow（A）Follow(B)，冲突仍然存在！,2023/4/26,编译原理与技术讲义,49,SLR（1）分析,SLR(1)分析表构造 若AaI，且goto(I,a)=J，则actionI,a=sJ 若A I，则actionI,b=r A,bFollow(A)若SS I，则actionI,$=acc 若goto(I,B)=K，则GOTOI,B=K 其它为空白/errorSLR(1)文法SLR分析表没

23、有多重定义条目表达式文法G2是SLR（1）的。,分析表见e.g.21,2023/4/26,编译原理与技术讲义,50,e.g.24 非SLR（1）的文法G9,文法G9(1)SL=R(2)SR(3)L*R(4)Lid(5)RLL：左值表达式R：右值表达式,文法G9是非二义性文法First(S)=*,id=First(L)=First(R)Follow(S)=$Follow(L)=,$Follow(R)=,$,2023/4/26,编译原理与技术讲义,51,e.g.24 识别G9活前缀的DFA,I0:S S S L=R S R L*R L id R L,I1:S S,I2:S L=R R L,I3:S

24、 R,I4:L*R R L L*R L id,I6:S L=R R L L*R L id,I8:L*R,I7:R L,I5:L id,I9:S L=R,S,L,R,id,*,=,L,*,R,L,R,id,id,*,2023/4/26,编译原理与技术讲义,52,状态I2中存在移进-归约冲突项目S L=R 要求当前输入符是=时移进，即action2,=s6 项目R L 则要求当前输入符是=或者$时归约，即action2,=r5 action2,$=r5,分析栈：0L2,=$输入串,移进后分析栈：0L2=6,$输入串,归约后分析栈：0R3,=$输入串,R=却不是文法G9的活前缀,2023/4/26,

25、编译原理与技术讲义,53,LR（1）分析器,SLR分析的归约定义在Follow集合名下，可能导致归约的“扩大化”，引起不必要的冲突，造成了SLR分析能力不强。LR(1)分析规范的LR分析，能够准确地将归约定义在有关符号名下（仅是Follow的子集），即这些符号只能是最左归约所对应最右推导逆过程的那一步中跟在左部非终结符后面的（终结）符号。LR(1)分析使得最左归约的分析过程与最右推导过程精确地对应，具有最强的分析能力。,2023/4/26,编译原理与技术讲义,54,LR(1)项目 A，a,识别活前缀的LR(1)项目集族（DFA）,LR(0)项目,搜索符,1），移进项目，与搜索符无关,2）=，归

26、约项目，当前输入符是搜索符时才进行归约,2023/4/26,编译原理与技术讲义,55,有效项目LR(1)项目 A，a 对活前缀有效，如果有最右推导过程，其中 a First($)。,识别活前缀的LR(1)项目集族,a即是右句型A$中跟在A后面的终结符；,当活前缀 出现在栈顶时，下一输入符是a时，才能将归约成A,2023/4/26,编译原理与技术讲义,56,识别活前缀的LR(1)项目集族,有效项目如果LR(1)项目 AB，a 对活前缀有效，则对于BP,LR(1)项目B,b对活前缀也有效。其最右推导过程如下，其中 a First($),而b First($)=First(a)=First(a)。显

27、然，项目 AB，a 和 B,b 应在同一状态(项目集合),2023/4/26,编译原理与技术讲义,57,识别活前缀的LR(1)项目集族,closure(I)1）I closure(I)2）若项目AB,aI，BP，则项目 B,b closure(I),bFirst(a)3）重复2）直至closure(I)不再增大goto(I,X)J=closure(AX,a|AX,a I)初始项目I0=closure(SS,$),2023/4/26,编译原理与技术讲义,58,LR(1)分析表,构造LR(1)分析表归约动作只填在搜索符名下；其它同SLR(1)LR(1)文法其LR(1)分析表没有多重定义表项。文法G

28、9虽不是SLR文法，但却是LR(1)文法。,2023/4/26,编译原理与技术讲义,59,e.g.25 识别G9活前缀的LR(1)部分项目集族,I0：SS,$SL=R,$SR,$L*R,=/$Lid,=/$RL,$,I2：SL=R,$RL,$,L,下一输入符是=时移进,只有碰到结束符$时才归约,冲突解决了！,2023/4/26,编译原理与技术讲义,60,e.g.26 文法G10的LR(1)分析表,文法G10(0)SS(1)SBB(2)BbB(3)Ba,I0=closure(SS,$)SS,$S BB,$B bB,a/bB a,a/b,Follow(S)=$Follow(B)=a,b,$Firs

29、t(S)=a,b First(B)=a,b,2023/4/26,编译原理与技术讲义,61,I0:SS,$SBB,$BbB,a/bBa,a/b,I1:SS,$,I2:SBB,$BbB,$Ba,$,I3:BbB,a/bBbB,a/bBa,a/b,I4:Ba,a/b,S,B,b,a,I5:SBB,$,B,I6:B bB,$BbB,$Ba,$,b,I7:Ba,$,a,I8:BbB,a/b,B,b,a,b,I9:B bB,$,B,a,e.g.26 识别活前缀的LR(1)项目集族,2023/4/26,编译原理与技术讲义,62,e.g.26 文法G10的LR(1)分析表,2023/4/26,编译原理与技术讲

30、义,63,e.g.26 文法G10的LR(1)分析表（续）,2023/4/26,编译原理与技术讲义,64,I0:SS SBBBbBBa,I1:SS,I2:SBBBbBBa,I3:BbBBbBBa,I4:Ba,S,B,b,a,I5:SBB,B,I8:BbB,B,b,a,e.g.27 识别文法G10活前缀的LR(0)项目集族,b,a,2023/4/26,编译原理与技术讲义,65,LALR(1)分析,LR(1)分析功能最强，但分析表远比SLR(1)大(状态数多)。同心集两个（以上）LR(1)项目集合若忽略搜索符后它们的LR(0)项目集合相同。e.g.26中状态I3与I6、I8与I9以及I4和I7分别

31、是同心集。LALR(1)分析 通过合并LR(1)项目集族中的同心集（即保持同心集合的LR(0)项目集合不变，而对应项目的搜索符加以合并同时调整相应的状态转换）以减少状态、压缩分析表。（合并后其状态数和相应的SLR(1)状态数一样，但带有搜索符）若状态I和J同心则goto(I,X)和goto(J,X)也同心。,2023/4/26,编译原理与技术讲义,66,I0:SS,$SBB,$BbB,a/bBa,a/b,I1:SS,$,I2:SBB,$BbB,$Ba,$,I36:BbB,a/b/$BbB,a/b/$Ba,a/b/$,I47:Ba,a/b/$,S,B,b,a,I5:SBB,$,B,I89:BbB

32、,a/b/$,B,b,a,e.g.28 文法G10的LALR项目集族合并例26中同心集,b,a,2023/4/26,编译原理与技术讲义,67,LALR(1)分析,合并同心集合后可能“新出现”的归约-归约冲突（由搜索符的合并而引起的）但合并同心集不会产生“新”的移进-归约冲突（若有移进-归约冲突，则在合并前已经存在）。分析能力介于SLR和LR（1）之间（why？）LALR分析表构造同LR(1)；其发现并报告错误可能比LR(1)要迟（作了一些无用的归约），但不会漏掉错误。,2023/4/26,编译原理与技术讲义,68,e.g.29 合并同心集合,文法G11S aAdS bBdS aBeS bAeA

33、 cB c,G11只产生四个句子：acd ace bcd bce,2023/4/26,编译原理与技术讲义,69,e.g.29 合并同心集合,文法G11S aAdS bBdS aBeS bAeA cB c,对活前缀ac有效的LR(1)项目集I A c,d B c,e why?,SaAdacd SaBeace,而对活前缀bc有效的LR(1)项目集J A c,e B c,d why?,SbAebce SbBdbcd,2023/4/26,编译原理与技术讲义,70,项目集I 和 J 显然是同心集合并之！合并后的项目集合Iij A c,d/e B c,e/d 出现（新的）归约-归约冲突即面临输入符e或者d

34、时，按Ac还是Bc来归约呢？而这一冲突在合并前是没有的！,e.g.29 合并同心集合,2023/4/26,编译原理与技术讲义,71,e.g.30 串ba$的LR分析,b a$,b a$,b a$,2023/4/26,编译原理与技术讲义,72,e.g.30 串ba$的LR分析,b a$,b a$,b a$,2023/4/26,编译原理与技术讲义,73,e.g.30 串ba$的LR分析,b a$,b a$,b a$,2023/4/26,编译原理与技术讲义,74,e.g.30 串ba$的LR分析,b a$,b a$,b a$,2023/4/26,编译原理与技术讲义,75,e.g.30 串ba$的LR

35、分析,b a$,b a$,b a$,错误定位点相同,2023/4/26,编译原理与技术讲义,76,非LR的上下文无关文法,二义性文法绝不是LR类文法（LR（0）、SLR（1），LR（1），LALR（1）存在非二义的文法G不是LR类文法。e.g.31文法G12产生语言L12=R|(a|b)*G12：S a S a S b S b S G12不是LR（K）文法，K0。,2023/4/26,编译原理与技术讲义,77,e.g.31文法G12关于串aabbaa$的最右推导。S a S a a a S a a a a b S b a a a a b b a a a a b b a a,非LR的上下文无关文

36、法,“推导出”前一半串时才用产生式S。而在LR分析中无法通过移入当前符号来判明是否到达串的中点（或读完一半的串），即在什么时候使用该空产生式上存在二义性（矛盾）。,2023/4/26,编译原理与技术讲义,78,非LR的上下文无关文法,识别文法G12活前缀的LR（0）部分项目集簇I0：S.S S.a S a S.b S b S.仅状态I0在面临a或b或$时归约；面临a或b时移进。存在移进/归约冲突！因而G12非SLR（1）文法！,2023/4/26,编译原理与技术讲义,79,识别文法G12活前缀的LR（1）部分项目集簇,非LR的上下文无关文法,I0:S.S,$S.a S a,$S.b S b,$

37、S.,$,I2:S a.S a,$S.a S a,a S.b S b,a S.,a,a,I0中冲突解决,I2中冲突依然存在,2023/4/26,编译原理与技术讲义,80,非LR的上下文无关文法,类似的，文法G13：S a S a|a 也不是LR（K）文法。e.g.32 产生语言L14=ambn|mn0的3个文法。（1）二义性文法G14（2）非二义非LR文法G15（3）LR（1）文法G16,2023/4/26,编译原理与技术讲义,81,e.g.32 产生L14=ambn|mn0的3个文法,（1）二义性文法G14S a S b|a S|,a a a a b b b,SaSb aaSbb aaaSb

38、bbaaaaSbbb aaaa bbb aaaabbb,SaS aaSb aaaSbbaaaaSbbb aaaa bbb aaaabbb,2023/4/26,编译原理与技术讲义,82,e.g.32 产生L14=ambn|mn0的3个文法,（1）二义性文法G14S a S b|a S|,SaSb aaSbb aaaSbbbaaaaSbbb aaaa bbb aaaabbb,SaS aaSb aaaSbbaaaaSbbb aaaa bbb aaaabbb,句柄不同,句柄已出现，应归约，即将栈顶的a看作多出来的。,句柄未出现，需移进b后才形成句柄，以便栈顶a与b的“配对”。,2023/4/26,编译

39、原理与技术讲义,83,e.g.32 产生L14=ambn|mn0的3个文法,（2）非二义非LR文法G15S a S b|A A a A|,a a a a b b b,SaSb aaSbb aaaSbbb aaaAbbb aaaaAbbb aaaabbb aaaabbb,2023/4/26,编译原理与技术讲义,84,（2）识别文法G15活前缀的部分LR(1)项目簇：,I0:S.S,$S.a S b,$S.A,$A.a A,$A.,$,I3:S a.S b,$S.a S b,b S.A,b A a.A,$A.a A,$/b A.,$/b,a,a,I5:S a.S b,b S.a S b,b S.A

40、,b A a.A,$/b A.a A,$/b A.,$/b,a,A,I7:归归冲突 S A.,b A a A.,$/b,即在输入串中含有多于一个的a，且含有b时，状态5面临b要进行归约（A的空产生式），然后进入状态7，此时面临输入符号b存在归归冲突。也就是说，如何看待栈顶的a：它是多出来的，则按A aA归约；它和b“配对”，则按 S A归约（希望形成aSb）。,2023/4/26,编译原理与技术讲义,85,e.g.32 产生L14=ambn|mn0的3个文法,（3）LR（1）文法G16S a S|A A a A b|,a a a a b b b,输入串含有多于一个a和b时，在读到b时，将首先用

41、A的空产生式进行归约，然后在移进b，形成aAb，再归约（再读入b，等等）。等全部的b读完后，将A归约为S，进一步形成aS而归约。,2023/4/26,编译原理与技术讲义,86,二义文法的应用,二义文法不是LR文法，但文法简单，分析表较小分析冲突的解决 通过算符的优先级与结合性E+E*(shift first)E+E+(reduce first)E*E*(reduce first)E*E+(reduce first)优先于移进if E then S else$产生式规则靠前的优先归约,2023/4/26,编译原理与技术讲义,87,LR分析的错误恢复,发现错误仅在查找动作表时，actionS,a=

42、error/空白；一般地，SLR和LALR分析器报告错误会比LR(1)分析器迟因为作了些无效的归约，但他们都不会把出错点后的输入符号移入分析栈。紧急方式错误恢复 分析栈：从栈顶往栈中寻找存在有非终结符A转移的状态S，即有S A S 或gotoS,A=S，弹出状态S以上的栈内容；将A和状态S压入栈。,2023/4/26,编译原理与技术讲义,88,LR分析的错误恢复,紧急方式错误恢复 输入串：将输入指针调整到aFollow(A)（同步符号）A的选择：较大的语法单位，如表达式、语句、分程序等,2023/4/26,编译原理与技术讲义,89,YACCYet Another Compiler Compil

43、er LALR分析器自动生成工具,YACC简介,yacc描述文件,yacc,y.tab.cyyparse(),y.tab.c lex.yy.c*.c,cc,可执行程序文件a.out,2023/4/26,编译原理与技术讲义,90,YACC描述文件,由三部分组成 定义段（definitions）规则段（rules）辅助程序段,2023/4/26,编译原理与技术讲义,91,定义段%/*合法的C声明、包含文件、宏定义等*/#include#include%单词符号的说明，如%token digit 算符优先级、结合性的说明（注意书写的先后次序）%left+-低优先级的算符说明位置在前%left*/%r

44、ight优先级越高，位置越后 开始符号（缺省时为第一个产生式的左部符号）%start symbol,2023/4/26,编译原理与技术讲义,92,规则段A:1 语义动作1|2 语义动作2|n 语义动作n|没有,则使用缺省的语义动作;产生式结束用分号标记 语义动作是C的语句序列（在一对中间），可以引用声明段中定义的C变量、宏等，还可以使用yacc的伪变量。,语义动作的一般是在产生式右部分析完，归约动作进行前执行。,2023/4/26,编译原理与技术讲义,93,规则段（续）yacc中的伪变量（类型缺省为整型）$-产生式左部非终结符的“值”$i-产生式右部第i个文法符号的“值”yacc中有一个与分析

45、栈“平行”的属性值栈如：E:E+T$=$1+$3;|T$=$1/*这是缺省的语义动作；可以省略*/;,2023/4/26,编译原理与技术讲义,94,辅助程序段用户自定义的C程序，如#include“lex.yy.c”main()void yyerror(char*s)printf(s);,2023/4/26,编译原理与技术讲义,95,e.g.33 简单的算术表达式计算器,/*定义段：*/%#include#include%token number%,2023/4/26,编译原理与技术讲义,96,e.g.33 简单的算术表达式计算器(续),/*规则段：*/Line:Expr printf(“th

46、e value is%dn”,$1);Expr:Expr+Term$=$1+$3;|Expr-Term$=$1-$3;|Term;Term:Term*Factor$=$1*$3;|Term/Factor if($3=0)printf(“divided by zero”）;exit(1);else$=$1/$3;,2023/4/26,编译原理与技术讲义,97,e.g.33 简单的算术表达式计算器(续),/*规则段：*/Term:Term*Factor|Term/Factor|Factor$=$1;Factor:(Expr)$=$2;|number;%,2023/4/26,编译原理与技术讲义,98

47、,/*程序段*/main()return yyparse();int yylex()int c;while(c=getchar()=);/skip blanks;if(isdigit(c)ungetc(c,stdin);scanf(“%d”,2023/4/26,编译原理与技术讲义,99,YACC中分析冲突的解决,移进归约冲突优先移进；yacc不报告可以由算符优先级、结合性规则解决的冲突。归约归约冲突产生式位置靠前的优先,2023/4/26,编译原理与技术讲义,100,YACC中错误恢复,出错产生式A error 错误发生时，yacc将从分析栈中寻找含有形如项目A error 的状态s；弹出状态

48、s上的所有内容，将特殊记号error移入栈顶，同时在输入串中寻找和匹配的输入并移入栈顶，此时分析器将把位于栈顶的error 和归约成A，使分析得以继续。如：Stat error;/语句出错时将跳至下一分号,2023/4/26,编译原理与技术讲义,101,YACC内部使用符号,名称含义y.tab.cyacc 输出文件名y.tab.hyacc 生成的头文件yyparseyacc分析主函数yylval属性栈顶（对应符号的）值yyerror错误信息的输出函数erroryacc中“错误”伪记号yyerrok出错后重置分析栈于正常工作状态YYSTYPE定义属性栈值类型yydebug值为1时，产生分析器运行信息,2023/4/26,编译原理与技术讲义,102,YACC中的定义机制,定义含义%token定义记号（终结符）%start定义开始符号%union定义YYSTYPE,允许符号的值有不同的类型%type定义符号的值类型%left算符优先级、左、右结合性%right位置越前，优先级越低%nonassoc算符不可结合，如abc,