川师编译原理课件7.ppt

《川师编译原理课件7.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章LR分析法教学目的：让学生了解LR分析方法的基本思想，掌握LR(0)、SLR(1)、LR(1)、LALR(1)分析法。教学重点：LR(0)、LR(1)分析课时分配：8学时。教学过程：2021/7/211吉首大学：莫礼平前一章主要内容回顾短语、素短语算符优先分析法的分析过程算符优先关系的确定(FIRSVT、LASVT)算符优先关系表的构造算符优先关系表的线性化——算符优先函数算符优先分析法的问题(文法限制、素短语、最左素短语NiaiNi+1ai+1…NjajNj+1)希望找到一个更方便的方法2021/7

2、/2127.1LR(Left-Right)分析法一、算符优先分析法存在的问题强调算符之间的优先关系的唯一性，这使得它的适应面比较窄；算法在发现最左素短语的尾时，需要返回来寻找对应的最左素短语头；二、LR(k)分析法L：从左到右扫描输入符号，R：最右推导对应的最左归约(反序完成最右推导)k：超前读入k个符号，用以确定归约所用的规则。2021/7/213三、LR分析器工作示意图a1…ai…an#LR总控程序动作表action转移表goto输出规则序列状态/符号栈输入缓冲区分析表SmSm-1………S1S0XmXm

3、-1………X1#2021/7/214四、LR分析表：action[s,a]；goto[s,X]动作表转移表状态actiongotoab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2LR(0)、SLR(1)、LR(1)、LALR(1)将以不同的原则构造这张分析表约定：sn:将符号a、状态n压入栈;rn:用第n个产生式进行归约.2021/7/2157.2LR(0)分析法例:G[S]:S→aAcBe[1]A→Ab[2]A→b[3]B→d[4](S'→S[0])对句子

4、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]称为可归前缀（即规范句型中每步归约前句型的前部分串）。可归前缀的前缀称活前缀。2021/7/216规范句型活前缀一、活前缀和可归前缀的形式定义若S‘αAγαβγ,则称αβ为可归前缀;若有串W是αβ的前缀，则称W是G的一个活前缀（S‘为文阖拓广后的开始符，它只出现在规则左部）。二、说明：

5、1、LR分析时，把αβ的前缀的前缀W列出在符号栈中，一旦出现αβ即说明句柄形成，则用规则Aβ归约。2、规范规约所得到的规范句型的活前缀是出现在分析栈中的符号串，所以，活前缀中不会出现句柄之后的任何字符。2021/7/2177.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和一些ε弧，

6、将各可归前缀的有穷自动机合并成一个有穷自动机NFA。其中由S[0]得到的终态称为句子识别状态，用*标记。2021/7/2182021/7/219上图是通过一个句子(abbcde)的归约过程直观的看出其活前缀和可归前缀，然后构造其NFA。对前面有穷自动机NFA确定化为DFA：思考：如何求一个文法的所有可归前缀？X425137689SAbaBcdeb*2021/7/21107.2.2求可归前缀的一般算法设文法G是一个2型文法，对于非终结符A，定义集合LC(A)={α

7、S‘αAβ,α∈V*,β∈VT*}。LC(A

8、)即A左边所出现的符号串集。显然，LC(A)为所有不包括句柄的活前缀。若有产生式A→γ,即LC(A).γ为一可归前缀。习惯上将LC(A)写成[A]。2021/7/2111推论若文法G中有产生式B→αAβ,则有LC(B).αLC(A)证：S‘δBγδαAβγ.显然有上推论成立。利用此推论即可列出正规式方程组，求得所有的活前缀；再利用文法规则和所求得的活前缀，即可求得可归前缀：2021/7/2112例6.1：对文法G[S']:S'→SS→aAcBeA→AbA→bB→d,求所有可归前缀.解：列方程组如右：[S']

9、=ε[S]=[S']ε[A]=[S]a

10、[A]ε[B]=[S]aAc可解得：[S']=ε[S]=ε[A]=a[B]=aAc2021/7/2113在LR(0)方法中，含句柄在内的活前缀计算方法如下：LR（0）C(Aβ)=LC(A).{β}则前例中：LR（0）C(S’S)=SLR（0）C(SaAcBe)=aAcBeLR（0）C(Ab)=abLR（0）C(AAb)=aAbLR（0）C(Bd)=aAcd即所求