编译原理与技术 自底向上分析.ppt
2019/10/25,编译原理与技术讲义,1,编译原理与技术,自底向上分析,2019/10/25,编译原理与技术讲义,2,自底向上分析,移进归约分析 分析树的构建 从叶子结点开始，逐步构造各内部结点直至根结点出现。 分析技术的关键句柄的识别 句柄（handle）是什么？ 简单讲，句柄是一个产生式的右部；自底向上分析（移进归约分析）过程，其实就是发现句柄并将句柄（产生式右部）替换成相应左部非终结符的过程。该替换称为最左归约，它对应着某最右推导逆过程的一步。,2019/10/25,编译原理与技术讲义,3,自底向上分析,分析技术的关键句柄的识别 句柄（handle）是什么？ 一般地，如果有以下最右推导序列， 则产生式A及其在右句型中的位置称为右句型的句柄。,2019/10/25,编译原理与技术讲义,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 $,最左归约,最右推导,2019/10/25,编译原理与技术讲义,5,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,2019/10/25,编译原理与技术讲义,6,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,2019/10/25,编译原理与技术讲义,7,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,2019/10/25,编译原理与技术讲义,8,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,2019/10/25,编译原理与技术讲义,9,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,2019/10/25,编译原理与技术讲义,10,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,B,2019/10/25,编译原理与技术讲义,11,自底向上分析,e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd,串abbcde$的对应分析树的建立过程。,输入串 a b b c d e $,A,A,B,S,2019/10/25,编译原理与技术讲义,12,移进归约分析,e.g.17 用栈来实现串abbcde$的分析（1）,2019/10/25,编译原理与技术讲义,13,移进归约分析,e.g.17 用栈来实现串abbcde$的分析（2）,分析成功！,2019/10/25,编译原理与技术讲义,14,移进归约分析,四种分析动作（action） 移进（shift）将当前输入符号移入栈顶top（why？） 归约（reduce）当“句柄”出现在栈顶（从栈中某处到栈顶top），则将“句柄”从栈顶弹弹出，并将相应产生式左部非终结符置入栈顶top。（when？） 接受（accept）分析成功！ 报错（error）出现语法错误，调错误恢复例程,2019/10/25,编译原理与技术讲义,15,移进归约分析,分析动作冲突 移进-归约冲突（shift-reduce conflict） 当“句柄”处于栈顶时，分析动作指示既可以将下一输入符号移入栈顶top，又可以实施归约操作。如何动作呢？ 归约-归约冲突（reduce-reduce conflict） 位于栈顶的“句柄”，同时匹配两个（以上）产生式的右部。选谁呢？,怎么可能呢？,2019/10/25,编译原理与技术讲义,16,移进归约分析冲突,二义文法G不适合移进归约分析 e.g. 18 移进-归约冲突 文法G7： S if E then S | if E then S else S S a,$. if E then S,“句柄”？,else. ,分析栈,输入串：,当前输入符号,2019/10/25,编译原理与技术讲义,17,$. if E then S else,栈顶,. ,分析栈,输入串：,$ S,else . ,分析栈,输入串：,归约动作,移进动作,文法G7: S if E then S | if E then S else S | a,期待新的“长句柄”,2019/10/25,编译原理与技术讲义,18,e.g.19 二义性文法G8如下： EE+E | E * E | (E) | id 输入串id+id+id$的最右推导： 1）EE+EE+idE+E+idE+id+idid+id+id 2）EE+EE+E+EE+E+idE+id+idid+id+id 带下划线的符号串是相应句型的句柄。,移进归约分析冲突,2019/10/25,编译原理与技术讲义,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+,归约,移进,2019/10/25,编译原理与技术讲义,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+id $ $ $E+E+E $E+E $ $ $E+E $E $ $ $E,2019/10/25,编译原理与技术讲义,21,移进归约分析冲突,归约-归约冲突 e.g.20 文法G9 1）Statid ( para_list ) | expr := expr 2）para_listpara_list , para | para 3）paraid 4）exprid ( expr_list ) 5）exprid 6）expr_listexpr_list , expr | expr,2019/10/25,编译原理与技术讲义,22,e.g.20分析输入串id(id,id)$,分析栈 输入串 $ id ( id , id ) $ 1) $ id ( expr , id ) $ 2) $ id ( para , id ) $,paraid，目标：过程调用语句,exprid 目标：数组引用,2019/10/25,编译原理与技术讲义,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）,2019/10/25,编译原理与技术讲义,24,LR分析器,输入串,LR控制程序,LR分析表,状态 符号 栈,输出,Top,Bottom,动作表 Action,转移表 GOTO,2019/10/25,编译原理与技术讲义,25,格局： 状态符号栈 输入串 分析表 动作表（Action）： S （$） shift , reduce, accept, error 转移表（GOTO）： S VN S,LR分析器,2019/10/25,编译原理与技术讲义,26,分析算法 初始，状态S0位于栈底（栈顶）； 根据当前栈顶状态S和当前输入符号a，查action表，由actionS,a决定分析动作： si输入符a移入栈顶top（push a ）；状态i移入栈顶top（push i）。 rj 按第j个产生式（A）进行归约，首先将从栈顶top往栈中的|个状态和|个符号（计2×|个）弹出分析栈；设此时栈顶状态为T，再将符号A和状态S=GOTOT,A 依次移入分析栈（S在栈顶top） acc 输入串被接受，分析成功！ error 输入串有错，调错误恢复程序,2019/10/25,编译原理与技术讲义,27,e.g.21 表达式文法G2的LR分析表,文法G2： （1）EE + T （2）ET （3）TT * F （4）TF （5）F（ E ） （6）F id,2019/10/25,编译原理与技术讲义,28,e.g.21 表达式文法G2的LR分析表,2019/10/25,编译原理与技术讲义,29,e.g.21 表达式文法G2的LR分析表（续）,2019/10/25,编译原理与技术讲义,30,e.g.21 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,31,e.g.21 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,32,e.g.21 id*(id+id)$的移进-归约分析过程,2019/10/25,编译原理与技术讲义,33,活前缀（viable prefix） 是规范（右）句型的前缀，它不包含句柄后的任何符号（即活前缀的长度不会超过句柄的最右端）。若AP，有如下规范推导， 则，的前缀为右句型的活前缀。,识别活前缀的DFA,2019/10/25,编译原理与技术讲义,34,活前缀与句柄 移进-归约分析过程中，分析栈内的符号串构成活前缀（这表明已扫描过的输入串没有语法错误；事实上，也只有形成活前缀的符号才会被移入分析栈；分析的实质就是判断剩余输入串能否继续形成活前缀） 活前缀不包含或部分包含句柄 此时期待着“匹配”句柄的输入串并将之移入栈顶；,bottom,2019/10/25,编译原理与技术讲义,35,活前缀与句柄 活前缀已完全包含句柄 此时句柄位于栈顶，需要进行归约。,bottom,句柄,A,bottom,2019/10/25,编译原理与技术讲义,36,识别活前缀的DFA,LR（0）项目 产生式右部加 “” ； “”的左部表示已“看见”（分析识别过）的部分；而右部则是期望“看到”的部分。如：产生式AP，其LR（0）项目有： A 期望看到产生的串（移进项目） A 已分析期望看到产生的串（移进项目） A 、都分析完了 （ 归约项目） 特别的，空产生式A 的LR（0）项目只有一个： A （ 归约项目）,2019/10/25,编译原理与技术讲义,37,识别活前缀的NFA,拓展文法 引入新产生式SS ， S为新的开始符号 NFA的状态： 各个产生式的LR（0）项目； 初态：SS 终态（唯一） ： SS NFA的状态转换,i: AX,j: AX,X,h: AB,k: B ,XVTVN,BVN,2019/10/25,编译原理与技术讲义,38,采用子集构造法转换上述的NFA到DFA 闭包 closure（I） / I：NFA的状态子集即LR(0)项目集合 1）I closure（I） 2）若项目ABI，BP，则项目 B closure（I） 3）重复2）直至closure（I）不再增大 转移 goto（I，X） / XVTVN J=goto（I，X）=closure（AX| AX I）,2019/10/25,编译原理与技术讲义,39,DFA识别的活前缀从DFA初态I0到任一状态Ij的路径上所“读过”的符号串。状态Ij可以指示下一步的“动作”。 该DFA识别所有的活前缀；且只能识别活前缀。 LR(0)项目规范族C=DFA的状态 LR(0)有效项目 项目A，如果有 则项目A 对活前缀有效。 对同一活前缀有效的（多个）LR（0）项目均在同一个项目集合（状态）中；而且同一LR（0）项目可以对多个活前缀有效（即该项目可以出现在不同的项目集合中）。,2019/10/25,编译原理与技术讲义,40,LR(0)有效项目 如果项目AB对活前缀有效，即有最右推导 如果BP 则有以下最右推导， 显然，项目B对活前缀也有效。 项目AB和B应在同一个状态(项目集合) 这就是closure（）函数,2019/10/25,编译原理与技术讲义,41,LR(0)有效项目 如果项目AXI对活前缀有效，则项目 AXJ=goto(I,X)显然对活前缀X有效。,2019/10/25,编译原理与技术讲义,42,e.g.22 识别文法G2活前缀的DFA,拓展文法G2 （0）EE （1）EE + T （2）ET （3）TT * F （4）TF （5）F（ E ） （6）F id,DFA的初态I0= closure(EE) E E E E + T E T T T * F T F F （ E ） F id,2019/10/25,编译原理与技术讲义,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,(,id,),+,*,2019/10/25,编译原理与技术讲义,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,2019/10/25,编译原理与技术讲义,45,LR(0)分析仅取决于当前（栈顶）状态，由状态本身所包含的信息决定下一步动作。如，,LR(0)分析方法,I7:TT * F / 转移 F(E) / 移进下一输入符号 Fid / 移进下一输入符号 至于移入栈顶的符号不是 ( 或 id，则报错,I10:TT*F / 归约（不论下一输入符号是谁）,2019/10/25,编译原理与技术讲义,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(0)文法。 如状态I1、I2、I9中有移进-归约冲突。（分析表略）,2019/10/25,编译原理与技术讲义,47,SLR（1）分析,LR(0)分析能力很弱！ 解决LR(0)分析冲突 通过向前看一个符号（当前输入符）来解决 移进-归约冲突 若状态I中同时含有移进和归约的LR(0)项目，如， Aa B 则 约定仅在当前输入符号Follow(B)时进行归约因为完成B的分析后，读到的输入符号应该是B的后继符号。而当前输入符号是a时则进行移进。如果a Follow(B)，冲突仍然存在！,2019/10/25,编译原理与技术讲义,48,SLR（1）分析,解决LR(0)分析冲突 通过向前看一个符号（当前输入符）来解决 归约-归约冲突 若状态I中同时含有两个（或两个以上）归约LR(0)项目，如，A B 则 约定仅在当前输入符号Follow(A)时进行按A归约；仅当前输入符号Follow(B)时进行按B归约； 如果Follow（A） Follow(B) ，冲突仍然存在！,2019/10/25,编译原理与技术讲义,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 其它为空白/error SLR(1)文法SLR分析表没有多重定义条目 表达式文法G2是SLR（1）的。,分析表见e.g.21,2019/10/25,编译原理与技术讲义,50,e.g.24 非SLR（1）的文法G9,文法G9 (1) SL = R (2) SR (3) L*R (4) Lid (5) RL L：左值表达式 R：右值表达式,文法G9是非二义性文法 First(S)=*,id=First(L)=First(R) Follow(S)=$ Follow(L)= = , $ Follow(R)= =, $ ,2019/10/25,编译原理与技术讲义,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 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,*,2019/10/25,编译原理与技术讲义,52,状态I2中存在移进-归约冲突 项目S L =R 要求当前输入符是=时移进 ，即 action2,= = s6 项目R L 则要求当前输入符是=或者$时归约，即 action2,= = r5 action2,$ = r5,分析栈： 0L2,= $ 输入串,移进后分析栈： 0L2=6,$ 输入串,归约后分析栈： 0R3,= $ 输入串,R= 却不是文法G9的活前缀,2019/10/25,编译原理与技术讲义,53,LR（1）分析器,SLR分析的归约定义在Follow集合名下，可能导致归约的“扩大化”，引起不必要的冲突，造成了SLR分析能力不强。 LR(1)分析规范的LR分析，能够准确地将归约定义在有关符号名下（仅是Follow的子集），即这些符号只能是最左归约所对应最右推导逆过程的那一步中跟在左部非终结符后面的（终结）符号。LR(1)分析使得最左归约的分析过程与最右推导过程精确地对应，具有最强的分析能力。,2019/10/25,编译原理与技术讲义,54,LR(1)项目 A，a ,识别活前缀的LR(1)项目集族（DFA）,LR(0) 项目,搜索符,1） ，移进项目，与搜索符无关,2） =，归约项目，当前输入符是搜索符时才进行归约,2019/10/25,编译原理与技术讲义,55,有效项目 LR(1)项目 A，a 对活前缀有效，如果有最右推导过程，其中 a First( $ )。,识别活前缀的LR(1)项目集族,a即是右句型A$中跟在A后面的终结符；,当活前缀 出现在栈顶时，下一输入符是a时，才能将归约成A,2019/10/25,编译原理与技术讲义,56,识别活前缀的LR(1)项目集族,有效项目 如果LR(1)项目 AB，a 对活前缀有效，则对于BP, LR(1)项目B ,b对活前缀也有效。其最右推导过程如下， 其中 a First( $ ), 而b First( $ )=First(a) =First(a) 。显然， 项目 AB，a 和 B ,b 应在同一状态(项目集合),2019/10/25,编译原理与技术讲义,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,$ ),2019/10/25,编译原理与技术讲义,58,LR(1)分析表,构造LR(1)分析表 归约动作只填在搜索符名下； 其它同SLR(1) LR(1)文法其LR(1)分析表没有多重定义表项。 文法G9虽不是SLR文法，但却是LR(1)文法。,2019/10/25,编译原理与技术讲义,59,e.g.25 识别G9活前缀的LR(1)部分项目集族,I0：SS,$ SL=R,$ SR,$ L*R,=/$ Lid,=/$ RL,$,I2：SL=R,$ RL,$,L,下一输入符是=时移进,只有碰到结束符$时才归约,冲突解决了！,2019/10/25,编译原理与技术讲义,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/b B a, a/b,Follow(S)=$ Follow(B)=a,b,$ First(S)=a,b First(B)=a,b,2019/10/25,编译原理与技术讲义,61,I0: SS,$ SBB,$ BbB, a/b Ba, a/b,I1: SS,$,I2: SBB,$ BbB, $ Ba, $,I3: BbB, a/b BbB, a/b Ba, 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)项目集族,2019/10/25,编译原理与技术讲义,62,e.g.26 文法G10的LR(1)分析表,2019/10/25,编译原理与技术讲义,63,e.g.26 文法G10的LR(1)分析表（续）,2019/10/25,编译原理与技术讲义,64,I0: SS SBB BbB Ba,I1: SS,I2: SBB BbB Ba,I3: BbB BbB Ba,I4: Ba,S,B,b,a,I5: SBB,B,I8: BbB,B,b,a,e.g.27 识别文法G10 活前缀的LR(0)项目集族,b,a,2019/10/25,编译原理与技术讲义,65,LALR(1)分析,LR(1)分析功能最强，但分析表远比SLR(1) 大(状态数多) 。 同心集两个（以上）LR(1)项目集合若忽略搜索符后它们的LR(0)项目集合相同。 e.g.26中状态I3与I6、I8与I9以及I4和I7分别是同心集。 LALR(1)分析 通过合并LR(1)项目集族中的同心集（即保持同心集合的LR(0)项目集合不变，而对应项目的搜索符加以合并同时调整相应的状态转换）以减少状态、压缩分析表。（合并后其状态数和相应的SLR(1)状态数一样，但带有搜索符） 若状态I和J同心则goto(I,X)和goto(J,X)也同心。,2019/10/25,编译原理与技术讲义,66,I0: SS,$ SBB,$ BbB, a/b Ba, 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, a/b/$,B,b,a,e.g.28 文法G10的LALR项目集族合并例26中同心集,b,a,2019/10/25,编译原理与技术讲义,67,LALR(1)分析,合并同心集合后可能“新出现”的归约-归约冲突（由搜索符的合并而引起的） 但合并同心集不会产生“新”的移进-归约冲突（若有移进-归约冲突，则在合并前已经存在）。 分析能力介于SLR和LR（1）之间（why？） LALR分析表构造同LR(1)；其发现并报告错误可能比LR(1)要迟（作了一些无用的归约），但不会漏掉错误。,2019/10/25,编译原理与技术讲义,68,e.g.29 合并同心集合,文法G11 S aAd S bBd S aBe S bAe A c B c,G11只产生四个句子： acd ace bcd bce,2019/10/25,编译原理与技术讲义,69,e.g.29 合并同心集合,文法G11 S aAd S bBd S aBe S bAe A c B 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,2019/10/25,编译原理与技术讲义,70,项目集I 和 J 显然是同心集合并之！ 合并后的项目集合Iij A c,d/e B c,e/d 出现（新的）归约-归约冲突即面临输入符e或者d时，按Ac还是Bc来归约呢？ 而这一冲突在合并前是没有的！,e.g.29 合并同心集合,2019/10/25,编译原理与技术讲义,71,e.g.30 串ba$的LR分析,b a $,b a $,b a $,2019/10/25,编译原理与技术讲义,72,e.g.30 串ba$的LR分析,b a $,b a $,b a $,2019/10/25,编译原理与技术讲义,73,e.g.30 串ba$的LR分析,b a $,b a $,b a $,2019/10/25,编译原理与技术讲义,74,e.g.30 串ba$的LR分析,b a $,b a $,b a $,2019/10/25,编译原理与技术讲义,75,e.g.30 串ba$的LR分析,b a $,b a $,b a $,错误定位点相同,2019/10/25,编译原理与技术讲义,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。,2019/10/25,编译原理与技术讲义,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的上下文无关文法,“推导出”前一半串时才用产生式S。而在LR分析中无法通过移入当前符号来判明是否到达串的中点（或读完一半的串），即在什么时候使用该空产生式上存在二义性（矛盾）。,2019/10/25,编译原理与技术讲义,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）文法！,2019/10/25,编译原理与技术讲义,79,识别文法G12活前缀的LR（1）部分项目集簇,非LR的上下文无关文法,I0: S .S, $ S . a S a, $ S . b S b, $ S . , $,I2: S a.S a, $ S . a S a, a S . b S b, a S . , a,a,I0中冲突解决,I2中冲突依然存在,2019/10/25,编译原理与技术讲义,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,2019/10/25,编译原理与技术讲义,81,e.g.32 产生L14=ambn|mn0的3个文法,（1）二义性文法G14 S a S b | a S | ,a a a a b b b,SaSb aaSbb aaaSbbb aaaaSbbb aaaa bbb aaaabbb,SaS aaSb aaaSbb aaaaSbbb aaaa bbb aaaabbb,2019/10/25,编译原理与技术讲义,82,e.g.32 产生L14=ambn|mn0的3个文法,（1）二义性文法G14 S a S b | a S | ,SaSb aaSbb aaaSbbb aaaaSbbb aaaa bbb aaaabbb,SaS aaSb aaaSbb aaaaSbbb aaaa bbb aaaabbb,句柄不同,句柄已出现，应归约，即将栈顶的a看作多出来的。,句柄未出现，需移进b后才形成句柄，以便栈顶a与b的“配对” 。,2019/10/25,编译原理与技术讲义,83,e.g.32 产生L14=ambn|mn0的3个文法,（2）非二义非LR文法G15 S a S b | A A a A | ,a a a a b b b,SaSb aaSbb aaaSbbb aaaAbbb aaaaAbbb aaaabbb aaaabbb,2019/10/25,编译原理与技术讲义,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, 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）。,2019/10/25,编译原理与技术讲义,85,e.g.32 产生L14=ambn|mn0的3个文法,（3）LR（1）文法G16 S a S | A A a A b | ,a a a a b b b,输入串含有多于一个a和b时，在读到b时，将首先用A的空产生式进行归约，然后在移进b，形成aAb，再归约（再读入b，等等）。等全部的b读完后，将A归约为S，进一步形成aS而归
