编译原理LR1.doc

姓名： 刘玉华 学号： 20101103846 课题：LR(1)分析法 指导教师： 富玉柱 LR(1)分析法1.LR(1)分析法定义LR分析法是一种有效的自底向上的语法分析技术，它能适用于大部分上下文无关文法的分析，一般叫LR(k)分析方法，其中L是指自左(Left)向右扫描输入单词串，R是指分析过程都是构造最右(Right)推导的逆过程(规范归约)，括号中的k是指在决定当前分析动作时向前看的符号个数。LR（1）项目可以看成两个部分组成，一部分和LR（0）项目相同，这部分成为心，另一部分为向前搜索符集合。所以只有当面临的输入符属于向前搜索符的集合，才做规约动作，其他情况均出错。LR（1）方法恰好解决SLR（1）方法在某些情况下存在的无效规约问题。2. LR(1)分析法的主要思想(1)严格地进行最左归约（识别句柄并归约它）。(2)将识别句柄的过程划分为由若干状态控制，每个状态控制识别出句柄的一个符号。(3)分析栈：存放已识别的文法符号和状态,描述的是分析过程中的历史和展望信息。(4)由一个总控程序来控制整个识别过程。3. LR(1)分析法的构造方法(Aab,a)的二元式称为LR(1)项目。其中，Aba是文法的一个产生式，a是终结符，称为搜索符。文法的LR（1）项目集规范族指文法活前缀的有效的项目集。(1)构造LR(1)项目集I的闭包函数CLOSURE(I) a)I的任何项目都属于CLOSURE(I)；b)若项目(AaBb,a)属于CLOSURE(I)，Bg是一个产生式，则对于FIRST(ba)中的每个终结符b，如果(Bg,b)原来不在CLOSURE(I)中，则把它加进去； c)重复步骤b)直到CLOSURE(I)不再扩大为止。(2)构造转换函数即GO函数令I是一个LR(1)项目集，X是一个文法符号，函数GO(I,X)定义为：GO(I,X)=CLOSURE(J)，其中: J=(AaXb,a)|(AaXb,a)I。注：在执行转换函数GO时，搜索符并不改变。(3)构造拓广文法G的LR(1)项目集族C的算法 C=CLOSURE(S S,#); DOFOR 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.令那个含有项目SS ，#的Ik的下标k为状态0（初态）.ACTION表和GOTO表可按如下方法构造。2.若项目A,b属于Ik, 那么置ACTIONk, b为“用产生式A进行规约”，简记为“rj”;(假定A为文法G的第j个产生式)。3.若项目Aa,b属于Ik且GO (Ik, a)= Ij,则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”。4.若项目SS,#属于Ik, 则置ACTIONk, #为“接受”，简记为“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)的适用范围广，但LR(1)分析表含有较多的状态数，占用存储太大,影响了实践使用。1.LR(1)比SLR（1）能力强例: (0)SS (1)SL=R (2)SR (3)L *R (4)Li (5)RL不能用SLR（1）技术解决，但能用LR（1）。2.LR（1）项目集不存在动作冲突，合并同心集后会不会产生新的冲突（移进-归约，归约-归约）例:S SS aBc | bCc | aCd | bBdB eC e3.如果栈里的符号串为$da,归约后编程$dA,当前读到的输入符号是a，若文法中不存在以$da为前缀的规范句型，那么，这种归约无效。例：规范句型i=i的SLR(1)分析过程 状态栈 符号栈 输入串 0 $ i=i$ 05 $i =i$ 02 $L =i$ 03 $R =i$4.一个SLR文法的规范LR分析表比其SLR分析表含有更多的状态。在严重的情况下，状态数可能成几倍增长,因此需要简化。例：有如下文法: 1. Z S 2. S L=R 3. S R 4. L aR 5. L b 6. R L按照求LR(1)项目集规范族的算法，求G(S)文法的项目集族解：求初态项目集I0：从(Z S,#)项目开始求闭包得：I0初态ZS,#SL=R,#SR,#LaR,