LR分析法.(完整)

《LR分析法.(完整)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章LR分析法【预习思考】复习自顶向下和自底向上语法分析思想的区别。自底向上分析方法是一种移进-归约过程。简单优先分析法是如何确定可归约串的？什么是规范推导和规范归约？它们之间有什么关系？什么是规范句型？什么是规范句型的句柄？移进-归约过程是当分析的栈顶符号串形成句柄时就采取归约动作。自底向上分析法的关键问题是在分析过程中如何确定句柄。如何确定一个输入符号串是否是所给文法的句子？【学习目标】理解LR分析法的基本思想。理解可归前缀和活前缀概念。理解识别活前缀的有限自动机概念。掌握LR分析器的构造思想和方法。对给定的文法能构造LR(0)

2、、SLR(1)、LALR(1)、LR(1)四种分析器。对给定的输入符号串能用构造的分析器判断该输入串是否是所给文法的句子LR分析中的应用。【学习指南】LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K≥0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。其中LR(0)分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，然而，它是构造其它LR类分析器的基础。【重

3、难点】可归前缀和活前缀概念识别活前缀的有限自动机概念对可归前缀为规范归约的句柄的理解构造LR(1)项目集族时搜索符的计算LR分析器的关键部分是分析表的构造对给定的文法能构造LR(0)、SLR(1)、LALR(1)、LR(1)四种分析器当一个文法能构造出不含移进-归约或归约-归约冲突时的LR(0)/SLR(1)/LALR(1)/LR(1)分析表时，称这个文法分别为LR(0)/SLR(1)/LALR(1)/LR(1)文法。1965年，D.knuth首先提出了LR(K)文法及LR(K)分析技术。LR(K)分析是指自左向右扫描和自底向上的语法

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

5、表示在每一步分析时都不用向前输入符号LR(1)：表示在每一步分析时都向前看一个输入符号来决定当前的动作。SLR(1)：表示简单的LR(1)，即只在动作不唯一的地方向前看一个符号，在动作唯一时则不向前看输入符号。LALR(1)：表示向前看的LR(1)，即基于LR(1)作相同心项目的合并以减少状态数量。2）要移进时，即把Xn+1进栈，并读下一符号：#X1X2…Xi…XnXn+1Xn+2…Xn+k…#在栈中当前扫描符栈顶7.1LR分析概论一.LR分析器的逻辑结构及工作过程从逻辑上来说，一个LR分析器如图7.1所示。输入串#…ai…a1sp→

6、X1#S1S0┋┋┋┋XmSm总控程序输出ACTION表GOTO表其中S栈为状态栈X栈为符号栈栈产生式表图7.1LR分析器的逻辑结构即一个LR(k)分析器主要由：总控程序，分析栈（状态栈和符号栈）输入队列和分析表组成。一般来说所有LR分析器的总控程序基本上是大同小异。只有分析表各不相同。一般主要讨论三种不同的分析表的构造方法。第一种称为规范LR分析表构造法。用此法构造的分析表功能最强而且也适合于很多文法，但实现代价比较高。第二种称为简单LR(即SLR)分析表构造法。这是一种比较容易实现的方法。但SLR分析表的功能太弱，而且对某些文法可

7、能根本就构造不出相应的SLR分析表。第三种称为向前LR（即LALR）分析表构造法。这种方法构造的分析表功能介于规范LR分析表SLR分析表之间。这种表适用于绝大多数程序语言的文法。而且也可以设法有效的实现。二、LR分析器的分析过程如下：1.首先将初始状态S0及句子的左界符#分别压入状态栈和符号栈中。则用栈顶状态Sm和当前扫描符ai组成符号对（Sm,ai)去查分析动作表，根据ACTION[Sm,ai]的指示完成相应的分析动作。表中每一表元素所规定的动作仅能是下列四种动作之一：S0S1S2…SmSm+1ai+1ai+2…an##X1X2…X

8、mai↑↑↓2.设在分析中的某一步，分析栈及余留的输入串为如下格局：↓S0S1…Smaiai+1…an#X1…Xm↑↑（1）ACTION[Sm,ai]=Sm+1（移进）表明句柄尚未在栈顶形成，此时正期待移进输入符号以便形