第七章lr分析法.ppt

第第77章章LRLR分析法分析法学****目标:?掌握:LR(0)分析,SLR(1)分析?理解:活前缀,可归前缀?了解:LR(1)、LALR(1)(0)(1)(1)、LALR(1)分析思想2回顾:自底向上分析实现的基本思想——“移进-归约”方法(1)S→aAcBe (2)A→b(3)A→Ab (4) B→d 判断输入串abbcde# 是否为该文法的句子归约(S→aAcBe)##aAcBe10)接受##S11)移进ee##aAcB9)归约(B→d)e##aAcd8)移进dde##aAc7)归约(A→Ab)cde##aAb5)de##aA6)移进bbcde##aA4)归约(A→b)bcde##ab3)移进bbbcde##a2)移进aabbcde##1):根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K>=0)符号就可唯一地确定句柄。?LR(K)的含义:?L表示从左到右扫描输入串?R表示最左规约(即最右推导的逆过程)?K表示向右查看输入串符号的个数当K=1时,能满足当前绝大多数高级语言编译程序的需要,所以着重介绍LR(0),SLR(1),LR(1),LALR(1) LRLR分析概述分析概述4?LR分析的特点:?是规范归约?适用范围广,适用于大多数上下文无关文法描述的语言?分析速度快,能准确定位错误?缺点:)总控程序:所有LR分析器总控程序相同。2)分析表:?不同文法有不同的分析表?同一文法采用的LR分析器不同,分析表也不同?分析表分为ACTION表(动作表)和GOTO表(状态转换表)。3)分析栈:包括状态栈S和文法符号栈X。:列标题为状态,行标题为文法符号?GOTO表示当前状态面临文法符号时应转向的下一个状态。?ACTION表示当前状态面临输入符号时应采取的动作ACTIONGOTOacebd#acebd#2SS133r2r2r2r2r2r27为了节省空间,将ACTION和GOTO中关于终结符号的各列合并起来ACTIONGOTOacebd#acebd#2SS133r2r2r2r2r2r2ACTIONGOTOacebd#2S1S33r2r2r2r2r2r28?ACTION表中的动作有4种:1)移进(Sk):把状态k移入状态栈,若当前状态是i,且k=GOTO[i,a],把a移入符号栈2)归约(rk):用第k条产生式进行归约,此时栈顶形成了句柄β,文法中第k条产生式为A->β,且|β|=r,归约时从状态栈和符号栈中弹出r个符号,把A移入符号栈,j=GOTO[i,A]移入状态栈,其中状态i为修改指针后的栈顶状态3)接受(acc):当符号栈只剩文法开始符S,并且当前输入符为‘#’,则分析成功4)报错:当状态栈顶的状态遇到了不应该出现的文法符号,则报错,说明输入串不是该文法的句子9?LR分析器的工作过程示意图输入串a1a2…an #总控程序ACTION表GOTO表nXn10X1#SP输出状态栈文法符号栈栈指针LR分析器:在分析的每一步,通用的总控程序按照状态栈栈顶状态i和当前输入符号a查LR分析表,并执行其中ACTION和GOTO规定的操作。10