LL1 first follow集.doc

课 程 名 称: LL1文法的判别 年级/专业/班: 11级计算机类（二）班 姓 名: 徐勇兵 学 号： E01114278 一、背景资料如果一个文法具有以下两个特点：（1） 每个产生式的右部都由终结符开始；（2） 如果两个产生式有相同的左部，那么他们的右部则由不同的终结符开始。显然对于这样的文法，其推导过程完全可以根据当前的输入符号，决定选哪个产生式往下推导，分析过程是惟一确定的，可以采用不带回溯的自上而下的预测分析方法。如果两个产生式的左部相同，而右部都由非终结符开始，例如，存在A / , 和均以非终结符开始，那么就很难决定何时使用A 选项，何时使用A选项。二、实验目的要求输入：任意的上下文无关文法。输出：所输入的上下文无关文法一切非终结符的first集合和follow集合和其空表以及对是否是LL1的判别。三、实验原理设文法GS（VN，VT，P，S），则首字符集为： FIRST（）a | a，aVT，,V *。若，FIRST（）。由定义可以看出，FIRST（）是指符号串能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。设x1x2xn，FIRST（）可按下列方法求得：令FIRST（），i1；（1） 若xiVT，则xiFIRST（）；（2） 若xiVN； 若FIRST（xi），则FIRST（xi）FIRST（）； 若FIRST（xi），则FIRST（xi）FIRST（）；（3） ii+1，重复（1）、（2），直到xiVT，（i2，3，n）或xiVN且若FIRST（xi）或in为止。当一个文法中存在产生式时，例如，存在A，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。设文法GS（VN，VT，P，S），则 FOLLOW（A）a | S Aa ，aVT。若SA，#FOLLOW（A）。由定义可以看出，FOLLOW（A）是指在文法GS的所有句型中，紧跟在非终结符A后的终结符号的集合。FOLLOW集可按下列方法求得：（1） 对于文法GS的开始符号S，有#FOLLOW（S）；（2） 若文法GS中有形如BxAy的规则，其中x，yV *，则FIRST（y）FOLLOW（A）；（3） 若文法GS中有形如BxA的规则，或形如BxAy的规则且FIRST（y），其中x，yV *，则FOLLOW（B）FOLLOW（A）；import java.util.Vector;import javax.swing.JOptionPane;class Toolspublic Vector protection(Vector vs)Vector newvector=new Vector();for(int i=0;ivs.size();i+)newvector.add(vs.get(i);return newvector;public VectorVector doubleprotection(VectorVector vs)VectorVector newvector=new VectorVector();for(int i=0;ivs.size();i+)Vector produce=(Vector)vs.get(i);Vector temp=new Vector();for(int j=0;jproduce.size();j+)temp.add(String)produce.get(j);/for jnewvector.add(temp);/for ireturn newvector;class ElementsVector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符VectorVector produce=new VectorVector();/产生式public void setend()/终结符元素添加while(true)String s=JOptionPane.showInputDialog(null,请输入终结符);if(s=null)return;/ifend.add(s);/while/public void addend()/元素添加public void setnoend()/非终结符元素添加while(true)String s=JOptionPane.showInputDialog(null,非请输入终结符);if(s=null)return;/ifnoend.add(s);/while/public void addnoend()/public void setproduce() while(true) String s=JOptionPane.showInputDialog(null,请输入产生式，-隔开); if(s=null)return; Vector temp=new Vector(); temp.add(s.split(-)0); temp.add(s.split(-)1); produce.add(temp); /while/public void addproduce()public Vector getend()return end;public Vector getnoend()return noend;public VectorVector getproduce()return duce;public void run() /*TEST*/end.add(a);end.add(b);end.add(c);end.add(e);noend.add(S);noend.add(A);noend.add(B);noend.add(C);noend.add(D); Vector temp=new Vector(); temp.add(S); temp.add(AB); produce.add(temp); /*/ Vector temp1=new Vector(); temp1.add(S); temp1.add(bC); produce.add(temp1); /*/ Vector temp2=new Vector(); temp2.add(A); temp2.add(e); produce.add(temp2); /*/ Vector temp3=new Vector(); temp3.add(A); temp3.add(b); produce.add(temp3); /*/ Vector temp4=new Vector(); temp4.add(B); temp4.add(e); produce.add(temp4); /*/ Vector temp5=new Vector(); temp5.add(B); temp5.add(aD); produce.add(temp5); /*/ Vector temp6=new Vector(); temp6.add(C); temp6.add(AD); produce.add(temp6); /*/ Vector temp7=new Vector(); temp7.add(C); temp7.add(b); produce.add(temp7); /*/ Vector temp8=new Vector(); temp8.add(D); temp8.add(aS); produce.add(temp8); /*/ Vector temp9=new Vector(); temp9.add(D); temp9.add(c); produce.add(temp9); /*/ / System.out.println(produce.size()=+produce.size();/*TEST*/this.setend();/this.setnoend();/this.setproduce();public boolean Iscontainend(String s)/正则表达式判断s1是否在END的闭包里面 正则忘了怎么写了 int length=s.length(); for(int i=0;ilength;i+) String a=+s.charAt(i); if(end.contains(a) return true; else continue; /for return false;/public boolean isRGPcontain(String s)public boolean IsNoENd(String s) String ss=+s.charAt(0); if(! Iscontainend(ss)/如果不含有终结符,则为非终结符 return true; return false; / public boolean/class Elementsclass FollowVector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符VectorVector produce=new VectorVector();/产生式VectorVector emptytable=new VectorVector();Elements elements;First first;VectorVector flagtable=new VectorVector();VectorVector followtable=new VectorVector();public void showfollowtable()for(int i=0;ifollowtable.size();i+)System.out.println();Vector temp=followtable.get(i);System.out.print(temp.get(0)+的Follow集：);for(int j=1;jtemp.size();j+)System.out.print(temp.get(j)+,);/public void showfollowtable()public Vector getAppointfollow(String s)Vector temp=new Vector();for(int i=0;ifollowtable.size();i+)temp=followtable.get(i);if(temp.get(0).equals(s)return temp;/forreturn temp;/public Vector getAppointfollow(String s)public void init_flagtableAndfollowtable()for(int i=0;inoend.size();i+)Vector temp=new Vector();temp.add(noend.get(i);temp.add(no);flagtable.add(temp);/forfor(int i=0;inoend.size();i+)Vector temp=new Vector();temp.add(noend.get(i);followtable.add(temp);/for/public void init_flagtableAndfollowtablepublic void show_flagtableAndfollowtable()System.out.println();System.out.println(flagtable is shown as follows:);for(int i=0;iflagtable.size();i+)Vector temp=flagtable.get(i);System.out.print(temp.get(0)+:+temp.get(1);System.out.println();/forSystem.out.println(followtable is shown as follows:);for(int i=0;ifollowtable.size();i+)System.out.println();Vector temp=followtable.get(i);System.out.print(temp.get(0)+:);for(int j=1;jtemp.size();j+)System.out.print(temp.get(j);/forpublic String getFlagTable(String s)for(int i=0;iflagtable.size();i+)Vector temp=flagtable.get(i);if(temp.get(0).equals(s)return temp.get(1);/forreturn no;/public String getFlagTable(String s)public void setFlagTable(String s)for(int i=0;iflagtable.size();i+)Vector temp=flagtable.get(i);if(temp.get(0).equals(s) temp.set(1,yes);/for/public String setFlagTable(String s) public boolean Isindicateempty(String s) for(int i=0;iemptytable.size();i+) Vector temp=emptytable.get(i); if(temp.get(0).equals(s) if(temp.get(1).equals(yes) return true; else return false; /if 外层 /for return false; / public boolean Isindicatefull(String s)public VectorVector getFirsrtandFollow(String s)/获得非终结符s的要加入的Follw(A)和First（a）的a和A/System.out.println(欲求+s+的相关信息);VectorVectorvs=new VectorVector();Vector first=new Vector();Vector follow=new Vector();for(int i=0;iproduce.size();i+)Vector temp=produce.get(i);String left=temp.get(0);String right=temp.get(1);/获取产生式的右部int index=right.indexOf(s);if(index!=(-1)/如果右部含有次非终结符的话if(right.length()=(index+1)/D-aS型(S为所求)follow.add(left);elseString nextchar=+right.charAt(index+1);first.add(nextchar);if(Isindicateempty(nextchar)/如果此非终结符可以产生空的话follow.add(left);/if(index!=(-1)/for/*if(first.isEmpty()=false)/如果不空System.out.println(s+firsr为:); for(int i=0;ifirst.size();i+) System.out.println(); String sb=(String)first.get(i); System.out.print(sb); /for else/System.out.println(s+的first为空); if(follow.isEmpty()=false)/如果不空System.out.println(); System.out.print(s+的follow为:); for(int i=0;ifollow.size();i+) String sb=(String)follow.get(i); System.out.print(sb); /for else/System.out.println(s+的follow为空);*/vs.add(first);vs.add(follow);return vs;public Vector addElements(Vector vs,Vectortemp)for(int i=0;itemp.size();i+)if(!vs.contains(temp.get(i) vs.add(temp.get(i); /forreturn vs;/public Vector addElements(Vector vs,Vectortemp)public Vector getFollow(String s) Vector follow=getAppointfollow(s); /System.out.println(s+的flagtable对应的是+getFlagTable(s); if(getFlagTable(s).equals(yes) /*System.out.println(返回follow集，防止死循环); System.out.println(返回follow集签先输出查看); for(int i=0;ifollow.size();i+) System.out.print(follow.get(i)+,); System.out.println();*/ Vector kk=new Vector(); for(int i=1;ifollow.size();i+) kk.add(follow.get(i); return kk; setFlagTable(s);/将flagtable的对应表项置为yes String Start_Characrter=S; if(s.equals(Start_Characrter) /System.out.println(follow加入了#); follow.add(#); VectorVector vs=getFirsrtandFollow(s); /show_flagtableAndfollowtable(); Vector firstcharacter=vs.get(0); Vector followcharacter=vs.get(1); System.out.println(); /System.out.println(111111111111111111); if(firstcharacter.isEmpty()=false)/如果不空 for(int i=0;ifirstcharacter.size();i+) String sb=(String)firstcharacter.get(i); Vector vv= first.getFirst(sb); follow=addElements(follow,vv); /for if(followcharacter.isEmpty()=false)/如果不空 for(int i=0;ifollowcharacter.size();i+) String sb=(String)followcharacter.get(i); Vector vv= getFollow(sb); follow=addElements(follow,vv); /for follow.remove(e); Vector kk=new Vector(); for(int i=1;ifollow.size();i+) kk.add(follow.get(i); /return follow; return kk; public Follow(Elements _elements,VectorVector _emptytable,First _first)this.elements=_elements;this.emptytable=_emptytable;this.first=_first;this.end=elements.getend();this.noend=elements.getnoend();duce=elements.getproduce();init_flagtableAndfollowtable();/class followclass FirstVector end=new Vector();/表示终结符Vector noend=new Vector();/表示非终结符VectorVector produce=new VectorVector();/产生式VectorVector emptytable=new VectorVector();Elements elements;public First(Elements _elements,VectorVector _emptytable)this.elements=_elements;this.emptytable=_emptytable;this.end=elements.getend();this.noend=elements.getnoend();duce=elements.getproduce();public Vector getRight(String left) Vector right=new Vector(); for(int i=0;iproduce.size();i+) Vectortemp=produce.get(i); if(temp.get(0).equals(left) right.add(temp.get(1); /for return right;/public String getRight(String left)public Vector addElements(Vector vs,Vectortemp)for(int i=0;itemp.size();i+)if(!vs.contains(temp.get(i) vs.add(temp.get(i); /forreturn vs;/public Vector addElements(Vector vs,Vectortemp) public boolean Isindicateempty(String s) for(int i=0;iemptytable.size();i+) Vector temp=emptytable.get(i); if(temp.get(0).equals(s) if(temp.get(1).equals(yes) return true; else return false; /if 外层 /for return false; / public boolean Isindicatefull(String s) public boolean IsNoENd(String s) String ss=+s.charAt(0); if(! elements.Iscontainend(ss)/如果不含有终结符,则为非终结符 return true; return false; / public boolean public boolean IsStartWithEnd(String s)/判断是否以终结符开头 String ss=+s.charAt(0); if( elements.Iscontainend(ss) return true; return false; public Vector getFirst(String s) Vector vs=new Vector(); int ii=0; if(IsStartWithEnd(s) vs.add(+s.charAt(0); if(s.length()=1&IsNoENd(s)/形如 Fisst（A） Vector temp=getRight(s); for(int i=0;itemp.size();i+) vs=addElements(vs,getFirst(temp.get(i); /for /if if(s.length()!=1)/形如First(AB)或者First(AaB) for(ii=0;iis.length();ii+) String ss=+s.charAt(ii); if(Isindicateempty(ss)/如果能退出空 Vector temp=getFirst(ss); if(temp.contains(e)/如果有空则删除 temp.remove(e); vs=addElements(vs,temp); /if elsevs=addElements(vs,getFirst(ss);break; /for if(ii=s.length()/如果所有的非终结符都能退出空，则将e加入 vs.add(e); /if if(s.length()!=1)/形如First(AB)或者First(AaB) return vs; /class Firstclass SelectElements elements;First first;Follow follow;Emptytable emptytable;Vector end;Vector noend;VectorVector produce;VectorVector flagtable=new VectorVector();VectorVector followtable=new VectorVector();public Select(Elements _elements,Emptytable _emptytable,First _first,Follow _follow)this.elements=_elements;this.emptytable=_emptytable;this.end=elements.getend();this.noend=elements.getnoend();duce=elements.getproduce();this.first=_first;this.follow=_follow;init_flagtable();public void showselecttable()for(int i=0;iproduce.size();i+)Vector temp=produce.get(i);System.out.println();System.out.print(产生式+temp.get(0)+-+temp.get(1)+的select集是：);Vector select=getselect(temp);for(int j=0;jselect.size();j+)System.out.print(select.get(j)+,);public Vector addElements(Vector vs,Vectortemp)for(int i=0;itemp.size();i+)if(!vs.contains(temp.get(i) vs.add(temp.get(i); /forreturn vs;/public Vector addElements(Vector vs,Vectortemp) public VectorVector getallproduces(String left)/返回以left为左部的所有产生式 VectorVector vs=new VectorVector(); for(int i=0;iproduce.size();i+) Vector temp=produce.get(i); if(temp.get(0).equals(left) vs.add(temp); return vs; public void init_flagtable()for(int i=0;inoend.size();i+)Vector temp=new Vector();temp.add(noend.get(i);temp.add(no);flagtable.add(temp);/for/public void init_flagtable public String getFlagTable(String s)for(int i=0;iflagtable.size();i+)Vector temp=flagtable.get(i);if(temp.get(0).equals(s)return temp.get(1);/forreturn no;/public String getFlagTable(String s) public void setFlagTable(String s)for(int i=0;iflagtable.size();i+)Vector temp=flagtable.get(i);if(temp.get(0).equals(s) temp.set(1,yes);/for/public String setFlagTable(String s) public boolean IsIndicateEmpty(String right)/判断产生式右部是否可以推出空 for(int i=0;ie continue; if(elements.Iscontainend(vv)/如果含有除e以外的终结符 /System.out.pr