编译原理与技术

2020/1/23《编译原理与技术》讲义1编译原理与技术－－自底向上分析2020/1/23《编译原理与技术》讲义2自底向上分析移进－归约分析分析树的构建从叶子结点开始，逐步构造各内部结点直至根结点出现。分析技术的关键－句柄的识别句柄（handle）是什么？简单讲，句柄是一个产生式的右部；自底向上分析（移进－归约分析）过程，其实就是发现句柄并将句柄（产生式右部）替换成相应左部非终结符的过程。该替换称为最左归约，它对应着某最右推导逆过程的一步。2020/1/23《编译原理与技术》讲义3自底向上分析分析技术的关键－句柄的识别句柄（handle）是什么？一般地，如果有以下最右推导序列，则产生式A及其在右句型中的位置称为右句型的句柄。,APA*Srmrm2020/1/23《编译原理与技术》讲义4自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的分析过程。输入串abbcde$aAbcde$aAde$aABe$S$最左归约最右推导2020/1/23《编译原理与技术》讲义5自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$2020/1/23《编译原理与技术》讲义6自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$2020/1/23《编译原理与技术》讲义7自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$A2020/1/23《编译原理与技术》讲义8自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$A2020/1/23《编译原理与技术》讲义9自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$AA2020/1/23《编译原理与技术》讲义10自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$AAB2020/1/23《编译原理与技术》讲义11自底向上分析e.g.17文法G61）SaABe2）AAbc3）Ab4）Bd串abbcde$的对应分析树的建立过程。输入串abbcde$AABS2020/1/23《编译原理与技术》讲义12移进－归约分析e.g.17用栈来实现串abbcde$的分析（1）分析栈输入串动作$abbcde$$abbcde$移进a$abbcde$移进b$aAbcde$归约：Ab$aAbcde$移进b$aAbcde$移进c2020/1/23《编译原理与技术》讲义13移进－归约分析e.g.17用栈来实现串abbcde$的分析（2）分析栈输入串动作$aAbcde$移进c$aAde$归约:AAbc$aAde$移进d$aABe$归约：Bd$aABe$移进e$S$r:SaABe分析成功！2020/1/23《编译原理与技术》讲义14移进－归约分析四种分析动作（action）∙移进（shift）－将当前输入符号移入栈顶top（why？）∙归约（reduce）－当“句柄”出现在栈顶（从栈中某处到栈顶top），则将“句柄”从栈顶弹弹出，并将相应产生式左部非终结符置入栈顶top。（when？）∙接受（accept）－分析成功！∙报错（error）－出现语法错误，调错误恢复例程2020/1/23《编译原理与技术》讲义15移进－归约分析分析动作冲突∙移进-归约冲突（shift-reduceconflict）当“句柄”处于栈顶时，分析动作指示既可以将下一输入符号移入栈顶top，又可以实施归约操作。如何动作呢？∙归约-归约冲突（reduce-reduceconflict）位于栈顶的“句柄”，同时匹配两个（以上）产生式的右部。选谁呢？怎么可能呢？2020/1/23《编译原理与技术》讲义16移进－归约分析冲突二义文法G不适合移进－归约分析e.g.18移进-归约冲突文法G7：SifEthenS|ifEthenSelseSSa$...…ifEthenS“句柄”？else...…分析栈输入串：当前输入符号2020/1/23《编译原理与技术》讲义17$...…ifEthenSelse栈顶...…分析栈输入串：$……Selse...…分析栈输入串：－归约动作－移进动作文法G7:SifEthenS|ifEthenSelseS|a期待新的“长句柄”2020/1/23《编译原理与技术》讲义18e.g.19二义性文法G8如下：EE+E|E*E|(E)|id输入串id+id+id$的最右推导：1）EE+EE+idE+E+idE+id+idid+id+id2）EE+EE+E+EE+E+idE+id+idid+id+id带下划线的符号串是相应句型的句柄。移进－归约分析冲突2020/1/23《编译原理与技术》讲义19e.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+归约移进2020/1/23《编译原理与技术》讲义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$$$E2020/1/23《编译原理与技术》讲义21移进－归约分析冲突归约-归约冲突e.g.20文法G91）Statid(para_list)|expr:=expr2）para_listpara_list,para|para3）paraid4）exprid(expr_list)5）exprid6）expr_listexpr_list,expr|expr2020/1/23《编译原理与技术》讲义22e.g.20分析输入串id(id,id)$分析栈输入串$id(id,id)$1)$id(expr,id)$2)$id(para,id)$paraid，目标：过程调用语句exprid目标：数组引用2020/1/23《编译原理与技术》讲义23LR分析器高效易实现的自底向上的分析方法文法限制少，适用于大多数CFG（包括含左递归、左因子的文法）LR（k）分析器L－从左自右读（readfromLefttoright）R－构造最右推导的逆（forconstructingaRightmostderivationinreverse）k－向前看符号的个数（thenumberofinputsymbolsoflookhead）2020/1/23《编译原理与技术》讲义24LR分析器输入串LR控制程序LR分析表SmXm..S0a1..ai..$状态符号栈输出TopBottom动作表Action转移表GOTO2020/1/23《编译原理与技术》讲义25格局：状态符号栈输入串S0……Xi-1Si-1XiSi，Xi+1……Xn$分析表∙动作表（Action）：S（{$}）{shift,reduce,accept,error}∙转移表（GOTO）：SVNSLR分析器2020/1/23《编译原理与技术》讲义26分析算法初始，状态S0位于栈底（栈顶）；根据当前栈顶状态S和当前输入符号a，查action表，由action[S,a]决定分析动作：∙si－输入符a移入栈顶top（pusha）；状态i移入栈顶top（pushi）。∙rj－按第j个产生式（A）进行归约，首先将从栈顶top往栈中的||个状态和||个符号（计2×||个）弹出分析栈；设此时栈顶状态为T，再将符号A和状态S’=GOTO[T,A]依次移入分析栈（S’在栈顶top）∙acc－输入串被接受，分析成功！∙error－输入串有错，调错误恢复程序2020/1/23《编译原理与技术》讲义27e.g.21表达式文法G2的LR分析表文法G2：（1）EE+T（2）ET（3）TT*F（4）TF（5）F（E）（6）Fid2020/1/23《编译原理与技术》讲义28e.g.21表达式文法G2的LR分析表状态actiongotoid+*()$ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4932020/1/23《编译原理与技术》讲义29e.g.21表达式文法G2的LR分析表（续）状态actiongotoid+*()$ETF7s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r52020/1/23《编译原理与技术》讲义30e.g.21id*(id+id)$的移进-归约分析过程分析栈输入串输出0id*(id+id)$0id5*(id+id)$s5:移进id0F3*(id+id)$r6:Fid0T2*(id+id)$r4:TF0T2*7(id+id)$s7:移进*0T2*7(4id+id)$s4:移进(0T2*7(4id5+id)$s5:移进id2020/1/23《编译原理与技术》讲义31e.g.21id*(id+id)$的移进-归约分析过程输入串输出分析栈+id)$s5:移进id0T2*7(4id5+id)$r6:Fid0T2*7(4F3+id)$r4:TF0T2*7(4T2+id)$r2:ET0T2*7(4E8id)$s6:移进+0T2*7(4E8+60T2*7(4E8+6id5)$s5:移进id0T2*7(4E8+6F3)$r6:Fid2020/1/23《编译原理与技术》讲义32e.g.21id*(id+id)$的移进-归约分析过程输入串输出分析栈0T2*7(4E8+6F3)$r6:Fid0T2*7(4E8+6T9)$r4:TF0T2*7(4E8)$r1:EE+T0T2*7(4E8)11$s11:移进)0T2*7F10$r5:F(E)0T2$r3:TT*F0E1$r2:ET0E1$acc2020/1/23《编译原理与技术》讲义33活前缀（viableprefix）是规范（右）句型的前缀，它不包含句柄后的任何符号（即活前缀的长度不会超过句柄的最右端）。若A∈P，有如下规范推导，则，的前缀为右句型的活前缀。识别活前缀的DFA*RRSA2020/1/23《编译原理与技术》讲义34活前缀与句柄移进-归约分析过程中，分析栈内的符号串构成活前缀（这表明已扫描过的输入串没有语法错误；事实上，也只有形成活前缀的符号才会被移入分析栈；分析的实质就是判断剩余输入串能否继续形成活前缀）∙活前缀不包含或部分包含句柄－此时期待着“匹配”句柄的输入串并将之移入栈顶；$bottom2020/1/23《编译原理与技术》讲义35活前缀与句柄∙活前缀已完全包含句柄－此时句柄位于栈顶，需要进行归约。$bottom句柄A$bottom2020/1/23《编译原理与技术》讲义36识别活前缀的DFALR（0）项目产生式右部加“∙”；“∙”的左部表示已“看见”（分析识别过）的部分；而右部则是期望“看到”的部分。如：产生式A∈P，其LR（0）项目有：A∙期望看到产生的串（移进项目）A∙已分析期望看到产生的串（移进项目）A∙、都分析完了（归约项目）特别的，空产生式A的LR（0）项目只有一个：A∙（归约项目）2020/1/23《编译原理与技术》