Dknuth首先提出了LR(K)文法及LR(K)分析技术.ppt

《Dknuth首先提出了LR(K)文法及LR(K)分析技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章LR分析法1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。LR(K)分析是指自左向右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈中当前已移进和归约出的全部文法符号，并至多再向前查看K个输入符号，就能确定相当于某一产生式右部符号的句柄是否已在分析栈的顶部形成。从而也就可以确定所应采取的分析动作（是移进输入符号还是按某产生式进行归约）。当前扫描到Xn+1,向前查看k个符号，来确定是把Xn+1移进栈，还是把Xi…Xn作为句柄进行归约。1）要归约时，则根据某产生式U→XiXi+1…Xn进行归约：#X1X2…Xi-1UXn+1Xn+2…Xn+k…#例：

2、#X1X2…Xi…XnXn+1Xn+2…Xn+kXn+k+1…#栈顶（续页）LR(0)表示在每一步分析时都不用向前输入符号LR(1)表示在每一步分析时都向前看一个输入符号来决定当前的动作。SLR(1)表示简单的LR(1)，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号。2）要移进时，即把Xn+1进栈，并读下一符号：#X1X2…Xi…XnXn+1Xn+2…Xn+k…#在栈中当前扫描符栈顶6.1LR分析概论一.LR分析器的逻辑结构及工作过程从逻辑上来说，一个LR分析器如图：输入串#…ai…a1Sp→X1#S1S0┋┋┋┋XmSm总控程序输出ACTION表GOTO表其中

3、S栈为状态栈X栈为符号栈栈即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。第一种称为规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可能根本就构造不出相应的SLR分析表。第三种称为向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大

4、多数程序语言的文法。而且也可以设法有效的实现。二、LR分析器的分析过程如下：1.首先将初始状态S0及句子的左界限#分别压入状态栈和符号栈中。则用栈顶状态Sm和当前扫描符ai组成符号对（Sm,ai)去查分析动作表，根据ACTION[Sm,ai]的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一：S0S1S2…SmSm+1ai+1ai+2…an##X1X2…Xmai↑↑↓2.设在分析中的某一步，分析栈及余留的输入串为如下格局：↓S0S1…Smaiai+1…an#X1…Xm↑↑（1）ACTION[Sm,ai]=Sm+1（移进）表明句柄尚未在栈顶形成，此时正期待移进输入

5、符号以便形成句柄。故将当前的输入符号和表元素Sm+1分别压入栈中，有（2）ACTION[Sm,ai]=Rj(归约）表明此时应按文法的第j个产生式A→Xm-k+1Xm-k+2…Xm进行归约。即栈顶符号串Xm-k+1Xm-k+2…Xm已成为当前句型的句柄。所谓按第j个产生式归约，就是将分析栈中从顶向下的k个符号退栈，然后将文法符号A压入符号栈中。此时分析的格局为：↓S0S1…Sm-kaiai+1…an##X1…Xm-kA↑↑然后以（Sm-k,A)去查状态转移表，设GOTO[Sm-k,A]=Sl,则将此新状态压入状态栈中，则有如下格局：↓S0S1…Sm-kSlaiai+1…an##X1…Xm

6、-kA↑↑（3）ACTION[Sm,ai]=acc（接受）表明当前的输入串已被成功地分析完毕，应停止分析器的工作。其中Z为文法开始符号Sα为使ACTION[Sα，#]=acc的唯一状态（接受状态）（4）ACTION[Sm,ai]=ERROR（空白）。表明当前的输入串中含有错误，也应终止当前的分析工作。转出错处理。3.重复上述第2步的工作，直到分析栈顶出现“接受状态”或“出错状态“为止。对接受状态，分析栈的格局为：↓S0Sα##Z↑↑例：有文法G[S]:1：S→aAcBe2：A→b3：A→Ab4：B→d其ACTION表和GOTO表为：考察对输入串abbcde#的分析过程。r1r1r1r1

7、r1r1r4r4r4r4r4r4S9r3r3r3r3r3r37S8r2r2r2r2r2r2S6S53S4acc1S2BAS#dbecaGOTOACTION0123456789SaAcBeAbdb对输入串abbcde#的分析过程为：ACTIONGOTO步骤状态栈符号栈输入流分析动作下一状态10#abbcde#S2(0,a)202#abbcde#S4(2,b)3024#abbcde#r2(4,b)GOTO[2,A]=34023#aAbcde#S6(