编译原理与技术讲义

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

2、称为右句型的句柄。,APA*Srmrm 2022-4-13编译原理与技术讲义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 $最左归约最右推导2022-4-13编译原理与技术讲义5自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串abbcde$的对应分析树的建立过程。输入串 a b b c d e $ 2022-4-13编译原理与技术讲义6自底向上分析e.g.17 文法G6 1）Sa

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

4、SaABe 2）AAbc 3）Ab 4）Bd 串abbcde$的对应分析树的建立过程。输入串 a b b c d e $ AA2022-4-13编译原理与技术讲义10自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串abbcde$的对应分析树的建立过程。输入串 a b b c d e $ AAB2022-4-13编译原理与技术讲义11自底向上分析e.g.17 文法G6 1）SaABe 2）AAbc 3）Ab 4）Bd 串abbcde$的对应分析树的建立过程。输入串 a b b c d e $ AABS2022-4-13编译原理与技术讲义12移进归约分析e.

5、g.17 用栈来实现用栈来实现串abbcde$的分析（1）分析栈输入串动作$ a b b c d e $ ab b c d e $移进a$ a bb c d e $移进b$ a Ab c d e $归约：Ab$ a A bc d e $移进b$ a A b cd e $移进c2022-4-13编译原理与技术讲义13移进归约分析e.g.17 用栈来实现用栈来实现串abbcde$的分析（2）分析栈输入串动作$ a A b cd e $移进c$ a Ad e $归约: AAbc$ a A de $移进d$ a A Be $归约：Bd$ a A B e$移进e$ S$r: SaABe分析成功！2022

6、-4-13编译原理与技术讲义14移进归约分析四种分析动作（action） 移进（shift）将当前输入符号移入栈顶top（why？） 归约（reduce）当“句柄”出现在栈顶（从栈中某处到栈顶top），则将“句柄”从栈顶弹弹出，并将相应产生式左部非终结符置入栈顶top。（when？） 接受（accept）分析成功！ 报错（error）出现语法错误，调错误恢复例程2022-4-13编译原理与技术讲义15移进归约分析分析动作冲突 移进-归约冲突（shift-reduce conflict）当“句柄”处于栈顶时，分析动作指示既可以将下一输入符号移入栈顶top，又可以实施归约操作。如何动作呢？ 归约-

7、归约冲突（reduce-reduce conflict） 位于栈顶的“句柄”，同时匹配两个（以上）产生式的右部。选谁呢？怎么可能呢？2022-4-13编译原理与技术讲义16移进归约分析冲突二义文法G不适合移进归约分析 e.g. 18 移进-归约冲突文法G7： S if E then S | if E then S else S S a$. if E then S“句柄”？else. 分析栈输入串：当前输入符号2022-4-13编译原理与技术讲义17$. if E then S else栈顶. 分析栈输入串：$ Selse . 分析栈输入串：归约动作移进动作文法G7: S if E then S

8、 | if E then S else S | a期待新的期待新的“长长句柄句柄”2022-4-13编译原理与技术讲义18e.g.19 二义性文法G8如下：EE+E | E * E | (E) | id 输入串id+id+id$的最右推导：1）EE+EE+idE+E+idE+id+idid+id+id2）EE+EE+E+EE+E+idE+id+idid+id+id带下划线的符号串是相应句型的句柄。移进归约分析冲突2022-4-13编译原理与技术讲义19e.g.19输入串id+id+id$的栈分析过程分析1）输入串分析2）$ id+id+id$ $id +id+id$ $id$E +id+id$

9、 $E $E+ id+id$ $E+$E+id +id$ $E+id$E+E +id$ $E+E$E +id$ id$ $E+E+归约移进2022-4-13编译原理与技术讲义20e.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 $ $ $E2022-4-13编译原理与技术讲义21移进归约分析冲突归约-归约冲突e.g.20 文法G91）Statid ( para_list ) | expr := expr

10、2）para_listpara_list , para | para3）paraid4）exprid ( expr_list ) 5）exprid6）expr_listexpr_list , expr | expr2022-4-13编译原理与技术讲义22e.g.20分析输入串id(id,id)$分析栈输入串 $ id ( id , id ) $1) $ id ( expr , id ) $2) $ id ( para , id ) $paraid，目标：过程调用语句exprid 目标：数组引用2022-4-13编译原理与技术讲义23LR分析器高效易实现的自底向上的分析方法文法限制少，适用于大多

11、数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）2022-4-13编译原理与技术讲义24LR分析器输入串LR控制程序LR分析表SmXm.S0a1.ai.$状态 符号 栈输出TopBottom动作表Action转移表GOTO2022-4-13编译原理与技术讲义25格局： 状态符号栈 输入串 分析表 动作

12、表（Action）：S （$） shift , reduce, accept, error 转移表（GOTO）：S VN SLR分析器2022-4-13编译原理与技术讲义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 输入串被

13、接受，分析成功！ error 输入串有错，调错误恢复程序2022-4-13编译原理与技术讲义27e.g.21 表达式文法G2的LR分析表文法G2：（1）EE + T（2）ET（3）TT * F（4）TF（5）F（ E ）（6）F id 2022-4-13编译原理与技术讲义28e.g.21 表达式文法G2的LR分析表状态actiongotoid+*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4932022-4-13编译原理与技术讲义29e.g.21 表达式文法G2的LR分析表（续）状态actiongotoid+*()$ET

14、F7s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r52022-4-13编译原理与技术讲义30e.g.21 id*(id+id)$的移进-归约分析过程分析栈输入串输出0id*(id+id)$0id5*(id+id)$s5:移进id0F3*(id+id)$r6:Fid0T2*(id+id)$r4:TF0T2*7(id+id)$s7:移进*0T2*7(4id+id)$s4:移进(0T2*7(4id5+id)$s5:移进id2022-4-13编译原理与技术讲义31e.g.21 id*(id+id)$的移进-归约分析过程输入串输出分析栈+id)$s5:移进id0T2*7

15、(4id5+id)$r6:Fid0T2*7(4F3+id)$r4:TF0T2*7(4T2+id)$r2:ET0T2*7(4E8id)$s6:移进+0T2*7(4E8+60T2*7(4E8+6id5)$s5:移进id0T2*7(4E8+6F3)$r6:Fid2022-4-13编译原理与技术讲义32e.g.21 id*(id+id)$的移进-归约分析过程输入串输出分析栈0T2*7(4E8+6F3)$r6:Fid0T2*7(4E8+6T9)$r4:TF0T2*7(4E8)$r1:EE+T0T2*7(4E8)11$s11:移进)0T2*7F10$r5:F(E)0T2$r3:TT*F0E1$r2:ET0

16、E1$acc2022-4-13编译原理与技术讲义33活前缀（viable prefix）是规范（右）句型的前缀，它不包含句柄后的任何符号（即活前缀的长度不会超过句柄的最右端）。若AP，有如下规范推导， 则，的前缀为右句型的活前缀。识别活前缀的DFA*RRSA2022-4-13编译原理与技术讲义34活前缀与句柄移进移进-归约分析过程中，分析栈内的符号串构成活归约分析过程中，分析栈内的符号串构成活前缀（这表明已扫描过的输入串没有语法错误；前缀（这表明已扫描过的输入串没有语法错误；事实上，也只有形成活前缀的符号才会被移入分事实上，也只有形成活前缀的符号才会被移入分析栈；析栈；分析的实质就是判断剩余输

17、入串能否继续分析的实质就是判断剩余输入串能否继续形成活前缀）形成活前缀） 活前缀不包含或部分包含句柄 此时期待着“匹配”句柄的输入串并将之移入栈顶； $bottom2022-4-13编译原理与技术讲义35活前缀与句柄 活前缀已完全包含句柄 此时句柄位于栈顶，需要进行归约。 $bottom句柄A $bottom2022-4-13编译原理与技术讲义36识别活前缀的DFALR（0）项目产生式右部加 “” ； “”的左部表示已“看见”（分析识别过）的部分；而右部则是期望“看到”的部分。如：产生式AP，其LR（0）项目有：A 期望看到产生的串（移进项目移进项目） A 已分析期望看到产生的串（移进项目）

18、A 、都分析完了 （ 归约项目归约项目）特别的，空产生式A 的LR（0）项目只有一个只有一个： A （ 归约项目归约项目）2022-4-13编译原理与技术讲义37识别活前缀的NFA拓展文法引入新产生式SS ， S为新的开始符号NFA的状态：各个产生式的各个产生式的LR（0）项目；）项目；初态：初态：S S 终态终态（唯一） ： SS NFA的状态转换i: AXj: AXXh: ABk: B XVTVNBVN2022-4-13编译原理与技术讲义38采用子集构造法转换上述的NFA到DFA闭包 closure（I） / I：NFA的状态子集即LR(0)项目集合1）I closure（I）2）若项目A

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

20、（状态）中；而且同一而且同一LR（0）项目）项目可以对多个活前缀有效（即该项目可以出现在不可以对多个活前缀有效（即该项目可以出现在不同的项目集合中）同的项目集合中）。*RRSA 2022-4-13编译原理与技术讲义40LR(0)有效项目如果项目AB对活前缀有效，即有最右推导如果BP 则有以下最右推导， 显然，项目B对活前缀也有效。项目AB和B应在同一个状态(项目集合) 这就是closure（）函数*RRSBA*RRRRSBBA 2022-4-13编译原理与技术讲义41LR(0)有效项目如果项目AXI对活前缀有效，则项目AXJ=goto(I,X)显然对活前缀X有效。2022-4-13编译原理与技

21、术讲义42e.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 EE E + TE TT T * FT FF （ E ）F id 2022-4-13编译原理与技术讲义43I1:EE E E + TI2:ET TT * FI3:T F I4:F(E) EE + T ET TT * F TF F(E) FidI5:F id I0:E E E E + T E T T T * F T F F (E) F idI7:TT * F F(E) FidI6:EE +

22、T TT * F TF F(E) FidI8:F(E) EE + TI11:F(E) I9:EE + T TT * F I10:TT*F ETidF(+*(ETFidTF(idF(id)+*2022-4-13编译原理与技术讲义44e.g.23 对活前缀E+T*有效的LR(0)项目E+T*的识别路径：I0E I1+ I6T I9* I7项目集合（状态）I7中的项目对E+T*有效： TT *F F(E) FidEE+T E+T*FEE+T E+T*F E+T*(E)EE+T E+T*F E+T*id=E+ = T* =F=E+T* = =(E) 或 id2022-4-13编译原理与技术讲义45LR

23、(0)分析仅取决于当前（栈顶）状态仅取决于当前（栈顶）状态，由状态本身所包含的信息决定下一步动作。如，LR(0)分析方法I7:TT * F / 转移 F(E) / 移进下一输入符号 Fid / 移进下一输入符号 至于移入栈顶的符号不是 ( 或 id，则报错I10:TT*F / 归约（不论下一输入符号是谁） 2022-4-13编译原理与技术讲义46LR(0)分析方法LR(0)分析表的构造 若AaI，且goto(I,a)=J，则actionI,a=sJ 若A I，则actionI,a = r A,a VT或或$ 若SS I，则actionI,$ = acc 若goto(I,B)=K，则GOTOI,

24、B=K 其它为空白/error文法G是LR(0)的，如果它的LR(0)分析表项没有多重定义即动作冲突；或者它的LR(0)项目规范族中的任一状态不能同时含有移进和归约的LR(0)项目。e.g.23中表达式文法G2不是LR(0)文法。如状态I1、I2、I9中有移进-归约冲突。（分析表略）2022-4-13编译原理与技术讲义47SLR（1）分析LR(0)分析能力很弱！解决LR(0)分析冲突通过向前看一个符号（当前输入符）来解决移进-归约冲突 若状态I中同时含有移进和归约的LR(0)项目，如， Aa B 则 约定仅在当前输入符号仅在当前输入符号 Follow(B)时进行归约时进行归约因为完成B的分析后

25、，读到的输入符号应该是B的后继符号。而当前输入符而当前输入符号是号是a时则进行移进。时则进行移进。如果如果a Follow(B)，冲突仍，冲突仍然存在！然存在！2022-4-13编译原理与技术讲义48SLR（1）分析解决LR(0)分析冲突通过向前看一个符号（当前输入符）来解决归约-归约冲突 若状态I中同时含有两个（或两个以上）归约LR(0)项目，如，A B 则 约定仅在仅在当前输入符号当前输入符号Follow(A)时进行按时进行按A归归约；仅当前输入符号约；仅当前输入符号Follow(B)时进行按时进行按B归约；归约； 如果如果Follow（A） Follow(B) ，冲突仍然存在！，冲突仍然

26、存在！2022-4-13编译原理与技术讲义49SLR（1）分析SLR(1)分析表构造 若AaI，且goto(I,a)=J，则actionI,a=sJ 若A I，则actionI,b = r A,b Follow(A) 若SS I，则actionI,$ = acc 若goto(I,B)=K，则GOTOI,B=K 其它为空白/errorSLR(1)文法SLR分析表没有多重定义条目表达式文法G2是SLR（1）的。分析表见e.g.212022-4-13编译原理与技术讲义50e.g.24 非SLR（1）的文法G9文法G9(1)SL = R (2)SR(3) L*R (4) Lid(5) RLL：左值表达

27、式R：右值表达式 文法G9是非二义性文法First(S)=*,id=First(L)=First(R) Follow(S)=$ Follow(L)= = , $ Follow(R)= =, $ 2022-4-13编译原理与技术讲义51e.g.24 识别G9活前缀的DFAI0:S S S L=R S R L *R L id R LI1: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 idI8:L * R I7:R L I5:L id I9:S L= R SLRid*=L*RLRidid*2022-4-1

28、3编译原理与技术讲义52状态I2中存在移进-归约冲突项目S L =R 要求当前输入符是=时移进 ，即action2,= = s6 项目R L 则要求当前输入符是=或者$时归约，即action2,= = r5 action2,$ = r5分析栈： 0L2= $ 输入串移进后分析栈： 0L2=6$ 输入串归约后分析栈： 0R3= $ 输入串R= 却不是文法G9的活前缀2022-4-13编译原理与技术讲义53LR（1）分析器SLR分析的归约定义在Follow集合名下，可能导致归约的“扩大化”，引起不必要的冲突，造成了SLR分析能力不强。LR(1)分析规范的LR分析，能够准确地将归约定义在有关符号名下

29、（仅是Follow的子集），即这些符号只能是最左归约所对应最即这些符号只能是最左归约所对应最右推导逆过程的那一步中跟在左部非终结符右推导逆过程的那一步中跟在左部非终结符后面的（终结）符号。后面的（终结）符号。LR(1)分析使得最左归约的分析过程与最右推导过程精确地对应，具有最强最强的分析能力。2022-4-13编译原理与技术讲义54LR(1)项目 A，a 识别活前缀的LR(1)项目集族（DFA）LR(0)项目搜索符1） ，移进项目，与搜索符无关2） =，归约项目，当前输入符是搜索符时才进行归约2022-4-13编译原理与技术讲义55有效项目LR(1)项目 A，a 对活前缀有效，如果有最右推导过

30、程，其中 a First( $ )$ )。 识别活前缀的LR(1)项目集族*RR$A$S a即是右句型A$中跟在A后面的终结符； 当活前缀 出现在栈顶时，下一输入符是a时，才能将归约成A2022-4-13编译原理与技术讲义56识别活前缀的LR(1)项目集族有效项目如果LR(1)项目 AB，a 对活前缀有效，则对于BP, LR(1)项目B ,b对活前缀也有效。其最右推导过程如下， 其中 a First( $ ), 而b First( $ )=First( a) =First( a) 。显然，显然， 项目项目 AB，a 和 B ,b 应在同一状态(项目集合)*RRRR$A $SBB2022-4-1

31、3编译原理与技术讲义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,$ )2022-4-13编译原理与技术讲义58LR(1)分析表构造LR(1)分析表归约动作只填在搜索符名下归约动作只填在搜索符名下；其它同SLR(1)LR(1)文法其LR(1)分析表没有多重定义表项。文法G9虽不是SLR文法，但却是LR(1)文法。20

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

33、4-13编译原理与技术讲义61I0:SS,$ SBB,$BbB, a/bBa, a/bI1:SS,$ I2:SBB,$BbB, $Ba, $I3:BbB, a/bBbB, a/bBa, a/bI4:Ba, a/bSBbaI5:SBB,$BI6:B bB, $BbB, $Ba, $bI7:Ba, $aI8:BbB, a/bBbabI9:B bB, $Bae.g.26 识别活前缀的LR(1)项目集族2022-4-13编译原理与技术讲义62e.g.26 文法G10的LR(1)分析表状态actiongotoab$SB0s4s3121acc2s7s653s4s384r3r35r16s7s692022-4

34、-13编译原理与技术讲义63e.g.26 文法G10的LR(1)分析表（续）状态actiongotoab$SB7r38r2r29r22022-4-13编译原理与技术讲义64I0:SS SBBBbBBaI1:SS I2:SBBBbBBaI3:BbBBbBBaI4:BaSBbaI5:SBBBI8:BbBBbae.g.27 识别文法G10活前缀的LR(0)项目项目集族集族ba2022-4-13编译原理与技术讲义65LALR(1)分析LR(1)分析功能最强，但分析表远比SLR(1) 大(状态数多) 。同心集两个（以上）LR(1)项目集合若忽略搜索符后它们的LR(0)项目集合相同。 e.g.26中状态I

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

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

37、 cB cG11只产生四个句子：acd ace bcd bce2022-4-13编译原理与技术讲义69e.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 SbBdbcd2022-4-13编译原理与技术讲义70项目集I 和 J 显然是同心集合并之！合并后的项目集合Iij A c,d/e B c,e/d 出现（新的）归约-归约冲突即面临输入符e或者d时，按Ac还是Bc来归约

38、呢？而这一冲突在合并前是没有的！e.g.29 合并同心集合2022-4-13编译原理与技术讲义71e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b3 移进b0b3 移进b0b36 移进bb a $b a $b a $2022-4-13编译原理与技术讲义72e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a4 移进a0b3a4 移进a0b36a47 移进ab a $b a $b a $2022-4-13编译原理与技术讲义73e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3

39、a40b36a470b3B8 多余归约error 立即报错0b36B89 多余归约b a $b a $b a $2022-4-13编译原理与技术讲义74e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3a40b36a470b3B8error 立即报错0b36B890B2 多余归约0B2 多余归约b a $b a $b a $2022-4-13编译原理与技术讲义75e.g.30 串ba$的LR分析SLR（1）LR（1）LALR（1）0b30b30b360b3a40b3a40b36a470b3B8Error 立即报错0b36B890B20B2e

40、rror 报错error 报错b a $b a $b a $错误定位点相同2022-4-13编译原理与技术讲义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。2022-4-13编译原理与技术讲义77e.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的上下文

41、无关文法“推导出”前一半串时才用产生式S。而在LR分析中无法通过移入当前符号来判明是否到达串的中点（或读完一半的串），即在什么时候使用该空产生式上存在二义性（矛盾）。2022-4-13编译原理与技术讲义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）文法！2022-4-13编译原理与技术讲义79识别文法G12活前缀的LR（1）部分项目集簇非LR的上下文无关文法I0: S .S, $ S . a S a, $ S

42、 . b S b, $ S . , $ I2: S a.S a, $ S . a S a, a S . b S b, a S . , a aI0中冲突解决I2中冲突依然存在2022-4-13编译原理与技术讲义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）文法G162022-4-13编译原理与技术讲义81e.g.32 产生L14=ambn|mn0的3个文法（1）二义性文法G14S a S b | a S | a a a a b

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

44、” 。2022-4-13编译原理与技术讲义83e.g.32 产生L14=ambn|mn0的3个文法（2）非二义非LR文法G15S a S b | A A a A | a a a a b b bSaSb aaSbb aaaSbbb aaaAbbb aaaaAbbb aaaabbb aaaabbb2022-4-13编译原理与技术讲义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

45、 A, $/b A . , $/b aaI5: S a . S b, b S . a S b, b S . A, b A a . A, $/b A . a A, $/b A . , $/b aAI7: 归归冲突归归冲突 S A . , b A a A . , $/b 即在输入串中含有多于一个的即在输入串中含有多于一个的a，且含有，且含有b时，状态时，状态5面临面临b要进行归约（要进行归约（A的空产生的空产生式），然后进入状态式），然后进入状态7，此时面临输入符号，此时面临输入符号b存在归归冲突。也就是说，如何看待栈存在归归冲突。也就是说，如何看待栈顶的顶的a：它是多出来的，则按：它是多出来的，

46、则按A aA归约；归约；它和它和b“配对配对”，则按，则按 S A归约（希望形归约（希望形成成aSb）。）。2022-4-13编译原理与技术讲义85e.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时，将首先用A的空产生式进行归约，然后在移进b，形成aAb，再归约（再读入b，等等）。等全部的b读完后，将A归约为S，进一步形成aS而归约。2022-4-13编译原理与技术讲义86二义文法的应用二义文法不是LR文法，但文法简单，分析表较小分析冲突的解决 通过算符的优先级

47、与结合性E+E * ( shift first ) E+E + ( reduce first ) E*E * ( reduce first )E*E + ( reduce first ) 优先于移进if E then S else $ 产生式规则靠前的优先归约 2022-4-13编译原理与技术讲义87LR分析的错误恢复发现错误仅在查找动作表时，actionS,a=error/空白；一般地，SLR和LALR分析器报告错误会比LR(1)分析器迟因为作了些无效的归约，但他们都不会把出错点后的输入符号移入分析栈。紧急方式错误恢复 分析栈：从栈顶往栈中寻找存在有非终结符A转移的状态S，即有S A S 或

48、gotoS,A=S，弹出状态S以上的栈内容；将A和状态S压入栈。2022-4-13编译原理与技术讲义88LR分析的错误恢复紧急方式错误恢复 输入串：将输入指针调整到aFollow(A)（同步符号） A的选择：较大的语法单位，如表达式、语句、分程序等2022-4-13编译原理与技术讲义89YACCYet Another Compiler Compiler LALR分析器自动生成工具YACC简介yacc描述文件yaccy.tab.cyyparse()y.tab.c lex.yy.c *.ccc 可执行程序文件a.out2022-4-13编译原理与技术讲义90YACC描述文件由三部分组成 定义段（d

49、efinitions） 规则段（rules） 辅助程序段2022-4-13编译原理与技术讲义91定义段%/* 合法的C声明、包含文件、宏定义等 */#include #include % 单词符号的说明，如 %token digit 算符优先级、结合性的说明（注意书写的先后次序） %left+ - 低优先级的算符说明位置在前 %left* / %right 优先级越高，位置越后 开始符号（缺省时为第一个产生式的左部符号） %start symbol 2022-4-13编译原理与技术讲义92规则段A : 1 语义动作1 | 2 语义动作2 | | n 语义动作n | 没有,则使用缺省的语义动作 ; 产生式结束用分号标记 语义动作是C的语句序列（在一对中间），可以引用声明段中定义的C变量、宏等，还可以使用yacc的伪变量。 语义动作的一般是在产生式右部分析完，归约动作进行前执行。2022-4-13编译原理与技术讲义93规则段（续）yacc中的伪变量（类型缺省为整型） $ - 产生式左部非终结符的“值” $i - 产生式右部第i个文法符号的“值” yacc中有一个与分析栈“平行”的