java编写的LALR1文法分析器

1、软件课程设计LALR(1)文法分析器尹星晨0806230331LALR1文法分析器一、 题目简介1、 目的a) 巩固LR(1)、LALR(1)语法分析的原理知识。b) 通过对语法分析表的自动生成加深语法分析表的认识，以及语法分析过程。c) 理解并处理语法分析中的异常和错误。2、 要求已知给定如下文法G(S)：0: S->S; 1: S->E 2: E->E+T 3: E->T 4: T->(E) 5: T->a要求实现以下功能： 编写实现给定文法的LR分析的程序以及在此基础上实现的LALR(1)分析过程 a计算每个非终结符的first集和follow集 b初

2、始项目集扩大以及判断是否需要生成新项目集 c同心集合并以及预测分析表的合并 打印每个LALR(1)的每个项目集 打印该文法的预测分析表 根据生成的预测分析表判断输入串是否合法，若不合法则给出相应的提示信息，若合法打印每个合法输入串的语法树二、 预期结果1、 能够打印出化简后的分析表【如下：】。状态ActionGoto+()a#SET0S4S51231acc2S6r13r3r34S4S5735r5r5r56S4S587S6S98r2r2r29r4r4r42、 打印出该文法的所有化简后的状态，并且给出给状态之间的转换过程。手工推导出的化简的状态机图如下：化简后的状态机图如下：3、 输入句子，判断该

3、句子是否为该文法的句子，是则画出语法树。例1：如果输入ab。结果：因为b不为文法中的终结符，故显示输入错误。例2：如果输入a(a)。结果：虽然所有字符都是文法中的终结符，但因不符合文法，故显示错误提示信息。例3：如果输入a+a。结果：该句子符合该文法，所以显示正确的提示信息，并且画出语法树。语法树样例如下：a -T-E-+ -E-Sa -T-/三、 分析过程该文法分析器的构造思路为：首先求出该文法的First集合和Follow集合；据此导出文法的LR(1)分析的状态机；接下来化简LR(1)得到LALR(1)状态；然后，画出LALR(1)型的分析表；最后根据生成的分析表判断输入的句子是否为该文法

4、的句子。构造过程如下：由于本利程采用图形化界面，图像化界面设计原型如下：输入框：在这里输入需要判断的字符串：显示分析结果的界面如下：四、 实际结果实际输入界面：输入例如“ab”错误时：应该显示如下提示信息：实际显示结果界面：显示所有状态机：以下给出完全LALR(1)状态机：LALR(1)状态机如下：I0:Q - > .S #S - > .E #E - > .E+T #+E - > .T #+T - > .(E) #+T - > .a #+I1:Q - > S. #I2:S - > E. #E - > E.+T #+I3:E - > T

5、. #+)I4:T - > (.E) #+)E - > .E+T )+E - > .T )+T - > .(E) )+T - > .a )+I5:T - > a. #+)I6:E - > E+.T #+)T - > .(E) #+)T - > .a #+)I7:T - > (E.) #+)E - > E.+T )+I8:E - > E+T. #+)I9:T - > (E). #+)状态之间的转换如下：I0 S 1I0 E 2I0 T 3I0 ( 4I0 a 5I2 + 6I4 E 7I4 T 3I4 ( 4I4 a

6、5I6 T 8I6 ( 4I6 a 5I7 + 6I7 ) 9显示分析表：显示输入字符串为“a+(a)”的语法树：其分析过程如下：步骤状态栈符号栈输入串动作1 0 #a+(a)#移进2 05 #a +(a)#规约：用T->a3 03 #T +(a)#规约：用E->T4 02 #E +(a)#移进5 026 #E+ (a)#移进6 0264 #E+( a)#移进7 02645 #E+(a)#规约：用T->a8 02643 #E+(T )#规约：用E->T9 02647 #E+(E )#移进10 026479 #E+(E) #规约：用T->(E)11 0268 #E+

7、T #规约：用 E->E+T12 02 #E #规约：用S->E13 01 #S #接受当输入为a(a型错误时，应如下显示：五、 结果比对通过比较发现所得结果与预期结果相符。在分析过程中，会给出First集合和Follow集合。预期结果如下：First集合如下:FIRST(Q)= ( a FIRST(S)= ( a FIRST(E)= ( a FIRST(T)= ( a Follow集合如下:FOLLOW(Q)= # FOLLOW(S)= # FOLLOW(E)= # + ) FOLLOW(T)= # + ) 通过打印输出的结果如下：因为由LR(1)简化得到LALR(1)状态机：如

8、下给出LR状态及其转换：LR(1)状态机如下：I0:Q - > .S #S - > .E #E - > .E+T #+E - > .T #+T - > .(E) #+T - > .a #+I1:Q - > S. #I2:S - > E. #E - > E.+T #+I3:E - > T. #+I4:T - > (.E) #+E - > .E+T )+E - > .T )+T - > .(E) )+T - > .a )+I5:T - > a. #+I6:E - > E+.T #+T - >

9、 .(E) #+T - > .a #+I7:T - > (E.) #+E - > E.+T )+I8:E - > T. )+I9:T - > (.E) )+E - > .E+T )+E - > .T )+T - > .(E) )+T - > .a )+I10:T - > a. )+I11:E - > E+T. #+I12:E - > E+.T )+T - > .(E) )+T - > .a )+I13:T - > (E). #+I14:T - > (E.) )+E - > E.+T )+I15

10、:E - > I16:T - > (E). )+状态之间的转换如下：I0 S 1I0 E 2I0 T 3I0 ( 4I0 a 5I2 + 6I4 E 7I4 T 8I4 ( 9I4 a 10I6 T 11I6 ( 4I6 a 5I7 + 12I7 ) 13I9 E 14I9 T 8I9 ( 9I9 a 10I12 T 15I12 ( 9I12 a 10I14 + 12I14 ) 16六、 个人感想在本次试验中，主要碰到的问题是First集、Follow集的求解，递归求集合的函数中有的并不是用递归得到，而是直接返回，造成一些元素漏了，通过仔细对照书本的求法，最终理解了递归求集合的方法

11、。通过本次试验，了解最为简单的编译器的编写。附录：部分源码1、 申明的变量及其注释；private Map<Character,String> mapt=new HashMap<Character,String>();/终结符private Map<Character,Integer> mapn=new HashMap<Character,Integer>(); /非终结符 private char map=new char5; /非终结符 private String pro=new String10; private int len=0; /

12、产生式的个数 private int cntn=0; /非终结符个数 private int cntt=0; /终结符个数 private char first=new char58; private char follow=new char58; private int firstlen=new int5; private int followlen=new int5; private String I=new String2008;/LALR项目集 private String It=new String 2008; /LR后跟的集合 private String Iori=new Str

13、ing 25; private String Itori=new String 8; private int Icnt=new int200;/每个项目集中产生式的个数 private int Ioricnt=new int200;/每个项目集的原始产生式个数 private int Inum=0;/项目集的个数 private int Taction=new int20010; private int Tgoto=new int2005; private String mstr=null; /要分析的句子 private int escape1=new int8; /终结符要跟着输出的空格数

14、 private int escape2=new int5;/非终结符2、 First集合处理函数；public boolean FindFirst(int u,char v)/查看第u个非终结符的first集是否包含终结符v int i; for(i=0;i<firstlenu;i+) if(firstui=v) return true;/包含则返回true return false; public boolean AddFirst(int u,int v)/查看第v个非终结符的first集是否全部在第u个非终结符的first集中，若不在则添加到第u个非终结符的first集中并增加该f

15、irst集的长度 boolean flag=false; int i; for(i=0;i<firstlenv;i+) if(!FindFirst(u,firstvi)/没有找到，添加到第u个非终结符的first集中 firstufirstlenu+=firstvi; flag=true; return flag;/flag=true 说明第v个非终结符的first集是不全部在第u个非终结符的first集中，即第u个非终结符的first集有更新 public void First() throws NullPointerException try int i=0,j=0,k=0; boo

16、lean flag=true; boolean flagtemp=true;/两个变量都用来标注first集有更新，为true则需要循环直到每个非终结符的first集不在扩大 for(i=0;i<cntn;i+) firstleni=0;/每个非终结符的first集长度初始化为0 while(flag) flag=false; for(i=0;i<cntn;i+)/计算每个非终结符的first集 for(j=0;j<len;j+)/对每个产生式进行查询 if(proj.charAt(0)=mapi)/该产生式的左侧为mapi所对应的非终结符，则对该产生式的右侧进行判断 if(

17、IsT(proj.charAt(2)/判断产生式右侧的第一个字符是否为终结符，若是 if(!FindFirst(i,proj.charAt(2)/判断该终结符是否已经在第i个非终结符的first中 firstifirstleni+=proj.charAt(2);/不在，则添加到first集中 flag=true;/标志第i个非终结符的first集有更新 else/产生式右侧的第一个字符是非终结符 flagtemp=AddFirst(i,mapn.get(proj.charAt(2);/mapn.get(proj.charAt(2)是产生式右侧第一个非终结符的位置 if(flagtemp=tru

18、e) flag=true;/产生式右侧的第一个非终结符的first集不全在第i个非终结符的first中，first集有更新 /没有空产生式 因此此处没有考虑这个情况 catch(Exception e) System.out.println(e); 3、 Follow集合处理函数；public booleanFindFollow(int u,char v)/查看第u个非终结符的Follow集是否包含终结符vint i=0;for(i=0;i<followlenu;i+)if(followui=v) return true;/包含则返回truereturn false;public boo

19、lean AddFollow(int u,int v)/查看第v个非终结符的follow集是否全部在第u个非终结符的follow集中，若不在则添加到第u个非终结符的follow集中并增加该follow集的长度boolean flag=false;int i=0; for(i=0;i<followlenv;i+) if(!FindFollow(u,followvi)/没有找到，添加到第u个非终结符的follow中 followufollowlenu+=followvi; flag=true;/follow集有更新 return flag; public void Follow() thro

20、ws NullPointerException try boolean flag=true; boolean flagtemp; int i=0,j=0,k=0; for(i=0;i<cntn;i+) followleni=0;/每个非终结符的follow集长度初始化为0 follow0followlen0+='e' /'Q'的follow中有'#' while(flag) flag=false; for(i=0;i<len;i+)/对每个产生式进行查询 for(j=3;j<proi.length();j+) if(IsT(pr

21、oi.charAt(j)&&!IsT(proi.charAt(j-1)/产生式的第j个字符是终结符并且第j1个字符是非终结符 if(!FindFollow(mapn.get(proi.charAt(j-1),proi.charAt(j)/检查第j个字符是终结符是否在第j1个字符的follow集中 int t=mapn.get(proi.charAt(j-1); followtfollowlent+=proi.charAt(j);/不在则添加 flag=true; if(!IsT(proi.charAt(proi.length()-1)/产生式的最后一个字符是非终结符 int t

22、=proi.length()-1; flagtemp=AddFollow(mapn.get(proi.charAt(t),mapn.get(proi.charAt(0); if(flagtemp=true) flag=true; catch(Exception e) System.out.println(e); 4、 LR1处理函数； public void LR1() int i=0,j=0; for(i=0;i<200;i+) Icnti=0; Ioricnti=0; Inum=0;/项目集的个数 /初始化Taction和Tgoto for(i=0;i<200;i+) for(

23、j=0;j<10;j+) Tactionij=-1;/终结符个数 for(j=0;j<5;j+) Tgotoij=-1;/非终结符个数 IInumIcntInum="Q->.S" ItInumIcntInum+="e"/项目集0的第一个产生式集后跟符 Ioricnt0=1; CalLR1(0);/将项目集0进行扩大 int que=new int200;/记录项目集编号 int s=0;/最开始的项目集编号 int t=0; /s记录当前正在分析的项目集，t为当前最大的项目集编号（也为项目集个数） quet+=0; int cnttem

24、p=0; while(s<t) int stat=ques+;/指针依次往后移，对每个项目集进行分析 for(i=0;i<cntn;i+)/给一个非终结符 cnttemp=0; for(j=0;j<Icntstat;j+) int k=3; while(Istatj.charAt(k)!='.') k+; k+; if(k<Istatj.length() if(Istatj.charAt(k)=mapi)/"."后的第一个字符正好为给定的非终结符 String str1=MakeStr(stat,j);/则将"."

25、向后移一位 Ioricnttemp=str1;/新产生的项目集的初始化产生式以及后跟符 Itoricnttemp+=Itstatj; if(cnttemp>0)/cnttemp为新增项目集的初始化产生式的个数 /检查是否需要新增项目集 if(!FindIstr(cnttemp,stat,i,0)/stat原项目集编号，i为两个项目集间进行变换的移进字符编号，0代表当前移进字符为非终结符 /已经存在的项目集的初始化产生式都不与新增项目集的初始化产生式相匹配，则需要新增加项目集 for(j=0;j<cnttemp;j+) IInumj=Iorij; ItInumj=Itorij; Ic

26、ntInum=cnttemp; IoricntInum=cnttemp; CalLR1(Inum);/将新增加的项目集扩大化 quet+=Inum; Tgotostati=Inum; /goto表中填入新增加的项目集编号 Inum+;/项目集个数增加1 for(i=0;i<cntt;i+)/给一个终结符 cnttemp=0; for(j=0;j<Icntstat;j+) int k=3; while(Istatj.charAt(k)!='.') k+; k+; if(k<Istatj.length() if(Istatj.charAt(k)=(char)(&#

27、39;a'+i)/"."后的第一个字符正好为给定的终结符 String str1=MakeStr(stat,j);/则将"."向后移一位 Ioricnttemp=str1; Itoricnttemp+=Itstatj; if(cnttemp>0) /检查是否需要新增项目集 /新增项目集 if(!FindIstr(cnttemp,stat,i,1) for(j=0;j<cnttemp;j+) IInumj=Iorij; ItInumj=Itorij; IcntInum=cnttemp; IoricntInum=cnttemp; CalL

28、R1(Inum); quet+=Inum;/ Tactionstati=Inum; /action表中填入新增加的项目集编号 Inum+; 5、 合并同心集函数； public void ToOne(int u,int v)/在找到同心集的基础上 将项目集u合并到项目集v中 int i,j; int p,q; for(i=0;i<Icntu;i+) for(j=0;j<Icntv;j+) if(IpareTo(Ivj)=0) for(p=0;p<Itui.length();p+)/将相同产生式的后跟符合并，将u的后跟符放到v的后跟符中，最终v为两个合并后的后跟符

29、for(q=0;q<Itvj.length();q+) if(Itui.charAt(p)=Itvj.charAt(q) break; if(q=Itvj.length() Itvj+=Itui.charAt(p); /修改两个表 /将原表中到达u的项修改为到达状态v for(i=0;i<Inum;i+) for(j=0;j<cntt;j+) if(Tactionij=u) Tactionij=v; for(j=0;j<cntn;j+) if(Tgotoij=u) Tgotoij=v; /合并表中的u行到v行 for(i=0;i<cntt;i+) Tactionv

30、i=min(Tactionvi,Tactionui); for(i=0;i<cntn;i+) Tgotovi=min(Tgotovi,Tgotoui); 6、 LRToLALR1处理函数； public void LR1toLALR() int i=0,j=0; int point=0; for(i=1;i<Inum;i+) for(j=0;j<=point;j+) if(EqualLR(i,j) ToOne(i,j); break; /因为发现项目集时，即项目集i在前面有同心集，point指针不动，即保证point前面不会有同心集 if(j>point)/每个项目集只

31、与比它项目集编号小的状态比较，若没有发现同心集，则将项目集向point+1处编号的项目集拷贝 Move(i,point+1); point+;/将指针增加 继续与下面的项目集比较，看是否是同心集 Inum=point+1;/Inum为LALR的项目集个数 7、 生成表处理函数； public void MakeTable() /填入规约项 int i,j,k,p; for(i=0;i<Inum;i+) for(j=0;j<Icnti;j+) k=0; while(Iij.charAt(k)!='.') k+; k+; if(k=Iij.length()/说明为规约项

32、 if(Iij.charAt(0)='Q')/在是规约项的基础上检验 是接受项目 for(p=0;p<Itij.length();p+)/检验后跟符号集 int t=Itij.charAt(p)-'a'/获得后跟符号集中终结符的位置 Tactionit=1000;/1000表示接受 表中每个后跟符号所对应的列填入规约 表示遇到该终结符进行规约 else/为规约项但不是接受项目 for(p=0;p<Itij.length();p+) int t=Itij.charAt(p)-'a' String protemp=Iij.charAt(0

33、)+"-" for(int l=3;l<Iij.length()-1;l+) protemp+=Iij.charAt(l);/获得进行规约的产生式 for(int l=0;l<len;l+) if(pareTo(protemp)=0)/l为产生式所对应的位置 Tactionit=100+l;/表示用产生式l规约 8、 生成语法树处理函数； public void Analysis(String nstr) int stat=new int 50; /状态栈 int fr=-1; stat+fr=0;/状态栈初始状态 String tree=new

34、 String 100;/语法树 限制输入的串最多为100个字符, int i=0,j=0; int point=0;/指向下一个输入符号 int ttail=0; if(Trans(nstr) while(point<mstr.length() int w=mstr.charAt(point)-'a' if(Tactionstatfrw=-1)jta2.append("出错!符号串不是该文法的符号串!"); return; if(Tactionstatfrw<100)/为移进项目 statfr+1=Tactionstatfrw; fr+; tr

35、eettail+=String.valueOf(mstr.charAt(point);/? point+; else if(Tactionstatfrw>=100&&Tactionstatfrw<1000)/为规约项目 int r=Tactionstatfrw-100;/规约产生式的编号 char e=pror.charAt(0); int ee=0; for(i=0;i<cntn;i+) if(mapi=e) ee=i;/ee为规约产生式左侧的非终结符的位置 if(pror.length()=3)/只要一个字符进行规约 if(Tgotostatfr-1ee=

36、-1)jta2.append("出错!符号串不是该文法的符号串!n"); return; statfr=Tgotostatfr-1ee; for(j=ttail-1;j>=0;j-) if(treej.charAt(treej.length()-1)='-'| treej.charAt(treej.length()-1)='/'| treej.charAt(treej.length()-1)='' ) continue; treej+="-"+e; break; else/需要多个字符进行规约 int

37、 t=pror.length()-2; if(Tgotostatfr-tee=-1)jta2.append("出错!符号串不是该文法的符号串!n"); return; statfr-t+1=Tgotostatfr-tee; fr=fr-t+1; int end=0,start=0; i=0; j=ttail-1; while(i<t)/找到进行规约的最前端和最后端 while(treej.charAt(treej.length()-1)='-'| treej.charAt(treej.length()-1)='/'| treej.charAt(tr