编译原理LR1知识点.docVIP

姓名： 刘玉华 学号： 20101103846 课题：LR(1)分析法 指导教师： 富玉柱 LR(1)分析法 1.LR(1)分析法定义 LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向前看的符号个数。 LR（1）((?(,a)的二元式称为LR(1)项目。其中，A(((是文法的一个产生式，a是终结符，称为有哪些信誉好的足球投注网站符。文法的LR（1）项目集规范族指文法活前缀的有效的项目集。 (1)构造LR(1)项目集I的闭包函数CLOSURE(I) a)I的任何项目都属于CLOSURE(I)； b)若项目(A((?B(,a)属于CLOSURE(I)，B((是一个产生式，则对于FIRST((a)中的每个终结符b，如果(B(?(,b)原来不在CLOSURE(I)中，则把它加进去； c)重复步骤b)直到CLOSURE(I)不再扩大为止。 (2)构造转换函数即GO函数 令I是一个LR(1)项目集，X是一个文法符号，函数GO(I,X)定义为：GO(I,X)=CLOSURE(J)，其中: J={(A((X?(,a)|(A((?X(,a)(I}。注：在执行转换函数GO时，有哪些信誉好的足球投注网站符并不改变。 (3)构造拓广文法G`的LR(1)项目集族C的算法 {C={CLOSURE({(S` (?S,#)})}; DO{FOR C中的每个项目集I和每个文法符号X IF GO(I,X)非空且不属于C 把GO(I,X)加入C中； }WHILE C依然扩大； } 4. LR(1)分析表的构造 假定LR(1)项目集规范族C={I0, I1,……，In}，令每个项目集Ik的下标k 为分析器的一个状态，G’ 的LR（1）分析表含有状态0，1，……，n。 1.令那个含有项目[S’→．S ，#]的Ik的下标k为状态0（初态）.ACTION表和GOTO表可按如下方法构造。 2.若项目[A→α．,b]属于Ik, 那么置ACTION[k, b]为“用产生式A→α进行规约”，简记为“rj”;(假定A→α为文法G’的第j个产生式)。 3.若项目[A→α．aβ,b]属于Ik且GO (Ik, a)= Ij,则置ACTION[k, a]为“把状态j和符号a移进栈”，简记为“sj”。 4.若项目[S’→S．,#]属于Ik, 则置ACTION[k, #]为“接受”，简记为“acc”。 5.若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j;分析表中凡不能用规则1至5填入信息的空白格均置上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张规范的LR(1)分析表。具有规范的LR(1)表的文法G称为一个LR（1）文法。 5. LR(1)分析法的利弊 LR(1)的规约项目不存在任何无效规约，但在多数情况下同一个文法的LR(1)项目集的个数比LR(0)项目集的个数多。这是因为对同一个LR(0)项目集，由于有哪些信誉好的足球投注网站符不同而对应着多个LR(1)项目集。LR(1)分析法虽然可以解决SRLR(1)方法所难以解决的“移进-归约”或“归约-归约”冲突，但是对同一个文法而言，但有哪些信誉好的足球投注网站符不同时，是的同一个项目集被分裂成多个项目集从而引起状态数的剧烈增长，导致了时间和内存空间的急剧上升，它的应用也相应地受到了一定的限制。为了克服LR(1)分析法的这种缺点，可以采用LALR(1)分析法。 LR分析法（适用范围广；分析速度快；报错准确）。LR(1)分析法比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。对于大多数用无二义性上下文无关文法描述的语言都可以用LR分析法进行有效的分析，而且这种分析法分析速度快，并能准确及时地指出输入串的语法错误和出错的位置。但是，这种分析法有一个主要缺点，那就是对于一个语言的文法，构造LR分析器的工作量相当大，具体实现较困难。SLR(1)的状态数少LR(1)的适用范围广占用存储太大,影响了实践使用。 (1)S→L=R (2)S→R (3)L→ *R (4)L→i (5)R→L 不能用SLR（1）技术解决，但能用LR（1）。 2.LR（1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进-归约，归约-归约） 例:S – S S – aBc | bCc | aCd | bBd B – e C – e 3.如果栈里的符号串为$(