07LR(k)分析方法.ppt

第七章 LR(k)分析法 从左到右、自底向上的语法分析 LR分析方法的逻辑结构与分析过程 LR(0)文法及LR(0)分析表的构造 LR(1)文法及LR(1)分析表的构造 SLR(1)文法及SLR(1)分析表的构造 LR分析方法的逻辑结构 LR分析器的组成部分 由3个部分组成： LR分析程序，又称总控程序。所有的LR分析器的总控程序都是相同的。 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析表(分析函数)，不同的文法分析表不同； 同一个文法采用的LR分析器不同时，分析表也不同。分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。 关键是构造分析表 分析表的构造方法 有四种： LR（0）分析表构造法 简单LR（SLR(1)）分析表构造法 LR （1）分析表构造法 向前看LR（LALR）分析表构造法 LR分析过程： 在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作 分析表的组成 分析动作表Action是一个二维数组 状态转换表goto 也是一个二维数组 LR分析过程 用三元式: (状态栈，符号栈，输入符号) 表示分析过程中状态栈，符号栈，输入符号的变化。 将初始状态S0和#进分析栈。三元式为： (S0, # , a1a2…an#) 任一时刻的三元式为： (S0S1…Sm，#X1X2…Xm，aiai+1…an#) 分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。 LR分析过程 根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成不同的动作，若action[Sm, ai]为： 移进：当前输入符号ai进符号栈，下一输入符号变成当前输入符号，将action表中指出的状态S进状态栈。三元式变为：(S0S1…SmS, # X1X2…Xmai, ai+1…an#) 归约：按某个产生式A→β进行归约，若产生式的右端长度为r，则两个栈顶的r个元素同时出栈。将归约后的符号A进符号栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表, S=goto[Sm-r, A]进状态栈。三元式变为： (S0S1 … Sm-r S, # X1X2…Xm-rA, aiai+1…an #) 接受：分析成功，终止分析。三元式不再变化。 出错：报告出错信息。三元式的变化过程终止。 可归前缀的求法 对于任一文法，若有已知的可归前缀，用下面的方法即可求得所有的可归前缀 若αA?（A∈Vn）是某文法的可归前缀，若有规则A→u，则α u也是该文法的可归前缀 接上表 LR（0）文法 对于一个文法G，若其状态描述序列中的每个状态其项目集是相容的，则称该文法G是LR(0)文法。 由状态描述序列图，可以判断该文法是否为LR(0)文法 由此构造的分析表为LR（0）分析表，使用LR（0）分析表进行分析的方法为“LR（0）方法” 解决方法SLR(1)方法 当出现了不确定动作时，无法用前述LR（0）方法解决，有时可用LR（K）方法解决。 LR（K）方法是从左到右向前看K个符号来解决状态中的移进和归约的冲突动作。 当k=1时，即是LR（1）方法，是用从左到右向前看一个符号来解决冲突动作。 SLR（1）方法是一种简单的LR（1）方法，它只能在不确定状态下向前看一个符号来解决冲突动作。 SLR（1）Vs LR（1）方法 SLR（1）的向前看的符号是在出现冲突时才确定向前看的符号，而LR（1）方法则在一开始就确定向前看的符号 SLR（1）分析表的构造方法思想 对于项目集中有移进—归约、归约—归约冲突，采取如下的解决策略 Si=｛B→α△?,A→α△,C→α△｝(?是首符号为终结符的符号串) 对于归约项目A→α△，C→α△，分别求Follow(A)和Follow(C) 对于移进项目B→α△?，求其First(?) 若Follow(A)∩Follow(C) ∩First(?)=?，则可以用SLR(1)方法来分析 当状态I面临输入符号a时，如下构造分析表： 若当前输入符a ? First(?)，移进； 若当前输入符a ? Follow(A)，按A?α 产生式归约； 若当前输入符a ? Follow(B)，按B?α 产生式归约； 其他，报错。 LR(1)分析表的构造 SLR(1)分析的局限性 如果 SLR(1) 分析表仍有多重入口（移进归约冲突或归约归约冲突），则说明该文法不是 SLR(1) 文法； 说明仅使用 LR(0) 项目集和 FOLLOW 集还不足以分析这种文法 LR（1）分析表的构造方法思想 结论 任何LR(K)，LL(K)都是无二义性的。 任何二义性的文法均不可能是