LR(0)分析器的设计分析

现代商贸工业No.3,2010Modern Business Trade Industry2010年第3期LR(0)分析器的设计分析褚亚飞陈德城宋一波(浙江海洋学院萧山科技学院,浙江杭州311258)摘要:阐述了 编译原理课程中的LR(0)分析器的设计原理和算法。对给定的文法设计一个LR(0)分析器，給出LR .(0)分析表,并对给定的文法进行分析。关键词:LR(0);原理;文法;算法;设计中图分类号:TP文献标识码:A文章编号:1672-3198(2010)03-0280-031 LR(0)分析表的构造F→. (E)LR(0)分析表包括两个部分,一是“动作" (ACTION)F→.i表,另一是“状态转换"(GOTO)表，它们都是二维数组。1.2 构造状态转换函数 GO(I,X)ACTION[S,a]规定了当状态s面临输人符号a时应采取什构造状态转换函数是构造DFA的前提条件,这个函数么动作。GOTO[S,X]规定了状态s面对文法符号X(终结的意义是:当项目集1面临文法符号X的时候所转向的另符或非终结符)时下-状态是什么。下面就具体说明在构一个项目集。 它的定义为造LR(0)分析表过程中要涉及到的具体内容。GO(I,X) =CLOSURE()1.1构造文 法的项目集规范族如下列文法:J= {任何形如[A→aX. p,a]的项目I [A→a Xp,a]∈(1)E-E+TI} ,那么,在设计中采用的文法的GO函数构造如下:GO(I0,E)=l1G0(I6,i)=15(2)E-TG0(10,)=I5GO(I6,F)=I3(3)T→T#FGO(IO,F)=I3GO(I6,()=I4(4)T→FGO(I0,()=I4GO(17,i)=I5 .(5)F→+(E)GO(IO,T)=I2GO(17,()=14(6)F→i .G0(l1,+)=16GO(I7,F)=I10LR(0)项目集规范族的构造的基本思想是根据双标记GO(I2,*)=17G0(I8,+)=I6法,定义两个标志位ltag.rtag. Ltag 表示项目集是否增加.GO(I4,F)=13GO(I8,))=111完。在构造项目集时,若该项目集不再增大,则将ltag置为GO(I4,()=I4 .G0(I9,*)=17true,否则false. rtag 表示该项目集是否传播完。在已经构GO(I4,i)=I5造的项目集中,若已经求出所有的该项目集的状态转移后GO(I4,E)= I8的新的项目集,那么将rtag置为true,并 以分析表表示边的.3 构造识别活前缓的DFA关系。这个文法的项目集规范族为:把这些项目集规范族和转换函数GO表示成有限自动S'+.E5;机便成为一个能识别活前缀的DFA,如下图1所示。E→. E+T6:E→+E+.T这样,我们就可以利用这个有限自动机来构造LR分析E→.TT→.T*F表的ACTION和GOTO子表。接着,我们的任务就是要利T+.F用它来构造LR(0)分析表。T→.FF→.(F)1.4构造LR(0)分析表.4.1 类的定义.7:T→T#.F①集合类Set和产生式类Precept的定义和LL(1)预测1:S'→E. F→. (E)分析器中的定义一样;E→E. +T②其他类的定义2:E- +T. .I8;F→(E.)class Pair //定义项目类T→T. *F3:T→F.public :I4;F→(. E)9:E→E+T.Pair( );E+. E+TT→T. *PPair(inti, int j);E+. TIl0:T→T*F.11:F-(E).中国煤化工T-.FYHCN M H Gair) const;作者简介:宋一波(1981-)男,于2006 年开始在浙江海洋学院萧山科技学院工作至今,主要从事网络管理及计算机类相关学科教学工作。一咒数据现代商贸工业No. 3,2010Modern Business Trade Industry2010年第3期，Precept GetPrecept(int n);Grammar( void) ;~Grammar( void);Grammar(const Grammar & g);const Grammar operator = (const Grammar & g);'void SetVt(string vt);void SetVn(string vn) ;void SetStart(char start);void AddPrecept(string p) ;bool IsGrammarLegal( );bool IsInVn(char cChar);bool IsInVt(char cChar);char GetStart( );void GenerateLR0Table( ); .string OutputHTML( );void Output(char # pFilename);囝1识别活前缓的DFAbool IsLegalLROGrammar( );};private:class GoData //对项目进行传播的类定义Set VtSet Vn;public:char cStart;GoData( );vector P;~GoData( );vector C;int iFrom;Pair * pTable;char eChar;vector GoSet;int iTo;int nVt;);int nVn; :class ProijectSet//定义项目集族类int nP; .{int nC;void EnlargeGrammar( );ProjetSet(void);void MakeProjects( );~ ProjectSet( void);void GenerateTable( ); .ProjectSet( const ProjectSet & set);Precept GetProject( const Pair & pair1);ProjectSet(Pair pair) ;ProjectSet GetClosure( const Pair & pair1);bool Insert(Pair insert);ProjectSet MakeGoSet(int iI, char cChar);bool Delete(Pair del);int GetGoSet(int il, char eChar) ;bool Find(const Pair & find) const;bool AddProject( const ProjectSet & ps);int FindPos(const Pair & find) const;bool FllTable(int nLine, char eChar, Pair p);int Add(const ProjectSet & set);int ilegal;int Sub( const ProjectSet & set);void CopyGrammar(const Granmar & g);int Size( ) const;protected;PrijetSet operator + (const ProjectSet & set);int GetProjectNum(const Pair & p);PrietSet operator - (const ProjectSet & set);const ProjectSet operator =(const ProjectSet & set);1.4.2构造算法bool operator = = (const ProjectSet & set);构造LR(0)分析表的关键就是要它的ACTION和GO-Pair GetAt(int iPos);TO子表,上面已经构造好了这个文法的GO函数,我们将bool IsEmpty( );利用这个GO函数来构造出这两个子表。算法如下:①若项目A→a.a属于Ik且GO(Ik,a)=lj,a为终结vector SetContent;符,则置ACTION[k,a]为“把(j,a)移进栈”,简记为“s”;中国煤化工何终结符a(或终结.class Grammar //定义LR(0)文法类符#)，MHCNMHG→a进行归约”，简.记为“;个产生式):③若项目S'→S.属于k,则置ACTION[k, #]为“接.int GetGoTo(int iStatus, char eChar);受”,简记为“ace" ;Pair GetAction(int iStatus, char cNext);④若GO(Ilk,A) =Ij,A为非终结符,则置GOTO[k,A]一281一现代商贸工业No.3,2010Modern Business Trade Industry2010年第3期=j;.0..... sm - rs, # x2.....m- rA,aiai+ ....n#).⑤分析表中凡不能用规则1至4填入信息的空白格均此处,s= GOTO[sm-r,A],r为β的长度,β= Xm- -τ置上“报错标志”.+.....Xmn.根据这个算法构造出文法的LR(0)分析表如下:③若ACTION sm,ai]为“接受”,则三元式不再变化，表1 LR(0)分析表变化过程终止,宣布分析成功.ACTION(动作) COTO(转 换)④若ACTION[ sm,ai]为“报错”,则三元式的变化过程状态终止,报告错误。0523一个LR分析器的工作过程就是一步一步地变换三元s6acc式,直至执行“接受”或“报错”为止。r2 s7r2r22.2 LR(0)分 析程序总控程序的流程4I4r4r4LR分析器实际上就是一个有限自动机,分析栈的栈顶4s5Is482 3的状态概括了整个栈的内容，因此,无需扫描整个栈。我们r6Tr6r6 r66| s9T 3只要根据栈顶的内容和现行输人符号就可以识别一个句s5s40柄。只是LR分析表的设计较LL(1)分析表的设计要麻烦，8 s6s11但是LR(0)分析法比LL(1)分析法的功能要强,并且一般9r1Ts71r能用LL(1)分析的文法用LR(0)也一定可以分析。具体的r3r3r3 r3流程图分析如下:C开舶D说明:记号的意义是:Stane 0 FLAG TRUE(1)sj:把下一-状态j和现行输人符号a移进栈;(2)r;:按第j个产生式进行归约;把状态0利行号分压入状态控利符号园(3)acc:接受;厄第一个许号请(4)空白格:出错标志,报错.2 LR(0)分 析器的设计< FLAG-TRUEDY2.1设计原理LR(0)分析器的核心就是一张分析表.这张分析表现为移进少在也已经构成,下面我们要做的工作就是构造LR(0)分析移进接受报销器了。每一项ACTION[s,a]所规定的动作不外是下述四State -GOTO状态找和符号校分析成功] 出锁处理]种可能之一:Isuaie.l分别进行欢出校(1)移进。把(s,a)的下一状态s' = GOTO[s,a]和输入[ Sase进状泰线] 5 =状栈L 栈丽状态CASE ASE符号a推进栈，下一输人符号变成现行输人符号.C进符号栈]Erisre -OOTO1(2)归约。用某一个产生式A→β进行归约。假若β的长度是r,归约的动作是A,去除栈顶的r个项,使状态sm-r变成栈顶状态,然后把(sm- -r,A)的下一状态s'= GOTO[随符号技J[sm- r,A]和文法符号A推进栈。归约动作不改变现行输下一输入粉号读遇]人符号.执行归约动作意味着(= Xm-r+1-Xm)巳垦现于栈顶而且是一个相对于A的句柄。C纺乘)(3)接受。宣布分析成功,停止分析器的工作。圉2.(4)报错。发现源程序含有错误,调用出错处理程序。一个LR分析器的工作过程可看成是栈里的状态序列、3结束语已归约串和输人串所构成的三元式的变化过程。分析开始该分析器不同于传统的多媒体教学软件限制教学案例:用时的初始三元式为户只要按规定的格式输入问题，系统能自动地给出该问题的答(s0，#，a2....n#)案和解答过程。该系统能作为学生学习的辅助工具,同时也可其中s0为分析器的初态, #为句子的左括号a2......以作 为教师的教学工具,辅助教学,这也是适应新世纪教学改an为输入串,其后的#为结束符(句子右括号).分析过程革的需要。 本分析器专门是针对编译原理这门课程而设计的，每步的结果可表示为因此,它的运用就仅局限于对编详原理的解答。<....sm,.. # X2..... Xm, a+....an#)分析器的下一步动作是由栈顶状态sm和现行输人符参考文献号ai所唯一决定的，即执行ACTION[sm,ai]所规定的动[1] 吕映芝,张素琴,编译原理[M].北京:清华大学出版社,1998.作,经执行每种可能的动作之后,三元式的变化情形是:[2]K“中国煤化工峰原理反实成[M]北①若ACTION[Ssm,a门]为移进，且s= GOTO[sm,ai],则[3]陈|YHCN M H G(第3版)[MJ.北京，三元式的变成:.0..... sms, # X2..... Xmai, a+..... an# )国防工业出殿社,Z0U1.②若ACTION[sm,ai]={A→β) ,则按产生式A→β进[4]卢伟,李堂秋.嵌入语义动作的LR分析器构造方法[J].计算机工程与应用,1998,37(6) ;41-47.行归约。此时三元式变为方数据