川师编译原理课件7.ppt

第七章 LR分析法 前一章主要内容回顾 短语、素短语 算符优先分析法的分析过程 算符优先关系的确定(FIRSVT、LASVT) 算符优先关系表的构造 算符优先关系表的线性化——算符优先函数 算符优先分析法的问题(文法限制、素短语、最左素短语Niai Ni+1ai+1… Njaj Nj+1) 希望找到一个更方便的方法 7.1 LR(Left-Right)分析法 一、算符优先分析法存在的问题 强调算符之间的优先关系的唯一性，这使得它的适应面比较窄； 算法在发现最左素短语的尾时，需要返回来寻找对应的最左素短语头； 二、LR(k)分析法 L ：从左到右扫描输入符号， R ：最右推导对应的最左归约(反序完成最右推导) k ：超前读入k个符号，用以确定归约所用的规则。 三、LR分析器工作示意图 四、LR 分析表：action[s,a]；goto[s,X] 7.2 LR(0)分析法 例:G[S]:S→aAcBe[1] A→Ab[2] A→b[3] B→d[4] (S→S[0]) 对句子abbcde分析过程如下: ab[3]b[2]cd[4]e[1] ?aAb[2]cd[4]e[1]? aAcd[4]e[1] ?aAcBe[1]? S[0]?S 其中：ab[3],aAb[2],aAcd[4],aAcBe[1]和S[0]称为可归前缀（即规范句型中每步归约前句型的前部分串）。 可归前缀的前缀称活前缀。 规范句型活前缀 一、活前缀和可归前缀的形式定义 若S‘ αAγ αβγ,则称αβ为可归前缀; 若有串W是αβ的前缀，则称W是G的一个活前缀（S‘为文阖拓广后的开始符，它只出现在规则左部）。 二、说明： 1、LR分析时，把αβ的前缀的前缀W列出在符号栈中，一旦出现αβ即说明句柄形成，则用规则A? β归约。 2、规范规约所得到的规范句型的活前缀是出现在分析栈中的符号串，所以，活前缀中不会出现句柄之后的任何字符。 7.2.1 识别活前缀的有穷自动机 例:G[S]:S→aAcBe[1] A→Ab[2] A→b[3] B→d[4] (S→S[0]) 对句子abbcde,其可归前缀为：ab[3],aAb[2],aAcd[4],aAcBe[1],S[0] 对它们分别构造有穷自动机，然后，通过加入一开始状态X和一些ε弧，将各可归前缀的有穷自动机合并成一个有穷自动机NFA。其中由S[0]得到的终态称为句子识别状态，用*标记。 上图是通过一个句子(abbcde)的归约过程直观的看出其活前缀和可归前缀，然后构造其NFA。 对前面有穷自动机NFA确定化为DFA： 思考： 如何求一个文法的所有可归前缀？ 7.2.2 求可归前缀的一般算法 设文法G是一个2型文法，对于非终结符A，定义集合LC(A)={α|S‘ αAβ,α∈V*, β∈VT* }。 LC(A)即A左边所出现的符号串集。 显然，LC(A)为所有不包括句柄的活前缀。若有产生式A→γ,即LC(A).γ为一可归前缀。 习惯上将LC(A)写成[A]。 推论 若文法G中有产生式B→αAβ,则有LC(B).α LC(A) 证： S‘ δBγ δαAβγ .显然有上推论成立。 利用此推论即可列出正规式方程组，求得所有的活前缀；再利用文法规则和所求得的活前缀，即可求得可归前缀： 例6.1：对文法G[S]:S→S S→aAcBe A→Ab A→b B→d,求所有可归前缀. 解：列方程组如右： [S]= ε [S]=[S]ε [A]=[S]a | [A]ε [B]=[S]aAc 可解得： [S]= ε [S]= ε [A]=a [B]=aAc 在LR(0)方法中，含句柄在内的活前缀计算方法如下： LR（0）C(A? β) = LC(A).{β} 则前例中： LR（0）C(S’? S) = S LR（0）C(S? aAcBe) = aAcBe LR（0）C(A?b) = ab LR（